zlib_rs/crc32/
combine.rs

1use super::braid::CRC32_LSB_POLY;
2
3pub const fn crc32_combine(crc1: u32, crc2: u32, len2: u64) -> u32 {
4    crc32_combine_op(crc1, crc2, crc32_combine_gen(len2))
5}
6
7#[inline(always)]
8const fn crc32_combine_gen(len2: u64) -> u32 {
9    x2nmodp(len2, 3)
10}
11
12#[inline(always)]
13const fn crc32_combine_op(crc1: u32, crc2: u32, op: u32) -> u32 {
14    multmodp(op, crc1) ^ crc2
15}
16
17const X2N_TABLE: [u32; 32] = [
18    0x40000000, 0x20000000, 0x08000000, 0x00800000, 0x00008000, 0xedb88320, 0xb1e6b092, 0xa06a2517,
19    0xed627dae, 0x88d14467, 0xd7bbfe6a, 0xec447f11, 0x8e7ea170, 0x6427800e, 0x4d47bae0, 0x09fe548f,
20    0x83852d0f, 0x30362f1a, 0x7b5a9cc3, 0x31fec169, 0x9fec022a, 0x6c8dedc4, 0x15d6874d, 0x5fde7a4e,
21    0xbad90e37, 0x2e4e5eef, 0x4eaba214, 0xa8a472c0, 0x429a969e, 0x148d302a, 0xc40ba6d0, 0xc4e22c3c,
22];
23
24// Return a(x) multiplied by b(x) modulo p(x), where p(x) is the CRC polynomial,
25// reflected. For speed, this requires that a not be zero.
26const fn multmodp(a: u32, mut b: u32) -> u32 {
27    let mut m = 1 << 31;
28    let mut p = 0;
29
30    loop {
31        if (a & m) != 0 {
32            p ^= b;
33            if (a & (m - 1)) == 0 {
34                break;
35            }
36        }
37        m >>= 1;
38        b = if (b & 1) != 0 {
39            (b >> 1) ^ CRC32_LSB_POLY as u32
40        } else {
41            b >> 1
42        };
43    }
44
45    p
46}
47
48// Return x^(n * 2^k) modulo p(x).
49const fn x2nmodp(mut n: u64, mut k: u32) -> u32 {
50    let mut p: u32 = 1 << 31; /* x^0 == 1 */
51
52    while n > 0 {
53        if (n & 1) != 0 {
54            p = multmodp(X2N_TABLE[k as usize & 31], p);
55        }
56        n >>= 1;
57        k += 1;
58    }
59
60    p
61}
62
63#[cfg(test)]
64mod test {
65    use super::*;
66
67    use crate::crc32;
68
69    #[test]
70    fn test_crc32_combine() {
71        ::quickcheck::quickcheck(test as fn(_) -> _);
72
73        fn test(data: Vec<u8>) -> bool {
74            let Some(buf_len) = data.first().copied() else {
75                return true;
76            };
77
78            let buf_size = Ord::max(buf_len, 1) as usize;
79
80            let crc0 = 0;
81            let mut crc1 = crc0;
82            let mut crc2 = crc0;
83
84            /* CRC32 */
85            for chunk in data.chunks(buf_size) {
86                let crc3 = crc32(crc0, chunk);
87                let op = crc32_combine_gen(chunk.len() as _);
88                let crc4 = crc32_combine_op(crc1, crc3, op);
89                crc1 = crc32(crc1, chunk);
90
91                assert_eq!(crc1, crc4);
92            }
93
94            crc2 = crc32(crc2, &data);
95
96            assert_eq!(crc1, crc2);
97
98            let combine1 = crc32_combine(crc1, crc2, data.len() as _);
99            let combine2 = crc32_combine(crc1, crc1, data.len() as _);
100            assert_eq!(combine1, combine2);
101
102            // Fast CRC32 combine.
103            let op = crc32_combine_gen(data.len() as _);
104            let combine1 = crc32_combine_op(crc1, crc2, op);
105            let combine2 = crc32_combine_op(crc2, crc1, op);
106            assert_eq!(combine1, combine2);
107
108            let combine1 = crc32_combine(crc1, crc2, data.len() as _);
109            let combine2 = crc32_combine_op(crc2, crc1, op);
110            assert_eq!(combine1, combine2);
111
112            true
113        }
114    }
115}
zlib_rs/crc32/combine.rs

zlib_rs/crc32/
combine.rs
