crc32fast/
baseline.rs

1use crate::table::CRC32_TABLE;
2
3/// Folds the first 16 bytes of `block` into `crc`.
4///
5/// `block` must be at least 16 bytes long. The decode is explicitly
6/// little-endian, so the result is identical on big-endian targets.
7#[inline(always)]
8fn fold_16(crc: u32, block: &[u8]) -> u32 {
9    let w0 = u32::from_le_bytes([block[0], block[1], block[2], block[3]]) ^ crc;
10    CRC32_TABLE[0x0][block[0xf] as usize]
11        ^ CRC32_TABLE[0x1][block[0xe] as usize]
12        ^ CRC32_TABLE[0x2][block[0xd] as usize]
13        ^ CRC32_TABLE[0x3][block[0xc] as usize]
14        ^ CRC32_TABLE[0x4][block[0xb] as usize]
15        ^ CRC32_TABLE[0x5][block[0xa] as usize]
16        ^ CRC32_TABLE[0x6][block[0x9] as usize]
17        ^ CRC32_TABLE[0x7][block[0x8] as usize]
18        ^ CRC32_TABLE[0x8][block[0x7] as usize]
19        ^ CRC32_TABLE[0x9][block[0x6] as usize]
20        ^ CRC32_TABLE[0xa][block[0x5] as usize]
21        ^ CRC32_TABLE[0xb][block[0x4] as usize]
22        ^ CRC32_TABLE[0xc][(w0 >> 24) as usize]
23        ^ CRC32_TABLE[0xd][((w0 >> 16) & 0xFF) as usize]
24        ^ CRC32_TABLE[0xe][((w0 >> 8) & 0xFF) as usize]
25        ^ CRC32_TABLE[0xf][(w0 & 0xFF) as usize]
26}
27
28/// Folds the first 8 bytes of `block` into `crc` (slicing-by-8).
29#[inline(always)]
30fn fold_8(crc: u32, block: &[u8]) -> u32 {
31    let w0 = u32::from_le_bytes([block[0], block[1], block[2], block[3]]) ^ crc;
32    CRC32_TABLE[0x0][block[7] as usize]
33        ^ CRC32_TABLE[0x1][block[6] as usize]
34        ^ CRC32_TABLE[0x2][block[5] as usize]
35        ^ CRC32_TABLE[0x3][block[4] as usize]
36        ^ CRC32_TABLE[0x4][(w0 >> 24) as usize]
37        ^ CRC32_TABLE[0x5][((w0 >> 16) & 0xFF) as usize]
38        ^ CRC32_TABLE[0x6][((w0 >> 8) & 0xFF) as usize]
39        ^ CRC32_TABLE[0x7][(w0 & 0xFF) as usize]
40}
41
42/// Folds the first 4 bytes of `block` into `crc` (slicing-by-4).
43#[inline(always)]
44fn fold_4(crc: u32, block: &[u8]) -> u32 {
45    let w0 = u32::from_le_bytes([block[0], block[1], block[2], block[3]]) ^ crc;
46    CRC32_TABLE[0x0][(w0 >> 24) as usize]
47        ^ CRC32_TABLE[0x1][((w0 >> 16) & 0xFF) as usize]
48        ^ CRC32_TABLE[0x2][((w0 >> 8) & 0xFF) as usize]
49        ^ CRC32_TABLE[0x3][(w0 & 0xFF) as usize]
50}
51
52pub(crate) fn update_fast_16(prev: u32, mut buf: &[u8]) -> u32 {
53    const UNROLL: usize = 4;
54    const BYTES_AT_ONCE: usize = 16 * UNROLL;
55
56    let mut crc = !prev;
57
58    while buf.len() >= BYTES_AT_ONCE {
59        for _ in 0..UNROLL {
60            crc = fold_16(crc, buf);
61            buf = &buf[16..];
62        }
63    }
64
65    // Fold whatever whole 16-byte blocks remain rather than handing them to the
66    // byte-at-a-time loop.
67    while buf.len() >= 16 {
68        crc = fold_16(crc, buf);
69        buf = &buf[16..];
70    }
71
72    update_short(!crc, buf)
73}
74
75/// Like `update_fast_16`, but without the 16-byte loops, for buffers shorter than 16 bytes.
76///
77/// Up to 3 bytes go straight to the byte loop. Longer buffers are folded out of line, so a caller
78/// that inlines this doesn't need the extra registers the slicing code uses.
79#[inline]
80pub(crate) fn update_short(prev: u32, buf: &[u8]) -> u32 {
81    if buf.len() < 4 {
82        update_slow(prev, buf)
83    } else {
84        update_4_to_15(prev, buf)
85    }
86}
87
88#[inline(never)]
89fn update_4_to_15(prev: u32, mut buf: &[u8]) -> u32 {
90    let mut crc = !prev;
91
92    if buf.len() >= 8 {
93        crc = fold_8(crc, buf);
94        buf = &buf[8..];
95    }
96    if buf.len() >= 4 {
97        crc = fold_4(crc, buf);
98        buf = &buf[4..];
99    }
100
101    update_slow(!crc, buf)
102}
103
104pub(crate) fn update_slow(prev: u32, buf: &[u8]) -> u32 {
105    let mut crc = !prev;
106
107    for &byte in buf.iter() {
108        crc = CRC32_TABLE[0][((crc as u8) ^ byte) as usize] ^ (crc >> 8);
109    }
110
111    !crc
112}
113
114#[cfg(test)]
115mod test {
116    #[test]
117    fn slow() {
118        assert_eq!(super::update_slow(0, b""), 0);
119
120        // test vectors from the iPXE project (input and output are bitwise negated)
121        assert_eq!(super::update_slow(!0x12345678, b""), !0x12345678);
122        assert_eq!(super::update_slow(!0xffffffff, b"hello world"), !0xf2b5ee7a);
123        assert_eq!(super::update_slow(!0xffffffff, b"hello"), !0xc9ef5979);
124        assert_eq!(super::update_slow(!0xc9ef5979, b" world"), !0xf2b5ee7a);
125
126        // Some vectors found on Rosetta code
127        assert_eq!(super::update_slow(0, b"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"), 0x190A55AD);
128        assert_eq!(super::update_slow(0, b"\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF"), 0xFF6CAB0B);
129        assert_eq!(super::update_slow(0, b"\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0A\x0B\x0C\x0D\x0E\x0F\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1A\x1B\x1C\x1D\x1E\x1F"), 0x91267E8A);
130    }
131
132    quickcheck::quickcheck! {
133        fn fast_16_is_the_same_as_slow(crc: u32, bytes: Vec<u8>) -> bool {
134            super::update_fast_16(crc, &bytes) == super::update_slow(crc, &bytes)
135        }
136    }
137}
crc32fast/baseline.rs

crc32fast/
baseline.rs
