checksum_tapestry/
crc_table.rs

1//! CRC table generation code.
2//! These are different versions of CRC table generation code.
3//! This includes optimized and unoptimized versions.
4//! CRC generation code was based on the crc crate
5use crate::crc::{CRCConfiguration, CRCEndianness};
6
7/// Compute a CRC using a 16-bit polynomial
8///
9/// # Examples
10///
11///
12/// ```
13/// use checksum_tapestry::{
14///     Checksum,
15///     crc::{BitWidth, CRCConfiguration, CRCEndianness},
16///     crc_table::crc16,
17/// };
18///
19/// let configuration = CRCConfiguration::<u16>::new(
20///     "CRC-16/CCITT",
21///     BitWidth::Sixteen,
22///     CRCEndianness::MSB,
23///     0x1021,
24///     true,
25///     None,
26///     None,
27/// );
28///
29/// let crc = crc16(&configuration, 0xBBCE as u16);
30/// assert_eq!(crc, 0x3882);
31/// ```
32///
33pub const fn crc16(configuration: &CRCConfiguration<u16>, mut value: u16) -> u16 {
34    let poly = match configuration.endianness {
35        CRCEndianness::MSB => configuration.poly << (16 - (configuration.width as u8)),
36        CRCEndianness::LSB => {
37            let poly = configuration.poly.reverse_bits();
38            poly >> (16 - (configuration.width as u8))
39        }
40    };
41
42    if let CRCEndianness::LSB = configuration.endianness {
43        let mut i = 0;
44        while i < 8 {
45            value = (value >> 1) ^ ((value & 1) * poly);
46            i += 1;
47        }
48    } else {
49        value <<= 8;
50
51        let mut i = 0;
52        while i < 8 {
53            value = (value << 1) ^ (((value >> 15) & 1) * poly);
54            i += 1;
55        }
56    }
57    value
58}
59
60/// Compute a CRC using a 32-bit polynomial
61///
62/// # Examples
63///
64///
65/// ```
66/// use checksum_tapestry::{
67///     Checksum,
68///     crc::{BitWidth, CRCConfiguration, CRCEndianness},
69///     crc_table::crc32,
70/// };
71///
72/// let configuration = CRCConfiguration::<u32>::new(
73///     "CRC-32/MPEG-2",
74///     BitWidth::ThirtyTwo,
75///     CRCEndianness::MSB,
76///     0x04C11DB7,
77///     false,
78///     Some(0xFFFFFFFF),
79///     None,
80/// );
81///
82/// let crc = crc32(&configuration, 0x00BBCE7B as u32);
83/// assert_eq!(crc, 0xCBFFD686);
84/// ```
85///
86pub const fn crc32(configuration: &CRCConfiguration<u32>, mut value: u32) -> u32 {
87    let poly = match configuration.endianness {
88        CRCEndianness::MSB => configuration.poly << (32 - (configuration.width as u8)),
89        CRCEndianness::LSB => {
90            let poly = configuration.poly.reverse_bits();
91            poly >> (32 - (configuration.width as u8))
92        }
93    };
94
95    if let CRCEndianness::LSB = configuration.endianness {
96        let mut i = 0;
97        while i < 8 {
98            value = (value >> 1) ^ ((value & 1) * poly);
99            i += 1;
100        }
101    } else {
102        value <<= 24;
103
104        let mut i = 0;
105        while i < 8 {
106            value = (value << 1) ^ (((value >> 31) & 1) * poly);
107            i += 1;
108        }
109    }
110    value
111}
112
113/// This builds the CRC based on the endianness, as opposed to the reflect_in
114/// and reflect_out parameters.
115/// It supports most use-cases, but there are some CRCs, like CRC-16/Genibus
116/// that require unmatched reflect_in and reflect_out settings.
117/// The real-world is messy.
118/// These are simpler to understand than optimized table generation
119/// routines that make use of the fact that table[i xor j] == table[i]
120/// xor table[j], so that we only have to update entries corresponding
121/// to powers of two.
122///
123/// This is based on the Sarwate method, outlined in Sarwate, Dilip
124/// V. (August 1998). "Computation of Cyclic Redundancy Checks via
125/// Table Look-Up". Communications of the ACM. 31 (8):
126/// 1008–1013. doi:10.1145/63030.63037. S2CID 5363350.
127///
128/// The tutorial at
129/// https://github.com/komrad36/CRC/blob/master/README.md by komrad36
130/// provides a very good overview of why this works.
131///
132/// # Examples
133///
134/// ```
135/// use checksum_tapestry::{
136///     Checksum,
137///     crc::{BitWidth, CRCConfiguration, CRCEndianness},
138///     crc_table::build_table_16,
139/// };
140///
141/// let configuration = CRCConfiguration::<u16>::new(
142///     "CRC-16/KERMIT",
143///     BitWidth::Sixteen,
144///     CRCEndianness::LSB,
145///     0x1021,
146///     // true,
147///     true,
148///     None,
149///     None,
150/// );
151///
152/// let table = build_table_16(&configuration);
153/// ```
154pub fn build_table_16(configuration: &CRCConfiguration<u16>) -> [u16; 256] {
155    let mut table: [u16; 256] = [0; 256];
156    let mut i = 0;
157
158    while i < table.len() {
159        table[i] = crc16(configuration, i as u16);
160        i += 1;
161    }
162    table
163}
164
165/// This builds the CRC based on the endianness, as opposed to the reflect_in
166/// and reflect_out parameters.
167/// It supports most use-cases, but there are some CRCs, like CRC-16/Genibus
168/// that require unmatched reflect_in and reflect_out settings.
169/// The real-world is messy.
170/// These are simpler to understand than optimized table generation
171/// routines that make use of the fact that table[i xor j] == table[i]
172/// xor table[j], so that we only have to update entries corresponding
173/// to powers of two.
174///
175/// This is based on the Sarwate method, outlined in Sarwate, Dilip
176/// V. (August 1998). "Computation of Cyclic Redundancy Checks via
177/// Table Look-Up". Communications of the ACM. 31 (8):
178/// 1008–1013. doi:10.1145/63030.63037. S2CID 5363350.
179///
180/// The tutorial at
181/// https://github.com/komrad36/CRC/blob/master/README.md by komrad36
182/// provides a very good overview of why this works.
183///
184/// # Examples
185///
186/// ```
187/// use checksum_tapestry::{
188///     Checksum,
189///     crc::{BitWidth, CRCConfiguration, CRCEndianness},
190///     crc_table::build_table_32,
191/// };
192///
193/// let mut configuration = CRCConfiguration::<u32>::new(
194///     "CRC-32/MPEG-2",
195///     BitWidth::ThirtyTwo,
196///     CRCEndianness::MSB,
197///     0x04C11DB7,
198///     false,
199///     Some(0xFFFFFFFF),
200///     None,
201/// );
202///
203/// let table = build_table_32(&configuration);
204/// ```
205pub fn build_table_32(configuration: &CRCConfiguration<u32>) -> [u32; 256] {
206    let mut table: [u32; 256] = [0; 256];
207    let mut i = 0;
208
209    while i < table.len() {
210        table[i] = crc32(configuration, i as u32);
211        i += 1;
212    }
213    table
214}
215
216/// Build a CRC table for MSB 32-bit CRCs
217///
218/// Make use of the fact that table[i xor j] == table[i] xor table[j],
219/// we only have to update entries corresponding to powers of two
220pub fn optimized_build_msb_table_32(configuration: &CRCConfiguration<u32>) -> [u32; 256] {
221    let mut table: [u32; 256] = [0; 256];
222    let mut crc: u32;
223
224    let mut i = 1;
225
226    // i starts at 1 and is shifted left every iteration, so values of i are:
227    // 1, 2, 4, 8, 16, 32, 64, 128
228    while i < 256 {
229        crc = crc32(configuration, i as u32);
230
231        // j iterates from 0 to i - 1, or 0 to 0, non-inclusive
232        // So on the first outer iteration, it iterates from 0 to 0,
233        // It doesn't enter the loop.
234        // On the next iteration it iterates from 0 to 1, non-inclusive,
235        // It enters the loop once.
236        for j in 0..i {
237            table[i ^ j] = crc ^ table[j];
238        }
239        i <<= 1;
240    }
241
242    table
243}
244
245/// Build a CRC table for LSB 32-bit CRCs
246///
247/// Make use of the fact that table[i xor j] == table[i] xor table[j],
248/// we only have to update entries corresponding to powers of two
249pub fn optimized_build_lsb_table_32(configuration: &CRCConfiguration<u32>) -> [u32; 256] {
250    let mut table: [u32; 256] = [0; 256];
251    let mut crc: u32;
252    let mut i: usize = 128;
253
254    while i > 0 {
255        crc = crc32(configuration, i as u32);
256
257        let mut j = 0;
258        while j < 256 {
259            table[i ^ j] = crc ^ table[j];
260            j += 2 * i;
261        }
262        i >>= 1;
263    }
264
265    table
266}
267
268/// Build a CRC table for MSB 16-bit CRCs
269///
270/// Make use of the fact that table[i xor j] == table[i] xor table[j],
271/// we only have to update entries corresponding to powers of two
272pub fn optimized_build_msb_table_16(configuration: &CRCConfiguration<u16>) -> [u16; 256] {
273    let mut table: [u16; 256] = [0; 256];
274    let mut crc;
275
276    let mut i = 1;
277
278    while i < 256 {
279        crc = crc16(configuration, i as u16);
280
281        for j in 0..i {
282            table[i ^ j] = crc ^ table[j];
283        }
284        i <<= 1;
285    }
286
287    table
288}
289
290/// Build a CRC table for LSB 16-bit CRCs
291///
292/// Make use of the fact that table[i xor j] == table[i] xor table[j],
293/// we only have to update entries corresponding to powers of two
294pub fn optimized_build_lsb_table_16(configuration: &CRCConfiguration<u16>) -> [u16; 256] {
295    let mut table: [u16; 256] = [0; 256];
296    let mut crc: u16;
297    let mut i: usize = 128;
298
299    while i > 0 {
300        crc = crc16(configuration, i as u16);
301
302        let mut j = 0;
303        while j < 256 {
304            table[i ^ j] = crc ^ table[j];
305            j += 2 * i;
306        }
307        i >>= 1;
308    }
309
310    table
311}
312
313#[cfg(test)]
314mod tests {
315    use crate::crc::{BitWidth, CRCConfiguration, CRCEndianness};
316
317    use super::{
318        build_table_16, build_table_32, optimized_build_lsb_table_16, optimized_build_lsb_table_32,
319        optimized_build_msb_table_16, optimized_build_msb_table_32,
320    };
321
322    /// This contains a table generated from the CCITT 16-bit polynomial.
323    /// Used to test the table generation code.
324    /// Below is the configuration.
325    /// let configuration = CRCConfiguration::<u16>::new(
326    ///     "CRC-16/CCITT",
327    ///     BitWidth::Sixteen,
328    ///     CRCEndianness::MSB,
329    ///     0x1021,
330    ///     true,
331    ///     None,
332    ///     None,
333    /// );
334    const CCITT_TABLE: [u16; 256] = [
335        0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7, 0x8108, 0x9129, 0xA14A,
336        0xB16B, 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF, 0x1231, 0x0210, 0x3273, 0x2252, 0x52B5, 0x4294,
337        0x72F7, 0x62D6, 0x9339, 0x8318, 0xB37B, 0xA35A, 0xD3BD, 0xC39C, 0xF3FF, 0xE3DE, 0x2462,
338        0x3443, 0x0420, 0x1401, 0x64E6, 0x74C7, 0x44A4, 0x5485, 0xA56A, 0xB54B, 0x8528, 0x9509,
339        0xE5EE, 0xF5CF, 0xC5AC, 0xD58D, 0x3653, 0x2672, 0x1611, 0x0630, 0x76D7, 0x66F6, 0x5695,
340        0x46B4, 0xB75B, 0xA77A, 0x9719, 0x8738, 0xF7DF, 0xE7FE, 0xD79D, 0xC7BC, 0x48C4, 0x58E5,
341        0x6886, 0x78A7, 0x0840, 0x1861, 0x2802, 0x3823, 0xC9CC, 0xD9ED, 0xE98E, 0xF9AF, 0x8948,
342        0x9969, 0xA90A, 0xB92B, 0x5AF5, 0x4AD4, 0x7AB7, 0x6A96, 0x1A71, 0x0A50, 0x3A33, 0x2A12,
343        0xDBFD, 0xCBDC, 0xFBBF, 0xEB9E, 0x9B79, 0x8B58, 0xBB3B, 0xAB1A, 0x6CA6, 0x7C87, 0x4CE4,
344        0x5CC5, 0x2C22, 0x3C03, 0x0C60, 0x1C41, 0xEDAE, 0xFD8F, 0xCDEC, 0xDDCD, 0xAD2A, 0xBD0B,
345        0x8D68, 0x9D49, 0x7E97, 0x6EB6, 0x5ED5, 0x4EF4, 0x3E13, 0x2E32, 0x1E51, 0x0E70, 0xFF9F,
346        0xEFBE, 0xDFDD, 0xCFFC, 0xBF1B, 0xAF3A, 0x9F59, 0x8F78, 0x9188, 0x81A9, 0xB1CA, 0xA1EB,
347        0xD10C, 0xC12D, 0xF14E, 0xE16F, 0x1080, 0x00A1, 0x30C2, 0x20E3, 0x5004, 0x4025, 0x7046,
348        0x6067, 0x83B9, 0x9398, 0xA3FB, 0xB3DA, 0xC33D, 0xD31C, 0xE37F, 0xF35E, 0x02B1, 0x1290,
349        0x22F3, 0x32D2, 0x4235, 0x5214, 0x6277, 0x7256, 0xB5EA, 0xA5CB, 0x95A8, 0x8589, 0xF56E,
350        0xE54F, 0xD52C, 0xC50D, 0x34E2, 0x24C3, 0x14A0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,
351        0xA7DB, 0xB7FA, 0x8799, 0x97B8, 0xE75F, 0xF77E, 0xC71D, 0xD73C, 0x26D3, 0x36F2, 0x0691,
352        0x16B0, 0x6657, 0x7676, 0x4615, 0x5634, 0xD94C, 0xC96D, 0xF90E, 0xE92F, 0x99C8, 0x89E9,
353        0xB98A, 0xA9AB, 0x5844, 0x4865, 0x7806, 0x6827, 0x18C0, 0x08E1, 0x3882, 0x28A3, 0xCB7D,
354        0xDB5C, 0xEB3F, 0xFB1E, 0x8BF9, 0x9BD8, 0xABBB, 0xBB9A, 0x4A75, 0x5A54, 0x6A37, 0x7A16,
355        0x0AF1, 0x1AD0, 0x2AB3, 0x3A92, 0xFD2E, 0xED0F, 0xDD6C, 0xCD4D, 0xBDAA, 0xAD8B, 0x9DE8,
356        0x8DC9, 0x7C26, 0x6C07, 0x5C64, 0x4C45, 0x3CA2, 0x2C83, 0x1CE0, 0x0CC1, 0xEF1F, 0xFF3E,
357        0xCF5D, 0xDF7C, 0xAF9B, 0xBFBA, 0x8FD9, 0x9FF8, 0x6E17, 0x7E36, 0x4E55, 0x5E74, 0x2E93,
358        0x3EB2, 0x0ED1, 0x1EF0,
359    ];
360
361    /// This contains a table generated from the KERMIT 16-bit polynomial.
362    /// Used to test the table generation code.
363    /// Below is the configuration.
364    /// let configuration = CRCConfiguration::<u16>::new(
365    ///     "CRC-16/KERMIT",
366    ///     BitWidth::Sixteen,
367    ///     CRCEndianness::LSB,
368    ///     0x1021,
369    ///     true,
370    ///     true,
371    ///     None,
372    ///     None,
373    /// );
374    const KERMIT_TABLE: [u16; 256] = [
375        0x0000, 0x1189, 0x2312, 0x329B, 0x4624, 0x57AD, 0x6536, 0x74BF, 0x8C48, 0x9DC1, 0xAF5A,
376        0xBED3, 0xCA6C, 0xDBE5, 0xE97E, 0xF8F7, 0x1081, 0x0108, 0x3393, 0x221A, 0x56A5, 0x472C,
377        0x75B7, 0x643E, 0x9CC9, 0x8D40, 0xBFDB, 0xAE52, 0xDAED, 0xCB64, 0xF9FF, 0xE876, 0x2102,
378        0x308B, 0x0210, 0x1399, 0x6726, 0x76AF, 0x4434, 0x55BD, 0xAD4A, 0xBCC3, 0x8E58, 0x9FD1,
379        0xEB6E, 0xFAE7, 0xC87C, 0xD9F5, 0x3183, 0x200A, 0x1291, 0x0318, 0x77A7, 0x662E, 0x54B5,
380        0x453C, 0xBDCB, 0xAC42, 0x9ED9, 0x8F50, 0xFBEF, 0xEA66, 0xD8FD, 0xC974, 0x4204, 0x538D,
381        0x6116, 0x709F, 0x0420, 0x15A9, 0x2732, 0x36BB, 0xCE4C, 0xDFC5, 0xED5E, 0xFCD7, 0x8868,
382        0x99E1, 0xAB7A, 0xBAF3, 0x5285, 0x430C, 0x7197, 0x601E, 0x14A1, 0x0528, 0x37B3, 0x263A,
383        0xDECD, 0xCF44, 0xFDDF, 0xEC56, 0x98E9, 0x8960, 0xBBFB, 0xAA72, 0x6306, 0x728F, 0x4014,
384        0x519D, 0x2522, 0x34AB, 0x0630, 0x17B9, 0xEF4E, 0xFEC7, 0xCC5C, 0xDDD5, 0xA96A, 0xB8E3,
385        0x8A78, 0x9BF1, 0x7387, 0x620E, 0x5095, 0x411C, 0x35A3, 0x242A, 0x16B1, 0x0738, 0xFFCF,
386        0xEE46, 0xDCDD, 0xCD54, 0xB9EB, 0xA862, 0x9AF9, 0x8B70, 0x8408, 0x9581, 0xA71A, 0xB693,
387        0xC22C, 0xD3A5, 0xE13E, 0xF0B7, 0x0840, 0x19C9, 0x2B52, 0x3ADB, 0x4E64, 0x5FED, 0x6D76,
388        0x7CFF, 0x9489, 0x8500, 0xB79B, 0xA612, 0xD2AD, 0xC324, 0xF1BF, 0xE036, 0x18C1, 0x0948,
389        0x3BD3, 0x2A5A, 0x5EE5, 0x4F6C, 0x7DF7, 0x6C7E, 0xA50A, 0xB483, 0x8618, 0x9791, 0xE32E,
390        0xF2A7, 0xC03C, 0xD1B5, 0x2942, 0x38CB, 0x0A50, 0x1BD9, 0x6F66, 0x7EEF, 0x4C74, 0x5DFD,
391        0xB58B, 0xA402, 0x9699, 0x8710, 0xF3AF, 0xE226, 0xD0BD, 0xC134, 0x39C3, 0x284A, 0x1AD1,
392        0x0B58, 0x7FE7, 0x6E6E, 0x5CF5, 0x4D7C, 0xC60C, 0xD785, 0xE51E, 0xF497, 0x8028, 0x91A1,
393        0xA33A, 0xB2B3, 0x4A44, 0x5BCD, 0x6956, 0x78DF, 0x0C60, 0x1DE9, 0x2F72, 0x3EFB, 0xD68D,
394        0xC704, 0xF59F, 0xE416, 0x90A9, 0x8120, 0xB3BB, 0xA232, 0x5AC5, 0x4B4C, 0x79D7, 0x685E,
395        0x1CE1, 0x0D68, 0x3FF3, 0x2E7A, 0xE70E, 0xF687, 0xC41C, 0xD595, 0xA12A, 0xB0A3, 0x8238,
396        0x93B1, 0x6B46, 0x7ACF, 0x4854, 0x59DD, 0x2D62, 0x3CEB, 0x0E70, 0x1FF9, 0xF78F, 0xE606,
397        0xD49D, 0xC514, 0xB1AB, 0xA022, 0x92B9, 0x8330, 0x7BC7, 0x6A4E, 0x58D5, 0x495C, 0x3DE3,
398        0x2C6A, 0x1EF1, 0x0F78,
399    ];
400
401    /// This contains a table generated from the MPEG2 32-bit polynomial
402    /// Used to test the table generation code.
403    /// Below is the configuration:
404    /// let configuration = CRCConfiguration::<u32>::new(
405    ///     "CRC-32/MPEG-2",
406    ///     BitWidth::ThirtyTwo,
407    ///     CRCEndianness::MSB,
408    ///     0x04C11DB7,
409    ///     false,
410    ///     Some(0xFFFFFFFF),
411    ///     None,
412    /// );
413    const MPEG2_TABLE: [u32; 256] = [
414        0x00000000, 0x04C11DB7, 0x09823B6E, 0x0D4326D9, 0x130476DC, 0x17C56B6B, 0x1A864DB2,
415        0x1E475005, 0x2608EDB8, 0x22C9F00F, 0x2F8AD6D6, 0x2B4BCB61, 0x350C9B64, 0x31CD86D3,
416        0x3C8EA00A, 0x384FBDBD, 0x4C11DB70, 0x48D0C6C7, 0x4593E01E, 0x4152FDA9, 0x5F15ADAC,
417        0x5BD4B01B, 0x569796C2, 0x52568B75, 0x6A1936C8, 0x6ED82B7F, 0x639B0DA6, 0x675A1011,
418        0x791D4014, 0x7DDC5DA3, 0x709F7B7A, 0x745E66CD, 0x9823B6E0, 0x9CE2AB57, 0x91A18D8E,
419        0x95609039, 0x8B27C03C, 0x8FE6DD8B, 0x82A5FB52, 0x8664E6E5, 0xBE2B5B58, 0xBAEA46EF,
420        0xB7A96036, 0xB3687D81, 0xAD2F2D84, 0xA9EE3033, 0xA4AD16EA, 0xA06C0B5D, 0xD4326D90,
421        0xD0F37027, 0xDDB056FE, 0xD9714B49, 0xC7361B4C, 0xC3F706FB, 0xCEB42022, 0xCA753D95,
422        0xF23A8028, 0xF6FB9D9F, 0xFBB8BB46, 0xFF79A6F1, 0xE13EF6F4, 0xE5FFEB43, 0xE8BCCD9A,
423        0xEC7DD02D, 0x34867077, 0x30476DC0, 0x3D044B19, 0x39C556AE, 0x278206AB, 0x23431B1C,
424        0x2E003DC5, 0x2AC12072, 0x128E9DCF, 0x164F8078, 0x1B0CA6A1, 0x1FCDBB16, 0x018AEB13,
425        0x054BF6A4, 0x0808D07D, 0x0CC9CDCA, 0x7897AB07, 0x7C56B6B0, 0x71159069, 0x75D48DDE,
426        0x6B93DDDB, 0x6F52C06C, 0x6211E6B5, 0x66D0FB02, 0x5E9F46BF, 0x5A5E5B08, 0x571D7DD1,
427        0x53DC6066, 0x4D9B3063, 0x495A2DD4, 0x44190B0D, 0x40D816BA, 0xACA5C697, 0xA864DB20,
428        0xA527FDF9, 0xA1E6E04E, 0xBFA1B04B, 0xBB60ADFC, 0xB6238B25, 0xB2E29692, 0x8AAD2B2F,
429        0x8E6C3698, 0x832F1041, 0x87EE0DF6, 0x99A95DF3, 0x9D684044, 0x902B669D, 0x94EA7B2A,
430        0xE0B41DE7, 0xE4750050, 0xE9362689, 0xEDF73B3E, 0xF3B06B3B, 0xF771768C, 0xFA325055,
431        0xFEF34DE2, 0xC6BCF05F, 0xC27DEDE8, 0xCF3ECB31, 0xCBFFD686, 0xD5B88683, 0xD1799B34,
432        0xDC3ABDED, 0xD8FBA05A, 0x690CE0EE, 0x6DCDFD59, 0x608EDB80, 0x644FC637, 0x7A089632,
433        0x7EC98B85, 0x738AAD5C, 0x774BB0EB, 0x4F040D56, 0x4BC510E1, 0x46863638, 0x42472B8F,
434        0x5C007B8A, 0x58C1663D, 0x558240E4, 0x51435D53, 0x251D3B9E, 0x21DC2629, 0x2C9F00F0,
435        0x285E1D47, 0x36194D42, 0x32D850F5, 0x3F9B762C, 0x3B5A6B9B, 0x0315D626, 0x07D4CB91,
436        0x0A97ED48, 0x0E56F0FF, 0x1011A0FA, 0x14D0BD4D, 0x19939B94, 0x1D528623, 0xF12F560E,
437        0xF5EE4BB9, 0xF8AD6D60, 0xFC6C70D7, 0xE22B20D2, 0xE6EA3D65, 0xEBA91BBC, 0xEF68060B,
438        0xD727BBB6, 0xD3E6A601, 0xDEA580D8, 0xDA649D6F, 0xC423CD6A, 0xC0E2D0DD, 0xCDA1F604,
439        0xC960EBB3, 0xBD3E8D7E, 0xB9FF90C9, 0xB4BCB610, 0xB07DABA7, 0xAE3AFBA2, 0xAAFBE615,
440        0xA7B8C0CC, 0xA379DD7B, 0x9B3660C6, 0x9FF77D71, 0x92B45BA8, 0x9675461F, 0x8832161A,
441        0x8CF30BAD, 0x81B02D74, 0x857130C3, 0x5D8A9099, 0x594B8D2E, 0x5408ABF7, 0x50C9B640,
442        0x4E8EE645, 0x4A4FFBF2, 0x470CDD2B, 0x43CDC09C, 0x7B827D21, 0x7F436096, 0x7200464F,
443        0x76C15BF8, 0x68860BFD, 0x6C47164A, 0x61043093, 0x65C52D24, 0x119B4BE9, 0x155A565E,
444        0x18197087, 0x1CD86D30, 0x029F3D35, 0x065E2082, 0x0B1D065B, 0x0FDC1BEC, 0x3793A651,
445        0x3352BBE6, 0x3E119D3F, 0x3AD08088, 0x2497D08D, 0x2056CD3A, 0x2D15EBE3, 0x29D4F654,
446        0xC5A92679, 0xC1683BCE, 0xCC2B1D17, 0xC8EA00A0, 0xD6AD50A5, 0xD26C4D12, 0xDF2F6BCB,
447        0xDBEE767C, 0xE3A1CBC1, 0xE760D676, 0xEA23F0AF, 0xEEE2ED18, 0xF0A5BD1D, 0xF464A0AA,
448        0xF9278673, 0xFDE69BC4, 0x89B8FD09, 0x8D79E0BE, 0x803AC667, 0x84FBDBD0, 0x9ABC8BD5,
449        0x9E7D9662, 0x933EB0BB, 0x97FFAD0C, 0xAFB010B1, 0xAB710D06, 0xA6322BDF, 0xA2F33668,
450        0xBCB4666D, 0xB8757BDA, 0xB5365D03, 0xB1F740B4,
451    ];
452
453    /// This contains a table generated from the ISO-HDLC 32-bit polynomial
454    /// Used to test the table generation code.
455    /// Below is the configuration:
456    /// let configuration = CRCConfiguration::<u32>::new(
457    ///     "CRC-32/ISO-HDLC",
458    ///     BitWidth::ThirtyTwo,
459    ///     CRCEndianness::LSB,
460    ///     0x04C11DB7,
461    ///     true,
462    ///     true,
463    ///     Some(0xFFFFFFFF),
464    ///     Some(0xFFFFFFFF),
465    /// );
466    const ISO_HDLC_TABLE: [u32; 256] = [
467        0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535,
468        0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD,
469        0xE7B82D07, 0x90BF1D91, 0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE, 0x1ADAD47D,
470        0x6DDDE4EB, 0xF4D4B551, 0x83D385C7, 0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC,
471        0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4,
472        0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 0x35B5A8FA, 0x42B2986C,
473        0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59, 0x26D930AC,
474        0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F,
475        0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924, 0x2F6F7C87, 0x58684C11, 0xC1611DAB,
476        0xB6662D3D, 0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F,
477        0x9FBFE4A5, 0xE8B8D433, 0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB,
478        0x086D3D2D, 0x91646C97, 0xE6635C01, 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
479        0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA,
480        0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65, 0x4DB26158, 0x3AB551CE,
481        0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A,
482        0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9,
483        0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409,
484        0xCE61E49F, 0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81,
485        0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A, 0xEAD54739,
486        0x9DD277AF, 0x04DB2615, 0x73DC1683, 0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8,
487        0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1, 0xF00F9344, 0x8708A3D2, 0x1E01F268,
488        0x6906C2FE, 0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0,
489        0x10DA7A5A, 0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 0xD6D6A3E8,
490        0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
491        0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF,
492        0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236, 0xCC0C7795, 0xBB0B4703,
493        0x220216B9, 0x5505262F, 0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7,
494        0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D, 0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A,
495        0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713, 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE,
496        0x0CB61B38, 0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242,
497        0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777, 0x88085AE6,
498        0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45,
499        0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661, 0xD06016F7, 0x4969474D,
500        0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5,
501        0x47B2CF7F, 0x30B5FFE9, 0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605,
502        0xCDD70693, 0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
503        0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D,
504    ];
505
506    #[test]
507    fn optimized_build_msb_table_32_works() {
508        let configuration = CRCConfiguration::<u32>::new(
509            "CRC-32/MPEG-2",
510            BitWidth::ThirtyTwo,
511            CRCEndianness::MSB,
512            0x04C11DB7,
513            false,
514            Some(0xFFFFFFFF),
515            None,
516        );
517
518        let table = optimized_build_msb_table_32(&configuration);
519
520        assert_eq!(table.len(), 256);
521        assert_eq!(table, MPEG2_TABLE);
522    }
523
524    #[test]
525    fn optimized_build_lsb_table_32_works() {
526        let configuration = CRCConfiguration::<u32>::new(
527            "CRC-32/ISO-HDLC",
528            BitWidth::ThirtyTwo,
529            CRCEndianness::LSB,
530            0x04C11DB7,
531            true,
532            Some(0xFFFFFFFF),
533            Some(0xFFFFFFFF),
534        );
535
536        let table = optimized_build_lsb_table_32(&configuration);
537
538        assert_eq!(table.len(), 256);
539        assert_eq!(table, ISO_HDLC_TABLE);
540    }
541
542    #[test]
543    fn optimized_build_msb_table_16_works() {
544        let configuration = CRCConfiguration::<u16>::new(
545            "CRC-16/CCITT",
546            BitWidth::Sixteen,
547            CRCEndianness::MSB,
548            0x1021,
549            true,
550            None,
551            None,
552        );
553        let table = optimized_build_msb_table_16(&configuration);
554
555        assert_eq!(table.len(), 256);
556        assert_eq!(table, CCITT_TABLE);
557    }
558
559    #[test]
560    fn optimized_build_lsb_table_16_works() {
561        let configuration = CRCConfiguration::<u16>::new(
562            "CRC-16/KERMIT",
563            BitWidth::Sixteen,
564            CRCEndianness::LSB,
565            0x1021,
566            true,
567            None,
568            None,
569        );
570        let table = optimized_build_lsb_table_16(&configuration);
571
572        assert_eq!(table.len(), 256);
573        assert_eq!(table, KERMIT_TABLE);
574    }
575
576    #[test]
577    fn build_table_msb_16_works() {
578        let configuration = CRCConfiguration::<u16>::new(
579            "CRC-16/CCITT",
580            BitWidth::Sixteen,
581            CRCEndianness::MSB,
582            0x1021,
583            true,
584            None,
585            None,
586        );
587        let table = build_table_16(&configuration);
588
589        assert_eq!(table.len(), 256);
590        assert_eq!(table, CCITT_TABLE);
591    }
592
593    #[test]
594    fn build_table_lsb_16_works() {
595        let configuration = CRCConfiguration::<u16>::new(
596            "CRC-16/KERMIT",
597            BitWidth::Sixteen,
598            CRCEndianness::LSB,
599            0x1021,
600            true,
601            None,
602            None,
603        );
604        let table = build_table_16(&configuration);
605
606        assert_eq!(table.len(), 256);
607        assert_eq!(table, KERMIT_TABLE);
608    }
609
610    #[test]
611    fn build_table_msb_32_works() {
612        let configuration = CRCConfiguration::<u32>::new(
613            "CRC-32/MPEG-2",
614            BitWidth::ThirtyTwo,
615            CRCEndianness::MSB,
616            0x04C11DB7,
617            false,
618            Some(0xFFFFFFFF),
619            None,
620        );
621        let table = build_table_32(&configuration);
622
623        assert_eq!(table.len(), 256);
624        assert_eq!(table, MPEG2_TABLE);
625    }
626
627    #[test]
628    fn build_table_lsb_32_works() {
629        let configuration = CRCConfiguration::<u32>::new(
630            "CRC-32/ISO-HDLC",
631            BitWidth::ThirtyTwo,
632            CRCEndianness::LSB,
633            0x04C11DB7,
634            true,
635            Some(0xFFFFFFFF),
636            Some(0xFFFFFFFF),
637        );
638        let table = build_table_32(&configuration);
639
640        assert_eq!(table.len(), 256);
641        assert_eq!(table, ISO_HDLC_TABLE);
642    }
643
644    // Just to remind ourselves how Rust range iterations work
645    #[test]
646    fn test_rust_range_iter() {
647        let mut count = 0;
648
649        for _j in 0..0 {
650            count += 1;
651        }
652        assert_eq!(count, 0);
653
654        count = 0;
655        for _j in 0..1 {
656            count += 1;
657        }
658        assert_eq!(count, 1);
659
660        count = 0;
661        for _j in 0..=0 {
662            count += 1;
663        }
664        assert_eq!(count, 1);
665
666        count = 0;
667        for _j in 0..=1 {
668            count += 1;
669        }
670        assert_eq!(count, 2);
671    }
672}
checksum_tapestry/crc_table.rs

checksum_tapestry/
crc_table.rs
