slice_by_8/
algorithm.rs

1//!
2//! This CRC implementation is based on slice-by-8 intel algorithm from the paper
3//! "A Systematic Approach to building High Performance, Software-based, CRC Generators"
4//! By Intel Researche and Development"
5//! Adapation from <https://create.stephan-brumme.com/crc32/>
6//! LookUpTable generated with polynomial 0x04c11db7
7use core::mem::MaybeUninit;
8
9/// Computes the CRC checksum for the specified buffer using the slicing by 8
10/// algorithm over 64 bit quantities.
11///
12/// # Example
13/// ```
14/// use slice_by_8::slice_by_8;
15/// 
16/// let my_lookup_table: [[u32; 256]; 8] = slice_by_8::generate_table(slice_by_8::crc32::POLYNOMIAL);
17/// const HASH_ME: &[u8] = b"abcdefghijklmnopqrstuvwxyz";
18///
19/// assert_eq!(slice_by_8(HASH_ME, &my_lookup_table), 0x4C2750BD);
20/// ```
21#[inline(always)]
22pub fn slice_by_8(buf: &[u8], lookup_table: &[[u32; 256]; 8]) -> u32 {
23    slice_by_8_with_seed(buf, 0, lookup_table)
24}
25
26/// Computes the CRC checksum for the specified buffer using the slicing by 8
27/// algorithm over 64 bit quantities, adding a seed to the result.
28///
29/// # Example
30/// ```
31/// use slice_by_8::slice_by_8_with_seed;
32/// 
33/// let my_lookup_table: [[u32; 256]; 8] = slice_by_8::generate_table(slice_by_8::crc32::POLYNOMIAL);
34/// const HASH_ME: &[u8] = b"abcdefghijklmnopqrstuvwxyz";
35///
36/// assert_eq!(slice_by_8_with_seed(HASH_ME, 123456789, &my_lookup_table), 0xEADB5034);
37/// ```
38pub fn slice_by_8_with_seed(buf: &[u8], seed: u32, lookup_table: &[[u32; 256]; 8]) -> u32 {
39    let mut crc = !seed;
40
41    // Consume all bits until we are 8 bits aligned
42    let (prefix, shorts, suffix) = unsafe { buf.align_to::<u64>() };
43    crc = prefix.iter().fold(crc, |acc, byte| {
44        lookup_table[0][((acc ^ *byte as u32) & 0xff) as usize] ^ (acc >> 8)
45    });
46
47    // Process eight bytes at once (Slicing-by-8)
48    #[cfg(target_endian = "big")]
49    let process_8_bytes_at_once = |acc: u32, byte: &u64| {
50        let byte = *byte;
51        let (low, high) = (
52            (byte as u32) ^ acc.reverse_bits(),
53            (byte >> u32::BITS) as u32,
54        );
55        lookup_table[0][(high & 0xFF) as usize]
56            ^ lookup_table[1][((high >> 8) & 0xFF) as usize]
57            ^ lookup_table[2][((high >> 16) & 0xFF) as usize]
58            ^ lookup_table[3][((high >> 24) & 0xFF) as usize]
59            ^ lookup_table[4][(low & 0xFF) as usize]
60            ^ lookup_table[5][((low >> 8) & 0xFF) as usize]
61            ^ lookup_table[6][((low >> 16) & 0xFF) as usize]
62            ^ lookup_table[7][((low >> 24) & 0xFF) as usize]
63    };
64
65    #[cfg(target_endian = "little")]
66    let process_8_bytes_at_once = |acc: u32, byte: &u64| {
67        let byte = *byte;
68        let (low, high) = ((byte as u32) ^ acc, (byte >> u32::BITS) as u32);
69        lookup_table[0][((high >> 24) & 0xFF) as usize]
70            ^ lookup_table[1][((high >> 16) & 0xFF) as usize]
71            ^ lookup_table[2][((high >> 8) & 0xFF) as usize]
72            ^ lookup_table[3][(high & 0xFF) as usize]
73            ^ lookup_table[4][((low >> 24) & 0xFF) as usize]
74            ^ lookup_table[5][((low >> 16) & 0xFF) as usize]
75            ^ lookup_table[6][((low >> 8) & 0xFF) as usize]
76            ^ lookup_table[7][(low & 0xFF) as usize]
77    };
78    crc = shorts.iter().fold(crc, process_8_bytes_at_once);
79
80    // Consume remaining 1 to 7 bytes (standard algorithm)
81    !suffix.iter().fold(crc, |acc, byte| {
82        (acc >> 8) ^ lookup_table[0][((acc ^ *byte as u32) & 0xff) as usize]
83    })
84}
85
86/// Generate a lookup table.
87/// The given polynomial is reversed before the generation
88///
89/// # Example
90/// ```
91/// use slice_by_8::{crc32,generate_table};
92///
93/// assert_eq!(generate_table(crc32::POLYNOMIAL), crc32::LOOKUP_TABLE);
94/// ```
95pub fn generate_table(polynomial: u32) -> [[u32; 256]; 8] {
96    let mut generated_lookup_table = MaybeUninit::<[[u32; 256]; 8]>::uninit();
97
98    // This implementation is not pleasant to read.
99    // A better version is above but is not compilable in constant expression for now
100    unsafe {
101        // Generate table 0
102        for (i, x) in generated_lookup_table.assume_init_mut()[0]
103            .iter_mut()
104            .enumerate()
105        {
106            *x = (0..8).fold(i as u32, |acc, _| {
107                (acc >> 1) ^ ((acc & 1) * polynomial.reverse_bits())
108            });
109        }
110
111        // Generate table 1..=7
112        let table_0 = &generated_lookup_table.assume_init()[0];
113        for i in 1..=7 {
114            let table_before = &generated_lookup_table.assume_init()[i - 1];
115            for (i, x) in generated_lookup_table.assume_init_mut()[i]
116                .iter_mut()
117                .enumerate()
118            {
119                *x = (table_before[i] >> 8) ^ table_0[(table_before[i] & 0xFF) as usize];
120            }
121        }
122        *generated_lookup_table.assume_init_mut()
123    }
124}
125
126#[cfg(test)]
127mod tests {
128    use crate as slice_by_8;
129    use slice_by_8::crc32::LOOKUP_TABLE;
130
131    #[test]
132    fn slice_by_8_no_seed() {
133        const HASH_ME: &[u8] = b"abcdefghijklmnopqrstuvwxyz";
134        assert_eq!(slice_by_8::slice_by_8(HASH_ME, &LOOKUP_TABLE), 0x4C2750BD);
135    }
136
137    #[test]
138    fn slice_by_8_with_seed() {
139        const HASH_ME: &[u8] = b"abcdefghijklmnopqrstuvwxyz";
140        assert_eq!(
141            slice_by_8::slice_by_8_with_seed(HASH_ME, 123456789, &LOOKUP_TABLE),
142            0xEADB5034
143        );
144    }
145}
slice_by_8/algorithm.rs

slice_by_8/
algorithm.rs
