Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How are zlib, gzip and Zip related? (2013)

stackoverflow.com

Post reply on HN
Print view View original

111–120 of 145 posts

Re: How are zlib, gzip and Zip related? (2013)

#111

Post by rsneekes »

WoodenChair wrote: post #109
kimmel wrote: post #102

Earlier quoted context omitted.

This is covered in the BBS Documentary[1]. A comparison of Phil Katz work showed he just renamed variables and moved things around. Phil rallied the BBS community to character assassinate Thom. The documentary is shot years later and Thom still breaks down and cries when talking about what happened. It is very sad. [1] http://bbsdocumentary.com/

Crazy how that documentary appears to be not for sale in any form and DVDs on Amazon go for $3xx. Am I missing something?

The page says: "Enhanced Digital Downloads of the BBS Documentary series are planned. Please sign up here: sales@bbsdocumentary.com if you wish to be notified."

But it appears to be on YouTube: https://www.youtube.com/playlist?list=PL2B9EF89CE228ED0A

Re: How are zlib, gzip and Zip related? (2013)

#112

Post by ww520 »

kbenson wrote: post #77
ww520 wrote: post #41

Earlier quoted context omitted.

The tar.gz format is to combine a collection of files first as a single tar file and then compress the one file into gz. It's not compressing individual file and then combing the compressed files into a tar. Accessing the last file requires decompressing the whole archive. What you described is the zip format. Both zip and gz use the DEFLATE algorithm so there's no difference in compression. The difference is in how…

> It's not compressing individual file and then combing the compressed files into a tar. Accessing the last file requires decompressing the whole archive. Yes, that is the whole point of this discussion. This limitation causes problems for some. > What you described is the zip format. That is not the zip format. Zip is a collection of file objects with uncompressed headers which specify the metadata and size of the c…

> The benefit would be that since the index is just another file in the tar, you can uncompress the format from a plain tar command with no negative consequences besides an extra file being present (the index).

I still don't get how you can extract the index file from the tar.gz without uncompressing the whole gzipped archive first. Plus I believe you cannot extract a file from a tar archive without extracting all the files first (I could be wrong here.)

Re: How are zlib, gzip and Zip related? (2013)

#113

Post by eln1 »

gopalv wrote: post #27
404-universe wrote: post #4

Where do the other popular compression utilities (e.g. bzip2, xzip, lzma, 7zip) fit in to this?

The big picture is that there's a few compression algorithms. Run Length Encoding Huffman Encoding Lempel Ziv (LZ77) Burrows Wheeler Transform The interesting part of all these specific implementations is their own specialized way of extending or combining these algorithms for their own niche (or tradeoff point). Bzip2 is for example, compresses really well because BWT is expensive, but clever - rzip extends the LZ p…

Beside Huffman coding, there is also arithmetic/range coding and now is becoming widely used ANS coding - e.g. LZFSE (Apple), ZSTD (Facebook), VP10 (Google): http://encode.ru/threads/2078-List-of-Asymmetric-Numeral-Sys...

Re: How are zlib, gzip and Zip related? (2013)

#114

Post by digi_owl »

The last few days i find myself wondering if there needs to be some kind of org set up to preserve this sort of info.

Right now it seems to be strewn across a myriad of blogs, forums and whatsnot that risk going poof. And even if the Internet Archive picks them up, it is anything but curated (unlike say wikipedia, even with all the warts).

Re: How are zlib, gzip and Zip related? (2013)

#115

Post by kbenson »

ww520 wrote: post #110
kbenson wrote: post #77

Earlier quoted context omitted.

> It's not compressing individual file and then combing the compressed files into a tar. Accessing the last file requires decompressing the whole archive. Yes, that is the whole point of this discussion. This limitation causes problems for some. > What you described is the zip format. That is not the zip format. Zip is a collection of file objects with uncompressed headers which specify the metadata and size of the c…

> The stream format works in blocks of up to 65k. Can you point to where in the gzip or DEFLATE spec having that stipulation? The gzip format doesn't store the compressed data length, nor the offset of the compressed data blobs. It just has the header and then the blobs of DEFLATE compressed data, one after another. That's why it's good for streaming. Same thing with DEFLATE. It's just a series of arbitrary size comp…

> Can you point to where in the gzip or DEFLATE spec having that stipulation?

