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

Dissecting the gzip format (2011)

infinitepartitions.com

Post reply on HN
Print view View original

51–60 of 68 posts

Re: Dissecting the gzip format (2011)

#51

Post by lifthrasiir »

lxgr wrote: post #50
umvi wrote: post #36

Earlier quoted context omitted.

> at the same compression time/decompression time as gzip In my experience zstd is considerably faster than gzip for compression and decompression, especially considering zstd can utilize all cores. gzip is inferior to zstd in practically every way, no contest.

Practically, compatibility matters too, and it's hard to beat gzip there.

The benefit from zstd is however so great that I even copied the zstd binary to some server I was managing but couldn't easily compile it from scratch. Seriously, bundling zstd binary is that worthy by now.

Re: Dissecting the gzip format (2011)

#52

Post by 0d0a »

mbreese wrote: post #45
Arkanosis wrote: post #42

Earlier quoted context omitted.

On top of enabling indexing, it reduces the amount of data lost in the event of data corruption — something you get for free with block-based compression algorithms like BWT-based bzip2 but is most of the time missing from dictionary-based algorithms like LZ-based gzip. I don't think many people use that last property or are even aware of it, which is a shame. I wrote a tool (bamrescue) to easily recover data from un…

Why do you think I wanted to add hashes and encryption at the block level? :) I’ve had to do similar things in the past and it’s a great side-feature of the format. It’s a horrible feeling when you find a corrupted FASTQ file that was compressed with normal gzip. At least with bgzip corrupted files, you can find and start recovery from the next block.

Even if it doesn't use block-based compression, if there isn't a huge range of corrupted bytes, corruption offsets are usually identifiable, as you will quickly end up with invalid length-distance pairs and similar errors. Although, errors might be reported a few bytes after the actual corruption.

I was motivated some years ago to try recovering from these errors [1] when I was handling a DEFLATE compressed JSON file, where there seemed to be a single corrupted byte every dozen or so bytes in the stream. It looked like something you could recover from. If you output decompressed bytes as the stream was parsed, you could clearly see a prefix of the original JSON being recovered up to the first corruption.

In that case the decompressed payload was plaintext, but even with a binary format, something like kaitai-struct might give you an invalid offset to work from.

For these localized corruptions, it's possible to just bruteforce one or two bytes along this range, and reliably fix the DEFLATE stream. Not really doable once we are talking about a sequence of four or more corrupted bytes.

[1]: https://github.com/nevesnunes/deflate-frolicking

Re: Dissecting the gzip format (2011)

#53

Post by mxmlnkn »

082349872349872 wrote: post #19
userbinator wrote: post #2

Besides a persistent off-by-one error, and the use of actual trees instead of table lookup for canonical Huffman, this is a pretty good summary of the LZ+Huffman process in general; and in the 80s through the mid 90s, this combination was widely used for data compression, before the much more resource-intensive adaptive arithmetic schemes started becoming popular. It's worth noting that the specifics of DEFLATE were…

I'd agree with TFA that canonical Huffman, although interesting, would be yet another thing to explain, and better left out of scope, but it does raise a question: In what other areas (there must be many) do we use trees in principle but sequences in practice? (eg code: we think of it as a tree, yet we store source as a string and run executables which —at least when statically linked— are also stored as strings)

> In what other areas (there must be many) do we use trees in principle but sequences in practice?

Heapsort comes to mind first.

Re: Dissecting the gzip format (2011)

#54

Post by qhwudbebd »

zie wrote: post #33
gloflo wrote: post #14

Earlier quoted context omitted.

... --auto-compress ... foo.tar.zstd

That's cool! Is that a GNU tar only thing? Based on it being a longopt, I'm guessing a GNU tar only thing. That's the problem with these things, it takes a while to get pushed to all the installed copies of tar running around. Perhaps it's time to check: * MacOS Sonoma(14.6) has tar --auto-compress and --zstd * OpenBSD tar does not appear to have it: https://man.openbsd.org/tar * FreeBSD does: https://man.freebsd.org…

