Fast CRC or hash

[bludin]

For a project that does file transfer over serial, I'm looking for a fast CRC or hash function. A pure python implementation of CRC16 with a pre-calculated table takes about 9-10ms for a 1 kB packet, which is rather slow. Do you see a way to speed this up significantly? Does Circuitpython offer faster built-in options (binascii is missing CPython's crc32 and crc_hqx funcs)? Apparently, the SAMD51 even has a built-in CRC engine. Could that be leveraged somehow?

Code: Select all

def make_crc_table():
    poly = 0x8408
    table = []
    for byte in range(256):
        crc = 0
        for bit in range(8):
            if (byte ^ crc) & 1:
                crc = (crc >> 1) ^ poly
            else:
                crc >>= 1
            byte >>= 1
        table.append(crc)
    return table

table = make_crc_table()

def crc_16_fast(msg):
    crc = 0xffff
    for byte in msg:
        crc = table[(byte ^ crc) & 0xff] ^ (crc >> 8)
    return crc ^ 0xffff

# Test

msg = bytearray(b'x' * 1024)
t0 = time.monotonic_ns()
n = 100
for _ in range(n):
    crc_16_fast(msg)

print((time.monotonic_ns()- t0) / n / 1e6, 'ms')

[danhalbert]

binascii.crc32() uses the crc32 implementation in zlib. We don't have zlib turned on, as it's fairly large, and not robust (I think that's part of the reason). However, the actual CRC calculation is only about 10 lines of code. So it would not be hard to add an independent implementation of crc32 to binascii.

`hash(a bytes object)` exists, but it is just the sum of the bytes.

I looked at whether aesio might be of any use to you, even though it's overkill, but the length restrictions don't seem to work out.

You could bring this up as an issue in the circuitpython repo. If you feel inclined, you could even submit a PR to add `binascii.crc32()`. There are older (closed) PR's and issues about zlib, but nothing is happening at the moment.

[bludin]

Thanks for your reply, I will bring this up on Github then.
BTW, hash() does more than just adding bytes, I believe:

Code: Select all

>>> hash(b'xy'); hash(b'yx')
4
36

But surprisingly, it's quite slow also, taking about 5ms for a 1kB-object.

[bludin]

...but interestingly:

Code: Select all

>>> hash(b'xy' * 512)
5
>>> hash(b'yx' * 512)
5
>>> hash(b'yy' * 512 + b'xx' * 512)
5
>>> hash(b'xx' * 512 + b'yy' * 512)
5
>>> hash(b'aa' * 512 + b'bb' * 512)
5

...