From patchwork Tue Jul 17 06:57:09 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Coly Li X-Patchwork-Id: 10528187 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 454706020A for ; Tue, 17 Jul 2018 06:57:31 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 3B45B28B2A for ; Tue, 17 Jul 2018 06:57:31 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 2F97528B53; Tue, 17 Jul 2018 06:57:31 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-7.9 required=2.0 tests=BAYES_00, MAILING_LIST_MULTI, RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 6BF4128B2A for ; Tue, 17 Jul 2018 06:57:30 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727481AbeGQH2e (ORCPT ); Tue, 17 Jul 2018 03:28:34 -0400 Received: from mx2.suse.de ([195.135.220.15]:49424 "EHLO mx1.suse.de" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1728095AbeGQH2d (ORCPT ); Tue, 17 Jul 2018 03:28:33 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay1.suse.de (unknown [195.135.220.254]) by mx1.suse.de (Postfix) with ESMTP id 88E19ADD9; Tue, 17 Jul 2018 06:57:25 +0000 (UTC) From: Coly Li To: linux-kernel@vger.kernel.org Cc: linux-bcache@vger.kernel.org, linux-block@vger.kernel.org, Coly Li , Greg Kroah-Hartman , Andy Shevchenko , Michael Lyle , Kent Overstreet , Linus Torvalds , Thomas Gleixner , Kate Stewart Subject: [PATCH v2 1/3] lib: add crc64 calculation routines Date: Tue, 17 Jul 2018 14:57:09 +0800 Message-Id: <20180717065711.28281-2-colyli@suse.de> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180717065711.28281-1-colyli@suse.de> References: <20180717065711.28281-1-colyli@suse.de> Sender: linux-block-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-block@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP This patch adds the re-write crc64 calculation routines for Linux kernel. The CRC64 polynomical arithmetic follows ECMA-182 specification, inspired by CRC paper of Dr. Ross N. Williams (see http://www.ross.net/crc/download/crc_v3.txt) and other public domain implementations. All the changes work in this way, - When Linux kernel is built, host program lib/gen_crc64table.c will be compiled to lib/gen_crc64table and executed. - The output of gen_crc64table execution is an array called as lookup table (a.k.a POLY 0x42f0e1eba9ea369) which contain 256 64bits-long numbers, this talbe is dumped into header file lib/crc64table.h. - Then the header file is included by lib/crc64.c for normal 64bit crc calculation. - Function declaration of the crc64 calculation routines is placed in include/linux/crc64.h Signed-off-by: Coly Li Reviewed-by: Hannes Reinecke Cc: Greg Kroah-Hartman Cc: Andy Shevchenko Cc: Michael Lyle Cc: Kent Overstreet Cc: Linus Torvalds Cc: Thomas Gleixner Cc: Kate Stewart --- include/linux/crc64.h | 15 +++++++++ lib/.gitignore | 2 ++ lib/Kconfig | 8 +++++ lib/Makefile | 11 +++++++ lib/crc64.c | 71 +++++++++++++++++++++++++++++++++++++++ lib/gen_crc64table.c | 77 +++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 184 insertions(+) create mode 100644 include/linux/crc64.h create mode 100644 lib/crc64.c create mode 100644 lib/gen_crc64table.c diff --git a/include/linux/crc64.h b/include/linux/crc64.h new file mode 100644 index 000000000000..cbd10a47d861 --- /dev/null +++ b/include/linux/crc64.h @@ -0,0 +1,15 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* + * crc64.h + * + * See lib/crc64.c for the related specification and polynomical arithmetic. + */ +#ifndef _LINUX_CRC64_H +#define _LINUX_CRC64_H + +#include + +__le64 crc64_le_update(__le64 crc, const void *_p, size_t len); +__le64 crc64_le(const void *p, size_t len); +__le64 crc64_le_bch(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..6341de4c7ab4 --- /dev/null +++ b/lib/crc64.c @@ -0,0 +1,71 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Normal 64bit 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_le[256] is the lookup table of a table-driver 64bit 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 + * + */ + +#include +#include +#include "crc64table.h" + +MODULE_DESCRIPTION("CRC64 calculations"); +MODULE_LICENSE("GPL"); + +__le64 crc64_le_update(__le64 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) ^ (__le64)(*p++)) & 0xFF; + crc = crc64table_le[t] ^ (crc << 8); + } + + return crc; +} +EXPORT_SYMBOL_GPL(crc64_le_update); + +__le64 crc64_le(const void *p, size_t len) +{ + __le64 crc = 0x0ULL; + + crc = crc64_le_update(crc, p, len); + + return crc; +} +EXPORT_SYMBOL_GPL(crc64_le); + +/* For checksum calculation in drivers/md/bcache/ */ +__le64 crc64_le_bch(const void *p, size_t len) +{ + __le64 crc = 0xFFFFFFFFFFFFFFFFULL; + + crc = crc64_le_update(crc, p, len); + + return (crc ^ 0xFFFFFFFFFFFFFFFFULL); +} +EXPORT_SYMBOL_GPL(crc64_le_bch); diff --git a/lib/gen_crc64table.c b/lib/gen_crc64table.c new file mode 100644 index 000000000000..5f292f287498 --- /dev/null +++ b/lib/gen_crc64table.c @@ -0,0 +1,77 @@ +// 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 + * + */ + +#include +#include +#include +#include "../usr/include/asm/byteorder.h" + +#define CRC64_ECMA182_POLY 0x42F0E1EBA9EA3693ULL + +#ifdef __LITTLE_ENDIAN +# define cpu_to_le64(x) ((__le64)(x)) +#else +# define cpu_to_le64(x) ((__le64)__swab64(x)) +#endif + +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_crc64le_table(void) +{ + int i; + + printf("/* this file is generated - do not edit */\n\n"); + printf("#include \n"); + printf("#include \n\n"); + printf("static const __le64 ____cacheline_aligned crc64table_le[256] = {\n"); + for (i = 0; i < 256; i++) { + printf("\t0x%016" PRIx64 "ULL", cpu_to_le64(crc64_table[i])); + if (i & 0x1) + printf(",\n"); + else + printf(", "); + } + printf("};\n"); +} + +int main(int argc, char *argv[]) +{ + generate_crc64_table(); + print_crc64le_table(); + return 0; +}