bitfield-rle

Crates.iobitfield-rle
lib.rsbitfield-rle
version0.2.1
sourcesrc
created_at2018-07-10 14:35:51.551953
updated_at2024-03-31 07:46:08.061952
descriptionA run-length-encoder that compresses bitfields
homepage
repositoryhttps://github.com/datrs/bitfield-rle
max_upload_size
id73623
size39,792
Maintainers (github:datrs:maintainers)

documentation

https://docs.rs/bitfield-rle

README

bitfield-rle

crates.io version build status downloads docs.rs docs

A run-length-encoder that compresses bitfields.

The encoder uses a compact format and will only run length encode sequences of bits if it compresses the bitfield. The encoded bitfield should therefore always be smaller or the same size as the original bitfield with the exception of a 1-6 byte header.

Since this uses run-length-encoding, you'll get the best compression results if you have longer sequences of the same bit in your bitfield.

Usage

extern crate bitfield_rle;
extern crate sparse_bitfield;

use sparse_bitfield::Bitfield;

let mut bits = Bitfield::new(1024);
bits.set(400, true);

let enc = bitfield_rle::encode(bits);
assert_eq!(enc.len(), 6);

let dec = bitfield_rle::decode(enc);

let bits = Bitfield::from_bytes(dec);
assert_eq!(bits.get(400), true);

Format

The encoded bitfield is a series of compressed and uncompressed bit sequences. All sequences start with a header that is a varint.

If the last bit is set in the varint (it is an odd number) then a header represents a compressed bit sequence.

S = varint([l << 2, b << 1, 1])

where
  S = compressed sequence
  l = byte length of sequence
  b = bit

If the last bit is set to 0 then a header represents an uncompressed bit sequence.

S = [varint([l << 1, 0]), b]

where
  S = uncompressed sequence
  l = byte length of bitfield
  b = bitfield

Installation

$ cargo add bitfield-rle

License

MIT OR Apache-2.0

Commit count: 42

cargo fmt