linux-kernel - RE: [PATCHv4 5/8] lib: add rocksoft model crc64

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <30e059eca211460780442e2ded092722@AcuMS.aculab.com>
Date:   Fri, 4 Mar 2022 07:53:44 +0000
From:   David Laight <David.Laight@...LAB.COM>
To:     'Keith Busch' <kbusch@...nel.org>,
        "linux-nvme@...ts.infradead.org" <linux-nvme@...ts.infradead.org>,
        "linux-block@...r.kernel.org" <linux-block@...r.kernel.org>,
        "linux-crypto@...r.kernel.org" <linux-crypto@...r.kernel.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>
CC:     "axboe@...nel.dk" <axboe@...nel.dk>, "hch@....de" <hch@....de>,
        "martin.petersen@...cle.com" <martin.petersen@...cle.com>,
        Hannes Reinecke <hare@...e.de>
Subject: RE: [PATCHv4 5/8] lib: add rocksoft model crc64

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)