crc_0x8810/lib.rs
1#![no_std]
2#![forbid(unsafe_code)]
3
4//! compute crcs using the ccitt polynomial efficiently without tables
5//!
6//! P(x) = x**16 + x**12 + x**5 + 1
7//!
8//! MSB polynomial: 0x8810
9//! MSB polynomial (with explicit 1): 0x1021
10//!
11//! https://users.ece.cmu.edu/~koopman/crc/c16/0x8810.txt
12//!
13//! The method used is described in a few places:
14//!
15//! - [Greg Cook provides some commented 6502 asm](http://6502.org/source/integers/crc-more.html)
16//! - [Jon Buller describes how to determine it through automated symbolic calculation and provides some 8051 asm](https://groups.google.com/g/comp.arch.embedded/c/fvQ7yM5F6ys/m/3xcgqF3Kqc4J?pli=1)
17//! - [adapted by others into C](https://www.ccsinfo.com/forum/viewtopic.php?t=24977)
18//! - the same method is used in [avr-libc](https://www.nongnu.org/avr-libc/user-manual/group__util__crc.html)'s `_crc_ccitt_update` function.
19//!
20
21/// The lowest level operation, applies a single byte of data to a given crc and returns the new
22/// crc
23///
24/// NOTE: internally, this is performing a least significant bit (LSB) first crc. This means that
25/// performing an MSB first operation requires reversing the bits of each input byte and revsersing
26/// the final CRC output. It _may_ be possible to determine a direct method to calculate the crc
27/// without needing a reverse bits operation (which can be expensive on some platforms)
28pub const fn update(crc: u16, data: u8) -> u16 {
29 let data = data ^ (crc as u8);
30 let data = data ^ (data << 4);
31 (((data as u16) << 8) | (crc >> 8)) ^ ((data >> 4) as u16) ^ ((data as u16) << 3)
32}
33
34#[derive(Debug, Copy, Clone)]
35pub struct Algorithm {
36 pub init: u16,
37 pub refin: bool,
38 pub refout: bool,
39 pub xorout: u16,
40 pub check: u16,
41 pub residue: u16,
42}
43
44impl Algorithm {
45 pub const fn checksum(&self, bytes: &[u8]) -> u16 {
46 let mut crc = self.init();
47 crc = self.update(crc, bytes);
48 self.finalize(crc)
49 }
50
51 const fn init(&self) -> u16 {
52 if self.refin {
53 self.init.reverse_bits()
54 } else {
55 self.init
56 }
57 }
58
59 const fn update(&self, mut crc: u16, bytes: &[u8]) -> u16 {
60 let mut i = 0;
61 if self.refin {
62 while i < bytes.len() {
63 crc = update(crc, bytes[i]);
64 i += 1;
65 }
66 } else {
67 while i < bytes.len() {
68 crc = update(crc, bytes[i].reverse_bits());
69 i += 1;
70 }
71 }
72 crc
73 }
74
75 const fn finalize(&self, mut crc: u16) -> u16 {
76 if !self.refout {
77 crc = crc.reverse_bits();
78 }
79 crc ^ self.xorout
80 }
81
82 pub const fn digest(&self) -> Digest {
83 Digest::new(self)
84 }
85}
86
87/// A `crc` crate like `Digest` api
88#[derive(Debug, Copy, Clone)]
89pub struct Digest<'a> {
90 algorithm: &'a Algorithm,
91 value: u16,
92}
93
94impl<'a> Digest<'a> {
95 const fn new(algorithm: &'a Algorithm) -> Self {
96 let value = algorithm.init();
97 Digest { algorithm, value }
98 }
99
100 pub fn update(&mut self, bytes: &[u8]) {
101 self.value = self.algorithm.update(self.value, bytes);
102 }
103
104 pub const fn finalize(self) -> u16 {
105 self.algorithm.finalize(self.value)
106 }
107}
108
109/// CRC-16/XMODEM
110///
111/// width=16 poly=0x1021 init=0x0000 refin=false refout=false xorout=0x0000 check=0x31c3 residue=0x0000 name="CRC-16/XMODEM"
112pub const CRC_16_XMODEM: Algorithm = Algorithm {
113 init: 0,
114 refin: false,
115 refout: false,
116 xorout: 0,
117 check: 0x31c3,
118 residue: 0,
119};
120
121/// CRC-16/GENIBUS
122///
123/// width=16 poly=0x1021 init=0xffff refin=false refout=false xorout=0xffff check=0xd64e residue=0x1d0f name="CRC-16/GENIBUS"
124pub const CRC_16_GENIBUS: Algorithm = Algorithm {
125 init: 0xffff,
126 refin: false,
127 refout: false,
128 xorout: 0xffff,
129 check: 0xd64e,
130 residue: 0x1d0f,
131};
132
133/// CRC-16/GSM
134///
135/// width=16 poly=0x1021 init=0x0000 refin=false refout=false xorout=0xffff check=0xce3c residue=0x1d0f name="CRC-16/GSM"
136pub const CRC_16_GSM: Algorithm = Algorithm {
137 init: 0,
138 refin: false,
139 refout: false,
140 xorout: 0xffff,
141 check: 0xce3c,
142 residue: 0x1d0f,
143};
144
145/// CRC-16/IBM-3740
146///
147/// width=16 poly=0x1021 init=0xffff refin=false refout=false xorout=0x0000 check=0x29b1 residue=0x0000 name="CRC-16/IBM-3740"
148pub const CRC_16_IBM_3740: Algorithm = Algorithm {
149 init: 0xffff,
150 refin: false,
151 refout: false,
152 xorout: 0,
153 check: 0x29b1,
154 residue: 0x000,
155};
156
157/// Alias of [`CRC_16_IBM_3740`]
158pub const CRC_16_AUTOSAR: Algorithm = CRC_16_IBM_3740;
159
160/// CRC-16/IBM-SDLC
161///
162/// width=16 poly=0x1021 init=0xffff refin=true refout=true xorout=0xffff check=0x906e residue=0xf0b8 name="CRC-16/IBM-SDLC"
163pub const CRC_16_IBM_SDLC: Algorithm = Algorithm {
164 init: 0xffff,
165 refin: true,
166 refout: true,
167 xorout: 0xffff,
168 check: 0x906e,
169 residue: 0xf0b8,
170};
171
172/// Alias of [`CRC_16_IBM_SDLC`]
173pub const CRC_16_ISO_HDLC: Algorithm = CRC_16_IBM_SDLC;
174/// Alias of [`CRC_16_IBM_SDLC`]
175pub const CRC_16_ISO_IEC_14443_3_B: Algorithm = CRC_16_IBM_SDLC;
176/// Alias of [`CRC_16_IBM_SDLC`]
177pub const CRC_16_X_25: Algorithm = CRC_16_IBM_SDLC;
178
179/// CRC-16/ISO-IEC-14443-3-A
180///
181/// width=16 poly=0x1021 init=0xc6c6 refin=true refout=true xorout=0x0000 check=0xbf05 residue=0x0000 name="CRC-16/ISO-IEC-14443-3-A"
182pub const CRC_16_ISO_IEC_14443_3_A: Algorithm = Algorithm {
183 init: 0xc6c6,
184 refin: true,
185 refout: true,
186 xorout: 0,
187 check: 0xbf05,
188 residue: 0,
189};
190
191/// CRC-16/KERMIT
192///
193/// width=16 poly=0x1021 init=0x0000 refin=true refout=true xorout=0x0000 check=0x2189 residue=0x0000 name="CRC-16/KERMIT"
194pub const CRC_16_KERMIT: Algorithm = Algorithm {
195 init: 0,
196 refin: true,
197 refout: true,
198 xorout: 0,
199 check: 0x2189,
200 residue: 0,
201};
202
203/// Alias of [`CRC_16_KERMIT`]
204pub const CRC_16_CCITT: Algorithm = CRC_16_KERMIT;
205
206/// Alias of [`CRC_16_XMODEM`]
207pub const CRC_16_LORA: Algorithm = CRC_16_XMODEM;