5
\$\begingroup\$

I have code to calculate STM CRC32 in python. It works well but I'm shocked from time when I see how much it takes. Namely calculating for 5120 bytes takes about 20ms (or even more)! Now I'm thinking this code is weak or it is just python ?

Code :

custom_crc_table = {}
poly = 0x04C11DB7

def generate_crc32_table(_poly):

    global custom_crc_table

    for i in range(256):
        c = i << 24

        for j in range(8):
            c = (c << 1) ^ _poly if (c & 0x80000000) else c << 1

        custom_crc_table[i] = c & 0xffffffff

def crc32_stm(bytes_arr):

    length = len(bytes_arr)
    crc = 0xffffffff

    k = 0
    while length >= 4:

        v = ((bytes_arr[k] << 24) & 0xFF000000) | ((bytes_arr[k+1] << 16) & 0xFF0000) | \
        ((bytes_arr[k+2] << 8) & 0xFF00) | (bytes_arr[k+3] & 0xFF)

        crc = ((crc << 8) & 0xffffffff) ^ custom_crc_table[0xFF & ((crc >> 24) ^ v)]
        crc = ((crc << 8) & 0xffffffff) ^ custom_crc_table[0xFF & ((crc >> 24) ^ (v >> 8))]
        crc = ((crc << 8) & 0xffffffff) ^ custom_crc_table[0xFF & ((crc >> 24) ^ (v >> 16))]
        crc = ((crc << 8) & 0xffffffff) ^ custom_crc_table[0xFF & ((crc >> 24) ^ (v >> 24))]

        k += 4
        length -= 4

    if length > 0:
        v = 0

        for i in range(length):
            v |= (bytes_arr[k+i] << 24-i*8)

        if length == 1:
            v &= 0xFF000000

        elif length == 2:
            v &= 0xFFFF0000

        elif length == 3:
            v &= 0xFFFFFF00

        crc = (( crc << 8 ) & 0xffffffff) ^ custom_crc_table[0xFF & ( (crc >> 24) ^ (v ) )]
        crc = (( crc << 8 ) & 0xffffffff) ^ custom_crc_table[0xFF & ( (crc >> 24) ^ (v >> 8) )]
        crc = (( crc << 8 ) & 0xffffffff) ^ custom_crc_table[0xFF & ( (crc >> 24) ^ (v >> 16) )]
        crc = (( crc << 8 ) & 0xffffffff) ^ custom_crc_table[0xFF & ( (crc >> 24) ^ (v >> 24) )]


    return crc
\$\endgroup\$
4
  • \$\begingroup\$ Which Python interpreter are you using? CPython? JPython? IronPython? \$\endgroup\$
    – Snowbody
    Commented Sep 19, 2017 at 6:35
  • \$\begingroup\$ @Snowbody CPython \$\endgroup\$
    – KyluAce
    Commented Sep 19, 2017 at 7:31
  • \$\begingroup\$ Have you done any code speed profiling? The bitwise operations are the most suspicious in my book. If that's the case, look into an external lib like this question stackoverflow.com/questions/27593999/… \$\endgroup\$
    – Snowbody
    Commented Sep 19, 2017 at 13:02
  • 1
    \$\begingroup\$ Not sure why you are using python on an ARM-M series microcontroller and worrying about performance. Also, most STM32s have hardware acceleration support of CRC which should take around 20 microseconds to process your data even at the slowest clock speed. \$\endgroup\$ Commented Feb 4 at 13:48

2 Answers 2

1
\$\begingroup\$

Accumulating impressions/insights. Not a full review:

  • Shifting right instead of left saves a mask operation here&there and avoids numbers getting longer
  • Assembling v only to use each original part masked off looks pointless and obfuscating.
    CRC computation processes the bytes in order k+3, k+2, k+1, k+0?!
    I don't find that in the manufacturers Application note AN4187 on the STM32 CRC peripheral, nor a mention of ARM's selectable endianness.
  • It seems to be possible to "do the EX-OR" unconditionally, by (4-byte) word.
\$\endgroup\$
1
\$\begingroup\$

word at a time

There's no need to painstakingly assemble the value v from its four constituent bytes. We have arrays to do that for us.

from array import array


def crc32_stm(bytes_arr: bytes) -> int:
    length = len(bytes_arr)
    crc = 0xFFFF_FFFF

    a = array("I", bytes_arr[: length - length % 4])
    if sys.byteorder == "little":
        a.byteswap()

    for v in a:
        crc = ...
        crc = ...
        crc = ...
        crc = ...

    k = 4 * len(a)
    length -= k

Iterating over 32-bit values in that way shaves off about a quarter of the runtime, when hashing "big" input buffers of OP's suggested 5120 bytes.

Also, using cPython 3.11.7 seems to go about 9x faster than the interpreter OP was using: 2.2 msec vs 20 msec for a big buffer, using original OP code.

Apparently dicts have been optimized to within an inch of their life. The CRC table is of dict[int, int]. When I converted that to an integer array there was no noticeable timing change.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.