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

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(-)

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>

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)

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.