On 2018/7/17 3:34 PM, Coly Li wrote:

On 2018/7/17 3:13 PM, Eric Biggers wrote:

quoted

On Tue, Jul 17, 2018 at 02:25:24PM +0800, Coly Li wrote:

quoted

On 2018/7/17 11:34 AM, Eric Biggers wrote:

quoted

Hi Coly,

On Tue, Jul 17, 2018 at 12:55:05AM +0800, Coly Li wrote:

quoted

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

[...]

quoted

diff --git a/lib/crc64.c b/lib/crc64.c
new file mode 100644
index 000000000000..03f078303bd3
--- /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 <colyli@suse.de>
+ *
+ */
+
+#include <linux/module.h>
+#include <uapi/linux/types.h>
+#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 = 0x0000000000000000ULL;
+
+	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);

[snipped]

quoted

quoted

I see your point here. I am not expert in coding theory, the knowledge I
have is from wikipedia, ECMA-182 and the document from Dr. Ross
Williams. From ECMA-182 document, I don't see any word with 'big
endian', so I take it as a standard poly and regardless the byte order.

And on wikepedia page
https://en.wikipedia.org/wiki/Cyclic_redundancy_check , CRC-64-ECMA
references the same poly and call "0x42F0E1EBA9EA3693" as normal poly,
which one links to polynomial
	"x^64 + x^62 + x^57 + x^55 + x^54 + ....x^7 + x^4 + x + 1"
if I understand correctly. But from your information, it seems the
polynomial in generate_crc64_table() is x^64 + x^61 ..... Maybe I
misunderstand you, could you please give me more hint ?

As I said, the "normal" convention is the same as "big endian", and the
"reversed" convention is the same as "little endian" (again, meaning "bitwise"
endianness, not the usual "bytewise" endianness).  The polynomial is correct but
you are claiming the polynomial coefficients are mapped to bits in a different
order than they actually are.

In v3 series, I remove _le and __le64 from the patch, that means the
calculation is not explicit resitricted to little endian, and the caller
should make sure the data in a proper byte order. The result is, there
is no misleading naming issue. Since so far the only user is bcache, and
potential user is bcachefs, the developers should know how to use
crc64_update() and crc64_bch() properly.

So now the routines are named as crc64(), crc64_update(), crc64_bch(),
and return value is u64.

I hope now the misleading can be avoided.

Thanks.

Coly Li