diff mbox series

[PATCHv4,5/8] lib: add rocksoft model crc64

Message ID 20220303201312.3255347-6-kbusch@kernel.org
State Accepted
Commit cbc0a40e17da361a2ada8d669413ccfbd2028f2d
Headers show
Series 64-bit data integrity field support | expand

Commit Message

Keith Busch March 3, 2022, 8:13 p.m. UTC
The NVM Express specification extended data integrity fields to 64 bits
using the Rocksoft parameters. Add the poly to the crc64 table
generation, and provide a generic library routine implementing the
algorithm.

The Rocksoft 64-bit CRC model parameters are as follows:
    Poly: 0xAD93D23594C93659
    Initial value: 0xFFFFFFFFFFFFFFFF
    Reflected Input: True
    Reflected Output: True
    Xor Final: 0xFFFFFFFFFFFFFFFF

Since this model used reflected bits, the implementation generates the
reflected table so the result is ordered consistently.

Cc: Christoph Hellwig <hch@lst.de>
Cc: Hannes Reinecke <hare@suse.de>
Cc: Martin K. Petersen <martin.petersen@oracle.com>
Signed-off-by: Keith Busch <kbusch@kernel.org>
---
v3->v4:

  Require the caller to provide 0 for the initial value. This means the
  calculation is responsible to invert it now, and makes updating the
  crc in multiple chunks easier.

 include/linux/crc64.h |  2 ++
 lib/crc64.c           | 28 ++++++++++++++++++++++++
 lib/gen_crc64table.c  | 51 +++++++++++++++++++++++++++++++++----------
 3 files changed, 70 insertions(+), 11 deletions(-)

Comments

Martin K. Petersen March 4, 2022, 2:41 a.m. UTC | #1
Keith,

> The NVM Express specification extended data integrity fields to 64
> bits using the Rocksoft parameters. Add the poly to the crc64 table
> generation, and provide a generic library routine implementing the
> algorithm.

Reviewed-by: Martin K. Petersen <martin.petersen@oracle.com>
David Laight March 4, 2022, 7:53 a.m. UTC | #2
From: Keith Busch
> Sent: 03 March 2022 20:13
> 
> The NVM Express specification extended data integrity fields to 64 bits
> using the Rocksoft parameters. Add the poly to the crc64 table
> generation, and provide a generic library routine implementing the
> algorithm.
> 
> The Rocksoft 64-bit CRC model parameters are as follows:
>     Poly: 0xAD93D23594C93659
>     Initial value: 0xFFFFFFFFFFFFFFFF
>     Reflected Input: True
>     Reflected Output: True
>     Xor Final: 0xFFFFFFFFFFFFFFFF
> 
> Since this model used reflected bits, the implementation generates the
> reflected table so the result is ordered consistently.

Since the data is processed least significant bit first the
table must be setup slightly differently.

...
> + * crc64rocksoft[256] table is from the Rocksoft specification polynomial
> + * defined as,
> + *
> + * x^64 + x^63 + x^61 + x^59 + x^58 + x^56 + x^55 + x^52 + x^49 + x^48 + x^47 +
> + * x^46 + x^44 + x^41 + x^37 + x^36 + x^34 + x^32 + x^31 + x^28 + x^26 + x^23 +
> + * x^22 + x^19 + x^16 + x^13 + x^12 + x^10 + x^9 + x^6 + x^4 + x^3 + 1

Which matches the Poly: 0xAD93D23594C93659 above.

...
> +#define CRC64_ROCKSOFT_POLY 0x9A6C9329AC4BC9B5ULL

But that value is clearly different.

You really ought to add a comment that each byte of the constant
has to be bit reversed from the polynomial coefficients.

> -static void generate_crc64_table(void)
> +static void generate_reflected_crc64_table(uint64_t table[256], uint64_t poly)
> +{
> +	uint64_t i, j, c, crc;
> +
> +	for (i = 0; i < 256; i++) {
> +		crc = 0ULL;
> +		c = i;
> +
> +		for (j = 0; j < 8; j++) {
> +			if ((crc ^ (c >> j)) & 1)
> +				crc = (crc >> 1) ^ poly;
> +			else
> +				crc >>= 1;
> +		}
> +		table[i] = crc;
> +	}
> +}

That can be speeded up by using the identity:
	table[x ^ y] == table[x] ^ table[y]

something like:
	crc = poly;  /* actually crc(1) */
	table[0] = 0;
	table[1] = crc;
	for (i = 2; i < 8; i++) [
		crc = crc & 1 ? (crc >> 1) ^ poly : crc >> 1;
		for (j = 0; j < 1u << i; j++)
			table[j + (1i << i)] = table[j] ^ crc;
	}

I think the same code can be used for a normal MSB first crc
provided both the polynomial and crc(1) are passed in.

OTOH initialisation speed may not matter.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
Keith Busch March 4, 2022, 3:02 p.m. UTC | #3
On Fri, Mar 04, 2022 at 07:53:44AM +0000, David Laight wrote:
> 
> That can be speeded up by using the identity:
> 	table[x ^ y] == table[x] ^ table[y]
> 
> something like:
> 	crc = poly;  /* actually crc(1) */
> 	table[0] = 0;
> 	table[1] = crc;
> 	for (i = 2; i < 8; i++) [
> 		crc = crc & 1 ? (crc >> 1) ^ poly : crc >> 1;
> 		for (j = 0; j < 1u << i; j++)
> 			table[j + (1i << i)] = table[j] ^ crc;
> 	}
> 
> I think the same code can be used for a normal MSB first crc
> provided both the polynomial and crc(1) are passed in.
> 
> OTOH initialisation speed may not matter.

