Hi all,

This patch was developed during a hackathon organized by LKCAMP [1],
with the objective of writing KUnit tests, both to introduce people to
the kernel development process and to learn about different subsystems
(with the positive side effect of improving the kernel test coverage, of
course).

We noticed there were tests for CRC32 in lib/crc32test.c and thought it
would be nice to have something similar for CRC16, since it seems to be
widely used in network drivers (as well as in some ext4 code).

Although this patch turned out quite big, most of the LOCs come from
tables containing randomly-generated test data that we use to validate
the kernel's implementation of CRC-16.

We would really appreciate any feedback/suggestions on how to improve
this. Thanks! :-)

Vinicius Peixoto (1):
  lib/crc16_kunit.c: add KUnit tests for crc16

 lib/Kconfig.debug |   8 +
 lib/Makefile      |   1 +
 lib/crc16_kunit.c | 715 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 724 insertions(+)
 create mode 100644 lib/crc16_kunit.c

-- 
2.43.0

Add Kunit tests for the kernel's implementation of the standard CRC-16
algorithm (<linux/crc16.h>). The test data consists of 100
randomly-generated test cases, validated against a reference
implementation.

This implementation follows roughly the same logic as lib/crc32test.c,
but without the performance measurements.

Signed-off-by: Vinicius Peixoto <vpeixoto@lkcamp.dev>
Co-developed-by: Enzo Bertoloti <ebertoloti@lkcamp.dev>
Signed-off-by: Enzo Bertoloti <ebertoloti@lkcamp.dev>
Co-developed-by: Fabricio Gasperin <fgasperin@lkcamp.dev>
Signed-off-by: Fabricio Gasperin <fgasperin@lkcamp.dev>
---
 lib/Kconfig.debug |   8 +
 lib/Makefile      |   1 +
 lib/crc16_kunit.c | 715 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 724 insertions(+)
 create mode 100644 lib/crc16_kunit.c

diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index bc8faa4509e1..848fe54f1aba 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -2835,6 +2835,14 @@ config USERCOPY_KUNIT_TEST
 	  on the copy_to/from_user infrastructure, making sure basic
 	  user/kernel boundary testing is working.
 
+config CRC16_KUNIT_TEST
+	tristate "KUnit tests for CRC16"
+	depends on KUNIT
+	default KUNIT_ALL_TESTS
+	help
+	  Enable this option to run unit tests for the kernel's CRC16
+	  implementation (<linux/crc16.h>).
+
 config TEST_UDELAY
 	tristate "udelay test driver"
 	help
diff --git a/lib/Makefile b/lib/Makefile
index 773adf88af41..1faed6414a85 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -389,6 +389,7 @@ CFLAGS_fortify_kunit.o += $(DISABLE_STRUCTLEAK_PLUGIN)
 obj-$(CONFIG_FORTIFY_KUNIT_TEST) += fortify_kunit.o
 obj-$(CONFIG_SIPHASH_KUNIT_TEST) += siphash_kunit.o
 obj-$(CONFIG_USERCOPY_KUNIT_TEST) += usercopy_kunit.o
+obj-$(CONFIG_CRC16_KUNIT_TEST) += crc16_kunit.o
 
 obj-$(CONFIG_GENERIC_LIB_DEVMEM_IS_ALLOWED) += devmem_is_allowed.o
 
