Messages in this thread | | | From | David Laight <> | Subject | RE: [PATCHv4 5/8] lib: add rocksoft model crc64 | Date | Fri, 4 Mar 2022 07:53:44 +0000 |
| |
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)
| |