You are correct, I was misreading the stream format. There's a mode in it that mentioned 65k of data, and I was misreading what I saw (rather badly, at that). That said, it looks like, since deflate duplicate string reduction portion (LZ77 in gzip) references a sequence of bytes in the prior 32k, you could make sure to read at least 32k prior to the point you want to start looking at, and that would be covered. Unfortunately, the location of the huffman table looks to be the sticking point. If it was one large block, that would be easy, read some of the front, but it's probably not as easy as that, depending on how tar adds files.

> The gzip format doesn't store the compressed data length, nor the offset of the compressed data blobs.

I wasn't expecting it to store the offset, but I was incorrectly interpreting that it had a max length, which meant you could likely find it with high assurance.

I'm going to look deeper into the specifics of the huffman table, where it can/must be within the block, and how tar handles adding files to a compressed archive (does it add another block, or extend the existing one?) and when compressing in general (does tar arbitrarily limit deflate stream block sizes?). I'm not super confident it's possible, otherwise I imagine someone would have done it.

Re: How are zlib, gzip and Zip related? (2013)

#116

Post by kbenson »

ww520 wrote: post #112
kbenson wrote: post #77

Earlier quoted context omitted.

> It's not compressing individual file and then combing the compressed files into a tar. Accessing the last file requires decompressing the whole archive. Yes, that is the whole point of this discussion. This limitation causes problems for some. > What you described is the zip format. That is not the zip format. Zip is a collection of file objects with uncompressed headers which specify the metadata and size of the c…

> The benefit would be that since the index is just another file in the tar, you can uncompress the format from a plain tar command with no negative consequences besides an extra file being present (the index). I still don't get how you can extract the index file from the tar.gz without uncompressing the whole gzipped archive first. Plus I believe you cannot extract a file from a tar archive without extracting all th…

No, you can extract specific files from a tar archive. I believe it skips through the tar file object headers, which include file length, so it only has to read the headers. That said, there are problems with my proposal, as you pointed out elsewhere here.

Re: How are zlib, gzip and Zip related? (2013)

#117

Post by ww520 »

kbenson wrote: post #115
ww520 wrote: post #110

Earlier quoted context omitted.

> The stream format works in blocks of up to 65k. Can you point to where in the gzip or DEFLATE spec having that stipulation? The gzip format doesn't store the compressed data length, nor the offset of the compressed data blobs. It just has the header and then the blobs of DEFLATE compressed data, one after another. That's why it's good for streaming. Same thing with DEFLATE. It's just a series of arbitrary size comp…

> Can you point to where in the gzip or DEFLATE spec having that stipulation? You are correct, I was misreading the stream format. There's a mode in it that mentioned 65k of data, and I was misreading what I saw (rather badly, at that). That said, it looks like, since deflate duplicate string reduction portion (LZ77 in gzip) references a sequence of bytes in the prior 32k, you could make sure to read at least 32k pri…

See [1] for arbitrary block size during compression, [2] for the requirement of a decompressor to handle arbitrary block size.

The 32K back distance just limits how far back to use the duplicate data from the current cursor. It doesn't really limit the block size.

The last I looked, it's really difficult to find the boundary of a Huffman block since the Huffman alphabet code is not on 8-bit boundary. Walking the bits to find the end code symbol is basically decompressing the whole block.

Tar doesn't compress data. It just packages files into an archive. Gzip then applies compression on the resulting archive. Tar works well with gzip because both can stream data. It just pipes the archiving data to gzip for on the fly compression.

Adding an index table for file metadata at the end of the archive is a good idea, but then that's what zip does, so might as well use that. That's why we end up with two popular formats: gzip for streaming, zip for random access.

[1] https://www.w3.org/Graphics/PNG/RFC-1951#overview [2] https://www.w3.org/Graphics/PNG/RFC-1951#formatcompliance

Re: How are zlib, gzip and Zip related? (2013)

#118

Post by kbenson »

ww520 wrote: post #117
kbenson wrote: post #115

Earlier quoted context omitted.

> Can you point to where in the gzip or DEFLATE spec having that stipulation? You are correct, I was misreading the stream format. There's a mode in it that mentioned 65k of data, and I was misreading what I saw (rather badly, at that). That said, it looks like, since deflate duplicate string reduction portion (LZ77 in gzip) references a sequence of bytes in the prior 32k, you could make sure to read at least 32k pri…