diff --git a/lib/crc16_kunit.c b/lib/crc16_kunit.c
new file mode 100644
index 000000000000..24a682533500
--- /dev/null
+++ b/lib/crc16_kunit.c
@@ -0,0 +1,715 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * KUnits tests for CRC16.
+ *
+ * Copyright (C) 2024, LKCAMP
+ * Author: Vinicius Peixoto <vpeixoto@lkcamp.dev>
+ * Author: Fabricio Gasperin <fgasperin@lkcamp.dev>
+ * Author: Enzo Bertoloti <ebertoloti@lkcamp.dev>
+ */
+#include <kunit/test.h>
+#include <linux/crc16.h>
+
+/**
+ * struct crc16_test - CRC16 test data
+ * @crc: initial input value to CRC16
+ * @start: Start index within the data buffer
+ * @length: Length of the data
+ * @crc16: Expected CRC16 value for the test
+ */
+static struct crc16_test {
+	u16 crc;
+	u16 start;
+	u16 length;
+	u16 crc16;
+} tests[100] = {
+	{0xe5e5, 0x07c0, 0x0456, 0xc191},
+	{0x2995, 0x00d1, 0x06bd, 0xdcea},
+	{0x4e00, 0x0362, 0x029c, 0x6330},
+	{0x3232, 0x01b9, 0x0674, 0x0fe0},
+	{0x3c04, 0x03f4, 0x059c, 0xd1f1},
+	{0x6b44, 0x00d4, 0x0308, 0x546d},
+	{0xa968, 0x0625, 0x055c, 0x87b0},
+	{0x4e59, 0x01ee, 0x04bc, 0x31e2},
+	{0xb298, 0x0646, 0x062e, 0x728c},
+	{0x1f8a, 0x02aa, 0x0372, 0x0338},
+	{0x563a, 0x03a4, 0x0379, 0x5572},
+	{0x627a, 0x07c1, 0x07ae, 0x5bc1},
+	{0xeffc, 0x0725, 0x03f5, 0x1002},
+	{0x0cf6, 0x03e8, 0x0560, 0xe277},
+	{0x0c69, 0x0671, 0x055f, 0xfcdc},
+	{0x730e, 0x0407, 0x0132, 0xd014},
+	{0x21de, 0x0752, 0x00ce, 0xba9e},
+	{0x81d1, 0x07b3, 0x0456, 0x7edb},
+	{0xabc9, 0x01df, 0x0016, 0xb1ce},
+	{0xbb30, 0x0513, 0x05f5, 0x870c},
+	{0x39ca, 0x03d2, 0x07ad, 0x2704},
+	{0x8cc4, 0x0469, 0x044a, 0x05fa},
+	{0x4625, 0x002c, 0x005e, 0x47d7},
+	{0xcd4f, 0x0190, 0x0692, 0x2a1b},
+	{0xa04c, 0x001c, 0x01d3, 0xe004},
+	{0x723d, 0x072b, 0x0467, 0x0821},
+	{0x41ef, 0x0058, 0x02e2, 0xed47},
+	{0x2eeb, 0x067d, 0x06e7, 0x708a},
+	{0xd72e, 0x01d6, 0x063a, 0xbac6},
+	{0xb81f, 0x014b, 0x0378, 0xf0e4},
+	{0xcf55, 0x031c, 0x068d, 0x1353},
+	{0xaec2, 0x04fd, 0x00b8, 0xe2ca},
+	{0x41d9, 0x0130, 0x0107, 0xbffa},
+	{0x65a3, 0x00a0, 0x0266, 0xc265},
+	{0x163a, 0x069d, 0x075a, 0xa28a},
+	{0xedb6, 0x0334, 0x0570, 0xb0a4},
+	{0xb2f7, 0x02f0, 0x0096, 0x61ff},
+	{0xdbaa, 0x01f4, 0x053e, 0xa7c6},
+	{0xbf2b, 0x07dd, 0x02a8, 0xf8b9},
+	{0x75f4, 0x02b3, 0x0610, 0xee85},
+	{0x1184, 0x044a, 0x01ea, 0xd155},
+	{0x74c7, 0x04ee, 0x00af, 0x4df0},
+	{0x38b1, 0x06d8, 0x070a, 0xfb7e},
+	{0xd09a, 0x01f7, 0x0765, 0x6135},
+	{0xe3e6, 0x04a3, 0x0761, 0xd6d5},
+	{0x1fe3, 0x0190, 0x07d6, 0xbf52},
+	{0xfac9, 0x010f, 0x06ea, 0xafe3},
+	{0x3753, 0x02a1, 0x0798, 0x79af},
+	{0xee8f, 0x0212, 0x02b0, 0xab0a},
+	{0x8484, 0x07cf, 0x068c, 0x97d7},
+	{0x48a0, 0x02b5, 0x0144, 0xe533},
+	{0xe0b1, 0x079b, 0x03d1, 0x8011},
+	{0x403d, 0x01f0, 0x01f6, 0x4339},
+	{0x64f9, 0x06e2, 0x001c, 0x82b1},
+	{0x6fd3, 0x0202, 0x0115, 0x0f4a},
+	{0x7c19, 0x04ca, 0x02ea, 0x4eb7},
+	{0xbd2c, 0x039a, 0x059e, 0x483c},
+	{0x978d, 0x07ff, 0x0710, 0x9886},
+	{0xd427, 0x04c8, 0x024c, 0x37e2},
+	{0x006b, 0x0020, 0x011a, 0x6648},
+	{0x8a6b, 0x0775, 0x06dd, 0x2ca8},
+	{0x183e, 0x002a, 0x04e6, 0x0d00},
+	{0xb94c, 0x0534, 0x0230, 0x7831},
+	{0x91a8, 0x002a, 0x01a5, 0xdba6},
+	{0xe737, 0x0177, 0x06bd, 0xe8b5},
+	{0xb3d2, 0x0233, 0x0551, 0x4e19},
+	{0x80f1, 0x028a, 0x03ab, 0x2298},
+	{0x03ec, 0x0498, 0x0750, 0xb94a},
+	{0xab82, 0x04c9, 0x0422, 0x3a8d},
+	{0x1bee, 0x005c, 0x006b, 0xf268},
+	{0x38d9, 0x0547, 0x06c0, 0xb9d8},
+	{0x776b, 0x0635, 0x0622, 0xc7d7},
+	{0xbc0f, 0x0574, 0x0208, 0xa11d},
+	{0xf35d, 0x019b, 0x006e, 0xf1fd},
+	{0x6b5d, 0x0110, 0x0272, 0x10cb},
+	{0xbf05, 0x030c, 0x0351, 0x1062},
+	{0x08e0, 0x0514, 0x0498, 0x70cb},
+	{0xbb53, 0x009b, 0x0424, 0x9263},
+	{0x7e24, 0x07fb, 0x0239, 0x5910},
+	{0x26ae, 0x03b4, 0x0173, 0xdb50},
+	{0x4f7b, 0x0026, 0x0447, 0x0a5d},
+	{0x185a, 0x06e4, 0x07dc, 0xed96},
+	{0x566a, 0x02a7, 0x00fc, 0xbd1d},
+	{0xa0d7, 0x06c3, 0x02bb, 0x858d},
+	{0x81c1, 0x0263, 0x07ed, 0xffb2},
+	{0x86cb, 0x0126, 0x066e, 0x2f65},
+	{0x9ebd, 0x00ca, 0x0386, 0x87cd},
+	{0xbb68, 0x0740, 0x0439, 0xa32e},
+	{0x6b60, 0x04cf, 0x00de, 0x05ef},
+	{0x0f3c, 0x0178, 0x0076, 0xc68c},
+	{0x43c8, 0x05d3, 0x0048, 0xa639},
+	{0xeb54, 0x012b, 0x06b7, 0x2084},
+	{0x1f49, 0x01ed, 0x0517, 0xd24c},
+	{0x952c, 0x057f, 0x0548, 0xbb78},
+	{0x7991, 0x0187, 0x0164, 0x2f17},
+	{0xa787, 0x054c, 0x0155, 0xca00},
+	{0xea26, 0x03d7, 0x06e3, 0x9b3d},
+	{0x33ab, 0x00c9, 0x0208, 0x9ff7},
+	{0xabde, 0x06e4, 0x064f, 0x3705},
+	{0x4550, 0x023e, 0x06ff, 0x6f26},
+};
+
+/* 4096 bytes of random data */
+u8 data[] = {
+	0x4c, 0x82, 0x06, 0x1d, 0x58, 0xe6, 0x2a, 0x6f,
+	0xc8, 0x25, 0x89, 0x80, 0x58, 0x83, 0x78, 0x3d,
+	0x53, 0x00, 0x94, 0x1d, 0xe8, 0x2c, 0x76, 0xa6,
+	0xb1, 0xd7, 0xc5, 0xe8, 0x3c, 0xea, 0x2f, 0x5c,
+	0xdf, 0xd7, 0x93, 0x25, 0x31, 0x8a, 0xb7, 0x39,
+	0xe5, 0x06, 0x85, 0x44, 0x1f, 0x6d, 0x04, 0x06,
+	0x8a, 0x35, 0x8b, 0x59, 0x15, 0xcb, 0x10, 0xe5,
+	0xf8, 0xf6, 0xc5, 0x9e, 0x1e, 0x5a, 0x8b, 0xee,
+	0x10, 0x20, 0x7b, 0xc4, 0x16, 0xbf, 0x16, 0x9a,
+	0x9e, 0x37, 0xc9, 0x56, 0x3c, 0x12, 0x46, 0x31,
+	0x02, 0x0a, 0xc8, 0xd5, 0x5d, 0xb7, 0xf2, 0x8f,
+	0x17, 0x1f, 0xea, 0xba, 0x1c, 0x7f, 0xa0, 0xcd,
+	0x43, 0x52, 0x45, 0xde, 0x5b, 0x73, 0x88, 0x5f,
+	0x58, 0x71, 0x44, 0xeb, 0x7e, 0xa0, 0x5a, 0xac,
+	0xe0, 0xea, 0x28, 0x11, 0x5a, 0x84, 0x42, 0x8d,
+	0x58, 0x8c, 0x26, 0xdd, 0x08, 0xee, 0xa6, 0x4e,
+	0xde, 0x16, 0xa2, 0xee, 0x37, 0x36, 0x43, 0x37,
+	0xc7, 0xd8, 0xf7, 0x6d, 0x4c, 0x49, 0xcc, 0x59,
+	0x3e, 0x42, 0x97, 0x34, 0x93, 0xbe, 0xd3, 0xf4,
+	0x2e, 0xcb, 0x0f, 0xf6, 0xdd, 0x9a, 0xaa, 0x9e,
+	0xeb, 0x6e, 0x8e, 0x88, 0x1e, 0xba, 0x79, 0xd6,
+	0xfc, 0x64, 0xce, 0x1f, 0x64, 0xee, 0x2c, 0x54,
+	0xde, 0x0b, 0x60, 0xa4, 0x91, 0xa2, 0xca, 0xe8,
+	0xa2, 0x1a, 0x74, 0x23, 0xeb, 0x7f, 0xfd, 0xad,
+	0xd7, 0x70, 0x4e, 0x21, 0xb1, 0x92, 0xdd, 0x40,
+	0x8b, 0x3b, 0x8f, 0x0b, 0xca, 0x5f, 0x26, 0x22,
+	0x3d, 0x55, 0x29, 0x12, 0x47, 0x81, 0x10, 0x79,
+	0x44, 0xf3, 0xbf, 0xb3, 0x6d, 0x69, 0x43, 0x17,
+	0x68, 0x6b, 0x96, 0xde, 0xdd, 0x88, 0xf0, 0x5c,
+	0xc1, 0xfe, 0x73, 0xcd, 0x84, 0xb7, 0xb0, 0x0e,
+	0x53, 0x13, 0x90, 0xd8, 0x24, 0xa3, 0xac, 0xe4,
+	0x2a, 0x05, 0xb8, 0x76, 0x21, 0x6e, 0x58, 0xe0,
+	0x7f, 0x87, 0xf2, 0x6f, 0x94, 0xfc, 0x74, 0x0d,
+	0x70, 0xb4, 0x1d, 0xe4, 0xac, 0x5d, 0xca, 0xaa,
+	0x1f, 0xe2, 0x8f, 0xd4, 0x14, 0x5a, 0xb4, 0x8a,
+	0xda, 0x1f, 0xa9, 0x9d, 0x7c, 0xc0, 0x12, 0x47,
+	0xbf, 0x63, 0x3b, 0x4f, 0xc9, 0xc1, 0xcd, 0xbd,
+	0x47, 0x68, 0xf0, 0x20, 0xae, 0x36, 0xe7, 0x62,
+	0xf2, 0x88, 0x03, 0xb1, 0x09, 0xa9, 0xa2, 0xf6,
+	0xe7, 0x8a, 0x5e, 0x80, 0x19, 0xe0, 0x2c, 0x10,
+	0xa3, 0x6e, 0x10, 0x49, 0x99, 0x48, 0x7c, 0xdc,
+	0x67, 0xc1, 0xed, 0x72, 0x1d, 0xc5, 0xff, 0x2e,
+	0x91, 0x8a, 0x93, 0xbb, 0x63, 0xb4, 0x8d, 0xbe,
+	0xd5, 0xa1, 0xc4, 0x4d, 0x4f, 0xeb, 0xfa, 0xa0,
+	0x34, 0xf5, 0x82, 0xb9, 0x26, 0x4b, 0xa8, 0xa9,
+	0xf5, 0xa6, 0x6a, 0x0c, 0xdc, 0xea, 0x9f, 0x81,
+	0x78, 0x74, 0x3c, 0x7a, 0x3a, 0x00, 0x9c, 0x38,
+	0xbf, 0xc4, 0x81, 0x26, 0x37, 0xf2, 0x37, 0x30,
+	0xda, 0xfb, 0x9a, 0x78, 0x06, 0x00, 0xdf, 0xfa,
+	0x4a, 0xcd, 0x7b, 0x29, 0xe7, 0x4b, 0x00, 0xee,
+	0x73, 0xc8, 0xb0, 0xa9, 0xdb, 0xc5, 0x10, 0xfe,
+	0xba, 0x60, 0xa1, 0xc1, 0x67, 0x1d, 0x9c, 0xf6,
+	0x02, 0x79, 0x5d, 0xdb, 0xfb, 0x07, 0x69, 0x5d,
+	0xa9, 0x48, 0x60, 0x8e, 0xe3, 0xec, 0x54, 0xb2,
+	0x14, 0x16, 0x17, 0x47, 0x13, 0x67, 0x87, 0xf9,
+	0x99, 0xbd, 0x68, 0x1b, 0x64, 0xee, 0x86, 0x13,
+	0x4e, 0x8f, 0x49, 0x5c, 0x3b, 0xe5, 0xbf, 0xb8,
+	0x4b, 0xde, 0xde, 0xca, 0x68, 0x1f, 0x10, 0xc1,
+	0x27, 0xcd, 0xcf, 0xe8, 0x85, 0xdd, 0xc4, 0x2e,
+	0x87, 0x11, 0x1a, 0x86, 0x06, 0x28, 0x83, 0x12,
+	0x61, 0xbf, 0xa6, 0x5d, 0x4a, 0x25, 0x4a, 0x85,
+	0x24, 0xd0, 0xe9, 0x41, 0x84, 0x72, 0xb8, 0x51,
+	0x1b, 0x23, 0x08, 0x7e, 0x00, 0x42, 0x19, 0x2c,
+	0x48, 0xfa, 0x64, 0x26, 0x08, 0xdb, 0x9d, 0xd1,
+	0xa1, 0x1d, 0x96, 0x88, 0x6e, 0x20, 0x98, 0x71,
+	0x17, 0x49, 0x69, 0x0d, 0x44, 0xeb, 0x8b, 0x2c,
+	0x87, 0x14, 0xf5, 0xf8, 0xff, 0x10, 0x3a, 0x3c,
+	0xb6, 0x85, 0xd6, 0xec, 0xb7, 0x74, 0xab, 0x29,
+	0xe2, 0xd9, 0x90, 0x69, 0x98, 0x8a, 0x5e, 0x1e,
+	0xdb, 0x88, 0x64, 0x7f, 0x81, 0x2d, 0xdc, 0xc5,
+	0xed, 0x39, 0x56, 0x89, 0x95, 0x92, 0xb2, 0x70,
+	0xb5, 0xcc, 0x75, 0xd8, 0xd8, 0x1a, 0x67, 0xd3,
+	0x4d, 0x88, 0x6e, 0x22, 0x71, 0xc3, 0x7a, 0x67,
+	0xff, 0x77, 0x6b, 0xbb, 0x54, 0x95, 0x11, 0x47,
+	0x66, 0x11, 0x10, 0x41, 0x82, 0x49, 0x7d, 0x76,
+	0x20, 0xdb, 0xb3, 0x99, 0xa6, 0x9c, 0xf7, 0xe5,
+	0x53, 0x07, 0xd1, 0x7c, 0x2c, 0x7f, 0xa0, 0xde,
+	0x78, 0x8b, 0x7d, 0x10, 0x29, 0xa0, 0xe3, 0xa6,
+	0xaa, 0xe7, 0x6f, 0x0d, 0xcc, 0x5d, 0x11, 0xf8,
+	0xad, 0xf9, 0x1f, 0xf6, 0x6e, 0x7c, 0xf9, 0xc6,
+	0x00, 0xff, 0x8a, 0x59, 0xed, 0x55, 0x2c, 0x10,
+	0x7a, 0x7d, 0xb3, 0x78, 0x8c, 0x8c, 0xac, 0xc9,
+	0xd0, 0x9d, 0xbd, 0x80, 0xb8, 0xd5, 0xd6, 0x07,
+	0xa0, 0xdb, 0xdf, 0x1d, 0x41, 0x6e, 0x8d, 0xf7,
+	0x40, 0x9f, 0x00, 0x24, 0x87, 0x4e, 0x21, 0x9f,
+	0xda, 0xf5, 0xe1, 0x6b, 0xc1, 0x8b, 0x19, 0x01,
+	0x4f, 0x77, 0x04, 0xff, 0x73, 0x1e, 0x75, 0xbb,
+	0xdf, 0x33, 0xd7, 0xcf, 0xd8, 0xd6, 0xad, 0x63,
+	0xc5, 0x3d, 0xfb, 0xf4, 0x5c, 0x87, 0x3e, 0x46,
+	0x37, 0xab, 0x36, 0x76, 0xde, 0x47, 0x68, 0x08,
+	0x64, 0xa7, 0xe8, 0x61, 0x4b, 0x66, 0x46, 0x5c,
+	0xf9, 0xd7, 0x01, 0x55, 0x1d, 0xd0, 0x43, 0x8f,
+	0x5a, 0x2e, 0x76, 0x8c, 0x48, 0x2a, 0xdc, 0xe3,
+	0x87, 0x91, 0x1c, 0xf2, 0x01, 0x05, 0xeb, 0x24,
+	0xd9, 0x4f, 0x9f, 0x37, 0x02, 0xd8, 0x60, 0x2a,
+	0xf4, 0x15, 0x90, 0x7d, 0xc1, 0x7c, 0x6c, 0xc4,
+	0x59, 0xbb, 0x15, 0x30, 0x0e, 0x87, 0x00, 0x77,
+	0x3c, 0x26, 0xb4, 0x95, 0x75, 0xe3, 0x25, 0x97,
+	0xde, 0xe9, 0xdc, 0xf0, 0x03, 0xba, 0xec, 0x9c,
+	0xce, 0xcc, 0x8e, 0x04, 0x1c, 0x26, 0x80, 0xd6,
+	0x65, 0x4f, 0x1e, 0xb8, 0x7c, 0x1e, 0xf7, 0x1d,
+	0x18, 0x22, 0x97, 0x45, 0x9f, 0x78, 0xcc, 0xf0,
+	0xb8, 0x8e, 0x6b, 0x12, 0x84, 0x05, 0x96, 0x54,
+	0xa9, 0x0d, 0xec, 0x56, 0x2d, 0xda, 0xfc, 0x9a,
+	0x8e, 0x06, 0x90, 0xa5, 0x5c, 0x21, 0x9f, 0x63,
+	0x59, 0xe4, 0x57, 0x08, 0xf4, 0xff, 0x68, 0x9d,
+	0x76, 0xde, 0xc0, 0xf6, 0xe4, 0xea, 0xb5, 0x0e,
+	0xcb, 0xb9, 0xba, 0x4c, 0xd0, 0x2a, 0x18, 0xf1,
+	0x50, 0x47, 0x87, 0xc8, 0xa8, 0xa0, 0x2b, 0x11,
+	0x1b, 0xae, 0xee, 0xdf, 0x0a, 0xb2, 0xcb, 0x87,
+	0x49, 0x28, 0x82, 0x7f, 0x6c, 0x72, 0x83, 0x78,
+	0xda, 0x99, 0x0f, 0xbb, 0x27, 0xd5, 0x87, 0xa5,
+	0xd1, 0xd0, 0x77, 0x41, 0xa5, 0xa5, 0x82, 0xfd,
+	0x9c, 0x10, 0xad, 0xba, 0xa9, 0x9c, 0x57, 0x3f,
+	0x44, 0x21, 0xe9, 0x7e, 0xf3, 0xe8, 0xd5, 0x8f,
+	0xd8, 0xef, 0xde, 0x1c, 0x2b, 0x85, 0x0e, 0xbb,
+	0xea, 0xc7, 0x70, 0x01, 0x0e, 0xac, 0xcc, 0x73,
+	0x1c, 0xdc, 0x09, 0x83, 0x84, 0x45, 0xf4, 0x10,
+	0x17, 0xd4, 0x64, 0xe2, 0x06, 0xc2, 0x65, 0x33,
+	0xfa, 0x0c, 0x94, 0x7e, 0x9a, 0xe4, 0x00, 0x16,
+	0x63, 0x6d, 0x62, 0x65, 0x7d, 0x07, 0x24, 0x7d,
+	0x4a, 0xae, 0x5f, 0xe6, 0x25, 0xab, 0xcb, 0x7f,
+	0xbe, 0x87, 0x63, 0x4f, 0xe7, 0xa5, 0x39, 0xa6,
+	0x07, 0x8f, 0xd0, 0xf1, 0xff, 0xf8, 0xba, 0xd0,
+	0xba, 0xe1, 0xde, 0xde, 0x40, 0x20, 0x77, 0xac,
+	0x16, 0x73, 0xec, 0x5f, 0x02, 0x83, 0x91, 0xb2,
+	0xd4, 0x23, 0x34, 0x8c, 0xf9, 0xe8, 0xba, 0xb2,
+	0xf7, 0x10, 0x4e, 0x16, 0x2c, 0x61, 0x04, 0xbd,
+	0xb2, 0x22, 0x29, 0x3f, 0xb8, 0x9c, 0xb0, 0xd7,
+	0x35, 0x2c, 0xd3, 0xbb, 0xeb, 0x6c, 0x03, 0x61,
+	0x77, 0xa8, 0x73, 0x3b, 0x9e, 0x19, 0xc9, 0xeb,
+	0xbc, 0xc0, 0xd0, 0x06, 0xd8, 0xee, 0x98, 0x3e,
+	0xe6, 0x2d, 0xf7, 0x59, 0x15, 0x72, 0xf3, 0xad,
+	0x40, 0x9e, 0x28, 0x71, 0x19, 0x82, 0x1d, 0xec,
+	0xce, 0xdf, 0x3a, 0x69, 0x57, 0xc2, 0x60, 0x0e,
+	0x7f, 0xff, 0xc7, 0x33, 0x7b, 0xad, 0xf7, 0x76,
+	0x7a, 0x11, 0xa5, 0xb3, 0xfd, 0x47, 0x2d, 0x14,
+	0xd7, 0x1a, 0x70, 0x59, 0x0b, 0xc4, 0x2c, 0x1e,
+	0xc9, 0x7c, 0x83, 0x47, 0x62, 0x9c, 0x83, 0xcd,
+	0xe0, 0x84, 0x26, 0xaf, 0x69, 0x37, 0xbf, 0xce,
+	0x77, 0x75, 0xb0, 0xa1, 0x3c, 0xe3, 0xe3, 0x92,
+	0xdc, 0xcf, 0x87, 0xb2, 0x06, 0x77, 0xd6, 0x85,
+	0xcb, 0x74, 0xac, 0xe6, 0xc2, 0x7e, 0x94, 0x77,
+	0x91, 0x3e, 0xff, 0xd3, 0x93, 0x4d, 0x2c, 0xfa,
+	0x17, 0x1c, 0x2a, 0x4e, 0xc3, 0xda, 0x8f, 0x47,
+	0x0e, 0x58, 0x37, 0xfe, 0x02, 0x91, 0x33, 0xfd,
+	0x18, 0xd4, 0x3e, 0x2d, 0xf5, 0x12, 0xa2, 0x21,
+	0xd4, 0x07, 0xb0, 0x9d, 0xd6, 0xaf, 0x47, 0xef,
+	0x72, 0x89, 0xd6, 0xe8, 0x36, 0xd4, 0x8e, 0x50,
+	0xe5, 0x86, 0x4b, 0xd2, 0x95, 0x68, 0x1d, 0x9b,
+	0xef, 0x08, 0xa2, 0xda, 0xb7, 0xa4, 0x92, 0x0b,
+	0x07, 0xbe, 0x4f, 0xfd, 0xfc, 0xff, 0xab, 0xa4,
+	0x14, 0x4c, 0x1d, 0x36, 0x50, 0x51, 0x36, 0x24,
+	0xf4, 0x3b, 0x61, 0xb3, 0xbd, 0x80, 0xdf, 0xdf,
+	0x5b, 0x6c, 0x63, 0x46, 0xe7, 0xd1, 0x3e, 0x30,
+	0x1d, 0x54, 0xb7, 0xe0, 0xa9, 0x9e, 0xe5, 0x57,
+	0x1a, 0xf3, 0xfd, 0x24, 0xf3, 0x3c, 0xac, 0xf0,
+	0xa6, 0xdc, 0xea, 0x91, 0xed, 0xd0, 0xf4, 0x8b,
+	0x4c, 0x7a, 0x88, 0x99, 0xb4, 0x75, 0xc0, 0x32,
+	0x09, 0xa9, 0x48, 0x7f, 0x38, 0x4e, 0x8f, 0x39,
+	0x6c, 0x1c, 0x90, 0xe7, 0x1d, 0xb3, 0xde, 0xf5,
+	0x64, 0xc8, 0xaf, 0x7a, 0x3a, 0x4f, 0x4f, 0x7a,
+	0xd9, 0xbc, 0x65, 0xc3, 0x90, 0xa5, 0x40, 0x29,
+	0xc7, 0x36, 0x0a, 0x50, 0xc0, 0x75, 0x27, 0x33,
+	0x4a, 0x75, 0x93, 0x88, 0xb5, 0x01, 0xcc, 0x83,
+	0xa6, 0xb6, 0xec, 0x23, 0xd5, 0xdf, 0x25, 0x27,
+	0xfc, 0xd0, 0xc5, 0xc0, 0x45, 0x9d, 0x9b, 0xf6,
+	0xb7, 0xd6, 0x22, 0x5e, 0x80, 0xc7, 0x03, 0xcb,
+	0x2c, 0xb5, 0x17, 0xc8, 0x76, 0xdd, 0xc1, 0x63,
+	0xd1, 0xbe, 0x98, 0x57, 0x4c, 0x47, 0xfd, 0xe7,
+	0x91, 0x49, 0x2b, 0x6a, 0x6b, 0x0b, 0xe9, 0x67,
+	0x57, 0x35, 0x58, 0xae, 0xcf, 0xbf, 0x9b, 0x5d,
+	0xdf, 0xb2, 0x8e, 0xc5, 0x80, 0x82, 0x5a, 0x82,
+	0xdc, 0xae, 0x48, 0x12, 0x73, 0x56, 0xe6, 0x20,
+	0x2c, 0xb1, 0xf6, 0xf5, 0xda, 0xe4, 0x6e, 0xd9,
+	0x9e, 0xbc, 0x2d, 0x37, 0x8c, 0x2c, 0x59, 0x9c,
+	0xc9, 0xdc, 0x97, 0xda, 0x6d, 0x9b, 0x0c, 0x3f,
+	0x9e, 0x23, 0x75, 0x52, 0xbf, 0xb6, 0x2c, 0xea,
+	0x69, 0x94, 0x43, 0x1e, 0xa4, 0xc9, 0x68, 0x2f,
+	0x5d, 0xe5, 0xdd, 0x37, 0x80, 0x13, 0xa0, 0x4b,
+	0x08, 0x93, 0xa1, 0xb0, 0x99, 0x28, 0x91, 0xd9,
+	0x13, 0x46, 0xd2, 0x28, 0x17, 0x94, 0x4b, 0x62,
+	0x27, 0x58, 0x62, 0x48, 0x8b, 0x2f, 0xef, 0x30,
+	0x46, 0x15, 0x46, 0x82, 0x0b, 0x3f, 0xd5, 0x8f,
+	0xe9, 0xce, 0xe3, 0x0b, 0xd6, 0xed, 0xf6, 0x29,
+	0x1d, 0x21, 0x68, 0xf5, 0x53, 0xa8, 0x37, 0x79,
+	0xdf, 0xdc, 0xdd, 0x8d, 0xf7, 0xe6, 0x88, 0x7e,
+	0xba, 0xdb, 0x3a, 0xb7, 0x9b, 0x28, 0xee, 0x80,
+	0x3f, 0x71, 0xc8, 0x36, 0x88, 0xba, 0xec, 0x2d,
+	0x15, 0x1c, 0xe2, 0x64, 0xa6, 0x8d, 0x32, 0x7e,
+	0xa7, 0x01, 0xa2, 0xeb, 0xa6, 0x02, 0x75, 0x58,
+	0xe6, 0x07, 0xbf, 0x88, 0x53, 0x59, 0x70, 0xfa,
+	0x8a, 0xba, 0xee, 0x17, 0x54, 0x70, 0xd5, 0x8f,
+	0x43, 0x32, 0xf4, 0xda, 0xd1, 0xbb, 0xe3, 0x49,
+	0xdc, 0xfb, 0xd9, 0x14, 0x29, 0x6a, 0xef, 0xa2,
+	0x95, 0xe6, 0x67, 0x5e, 0x4b, 0x66, 0x94, 0x57,
+	0x10, 0x89, 0x25, 0x00, 0x37, 0xd9, 0xbc, 0x91,
+	0xc6, 0x8d, 0xe3, 0xe0, 0xc7, 0xce, 0x7f, 0x1f,
+	0xee, 0xc8, 0x52, 0x4c, 0x05, 0x55, 0xdc, 0x81,
+	0xa8, 0xa4, 0xbf, 0x10, 0x50, 0xc2, 0xc1, 0xf8,
+	0xea, 0x40, 0xd0, 0x40, 0x12, 0xf0, 0xc0, 0xe5,
+	0xd5, 0x59, 0x93, 0xc0, 0xeb, 0xef, 0x68, 0x20,
+	0x45, 0x1d, 0xa0, 0x5a, 0x7d, 0xed, 0xd2, 0x76,
+	0xff, 0xc6, 0x12, 0xa9, 0x39, 0x80, 0x25, 0x6a,
+	0x01, 0x37, 0x4c, 0xee, 0x68, 0x31, 0x6c, 0x10,
+	0xe5, 0x75, 0x93, 0x89, 0x28, 0xe1, 0xe6, 0x04,
+	0xf5, 0x81, 0x55, 0x5e, 0x5e, 0xab, 0x18, 0xc0,
+	0xce, 0xe8, 0x19, 0xb3, 0x22, 0xa6, 0x5c, 0xaf,
+	0xe1, 0x3e, 0x72, 0x0b, 0x9e, 0xa9, 0xb1, 0xa7,
+	0x1a, 0xf0, 0x23, 0xbd, 0x23, 0xae, 0x99, 0x39,
+	0x79, 0x3c, 0xab, 0x37, 0x63, 0x1a, 0x54, 0x59,
+	0x62, 0x34, 0xcb, 0x8a, 0x1b, 0x4c, 0x50, 0x73,
+	0x64, 0x1d, 0xbd, 0xe3, 0x94, 0xab, 0xc6, 0xe5,
+	0x8b, 0xa4, 0xc3, 0xb7, 0xe8, 0x7c, 0xd1, 0xa6,
+	0x68, 0xcb, 0x83, 0xd1, 0xa9, 0xda, 0xc9, 0xe9,
+	0xc6, 0x38, 0x9a, 0xbe, 0x6f, 0x7f, 0xc3, 0xdb,
+	0x4e, 0xa9, 0x44, 0xc9, 0x88, 0x6d, 0x52, 0x91,
+	0xd2, 0x83, 0x2d, 0xfc, 0x88, 0xc3, 0x25, 0xe7,
+	0x86, 0x29, 0xbe, 0x7c, 0xad, 0x35, 0xb2, 0x1d,
+	0x71, 0xe8, 0xf6, 0x7e, 0x2b, 0x7e, 0x75, 0x7c,
+	0x2a, 0x9f, 0x17, 0x67, 0x0d, 0x76, 0xb8, 0xd1,
+	0x16, 0xc5, 0x8f, 0x86, 0x0f, 0xc6, 0x5f, 0xa2,
+	0xe5, 0x33, 0xe6, 0x0a, 0x2e, 0x9b, 0x05, 0x38,
+	0xde, 0x14, 0x24, 0x8c, 0xdc, 0xfc, 0xbc, 0x7d,
+	0x24, 0xd9, 0x8e, 0x85, 0x5c, 0x07, 0xad, 0xe3,
+	0x11, 0xd8, 0x4e, 0x32, 0x05, 0xce, 0xa1, 0xee,
+	0x88, 0x3d, 0x04, 0xbf, 0x13, 0x2b, 0xe0, 0xf2,
+	0xba, 0xb1, 0xcc, 0x0e, 0xe7, 0xe1, 0x61, 0xf1,
+	0x37, 0xc3, 0x34, 0xc3, 0xce, 0xc0, 0x8f, 0xca,
+	0x3b, 0x4f, 0xfe, 0x4b, 0xb2, 0x32, 0xb4, 0x32,
+	0xaf, 0xbe, 0xf3, 0xe0, 0x58, 0xe5, 0x36, 0x36,
+	0x0a, 0x42, 0xf5, 0xe4, 0xe5, 0xe7, 0xa9, 0x9d,
+	0x87, 0x4a, 0x32, 0xf1, 0x24, 0x00, 0xe3, 0x52,
+	0x7a, 0xb0, 0x30, 0x2c, 0xed, 0x7e, 0x33, 0xcc,
+	0xcb, 0xf4, 0xb8, 0x83, 0x1a, 0x53, 0x6b, 0xaf,
+	0x4e, 0x59, 0x6b, 0x77, 0x33, 0x9f, 0x98, 0xa4,
+	0xeb, 0x55, 0xf5, 0xd7, 0x12, 0xc2, 0x40, 0x51,
+	0x5a, 0x7d, 0xfb, 0xe7, 0x7a, 0xd2, 0x1a, 0x5f,
+	0x1e, 0xa2, 0x3b, 0x07, 0xfd, 0x67, 0x3f, 0x86,
+	0x88, 0x59, 0xfe, 0x3e, 0xd7, 0x86, 0x56, 0x9c,
+	0x49, 0x81, 0xee, 0xbd, 0xcf, 0xb9, 0x1e, 0x6a,
+	0xc5, 0x77, 0x6e, 0x93, 0xe2, 0xb1, 0x52, 0xe6,
+	0x33, 0xf6, 0x7e, 0x82, 0x5a, 0x5c, 0x26, 0x81,
+	0xc4, 0x2b, 0x7f, 0x30, 0x2d, 0xfa, 0x81, 0xa5,
+	0x25, 0xfe, 0x75, 0x83, 0x5a, 0x79, 0x95, 0x2d,
+	0x65, 0x64, 0xb1, 0xed, 0xb3, 0x9d, 0x25, 0x6c,
+	0xe1, 0x68, 0xa9, 0x46, 0x06, 0x87, 0xad, 0x41,
+	0xc3, 0xe5, 0x33, 0xe2, 0x74, 0xf4, 0x13, 0x5b,
+	0xac, 0x1c, 0x92, 0xce, 0xc2, 0xb2, 0x9b, 0x93,
+	0xa1, 0x38, 0x80, 0xf3, 0xef, 0x06, 0x7b, 0x46,
+	0xd8, 0x0d, 0xb3, 0xee, 0x07, 0x2c, 0x6e, 0xcd,
+	0x2e, 0x67, 0xc9, 0xd6, 0xc7, 0x89, 0x9c, 0x42,
+	0x69, 0xdb, 0x42, 0x02, 0x2b, 0x41, 0x10, 0x62,
+	0x1f, 0x9c, 0x9e, 0x8f, 0xb1, 0x8f, 0x28, 0x39,
+	0x40, 0x82, 0x26, 0x33, 0xbc, 0x72, 0x82, 0x85,
+	0x62, 0x1c, 0xef, 0x71, 0xc7, 0x7d, 0xb7, 0xae,
+	0xe4, 0xce, 0x36, 0x76, 0xfd, 0xe4, 0x66, 0x1c,
+	0xe9, 0x63, 0x78, 0xc7, 0x2c, 0x0d, 0x55, 0x74,
+	0xdc, 0x16, 0x2c, 0xb9, 0xee, 0xbc, 0xfa, 0xa4,
+	0x12, 0xcf, 0xd3, 0xd6, 0x63, 0x11, 0x95, 0xe5,
+	0x0d, 0xc3, 0xbb, 0xc1, 0xfc, 0x05, 0xc7, 0xee,
+	0xc8, 0x82, 0x96, 0x76, 0x4a, 0x2a, 0xb0, 0x5c,
+	0x07, 0x28, 0x15, 0x5b, 0x46, 0x1e, 0xd9, 0x52,
+	0x75, 0x4b, 0x94, 0xf2, 0xb0, 0xe4, 0x97, 0x3c,
+	0x46, 0xd0, 0x57, 0x27, 0x1d, 0x9e, 0x49, 0x4a,
+	0x82, 0x80, 0xda, 0xa7, 0x3b, 0xf8, 0xa6, 0x83,
+	0xaa, 0xb7, 0x43, 0xc5, 0x86, 0xff, 0x5f, 0x7b,
+	0x59, 0x03, 0x05, 0xa3, 0x96, 0xc1, 0x7f, 0xef,
+	0x31, 0x51, 0xe0, 0xa6, 0x9f, 0x3a, 0xd1, 0x3d,
+	0x52, 0x7f, 0x5d, 0xe5, 0xb2, 0x8f, 0x61, 0x4f,
+	0x0e, 0x9e, 0x07, 0x2c, 0x02, 0x2b, 0x8c, 0xe5,
+	0x4b, 0xcc, 0x34, 0x8f, 0x3a, 0x9a, 0xa4, 0x0b,
+	0x5f, 0xe0, 0x28, 0xd4, 0x8b, 0xa0, 0x5f, 0xfc,
+	0x15, 0x50, 0x1a, 0xf3, 0xac, 0xda, 0xef, 0xea,
+	0x93, 0xc4, 0x9e, 0x07, 0x0f, 0x17, 0x6a, 0xd1,
+	0x09, 0x40, 0x24, 0x34, 0xcb, 0xd2, 0x0e, 0xee,
+	0x36, 0x79, 0xb9, 0x16, 0x2b, 0x07, 0x66, 0x88,
+	0x56, 0x7d, 0x1c, 0x7e, 0x88, 0x31, 0xb0, 0x16,
+	0x98, 0xb7, 0xa6, 0xcd, 0x34, 0x16, 0x57, 0xcb,
+	0x52, 0x1a, 0x07, 0xfc, 0xb2, 0xdb, 0x93, 0xda,
+	0x54, 0x03, 0x9d, 0x00, 0x04, 0x5b, 0xfb, 0xc8,
+	0x0b, 0x57, 0x9f, 0xbd, 0x89, 0xef, 0x48, 0x01,
+	0xc3, 0x4e, 0x1d, 0x3d, 0xb5, 0xf9, 0x43, 0x16,
+	0xe8, 0xc0, 0x72, 0x69, 0xd8, 0x13, 0xc9, 0x50,
+	0x7b, 0x35, 0xff, 0x54, 0xf9, 0xab, 0xa7, 0x2b,
+	0x63, 0x58, 0x86, 0xba, 0x8b, 0xc6, 0xb1, 0x61,
+	0x5b, 0xd8, 0x77, 0x2b, 0xb9, 0xb8, 0x0a, 0x07,
+	0x1c, 0xc1, 0x82, 0x5b, 0x7d, 0x80, 0xca, 0xac,
+	0xf6, 0x8e, 0x57, 0xf9, 0xb7, 0xaf, 0xe3, 0xb2,
+	0x35, 0x1f, 0xdd, 0x45, 0xa4, 0x65, 0xee, 0xb2,
+	0x0d, 0xa7, 0xf1, 0xc4, 0x82, 0x14, 0xe4, 0x9e,
+	0x3d, 0x9c, 0x72, 0x76, 0xde, 0xba, 0xe4, 0x69,
+	0x72, 0x61, 0xcc, 0x90, 0x2a, 0x0d, 0xb1, 0x97,
+	0x8a, 0xf1, 0x1e, 0x79, 0x01, 0x72, 0x83, 0xc3,
+	0xac, 0x8e, 0x8f, 0xa8, 0xac, 0x09, 0x87, 0x86,
+	0x07, 0xf3, 0xc0, 0xa8, 0x24, 0xaf, 0x7e, 0xe0,
+	0x12, 0x2d, 0x2a, 0xae, 0xed, 0xb3, 0x32, 0x14,
+	0x0a, 0xfc, 0xbc, 0x30, 0x92, 0xe2, 0xa8, 0x8b,
+	0xf9, 0xa0, 0x8e, 0x5b, 0xf9, 0xcc, 0xa1, 0xc8,
+	0x4c, 0x16, 0x68, 0xc8, 0x48, 0x2f, 0xdf, 0xc3,
+	0xd1, 0x97, 0xd8, 0x6e, 0xa5, 0x7f, 0x77, 0x11,
+	0x4b, 0xcd, 0x65, 0xdd, 0xce, 0x37, 0x0a, 0x1d,
+	0x82, 0xc7, 0x53, 0x24, 0xbb, 0xf9, 0x88, 0xd7,
+	0x06, 0xa8, 0xa8, 0x1e, 0xa5, 0xc4, 0x8c, 0x60,
+	0xc2, 0xb8, 0xc8, 0x44, 0x5d, 0x53, 0xd5, 0x31,
+	0x07, 0x80, 0xe6, 0x73, 0xb7, 0x0e, 0x23, 0xa8,
+	0xe8, 0x4b, 0xbd, 0xac, 0x5b, 0x2c, 0xd9, 0x83,
+	0x3b, 0xb8, 0x40, 0x4b, 0x9f, 0x62, 0xb4, 0x32,
+	0xea, 0xed, 0xd4, 0xe4, 0x85, 0xb4, 0xae, 0x3c,
+	0xae, 0x2b, 0x02, 0x71, 0xa4, 0x43, 0x2c, 0x8c,
+	0x4e, 0xe1, 0xd8, 0x44, 0x8d, 0xdc, 0xc0, 0xbf,
+	0xd2, 0x41, 0x36, 0xd1, 0xa5, 0x41, 0xb7, 0xc0,
+	0xc2, 0xd3, 0x6b, 0x23, 0x70, 0xba, 0x82, 0x65,
+	0xfc, 0x3a, 0xd6, 0xdb, 0x89, 0xb4, 0xdd, 0x23,
+	0xb6, 0x72, 0x9d, 0xc2, 0xe4, 0x7b, 0xff, 0x92,
+	0xe4, 0x2e, 0x61, 0x21, 0x53, 0xa3, 0x09, 0x84,
+	0x15, 0x33, 0xca, 0x24, 0x2a, 0x6f, 0x19, 0xaf,
+	0x73, 0xe2, 0x9c, 0x78, 0x4f, 0x12, 0xb9, 0xb6,
+	0x5d, 0xed, 0xc7, 0x00, 0xf2, 0x15, 0x80, 0xfc,
+	0x0a, 0xb5, 0x11, 0xc9, 0xe0, 0xa7, 0x2d, 0x0c,
+	0x9a, 0xb3, 0x04, 0x0c, 0x50, 0x26, 0x3a, 0x97,
+	0xe7, 0xfd, 0x8c, 0x29, 0x1f, 0xc4, 0x13, 0xfa,
+	0x97, 0x5b, 0x4c, 0x23, 0x51, 0x98, 0xe5, 0x07,
+	0x91, 0x1f, 0x8c, 0x48, 0xbb, 0x1c, 0xfb, 0x93,
+	0x09, 0xe8, 0x5f, 0x36, 0xe9, 0xc1, 0x62, 0x77,
+	0x29, 0x7c, 0xf9, 0x85, 0xe8, 0x09, 0xee, 0x58,
+	0xe8, 0x4b, 0x41, 0xa3, 0xbd, 0x93, 0x91, 0x3c,
+	0x4e, 0x33, 0xd0, 0x96, 0x2d, 0x60, 0xc0, 0xce,
+	0xb6, 0xeb, 0xce, 0x36, 0xcc, 0x91, 0xc3, 0xe2,
+	0xb2, 0x9a, 0x45, 0xe8, 0xc4, 0xaa, 0x3f, 0x99,
+	0x21, 0xcc, 0x4e, 0x91, 0x6c, 0xc1, 0xe1, 0x0b,
+	0x0f, 0x1c, 0xed, 0x31, 0xdc, 0x38, 0xdc, 0xc6,
+	0x3e, 0x80, 0x9e, 0x2a, 0x35, 0x49, 0x2e, 0x0e,
+	0xcd, 0xc8, 0x95, 0x39, 0x33, 0x30, 0xc9, 0x99,
+	0x85, 0x32, 0x3a, 0xc7, 0xc8, 0x10, 0x1c, 0xe5,
+	0xbc, 0xb7, 0xce, 0x02, 0x14, 0x2c, 0x9e, 0xa6,
+	0xd0, 0x4b, 0xdb, 0x4b, 0xf6, 0x2a, 0xd4, 0xc5,
+	0x8a, 0x87, 0x43, 0x20, 0x67, 0x38, 0xc0, 0xa8,
+	0x16, 0xc9, 0xb9, 0x16, 0xd1, 0x89, 0x55, 0x93,
+	0x33, 0x37, 0x75, 0x2e, 0x51, 0x16, 0x75, 0x32,
+	0x0d, 0xd7, 0x96, 0x54, 0xb0, 0xf8, 0xdc, 0xe6,
+	0x6f, 0x22, 0x2f, 0x5c, 0x84, 0xb7, 0x71, 0x20,
+	0x52, 0xf4, 0xff, 0xa1, 0xea, 0x19, 0x96, 0x94,
+	0x42, 0x94, 0xae, 0x35, 0xb3, 0xbf, 0x68, 0x03,
+	0x48, 0x8d, 0x06, 0x78, 0x2a, 0xd7, 0xb0, 0x12,
+	0x93, 0xac, 0x9b, 0x70, 0x81, 0x2d, 0xf5, 0x86,
+	0x3f, 0x73, 0xfb, 0x1e, 0xe0, 0x71, 0x5c, 0xf7,
+	0x6c, 0x3c, 0x63, 0x1b, 0x20, 0x96, 0xde, 0x2c,
+	0x92, 0x61, 0x72, 0x3b, 0x75, 0x35, 0x34, 0x3e,
+	0xfe, 0xf8, 0x92, 0x60, 0x23, 0x65, 0x09, 0x26,
+	0xb6, 0x18, 0xed, 0x81, 0x04, 0x7b, 0x0d, 0x21,
+	0x78, 0x27, 0xea, 0x16, 0x15, 0xa5, 0xdf, 0x99,
+	0x75, 0x67, 0x76, 0xc2, 0xfd, 0x04, 0xf7, 0x1b,
+	0x28, 0xd2, 0x00, 0x65, 0x8b, 0xe6, 0x30, 0x2c,
+	0xb9, 0x21, 0x93, 0xeb, 0x12, 0x7c, 0x8f, 0x54,
+	0xd8, 0x6e, 0x82, 0xf7, 0xfe, 0x10, 0x9e, 0xf1,
+	0x0e, 0xab, 0xa6, 0xf9, 0xd9, 0x19, 0x04, 0xdb,
+	0xf0, 0x8a, 0xf6, 0xd3, 0x87, 0x95, 0x5c, 0x38,
+	0x4e, 0x8a, 0xfd, 0xc5, 0xd8, 0x84, 0x12, 0xc7,
+	0x98, 0x21, 0x39, 0xf0, 0x14, 0xba, 0x14, 0xc5,
+	0xf3, 0x63, 0xdf, 0x2d, 0xf4, 0x48, 0x0a, 0x70,
+	0xac, 0xc2, 0x99, 0x42, 0x80, 0xa5, 0x1f, 0x4f,
+	0xdb, 0x62, 0x67, 0x7f, 0xe1, 0xb0, 0xf8, 0xef,
+	0xb1, 0x8d, 0xb1, 0xc1, 0xaa, 0x22, 0xe9, 0xd6,
+	0x98, 0x6b, 0xf7, 0x03, 0xd2, 0xfe, 0x9a, 0x1d,
+	0x62, 0xb9, 0x54, 0x6f, 0xec, 0x72, 0xbe, 0xf5,
+	0x29, 0x9e, 0x95, 0x84, 0x51, 0xdb, 0x7d, 0x69,
+	0x36, 0x9a, 0xc7, 0xd0, 0x0b, 0x4d, 0x4f, 0x0a,
+	0x78, 0x60, 0x67, 0xe1, 0x8c, 0x08, 0x21, 0x2f,
+	0x64, 0x53, 0xd1, 0xe0, 0x8b, 0x02, 0x92, 0x8b,
+	0xea, 0x64, 0x9d, 0x3e, 0xd2, 0xf8, 0x5e, 0xe4,
+	0x60, 0x27, 0x47, 0x21, 0xee, 0xd9, 0xa3, 0x6b,
+	0x55, 0x68, 0xc4, 0xe6, 0xd4, 0x37, 0x5f, 0x8f,
+	0x82, 0x92, 0x78, 0x3e, 0x1c, 0x86, 0x63, 0xdd,
+	0x24, 0x10, 0xb7, 0x00, 0x88, 0xd7, 0x50, 0xa2,
+	0xa9, 0x32, 0x89, 0x9b, 0x69, 0x55, 0xd8, 0xd9,
+	0x50, 0xcd, 0xb6, 0xea, 0xa7, 0xf8, 0x60, 0x7a,
+	0x56, 0xa8, 0xfd, 0xb2, 0x35, 0x7a, 0x29, 0x95,
+	0xd2, 0xaf, 0xbb, 0xf9, 0x7f, 0x6f, 0x8c, 0x26,
+	0x8e, 0xe6, 0xfc, 0x86, 0x06, 0x7e, 0x5c, 0xba,
+	0x42, 0x12, 0x6c, 0xc7, 0xdd, 0x1f, 0x3f, 0x1e,
+	0x83, 0xd2, 0xb2, 0x9f, 0x81, 0x4b, 0x0c, 0x56,
+	0x0f, 0xe5, 0x72, 0x48, 0x05, 0x22, 0x06, 0x7b,
+	0xd3, 0xd7, 0xfd, 0x2a, 0x83, 0xff, 0x46, 0x9f,
+	0xf1, 0x1f, 0x55, 0x57, 0xca, 0xdb, 0x43, 0xac,
+	0xe4, 0x2d, 0x08, 0xd2, 0x27, 0xac, 0x7e, 0xa1,
+	0xcf, 0xf2, 0x0d, 0x97, 0xe4, 0x4f, 0x7c, 0x1d,
+	0xbf, 0xe6, 0x53, 0x8c, 0xaf, 0x4d, 0x49, 0x01,
+	0x40, 0x29, 0x9e, 0x8d, 0xe1, 0x2e, 0xe6, 0x73,
+	0x60, 0x2c, 0x88, 0xc4, 0xea, 0x1f, 0x6f, 0x9b,
+	0xc2, 0x17, 0xbe, 0xf9, 0xb3, 0x5c, 0xa1, 0xf4,
+	0xe3, 0x18, 0x60, 0xa9, 0xdc, 0xf9, 0xda, 0x2c,
+	0x9b, 0x39, 0x40, 0xcc, 0xb9, 0x1f, 0x51, 0x06,
+	0xd7, 0xf6, 0x7c, 0xd4, 0xad, 0x66, 0xcd, 0xb5,
+	0xbf, 0x7a, 0xdb, 0x84, 0xdc, 0x0d, 0x86, 0x52,
+	0xd1, 0x6f, 0xbc, 0xe7, 0x4e, 0x8b, 0x1c, 0x90,
+	0x9e, 0x35, 0x57, 0x90, 0x8d, 0x77, 0xd0, 0x18,
+	0xb7, 0x35, 0xa2, 0xcd, 0x1b, 0xc2, 0x5a, 0xf5,
+	0xcf, 0x7e, 0xa1, 0x30, 0x38, 0x3e, 0xb6, 0x82,
+	0xae, 0xb5, 0x44, 0xdc, 0x8a, 0xc8, 0x1a, 0x5a,
+	0xff, 0x79, 0xa0, 0x2a, 0x43, 0x2a, 0x5c, 0x0a,
+	0x03, 0x1f, 0x90, 0x73, 0x95, 0x3c, 0xe5, 0x64,
+	0x62, 0xc7, 0x37, 0xc4, 0x87, 0xc9, 0x75, 0x6a,
+	0xb7, 0x2b, 0x7e, 0x48, 0xa5, 0xd1, 0xa6, 0x29,
+	0xa0, 0x72, 0xfe, 0xe3, 0x3f, 0x33, 0xb7, 0x05,
+	0xd5, 0x85, 0xea, 0x12, 0x49, 0xfe, 0x4b, 0x62,
+	0x08, 0xaa, 0x2c, 0x1d, 0xa9, 0x3b, 0x6f, 0x93,
+	0x85, 0xaf, 0x9f, 0xe0, 0x27, 0xac, 0x90, 0x89,
+	0x20, 0xcd, 0x4d, 0x67, 0x4f, 0x5f, 0xd0, 0x79,
+	0x90, 0xc8, 0xe3, 0xdd, 0xa2, 0x98, 0xde, 0xfe,
+	0x51, 0xd7, 0xfa, 0xef, 0xfc, 0x69, 0x4e, 0x8e,
+	0x1a, 0x2e, 0xcb, 0x7a, 0x17, 0x1e, 0x51, 0x51,
+	0xbc, 0x82, 0xc3, 0x76, 0xe6, 0x81, 0xcf, 0x8c,
+	0x19, 0xf4, 0xb4, 0xea, 0x35, 0xf7, 0x43, 0xf5,
+	0x22, 0xed, 0xc5, 0x5c, 0x6d, 0xb7, 0xab, 0x98,
+	0xd5, 0x13, 0x2c, 0xa2, 0x67, 0xf0, 0xb6, 0x65,
+	0x0b, 0x51, 0xc4, 0xf3, 0x19, 0xd5, 0xde, 0xd3,
+	0xeb, 0x45, 0x0d, 0xf2, 0xee, 0xd8, 0x12, 0x64,
+	0x6d, 0x6c, 0x4a, 0xd5, 0xae, 0x11, 0x63, 0x75,
+	0x1d, 0x20, 0x4f, 0xcd, 0xa2, 0xae, 0x92, 0x7f,
+	0xc4, 0xbe, 0x4d, 0x5f, 0xce, 0xb3, 0x95, 0x6c,
+	0x72, 0xe1, 0x84, 0xdb, 0x6f, 0x97, 0x54, 0xf8,
+	0x32, 0xb3, 0x9d, 0x73, 0x73, 0x45, 0x79, 0xe9,
+	0xc1, 0x73, 0x4e, 0x94, 0x46, 0xc2, 0x6c, 0x78,
+	0x16, 0x8c, 0xdf, 0x6a, 0x18, 0x9c, 0x4c, 0xdf,
+	0x6d, 0x3a, 0xb1, 0x7c, 0xfe, 0xc0, 0x3c, 0x5a,
+	0xa2, 0xa4, 0xbd, 0x84, 0x13, 0x0c, 0x07, 0x85,
+	0xb6, 0xb7, 0x9f, 0xe5, 0x93, 0x29, 0x4c, 0x10,
+	0xe1, 0x15, 0x0b, 0x99, 0x44, 0xe0, 0x98, 0x67,
+	0x3c, 0x2b, 0xa7, 0x65, 0x4c, 0x72, 0xd3, 0xef,
+	0x0c, 0x64, 0x4b, 0x43, 0x6d, 0xfc, 0x17, 0x41,
+	0x07, 0xf3, 0x04, 0xa3, 0xa8, 0xe2, 0x84, 0x04,
+	0xf7, 0x77, 0x88, 0xca, 0x9e, 0x6a, 0x32, 0xf4,
+	0x0d, 0x0b, 0xdb, 0xc7, 0x68, 0x30, 0x9b, 0x55,
+	0xc1, 0xb8, 0x7f, 0x00, 0x49, 0xda, 0xc0, 0xf1,
+	0x78, 0xa6, 0x8e, 0xdc, 0x98, 0x0e, 0xf1, 0x3d,
+	0x76, 0xaf, 0x30, 0xfd, 0x78, 0xf6, 0xc0, 0xb1,
+	0x0c, 0xce, 0xa2, 0xe0, 0xcb, 0x1d, 0x94, 0x83,
+	0x18, 0x62, 0x4b, 0xd7, 0xe7, 0x27, 0xc1, 0xe9,
+	0x99, 0x93, 0x6b, 0x4d, 0x26, 0xef, 0xb5, 0x48,
+	0x8c, 0xba, 0x91, 0x45, 0xcf, 0xf8, 0x73, 0x35,
+	0xb5, 0xc0, 0x08, 0x2f, 0x4b, 0xbe, 0x93, 0xfe,
+	0x49, 0xd0, 0xaf, 0x21, 0x87, 0xa3, 0x45, 0x43,
+	0xa8, 0xb5, 0xad, 0x3f, 0x97, 0xf3, 0x83, 0x01,
+	0x38, 0xbf, 0xfd, 0x32, 0x6b, 0x56, 0xa0, 0x24,
+	0x80, 0x0b, 0xd4, 0x42, 0xe7, 0xe5, 0xed, 0x48,
+	0xb4, 0xb4, 0x9a, 0xbf, 0x8b, 0x38, 0x77, 0x25,
+	0x04, 0x2a, 0x14, 0x10, 0x2b, 0x46, 0xda, 0x82,
+	0x97, 0xad, 0x61, 0x71, 0xdd, 0xbc, 0xec, 0x06,
+	0xd8, 0xe5, 0xdb, 0x87, 0x9d, 0x24, 0xa2, 0x81,
+	0xdc, 0x95, 0xbc, 0x10, 0x2b, 0xdd, 0x02, 0x28,
+	0xbb, 0xd0, 0x4c, 0x0e, 0x02, 0xff, 0x12, 0x73,
+	0xb4, 0x8c, 0xe0, 0x26, 0xe3, 0xd2, 0xdb, 0x57,
+	0x7b, 0xdf, 0x30, 0xe4, 0x6f, 0xeb, 0x36, 0x1c,
+	0xa9, 0x14, 0xfb, 0xce, 0x81, 0x05, 0xf3, 0x13,
+	0xdc, 0x6e, 0xbc, 0x40, 0x5e, 0x60, 0xf1, 0x82,
+	0x7d, 0x4e, 0x14, 0x8f, 0x74, 0xcd, 0x9e, 0xcf,
+	0xcb, 0x36, 0x71, 0x8d, 0x85, 0x18, 0x28, 0xe9,
+	0x0f, 0x1d, 0x1d, 0x88, 0xab, 0xc5, 0xf6, 0x58,
+	0xe6, 0xed, 0x78, 0xe5, 0x46, 0xfb, 0x28, 0xf5,
+	0xcf, 0xd1, 0x1c, 0xfa, 0xc3, 0x14, 0xc3, 0x32,
+	0x8a, 0xed, 0x4a, 0x8f, 0x2e, 0xf9, 0xca, 0x5b,
+	0x40, 0x9c, 0x53, 0x18, 0x9f, 0x12, 0xbc, 0x8e,
+	0x8a, 0xfd, 0x10, 0x23, 0x1d, 0xa2, 0x4f, 0x84,
+	0xeb, 0xe2, 0x42, 0x7a, 0x4c, 0x68, 0xbf, 0x5e,
+	0x05, 0x30, 0x3c, 0x97, 0x8a, 0xa0, 0x1d, 0x5f,
+	0x8a, 0xb3, 0x76, 0x69, 0x0a, 0xa3, 0x4a, 0x1b,
+	0x63, 0x99, 0x1a, 0xd7, 0x76, 0xae, 0xc1, 0x14,
+	0xb0, 0x47, 0x93, 0x39, 0x23, 0x10, 0x2f, 0xcf,
+	0xf6, 0xff, 0x5d, 0x92, 0x54, 0x8d, 0x51, 0xd2,
+	0x33, 0x6b, 0x7f, 0xd0, 0x26, 0xbb, 0xe8, 0x5a,
+	0xed, 0x6a, 0xe8, 0xaf, 0xab, 0x5b, 0x28, 0x47,
+	0xc8, 0xc3, 0x56, 0x75, 0xe7, 0xdc, 0x1c, 0x90,
+	0x38, 0x7d, 0x81, 0x3d, 0x2d, 0xb1, 0xf9, 0x4f,
+	0x79, 0x34, 0x61, 0xee, 0xd7, 0x71, 0xfb, 0x25,
+	0x7b, 0x34, 0x53, 0xe9, 0x65, 0xcf, 0xa8, 0x4b,
+	0x2f, 0x0a, 0x1b, 0xeb, 0x70, 0xeb, 0xe3, 0xe0,
+	0x79, 0xca, 0x9e, 0x00, 0x77, 0xbb, 0x5e, 0x53,
+	0x48, 0xdf, 0x3a, 0x99, 0x3c, 0x1e, 0x8e, 0xb3,
+	0x89, 0x15, 0xc0, 0x79, 0x96, 0x3c, 0x00, 0x8c,
+	0x18, 0xfe, 0xb1, 0x9d, 0xb3, 0xd3, 0xb6, 0xb8,
+	0xad, 0xbf, 0x7a, 0xc7, 0x92, 0xce, 0xc2, 0xb2,
+	0xae, 0xc1, 0x67, 0xa6, 0x1a, 0xe0, 0x2b, 0x76,
+	0x75, 0x39, 0x24, 0xe4, 0x40, 0x1c, 0x53, 0x9d,
+	0x4b, 0xcf, 0x11, 0x82, 0x3c, 0xbf, 0x72, 0xb2,
+	0x40, 0xaa, 0x03, 0x1e, 0x4a, 0x37, 0x89, 0x87,
+	0x6f, 0x16, 0xc7, 0xbd, 0x91, 0x59, 0x42, 0x28,
+	0x72, 0x3e, 0xc4, 0x2e, 0x2c, 0x5f, 0x69, 0x4f,
+	0xe8, 0x70, 0xff, 0x97, 0x48, 0xfd, 0x1d, 0xd0,
+	0xc9, 0x31, 0xec, 0x67, 0xde, 0x92, 0xc1, 0x60,
+	0x1d, 0x93, 0x19, 0xec, 0x5c, 0xfc, 0xce, 0xf9,
+	0xc3, 0xf3, 0xaf, 0x9d, 0xbe, 0x51, 0x1e, 0x4c,
+	0x5d, 0xa2, 0x62, 0x7b, 0xb0, 0x45, 0x7e, 0x45,
+	0x03, 0x5b, 0xd9, 0x43, 0x20, 0x2e, 0x73, 0x1b,
+	0xbd, 0xe4, 0x69, 0xd6, 0x6e, 0x41, 0x76, 0x65,
+	0x3d, 0x3d, 0x28, 0x98, 0xff, 0x70, 0x35, 0xa7,
+	0x28, 0x5f, 0xd5, 0xaf, 0x5c, 0xdc, 0xcd, 0xfd,
+	0xaf, 0x10, 0xf7, 0x62, 0xe0, 0x35, 0x7d, 0x15,
+	0x0a, 0x5a, 0x15, 0x71, 0x3b, 0x00, 0x11, 0xea,
+	0xf8, 0x8d, 0x4b, 0x3f, 0x59, 0x9b, 0x26, 0x86,
+	0x49, 0xcf, 0x86, 0xc4, 0xf2, 0x0c, 0xef, 0x21,
+	0x5d, 0xbe, 0x6a, 0x17, 0x25, 0xd9, 0xe6, 0xa1,
+	0x0d, 0x55, 0xeb, 0xc1, 0x31, 0xcb, 0xc5, 0xbf,
+	0xdb, 0xdd, 0x0e, 0xc0, 0x73, 0x18, 0xdc, 0x0a,
+	0x23, 0xbb, 0xc1, 0xf1, 0xe8, 0x8f, 0x1e, 0x77,
+	0x0f, 0x88, 0x62, 0x36, 0x5b, 0x60, 0x44, 0xba,
+	0xd3, 0x2c, 0x27, 0x7e, 0x66, 0xc1, 0x0e, 0x01,
+	0x1e, 0xe6, 0x69, 0xff, 0xfc, 0xd2, 0xad, 0xe7,
+	0xb3, 0x42, 0xb8, 0xc3, 0xea, 0xe9, 0xbd, 0x4a,
+	0xb4, 0x36, 0xf6, 0x5d, 0x25, 0xb3, 0xba, 0xe1,
+	0xb1, 0x45, 0x9c, 0x20, 0xef, 0x4a, 0xf5, 0x3f,
+	0x30, 0x10, 0x66, 0x54, 0xc2, 0xe7, 0x21, 0xb4,
+};
+
+/**
+ * crc16_test_empty - Test crc16 with empty data
+ *
+ * Test crc16 with empty data, the result should be the same as the initial crc
+ */
+static void crc16_test_empty(struct kunit *test)
+{
+	u16 crc;
+
+	crc = crc16(0x00, data, 0);
+	KUNIT_EXPECT_EQ(test, crc, 0);
+	crc = crc16(0xFF, data, 0);
+	KUNIT_EXPECT_EQ(test, crc, 0xFF);
+}
+
+/**
+ * crc16_test_correctness - Test crc16 with known data
+ *
+ * Test crc16 with a set of known data and expected results
+ */
+static void crc16_test_correctness(struct kunit *test)
+{
+	size_t i;
+	u16 crc;
+
+	for (i = 0; i < 100; i++) {
+		crc = crc16(tests[i].crc, data + tests[i].start,
+			    tests[i].length);
+		KUNIT_EXPECT_EQ(test, crc, tests[i].crc16);
+	}
+}
+
+
+/**
+ * crc16_test_combine - Test split crc16 calculations
+ *
+ * Test crc16 with data split in two parts, the result should be the same as
+ * crc16 with the data combined
+ */
+static void crc16_test_combine(struct kunit *test)
+{
+	size_t i, j;
+	u16 crc;
+
+	for (i = 0; i < 100; i++) {
+		for (j = 0; j < tests[i].length; j++) {
+			crc = crc16(tests[i].crc, data + tests[i].start, j);
+			crc = crc16(crc, data + tests[i].start + j, tests[i].length - j);
+			KUNIT_EXPECT_EQ(test, crc, tests[i].crc16);
+		}
+	}
+}
+
+
+static struct kunit_case crc16_test_cases[] = {
+	KUNIT_CASE(crc16_test_empty),
+	KUNIT_CASE(crc16_test_combine),
+	KUNIT_CASE(crc16_test_correctness),
+	{},
+};
+
+static struct kunit_suite crc16_test_suite = {
+	.name = "crc16",
+	.test_cases = crc16_test_cases,
+};
+kunit_test_suite(crc16_test_suite);
+
+MODULE_AUTHOR("Fabricio Gasperin <fgasperin@lkcamp.dev>");
+MODULE_AUTHOR("Vinicius Peixoto <vpeixoto@lkcamp.dev>");
+MODULE_AUTHOR("Enzo Bertoloti <ebertoloti@lkcamp.dev>");
+MODULE_DESCRIPTION("Unit tests for crc16");
+MODULE_LICENSE("GPL");
-- 
2.43.0

