Re: [PATCH v4 1/3] lib: add crc64 calculation routines

[Eric Biggers <ebiggers3@gmail.com>]

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