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

Lossless compression with Brotli

blogs.dropbox.com

Post reply on HN
Print view View original

31–40 of 66 posts

Re: Lossless compression with Brotli

#31

Post by frewsxcv »

JoshTriplett wrote: post #30
frewsxcv wrote: post #29

Earlier quoted context omitted.

(afl.rs maintainer here) I ran AFL on rust-brotli for a week a couple weeks ago. It didn't find anything. I plan to try again soon! No one is safe from AFL.

Have you run AFL against git2-rs? I'd love to see that interface hammered on, to make sure it doesn't expose any unsafe behavior from the underlying library.

I haven't, though I've thought about it. Most of the logic behind git2-rs (as far as I know) is written in C. While it's possible to run afl.rs on a Rust project that uses C code behind the scenes, I haven't ever attempted to get AFL instrumentation working on the underlying C code. I don't think it should be that difficult, I just haven't gotten around to it yet.

EDIT: I forgot to mention: It's possible to run AFL on uninstrumented code, it just won't be that smart about finding new code paths.

Re: Lossless compression with Brotli

#32

Post by daniel_rh »

saynsedit wrote: post #21
monocasa wrote: post #14

Earlier quoted context omitted.

> If they were going to run the whole thing in a SECCOMP container anyway, there is little damage a compromised C library could do. They can't block everything with SECCOMP, the code still has to be useful. It also must still do it's job correctly, which it won't if it's compromised. > If reasoning about uninitialized memory would take a review of the entire brotli code base, didn't the rust port require that anyway?…

Preventing compromise and ensuring determinism using checksums and SECCOMP is more reliable and easier to implement than reimplementing in rust an already de-facto secure library used millions of times every day. I'm sorry but the Rust rationale just isn't there. Porting to Rust is a strictly less efficient way of accomplishing the same exact goal. Now, writing a new library in rust, that's a different story and actu…

Your argument is certainly reasonable. One case where it might matter is if SECCOMP weren't available on all platforms that needed to decompress data. Also: a vulnerability could decide to only strike after a certain clock date. In that way it could sneak past certain checksum checks and still cause issues later.

Re: Lossless compression with Brotli

#33

Post by AceJohnny2 »

On a purely compression algorithm front, the recently format-stabilized [1] zstd [2] beats the pants down Brotli, in terms of compression speed, decompression speed, and compression ratio. Zstd isn't some random effort either, but a more flexible (in terms of compression time-for-ratio) effort by the creator of the popular and insanely fast lz4 compressor[3].

[1] http://fastcompression.blogspot.com/2016/06/zstandard-reache...

[2] https://github.com/Cyan4973/zstd

[3] https://github.com/Cyan4973/lz4

Re: Lossless compression with Brotli

#34

Post by AceJohnny2 »

AceJohnny2 wrote: post #33

On a purely compression algorithm front, the recently format-stabilized [1] zstd [2] beats the pants down Brotli, in terms of compression speed, decompression speed, and compression ratio. Zstd isn't some random effort either, but a more flexible (in terms of compression time-for-ratio) effort by the creator of the popular and insanely fast lz4 compressor[3]. [1] http://fastcompression.blogspot.com/2016/06/zstandard-…