Hey!

On 9/23/24 01:26, Vinicius Peixoto wrote:
> Hi all,
>
> This patch was developed during a hackathon organized by LKCAMP [1],
> with the objective of writing KUnit tests, both to introduce people to
> the kernel development process and to learn about different subsystems
> (with the positive side effect of improving the kernel test coverage, of
> course).
>
> We noticed there were tests for CRC32 in lib/crc32test.c and thought it
> would be nice to have something similar for CRC16, since it seems to be
> widely used in network drivers (as well as in some ext4 code).
>
> Although this patch turned out quite big, most of the LOCs come from
> tables containing randomly-generated test data that we use to validate
> the kernel's implementation of CRC-16.
Can you share how you created the tables? Given that is impossible to 
review the table itself, at least people will be able to see how they 
got created at least.
> We would really appreciate any feedback/suggestions on how to improve
> this. Thanks! :-)
>
> Vinicius Peixoto (1):
>    lib/crc16_kunit.c: add KUnit tests for crc16
>
>   lib/Kconfig.debug |   8 +
>   lib/Makefile      |   1 +
>   lib/crc16_kunit.c | 715 ++++++++++++++++++++++++++++++++++++++++++++++
>   3 files changed, 724 insertions(+)
>   create mode 100644 lib/crc16_kunit.c
>

