From: Coly Li <colyli@suse.de>
To: Eric Biggers <ebiggers3@gmail.com>
Cc: linux-kernel@vger.kernel.org, linux-bcache@vger.kernel.org,
linux-block@vger.kernel.org,
Andy Shevchenko <andriy.shevchenko@linux.intel.com>,
Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
Michael Lyle <mlyle@lyle.org>,
Kent Overstreet <kent.overstreet@gmail.com>,
Linus Torvalds <torvalds@linux-foundation.org>,
Thomas Gleixner <tglx@linutronix.de>,
Kate Stewart <kstewart@linuxfoundation.org>,
Andrew Morton <akpm@linux-foundation.org>,
Randy Dunlap <rdunlap@infradead.org>
Subject: Re: [PATCH v4 1/3] lib: add crc64 calculation routines
Date: Wed, 25 Jul 2018 00:29:24 +0800 [thread overview]
Message-ID: <dd95ab25-562e-1318-19e9-c8163969252f@suse.de> (raw)
In-Reply-To: <20180724042637.GA1944@sol.localdomain>
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
>
next prev parent reply other threads:[~2018-07-24 16:29 UTC|newest]
Thread overview: 15+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-07-18 16:55 [PATCH v4 0/3] add crc64 calculation as kernel library Coly Li
2018-07-18 16:55 ` [PATCH v4 1/3] lib: add crc64 calculation routines Coly Li
2018-07-24 4:26 ` Eric Biggers
2018-07-24 16:29 ` Coly Li [this message]
2018-07-24 17:06 ` Andy Shevchenko
2018-07-25 2:37 ` Coly Li
2018-07-25 21:22 ` Andrew Morton
2018-07-26 3:28 ` Coly Li
2018-07-18 16:55 ` [PATCH v4 2/3] bcache: use routines from lib/crc64.c for CRC64 calculation Coly Li
2018-07-18 16:55 ` [PATCH v4 3/3] lib/test_crc: Add test cases for crc calculation Coly Li
2018-07-18 21:24 ` Andrew Morton
2018-07-24 4:44 ` Eric Biggers
2018-07-24 16:28 ` Coly Li
2018-07-24 17:39 ` Eric Biggers
2018-07-25 4:07 ` Coly Li
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=dd95ab25-562e-1318-19e9-c8163969252f@suse.de \
--to=colyli@suse.de \
--cc=akpm@linux-foundation.org \
--cc=andriy.shevchenko@linux.intel.com \
--cc=ebiggers3@gmail.com \
--cc=gregkh@linuxfoundation.org \
--cc=kent.overstreet@gmail.com \
--cc=kstewart@linuxfoundation.org \
--cc=linux-bcache@vger.kernel.org \
--cc=linux-block@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mlyle@lyle.org \
--cc=rdunlap@infradead.org \
--cc=tglx@linutronix.de \
--cc=torvalds@linux-foundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).