RE: [PATCH v3 1/3] lib: add crc64 calculation routines

[David Laight]

From: Coly Li
> Sent: 17 July 2018 15:55
> 
> This patch adds the re-write crc64 calculation routines for Linux kernel.
> The CRC64 polynomical arithmetic follows ECMA-182 specification, inspired
> by CRC paper of Dr. Ross N. Williams
> (see http://www.ross.net/crc/download/crc_v3.txt) and other public domain
> implementations.
> 
> All the changes work in this way,
> - When Linux kernel is built, host program lib/gen_crc64table.c will be
>   compiled to lib/gen_crc64table and executed.

That seems excessive for a fixed table.
No real point doing more than putting a commented out copy of the code
with the initialisation data.

> - The output of gen_crc64table execution is an array called as lookup
>   table (a.k.a POLY 0x42f0e1eba9ea369) which contain 256 64bits-long
>   numbers, this talbe is dumped into header file lib/crc64table.h.
> - Then the header file is included by lib/crc64.c for normal 64bit crc
>   calculation.

How long are the buffers being processed?
For short buffers a lot of bytes will suffer cache line misses.
For longer buffers you'll be displacing 2k of data from the L1 data cache.
That could easily have a knock on effect on the surrounding code.

You might find that a nibble based loop and lookup table is faster.
Or, relying on the linearity of CRCs, separate lookup tables
for the high and low nibbles of each byte.

So replacing:
		crc = crc64table[t] ^ (crc << 8);
with:
		crc = crc64table_hi[t >> 4] ^ crc64table_lo[t & 15] ^ (crc << 8);

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)