Hi André,

On 9/24/24 6:33 PM, André Almeida wrote:
> Hey!
> 
> On 9/23/24 01:26, Vinicius Peixoto wrote:
>> Hi all,
>>
>> This patch was developed during a hackathon organized by LKCAMP [1],
>> with the objective of writing KUnit tests, both to introduce people to
>> the kernel development process and to learn about different subsystems
>> (with the positive side effect of improving the kernel test coverage, of
>> course).
>>
>> We noticed there were tests for CRC32 in lib/crc32test.c and thought it
>> would be nice to have something similar for CRC16, since it seems to be
>> widely used in network drivers (as well as in some ext4 code).
>>
>> Although this patch turned out quite big, most of the LOCs come from
>> tables containing randomly-generated test data that we use to validate
>> the kernel's implementation of CRC-16.
> Can you share how you created the tables? Given that is impossible to 
> review the table itself, at least people will be able to see how they 
> got created at least.

Yes, of course, that was an oversight on my part. I'll make sure to add 
a more detailed explanation in the cover letter/commit message for the 
next revisions. Thanks for the suggestion!

This test follows lib/crc32test.c very closely; the data table is filled 
with 4096 random bytes, and the idea is to calculate several checksums 
within it by randomly choosing a i) start offset within the data buffer, 
ii) number of bytes after the start offset and iii) input CRC.

