crc32fast/
combine.rs

1const POLY: u32 = 0xedb88320;
2
3static X2N_TABLE: [u32; 32] = [
4    0x00800000, 0x00008000, 0xedb88320, 0xb1e6b092, 0xa06a2517, 0xed627dae, 0x88d14467, 0xd7bbfe6a,
5    0xec447f11, 0x8e7ea170, 0x6427800e, 0x4d47bae0, 0x09fe548f, 0x83852d0f, 0x30362f1a, 0x7b5a9cc3,
6    0x31fec169, 0x9fec022a, 0x6c8dedc4, 0x15d6874d, 0x5fde7a4e, 0xbad90e37, 0x2e4e5eef, 0x4eaba214,
7    0xa8a472c0, 0x429a969e, 0x148d302a, 0xc40ba6d0, 0xc4e22c3c, 0x40000000, 0x20000000, 0x08000000,
8];
9
10// Calculates a(x) multiplied by b(x) modulo p(x), where p(x) is the CRC polynomial,
11// reflected. For speed, this requires that a not be zero.
12const fn multiply(a: u32, mut b: u32) -> u32 {
13    let mut p = 0u32;
14
15    let mut i = 0;
16    while i < 32 {
17        p ^= b & ((a >> (31 - i)) & 1).wrapping_neg();
18        b = (b >> 1) ^ ((b & 1).wrapping_neg() & POLY);
19        i += 1;
20    }
21
22    p
23}
24
25/// Returns x^(8 * len) modulo p(x), reflected. Multiplying a CRC state by it appends `len` zero
26/// bytes.
27const fn x8n(len: u64) -> u32 {
28    let mut p = 0x8000_0000; // x^0
29    let mut sq = 0x0080_0000; // x^8
30    let mut n = len;
31    while n != 0 {
32        if n & 1 != 0 {
33            p = multiply(sq, p);
34        }
35        sq = multiply(sq, sq);
36        n >>= 1;
37    }
38    p
39}
40
41/// The constants that fold a 128-bit accumulator forward by `bits` bits with two carry-less
42/// multiplies: `(x^(bits + 32), x^(bits - 32))` modulo p(x), reflected, as 33-bit values (the
43/// `K1`..`K4` of `specialized/pclmulqdq.rs`, which a test checks).
44#[cfg_attr(
45    not(all(stable_arm_crc32_intrinsics, target_arch = "aarch64")),
46    allow(dead_code)
47)]
48pub(crate) const fn fold_keys(bits: u64) -> [u64; 2] {
49    [
50        (x8n((bits + 32) / 8) as u64) << 1,
51        (x8n((bits - 32) / 8) as u64) << 1,
52    ]
53}
54
55/// Builds tables that append `len` zero bytes to a CRC state a byte at a time: the new state is
56/// the XOR of `table[k][(state >> (8 * k)) & 0xFF]` for `k` in `0..4`.
57#[cfg_attr(
58    not(all(stable_arm_crc32_intrinsics, target_arch = "aarch64")),
59    allow(dead_code)
60)]
61pub(crate) const fn shift_table(len: u64) -> [[u32; 256]; 4] {
62    let x = x8n(len);
63    let mut table = [[0u32; 256]; 4];
64    let mut k = 0;
65    while k < 4 {
66        let mut v = 0;
67        while v < 256 {
68            table[k][v] = multiply(x, (v as u32) << (8 * k));
69            v += 1;
70        }
71        k += 1;
72    }
73    table
74}
75
76/// Appends the zero bytes `table` was built for to the CRC state `state`.
77#[cfg_attr(
78    not(all(stable_arm_crc32_intrinsics, target_arch = "aarch64")),
79    allow(dead_code)
80)]
81#[inline(always)]
82pub(crate) fn shift(table: &[[u32; 256]; 4], state: u32) -> u32 {
83    table[0][(state & 0xFF) as usize]
84        ^ table[1][((state >> 8) & 0xFF) as usize]
85        ^ table[2][((state >> 16) & 0xFF) as usize]
86        ^ table[3][(state >> 24) as usize]
87}
88
89pub(crate) fn combine(crc1: u32, crc2: u32, len2: u64) -> u32 {
90    // Special case: If the length of the second chunk is zero, return the hash
91    // of the first chunk.
92    if len2 == 0 {
93        return crc1;
94    }
95
96    // We are padding the first checksum with len2-amount of zeroes. For efficiency,
97    // this is done in powers-of-two via a lookup table rather than one by one.
98    let mut p = crc1;
99    let n = 64 - len2.leading_zeros();
100    for i in 0..n {
101        if (len2 >> i & 1) != 0 {
102            p = multiply(X2N_TABLE[(i & 0x1F) as usize], p);
103        }
104    }
105
106    p ^ crc2
107}
108
109#[test]
110fn fold_keys_match_the_x86_constants() {
111    assert_eq!(fold_keys(128), [0x1751997d0, 0x0ccaa009e]);
112    assert_eq!(fold_keys(512), [0x154442bd4, 0x1c6e41596]);
113    assert_eq!(fold_keys(1024), [0x1e88ef372, 0x14a7fe880]);
114    assert_eq!(fold_keys(2048), [0x11542778a, 0x1322d1430]);
115}
116
117#[test]
118fn shift_table_appends_zeros() {
119    for &len in &[1u64, 7, 512, 32768] {
120        let table = shift_table(len);
121        let zeros = vec![0u8; len as usize];
122        for &state in &[0u32, 1, 0x8000_0000, 0xDEAD_BEEF, 0xFFFF_FFFF, 0x1234_5678] {
123            // `update_slow` takes and returns finalized CRCs, which are the inverted state.
124            let expected = !crate::baseline::update_slow(!state, &zeros);
125            assert_eq!(
126                shift(&table, state),
127                expected,
128                "len={len} state={state:#010x}"
129            );
130        }
131    }
132}
133
134#[test]
135fn golden() {
136    assert_eq!(combine(0x0, 0x1, 0x0), 0x0);
137    assert_eq!(combine(0xc401f8c9, 0x00000000, 0x0), 0xc401f8c9);
138    assert_eq!(combine(0x7cba3d5e, 0xe7466d39, 0xb), 0x76365c4f);
139    assert_eq!(combine(0x576c62d6, 0x123256e1, 0x47), 0x579a636);
140    assert_eq!(combine(0x4f626f9a, 0x9e5ccbf5, 0xa59d), 0x98d43168);
141    assert_eq!(combine(0xa09b8a88, 0x815b0f48, 0x40f39511), 0xd7a5f79);
142    assert_eq!(
143        combine(0x7f6a4306, 0xbc929646, 0x828cde72b3e25301),
144        0xef922dda
145    );
146}
crc32fast/combine.rs

crc32fast/
combine.rs
