8 ms·

Lossless compression with Brotli

281 points by nuriaion 10y ago

mmastrac 10y ago
Somewhat interesting for those who missed it - another rust/brotli project was a target for afl-rust. IIRC it didn't find any memory safety issues, but it definitely exposed a few panic crashes: https://github.com/frewsxcv/afl.rs https://github.com/frewsxcv/afl.rs (discussion https://news.ycombinator.com/item?id=11936983 https://news.ycombinator.com/item?id=11936983) I don't think they mentioned fuzzing their Brotli decompressor in this article, but I hope they try afl-rust.
- sanxiyn 10y ago
  Apparently this(https://github.com/dropbox/rust-brotli https://github.com/dropbox/rust-brotli) is much faster than the one(https://github.com/ende76/brotli-rs https://github.com/ende76/brotli-rs) fuzzed by afl.rs. Like 10x faster. See https://github.com/ende76/brotli-rs/issues/24 https://github.com/ende76/brotli-rs/issues/24.
  - seeekr 10y ago
    Relevant comment from ende76 on why brotli-rs is relatively slow and what the goals of the project are/were: "Yes, performance has not been a focus point at all so far. I've started this project as a a way to get familiar with Rust, and also with the Brotli spec. For the implementation, I have made it a point to work only from the spec, while avoiding looking at the reference implementation, because another goal was helping to improve the Brotli spec itself. I do believe that there are a number of places where copies could be avoided, and other places where I used clone() simply because at the time I was unable otherwise to appease the borrow checker. For a performance-oriented implementation, I would probably take the test cases and experiences so far, and start over with a new implementation."
- frewsxcv 10y ago
  (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.
  - JoshTriplett 10y ago
    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.
    - frewsxcv 10y ago
      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.
      - JoshTriplett 10y ago
        > 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.
vvanders 10y ago
Awesome to see the contributed back their custom allocator that lets you allocate from a fixed block: https://github.com/dropbox/rust-alloc-no-stdlib https://github.com/dropbox/rust-alloc-no-stdlib Solid stuff from the looks of it.
- gregwtmtno 10y ago
  That's going to be really great for embedded projects.
- saidajigumi 10y ago
  Now I have a huge hankering to whip up a frame-based allocator, as used to be popular in game and graphics programming. For those unfamiliar, the idea is that you segregate allocation of memory objects of different sizes into their own fixed blocks. This provides a means to control memory fragmentation, and avoids hitting the typically slow system allocator with a lot of small allocations/deallocations. Fancy frame allocators would actually use a fairly standard malloc-style interface, but transparently place allocations of different sizes in their own regions. The allocator would internally use the slow system malloc to create and expand the fixed blocks it uses for its own allocations. During development, the frame allocator would be used to profile and optimize the actual object allocation sizes being made. E.g. sometimes it might make sense to pad some objects to consolidate the number of allocation-size regions. As the project progresses, the initial block allocations for each allocation size would be adjusted so that the system malloc was called very infrequently, usually only at application startup.
  - Manishearth 10y ago
    It might be possible that jemalloc already does this? Rust uses it by default, and while I don't recall the specifics jemalloc does a bunch of things in userspace wrapped around malloc that make it better than malloc. Rust makes it easy to swap out the allocator too, so I'd love to see an allocator lib specifically focused on size management :)
    - Jweb_Guru 10y ago
maxst 10y ago
Somebody, make "image format powered by brotli", please.
- sanxiyn 10y ago
  I think zstd will be better: https://github.com/Cyan4973/zstd https://github.com/Cyan4973/zstd.
- niftich 10y ago
  Since most of Brotli's improvements over its ancestor LZ77 are due to its large, hardcoded, text-corpus dictionary [1], most of the algorithm's strengths would be wasted on binary data like images. Zopfli, from the same people, is a DEFLATE encoder, so it can be used in PNG [2] and this has already been added to some optimizers, e.g. AdvanceCOMP [3] [1] https://gist.github.com/klauspost/2900d5ba6f9b65d69c8e https://gist.github.com/klauspost/2900d5ba6f9b65d69c8e [2] https://github.com/google/zopfli/commit/337d27f25ef15a6cf34fef2acd0613fddc411cb1 https://github.com/google/zopfli/commit/337d27f25ef15a6cf34f... [3] http://www.advancemame.it/doc-advpng.html http://www.advancemame.it/doc-advpng.html
  - JyrkiAlakuijala 10y ago
    About 25 % of compression improvements for short files (such as web pages) come from the static dictionary. The rest are format improvements. The relatively small static dictionary does not improve the compression of long files.
  - est 10y ago
    First time saw the Brotli dictionary. It has duplicates. Line 3131 and 8704 both are "操作"
    - niftich 10y ago
      Interestingly, there are also 121 different transformations [1] you can apply to each dictionary word, from adding various prefixes and suffixes, trimming letters, and some more complex ones [2]. If the plain-text dictionary linked earlier [3] is accurate, it'd appear that the dictionary contains a lot of redundant forms. [1] https://tools.ietf.org/html/draft-alakuijala-brotli-11#page-27 https://tools.ietf.org/html/draft-alakuijala-brotli-11#page-... [2] https://tools.ietf.org/html/draft-alakuijala-brotli-11#appendix-B https://tools.ietf.org/html/draft-alakuijala-brotli-11#appen... [3] https://gist.github.com/klauspost/2900d5ba6f9b65d69c8e https://gist.github.com/klauspost/2900d5ba6f9b65d69c8e
mozumder 10y ago
Can Brotli compress streamed blocks, with SYNC_FLUSH or FULL_FLUSH the way zlib can?
- Jweb_Guru 10y ago
  Brotli compression is fully streamable, as is mentioned several times in the article.
saynsedit 10y ago
I'm having a hard time understanding the motivations for porting to rust... If they were going to run the whole thing in a SECCOMP container anyway, there is little damage a compromised C library could do. If reasoning about uninitialized memory would take a review of the entire brotli code base, didn't the rust port require that anyway? (speaking as someone who has done a couple of cross-language rewrites)
- monocasa 10y ago
  > 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? (speaking as someone who has done a couple of cross-language rewrites) But even if you go through the whole original codebase (which I assume was in C or C++), and kept it in that same memory unsafe language, you don't have any guarantees that you caught even a subset of possible classes of memory safety bugs.
  - saynsedit 10y ago
    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 actually is reasonable.
    - daniel_rh 10y ago
      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.
artur_makly 10y ago
go PiedPiper go!
- artur_makly 10y ago
  oof.no humor allowed . got it.
  - conceit 10y ago
    I don't even get it and so may the downvoters
    - artur_makly 10y ago
      Pied Piper = name of the startup in Silicon Valley TV series "... The team rushes to produce a feature-rich cloud storage platform based on their compression technology.." [1]https://en.wikipedia.org/wiki/Silicon_Valley_(TV_series) https://en.wikipedia.org/wiki/Silicon_Valley_(TV_series)
AceJohnny2 10y ago
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-reaches-final-format.html http://fastcompression.blogspot.com/2016/06/zstandard-reache... [2] https://github.com/Cyan4973/zstd https://github.com/Cyan4973/zstd [3] https://github.com/Cyan4973/lz4 https://github.com/Cyan4973/lz4
- AceJohnny2 10y ago
  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)
  - stijlist 10y ago
    https://github.com/atomicobject/heatshrink https://github.com/atomicobject/heatshrink, by @silentbicycle, sounds like it might be up your alley.
    - AceJohnny2 10y ago
      ...which is based on LZSS :|
  - unwind 10y ago
    I've had good results with LZJB[1] (designed by Jeff Bonwick for ZFS) in embedded scenarios, perhaps at least worth testing for you? I even have some public code for it, there's Python module [2] that will adequately address your wish for mediocre offline-friendly performance (heh) and a streaming C decompression library [3]. The runtime memory usage for the decompressor are tiny (which is good, since from my perspective your system sounds huge!) so that should be fine at least. Very interested in any feedback you might have, of course. [1] https://en.wikipedia.org/wiki/LZJB https://en.wikipedia.org/wiki/LZJB [2] https://github.com/unwind/python-lzjb https://github.com/unwind/python-lzjb [3] https://github.com/unwind/lzjb-stream https://github.com/unwind/lzjb-stream