The checksums for the randomly-generated test cases were calculated 
using a reference implementation [1] and this test compares them against 
the values yielded by the kernel's implementation.

Thanks,
Vinicius

[1] https://github.com/lammertb/libcrc/blob/master/src/crc16.c

>> We would really appreciate any feedback/suggestions on how to improve
>> this. Thanks! :-)
>>
>> Vinicius Peixoto (1):
>>    lib/crc16_kunit.c: add KUnit tests for crc16
>>
>>   lib/Kconfig.debug |   8 +
>>   lib/Makefile      |   1 +
>>   lib/crc16_kunit.c | 715 ++++++++++++++++++++++++++++++++++++++++++++++
>>   3 files changed, 724 insertions(+)
>>   create mode 100644 lib/crc16_kunit.c
>>

From: Vinicius Peixoto
> Sent: 23 September 2024 00:27
> 
> Hi all,
> 
> This patch was developed during a hackathon organized by LKCAMP [1],
> with the objective of writing KUnit tests, both to introduce people to
> the kernel development process and to learn about different subsystems
> (with the positive side effect of improving the kernel test coverage, of
> course).
> 
> We noticed there were tests for CRC32 in lib/crc32test.c and thought it
> would be nice to have something similar for CRC16, since it seems to be
> widely used in network drivers (as well as in some ext4 code).
> 
> Although this patch turned out quite big, most of the LOCs come from
> tables containing randomly-generated test data that we use to validate
> the kernel's implementation of CRC-16.
> 
> We would really appreciate any feedback/suggestions on how to improve
> this. Thanks! :-)