See [1] for arbitrary block size during compression, [2] for the requirement of a decompressor to handle arbitrary block size. The 32K back distance just limits how far back to use the duplicate data from the current cursor. It doesn't really limit the block size. The last I looked, it's really difficult to find the boundary of a Huffman block since the Huffman alphabet code is not on 8-bit boundary. Walking the bits…

> The 32K back distance just limits how far back to use the duplicate data from the current cursor. It doesn't really limit the block size.

Yes, which is a problem because the huffman encoding tree is at the begiing of the block (I believe). except for that, for LZ77 I believe it doesn't really matter when the block begins, because the deduplication is based on prior occurrences (within 32k), so as long as you have that prior 32k, the relative distance to the original should be within the data you have.

> The last I looked, it's really difficult to find the boundary of a Huffman block since the Huffman alphabet code is not on 8-bit boundary. Walking the bits to find the end code symbol is basically decompressing the whole block.

Yes, which is why I was talking about how the gzipping is done (usually by tar itself), and how files are added. If it's all one big block, or blocks of set size, that would be useful to know.

> Tar doesn't compress data.

At one point that was true. Then they added flags to tar to allow tar to handle the compression at the same time. At this point, I would hazard most tar.gz files are compressed by tar itself using zlib.

> It just pipes the archiving data to gzip for on the fly compression.

Yes, but since it's all internal to the program, they have control oh how they do that. It's entirely possible (if somewhat unlikely) that tar by default compresses using a deflate stream and chunks it in specific maximum size blocks, or one large block. The question then is, when appending a file to a compressed archive through tar and letting it handle the compression steps, what does it look like? Is it an added deflate stream block (which seems easiest)?

> Adding an index table for file metadata at the end of the archive is a good idea, but then that's what zip does, so might as well use that. That's why we end up with two popular formats: gzip for streaming, zip for random access.

Well, I would say we ended up with two popular formats because tar preexisted zip be a decade, and tar works well with UNIX files while zip had some problems (initially). I'm not sure if zip files currently support some of the more esoteric UNIX file types (sockets, devices). I assume they worked that out when they got UNIX permissions working correctly. Unfortunately, since the headers are uncompressed, you end up with a bunch of separate compression chunks, which isn't efficient for lots of small files.

Re: How are zlib, gzip and Zip related? (2013)

#119

Post by greggman »

bluedino wrote: post #38
greggman wrote: post #28

Earlier quoted context omitted.

You can't put the header first. It is an intentional feature of .zip that the header is at the end so you can update a large zip file by just appending a new header to the end. That way the entire file does not have to be rewritten. Just read the old header, append new files, append new header. This was important back in floppy disk days

>> Just read the old header, append new files, append new header. This was important back in floppy disk days Don't forget 'overwrite old header' Important for floppy disks in two ways, one because of space constraints and two, because of how slow floppies were.

You don't have to overwrite the old header. Concat any zip files you want and feed them to conforming deconpressors and they correctly extract only the last headers files.

If you didn't only look at the last header then you'd have the issue that I can store fake headers as uncompressed content (type 0) and your unzip util would screw up

Re: How are zlib, gzip and Zip related? (2013)

#120

Post by ww520 »

kbenson wrote: post #118
ww520 wrote: post #117

Earlier quoted context omitted.

See [1] for arbitrary block size during compression, [2] for the requirement of a decompressor to handle arbitrary block size. The 32K back distance just limits how far back to use the duplicate data from the current cursor. It doesn't really limit the block size. The last I looked, it's really difficult to find the boundary of a Huffman block since the Huffman alphabet code is not on 8-bit boundary. Walking the bits…

> The 32K back distance just limits how far back to use the duplicate data from the current cursor. It doesn't really limit the block size. Yes, which is a problem because the huffman encoding tree is at the begiing of the block (I believe). except for that, for LZ77 I believe it doesn't really matter when the block begins, because the deduplication is based on prior occurrences (within 32k), so as long as you have t…

In the risk of dragging this too far, tar is just a command line front end to gzip. It just forks gzip in a child process to pipe data to it. No zlib is involved.

The archive.tar.gz means tar the files into archive.tar, then gzip it into archive.tar.gz. You can run gzip -d to get back archive.tar. Tar -czf is just a shortcut command.

Tar cannot change the file format of .tar.gz. Otherwise, gzip -d won't work.

Post reply on HN