crc32fast/specialized/
pclmulqdq.rs

1//! Specialized checksum code for the x86 CPU architecture, based on the efficient algorithm described
2//! in the following whitepaper:
3//!
4//! Gopal, V., Ozturk, E., Guilford, J., Wolrich, G., Feghali, W., Dixon, M., & Karakoyunlu, D. (2009).
5//! _Fast CRC computation for generic polynomials using PCLMULQDQ instruction_. Intel.
6//! (Mirror link: <https://fossies.org/linux/zlib-ng/doc/crc-pclmulqdq.pdf>, accessed 2024-05-20)
7//!
8//! Throughout the code, this work is referred to as "the paper".
9
10#[cfg(target_arch = "x86")]
11use core::arch::x86 as arch;
12#[cfg(target_arch = "x86_64")]
13use core::arch::x86_64 as arch;
14
15#[derive(Clone)]
16pub struct State {
17    state: u32,
18}
19
20impl State {
21    #[cfg(not(feature = "std"))]
22    pub fn new(state: u32) -> Option<Self> {
23        if cfg!(target_feature = "pclmulqdq")
24            && cfg!(target_feature = "sse2")
25            && cfg!(target_feature = "sse4.1")
26        {
27            // SAFETY: The conditions above ensure that all
28            //         required instructions are supported by the CPU.
29            Some(Self { state })
30        } else {
31            None
32        }
33    }
34
35    #[cfg(feature = "std")]
36    pub fn new(state: u32) -> Option<Self> {
37        if is_x86_feature_detected!("pclmulqdq")
38            && is_x86_feature_detected!("sse2")
39            && is_x86_feature_detected!("sse4.1")
40        {
41            // SAFETY: The conditions above ensure that all
42            //         required instructions are supported by the CPU.
43            Some(Self { state })
44        } else {
45            None
46        }
47    }
48
49    pub fn update(&mut self, buf: &[u8]) {
50        // SAFETY: The `State::new` constructor ensures that all
51        //         required instructions are supported by the CPU.
52        self.state = unsafe { calculate(self.state, buf) }
53    }
54
55    pub fn finalize(self) -> u32 {
56        self.state
57    }
58
59    pub fn reset(&mut self) {
60        self.state = 0;
61    }
62
63    pub fn combine(&mut self, other: u32, amount: u64) {
64        self.state = crate::combine::combine(self.state, other, amount);
65    }
66}
67
68const K1: i64 = 0x154442bd4;
69const K2: i64 = 0x1c6e41596;
70const K3: i64 = 0x1751997d0;
71const K4: i64 = 0x0ccaa009e;
72const K5: i64 = 0x163cd6124;
73
74const P_X: i64 = 0x1DB710641;
75const U_PRIME: i64 = 0x1F7011641;
76
77#[target_feature(enable = "pclmulqdq", enable = "sse2", enable = "sse4.1")]
78unsafe fn calculate(crc: u32, mut data: &[u8]) -> u32 {
79    // In theory we can accelerate smaller chunks too, but for now just rely on
80    // the fallback implementation as it's too much hassle and doesn't seem too
81    // beneficial.
82    if data.len() < 128 {
83        return crate::baseline::update_fast_16(crc, data);
84    }
85
86    // Step 1: fold by 4 loop
87    let mut x3 = get(&mut data);
88    let mut x2 = get(&mut data);
89    let mut x1 = get(&mut data);
90    let mut x0 = get(&mut data);
91
92    // fold in our initial value, part of the incremental crc checksum
93    x3 = arch::_mm_xor_si128(x3, arch::_mm_cvtsi32_si128(!crc as i32));
94
95    let k1k2 = arch::_mm_set_epi64x(K2, K1);
96    while data.len() >= 64 {
97        x3 = reduce128(x3, get(&mut data), k1k2);
98        x2 = reduce128(x2, get(&mut data), k1k2);
99        x1 = reduce128(x1, get(&mut data), k1k2);
100        x0 = reduce128(x0, get(&mut data), k1k2);
101    }
102
103    let k3k4 = arch::_mm_set_epi64x(K4, K3);
104    let mut x = reduce128(x3, x2, k3k4);
105    x = reduce128(x, x1, k3k4);
106    x = reduce128(x, x0, k3k4);
107
108    // Step 2: fold by 1 loop
109    while data.len() >= 16 {
110        x = reduce128(x, get(&mut data), k3k4);
111    }
112
113    // Perform step 3, reduction from 128 bits to 64 bits. This is
114    // significantly different from the paper and basically doesn't follow it
115    // at all. It's not really clear why, but implementations of this algorithm
116    // in Chrome/Linux diverge in the same way. It is beyond me why this is
117    // different than the paper, maybe the paper has like errata or something?
118    // Unclear.
119    //
120    // It's also not clear to me what's actually happening here and/or why, but
121    // algebraically what's happening is:
122    //
123    // x = (x[0:63] • K4) ^ x[64:127]           // 96 bit result
124    // x = ((x[0:31] as u64) • K5) ^ x[32:95]   // 64 bit result
125    //
126    // It's... not clear to me what's going on here. The paper itself is pretty
127    // vague on this part but definitely uses different constants at least.
128    // It's not clear to me, reading the paper, where the xor operations are
129    // happening or why things are shifting around. This implementation...
130    // appears to work though!
131    let x = arch::_mm_xor_si128(
132        arch::_mm_clmulepi64_si128(x, k3k4, 0x10),
133        arch::_mm_srli_si128(x, 8),
134    );
135    let x = arch::_mm_xor_si128(
136        arch::_mm_clmulepi64_si128(
137            arch::_mm_and_si128(x, arch::_mm_set_epi32(0, 0, 0, !0)),
138            arch::_mm_set_epi64x(0, K5),
139            0x00,
140        ),
141        arch::_mm_srli_si128(x, 4),
142    );
143
144    // Perform a Barrett reduction from our now 64 bits to 32 bits. The
145    // algorithm for this is described at the end of the paper, and note that
146    // this also implements the "bit reflected input" variant.
147    let pu = arch::_mm_set_epi64x(U_PRIME, P_X);
148
149    // T1(x) = ⌊(R(x) % x^32)⌋ • μ
150    let t1 = arch::_mm_clmulepi64_si128(
151        arch::_mm_and_si128(x, arch::_mm_set_epi32(0, 0, 0, !0)),
152        pu,
153        0x10,
154    );
155    // T2(x) = ⌊(T1(x) % x^32)⌋ • P(x)
156    let t2 = arch::_mm_clmulepi64_si128(
157        arch::_mm_and_si128(t1, arch::_mm_set_epi32(0, 0, 0, !0)),
158        pu,
159        0x00,
160    );
161    // We're doing the bit-reflected variant, so get the upper 32-bits of the
162    // 64-bit result instead of the lower 32-bits.
163    //
164    // C(x) = R(x) ^ T2(x) / x^32
165    let c = arch::_mm_extract_epi32(arch::_mm_xor_si128(x, t2), 1) as u32;
166
167    if !data.is_empty() {
168        crate::baseline::update_fast_16(!c, data)
169    } else {
170        !c
171    }
172}
173
174unsafe fn reduce128(a: arch::__m128i, b: arch::__m128i, keys: arch::__m128i) -> arch::__m128i {
175    let t1 = arch::_mm_clmulepi64_si128(a, keys, 0x00);
176    let t2 = arch::_mm_clmulepi64_si128(a, keys, 0x11);
177    arch::_mm_xor_si128(arch::_mm_xor_si128(b, t1), t2)
178}
179
180unsafe fn get(a: &mut &[u8]) -> arch::__m128i {
181    debug_assert!(a.len() >= 16);
182    let r = arch::_mm_loadu_si128(a.as_ptr() as *const arch::__m128i);
183    *a = &a[16..];
184    r
185}
186
187#[cfg(test)]
188mod test {
189    quickcheck::quickcheck! {
190        fn check_against_baseline(init: u32, chunks: Vec<(Vec<u8>, usize)>) -> bool {
191            let mut baseline = super::super::super::baseline::State::new(init);
192            let mut pclmulqdq = super::State::new(init).expect("not supported");
193            for (chunk, mut offset) in chunks {
194                // simulate random alignments by offsetting the slice by up to 15 bytes
195                offset &= 0xF;
196                if chunk.len() <= offset {
197                    baseline.update(&chunk);
198                    pclmulqdq.update(&chunk);
199                } else {
200                    baseline.update(&chunk[offset..]);
201                    pclmulqdq.update(&chunk[offset..]);
202                }
203            }
204            pclmulqdq.finalize() == baseline.finalize()
205        }
206    }
207}
crc32fast/specialized/pclmulqdq.rs

crc32fast/specialized/
pclmulqdq.rs