Both libarchive ("bsdtar") and GNU tar have -a, which I guess are the only two upstream tar implementations that are still relevant? You're right, it can take a while for these things to propagate downstream though.

Re: Dissecting the gzip format (2011)

#55

Post by qhwudbebd »

duskwuff wrote: post #10
masklinn wrote: post #8

Earlier quoted context omitted.

TBF zstd runs most of the gamut, so depending on your settings you can have it run very fast at a somewhat limited level of compression or much lower at a very high compression. Bzip is pretty completely obsolete though. Especially because of how ungodly slow it is to decompress.

> TBF zstd runs most of the gamut Yep. But bzip2 is much less flexible; reducing its block size from the default of 900 kB just reduces its compression ratio. It doesn't make it substantially faster; the algorithm it uses is always slow (both to compress and decompress). There's no reason to use it when zstd is available.

I agree about the practical utility of bzip2. It's quite an interesting historical artefact, though, as it's the only one of these compression schemes that isn't dictionary-based. The Burrows-Wheeler transform is great fun to play with.

Re: Dissecting the gzip format (2011)

#56

Post by PROMISE_237 »

zie wrote: post #9
hk1337 wrote: post #6

Why do people use gzip more often than bzip? There must be some benefit but I don’t really see it, you can split and join two bzipped files (presumably CSV so you can see the extra rows). Bzip seems to compress better than gzip too.

Muscle memory. We've been doing gzip for decades and we are too lazy to remember the zstd commands to tar, assuming the installed version of tar has been updated.

[dead]

Re: Dissecting the gzip format (2011)

#58

Post by 082349872349872 »

commandlinefan wrote: post #35
082349872349872 wrote: post #11

Has anyone taken the coding as compression (when you create repeated behaviour, stuff it in the dictionary via creating a function; switching frameworks is changing initial dicts; etc.) metaphor seriously?

Sounds like LZW compression to me - is what you're thinking of different than that?

Different in terms of applying the same principle to produce "semantically compressed" code — instead of having each new dictionary entry be a reference to an older one along with the new symbol, each new function will refer to older ones along with some new literal data.

(If that still doesn't make sense, see the sibling comment to yours.)

Re: Dissecting the gzip format (2011)

#59

Post by egorpv »

mbreese wrote: post #26
Filligree wrote: post #20

One of my favorite gzip party tricks is that (ungzip (cat (gzip a) (gzip b))) == (cat a b). That is to say, the concatenation of two gzip streams is still a valid gzip file. This hasn't ever been practically useful, but it means you can trivially create a 19-layer gzip file containing more prayer strips than there are atoms in the universe, providing a theological superweapon. All you need to do is write it to a USB-…

In bioinformatics we use a modified gzip format called bgzip that exploits this fact heavily. The entire file is made of concatenated gzip chunks. Each chunk then contains the size of the chunk (stored in the gzip header). This lets you do random access inside the compressed blocks more efficiently. Sadly, the authors hard coded the expected headers so it’s not fully gzip compatible (you can’t add your own arbitrary…

In such case, imo, it would be more appropriate to use ZIP container format which supports multiple independent entries (files) and index table (including sizes) for them. Compression algorithm is essentially the same (Deflate) so it would not be bloated in any way. As for practical implementations of serializing complex "objects" into ZIP, numpy [0] can be mentioned as an example.

[0] https://numpy.org/doc/stable/reference/generated/numpy.savez...

Re: Dissecting the gzip format (2011)

#60

Post by lxgr »

lifthrasiir wrote: post #51
lxgr wrote: post #50

Earlier quoted context omitted.

Practically, compatibility matters too, and it's hard to beat gzip there.

The benefit from zstd is however so great that I even copied the zstd binary to some server I was managing but couldn't easily compile it from scratch. Seriously, bundling zstd binary is that worthy by now.

If you can control both sides, definitely go for it!

But in many cases, we unfortunately can't (gzip/Deflate is baked into tons of non-updateable hardware devices for example).

Post reply on HN