1 /*
2 * Copyright (c) 2018 Workaround GmbH.
3 * Copyright (c) 2017 Intel Corporation.
4 * Copyright (c) 2017 Nordic Semiconductor ASA
5 * Copyright (c) 2015 Runtime Inc
6 * Copyright (c) 2018 Google LLC.
7 * Copyright (c) 2022 Meta
8 *
9 * SPDX-License-Identifier: Apache-2.0
10 */
11 /** @file
12 * @brief CRC computation function
13 */
14
15 #ifndef ZEPHYR_INCLUDE_SYS_CRC_H_
16 #define ZEPHYR_INCLUDE_SYS_CRC_H_
17
18 #include <zephyr/types.h>
19 #include <stdbool.h>
20 #include <stddef.h>
21
22 #include <zephyr/sys/__assert.h>
23
24 #ifdef __cplusplus
25 extern "C" {
26 #endif
27
28 /* Initial value expected to be used at the beginning of the crc8_ccitt
29 * computation.
30 */
31 #define CRC8_CCITT_INITIAL_VALUE 0xFF
32 #define CRC8_ROHC_INITIAL_VALUE 0xFF
33
34 /* Initial value expected to be used at the beginning of the OpenPGP CRC-24 computation. */
35 #define CRC24_PGP_INITIAL_VALUE 0x00B704CEU
36 /*
37 * The CRC-24 value is stored on a 32-bit value, only the 3 least significant bytes
38 * are meaningful. Use the following mask to only keep the CRC-24 value.
39 */
40 #define CRC24_FINAL_VALUE_MASK 0x00FFFFFFU
41
42 /**
43 * @defgroup checksum Checksum
44 * @ingroup os_services
45 */
46
47 /**
48 * @defgroup crc CRC
49 * @ingroup checksum
50 * @{
51 */
52
53 /**
54 * @brief CRC algorithm enumeration
55 *
56 * These values should be used with the @ref crc dispatch function.
57 */
58 enum crc_type {
59 CRC4, /**< Use @ref crc4 */
60 CRC4_TI, /**< Use @ref crc4_ti */
61 CRC7_BE, /**< Use @ref crc7_be */
62 CRC8, /**< Use @ref crc8 */
63 CRC8_CCITT, /**< Use @ref crc8_ccitt */
64 CRC8_ROHC, /**< Use @ref crc8_rohc */
65 CRC16, /**< Use @ref crc16 */
66 CRC16_ANSI, /**< Use @ref crc16_ansi */
67 CRC16_CCITT, /**< Use @ref crc16_ccitt */
68 CRC16_ITU_T, /**< Use @ref crc16_itu_t */
69 CRC24_PGP, /**< Use @ref crc24_pgp */
70 CRC32_C, /**< Use @ref crc32_c */
71 CRC32_IEEE, /**< Use @ref crc32_ieee */
72 };
73
74 /**
75 * @brief Generic function for computing a CRC-16 without input or output
76 * reflection.
77 *
78 * Compute CRC-16 by passing in the address of the input, the input length
79 * and polynomial used in addition to the initial value. This is O(n*8) where n
80 * is the length of the buffer provided. No reflection is performed.
81 *
82 * @note If you are planning to use a CRC based on poly 0x1012 the functions
83 * crc16_itu_t() is faster and thus recommended over this one.
84 *
85 * @param poly The polynomial to use omitting the leading x^16
86 * coefficient
87 * @param seed Initial value for the CRC computation
88 * @param src Input bytes for the computation
89 * @param len Length of the input in bytes
90 *
91 * @return The computed CRC16 value (without any XOR applied to it)
92 */
93 uint16_t crc16(uint16_t poly, uint16_t seed, const uint8_t *src, size_t len);
94
95 /**
96 * @brief Generic function for computing a CRC-16 with input and output
97 * reflection.
98 *
99 * Compute CRC-16 by passing in the address of the input, the input length
100 * and polynomial used in addition to the initial value. This is O(n*8) where n
101 * is the length of the buffer provided. Both input and output are reflected.
102 *
103 * @note If you are planning to use a CRC based on poly 0x1012 the function
104 * crc16_ccitt() is faster and thus recommended over this one.
105 *
106 * The following checksums can, among others, be calculated by this function,
107 * depending on the value provided for the initial seed and the value the final
108 * calculated CRC is XORed with:
109 *
110 * - CRC-16/ANSI, CRC-16/MODBUS, CRC-16/USB, CRC-16/IBM
111 * https://reveng.sourceforge.io/crc-catalogue/16.htm#crc.cat.crc-16-modbus
112 * poly: 0x8005 (0xA001) initial seed: 0xffff, xor output: 0x0000
113 *
114 * @param poly The polynomial to use omitting the leading x^16
115 * coefficient. Important: please reflect the poly. For example,
116 * use 0xA001 instead of 0x8005 for CRC-16-MODBUS.
117 * @param seed Initial value for the CRC computation
118 * @param src Input bytes for the computation
119 * @param len Length of the input in bytes
120 *
121 * @return The computed CRC16 value (without any XOR applied to it)
122 */
123 uint16_t crc16_reflect(uint16_t poly, uint16_t seed, const uint8_t *src, size_t len);
124 /**
125 * @brief Generic function for computing CRC 8
126 *
127 * Compute CRC 8 by passing in the address of the input, the input length
128 * and polynomial used in addition to the initial value.
129 *
130 * @param src Input bytes for the computation
131 * @param len Length of the input in bytes
132 * @param polynomial The polynomial to use omitting the leading x^8
133 * coefficient
134 * @param initial_value Initial value for the CRC computation
135 * @param reversed Should we use reflected/reversed values or not
136 *
137 * @return The computed CRC8 value
138 */
139 uint8_t crc8(const uint8_t *src, size_t len, uint8_t polynomial, uint8_t initial_value,
140 bool reversed);
141
142 /**
143 * @brief Compute the checksum of a buffer with polynomial 0x1021, reflecting
144 * input and output.
145 *
146 * This function is able to calculate any CRC that uses 0x1021 as it polynomial
147 * and requires reflecting both the input and the output. It is a fast variant
148 * that runs in O(n) time, where n is the length of the input buffer.
149 *
150 * The following checksums can, among others, be calculated by this function,
151 * depending on the value provided for the initial seed and the value the final
152 * calculated CRC is XORed with:
153 *
154 * - CRC-16/CCITT, CRC-16/CCITT-TRUE, CRC-16/KERMIT
155 * https://reveng.sourceforge.io/crc-catalogue/16.htm#crc.cat.crc-16-kermit
156 * initial seed: 0x0000, xor output: 0x0000
157 *
158 * - CRC-16/X-25, CRC-16/IBM-SDLC, CRC-16/ISO-HDLC
159 * https://reveng.sourceforge.io/crc-catalogue/16.htm#crc.cat.crc-16-ibm-sdlc
160 * initial seed: 0xffff, xor output: 0xffff
161 *
162 * @note To calculate the CRC across non-contiguous blocks use the return
163 * value from block N-1 as the seed for block N.
164 *
165 * See ITU-T Recommendation V.41 (November 1988).
166 *
167 * @param seed Value to seed the CRC with
168 * @param src Input bytes for the computation
169 * @param len Length of the input in bytes
170 *
171 * @return The computed CRC16 value (without any XOR applied to it)
172 */
173 uint16_t crc16_ccitt(uint16_t seed, const uint8_t *src, size_t len);
174
175 /**
176 * @brief Compute the checksum of a buffer with polynomial 0x1021, no
177 * reflection of input or output.
178 *
179 * This function is able to calculate any CRC that uses 0x1021 as it polynomial
180 * and requires no reflection on both the input and the output. It is a fast
181 * variant that runs in O(n) time, where n is the length of the input buffer.
182 *
183 * The following checksums can, among others, be calculated by this function,
184 * depending on the value provided for the initial seed and the value the final
185 * calculated CRC is XORed with:
186 *
187 * - CRC-16/XMODEM, CRC-16/ACORN, CRC-16/LTE
188 * https://reveng.sourceforge.io/crc-catalogue/16.htm#crc.cat.crc-16-xmodem
189 * initial seed: 0x0000, xor output: 0x0000
190 *
191 * - CRC16/CCITT-FALSE, CRC-16/IBM-3740, CRC-16/AUTOSAR
192 * https://reveng.sourceforge.io/crc-catalogue/16.htm#crc.cat.crc-16-ibm-3740
193 * initial seed: 0xffff, xor output: 0x0000
194 *
195 * - CRC-16/GSM
196 * https://reveng.sourceforge.io/crc-catalogue/16.htm#crc.cat.crc-16-gsm
197 * initial seed: 0x0000, xor output: 0xffff
198 *
199 * @note To calculate the CRC across non-contiguous blocks use the return
200 * value from block N-1 as the seed for block N.
201 *
202 * See ITU-T Recommendation V.41 (November 1988) (MSB first).
203 *
204 * @param seed Value to seed the CRC with
205 * @param src Input bytes for the computation
206 * @param len Length of the input in bytes
207 *
208 * @return The computed CRC16 value (without any XOR applied to it)
209 */
210 uint16_t crc16_itu_t(uint16_t seed, const uint8_t *src, size_t len);
211
212 /**
213 * @brief Compute the ANSI (or Modbus) variant of CRC-16
214 *
215 * The ANSI variant of CRC-16 uses 0x8005 (0xA001 reflected) as its polynomial
216 * with the initial * value set to 0xffff.
217 *
218 * @param src Input bytes for the computation
219 * @param len Length of the input in bytes
220 *
221 * @return The computed CRC16 value
222 */
crc16_ansi(const uint8_t * src,size_t len)223 static inline uint16_t crc16_ansi(const uint8_t *src, size_t len)
224 {
225 return crc16_reflect(0xA001, 0xffff, src, len);
226 }
227
228 /**
229 * @brief Generate IEEE conform CRC32 checksum.
230 *
231 * @param data Pointer to data on which the CRC should be calculated.
232 * @param len Data length.
233 *
234 * @return CRC32 value.
235 *
236 */
237 uint32_t crc32_ieee(const uint8_t *data, size_t len);
238
239 /**
240 * @brief Update an IEEE conforming CRC32 checksum.
241 *
242 * @param crc CRC32 checksum that needs to be updated.
243 * @param data Pointer to data on which the CRC should be calculated.
244 * @param len Data length.
245 *
246 * @return CRC32 value.
247 *
248 */
249 uint32_t crc32_ieee_update(uint32_t crc, const uint8_t *data, size_t len);
250
251 /**
252 * @brief Calculate CRC32C (Castagnoli) checksum.
253 *
254 * @param crc CRC32C checksum that needs to be updated.
255 * @param data Pointer to data on which the CRC should be calculated.
256 * @param len Data length.
257 * @param first_pkt Whether this is the first packet in the stream.
258 * @param last_pkt Whether this is the last packet in the stream.
259 *
260 * @return CRC32 value.
261 *
262 */
263 uint32_t crc32_c(uint32_t crc, const uint8_t *data,
264 size_t len, bool first_pkt, bool last_pkt);
265
266 /**
267 * @brief Compute CCITT variant of CRC 8
268 *
269 * Normal CCITT variant of CRC 8 is using 0x07.
270 *
271 * @param initial_value Initial value for the CRC computation
272 * @param buf Input bytes for the computation
273 * @param len Length of the input in bytes
274 *
275 * @return The computed CRC8 value
276 */
277 uint8_t crc8_ccitt(uint8_t initial_value, const void *buf, size_t len);
278
279 /**
280 * @brief Compute ROHC variant of CRC 8
281 *
282 * ROHC (Robust Header Compression) variant of CRC 8.
283 * Uses 0x07 as the polynomial with reflection.
284 *
285 * @param initial_value Initial value for the CRC computation
286 * @param buf Input bytes for the computation
287 * @param len Length of the input in bytes
288 *
289 * @return The computed CRC8 value
290 */
291 uint8_t crc8_rohc(uint8_t initial_value, const void *buf, size_t len);
292
293 /**
294 * @brief Compute the CRC-7 checksum of a buffer.
295 *
296 * See JESD84-A441. Used by the MMC protocol. Uses 0x09 as the
297 * polynomial with no reflection. The CRC is left
298 * justified, so bit 7 of the result is bit 6 of the CRC.
299 *
300 * @param seed Value to seed the CRC with
301 * @param src Input bytes for the computation
302 * @param len Length of the input in bytes
303 *
304 * @return The computed CRC7 value
305 */
306 uint8_t crc7_be(uint8_t seed, const uint8_t *src, size_t len);
307
308 /**
309 * @brief Compute the CRC-4 checksum of a buffer.
310 *
311 * Used by the TMAG5170 sensor. Uses 0x03 as the
312 * polynomial with no reflection. 4 most significant
313 * bits of the CRC result will be set to zero.
314 *
315 * @param seed Value to seed the CRC with
316 * @param src Input bytes for the computation
317 * @param len Length of the input in bytes
318 *
319 * @return The computed CRC4 value
320 */
321 uint8_t crc4_ti(uint8_t seed, const uint8_t *src, size_t len);
322
323 /**
324 * @brief Generic function for computing CRC 4
325 *
326 * Compute CRC 4 by passing in the address of the input, the input length
327 * and polynomial used in addition to the initial value. The input buffer
328 * must be aligned to a whole byte. It is guaranteed that 4 most significant
329 * bits of the result will be set to zero.
330 *
331 * @param src Input bytes for the computation
332 * @param len Length of the input in bytes
333 * @param polynomial The polynomial to use omitting the leading x^4
334 * coefficient
335 * @param initial_value Initial value for the CRC computation
336 * @param reversed Should we use reflected/reversed values or not
337 *
338 * @return The computed CRC4 value
339 */
340 uint8_t crc4(const uint8_t *src, size_t len, uint8_t polynomial, uint8_t initial_value,
341 bool reversed);
342
343 /**
344 * @brief Generate an OpenPGP CRC-24 checksum as defined in RFC 4880 section 6.1.
345 *
346 * @param data A pointer to the data on which the CRC will be calculated.
347 * @param len Data length in bytes.
348 *
349 * @return The CRC-24 value.
350 */
351 uint32_t crc24_pgp(const uint8_t *data, size_t len);
352
353 /**
354 * @brief Update an OpenPGP CRC-24 checksum.
355 *
356 * @param crc The CRC-24 checksum that needs to be updated. The full 32-bit value of the CRC needs
357 * to be used between calls, do not mask the value to keep only the last 24 bits.
358 * @param data A pointer to the data on which the CRC will be calculated.
359 * @param len Data length in bytes.
360 *
361 * @return The CRC-24 value. When the last buffer of data has been processed, mask the value
362 * with CRC24_FINAL_VALUE_MASK to keep only the meaningful 24 bits of the CRC result.
363 */
364 uint32_t crc24_pgp_update(uint32_t crc, const uint8_t *data, size_t len);
365
366 /**
367 * @brief Compute a CRC checksum, in a generic way.
368 *
369 * This is a dispatch function that calls the individual CRC routine
370 * determined by @p type.
371 *
372 * For 7, 8, 16 and 24-bit CRCs, the relevant @p seed and @p poly values should
373 * be passed in via the least-significant byte(s).
374 *
375 * Similarly, for 7, 8, 16 and 24-bit CRCs, the relevant result is stored in the
376 * least-significant byte(s) of the returned value.
377 *
378 * @param type CRC algorithm to use.
379 * @param src Input bytes for the computation
380 * @param len Length of the input in bytes
381 * @param seed Value to seed the CRC with
382 * @param poly The polynomial to use omitting the leading coefficient
383 * @param reflect Should we use reflected/reversed values or not
384 * @param first Whether this is the first packet in the stream.
385 * @param last Whether this is the last packet in the stream.
386 * @return uint32_t the computed CRC value
387 */
crc_by_type(enum crc_type type,const uint8_t * src,size_t len,uint32_t seed,uint32_t poly,bool reflect,bool first,bool last)388 static inline uint32_t crc_by_type(enum crc_type type, const uint8_t *src, size_t len,
389 uint32_t seed, uint32_t poly, bool reflect, bool first,
390 bool last)
391 {
392 switch (type) {
393 case CRC4:
394 return crc4(src, len, poly, seed, reflect);
395 case CRC4_TI:
396 return crc4_ti(seed, src, len);
397 case CRC7_BE:
398 return crc7_be(seed, src, len);
399 case CRC8:
400 return crc8(src, len, poly, seed, reflect);
401 case CRC8_CCITT:
402 return crc8_ccitt(seed, src, len);
403 case CRC8_ROHC:
404 return crc8_rohc(seed, src, len);
405 case CRC16:
406 if (reflect) {
407 return crc16_reflect(poly, seed, src, len);
408 } else {
409 return crc16(poly, seed, src, len);
410 }
411 case CRC16_ANSI:
412 return crc16_ansi(src, len);
413 case CRC16_CCITT:
414 return crc16_ccitt(seed, src, len);
415 case CRC16_ITU_T:
416 return crc16_itu_t(seed, src, len);
417 case CRC24_PGP: {
418 uint32_t crc = crc24_pgp_update(seed, src, len);
419
420 if (last)
421 crc &= CRC24_FINAL_VALUE_MASK;
422 return crc;
423 }
424 case CRC32_C:
425 return crc32_c(seed, src, len, first, last);
426 case CRC32_IEEE:
427 return crc32_ieee_update(seed, src, len);
428 default:
429 break;
430 }
431
432 __ASSERT_NO_MSG(false);
433 return -1;
434 }
435
436 /**
437 * @}
438 */
439
440 #ifdef __cplusplus
441 }
442 #endif
443
444 #endif
445
