zlib_rs/
crc32.rs

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

zlib_rs/
crc32.rs