Would is be better to use a trivial PRNG to generate repeatable 'random enough'
data, rather than having a large static array?

As a matter of interest, how in crc16 implemented (I know I could look).
The code version:

uint32_t
crc_step(uint32_t crc, uint32_t byte_val)
{
    uint32_t t = crc ^ (byte_val & 0xff);
    t = (t ^ t << 4) & 0xff;
    return crc >> 8 ^ t << 8 ^ t << 3 ^ t >> 4;
}

may well be faster than a lookup table version.
Especially on modern multi-issue cpu and/or for small buffers where the lookup
table won't necessarily be resident in the D-cache.

It is slightly slower than the table lookup on the simple Nios-II cpu.
But we use a custom instruction to do it in one clock.

	David

> 
> Vinicius Peixoto (1):
>   lib/crc16_kunit.c: add KUnit tests for crc16
> 
>  lib/Kconfig.debug |   8 +
>  lib/Makefile      |   1 +
>  lib/crc16_kunit.c | 715 ++++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 724 insertions(+)
>  create mode 100644 lib/crc16_kunit.c
> 
> --
> 2.43.0
> 

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

...
> The checksums for the randomly-generated test cases were calculated
> using a reference implementation [1] and this test compares them against
> the values yielded by the kernel's implementation.

I'd just use a naïve implementation - doesn't really matter
if it is a bit slow.

