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