I don't think speed is an issue here. This part is executed just once
for the initial kernel compile, then never again.
diff mbox series

Patch

diff --git a/include/linux/crc64.h b/include/linux/crc64.h
index c756e65a1b58..9480f38cc7cf 100644
--- a/include/linux/crc64.h
+++ b/include/linux/crc64.h
@@ -8,4 +8,6 @@ 
 #include <linux/types.h>
 
 u64 __pure crc64_be(u64 crc, const void *p, size_t len);
+u64 __pure crc64_rocksoft_generic(u64 crc, const void *p, size_t len);
+
 #endif /* _LINUX_CRC64_H */
diff --git a/lib/crc64.c b/lib/crc64.c
index 9f852a89ee2a..61ae8dfb6a1c 100644
--- a/lib/crc64.c
+++ b/lib/crc64.c
@@ -22,6 +22,13 @@ 
  * 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
  *
+ * crc64rocksoft[256] table is from the Rocksoft specification polynomial
+ * defined as,
+ *
+ * x^64 + x^63 + x^61 + x^59 + x^58 + x^56 + x^55 + x^52 + x^49 + x^48 + x^47 +
+ * x^46 + x^44 + x^41 + x^37 + x^36 + x^34 + x^32 + x^31 + x^28 + x^26 + x^23 +
+ * x^22 + x^19 + x^16 + x^13 + x^12 + x^10 + x^9 + x^6 + x^4 + x^3 + 1
+ *
  * Copyright 2018 SUSE Linux.
  *   Author: Coly Li <colyli@suse.de>
  */
@@ -55,3 +62,24 @@  u64 __pure crc64_be(u64 crc, const void *p, size_t len)
 	return crc;
 }
 EXPORT_SYMBOL_GPL(crc64_be);
+
+/**
+ * crc64_rocksoft_generic - Calculate bitwise Rocksoft CRC64
+ * @crc: seed value for computation. 0 for a new CRC calculation, 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_rocksoft_generic(u64 crc, const void *p, size_t len)
+{
+	const unsigned char *_p = p;
+	size_t i;
+
+	crc = ~crc;
+
+	for (i = 0; i < len; i++)
+		crc = (crc >> 8) ^ crc64rocksofttable[(crc & 0xff) ^ *_p++];
+
+	return ~crc;
+}
+EXPORT_SYMBOL_GPL(crc64_rocksoft_generic);
diff --git a/lib/gen_crc64table.c b/lib/gen_crc64table.c
index 094b43aef8db..55e222acd0b8 100644
--- a/lib/gen_crc64table.c
+++ b/lib/gen_crc64table.c
@@ -17,10 +17,30 @@ 
 #include <stdio.h>
 
 #define CRC64_ECMA182_POLY 0x42F0E1EBA9EA3693ULL
+#define CRC64_ROCKSOFT_POLY 0x9A6C9329AC4BC9B5ULL
 
 static uint64_t crc64_table[256] = {0};
+static uint64_t crc64_rocksoft_table[256] = {0};
 
-static void generate_crc64_table(void)
+static void generate_reflected_crc64_table(uint64_t table[256], uint64_t poly)
+{
+	uint64_t i, j, c, crc;
+
+	for (i = 0; i < 256; i++) {
+		crc = 0ULL;
+		c = i;
+
+		for (j = 0; j < 8; j++) {
+			if ((crc ^ (c >> j)) & 1)
+				crc = (crc >> 1) ^ poly;
+			else
+				crc >>= 1;
+		}
+		table[i] = crc;
+	}
+}
+
+static void generate_crc64_table(uint64_t table[256], uint64_t poly)
 {
 	uint64_t i, j, c, crc;
 
@@ -30,26 +50,22 @@  static void generate_crc64_table(void)
 
 		for (j = 0; j < 8; j++) {
 			if ((crc ^ c) & 0x8000000000000000ULL)
-				crc = (crc << 1) ^ CRC64_ECMA182_POLY;
+				crc = (crc << 1) ^ poly;
 			else
 				crc <<= 1;
 			c <<= 1;
 		}
 
-		crc64_table[i] = crc;
+		table[i] = crc;
 	}
 }
 
-static void print_crc64_table(void)
+static void output_table(uint64_t table[256])
 {
 	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]);
+		printf("\t0x%016" PRIx64 "ULL", table[i]);
 		if (i & 0x1)
 			printf(",\n");
 		else
@@ -58,9 +74,22 @@  static void print_crc64_table(void)
 	printf("};\n");
 }
 
+static void print_crc64_tables(void)
+{
+	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");
+	output_table(crc64_table);
+
+	printf("\nstatic const u64 ____cacheline_aligned crc64rocksofttable[256] = {\n");
+	output_table(crc64_rocksoft_table);
+}
+
 int main(int argc, char *argv[])
 {
-	generate_crc64_table();
-	print_crc64_table();
+	generate_crc64_table(crc64_table, CRC64_ECMA182_POLY);
+	generate_reflected_crc64_table(crc64_rocksoft_table, CRC64_ROCKSOFT_POLY);
+	print_crc64_tables();
 	return 0;
 }