const_crc32_nostd/
lib.rs

1//! A `const fn` crc32 checksum implementation.
2//!
3//! # Examples
4//!
5//! ```
6//! use const_crc32_nostd as const_crc32;
7//! const BYTES: &[u8] = "The quick brown fox jumps over the lazy dog".as_bytes();
8//! const CKSUM: u32 = const_crc32::crc32(BYTES);
9//! assert_eq!(CKSUM, 0x414fa339_u32);
10//! ```
11#![no_std]
12
13/// used to generate up a [u32; 256] lookup table in `crc32`. this computes
14/// the table on demand for a given "index" `i`
15#[rustfmt::skip]
16const fn table_fn(i: u32) -> u32 {
17    let mut out = i;
18
19    out = if out & 1 == 1 { 0xedb88320 ^ (out >> 1) } else { out >> 1 };
20    out = if out & 1 == 1 { 0xedb88320 ^ (out >> 1) } else { out >> 1 };
21    out = if out & 1 == 1 { 0xedb88320 ^ (out >> 1) } else { out >> 1 };
22    out = if out & 1 == 1 { 0xedb88320 ^ (out >> 1) } else { out >> 1 };
23    out = if out & 1 == 1 { 0xedb88320 ^ (out >> 1) } else { out >> 1 };
24    out = if out & 1 == 1 { 0xedb88320 ^ (out >> 1) } else { out >> 1 };
25    out = if out & 1 == 1 { 0xedb88320 ^ (out >> 1) } else { out >> 1 };
26    out = if out & 1 == 1 { 0xedb88320 ^ (out >> 1) } else { out >> 1 };
27
28    out
29}
30
31const fn get_table() -> [u32; 256] {
32    let mut table: [u32; 256] = [0u32; 256];
33    let mut i = 0;
34
35    while i < 256 {
36        table[i] = table_fn(i as u32);
37        i += 1;
38    }
39
40    table
41}
42
43const TABLE: [u32; 256] = get_table();
44
45/// A `const fn` crc32 checksum implementation.
46///
47/// Note: this is a naive implementation that should be expected to have poor performance
48/// if used on dynamic data at runtime. Usage should generally be restricted to declaring
49/// `const` variables based on `static` or `const` data available at build time.
50pub const fn crc32(buf: &[u8]) -> u32 {
51    crc32_seed(buf, 0)
52}
53
54/// Calculate crc32 checksum, using provided `seed` as the initial state, instead of the
55/// default initial state of `0u32`.
56///
57/// # Examples
58///
59/// Calculating the checksum from several parts of a larger input:
60///
61/// ```
62/// use const_crc32_nostd as const_crc32;
63///
64/// const BYTES: &[u8] = "The quick brown fox jumps over the lazy dog".as_bytes();
65///
66/// let mut cksum = 0u32;
67///
68/// cksum = const_crc32::crc32_seed(&BYTES[0..10], cksum);
69/// cksum = const_crc32::crc32_seed(&BYTES[10..15], cksum);
70/// cksum = const_crc32::crc32_seed(&BYTES[15..], cksum);
71///
72/// assert_eq!(cksum, const_crc32::crc32(BYTES));
73/// ```
74///
75/// Using separate seeds for different kinds of data, to produce different checksums depending
76/// on what kind of data the bytes represent:
77///
78/// ```
79/// use const_crc32_nostd as const_crc32;
80///
81/// const THING_ONE_SEED: u32 = 0xbaaaaaad_u32;
82/// const THING_TWO_SEED: u32 = 0x2bad2bad_u32;
83///
84/// let thing_one_bytes = "bump! thump!".as_bytes();
85/// let thing_two_bytes = "thump! bump!".as_bytes();
86///
87/// let thing_one_cksum = const_crc32::crc32_seed(thing_one_bytes, THING_ONE_SEED);
88/// let thing_two_cksum = const_crc32::crc32_seed(thing_two_bytes, THING_TWO_SEED);
89///
90/// assert_ne!(thing_one_cksum, thing_two_cksum);
91/// ```
92#[inline]
93pub const fn crc32_seed(buf: &[u8], seed: u32) -> u32 {
94    let mut out = !seed;
95    let mut i = 0usize;
96    while i < buf.len() {
97        out = (out >> 8) ^ TABLE[((out & 0xff) ^ (buf[i] as u32)) as usize];
98        i += 1;
99    }
100    !out
101}
102
103#[cfg(test)]
104mod tests {
105    use super::*;
106    use rand::prelude::*;
107
108    fn crc32_compute_table() -> [u32; 256] {
109        let mut crc32_table = [0; 256];
110
111        for n in 0..256_u32 {
112            crc32_table[n as usize] = (0..8).fold(n, |acc, _| match acc & 1 {
113                1 => 0xedb88320 ^ (acc >> 1),
114                _ => acc >> 1,
115            });
116        }
117
118        crc32_table
119    }
120
121    #[test]
122    fn check_table_fn_against_example_code() {
123        let table = crc32_compute_table();
124        for i in 0..256 {
125            assert_eq!(table[i], table_fn(i as u32));
126        }
127    }
128
129    #[test]
130    fn simple_test() {
131        const BYTES: &[u8] = "The quick brown fox jumps over the lazy dog".as_bytes();
132        assert_eq!(crc32(BYTES), 0x414fa339_u32);
133        assert_eq!(crc32(BYTES), crc32fast::hash(BYTES));
134    }
135
136    #[test]
137    fn use_seed_to_checksum_from_partial_inputs() {
138        const BYTES: &[u8] = "The quick brown fox jumps over the lazy dog".as_bytes();
139        let mut cksum = crc32(&BYTES[0..10]);
140        cksum = crc32_seed(&BYTES[10..], cksum);
141        assert_eq!(cksum, crc32(BYTES));
142    }
143
144    #[test]
145    fn use_seed_to_checksum_from_many_chunks() {
146        let mut buf = [0u8; 1024];
147        let mut rng = thread_rng();
148        rng.fill(&mut buf[..]);
149
150        let mut cksum = 0;
151        for chunk in buf[..].chunks(7) {
152            cksum = crc32_seed(chunk, cksum);
153        }
154
155        assert_eq!(cksum, crc32(&buf[..]));
156    }
157
158    #[test]
159    fn check_random_inputs_against_crc32_fast() {
160        const N_ITER: usize = 100;
161        const BUFSIZE: usize = 4096;
162
163        let mut buf = [0u8; BUFSIZE];
164        let mut rng = thread_rng();
165
166        for _ in 0..N_ITER {
167            rng.fill(&mut buf[..]);
168            assert_eq!(crc32(&buf[..]), crc32fast::hash(&buf[..]));
169        }
170    }
171
172    #[test]
173    fn check_const_eval_limit_not_reached_on_100k_data() {
174        const BYTES: &[u8] = &[42u8; 1024 * 100];
175        const CKSUM: u32 = crc32(BYTES);
176        assert_eq!(CKSUM, crc32fast::hash(&BYTES[..]));
177    }
178
179    // #[test]
180    // fn check_const_eval_limit_not_reached_on_1mb_data() {
181    //     const BYTES: &[u8] = &[42u8; 1024 * 1024];
182    //     const CKSUM: u32 = crc32(BYTES);
183    //     assert_eq!(CKSUM, crc32fast::hash(&BYTES[..]));
184    // }
185}
const_crc32_nostd/lib.rs

const_crc32_nostd/
lib.rs