While I'm around, I've been looking for a good compressor for an embedded scenario, where compression time and memory is near-irrelevant (it's done offline), but streaming decompression time and memory use (both in code and scratch memory) is primordial. By memory use, I'm talking a system with single-digit megabyte RAM, and decompressor scratch memory usage in the dozens of kilobytes.

Right now, we're using LZSS because the decompressor code is tiny (hundreds of bytes), and scratch memory is in the single-digit kilobytes.

Any suggestions? All benchmarks I can find online are focused on desktop usage (where comp/decomp memory use is either not mentioned or in the megabyte range) or web streaming usage (where total comp+decomp time is important. I don't care (within reason) about comp time)

Re: Lossless compression with Brotli

#35

Post by JoshTriplett »

frewsxcv wrote: post #31
JoshTriplett wrote: post #30

Earlier quoted context omitted.

Have you run AFL against git2-rs? I'd love to see that interface hammered on, to make sure it doesn't expose any unsafe behavior from the underlying library.

I haven't, though I've thought about it. Most of the logic behind git2-rs (as far as I know) is written in C. While it's possible to run afl.rs on a Rust project that uses C code behind the scenes, I haven't ever attempted to get AFL instrumentation working on the underlying C code. I don't think it should be that difficult, I just haven't gotten around to it yet. EDIT: I forgot to mention: It's possible to run AFL o…

> Most of the logic behind git2-rs (as far as I know) is written in C.

True, but the Rust bindings necessarily contain tons of unsafe FFI code, and those bindings enforces many required safety properties. Even without checking the underlying C code, running AFL to check for any unsafe holes in the bindings would help.

That said, yes, for best results you'd want to check the combination of C and Rust to find new paths and full coverage on both.

Re: Lossless compression with Brotli

#36

Post by stijlist »

AceJohnny2 wrote: post #34
AceJohnny2 wrote: post #33

On a purely compression algorithm front, the recently format-stabilized [1] zstd [2] beats the pants down Brotli, in terms of compression speed, decompression speed, and compression ratio. Zstd isn't some random effort either, but a more flexible (in terms of compression time-for-ratio) effort by the creator of the popular and insanely fast lz4 compressor[3]. [1] http://fastcompression.blogspot.com/2016/06/zstandard-…

While I'm around, I've been looking for a good compressor for an embedded scenario, where compression time and memory is near-irrelevant (it's done offline), but streaming decompression time and memory use (both in code and scratch memory) is primordial. By memory use, I'm talking a system with single-digit megabyte RAM, and decompressor scratch memory usage in the dozens of kilobytes. Right now, we're using LZSS bec…

https://github.com/atomicobject/heatshrink, by @silentbicycle, sounds like it might be up your alley.

Re: Lossless compression with Brotli

#37

Post by JyrkiAlakuijala »

AceJohnny2 wrote: post #33

On a purely compression algorithm front, the recently format-stabilized [1] zstd [2] beats the pants down Brotli, in terms of compression speed, decompression speed, and compression ratio. Zstd isn't some random effort either, but a more flexible (in terms of compression time-for-ratio) effort by the creator of the popular and insanely fast lz4 compressor[3]. [1] http://fastcompression.blogspot.com/2016/06/zstandard-…

Brotli's fastest compression is slightly faster than zstd's. Zstd decompresses faster, but neither is slow. Zstd can use sliding window size longer than 16 MB, in brotli this is limited to 16 MB to have guarantees of the maximum resource use at decoding time. Zstd's longer sliding window helps with the longest files (16 MB+), and often benchmarking is done with 100 MB or even 1 GB files.

Brotli compresses usually more, and quite a lot more on shorter files. Try with cp.html, sparc sum or xargs.1. Brotli compresses these 9-19 % more densely on the following benchmark:

https://quixdb.github.io/squash-benchmark/unstable/

Note, that on this benchmark brotli is always limited to the 4 MB sliding window. Other algorithms are run with wider windows, too. This will make brotli seem worse on large files (4+ MB).

Re: Lossless compression with Brotli

#39

Post by AceJohnny2 »

JyrkiAlakuijala wrote: post #37
AceJohnny2 wrote: post #33

On a purely compression algorithm front, the recently format-stabilized [1] zstd [2] beats the pants down Brotli, in terms of compression speed, decompression speed, and compression ratio. Zstd isn't some random effort either, but a more flexible (in terms of compression time-for-ratio) effort by the creator of the popular and insanely fast lz4 compressor[3]. [1] http://fastcompression.blogspot.com/2016/06/zstandard-…

Brotli's fastest compression is slightly faster than zstd's. Zstd decompresses faster, but neither is slow. Zstd can use sliding window size longer than 16 MB, in brotli this is limited to 16 MB to have guarantees of the maximum resource use at decoding time. Zstd's longer sliding window helps with the longest files (16 MB+), and often benchmarking is done with 100 MB or even 1 GB files. Brotli compresses usually mor…

Thanks for the clarification! I was going to include the squash-benchmark link, but they don't include zstd yet. I guess I jumped the gun :\

And especially thanks for the clarification on performance relative to input file size and sliding window size.

Re: Lossless compression with Brotli

#40

Post by AceJohnny2 »

stijlist wrote: post #36
AceJohnny2 wrote: post #34

Earlier quoted context omitted.

While I'm around, I've been looking for a good compressor for an embedded scenario, where compression time and memory is near-irrelevant (it's done offline), but streaming decompression time and memory use (both in code and scratch memory) is primordial. By memory use, I'm talking a system with single-digit megabyte RAM, and decompressor scratch memory usage in the dozens of kilobytes. Right now, we're using LZSS bec…

https://github.com/atomicobject/heatshrink , by @silentbicycle, sounds like it might be up your alley.

...which is based on LZSS :|
Post reply on HN