compress_lib/checksum/
crc32.rs

1//! CRC-32 (ISO-HDLC, the gzip and zip checksum), slicing-by-16.
2
3/// The reflected CRC-32 polynomial (x^32 + x^26 + ... + 1).
4const POLY: u32 = 0xEDB8_8320;
5
6/// Sixteen 256-entry tables: `TABLES[0]` is the classic byte table, and
7/// `TABLES[k][b]` is the CRC of byte `b` followed by `k` zero bytes. Built at
8/// compile time (16 KiB of read-only data).
9static TABLES: [[u32; 256]; 16] = build_tables();
10
11const fn build_tables() -> [[u32; 256]; 16] {
12    let mut tables = [[0u32; 256]; 16];
13    let mut i = 0;
14    while i < 256 {
15        let mut crc = i as u32;
16        let mut bit = 0;
17        while bit < 8 {
18            crc = if crc & 1 != 0 {
19                (crc >> 1) ^ POLY
20            } else {
21                crc >> 1
22            };
23            bit += 1;
24        }
25        tables[0][i] = crc;
26        i += 1;
27    }
28    let mut k = 1;
29    while k < 16 {
30        let mut i = 0;
31        while i < 256 {
32            let prev = tables[k - 1][i];
33            tables[k][i] = (prev >> 8) ^ tables[0][(prev & 0xFF) as usize];
34            i += 1;
35        }
36        k += 1;
37    }
38    tables
39}
40
41/// Advances a raw (pre- and post-inverted by the caller) CRC over `data`.
42fn update(mut crc: u32, data: &[u8]) -> u32 {
43    let t = &TABLES;
44    let mut chunks = data.chunks_exact(16);
45    for c in &mut chunks {
46        let a = crc ^ u32::from_le_bytes([c[0], c[1], c[2], c[3]]);
47        crc = t[15][(a & 0xFF) as usize]
48            ^ t[14][((a >> 8) & 0xFF) as usize]
49            ^ t[13][((a >> 16) & 0xFF) as usize]
50            ^ t[12][(a >> 24) as usize]
51            ^ t[11][c[4] as usize]
52            ^ t[10][c[5] as usize]
53            ^ t[9][c[6] as usize]
54            ^ t[8][c[7] as usize]
55            ^ t[7][c[8] as usize]
56            ^ t[6][c[9] as usize]
57            ^ t[5][c[10] as usize]
58            ^ t[4][c[11] as usize]
59            ^ t[3][c[12] as usize]
60            ^ t[2][c[13] as usize]
61            ^ t[1][c[14] as usize]
62            ^ t[0][c[15] as usize];
63    }
64    for &b in chunks.remainder() {
65        crc = (crc >> 8) ^ t[0][((crc ^ u32::from(b)) & 0xFF) as usize];
66    }
67    crc
68}
69
70/// Computes the CRC-32 of `data` in one call.
71///
72/// This is the checksum gzip (RFC 1952) and zip use: polynomial `0x04C11DB7`
73/// reflected, initial value and final XOR `0xFFFFFFFF`.
74///
75/// # Examples
76///
77/// ```
78/// use compress_lib::checksum::crc32;
79///
80/// assert_eq!(crc32(b"123456789"), 0xCBF4_3926);
81/// assert_eq!(crc32(b""), 0);
82/// ```
83#[must_use]
84pub fn crc32(data: &[u8]) -> u32 {
85    !update(!0, data)
86}
87
88/// A CRC-32 computed over data that arrives in pieces.
89///
90/// The result does not depend on how the data was split.
91///
92/// # Examples
93///
94/// ```
95/// use compress_lib::checksum::{Crc32, crc32};
96///
97/// let mut crc = Crc32::new();
98/// crc.update(b"1234");
99/// crc.update(b"56789");
100/// assert_eq!(crc.finish(), crc32(b"123456789"));
101/// ```
102#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
103pub struct Crc32 {
104    /// The running value, inverted (the register as the algorithm keeps it).
105    state: u32,
106    /// Bytes seen, for [`Crc32::len`] and combining.
107    len: u64,
108}
109
110impl Crc32 {
111    /// A CRC-32 over no data yet.
112    ///
113    /// # Examples
114    ///
115    /// ```
116    /// assert_eq!(compress_lib::checksum::Crc32::new().finish(), 0);
117    /// ```
118    #[must_use]
119    pub const fn new() -> Self {
120        Self { state: !0, len: 0 }
121    }
122
123    /// Continues from a CRC-32 value already computed over `len` bytes (for
124    /// example, a stored checksum that more data is appended to).
125    ///
126    /// # Examples
127    ///
128    /// ```
129    /// use compress_lib::checksum::{Crc32, crc32};
130    ///
131    /// let mut crc = Crc32::from_value(crc32(b"1234"), 4);
132    /// crc.update(b"56789");
133    /// assert_eq!(crc.finish(), crc32(b"123456789"));
134    /// ```
135    #[must_use]
136    pub const fn from_value(crc: u32, len: u64) -> Self {
137        Self { state: !crc, len }
138    }
139
140    /// Feeds more data.
141    ///
142    /// # Examples
143    ///
144    /// ```
145    /// let mut crc = compress_lib::checksum::Crc32::new();
146    /// crc.update(b"abc");
147    /// assert_eq!(crc.finish(), 0x3524_41C2);
148    /// ```
149    pub fn update(&mut self, data: &[u8]) {
150        self.state = update(self.state, data);
151        self.len = self.len.wrapping_add(data.len() as u64);
152    }
153
154    /// The CRC-32 of everything fed so far. Does not reset; more data may
155    /// follow.
156    ///
157    /// # Examples
158    ///
159    /// ```
160    /// let mut crc = compress_lib::checksum::Crc32::new();
161    /// crc.update(b"a");
162    /// assert_eq!(crc.finish(), 0xE8B7_BE43);
163    /// ```
164    #[must_use]
165    pub const fn finish(&self) -> u32 {
166        !self.state
167    }
168
169    /// The number of bytes fed so far (wrapping at 2^64).
170    ///
171    /// # Examples
172    ///
173    /// ```
174    /// let mut crc = compress_lib::checksum::Crc32::new();
175    /// crc.update(b"abc");
176    /// assert_eq!(crc.len(), 3);
177    /// ```
178    #[must_use]
179    pub const fn len(&self) -> u64 {
180        self.len
181    }
182
183    /// `true` when no data has been fed.
184    ///
185    /// # Examples
186    ///
187    /// ```
188    /// assert!(compress_lib::checksum::Crc32::new().is_empty());
189    /// ```
190    #[must_use]
191    pub const fn is_empty(&self) -> bool {
192        self.len == 0
193    }
194
195    /// Appends the checksum of a second piece of data computed separately,
196    /// as if its bytes had been fed here.
197    ///
198    /// # Examples
199    ///
200    /// ```
201    /// use compress_lib::checksum::{Crc32, crc32};
202    ///
203    /// let mut left = Crc32::new();
204    /// left.update(b"hello ");
205    /// let mut right = Crc32::new();
206    /// right.update(b"world");
207    /// left.combine(&right);
208    /// assert_eq!(left.finish(), crc32(b"hello world"));
209    /// ```
210    pub fn combine(&mut self, other: &Crc32) {
211        let combined = crc32_combine(self.finish(), other.finish(), other.len);
212        self.state = !combined;
213        self.len = self.len.wrapping_add(other.len);
214    }
215}
216
217impl Default for Crc32 {
218    fn default() -> Self {
219        Self::new()
220    }
221}
222
223/// Multiplies two polynomials modulo the CRC polynomial (reflected bit
224/// order). The loop runs at most 32 times.
225const fn multiply_mod(a: u32, mut b: u32) -> u32 {
226    let mut product = 0;
227    let mut mask: u32 = 1 << 31;
228    while mask != 0 {
229        if a & mask != 0 {
230            product ^= b;
231        }
232        mask >>= 1;
233        b = if b & 1 != 0 { (b >> 1) ^ POLY } else { b >> 1 };
234    }
235    product
236}
237
238/// `POWERS[k]` is x^(2^k) modulo the polynomial.
239static POWERS: [u32; 67] = build_powers();
240
241const fn build_powers() -> [u32; 67] {
242    let mut powers = [0u32; 67];
243    let mut p: u32 = 1 << 30; // x^1
244    powers[0] = p;
245    let mut k = 1;
246    while k < 67 {
247        p = multiply_mod(p, p);
248        powers[k] = p;
249        k += 1;
250    }
251    powers
252}
253
254/// x^(8 * bytes) modulo the polynomial: the effect of `bytes` zero bytes.
255fn shift_bytes(bytes: u64) -> u32 {
256    let mut p: u32 = 1 << 31; // x^0
257    let mut n = bytes;
258    // Multiplying by 8 is three squarings, so start three entries into the
259    // table; a 64-bit count then needs entries 3 to 66.
260    let mut k = 3;
261    while n != 0 && k < POWERS.len() {
262        if n & 1 != 0 {
263            p = multiply_mod(POWERS[k], p);
264        }
265        n >>= 1;
266        k += 1;
267    }
268    p
269}
270
271/// Combines `crc1` (over data A) and `crc2` (over data B, `len2` bytes long)
272/// into the CRC-32 of A followed by B, in O(log len2).
273///
274/// # Examples
275///
276/// ```
277/// use compress_lib::checksum::{crc32, crc32_combine};
278///
279/// let ab = crc32_combine(crc32(b"hello "), crc32(b"world"), 5);
280/// assert_eq!(ab, crc32(b"hello world"));
281/// ```
282#[must_use]
283pub fn crc32_combine(crc1: u32, crc2: u32, len2: u64) -> u32 {
284    multiply_mod(shift_bytes(len2), crc1) ^ crc2
285}
286
287#[cfg(test)]
288mod tests {
289    use alloc::vec::Vec;
290
291    use proptest::prelude::*;
292
293    use super::*;
294
295    /// Bit-at-a-time reference implementation.
296    fn reference(data: &[u8]) -> u32 {
297        let mut crc = !0u32;
298        for &b in data {
299            crc ^= u32::from(b);
300            for _ in 0..8 {
301                crc = if crc & 1 != 0 {
302                    (crc >> 1) ^ POLY
303                } else {
304                    crc >> 1
305                };
306            }
307        }
308        !crc
309    }
310
311    #[test]
312    fn test_crc32_check_value_matches_catalogue() {
313        // CRC-32/ISO-HDLC check value from the CRC catalogue.
314        assert_eq!(crc32(b"123456789"), 0xCBF4_3926);
315    }
316
317    #[test]
318    fn test_crc32_known_strings_match() {
319        assert_eq!(crc32(b""), 0);
320        assert_eq!(crc32(b"a"), 0xE8B7_BE43);
321        assert_eq!(crc32(b"abc"), 0x3524_41C2);
322        assert_eq!(
323            crc32(b"The quick brown fox jumps over the lazy dog"),
324            0x414F_A339
325        );
326        assert_eq!(crc32(&[0u8; 32]), 0x190A_55AD);
327        assert_eq!(crc32(&[0xFFu8; 32]), 0xFF6C_AB0B);
328    }
329
330    #[test]
331    fn test_crc32_every_length_to_100_matches_reference() {
332        let data: Vec<u8> = (0..100u32).map(|i| (i * 31 + 7) as u8).collect();
333        for n in 0..=data.len() {
334            assert_eq!(crc32(&data[..n]), reference(&data[..n]), "length {n}");
335        }
336    }
337
338    #[test]
339    fn test_crc32_from_value_continues() {
340        let mut crc = Crc32::from_value(crc32(b"12345"), 5);
341        crc.update(b"6789");
342        assert_eq!(crc.finish(), 0xCBF4_3926);
343        assert_eq!(crc.len(), 9);
344        assert!(!crc.is_empty());
345        assert_eq!(Crc32::default(), Crc32::new());
346    }
347
348    #[test]
349    fn test_crc32_combine_empty_second_is_identity() {
350        assert_eq!(crc32_combine(0x1234_5678, 0, 0), 0x1234_5678);
351        let mut a = Crc32::new();
352        a.update(b"x");
353        a.combine(&Crc32::new());
354        assert_eq!(a.finish(), crc32(b"x"));
355    }
356
357    #[test]
358    fn test_crc32_combine_huge_length_terminates() {
359        // Not checked against data (2^64 bytes); this proves the loop ends and
360        // stays deterministic at the extreme.
361        let a = crc32_combine(1, 2, u64::MAX);
362        assert_eq!(a, crc32_combine(1, 2, u64::MAX));
363    }
364
365    proptest! {
366        #[test]
367        fn prop_crc32_matches_reference(data in proptest::collection::vec(any::<u8>(), 0..2048)) {
368            prop_assert_eq!(crc32(&data), reference(&data));
369        }
370
371        #[test]
372        fn prop_crc32_split_invariant(data in proptest::collection::vec(any::<u8>(), 0..2048), cut in any::<usize>()) {
373            let cut = if data.is_empty() { 0 } else { cut % (data.len() + 1) };
374            let mut crc = Crc32::new();
375            crc.update(&data[..cut]);
376            crc.update(&data[cut..]);
377            prop_assert_eq!(crc.finish(), crc32(&data));
378        }
379
380        #[test]
381        fn prop_crc32_combine_matches_concatenation(a in proptest::collection::vec(any::<u8>(), 0..512), b in proptest::collection::vec(any::<u8>(), 0..512)) {
382            let mut whole = a.clone();
383            whole.extend_from_slice(&b);
384            prop_assert_eq!(crc32_combine(crc32(&a), crc32(&b), b.len() as u64), crc32(&whole));
385        }
386    }
387}
compress_lib/checksum/crc32.rs

compress_lib/checksum/
crc32.rs
