| Message ID | 20180718165545.1622-2-colyli@suse.de (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
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. > + * 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 <colyli@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 <colyli@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
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 <colyli@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 <colyli@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 >
On Wed, 2018-07-25 at 00:29 +0800, Coly Li wrote: > 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. IIUC this series in Andrew's quilt. So, it's still possible to replace it with better one, I suppose. Ask Andrew (at least I remember recent case where he just replaced series by fixed one).
On 2018/7/25 1:06 AM, Andy Shevchenko wrote: > On Wed, 2018-07-25 at 00:29 +0800, Coly Li wrote: >> 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. > > IIUC this series in Andrew's quilt. So, it's still possible to replace > it with better one, I suppose. Ask Andrew (at least I remember recent > case where he just replaced series by fixed one). Hi Andrew, It seems there should be some fix/update for this series. I see current series is in linux-next for now. If I want to add the fix, should I post a new version of the series, or the incremental patches to fix current series ? Thanks in advance for your advice. Coly Li
On Wed, 25 Jul 2018 10:37:23 +0800 Coly Li <colyli@suse.de> wrote: > > IIUC this series in Andrew's quilt. So, it's still possible to replace > > it with better one, I suppose. Ask Andrew (at least I remember recent > > case where he just replaced series by fixed one). > > Hi Andrew, > > It seems there should be some fix/update for this series. I see current > series is in linux-next for now. If I want to add the fix, should I post > a new version of the series, or the incremental patches to fix current > series ? mm... it sounds like the changes will be large, so probably a new series would be better at this early stage. If the changes are small then little fixup patches would be nicer to the people who have already reviewed v1.
On 2018/7/26 5:22 AM, Andrew Morton wrote: > On Wed, 25 Jul 2018 10:37:23 +0800 Coly Li <colyli@suse.de> wrote: > >>> IIUC this series in Andrew's quilt. So, it's still possible to replace >>> it with better one, I suppose. Ask Andrew (at least I remember recent >>> case where he just replaced series by fixed one). >> >> Hi Andrew, >> >> It seems there should be some fix/update for this series. I see current >> series is in linux-next for now. If I want to add the fix, should I post >> a new version of the series, or the incremental patches to fix current >> series ? > > mm... it sounds like the changes will be large, so probably a new > series would be better at this early stage. If the changes are small > then little fixup patches would be nicer to the people who have already > reviewed v1. > Yes, it is large (patch 3/3 will be removed). So I will post a new series to replace current series. Thanks for the hint. Coly Li
diff --git a/include/linux/crc64.h b/include/linux/crc64.h new file mode 100644 index 000000000000..1fc9f0710c10 --- /dev/null +++ b/include/linux/crc64.h @@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* + * See lib/crc64.c for the related specification and polynomical arithmetic. + */ +#ifndef _LINUX_CRC64_H +#define _LINUX_CRC64_H + +#include <linux/types.h> + +u64 __pure crc64_be(u64 crc, const void *p, size_t len); +#endif /* _LINUX_CRC64_H */ diff --git a/lib/.gitignore b/lib/.gitignore index 09aae85418ab..f2a39c9e5485 100644 --- a/lib/.gitignore +++ b/lib/.gitignore @@ -2,5 +2,7 @@ # Generated files # gen_crc32table +gen_crc64table crc32table.h +crc64table.h oid_registry_data.c diff --git a/lib/Kconfig b/lib/Kconfig index 706836ec314d..9c10b9852563 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -170,6 +170,14 @@ config CRC32_BIT endchoice +config CRC64 + tristate "CRC64 functions" + help + This option is provided for the case where no in-kernel-tree + modules require CRC64 functions, but a module built outside + the kernel tree does. Such modules that use library CRC64 + functions require M here. + config CRC4 tristate "CRC4 functions" help diff --git a/lib/Makefile b/lib/Makefile index 90dc5520b784..40c215181687 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -102,6 +102,7 @@ obj-$(CONFIG_CRC16) += crc16.o obj-$(CONFIG_CRC_T10DIF)+= crc-t10dif.o obj-$(CONFIG_CRC_ITU_T) += crc-itu-t.o obj-$(CONFIG_CRC32) += crc32.o +obj-$(CONFIG_CRC64) += crc64.o obj-$(CONFIG_CRC32_SELFTEST) += crc32test.o obj-$(CONFIG_CRC4) += crc4.o obj-$(CONFIG_CRC7) += crc7.o @@ -215,7 +216,9 @@ obj-$(CONFIG_FONT_SUPPORT) += fonts/ obj-$(CONFIG_PRIME_NUMBERS) += prime_numbers.o hostprogs-y := gen_crc32table +hostprogs-y += gen_crc64table clean-files := crc32table.h +clean-files += crc64table.h $(obj)/crc32.o: $(obj)/crc32table.h @@ -225,6 +228,14 @@ quiet_cmd_crc32 = GEN $@ $(obj)/crc32table.h: $(obj)/gen_crc32table $(call cmd,crc32) +$(obj)/crc64.o: $(obj)/crc64table.h + +quiet_cmd_crc64 = GEN $@ + cmd_crc64 = $< > $@ + +$(obj)/crc64table.h: $(obj)/gen_crc64table + $(call cmd,crc64) + # # Build a fast OID lookip registry from include/linux/oid_registry.h # diff --git a/lib/crc64.c b/lib/crc64.c new file mode 100644 index 000000000000..d093298ba2c6 --- /dev/null +++ b/lib/crc64.c @@ -0,0 +1,56 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Normal 64-bit CRC calculation. + * + * This is a basic crc64 implementation following ECMA-182 specification, + * which can be found from, + * http://www.ecma-international.org/publications/standards/Ecma-182.htm + * + * Dr. Ross N. Williams has a great document to introduce the idea of CRC + * algorithm, here the CRC64 code is also inspired by the table-driven + * algorithm and detail example from this paper. This paper can be found + * from, + * http://www.ross.net/crc/download/crc_v3.txt + * + * crc64table[256] is the lookup table of a table-driver 64-bit CRC + * 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 <colyli@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. + * @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. + * + * 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. + * + * 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 <colyli@suse.de> + */ +#include <inttypes.h> +#include <stdio.h> + +#include <linux/swab.h> + +#define CRC64_ECMA182_POLY 0x42F0E1EBA9EA3693ULL + +static int64_t crc64_table[256] = {0}; + +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; +}