A lossless compressed morning
by Danny Willems
While working on the zkVM project for Optimism with O(1) Labs, I noticed that
zlib was used to decompress the memory, encoded in base64. I opened a PR to
decode the state.json that Cannon load-elf command produces, and I was a bit
lost in the different library in Rust implementing zlib (called zeta-lib!).
There are flate2 and
libflate. Oh, wait. What is zlib? What are
these libraries? Ok. Let’s learn about compression. I’ve never been into the
theory of it, neither implement any compression algorithm. Also, I ran into an
error while trying to use flate2, and I did not know what was happening. And I
don’t like when I don’t understand.
Therefore, I woke up the next day (today…), and while I was waiting for my
first coffee, I started YouTube-ing: zlib compression. Ok, found
Elegant Compression in Text (The LZ 77 Method) - Computerphile.
Nice introduction, better than the sum of all naturals are -1/12… Anyway.
Coffee is now ready. Let’s get my breakfast. Let’s watch another one while
eating.
How Computers Compress Text: Huffman Coding and Huffman Trees
is the next one.
So, Huffman Coding and Huffman trees. Fascinating! Very smart about the encoding of the letters. Never saw that before. As said in the video, instead of working with single letter, let’s work with words.
Lempel-Ziv 77 algorithm is a good reading, starting with the Wikipedia article
It drives me to the DEFLATE algorithm. Ah, nice! I know where flate comes from
now. Ok. Flate is sometimes used to call the DEFLATE algorithm.
It seems to be the basics of compression.
Ok, but what about zlib now? zlib is an implementation of the DEFLATE algorithm, and it is used in a lot of different softwares. The wikipedia article mentions a bunch of them.
What about zip, gzip, etc?
- gzip (GNU zip) is a file format, and also the related software implementing
it. Good reading is
the wikipedia article. The filename
extension is
gz - zip is another file format. Good reading is the [wikipedia article](https://en.wikipedia.org/wiki/ZIP_(file_format).
After quickly reading this, came the question of archiving formats, like tar. So, tar means Tape Archive. Interesting… Sounds like something that can go on savoir-inutile.
Therefore, for a structured, in-order, first crash course on compression:
- Huffman coding
- LZ-77 & LZ-78
- DEFLATE algorithm and the corresponding RFC 1951.
- zlib, the most used implementation of DEFLATE
- File formats: gzip, zip.
- Archive formats and other compression formats.