| Message ID | 20220303201312.3255347-6-kbusch@kernel.org (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | 64-bit data integrity field support | expand |
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.
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; }
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(-)