ende76/brotli-rs

A Brotli implementation in pure and safe Rust

Brotli-rs - Brotli decompression in pure, safe Rust

Documentation

Compression provides a <Read>-struct to wrap a Brotli-compressed stream. A consumer is thus able to read a compressed stream with usual convenience.

Changelog

v0.3.22 -> v0.3.23

---

Bug with literal buffer not being populated when processing uncompressed metablock, bug where a valid stream could be rejected too early as oversized, if the last bytes happened to be shortened by an OMIT-type transformation after the early check, reported and fixed by Daniel.

v0.3.21 -> v0.3.22

---

Bug with metablock structure not getting fully reset when encountering a new metablock in the brotli stream, reported and fixed by Daniel.

v0.3.20 -> v0.3.21

---

Bug with multiple metablocks, reported and fixed by Daniel.

###v0.3.19 -> v0.3.20

Worked around feature gate issue in nightly. (Thanks, Corey!)

v0.3.18 -> v0.3.19

---

Removed 64k big Pseudo-Code lookup table, because creating this trivial table probably took more time than making the calculcation on the fly. (Bench tests seem to suggest a 1% time savings without the lookup table)

v0.3.17 -> v0.3.18

---

Fixed case where a simple prefix code could have duplicate symbols.

v0.3.16 -> v0.3.17

---

Fixed case where a complex prefix code could have an incorrect checksum on its runlength code.

v0.3.15 -> v0.3.16

---

• Fixed incorrect calculation of alphabet size for distance code.
• Fixed evaluation where streams with excessive insert/copy lengths could be rejected early.

v0.3.14 -> v0.3.15

---

Fixed injection of invalid symbols in simple prefix code.

v0.3.13 -> v0.3.14

---

Fixed invalid block-type in switch command. (Thanks, Corey!).

v0.3.12 -> v0.3.13

---

Fixed uncaught non-positive distances. (Thanks, Corey!).

v0.3.11 -> v0.3.12

---

Fixed uncaught zero-byte in word transformation. (Thanks, Corey!).

v0.3.10 -> v0.3.11

---

Fixed possible arithmetic overflow in word transformation. (Thanks, Corey!).

v0.3.9 -> v0.3.10

---

Fixed incorrect type for runlength code. (Thanks, Corey!).

v0.3.8 -> v0.3.9

---

Fixed incorrect array index bound check in tree lookup. (Thanks, Corey!).

v0.3.7 -> v0.3.8

---

Fixed some value range checks on block types and ntree*. (Thanks, Corey!).

v0.3.6 -> v0.3.7

---

Went over "unreachable!()" statements, analyzed, and handled error condition properly, if they were reachable through invalid data.

v0.3.5 -> v0.3.6

---

Fixed a case where an invalid prefix code with all-zero codelengths could create an index-out-of-bounds panic. (Thanks, Corey!).

v0.3.4 -> v0.3.5

---

Fixed a case where an invalid insert-and-copy-length-code would produce a panic. (Thanks, Corey!).

v0.3.1 -> v0.3.4

---

Fair amount of internal small improvements, improving code quality. Fixed a couple of cases where invalid streams would lead to panics and/or infinite loops (Thanks, Corey!).

v0.3.0 -> v0.3.1

---

This is only a minor version bump, with no breakage in usage, but it's exciting nonetheless!

In Brotli, a lot of work is done with and by prefix codes. Through a change in the internal representation of prefix codes, it was possible to speed the reference benchmark time by a factor of ~7. The benchmark decompresses the contents of the file data/monkey.compressed.

• With linked-list-based, recursive tree implementation:
  test bench_monkey ... bench: 866,888 ns/iter (+/- 58,119)

• With array-based, iterative tree implementation, before max-depth constraint:
  test bench_monkey ... bench: 704,282 ns/iter (+/- 220,068)

• With array-based, iterative tree implementation, with max-depth constraint:
  test bench_monkey ... bench: 120,745 ns/iter (+/- 16,627)

v0.2.0 -> v0.3.0

---

