lib: crc: add CRC-32K/4.2
This adds the best HD=4 CRC32 polynomial. The discovery
is the result of research by Philip Koopman of Carnegie
Mellon University, and is well documented at
https://users.ece.cmu.edu/~koopman/crc/.
The user is given the option of trading 1024B of RAM to
improve the execution speed. The unit tests are parameterized
with this KConfig option.
Signed-off-by: JP Hutchins <jp@intercreate.io>
diff --git a/include/zephyr/sys/crc.h b/include/zephyr/sys/crc.h
index 7a0c33c..647d729 100644
--- a/include/zephyr/sys/crc.h
+++ b/include/zephyr/sys/crc.h
@@ -5,6 +5,7 @@
* Copyright (c) 2015 Runtime Inc
* Copyright (c) 2018 Google LLC.
* Copyright (c) 2022 Meta
+ * Copyright (c) 2024 Intercreate, Inc.
*
* SPDX-License-Identifier: Apache-2.0
*/
@@ -69,6 +70,7 @@
CRC24_PGP, /**< Use @ref crc24_pgp */
CRC32_C, /**< Use @ref crc32_c */
CRC32_IEEE, /**< Use @ref crc32_ieee */
+ CRC32_K_4_2, /**< Use @ref crc32_k_4_2_update */
};
/**
@@ -264,6 +266,32 @@
size_t len, bool first_pkt, bool last_pkt);
/**
+ * @brief Update a CRC-32K/4.2 (*op) (Koopman) checksum. This is a good HD=4
+ * checksum up to 2,147,483,615 bits and HD=5/6 up to 6,167 bits.
+ *
+ * Hamming Distance and properties:
+ *
+ * - Polynomial: 0x93a409eb
+ * - reflect-in: false
+ * - initial value (xor-in): provided by caller as crc argument (0xFFFFFFFF is OK)
+ * - reflect-out: false
+ * - xor-out: 0
+ * - HD=4 @ 2,147,483,615 bits
+ * - HD=5 @ 6,167 bits
+ * - HD=6 @ 6,167 bits
+ * - HD=7 @ 148 bits
+ *
+ * Reference: https://users.ece.cmu.edu/~koopman/crc/crc32.html
+ *
+ * @param crc CRC32 checksum that needs to be updated.
+ * @param data Pointer to data on which the CRC should be calculated.
+ * @param len Data length.
+ *
+ * @return CRC32 value.
+ */
+uint32_t crc32_k_4_2_update(uint32_t crc, const uint8_t *data, size_t len);
+
+/**
* @brief Compute CCITT variant of CRC 8
*
* Normal CCITT variant of CRC 8 is using 0x07.
@@ -378,7 +406,7 @@
* @param type CRC algorithm to use.
* @param src Input bytes for the computation
* @param len Length of the input in bytes
- * @param seed Value to seed the CRC with
+ * @param seed Seed or existing CRC value to update
* @param poly The polynomial to use omitting the leading coefficient
* @param reflect Should we use reflected/reversed values or not
* @param first Whether this is the first packet in the stream.
@@ -425,6 +453,8 @@
return crc32_c(seed, src, len, first, last);
case CRC32_IEEE:
return crc32_ieee_update(seed, src, len);
+ case CRC32_K_4_2:
+ return crc32_k_4_2_update(seed, src, len);
default:
break;
}
diff --git a/lib/crc/CMakeLists.txt b/lib/crc/CMakeLists.txt
index 7285af4..6a6b35e 100644
--- a/lib/crc/CMakeLists.txt
+++ b/lib/crc/CMakeLists.txt
@@ -1,6 +1,7 @@
# SPDX-License-Identifier: Apache-2.0
zephyr_sources_ifdef(CONFIG_CRC
+ crc32k_4_2_sw.c
crc32c_sw.c
crc32_sw.c
crc24_sw.c
diff --git a/lib/crc/Kconfig b/lib/crc/Kconfig
index 0402df5..eb2ced6 100644
--- a/lib/crc/Kconfig
+++ b/lib/crc/Kconfig
@@ -1,4 +1,5 @@
# Copyright (c) 2016,2023 Intel Corporation
+# Copyright (c) 2024 Intercreate, Inc.
# SPDX-License-Identifier: Apache-2.0
#
config CRC
@@ -13,4 +14,10 @@
select POSIX_C_LIB_EXT
help
Enable CRC checking for memory regions from the shell.
+
+config CRC32_K_4_2_TABLE_256
+ bool "Use 256-length table for CRC32-K/4.2"
+ help
+ Enable the 256-length instead of 16-length table for CRC32-K/4.2.
+
endif # CRC
diff --git a/lib/crc/crc32k_4_2_sw.c b/lib/crc/crc32k_4_2_sw.c
new file mode 100644
index 0000000..9208d78
--- /dev/null
+++ b/lib/crc/crc32k_4_2_sw.c
@@ -0,0 +1,84 @@
+/*
+ * Copyright (c) 2024 Intercreate, Inc.
+ *
+ * SPDX-License-Identifier: Apache-2.0
+ */
+
+#include <zephyr/sys/crc.h>
+
+uint32_t crc32_k_4_2_update(uint32_t crc, const uint8_t *const data, const size_t len)
+{
+
+#if defined(CONFIG_CRC32_K_4_2_TABLE_256)
+
+ /**
+ * CRC table generated from polynomial 0x93a409eb CRC-32K/4.2 (*op) (Koopman)
+ *
+ * pycrc --width 32 --poly 0x93a409eb --reflect-in False --xor-in 0 --reflect-out False
+ * --xor-out 0 --generate table --table-idx-width 8
+ */
+ static const uint32_t table[256] = {
+ 0x00000000, 0x93a409eb, 0xb4ec1a3d, 0x274813d6, 0xfa7c3d91, 0x69d8347a, 0x4e9027ac,
+ 0xdd342e47, 0x675c72c9, 0xf4f87b22, 0xd3b068f4, 0x4014611f, 0x9d204f58, 0x0e8446b3,
+ 0x29cc5565, 0xba685c8e, 0xceb8e592, 0x5d1cec79, 0x7a54ffaf, 0xe9f0f644, 0x34c4d803,
+ 0xa760d1e8, 0x8028c23e, 0x138ccbd5, 0xa9e4975b, 0x3a409eb0, 0x1d088d66, 0x8eac848d,
+ 0x5398aaca, 0xc03ca321, 0xe774b0f7, 0x74d0b91c, 0x0ed5c2cf, 0x9d71cb24, 0xba39d8f2,
+ 0x299dd119, 0xf4a9ff5e, 0x670df6b5, 0x4045e563, 0xd3e1ec88, 0x6989b006, 0xfa2db9ed,
+ 0xdd65aa3b, 0x4ec1a3d0, 0x93f58d97, 0x0051847c, 0x271997aa, 0xb4bd9e41, 0xc06d275d,
+ 0x53c92eb6, 0x74813d60, 0xe725348b, 0x3a111acc, 0xa9b51327, 0x8efd00f1, 0x1d59091a,
+ 0xa7315594, 0x34955c7f, 0x13dd4fa9, 0x80794642, 0x5d4d6805, 0xcee961ee, 0xe9a17238,
+ 0x7a057bd3, 0x1dab859e, 0x8e0f8c75, 0xa9479fa3, 0x3ae39648, 0xe7d7b80f, 0x7473b1e4,
+ 0x533ba232, 0xc09fabd9, 0x7af7f757, 0xe953febc, 0xce1bed6a, 0x5dbfe481, 0x808bcac6,
+ 0x132fc32d, 0x3467d0fb, 0xa7c3d910, 0xd313600c, 0x40b769e7, 0x67ff7a31, 0xf45b73da,
+ 0x296f5d9d, 0xbacb5476, 0x9d8347a0, 0x0e274e4b, 0xb44f12c5, 0x27eb1b2e, 0x00a308f8,
+ 0x93070113, 0x4e332f54, 0xdd9726bf, 0xfadf3569, 0x697b3c82, 0x137e4751, 0x80da4eba,
+ 0xa7925d6c, 0x34365487, 0xe9027ac0, 0x7aa6732b, 0x5dee60fd, 0xce4a6916, 0x74223598,
+ 0xe7863c73, 0xc0ce2fa5, 0x536a264e, 0x8e5e0809, 0x1dfa01e2, 0x3ab21234, 0xa9161bdf,
+ 0xddc6a2c3, 0x4e62ab28, 0x692ab8fe, 0xfa8eb115, 0x27ba9f52, 0xb41e96b9, 0x9356856f,
+ 0x00f28c84, 0xba9ad00a, 0x293ed9e1, 0x0e76ca37, 0x9dd2c3dc, 0x40e6ed9b, 0xd342e470,
+ 0xf40af7a6, 0x67aefe4d, 0x3b570b3c, 0xa8f302d7, 0x8fbb1101, 0x1c1f18ea, 0xc12b36ad,
+ 0x528f3f46, 0x75c72c90, 0xe663257b, 0x5c0b79f5, 0xcfaf701e, 0xe8e763c8, 0x7b436a23,
+ 0xa6774464, 0x35d34d8f, 0x129b5e59, 0x813f57b2, 0xf5efeeae, 0x664be745, 0x4103f493,
+ 0xd2a7fd78, 0x0f93d33f, 0x9c37dad4, 0xbb7fc902, 0x28dbc0e9, 0x92b39c67, 0x0117958c,
+ 0x265f865a, 0xb5fb8fb1, 0x68cfa1f6, 0xfb6ba81d, 0xdc23bbcb, 0x4f87b220, 0x3582c9f3,
+ 0xa626c018, 0x816ed3ce, 0x12cada25, 0xcffef462, 0x5c5afd89, 0x7b12ee5f, 0xe8b6e7b4,
+ 0x52debb3a, 0xc17ab2d1, 0xe632a107, 0x7596a8ec, 0xa8a286ab, 0x3b068f40, 0x1c4e9c96,
+ 0x8fea957d, 0xfb3a2c61, 0x689e258a, 0x4fd6365c, 0xdc723fb7, 0x014611f0, 0x92e2181b,
+ 0xb5aa0bcd, 0x260e0226, 0x9c665ea8, 0x0fc25743, 0x288a4495, 0xbb2e4d7e, 0x661a6339,
+ 0xf5be6ad2, 0xd2f67904, 0x415270ef, 0x26fc8ea2, 0xb5588749, 0x9210949f, 0x01b49d74,
+ 0xdc80b333, 0x4f24bad8, 0x686ca90e, 0xfbc8a0e5, 0x41a0fc6b, 0xd204f580, 0xf54ce656,
+ 0x66e8efbd, 0xbbdcc1fa, 0x2878c811, 0x0f30dbc7, 0x9c94d22c, 0xe8446b30, 0x7be062db,
+ 0x5ca8710d, 0xcf0c78e6, 0x123856a1, 0x819c5f4a, 0xa6d44c9c, 0x35704577, 0x8f1819f9,
+ 0x1cbc1012, 0x3bf403c4, 0xa8500a2f, 0x75642468, 0xe6c02d83, 0xc1883e55, 0x522c37be,
+ 0x28294c6d, 0xbb8d4586, 0x9cc55650, 0x0f615fbb, 0xd25571fc, 0x41f17817, 0x66b96bc1,
+ 0xf51d622a, 0x4f753ea4, 0xdcd1374f, 0xfb992499, 0x683d2d72, 0xb5090335, 0x26ad0ade,
+ 0x01e51908, 0x924110e3, 0xe691a9ff, 0x7535a014, 0x527db3c2, 0xc1d9ba29, 0x1ced946e,
+ 0x8f499d85, 0xa8018e53, 0x3ba587b8, 0x81cddb36, 0x1269d2dd, 0x3521c10b, 0xa685c8e0,
+ 0x7bb1e6a7, 0xe815ef4c, 0xcf5dfc9a, 0x5cf9f571};
+
+ for (size_t i = 0; i < len; i++) {
+ crc = (crc << 8) ^ table[((crc >> 24) ^ data[i]) & 0xff];
+ }
+
+#else
+
+ /**
+ * CRC table generated from polynomial 0x93a409eb CRC-32K/4.2 (*op) (Koopman)
+ *
+ * pycrc --width 32 --poly 0x93a409eb --reflect-in False --xor-in 0 --reflect-out False
+ * --xor-out 0 --generate table --table-idx-width 4
+ */
+ static const uint32_t table[16] = {0x00000000, 0x93a409eb, 0xb4ec1a3d, 0x274813d6,
+ 0xfa7c3d91, 0x69d8347a, 0x4e9027ac, 0xdd342e47,
+ 0x675c72c9, 0xf4f87b22, 0xd3b068f4, 0x4014611f,
+ 0x9d204f58, 0x0e8446b3, 0x29cc5565, 0xba685c8e};
+
+ for (size_t i = 0; i < len; i++) {
+ crc = (crc << 4) ^ table[((crc >> 28) ^ (data[i] >> 4)) & 0x0f];
+ crc = (crc << 4) ^ table[((crc >> 28) ^ data[i]) & 0x0f];
+ }
+
+#endif
+
+ return crc;
+}
diff --git a/lib/crc/crc_shell.c b/lib/crc/crc_shell.c
index 3d08a59..189ec76 100644
--- a/lib/crc/crc_shell.c
+++ b/lib/crc/crc_shell.c
@@ -32,6 +32,7 @@
[CRC24_PGP] = "24_pgp",
[CRC32_C] = "32_c",
[CRC32_IEEE] = "32_ieee",
+ [CRC32_K_4_2] = "32_k_4_2",
};
static int string_to_crc_type(const char *s)
diff --git a/tests/unit/crc/main.c b/tests/unit/crc/main.c
index ed5483d..6c3b834 100644
--- a/tests/unit/crc/main.c
+++ b/tests/unit/crc/main.c
@@ -12,6 +12,28 @@
#include "../../../lib/crc/crc32c_sw.c"
#include "../../../lib/crc/crc7_sw.c"
#include "../../../lib/crc/crc24_sw.c"
+#include "../../../lib/crc/crc32k_4_2_sw.c"
+
+ZTEST(crc, test_crc32_k_4_2)
+{
+ uint8_t test1[] = "A";
+ uint8_t test2[] = "123456789";
+ uint8_t test3[] = "Zephyr";
+
+ const uint32_t TEST2_CRC = 0x3ee83603;
+
+ zassert_equal(crc32_k_4_2_update(0xFFFFFFFF, test1, sizeof(test1) - 1), 0x2d098604);
+ zassert_equal(crc32_k_4_2_update(0xFFFFFFFF, test2, sizeof(test2) - 1), TEST2_CRC);
+ zassert_equal(crc32_k_4_2_update(0xFFFFFFFF, test3, sizeof(test3) - 1), 0xacf334b2);
+
+ /* test iteration */
+ uint32_t crc = 0xFFFFFFFF;
+
+ for (size_t i = 0; i < sizeof(test2) - 1; i++) {
+ crc = crc32_k_4_2_update(crc, &test2[i], 1);
+ }
+ zassert_equal(crc, TEST2_CRC);
+}
ZTEST(crc, test_crc32c)
{
diff --git a/tests/unit/crc/testcase.yaml b/tests/unit/crc/testcase.yaml
index 747bbc6..9e4626f 100644
--- a/tests/unit/crc/testcase.yaml
+++ b/tests/unit/crc/testcase.yaml
@@ -3,3 +3,9 @@
tags:
- crc
type: unit
+ utilities.crc.table256:
+ tags:
+ - crc
+ type: unit
+ extra_configs:
+ - CONFIG_CRC32_K_4_2_TABLE_256=y
