deflate implementation in standard library

[andrewrk]

These compression and decompression functions are so common that we should have them ship with the compiler. We'll probably need to depend on them for the package manager.

[itsmontoya]

Commenting here since Github won't let me be assigned.

I'll try to look into this asap

[daurnimator]

@itsmontoya @schmee did either of you get anywhere on this issue?

[devzero]

I didn't write it, but I found this: https://github.com/tiehuis/zig-deflate that looks pretty far along

[emekoi]

the implementation that is based on isn't designed for speed.

[schmee]

@daurnimator I'm messing around with it but no promises about when/if I'll be done. So if someone else wants to work on this please feel free! 🙂

[daurnimator]

Once this is done it should be used so that we can store the glibc data compressed (see #2847 (comment) )

[andrewrk]

This is a really nice article on the subject: https://www.hanshq.net/zip.html

[mlarouche]

I'll writing one for PNG support in zigimg

[iamgreaser]

Currently working on an implementation myself. I've got decompression working (it's about 1/4 of the speed of gunzip although it doesn't write to an actual output file yet), and I started working on a compressor yesterday, although that hasn't been pushed yet.

https://github.com/iamgreaser/deflate-for-zig/

I can be found on #zig under the name GreaseMonkey, if you have any suggestions then let me know.

[mlarouche]

My current progress is here: https://github.com/mlarouche/zigimg/blob/ReadPNGSupport/src/compression/deflate.zig Haven't mesured performance yet

[iamgreaser]

OK, so we've had 3 decompressors so far, of which the earlier one appears to be a port of a C implementation, and the other two happen to both work on Zig 0.6.0.

As far as performance is concerned, it'll really only be slow if you aren't buffering your input. If you're using the InStream interface, then you can plug in a BufferedInStream and that'll magically fix the worst of it.

If this should be in the standard library, then what API should we provide? And what primitives would we want in the standard library to make this work?

I'm mostly thinking from the perspective of

Here's what I'm thinking in terms of an API:

pub fn DeflateInStream(comptime TypeInStream: type) type { ... }
pub fn GzipInStream(comptime TypeInStream: type) type { ... } // FIXME: What capitalisation should we use?
pub fn ZlibInStream(comptime TypeInStream: type) type { ... }

And as for primitives, we do have BufferedInStream, BitInStream, and hash.Crc32 already (daurnimator pointed some of these out on IRC), but we're likely to need something like these to become a thing (names and interfaces TBD):

pub fn CanonicalHuffmanReader(... TODO ..., comptime out_type: type, max_len: usize) type { ... }
pub fn LzSlidingWindow(... TODO ..., comptime size: usize) type { ... }

Thoughts?

[mlarouche]

Looks good to me :)

[Rocknest]

@andrewrk please reopen since DEFLATE is not yet implemented

[andrewrk]

std.compress.deflate.inflateStream

[andrewrk]

ahh I see, my mistake.

[gsquire]

Would you be interested in including a snappy encoder and decoder? I implemented the block format here. It needs some more tests and polish but it's in a working state as of now.

[marnix]

Quoting iszn_11 from Discord:

I wrote a png decoder based on stb_image.h (basically a port), including zlib/deflate decompressor. While I could just use stb, I learned a lot about pngs and deflate. Honestly, png is the easy part. It's the decompression that almost broke me 🙃 .
https://gist.github.com/iszn11/4b4ae5cb68620fde295de4053e62d566

(Source: Discord link.)

[hdorio]

This is a really nice article on the subject: https://www.hanshq.net/zip.html

I made a Zig version of it if anyone wants to follow along with the article with Zig code https://github.com/hdorio/hwzip.zig

I also made a Zig version of the Go package compress/flate #10552

[andrewrk]

Thanks @hdorio! Landed in 0c1df96.