Re: [RFC 3/7] lib: add rocksoft model crc64

[Eric Biggers]

On Mon, Jan 24, 2022 at 08:01:03AM -0800, Keith Busch wrote:
> Since this model reflects inputs and outputs, a helper table and
> function are added to reverse bits of 8 and 64 bit values.

That's a silly way to do a bit-reflected CRC.  The proper way to do it is to
reflect the bytes too, so that the bits and bytes are ordered consistently, so
explicitly reflecting the bits isn't needed.  Most CRC-32's are bit-reflected,
and they are usually implemented this way.  E.g., see crc32_le() in lib/crc32.c.

Here's a Python script that shows that the Rocksoft CRC-64 can be computed
without explicitly reversing the bits.  It passes the tests from your patch 4:


COEFFS = [63, 61, 59, 58, 56, 55, 52, 49, 48, 47, 46, 44, 41, 37, 36, 34, 32,
          31, 28, 26, 23, 22, 19, 16, 13, 12, 10, 9, 6, 4, 3, 0]
POLY = sum(1 << (63 - coeff) for coeff in COEFFS)

# Generate the table.
table = [0] * 256
for i in range(256):
    crc = 0
    byte = i
    for j in range(8):
        if ((crc ^ (byte >> j)) & 1) == 1:
            crc = (crc >> 1) ^ POLY
        else:
            crc = crc >> 1
    table[i] = crc

# Compute the CRC-64 one byte at a time using the table.
def crc64_rocksoft(data):
    crc = 0xffffffffffffffff
    for byte in data:
        crc = (crc >> 8) ^ table[(crc & 0xff) ^ byte]
    return crc ^ 0xffffffffffffffff

# Tests
assert crc64_rocksoft(bytearray([0] * 4096)) == 0x6482D367EB22B64E
assert crc64_rocksoft(bytearray([255] * 4096)) == 0xC0DDBA7302ECA3AC
assert crc64_rocksoft(bytearray([i % 256 for i in range(4096)])) == 0x3E729F5F6750449C
assert crc64_rocksoft(bytearray([(255-i) % 256 for i in range(4096)])) == 0x9A2DF64B8E9E517E

# Print the table.
print(f'#define CRC64_ROCKSOFT_POLY 0x{POLY:016x}ULL')
print('')
print('static const u64 crc64_rocksoft_tab[] = {')
for i in range(0, 256, 2):
    print('\t', end='')
    for j in range(i, i + 2):
        print(f'0x{table[j]:016x}ULL,', end='')
        if j != 1:
            print(' ', end='')
    print('')
print('};')