tessera/crc.rs
1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2026 Cédric Mesnil <cslashm@pm.me>
3
4//! CRC-16 / CRC-32 cyclic redundancy checks (error-detection codes).
5//!
6//! # ⚠ Not cryptographic
7//!
8//! A CRC is a **linear error-detection code**, not a hash or a MAC. It is
9//! trivially forgeable (an attacker can adjust the message to hit any target
10//! CRC) and offers **no** integrity guarantee against tampering. Use it only
11//! for detecting *accidental* corruption of **public** data (protocol framing,
12//! file/format checksums). For integrity or authentication use a keyed MAC
13//! ([`crate::hmac`](mod@crate::hmac), [`crate::sp800_185`] KMAC) or a
14//! cryptographic hash.
15//!
16//! To make misuse a compile error, the CRC types here deliberately do **not**
17//! implement the [`Digest`](crate::Digest) / [`Xof`](crate::Xof) traits, so a
18//! CRC cannot be fed to `hmac`, `mgf1`, cSHAKE-keyed, or any generic
19//! `Digest`-bounded construction.
20//!
21//! # Not constant-time
22//!
23//! The table-driven implementation indexes a lookup table with data bytes, so
24//! it is **variable-time** by data. This is fine for the public data a CRC is
25//! meant for; never compute a CRC over secret material.
26//!
27//! # Model
28//!
29//! Parameters follow the Rocksoft^tm model (Williams, "A Painless Guide to CRC
30//! Error Detection Algorithms", 1993) as tabulated in the RevEng CRC catalogue:
31//! `(poly, init, refin, refout, xorout)`. Each named algorithm additionally
32//! records `check` — the CRC of the ASCII string `b"123456789"` — which the
33//! test suite asserts, so a mistyped parameter is caught immediately.
34//!
35//! ```
36//! use tessera::crc::{Crc32, CRC32_ISO_HDLC};
37//! assert_eq!(Crc32::checksum(&CRC32_ISO_HDLC, b"123456789"), 0xCBF4_3926);
38//! ```
39
40/// Generate the `reflect`, table, `Algorithm` and engine for one CRC width.
41///
42/// `$width` is 16 or 32; `$int` the matching unsigned type. The reflected /
43/// normal table recurrences and the `refin`/`refout` handling follow the
44/// RevEng reference model.
45macro_rules! crc_family {
46 ($algo:ident, $engine:ident, $int:ty, $width:expr, $reflect:ident, $table:ident, $doc_algo:literal, $doc_eng:literal) => {
47 /// Reflect the low `$width` bits of `v` (bit `i` ↔ bit `$width-1-i`).
48 const fn $reflect(mut v: $int) -> $int {
49 let mut r: $int = 0;
50 let mut i = 0;
51 while i < $width {
52 r = (r << 1) | (v & 1);
53 v >>= 1;
54 i += 1;
55 }
56 r
57 }
58
59 /// Build the 256-entry byte-wise CRC table for `poly`, in reflected
60 /// (LSB-first) or normal (MSB-first) form, at compile time.
61 const fn $table(poly: $int, reflected: bool) -> [$int; 256] {
62 let mut table = [0 as $int; 256];
63 let mut i = 0usize;
64 while i < 256 {
65 let mut c: $int;
66 if reflected {
67 let rpoly = $reflect(poly);
68 c = i as $int;
69 let mut k = 0;
70 while k < 8 {
71 c = if c & 1 != 0 { (c >> 1) ^ rpoly } else { c >> 1 };
72 k += 1;
73 }
74 } else {
75 c = (i as $int) << ($width - 8);
76 let msb: $int = 1 << ($width - 1);
77 let mut k = 0;
78 while k < 8 {
79 c = if c & msb != 0 { (c << 1) ^ poly } else { c << 1 };
80 k += 1;
81 }
82 }
83 table[i] = c;
84 i += 1;
85 }
86 table
87 }
88
89 #[doc = $doc_algo]
90 ///
91 /// Build a custom variant with [`new`](Self::new); the named `pub const`
92 /// definitions in this module cover the usual sets. Not cryptographic —
93 /// see the [module docs](self).
94 pub struct $algo {
95 /// Generator polynomial (Rocksoft normal form, MSB-first).
96 pub poly: $int,
97 /// Initial register value.
98 pub init: $int,
99 /// Reflect input bytes (LSB-first) if `true`.
100 pub refin: bool,
101 /// Reflect the final register if `true`.
102 pub refout: bool,
103 /// Value XORed into the final register.
104 pub xorout: $int,
105 /// CRC of `b"123456789"` — the self-check value (RevEng `check`).
106 pub check: $int,
107 /// Precomputed byte-wise table (const-generated from `poly`/`refin`).
108 table: [$int; 256],
109 }
110
111 impl $algo {
112 /// Define a CRC variant from its Rocksoft parameters. `const`, so the
113 /// 256-entry table is generated at compile time.
114 ///
115 /// - `poly` / `init` / `refin` / `refout` / `xorout`: model params.
116 /// - `check`: the expected CRC of `b"123456789"` (asserted in tests).
117 pub const fn new(poly: $int, init: $int, refin: bool, refout: bool, xorout: $int, check: $int) -> Self {
118 Self {
119 poly,
120 init,
121 refin,
122 refout,
123 xorout,
124 check,
125 table: $table(poly, refin),
126 }
127 }
128 }
129
130 #[doc = $doc_eng]
131 ///
132 /// `new` → `update`* → `finalize` (or the one-shot [`checksum`](Self::checksum)).
133 /// Not cryptographic — see the [module docs](self).
134 pub struct $engine<'a> {
135 alg: &'a $algo,
136 value: $int,
137 }
138
139 impl<'a> $engine<'a> {
140 /// Start a running CRC under `alg`.
141 pub fn new(alg: &'a $algo) -> Self {
142 let value = if alg.refin { $reflect(alg.init) } else { alg.init };
143 Self { alg, value }
144 }
145
146 /// Feed a chunk of input. May be called repeatedly.
147 pub fn update(&mut self, data: &[u8]) {
148 if self.alg.refin {
149 for &b in data {
150 let idx = ((self.value ^ b as $int) & 0xff) as usize;
151 self.value = (self.value >> 8) ^ self.alg.table[idx];
152 }
153 } else {
154 for &b in data {
155 let idx = (((self.value >> ($width - 8)) ^ b as $int) & 0xff) as usize;
156 self.value = (self.value << 8) ^ self.alg.table[idx];
157 }
158 }
159 }
160
161 /// Consume the state and return the final CRC value.
162 pub fn finalize(self) -> $int {
163 // The reflected engine keeps the register reflected; reflect
164 // again only when refin and refout disagree.
165 let v = if self.alg.refin != self.alg.refout {
166 $reflect(self.value)
167 } else {
168 self.value
169 };
170 v ^ self.alg.xorout
171 }
172
173 /// One-shot convenience: `new(alg)` then `update(data)` then `finalize`.
174 pub fn checksum(alg: &$algo, data: &[u8]) -> $int {
175 let mut c = $engine::new(alg);
176 c.update(data);
177 c.finalize()
178 }
179 }
180 };
181}
182
183crc_family!(
184 Crc16Algorithm,
185 Crc16,
186 u16,
187 16,
188 reflect16,
189 crc16_table,
190 "A CRC-16 variant (16-bit generator, Rocksoft parameters).",
191 "A running CRC-16 checksum over a chosen [`Crc16Algorithm`]."
192);
193crc_family!(
194 Crc32Algorithm,
195 Crc32,
196 u32,
197 32,
198 reflect32,
199 crc32_table,
200 "A CRC-32 variant (32-bit generator, Rocksoft parameters).",
201 "A running CRC-32 checksum over a chosen [`Crc32Algorithm`]."
202);
203
204// ---------------------------------------------------------------------------
205// Usual parameter sets (RevEng CRC catalogue). `check` = CRC of b"123456789".
206// ---------------------------------------------------------------------------
207
208/// CRC-32/ISO-HDLC — the ubiquitous "CRC-32" (zlib, gzip, PNG, Ethernet, POSIX).
209pub const CRC32_ISO_HDLC: Crc32Algorithm =
210 Crc32Algorithm::new(0x04C1_1DB7, 0xFFFF_FFFF, true, true, 0xFFFF_FFFF, 0xCBF4_3926);
211/// CRC-32/ISCSI — Castagnoli, "CRC-32C" (iSCSI, SCTP, ext4, Btrfs, hardware CRC).
212pub const CRC32_ISCSI: Crc32Algorithm =
213 Crc32Algorithm::new(0x1EDC_6F41, 0xFFFF_FFFF, true, true, 0xFFFF_FFFF, 0xE306_9283);
214/// CRC-32/BZIP2 — big-endian variant of the ISO-HDLC polynomial (bzip2).
215pub const CRC32_BZIP2: Crc32Algorithm =
216 Crc32Algorithm::new(0x04C1_1DB7, 0xFFFF_FFFF, false, false, 0xFFFF_FFFF, 0xFC89_1918);
217/// CRC-32/MPEG-2 — ISO-HDLC polynomial, no final XOR (MPEG-2 systems).
218pub const CRC32_MPEG_2: Crc32Algorithm =
219 Crc32Algorithm::new(0x04C1_1DB7, 0xFFFF_FFFF, false, false, 0x0000_0000, 0x0376_E6E7);
220/// CRC-32/CKSUM — the POSIX `cksum` polynomial (without the trailing length).
221pub const CRC32_CKSUM: Crc32Algorithm =
222 Crc32Algorithm::new(0x04C1_1DB7, 0x0000_0000, false, false, 0xFFFF_FFFF, 0x765E_7680);
223
224/// CRC-16/ARC — the classic "CRC-16" / "CRC-IBM" (LHA, many legacy protocols).
225pub const CRC16_ARC: Crc16Algorithm = Crc16Algorithm::new(0x8005, 0x0000, true, true, 0x0000, 0xBB3D);
226/// CRC-16/MODBUS — Modbus RTU serial framing.
227pub const CRC16_MODBUS: Crc16Algorithm = Crc16Algorithm::new(0x8005, 0xFFFF, true, true, 0x0000, 0x4B37);
228/// CRC-16/USB — USB data/token packet checks (MODBUS with final XOR).
229pub const CRC16_USB: Crc16Algorithm = Crc16Algorithm::new(0x8005, 0xFFFF, true, true, 0xFFFF, 0xB4C8);
230/// CRC-16/CCITT-FALSE — the "CCITT" often meant in practice (a.k.a. IBM-3740).
231pub const CRC16_CCITT_FALSE: Crc16Algorithm = Crc16Algorithm::new(0x1021, 0xFFFF, false, false, 0x0000, 0x29B1);
232/// CRC-16/XMODEM — XMODEM / ZMODEM file transfer.
233pub const CRC16_XMODEM: Crc16Algorithm = Crc16Algorithm::new(0x1021, 0x0000, false, false, 0x0000, 0x31C3);
234/// CRC-16/KERMIT — the true CCITT reflected variant (Kermit protocol).
235pub const CRC16_KERMIT: Crc16Algorithm = Crc16Algorithm::new(0x1021, 0x0000, true, true, 0x0000, 0x2189);
236
237#[cfg(test)]
238mod tests {
239 use super::*;
240
241 /// Every named variant must reproduce its RevEng `check` over "123456789".
242 #[test]
243 fn named_variants_self_check() {
244 macro_rules! check32 {
245 ($($alg:ident),+ $(,)?) => {$(
246 assert_eq!(Crc32::checksum(&$alg, b"123456789"), $alg.check, stringify!($alg));
247 )+};
248 }
249 macro_rules! check16 {
250 ($($alg:ident),+ $(,)?) => {$(
251 assert_eq!(Crc16::checksum(&$alg, b"123456789"), $alg.check, stringify!($alg));
252 )+};
253 }
254 check32!(CRC32_ISO_HDLC, CRC32_ISCSI, CRC32_BZIP2, CRC32_MPEG_2, CRC32_CKSUM);
255 check16!(
256 CRC16_ARC,
257 CRC16_MODBUS,
258 CRC16_USB,
259 CRC16_CCITT_FALSE,
260 CRC16_XMODEM,
261 CRC16_KERMIT
262 );
263 }
264
265 /// Chunked `update` must equal the one-shot checksum (streaming invariance).
266 #[test]
267 fn streaming_matches_one_shot() {
268 let msg = b"123456789";
269 let mut c = Crc32::new(&CRC32_ISO_HDLC);
270 c.update(&msg[..4]);
271 c.update(&msg[4..]);
272 assert_eq!(c.finalize(), Crc32::checksum(&CRC32_ISO_HDLC, msg));
273
274 let mut c = Crc16::new(&CRC16_CCITT_FALSE);
275 for &b in msg {
276 c.update(&[b]);
277 }
278 assert_eq!(c.finalize(), Crc16::checksum(&CRC16_CCITT_FALSE, msg));
279 }
280}