On 2018/7/24 12:26 PM, Eric Biggers wrote: > On Thu, Jul 19, 2018 at 12:55:43AM +0800, Coly Li wrote: >> This patch adds the re-write crc64 calculation routines for Linux kernel. >> The CRC64 polynomical arithmetic follows ECMA-182 specification, inspired > > "polynomical" => "polynomial". Same everywhere else in the patches. >
Hi Eric, Thanks for your careful review. I will post a fixing patch to fix all these issues. Coly Li >> + * crc64table[256] is the lookup table of a table-driver 64-bit CRC > > "table-driver" => "table-driven" > >> + * calculation, which is generated by gen_crc64table.c in kernel build >> + * time. The polynomial of crc64 arithmetic is from ECMA-182 specification >> + * as well, which is defined as, >> + * >> + * x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45 + >> + * x^40 + x^39 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^29 + x^27 + >> + * x^24 + x^23 + x^22 + x^21 + x^19 + x^17 + x^13 + x^12 + x^10 + x^9 + >> + * x^7 + x^4 + x + 1 >> + * >> + * Copyright 2018 SUSE Linux. >> + * Author: Coly Li <col...@suse.de> >> + */ >> + >> +#include <linux/module.h> >> +#include <linux/types.h> >> +#include "crc64table.h" >> + >> +MODULE_DESCRIPTION("CRC64 calculations"); >> +MODULE_LICENSE("GPL v2"); >> + >> +/** >> + * crc64_be - Calculate bitwise big-endian ECMA-182 CRC64 >> + * @crc: seed value for computation. 0 for a new CRC computing, or the >> + * previous crc64 value if computing incrementally. > > "0 or (u64)~0 for a new CRC calculation". Both conventions are common in > CRCs. > In fact the all-ones convention is generally considered better, because it > causes leading zeroes in the data to affect the checksum. > >> + * @p: pointer to buffer over which CRC64 is run >> + * @len: length of buffer @p >> + */ >> +u64 __pure crc64_be(u64 crc, const void *p, size_t len) >> +{ >> + size_t i, t; >> + >> + const unsigned char *_p = p; >> + >> + for (i = 0; i < len; i++) { >> + t = ((crc >> 56) ^ (*_p++)) & 0xFF; >> + crc = crc64table[t] ^ (crc << 8); >> + } >> + >> + return crc; >> +} >> +EXPORT_SYMBOL_GPL(crc64_be); >> diff --git a/lib/gen_crc64table.c b/lib/gen_crc64table.c >> new file mode 100644 >> index 000000000000..8296b0c3ea30 >> --- /dev/null >> +++ b/lib/gen_crc64table.c >> @@ -0,0 +1,68 @@ >> +// SPDX-License-Identifier: GPL-2.0 >> +/* >> + * Generate lookup table for the talbe-driven CRC64 calculation. > > "talbe-driven" => "table-driven" > >> + * >> + * gen_crc64table is executed in kernel build time and generates >> + * lib/crc64table.h. This header is included by lib/crc64.c for >> + * the table-driver CRC64 calculation. > > "table-driver" => "table-driven" > >> + * >> + * See lib/crc64.c for more information about which specification >> + * and polynomical arithmetic that gen_crc64table.c follows to >> + * generate the lookup table. >> + * >> + * Copyright 2018 SUSE Linux. >> + * Author: Coly Li <col...@suse.de> >> + */ >> +#include <inttypes.h> >> +#include <stdio.h> >> + >> +#include <linux/swab.h> >> + >> +#define CRC64_ECMA182_POLY 0x42F0E1EBA9EA3693ULL >> + >> +static int64_t crc64_table[256] = {0}; > > This really should be uint64_t, not int64_t. > >> + >> +static void generate_crc64_table(void) >> +{ >> + uint64_t i, j, c, crc; >> + >> + for (i = 0; i < 256; i++) { >> + crc = 0; >> + c = i << 56; >> + >> + for (j = 0; j < 8; j++) { >> + if ((crc ^ c) & 0x8000000000000000ULL) >> + crc = (crc << 1) ^ CRC64_ECMA182_POLY; >> + else >> + crc <<= 1; >> + c <<= 1; >> + } >> + >> + crc64_table[i] = crc; >> + } >> +} >> + >> +static void print_crc64_table(void) >> +{ >> + int i; >> + >> + printf("/* this file is generated - do not edit */\n\n"); >> + printf("#include <linux/types.h>\n"); >> + printf("#include <linux/cache.h>\n\n"); >> + printf("static const u64 ____cacheline_aligned crc64table[256] = {\n"); >> + for (i = 0; i < 256; i++) { >> + printf("\t0x%016" PRIx64 "ULL", crc64_table[i]); >> + if (i & 0x1) >> + printf(",\n"); >> + else >> + printf(", "); >> + } >> + printf("};\n"); >> +} >> + >> +int main(int argc, char *argv[]) >> +{ >> + generate_crc64_table(); >> + print_crc64_table(); >> + return 0; >> +} >> -- >> 2.17.1 >> > > - Eric >