Due to high demand, expect some shipping delays at this time - orders may not ship for up to 2-3 business days.
0

Fast CRC or hash
Moderators: adafruit_support_bill, adafruit

Please be positive and constructive with your questions and comments.

Fast CRC or hash

by bludin on Tue Jan 25, 2022 6:33 am

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 | TOGGLE FULL SIZE
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')

bludin
 
Posts: 78
Joined: Thu Apr 16, 2020 8:57 am

Re: Fast CRC or hash

by danhalbert on Tue Jan 25, 2022 10:34 am

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.

danhalbert
 
Posts: 3179
Joined: Tue Aug 08, 2017 12:37 pm

Re: Fast CRC or hash

by bludin on Wed Jan 26, 2022 2:55 am

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 | TOGGLE FULL SIZE
>>> hash(b'xy'); hash(b'yx')
4
36
But surprisingly, it's quite slow also, taking about 5ms for a 1kB-object.

bludin
 
Posts: 78
Joined: Thu Apr 16, 2020 8:57 am

Re: Fast CRC or hash

by bludin on Wed Jan 26, 2022 3:04 am

...but interestingly:
Code: Select all | TOGGLE FULL SIZE
>>> 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
...

bludin
 
Posts: 78
Joined: Thu Apr 16, 2020 8:57 am

Please be positive and constructive with your questions and comments.