wire_codec/checksum.rs
1//! Frame checksums.
2//!
3//! The [`Checksum`] trait describes an integrity check that produces a fixed
4//! number of bytes. Three common CRCs are built in, implemented locally with
5//! `const`-generated lookup tables (slice-by-8 for the CRC-32 variants) so
6//! the crate stays dependency-free:
7//!
8//! | Type | Algorithm (catalogue name) | Width | Typical use |
9//! | ---- | -------------------------- | ----- | ----------- |
10//! | [`Crc16CcittFalse`] | CRC-16/IBM-3740 (a.k.a. CRC-16/CCITT-FALSE) | 2 bytes | Serial links, Bluetooth, many embedded protocols |
11//! | [`Crc32`] | CRC-32/ISO-HDLC (IEEE 802.3, zlib, PNG) | 4 bytes | Ethernet, gzip, general purpose |
12//! | [`Crc32c`] | CRC-32/ISCSI (Castagnoli) | 4 bytes | iSCSI, SCTP, ext4, Kafka record batches |
13//!
14//! Pair a checksum with any framer through
15//! [`Checksummed`][`crate::framing::Checksummed`]. Implement [`Checksum`]
16//! yourself to plug in a different algorithm (for example a hardware CRC
17//! unit on a microcontroller).
18//!
19//! A CRC detects accidental corruption. It is not a MAC: anyone can compute
20//! a valid CRC for forged data. Use an authenticated cipher or a keyed MAC
21//! when the peer is adversarial.
22
23/// An integrity check over a byte slice that yields [`Checksum::LEN`] bytes.
24///
25/// # Example
26///
27/// A one-byte XOR checksum (weak, but a short example):
28///
29/// ```
30/// use wire_codec::checksum::Checksum;
31///
32/// struct Xor8;
33///
34/// impl Checksum for Xor8 {
35/// const LEN: usize = 1;
36/// fn compute(&self, data: &[u8]) -> u64 {
37/// u64::from(data.iter().fold(0u8, |acc, b| acc ^ b))
38/// }
39/// }
40///
41/// assert_eq!(Xor8.compute(&[0x0F, 0xF0]), 0xFF);
42/// ```
43pub trait Checksum {
44 /// Number of bytes the checksum occupies on the wire. Must be in `1..=8`.
45 const LEN: usize;
46
47 /// Compute the checksum of `data`.
48 ///
49 /// Only the low `LEN * 8` bits of the result are transmitted.
50 fn compute(&self, data: &[u8]) -> u64;
51}
52
53/// CRC-16/IBM-3740, widely known as CRC-16/CCITT-FALSE.
54///
55/// Polynomial `0x1021`, initial value `0xFFFF`, no reflection, no final XOR.
56/// Check value for `b"123456789"`: `0x29B1`.
57///
58/// # Example
59///
60/// ```
61/// use wire_codec::checksum::{Checksum, Crc16CcittFalse};
62///
63/// assert_eq!(Crc16CcittFalse.compute(b"123456789"), 0x29B1);
64/// ```
65#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Hash)]
66pub struct Crc16CcittFalse;
67
68impl Checksum for Crc16CcittFalse {
69 const LEN: usize = 2;
70
71 #[inline]
72 fn compute(&self, data: &[u8]) -> u64 {
73 u64::from(crc16_ccitt_false(data))
74 }
75}
76
77/// CRC-32/ISO-HDLC, the CRC-32 of IEEE 802.3, zlib, gzip, and PNG.
78///
79/// Reflected polynomial `0xEDB88320`, initial value and final XOR
80/// `0xFFFFFFFF`. Check value for `b"123456789"`: `0xCBF43926`.
81///
82/// # Example
83///
84/// ```
85/// use wire_codec::checksum::{Checksum, Crc32};
86///
87/// assert_eq!(Crc32.compute(b"123456789"), 0xCBF4_3926);
88/// ```
89#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Hash)]
90pub struct Crc32;
91
92impl Checksum for Crc32 {
93 const LEN: usize = 4;
94
95 #[inline]
96 fn compute(&self, data: &[u8]) -> u64 {
97 u64::from(crc32(data))
98 }
99}
100
101/// CRC-32/ISCSI (Castagnoli), used by iSCSI, SCTP, ext4, and Kafka.
102///
103/// Reflected polynomial `0x82F63B78`, initial value and final XOR
104/// `0xFFFFFFFF`. Check value for `b"123456789"`: `0xE3069283`.
105///
106/// # Example
107///
108/// ```
109/// use wire_codec::checksum::{Checksum, Crc32c};
110///
111/// assert_eq!(Crc32c.compute(b"123456789"), 0xE306_9283);
112/// ```
113#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Hash)]
114pub struct Crc32c;
115
116impl Checksum for Crc32c {
117 const LEN: usize = 4;
118
119 #[inline]
120 fn compute(&self, data: &[u8]) -> u64 {
121 u64::from(crc32c(data))
122 }
123}
124
125/// Compute CRC-16/IBM-3740 (CRC-16/CCITT-FALSE) of `data`.
126///
127/// # Example
128///
129/// ```
130/// use wire_codec::checksum;
131/// assert_eq!(checksum::crc16_ccitt_false(b"123456789"), 0x29B1);
132/// assert_eq!(checksum::crc16_ccitt_false(b""), 0xFFFF);
133/// ```
134#[inline]
135#[must_use]
136pub fn crc16_ccitt_false(data: &[u8]) -> u16 {
137 data.iter().fold(0xFFFF_u16, |crc, &byte| {
138 let index = usize::from((crc >> 8) as u8 ^ byte);
139 (crc << 8) ^ CRC16_CCITT_TABLE[index]
140 })
141}
142
143/// Compute CRC-32/ISO-HDLC (IEEE) of `data`.
144///
145/// # Example
146///
147/// ```
148/// use wire_codec::checksum;
149/// assert_eq!(checksum::crc32(b"123456789"), 0xCBF4_3926);
150/// assert_eq!(checksum::crc32(b""), 0);
151/// ```
152#[inline]
153#[must_use]
154pub fn crc32(data: &[u8]) -> u32 {
155 reflected_crc32(&CRC32_TABLE, data)
156}
157
158/// Compute CRC-32/ISCSI (Castagnoli) of `data`.
159///
160/// # Example
161///
162/// ```
163/// use wire_codec::checksum;
164/// assert_eq!(checksum::crc32c(b"123456789"), 0xE306_9283);
165/// ```
166#[inline]
167#[must_use]
168pub fn crc32c(data: &[u8]) -> u32 {
169 reflected_crc32(&CRC32C_TABLE, data)
170}
171
172#[inline]
173fn reflected_crc32(tables: &[[u32; 256]; 8], data: &[u8]) -> u32 {
174 // Slice-by-8: fold eight input bytes per step through eight derived
175 // tables, then finish the tail one byte at a time.
176 let mut crc = !0u32;
177 let mut chunks = data.chunks_exact(8);
178 for chunk in &mut chunks {
179 let mut word = [0u8; 8];
180 word.copy_from_slice(chunk);
181 let lo = u32::from_le_bytes([word[0], word[1], word[2], word[3]]) ^ crc;
182 let hi = u32::from_le_bytes([word[4], word[5], word[6], word[7]]);
183 crc = tables[7][usize::from(lo as u8)]
184 ^ tables[6][usize::from((lo >> 8) as u8)]
185 ^ tables[5][usize::from((lo >> 16) as u8)]
186 ^ tables[4][usize::from((lo >> 24) as u8)]
187 ^ tables[3][usize::from(hi as u8)]
188 ^ tables[2][usize::from((hi >> 8) as u8)]
189 ^ tables[1][usize::from((hi >> 16) as u8)]
190 ^ tables[0][usize::from((hi >> 24) as u8)];
191 }
192 for &byte in chunks.remainder() {
193 crc = (crc >> 8) ^ tables[0][usize::from(crc as u8 ^ byte)];
194 }
195 !crc
196}
197
198static CRC16_CCITT_TABLE: [u16; 256] = crc16_table(0x1021);
199static CRC32_TABLE: [[u32; 256]; 8] = slice_by_8(reflected_crc32_table(0xEDB8_8320));
200static CRC32C_TABLE: [[u32; 256]; 8] = slice_by_8(reflected_crc32_table(0x82F6_3B78));
201
202/// Byte-wise lookup table for an MSB-first (non-reflected) CRC-16.
203const fn crc16_table(poly: u16) -> [u16; 256] {
204 let mut table = [0u16; 256];
205 let mut i = 0;
206 while i < 256 {
207 let mut crc = (i as u16) << 8;
208 let mut bit = 0;
209 while bit < 8 {
210 crc = if crc & 0x8000 != 0 {
211 (crc << 1) ^ poly
212 } else {
213 crc << 1
214 };
215 bit += 1;
216 }
217 table[i] = crc;
218 i += 1;
219 }
220 table
221}
222
223/// Derive the eight slice-by-8 tables from the byte-wise table:
224/// `tables[k][i]` is the CRC contribution of byte `i` followed by `k` zeros.
225const fn slice_by_8(base: [u32; 256]) -> [[u32; 256]; 8] {
226 let mut tables = [[0u32; 256]; 8];
227 tables[0] = base;
228 let mut k = 1;
229 while k < 8 {
230 let mut i = 0;
231 while i < 256 {
232 let prev = tables[k - 1][i];
233 tables[k][i] = (prev >> 8) ^ base[(prev & 0xFF) as usize];
234 i += 1;
235 }
236 k += 1;
237 }
238 tables
239}
240
241/// Byte-wise lookup table for an LSB-first (reflected) CRC-32.
242const fn reflected_crc32_table(poly: u32) -> [u32; 256] {
243 let mut table = [0u32; 256];
244 let mut i = 0;
245 while i < 256 {
246 let mut crc = i as u32;
247 let mut bit = 0;
248 while bit < 8 {
249 crc = if crc & 1 != 0 {
250 (crc >> 1) ^ poly
251 } else {
252 crc >> 1
253 };
254 bit += 1;
255 }
256 table[i] = crc;
257 i += 1;
258 }
259 table
260}
261
262#[cfg(test)]
263mod tests {
264 use super::*;
265
266 /// Bit-at-a-time reference implementations, straight from the catalogue
267 /// parameters, to cross-check the table-driven versions.
268 fn crc16_reference(data: &[u8]) -> u16 {
269 let mut crc = 0xFFFFu16;
270 for &byte in data {
271 crc ^= u16::from(byte) << 8;
272 for _ in 0..8 {
273 crc = if crc & 0x8000 != 0 {
274 (crc << 1) ^ 0x1021
275 } else {
276 crc << 1
277 };
278 }
279 }
280 crc
281 }
282
283 fn crc32_reference(poly: u32, data: &[u8]) -> u32 {
284 let mut crc = !0u32;
285 for &byte in data {
286 crc ^= u32::from(byte);
287 for _ in 0..8 {
288 crc = if crc & 1 != 0 {
289 (crc >> 1) ^ poly
290 } else {
291 crc >> 1
292 };
293 }
294 }
295 !crc
296 }
297
298 #[test]
299 fn catalogue_check_values() {
300 assert_eq!(crc16_ccitt_false(b"123456789"), 0x29B1);
301 assert_eq!(crc32(b"123456789"), 0xCBF4_3926);
302 assert_eq!(crc32c(b"123456789"), 0xE306_9283);
303 }
304
305 #[test]
306 fn tables_agree_with_bitwise_reference() {
307 let data: Vec<u8> = (0..=255u8).chain((0..=255u8).rev()).collect();
308 for len in [0, 1, 2, 7, 64, data.len()] {
309 let slice = &data[..len];
310 assert_eq!(crc16_ccitt_false(slice), crc16_reference(slice));
311 assert_eq!(crc32(slice), crc32_reference(0xEDB8_8320, slice));
312 assert_eq!(crc32c(slice), crc32_reference(0x82F6_3B78, slice));
313 }
314 }
315
316 #[test]
317 fn tables_rebuilt_at_runtime_match_the_statics() {
318 // The table builders are `const fn` and normally run at compile
319 // time; calling them at runtime checks them (and covers them).
320 assert_eq!(crc16_table(0x1021), CRC16_CCITT_TABLE);
321 assert_eq!(slice_by_8(reflected_crc32_table(0xEDB8_8320)), CRC32_TABLE);
322 assert_eq!(slice_by_8(reflected_crc32_table(0x82F6_3B78)), CRC32C_TABLE);
323 assert_eq!(CRC32_TABLE[0][1], 0x7707_3096);
324 }
325
326 #[test]
327 fn trait_impls_report_width() {
328 assert_eq!(Crc16CcittFalse::LEN, 2);
329 assert_eq!(Crc32::LEN, 4);
330 assert_eq!(Crc32c::LEN, 4);
331 assert_eq!(
332 Crc16CcittFalse.compute(b"a"),
333 u64::from(crc16_ccitt_false(b"a"))
334 );
335 assert_eq!(Crc32.compute(b"a"), u64::from(crc32(b"a")));
336 assert_eq!(Crc32c.compute(b"a"), u64::from(crc32c(b"a")));
337 }
338}