Gzip decompression in 250 lines of Rust

https://iev.ee/blog/gzip-decompression-in-250-lines-of-rust/

by vismit2000 • 4 months ago

127 40 4 months ago

iev.ee

MisterTea• 4 months ago

twenty five thousand lines of pure C not counting CMake files. ...

Keep in mind this is also 31 years of cruft and lord knows what.

Plan 9 gzip is 738 lines total:

  gzip.c 217 lines
  gzip.h 40 lines
  zip.c  398 lines
  zip.h  83 lines

Even the zipfs file server that mounts zip files as file systems is 391 lines.

edit - post a link to said code: https://github.com/9front/9front/tree/front/sys/src/cmd/gzip

... (and whenever working with C always keep in mind that C stands for CVE).

Sigh.

tyingq2• 4 months ago

His also omits CRC, which is part of the 25k lines, no --fast/--best/etc, missing some output formats, and so on. I'm sure the 25k includes a lot of bloat, but the comparison is odd. Comparing to your list would make much more sense.

kibwen3• 4 months ago

I would expect a CRC to add a negligible number of lines of code. The reason that production-grade decompressors are tens of thousands of LOC is likely attributable to extreme manual optimization. For example, I wouldn't be surprised if a measurable fraction of those lines are actually inline assembly.

fullstop• 4 months ago

gzip also contains a significant amount of compatibility code for different platforms.

xxs2• 4 months ago

Crc32 can be written in handful lines of code. Although it'd be better to use the vector instruction set - e.g. AVX when available.

bboozzoo• 4 months ago

You forgot to include https://github.com/9front/9front/tree/front/sys/src/libflate which gzip is built around, which brings it closer to 10k lines.

carlos2562• 4 months ago

Interesting, the decompressor in Jdeflate is around 4k LoC. https://github.com/Jpn666/jdeflate

commandlinefan• 4 months ago

I wrote a standalone gzip decompressor in about 500 lines of code (including comments, with braces on the next line), with no dependencies at all: https://commandlinefanatic.com/cgi-bin/showarticle.cgi?artic...

nayuki2• 4 months ago

Just like that author, many years ago, I went through the process of understanding the DEFLATE compression standard and producing a short and concise decompressor for gzip+DEFLATE. Here are the resources I published as a result of that exploration:

* https://www.nayuki.io/page/deflate-specification-v1-3-html

* https://www.nayuki.io/page/simple-deflate-decompressor

* https://github.com/nayuki/Simple-DEFLATE-decompressor

uasi• 4 months ago

Those resources were a huge help when I was digging into the DEFLATE algorithm, thank you!

up2isomorphism• 4 months ago

Another dev who doesn’t show respect to what has been done and expect a particular language will do wonders for him. Also I don’t see this is much better in term of readability.

hybrid_study• 4 months ago

he does mention https://github.com/trifectatechfoundation/zlib-rs not just https://github.com/madler/zlib, but it would be interesting to hear from those developers also

maverwa• 4 months ago

Where do you see the lack of respect? The author wanted to learn how gzip works and chose to implement it in a language they like to do so. As a learning tool, not because the world needs another gzip decompressor.

mianos• 4 months ago

Chose to paste the C into an LLM and said 'make it rust'?

stgn• 4 months ago

so i wrote a gzip decompressor from scratch

After skimming through the author's Rust code, it appears to be a fairly straightforward port of puff.c (included in the zlib source): https://github.com/madler/zlib/blob/develop/contrib/puff/puf...

dymk• 4 months ago

This feels like it should have been mentioned in the article.

It makes me wonder if there was some LLM help, based on how similar the fn structure and identifier names are.

f1shy• 4 months ago

It makes me wonder if there was some LLM help

I would bet there was

fuhsnn• 4 months ago

This feels like it should have been mentioned in the article.

With an entire section complaining how many lines of code existing implementations are, looks like they did found a good simple implementation to clone in Rust then deliberately not mention it.

bitbasher• 4 months ago

You could say it was a “puff” piece, eh, eh!?

cmovq• 4 months ago

Even the function names are identical :/

Rexxar2• 4 months ago

The difference in size seems to be mainly due to the missing documentation before each function.

ieviev• 4 months ago

Oh i didnt even know of this. But i got a lot of help from this one

https://github.com/madler/infgen

EDIT: Didnt notice that it’s even by the same person of course it’s very similar

pseudohadamard• 4 months ago

Meh, I've written a gzip decompressor in two lines of shell script:

  #!/bin/sh
  gzip -d $@

Lerc3• 4 months ago

The function

  fn bits(&mut self, need: i32) -> i32 { ....

Put me in mind of one of my early experiments in Rust. It would be interesting to compare a iterator based form that just called .take(need)

I haven't written a lot of Rust, but one thing I did was to write an iterator that took an iterator of bytes as input and provided bits as output. Then used an iterator that gave bytes from a block of memory.

It was mostly as a test to see how much high level abstraction left an imprint on the compiled code.

The dissasembly showed it pulling in 32 bits at a time and shifting out the bits pretty much the same way I would have written in ASM.

I was quite impressed. Although I tested it was working by counting the bits and someone critizised it for not using popcount, so I guess you can't have everything.

kibwen3• 4 months ago

I tested it was working by counting the bits and someone critizised it for not using popcount

PSA: Rust exposes the popcnt intrinsic via the `count_ones` method on integer types: https://doc.rust-lang.org/std/primitive.u32.html#method.coun...

Lerc3• 4 months ago

Looks like that was added about 3 years after I wrote my test code.

evmar• 4 months ago

I had a similar experience implementing simd instructions in my emulator, where I needed to break apart a 64-bit value into four eight-bit values, do an operation on each value, then pack it back together. My first implementation did it with all the bit shifts you’d expect, but my second one used two helpers to unpack into an array, map on the array to a second array, and pack the array again. The optimized output was basically the same.

carlos2562• 4 months ago

the only flag we care about is FNAME The specification does not define an encoding for the file name. Different file systems may impose restrictions on certain names, so FNAME should not be used.

jmmv• 4 months ago

I was reading this and couldn't stop thinking https://en.wikipedia.org/wiki/Literate_programming

socalgal2• 4 months ago

that reminds me a zip file creator in a few lines of JS. Now that CompressionStream is a built in feature of the browser and node. No need to use some bloated npm lib. But momentum and popularity (and LLMs) will keep people using JSZip for eternity

Gzip decompression in 250 lines of Rust

Related Stories