icewrap/
lib.rs

1//! A Rust port of the [Heatshrink](https://github.com/atomicobject/heatshrink/) compression library for embedded/real-time systems.
2//!
3//! # How it works
4//!
5//! Heatshrink is based on [LZSS](https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Storer%E2%80%93Szymanski).
6//! It recognizes repeated byte sequences in data and encodes them as _backreferences_ to the original sequence.
7//! A _backreference_ consists of an index and length. The index is a negative offset from the current position in the data that can go as far back as `2^window`.
8//! The length can be any value in the inclusive range `[1, 2^lookahead]`.
9//!
10//! While a backreference of length 1 or 2 could technically be constructed, it would waste space (`sizeof(index) + sizeof(length) > sizeof(single byte)`).
11//! Instead, Heatshrink encodes these smaller sequences of data as _literals_; the raw data is emitted.
12//! To indicate whether data is a backreference or literal, the encoder includes a 1-bit identifer flag: `0` for a backreference, `1` for a literal.
13//!
14//! ## Encoder
15//!
16//! The encoder buffers up incoming data internally to try and generate backreferences in the available window of data.
17//! The search for backreferences is the most computationally intensive operation.
18//! There is an indexing optimization that speeds it up, but it uses more memory.
19//!
20//! ## Decoder
21//!
22//! The decoder immediately yields literals as they are received and maintains a circular buffer of the last `2^window` bytes for handling backreferences.
23//! There aren't really any computationally intensive operations performed.
24//!
25//! ## Raw Format
26//!
27//! ```text
28//! encoded_data = [entry]*
29//! entry = [tag_bit][tag_data]
30//! if tag_bit == [0] then tag_data = [index][len] (backreference)
31//! if tag_bit == [1] then tag_data = [byte] (literal)
32//! index = window-bits number
33//! len = lookahead-bits number
34//! byte = 8-bit number
35//! ```
36//!
37//! # Credits
38//!
39//! Scott Vokes is the author of the original C library.
40//! His [blog post](https://spin.atomicobject.com/heatshrink-embedded-data-compression/) goes into more detail on the origins and performance.
41
42#![cfg_attr(not(feature = "std"), no_std)]
43
44#[cfg(feature = "std")]
45extern crate std;
46
47mod consts {
48    /// Minimum window size in bits
49    pub const MIN_WINDOW_BITS: u8 = 4;
50
51    /// Maximum window size in bits
52    pub const MAX_WINDOW_BITS: u8 = 15;
53
54    /// Minimum lookahead in bits
55    ///
56    /// The maximum lookahead is `window_bits - 1`
57    pub const MIN_LOOKAHEAD_BITS: u8 = 3;
58
59    /// Bit marker for a literal
60    pub(crate) const LITERAL_MARKER: u8 = 1;
61
62    /// Bit marker for a backref
63    pub(crate) const BACKREF_MARKER: u8 = 0;
64
65    pub(crate) const U8_BITS: u8 = u8::BITS as u8;
66}
67
68/// Internal constants exposed for documentation purposes.
69pub mod _consts {
70    pub use crate::consts::{MAX_WINDOW_BITS, MIN_LOOKAHEAD_BITS, MIN_WINDOW_BITS};
71}
72
73/// Decode data encoded with Heatshrink.
74pub mod decode;
75
76/// Encode data in Heatshrink.
77pub mod encode;
78
79#[cfg(all(feature = "std", test))]
80mod tests {
81    use super::decode::*;
82    use super::encode::*;
83    use std::io::Read;
84
85    #[test]
86    #[cfg_attr(debug, ignore = "Test takes too long for debug profile")]
87    fn test_all_end_to_end_with_big_file() {
88        // let data = include_str!("./encode.rs");
89        let data = include_bytes!("../tests/input/crash-c58fa467dc18f85dce08996eabb8c55f66febd89")
90            .as_slice();
91
92        let it = all_non_indexed_encoders()
93            .zip(all_decoders())
94            .chain(all_indexed_encoders().zip(all_decoders()));
95
96        for (encoder, mut decoder) in it {
97            let mut pull_encoder = PullEncoder::new(encoder, data);
98            let mut enc_buf = vec![];
99            pull_encoder.read_to_end(&mut enc_buf).unwrap();
100            pull_encoder.finish().read_to_end(&mut enc_buf).unwrap();
101
102            let mut dec_buf = vec![];
103            let mut pull_decoder = PullDecoder::new(&mut decoder, enc_buf.as_slice());
104            pull_decoder.read_to_end(&mut dec_buf).unwrap();
105
106            let equal = data
107                .iter()
108                .copied()
109                .zip(dec_buf.iter().copied())
110                .take_while(|(x, y)| *x == *y)
111                .count();
112            assert!(
113                equal == data.len() && equal == dec_buf.len(),
114                "Difference (len {} vs {}) {:?} vs {:?}",
115                data.len(),
116                dec_buf.len(),
117                &data[equal..],
118                &dec_buf[equal..]
119            );
120        }
121    }
122}
icewrap/lib.rs

icewrap/
lib.rs
