3 ms·

> 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 th

by ww520 10y ago

> 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 compressed data blocks. With a dictionary upfront for dynamic Huffman and no dictionary for static Huffman. You read as much data as you can to decompress until encountering the ending Huffman symbol, where you arrive at the next block. The 65K limit is for non-compress type block, which is not useful in the scheme of things. There's no well known magic signature bytes to search for a DEFLATE header.

kbenson 10y ago
> 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.
- ww520 10y ago
  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 https://www.w3.org/Graphics/PNG/RFC-1951#overview [2] https://www.w3.org/Graphics/PNG/RFC-1951#formatcompliance https://www.w3.org/Graphics/PNG/RFC-1951#formatcompliance
  - kbenson 10y ago
    > 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.

by ww520 10y ago

kbenson 10y ago

> 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.

ww520 10y ago
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 https://www.w3.org/Graphics/PNG/RFC-1951#overview [2] https://www.w3.org/Graphics/PNG/RFC-1951#formatcompliance https://www.w3.org/Graphics/PNG/RFC-1951#formatcompliance
- kbenson 10y ago
  > 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.