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)
