Reading bits until the bitter end
Bitter reads bits in a desired endian format platform agonistically. Performance is the distinguishing feature compared to other bit readers. See benchmarks for more information.
u8 ... u32, f32, etc)no_std compatibleThe example below gives a good demonstration of the main API surface area to decode a 16 bit data model. It strikes a good balance between ergonomics and speed.
rust
use bitter::{BitReader, LittleEndianReader};
let mut bits = LittleEndianReader::new(&[0xff, 0x04]);
assert_eq!(bits.bytes_remaining(), 2);
assert_eq!(bits.read_bit(), Some(true));
assert_eq!(bits.bytes_remaining(), 1);
assert_eq!(bits.read_u8(), Some(0x7f));
assert!(bits.has_bits_remaining(7));
assert_eq!(bits.read_bits(7), Some(0x02));
However, one can unlock additional performance by amortizing internal state logic management when exploiting patterns in the encoded data. Colloquially known as Manual Mode, our example from before can be rewritten to take advantage of our domain knowledge that we'll be decoding 16 bits.
```rust use bitter::{BitReader, LittleEndianReader}; let mut bits = LittleEndianReader::new(&[0xff, 0x04]);
// Always start manual management with a refill, which // will return the number of bits buffered let len = bits.refill_lookahead();
// We need at least 16 bits buffered assert!(len >= 16);
// We use a combination of peek and consume instead of read* asserteq!(bits.peek(1), 1); bits.consume(1);
// Notice how the return type is not an Option
assert_eq!(bits.peek(8), 0x7f);
bits.consume(8);
// We can switch back to auto mode any time assert!(bits.hasbitsremaining(7)); asserteq!(bits.readbits(7), Some(0x02)); ```
The refill, peek, and consume combination are the building blocks for Manual Mode, and allows fine grain management for hot loops. The surface area of Manual Mode APIs is purposely compact to keep things simple. The "Auto Mode" API (the functions with read_ prefix) is larger as that API should be the one reaches for first
Manual mode can be intimidating, but it's one of if not the fastest way to decode a bit stream, as it's based on variant 4 from Fabian Giesen's excellent series on reading bits. Others have employed this underlying technique to significantly speed up DEFLATE.
Still, the limitation of a bit reading library only able to read up to 56 bits seems arbitrary and limiting. This can be mitigated through a couple measures. The first is to use a static assertion so we know refilling the lookahead buffer can yield sufficient data if available.
```rust use bitter::{BitReader, LittleEndianReader}; let mut bits = LittleEndianReader::new(&[0xff, 0x04]);
const : () = assert!( bitter::MAXREAD_BITS >= 16, "lookahead bit buffer not large enough for our data" );
let len = bits.refill_lookahead(); if len < 16 { panic!("Early EOF"); }
// ... peek & consume ... ```
The read size limitation can be eliminated by emulating larger reads. For instance, decoding a 128 bit number:
```rust use bitter::{BitReader, LittleEndianReader};
let value: i128 = 0x12345678901234567890123456789012;
let data = value.tolebytes();
let mut bits = LittleEndianReader::new(&data);
let mut out = [0u8; core::mem::sizeof::
Or one can break it down into manageable chunks:
```rust use bitter::{BitReader, LittleEndianReader};
let data: [u8; 8] = [0xab, 0xcd, 0xef, 0x01, 0x23, 0x45, 0x67, 0x89]; let bitstoread = 60u32; let value: u64 = 0x123456789; let mut bits = LittleEndianReader::new(&data); assert!(bits.hasbitsremaining(bitstoread as usize)); assert!(bits.refilllookahead() >= bitter::MAXREAD_BITS);
let lo = bits.peek(bitter::MAXREADBITS); bits.consume(bitter::MAXREADBITS);
let hibits = bitstoread - bitter::MAXREADBITS; assert!(bits.refilllookahead() >= hi_bits);
let hi = bits.peek(hibits); bits.consume(hibits);
let mut expected = [0u8; 8]; expected.copyfromslice(&data); expected[7] = 0x09;
asserteq!((hi << bitter::MAXREADBITS) + lo, u64::fromle_bytes(expected)); ```
There's one final trick that bitter exposes that dials performance to 11 at the cost of safety and increased assumptions. Welcome to the unchecked refill API (referred to as "unchecked"), which can only be called when there are at least 8 bytes left in the buffer. Anything less than that can cause invalid memory access. The upside is that this API unlocks the holy grail of branchless bit reading.
Always consider guarding unchecked access at a higher level:
```rust use bitter::{BitReader, LittleEndianReader};
let mut bits = LittleEndianReader::new(&[0u8; 100]); let objectstoread = 10; let objectbits = 56; let bitterpadding = 64;
// make sure we have enough data to read all our objects and there is enough // data leftover so bitter can unalign read 8 bytes without fear of reading past // the end of the buffer. if bits.hasbitsremaining(objectstoread * objectbits + bitterpadding) { for _ in 0..objectstoread { unsafe { bits.refilllookaheadunchecked() }; let _field1 = bits.peek(2); bits.consume(2);
let _field2 = bits.peek(18);
bits.consume(18);
let _field3 = bits.peek(18);
bits.consume(18);
let _field4 = bits.peek(18);
bits.consume(18);
}
} ```
All three modes: auto, manual, and unchecked can be mixed and matched as desired.
no_std cratesThis crate has a feature, std, that is enabled by default. To use this crate
in a no_std context, add the following to your Cargo.toml:
toml
[dependencies]
bitter = { version = "x", default-features = false }
Bitter is hardly the first Rust library for handling bits. nom, bitvec, bitstream_io, and bitreader are all crates that deal with bit reading. The reason why someone would choose bitter is speed.
Takeaways:
Benchmarks are ran with the following command:
bash
(cd compare && cargo clean && RUSTFLAGS="-C target-cpu=native" cargo bench)
find ./compare/target -path "*bit-reading*" -wholename "*/new/raw.csv" -print0 \
| xargs -0 xsv cat rows > assets/bitter-benchmark-data.csv
And can be analyzed with the R script found in the assets directory. Keep in mind, benchmarks will vary by machine