zlib_rs/
crc32.rs

1use crate::CRC32_INITIAL_VALUE;
2
3#[cfg(target_arch = "aarch64")]
4pub(crate) mod acle;
5mod braid;
6mod combine;
7#[cfg(target_arch = "x86_64")]
8mod pclmulqdq;
9#[cfg(target_arch = "x86_64")]
10#[cfg(feature = "vpclmulqdq")]
11mod vpclmulqdq;
12
13pub use combine::{crc32_combine, crc32_combine_gen, crc32_combine_op};
14
15pub fn crc32(start: u32, buf: &[u8]) -> u32 {
16    /* For lens < 64, crc32_braid method is faster. The CRC32 instruction for
17     * these short lengths might also prove to be effective */
18    if buf.len() < 64 {
19        return crc32_braid(start, buf);
20    }
21
22    let mut crc_state = Crc32Fold::new_with_initial(start);
23    crc_state.fold(buf, start);
24    crc_state.finish()
25}
26
27pub fn crc32_braid(start: u32, buf: &[u8]) -> u32 {
28    braid::crc32_braid::<5>(start, buf)
29}
30
31pub fn get_crc_table() -> &'static [u32; 256] {
32    braid::get_crc_table()
33}
34
35#[derive(Debug, Clone, Copy)]
36pub struct Crc32Fold {
37    #[cfg(target_arch = "x86_64")]
38    fold: pclmulqdq::Accumulator,
39    value: u32,
40}
41
42impl Default for Crc32Fold {
43    fn default() -> Self {
44        Self::new()
45    }
46}
47
48impl Crc32Fold {
49    pub const fn new() -> Self {
50        Self::new_with_initial(CRC32_INITIAL_VALUE)
51    }
52
53    pub const fn new_with_initial(initial: u32) -> Self {
54        Self {
55            #[cfg(target_arch = "x86_64")]
56            fold: pclmulqdq::Accumulator::new(),
57            value: initial,
58        }
59    }
60
61    pub fn fold(&mut self, src: &[u8], _start: u32) {
62        #[cfg(target_arch = "x86_64")]
63        if crate::cpu_features::is_enabled_pclmulqdq() {
64            return unsafe { self.fold.fold(src, _start) };
65        }
66
67        #[cfg(target_arch = "aarch64")]
68        if crate::cpu_features::is_enabled_crc() {
69            self.value = unsafe { self::acle::crc32_acle_aarch64(self.value, src) };
70            return;
71        }
72
73        // in this case the start value is ignored
74        self.value = braid::crc32_braid::<5>(self.value, src);
75    }
76
77    pub fn fold_copy(&mut self, dst: &mut [u8], src: &[u8]) {
78        #[cfg(target_arch = "x86_64")]
79        if crate::cpu_features::is_enabled_pclmulqdq() {
80            return unsafe { self.fold.fold_copy(dst, src) };
81        }
82
83        self.fold(src, 0);
84        dst[..src.len()].copy_from_slice(src);
85    }
86
87    pub fn finish(self) -> u32 {
88        #[cfg(target_arch = "x86_64")]
89        if crate::cpu_features::is_enabled_pclmulqdq() {
90            return unsafe { self.fold.finish() };
91        }
92
93        self.value
94    }
95}
96
97#[cfg(test)]
98mod test {
99    use braid::crc32_braid;
100
101    use super::*;
102
103    const INPUT: [u8; 1024] = {
104        let mut array = [0; 1024];
105        let mut i = 0;
106        while i < array.len() {
107            array[i] = i as u8;
108            i += 1;
109        }
110
111        array
112    };
113
114    #[test]
115    fn test_crc32_fold() {
116        // input large enough to trigger the SIMD
117        let mut h = crc32fast::Hasher::new_with_initial(CRC32_INITIAL_VALUE);
118        h.update(&INPUT);
119        assert_eq!(crc32(CRC32_INITIAL_VALUE, &INPUT), h.finalize());
120    }
121
122    #[test]
123    fn test_crc32_fold_align() {
124        // SIMD algorithm is sensitive to alignment;
125        for i in 0..16 {
126            for start in [CRC32_INITIAL_VALUE, 42] {
127                let mut h = crc32fast::Hasher::new_with_initial(start);
128                h.update(&INPUT[i..]);
129                assert_eq!(
130                    crc32(start, &INPUT[i..]),
131                    h.finalize(),
132                    "offset = {i}, start = {start}"
133                );
134            }
135        }
136    }
137
138    quickcheck::quickcheck! {
139        fn crc_fold_is_crc32fast(v: Vec<u8>, start: u32) -> bool {
140            let mut h = crc32fast::Hasher::new_with_initial(start);
141            h.update(&v);
142
143            let a = crc32(start, &v) ;
144            let b = h.finalize();
145
146            a == b
147        }
148    }
149
150    #[test]
151    fn chunked() {
152        const INPUT: &[&[u8]] = &[
153            &[116],
154            &[111, 107, 105, 111, 44, 32, 97, 115],
155            &[121, 110, 99, 45, 115, 116, 100, 44],
156            &[32, 97, 110, 100, 32, 115, 109, 111],
157            &[108, 46, 32, 89, 111, 117, 226, 128],
158            &[153, 118, 101, 32, 112, 114, 111, 98],
159            &[97, 98, 108, 121, 32, 117, 115, 101],
160            &[100, 32, 116, 104, 101, 109, 32, 97],
161            &[116, 32, 115, 111, 109, 101, 32, 112],
162            &[111, 105, 110, 116, 44, 32, 101, 105],
163            &[116, 104, 101, 114, 32, 100, 105, 114],
164            &[101, 99, 116, 108, 121, 32, 111, 114],
165            &[0],
166        ];
167
168        const START: u32 = 2380683574;
169
170        let mut in_chunks = START;
171        for chunk in INPUT {
172            in_chunks = crc32(in_chunks, chunk);
173        }
174
175        let flattened: Vec<_> = INPUT.iter().copied().flatten().copied().collect();
176        let flat = crc32(START, &flattened);
177
178        assert_eq!(in_chunks, flat);
179    }
180
181    #[test]
182    fn nasty_alignment() {
183        const START: u32 = 2380683574;
184
185        const FLAT: &[u8] = &[
186            116, 111, 107, 105, 111, 44, 32, 97, 115, 121, 110, 99, 45, 115, 116, 100, 44, 32, 97,
187            110, 100, 32, 115, 109, 111, 108, 46, 32, 89, 111, 117, 226, 128, 153, 118, 101, 32,
188            112, 114, 111, 98, 97, 98, 108, 121, 32, 117, 115, 101, 100, 32, 116, 104, 101, 109,
189            32, 97, 116, 32, 115, 111, 109, 101, 32, 112, 111, 105, 110, 116, 44, 32, 101, 105,
190            116, 104, 101, 114, 32, 100, 105, 114, 101, 99, 116, 108, 121, 32, 111, 114, 0,
191        ];
192
193        let mut i = 0;
194        let mut flat = FLAT.to_vec();
195        while flat[i..].as_ptr() as usize % 16 != 15 {
196            flat.insert(0, 0);
197            i += 1;
198        }
199
200        let flat = &flat[i..];
201
202        assert_eq!(crc32_braid::<5>(START, flat), crc32(START, flat));
203        assert_eq!(crc32(2380683574, flat), 1175758345);
204    }
205}
zlib_rs/crc32.rs

zlib_rs/
crc32.rs