sams99 10y ago
On the topic of Brotli, don't forget - It is available today on close to 50% or web browsers - Vast majority of CDNs block it today I wrote about it here: https://samsaffron.com/archive/2016/06/15/the-current-state-of-brotli-compression https://samsaffron.com/archive/2016/06/15/the-current-state-...

281 points by nuriaion 10y ago

Somewhat interesting for those who missed it - another rust/brotli project was a target for afl-rust. IIRC it didn't find any memory safety issues, but it definitely exposed a few panic crashes: https://github.com/frewsxcv/afl.rs https://github.com/frewsxcv/afl.rs (discussion https://news.ycombinator.com/item?id=11936983 https://news.ycombinator.com/item?id=11936983) I don't think they mentioned fuzzing their Brotli decompressor in this article, but I hope they try afl-rust.

sanxiyn 10y ago
Apparently this(https://github.com/dropbox/rust-brotli https://github.com/dropbox/rust-brotli) is much faster than the one(https://github.com/ende76/brotli-rs https://github.com/ende76/brotli-rs) fuzzed by afl.rs. Like 10x faster. See https://github.com/ende76/brotli-rs/issues/24 https://github.com/ende76/brotli-rs/issues/24.
- seeekr 10y ago
  Relevant comment from ende76 on why brotli-rs is relatively slow and what the goals of the project are/were: "Yes, performance has not been a focus point at all so far. I've started this project as a a way to get familiar with Rust, and also with the Brotli spec. For the implementation, I have made it a point to work only from the spec, while avoiding looking at the reference implementation, because another goal was helping to improve the Brotli spec itself. I do believe that there are a number of places where copies could be avoided, and other places where I used clone() simply because at the time I was unable otherwise to appease the borrow checker. For a performance-oriented implementation, I would probably take the test cases and experiences so far, and start over with a new implementation."
frewsxcv 10y ago
(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.
- JoshTriplett 10y ago
  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.
  - frewsxcv 10y ago
    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.
    - JoshTriplett 10y ago
      > 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.

vvanders 10y ago

Awesome to see the contributed back their custom allocator that lets you allocate from a fixed block: https://github.com/dropbox/rust-alloc-no-stdlib https://github.com/dropbox/rust-alloc-no-stdlib Solid stuff from the looks of it.

gregwtmtno 10y ago
That's going to be really great for embedded projects.
saidajigumi 10y ago
Now I have a huge hankering to whip up a frame-based allocator, as used to be popular in game and graphics programming. For those unfamiliar, the idea is that you segregate allocation of memory objects of different sizes into their own fixed blocks. This provides a means to control memory fragmentation, and avoids hitting the typically slow system allocator with a lot of small allocations/deallocations. Fancy frame allocators would actually use a fairly standard malloc-style interface, but transparently place allocations of different sizes in their own regions. The allocator would internally use the slow system malloc to create and expand the fixed blocks it uses for its own allocations. During development, the frame allocator would be used to profile and optimize the actual object allocation sizes being made. E.g. sometimes it might make sense to pad some objects to consolidate the number of allocation-size regions. As the project progresses, the initial block allocations for each allocation size would be adjusted so that the system malloc was called very infrequently, usually only at application startup.
- Manishearth 10y ago
  It might be possible that jemalloc already does this? Rust uses it by default, and while I don't recall the specifics jemalloc does a bunch of things in userspace wrapped around malloc that make it better than malloc. Rust makes it easy to swap out the allocator too, so I'd love to see an allocator lib specifically focused on size management :)
  - Jweb_Guru 10y ago

maxst 10y ago

Somebody, make "image format powered by brotli", please.

sanxiyn 10y ago
I think zstd will be better: https://github.com/Cyan4973/zstd https://github.com/Cyan4973/zstd.
niftich 10y ago
Since most of Brotli's improvements over its ancestor LZ77 are due to its large, hardcoded, text-corpus dictionary [1], most of the algorithm's strengths would be wasted on binary data like images. Zopfli, from the same people, is a DEFLATE encoder, so it can be used in PNG [2] and this has already been added to some optimizers, e.g. AdvanceCOMP [3] [1] https://gist.github.com/klauspost/2900d5ba6f9b65d69c8e https://gist.github.com/klauspost/2900d5ba6f9b65d69c8e [2] https://github.com/google/zopfli/commit/337d27f25ef15a6cf34fef2acd0613fddc411cb1 https://github.com/google/zopfli/commit/337d27f25ef15a6cf34f... [3] http://www.advancemame.it/doc-advpng.html http://www.advancemame.it/doc-advpng.html
- JyrkiAlakuijala 10y ago
  About 25 % of compression improvements for short files (such as web pages) come from the static dictionary. The rest are format improvements. The relatively small static dictionary does not improve the compression of long files.
- est 10y ago
  First time saw the Brotli dictionary. It has duplicates. Line 3131 and 8704 both are "操作"
  - niftich 10y ago
    Interestingly, there are also 121 different transformations [1] you can apply to each dictionary word, from adding various prefixes and suffixes, trimming letters, and some more complex ones [2]. If the plain-text dictionary linked earlier [3] is accurate, it'd appear that the dictionary contains a lot of redundant forms. [1] https://tools.ietf.org/html/draft-alakuijala-brotli-11#page-27 https://tools.ietf.org/html/draft-alakuijala-brotli-11#page-... [2] https://tools.ietf.org/html/draft-alakuijala-brotli-11#appendix-B https://tools.ietf.org/html/draft-alakuijala-brotli-11#appen... [3] https://gist.github.com/klauspost/2900d5ba6f9b65d69c8e https://gist.github.com/klauspost/2900d5ba6f9b65d69c8e

mozumder 10y ago

Can Brotli compress streamed blocks, with SYNC_FLUSH or FULL_FLUSH the way zlib can?

Jweb_Guru 10y ago
Brotli compression is fully streamable, as is mentioned several times in the article.

saynsedit 10y ago

I'm having a hard time understanding the motivations for porting to rust... If they were going to run the whole thing in a SECCOMP container anyway, there is little damage a compromised C library could do. If reasoning about uninitialized memory would take a review of the entire brotli code base, didn't the rust port require that anyway? (speaking as someone who has done a couple of cross-language rewrites)

monocasa 10y ago
> 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? (speaking as someone who has done a couple of cross-language rewrites) But even if you go through the whole original codebase (which I assume was in C or C++), and kept it in that same memory unsafe language, you don't have any guarantees that you caught even a subset of possible classes of memory safety bugs.
- saynsedit 10y ago
  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 actually is reasonable.
  - daniel_rh 10y ago
    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.

artur_makly 10y ago

go PiedPiper go!

artur_makly 10y ago
oof.no humor allowed . got it.
- conceit 10y ago
  I don't even get it and so may the downvoters
  - artur_makly 10y ago
    Pied Piper = name of the startup in Silicon Valley TV series "... The team rushes to produce a feature-rich cloud storage platform based on their compression technology.." [1]https://en.wikipedia.org/wiki/Silicon_Valley_(TV_series) https://en.wikipedia.org/wiki/Silicon_Valley_(TV_series)

AceJohnny2 10y ago

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-reaches-final-format.html http://fastcompression.blogspot.com/2016/06/zstandard-reache... [2] https://github.com/Cyan4973/zstd https://github.com/Cyan4973/zstd [3] https://github.com/Cyan4973/lz4 https://github.com/Cyan4973/lz4

AceJohnny2 10y ago
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)
- stijlist 10y ago
  https://github.com/atomicobject/heatshrink https://github.com/atomicobject/heatshrink, by @silentbicycle, sounds like it might be up your alley.
  - AceJohnny2 10y ago
    ...which is based on LZSS :|
- unwind 10y ago
  I've had good results with LZJB[1] (designed by Jeff Bonwick for ZFS) in embedded scenarios, perhaps at least worth testing for you? I even have some public code for it, there's Python module [2] that will adequately address your wish for mediocre offline-friendly performance (heh) and a streaming C decompression library [3]. The runtime memory usage for the decompressor are tiny (which is good, since from my perspective your system sounds huge!) so that should be fine at least. Very interested in any feedback you might have, of course. [1] https://en.wikipedia.org/wiki/LZJB https://en.wikipedia.org/wiki/LZJB [2] https://github.com/unwind/python-lzjb https://github.com/unwind/python-lzjb [3] https://github.com/unwind/lzjb-stream https://github.com/unwind/lzjb-stream

sams99 10y ago

On the topic of Brotli, don't forget - It is available today on close to 50% or web browsers - Vast majority of CDNs block it today I wrote about it here: https://samsaffron.com/archive/2016/06/15/the-current-state-of-brotli-compression https://samsaffron.com/archive/2016/06/15/the-current-state-...