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