• renamed crate compression -> brotli
• restructured modules to avoid redundant paths like brotli::brotli::Decompressor (now it's just brotli::Decompressor)

v0.1.0 -> v0.2.0

---

• Decompressor::new() now accepts a Read, as opposed to a BitReader.

brotli-rs's Issues

Panic while decompressing

extern crate brotli;

use std::io::Read;
use brotli::Decompressor;

fn main() {
    let mut input = vec![];
    let _ = Decompressor::new(&b"\x15\x3f\x60\x00\x15\x3f\x60\x00\x27\xb0\xdb\xa8\x80\x25\x27\xb0\xdb\x40\x80\x12".to_vec() as &[u8]).read_to_end(&mut input);
}

coreyf@frewbook-pro /t/meow (master) [101]> cargo run
     Running `target/debug/meow`
thread '<main>' panicked at 'shift operation overflowed', /Users/coreyf/.cargo/git/checkouts/brotli-rs-33811c30552ad7ba/master/src/lib.rs:1162
Process didn't exit successfully: `target/debug/meow` (exit code: 101)

Crash discovered using afl.rs

Panic while decompressing

extern crate brotli;

use std::io::Read;
use brotli::Decompressor;

fn main() {
    let mut input = vec![];
    let _ = Decompressor::new(&b"\x1b\x3f\x00\xff\xff\xb0\xe2\x99\x80\x12".to_vec() as &[u8]).read_to_end(&mut input);
}

coreyf@frewbook-pro /t/meow (master)> cargo run
     Running `target/debug/meow`
thread '<main>' panicked at 'arithmetic operation overflowed', /Users/coreyf/.cargo/git/checkouts/brotli-rs-33811c30552ad7ba/master/src/lib.rs:577
Process didn't exit successfully: `target/debug/meow` (exit code: 101)

Crash discovered using afl.rs

Panic while decompressing

extern crate brotli;

use std::io::Read;
use brotli::Decompressor;

fn main() {
    let mut input = vec![];
    let _ = Decompressor::new(&b"\x1b\x3f\x01\xf0\x24\xb0\xc2\xa4\x80\x54\xff\xd7\x24\xb0\x12".to_vec() as &[u8]).read_to_end(&mut input);
}

coreyf@frewbook-pro /t/meow (master)> cargo run
   Compiling brotli v0.3.11 (https://github.com/ende76/brotli-rs#3540aa18)
   Compiling meow v0.1.0 (file:///private/tmp/meow)
     Running `target/debug/meow`
thread '<main>' panicked at 'internal error: entered unreachable code', /Users/coreyf/.cargo/git/checkouts/brotli-rs-33811c30552ad7ba/master/src/transformation/mod.rs:35
Process didn't exit successfully: `target/debug/meow` (exit code: 101)

Crash discovered using afl.rs

Performance 10x worse than C implementation

I've been timing the C implementation versus the rust implementation and I generally notice about a factor of 8-10x difference.

Do you know offhand any obvious performance tradeoffs that were made in the design of this version?

Do you have any ideas about various strategies we could employ to bring it within a factor of two, or ideally to the same speed as the C version especially for multi-megabyte files?

I noticed no inline assembly in the C version, so I'm hoping it is possible to bring the rust version to parity.

Have you done any profiling of the existing code or compared it with the C code?

Access to the 'brotli' crates.io name

https://crates.io/crates/brotli

Servo has ownership of this name right now, but we can grant you access if you want. You just need to log in to (and by doing so 'creating') your crates.io account.

Panic when decompressing

extern crate brotli;

use std::io::Read;
use brotli::Decompressor;

fn main() {
    let mut input = vec![];
    let _ = Decompressor::new(&b"\xb1".to_vec() as &[u8]).read_to_end(&mut input);
}

coreyf@frewbook-pro /t/meow (master)> cargo run
     Running `target/debug/meow`
thread '<main>' panicked at '"Encountered unexpected EOF"', /Users/coreyf/.cargo/git/checkouts/brotli-rs-33811c30552ad7ba/master/src/lib.rs:2280
Process didn't exit successfully: `target/debug/meow` (exit code: 101)

Panic discovered using afl.rs

Panic while decompressing

extern crate brotli;

use std::io::Read;
use brotli::Decompressor;

fn main() {
    let mut input = vec![];
    let _ = Decompressor::new(&b"\x11\x3f\x00\x00\x24\xb0\xe2\x99\x80\x12".to_vec() as &[u8]).read_to_end(&mut input);
}

coreyf@frewbook-pro /t/meow (master) [101]> cargo run
     Running `target/debug/meow`
thread '<main>' panicked at 'index out of bounds: the len is 255 but the index is 391', ../src/libcollections/vec.rs:1110
Process didn't exit successfully: `target/debug/meow` (exit code: 101)

Crash discovered using afl.rs

zip file compressed with brotli doesn't roundtrip

https://www.dropbox.com/s/ubfjbfe0oowfvtl/svg.zip?dl=0
when compressed to brotli is
https://www.dropbox.com/s/9ifkxzaxblfhz50/svg.zip.compressed?dl=0

and it fails to roundtrip with the following message

"data/svg.zip.compressed":
output length = 65703
res = Err(Error { repr: Custom(Custom { kind: InvalidData, error: StringError("More uncompressed bytes than expected in meta-block") }) })
===========

However the copy and insert lengths appear to be the same as with the google-provided decompressor
https://www.dropbox.com/s/gc6rjqtca4mi4cx/svg.zip.cerrlog.txt?dl=0

brotli's log:

https://www.dropbox.com/s/vptya6rxmks5f97/svg.zip.errlog.txt?dl=0

Here's the tail end of the log from the brotli-rs binary

Insert And Copy Length = 137
(m_len, self.meta_block.count_output, insert_length, copy_length) = (87897, 87883, 1, 3)
btype = 0
[p1, p2] = RingBuffer { buf: [0, 0], pos: 0, cap: 2 }
Context Mode = 3
Lit = 0 0
Count output 87884
Count output 87887
Insert And Copy Length = 182
(m_len, self.meta_block.count_output, insert_length, copy_length) = (87897, 87887, 6, 8)
Fatal (m_len, a, b, c) = (87897, 87887, 87893, 87901)
output length = 65703
res = Err(Error { repr: Custom(Custom { kind: InvalidData, error: StringError("More uncompressed bytes than expected in meta-block") }) })
===========

OK ()

Panic while decompressing

extern crate brotli;

use std::io::Read;
use brotli::Decompressor;

fn main() {
    let mut input = vec![];
    let _ = Decompressor::new(&b"\x12\x1b\x00\x1e\x11\x00\x05\x09\x21\x00\x05\x04\x43\x05\xf5\x21\x1e\x11\x00\x05\xf5\x21\x00\x05\x04\x43".to_vec() as &[u8]).read_to_end(&mut input);
}

coreyf@frewbook-pro /t/meow (master)> cargo run
     Running `target/debug/meow`
thread '<main>' panicked at 'arithmetic operation overflowed', /Users/coreyf/.cargo/git/checkouts/brotli-rs-33811c30552ad7ba/master/src/transformation/mod.rs:145
Process didn't exit successfully: `target/debug/meow` (exit code: 101)

Crash discovered using afl.rs

Panic while decompressing

extern crate brotli;

use std::io::Read;
use brotli::Decompressor;

fn main() {
    let mut input = vec![];
    let _ = Decompressor::new(&b"\x5b\xff\x00\x01\x40\x0a\x00\xab\x16\x7b\xac\x14\x48\x4e\x73\xed\x01\x92\x03".to_vec() as &[u8]).read_to_end(&mut input);
}

Crash discovered using afl.rs

Panic when decompressing

extern crate brotli;

use std::io::{self, Read};
use brotli::Decompressor;

fn main() {
    let mut input = vec![];
    let _ = Decompressor::new(&b"\x1b\x3f\xff\xff\xdb\x4f\xe2\x99\x80\x12".to_vec() as &[u8]).read_to_end(&mut input);
}

Crash discovered using afl.rs

Doesn't build on Rust nightly

   Compiling brotli v0.3.19 (file:///Users/coreyf/Development/rust/brotli-rs)
src/lib.rs:686:18: 686:33 error: const indexing is an unstable feature
src/lib.rs:686              sum += 32 >> code_lengths[i];
                                         ^~~~~~~~~~~~~~~
src/lib.rs:686:18: 686:33 help: in Nightly builds, add `#![feature(const_indexing)]` to the crate attributes to enable
src/lib.rs:1512:10: 1512:60 error: const indexing is an unstable feature
src/lib.rs:1512                 1 << BROTLI_DICTIONARY_SIZE_BITS_BY_LENGTH[copy_length]
                                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
src/lib.rs:1512:10: 1512:60 help: in Nightly builds, add `#![feature(const_indexing)]` to the crate attributes to enable
src/lib.rs:1518:34: 1518:84 error: const indexing is an unstable feature
src/lib.rs:1518             let transform_id = word_id >> BROTLI_DICTIONARY_SIZE_BITS_BY_LENGTH[copy_length];
                                                          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
src/lib.rs:1518:34: 1518:84 help: in Nightly builds, add `#![feature(const_indexing)]` to the crate attributes to enable
error: aborting due to 3 previous errors
Could not compile `brotli`.

To learn more, run the command again with --verbose.

coreyf@frewbook-pro ~/D/r/brotli-rs (master) [101]> rustc -Vv
rustc 1.6.0-nightly (d49e36552 2015-12-05)
binary: rustc
commit-hash: d49e365528e026df6f56fe5eb001e81e2383fbf5
commit-date: 2015-12-05
host: x86_64-apple-darwin
release: 1.6.0-nightly

brotli-rs fails to decompress item compressed with -q 4 -w 16

I tried this on the bro binary from google and it fails to decompress with brotli-rs when compressed using -q 4 -w 16

https://www.dropbox.com/s/il9uhagaaawxl6i/bro?dl=0

https://www.dropbox.com/s/2lb4dzpjczbv8ll/bro.br?dl=0

but this is true for almost every binary I checked...
in fact I just wrote a checker script that simply, in a loop, compresses with bro -q X -w Y
where x = {1..11} and y = {16..22}
That's how I found this glitch.

Unable to decompress pdfs made by ./bro -q 2

Hi--
I tried running the rust brotli decompressor--and if I use -q 2 on the encoding for big binary files, it fails to decode

here's an example
https://www.dropbox.com/s/nzvkt9pl94qb3b8/origin.br?dl=0
https://www.dropbox.com/s/m35k1udfe56b1wp/origin.pdf?dl=0

Any idea what the issue is? The output is only 128KB and doesn't match the original

Uncompressed data is not fed into the literal_buf

Brotli expects the literal_buf to be prepopulated with uncompressed_data, if such data is encountered before something needing context bytes.

Currently the literal_buf is left to be 0,0 despite an uncompressed meta-block being encountered

Panic when decompressing

extern crate brotli;

use std::io::Read;
use brotli::Decompressor;

fn main() {
    let mut input = vec![];
    let _ = Decompressor::new(&b"\x1b\x30\x30\x30\x24\x30\xe2\xd9\x30\x30".to_vec() as &[u8]).read_to_end(&mut input);
}

coreyf@frewbook-pro /t/meow (master)> cargo run
     Running `target/debug/meow`
thread '<main>' panicked at 'internal error: entered unreachable code', /Users/coreyf/.cargo/git/checkouts/brotli-rs-33811c30552ad7ba/master/src/lib.rs:1274
Process didn't exit successfully: `target/debug/meow` (exit code: 101)

Crash discovered using afl.rs

Panic while decompressing

extern crate brotli;

use std::io::Read;
use brotli::Decompressor;

fn main() {
    let mut input = vec![];
    let _ = Decompressor::new(&b"\x51\xac\x00\x48\x2f\x73\x14\x01\x14\x00\x00\x01\x00\x14\x14\xff\x00\x02\x00\x00\x00\x00\x00\x64\x14\x24\x14\x14\x14\x14\x14\x80\x00\x00\x14\xff\xff\x00\x00\x14\x14\x14\x14\x14\x14\x80\x00\x80".to_vec() as &[u8]).read_to_end(&mut input);
}

Crash discovered using afl.rs

Panic while decompressing

extern crate brotli;

use std::io::Read;
use brotli::Decompressor;

fn main() {
    let mut input = vec![];
    let _ = Decompressor::new(&b"\x30\x30\x40\x00\x00\x00\x00\x00".to_vec() as &[u8]).read_to_end(&mut input);
}

coreyf@frewbook-pro /t/meow (master)> cargo run
     Running `target/debug/meow`
thread '<main>' panicked at 'index out of bounds: the len is 18 but the index is 18', ../src/libcollections/vec.rs:1110
Process didn't exit successfully: `target/debug/meow` (exit code: 101)

Crash discovered using afl.rs