Slow is relative - this code only takes 35ms to crc-64 over 5MB of data.

{
    volatile const uint32_t *r = (const void *)buf;
    for (crc = 0; r < (const uint32_t *)buf_end; r++) {
        uint64_t val = le32toh(*r);
        crc ^= bswap64(val);
        for (i = 0; i < 32; i++) {
            if (crc & (1ull << 63))
                crc = (crc << 1) ^ 0x42f0e1eba9ea3693ull;
            else
                crc = crc << 1;
        }
    }
}

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

Hi David,

On 9/26/24 13:21, David Laight wrote:
> ...
>> The checksums for the randomly-generated test cases were calculated
>> using a reference implementation [1] and this test compares them against
>> the values yielded by the kernel's implementation.
> 
> I'd just use a naïve implementation - doesn't really matter
> if it is a bit slow.

Thanks for the feedback. I agree that it makes more sense to use a naive 
implementation to validate the results from the kernel's crc16 instead 
of having a table of pre-computed results. I will include in v2 a 
bog-standard implementation of crc16 similar to yours (using a loop 
instead of a lookup table) to validate the results.

Thanks,
Vinicius

> 
> Slow is relative - this code only takes 35ms to crc-64 over 5MB of data.
> 
> {
>      volatile const uint32_t *r = (const void *)buf;
>      for (crc = 0; r < (const uint32_t *)buf_end; r++) {
>          uint64_t val = le32toh(*r);
>          crc ^= bswap64(val);
>          for (i = 0; i < 32; i++) {
>              if (crc & (1ull << 63))
>                  crc = (crc << 1) ^ 0x42f0e1eba9ea3693ull;
>              else
>                  crc = crc << 1;
>          }
>      }
> }
> 
> 	David
> 
> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> Registration No: 1397386 (Wales)

Hi David,

On 9/25/24 08:26, David Laight wrote:
> From: Vinicius Peixoto
>> Sent: 23 September 2024 00:27
>>
>> Hi all,
>>
>> This patch was developed during a hackathon organized by LKCAMP [1],
>> with the objective of writing KUnit tests, both to introduce people to
>> the kernel development process and to learn about different subsystems
>> (with the positive side effect of improving the kernel test coverage, of
>> course).
>>
>> We noticed there were tests for CRC32 in lib/crc32test.c and thought it
>> would be nice to have something similar for CRC16, since it seems to be
>> widely used in network drivers (as well as in some ext4 code).
>>
>> Although this patch turned out quite big, most of the LOCs come from
>> tables containing randomly-generated test data that we use to validate
>> the kernel's implementation of CRC-16.
>>
>> We would really appreciate any feedback/suggestions on how to improve
>> this. Thanks! :-)
> 
> Would is be better to use a trivial PRNG to generate repeatable 'random enough'
> data, rather than having a large static array?

That's fair, the big static arrays are indeed very unwieldy. I reworked 
it to use next_pseudo_random32 (from include/linux/prandom.h) to fill 
the tables with pseudorandom data before running the tests, and will 
send a v2 soon.

The LOC count is a lot smaller, although it is still using static tables 
to store the data and the tests (I thought it would be simpler than 
allocating them at runtime). Do you think this is acceptable?

> As a matter of interest, how in crc16 implemented (I know I could look).
> The code version:
> 
> uint32_t
> crc_step(uint32_t crc, uint32_t byte_val)
> {
>      uint32_t t = crc ^ (byte_val & 0xff);
>      t = (t ^ t << 4) & 0xff;
>      return crc >> 8 ^ t << 8 ^ t << 3 ^ t >> 4;
> }
> 
> may well be faster than a lookup table version.
> Especially on modern multi-issue cpu and/or for small buffers where the lookup
> table won't necessarily be resident in the D-cache.

lib/crc16.c does use a lookup table. I haven't had the time to run 
benchmarks testing whether this version is faster, but I'm curious as 
well, so I'll look into it.

Thanks,
Vinicius

> 
> It is slightly slower than the table lookup on the simple Nios-II cpu.
> But we use a custom instruction to do it in one clock.
> 
> 	David
> 
>>
>> Vinicius Peixoto (1):
>>    lib/crc16_kunit.c: add KUnit tests for crc16
>>
>>   lib/Kconfig.debug |   8 +
>>   lib/Makefile      |   1 +
>>   lib/crc16_kunit.c | 715 ++++++++++++++++++++++++++++++++++++++++++++++
>>   3 files changed, 724 insertions(+)
>>   create mode 100644 lib/crc16_kunit.c
>>
>> --
>> 2.43.0
>>
> 
> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> Registration No: 1397386 (Wales)