Algorithme CRC32 rapide pour l'ordre de bits inversé

Question

Je travaille avec un microcontrôleur qui calcule la somme de contrôle CRC32 des données que je télécharge dans sa mémoire flash à la volée. Cela peut ensuite être utilisé pour vérifier que le téléchargement était correct, en vérifiant la somme de contrôle résultante une fois toutes les données téléchargées.

Le seul problème est que le microcontrôleur inverse l'ordre des bits des octets d'entrée lorsqu'ils sont exécutés à travers le calcul crc32 standard. Cela signifie que je dois inverser chaque octet des données sur l'hôte de programmation afin de calculer la somme CRC32 pour vérification. Comme l'hôte de programmation est quelque peu restreint, cela prend beaucoup de temps.

Je pense que s'il est possible de modifier la table de recherche CRC32 pour pouvoir faire la recherche sans avoir à inverser l'ordre des bits, l'algorithme de vérification s'exécuterait beaucoup plus rapidement. Mais je semble incapable de trouver un moyen d'y parvenir.

Pour clarifier l'inversion des octets, je dois modifier les octets d'entrée comme suit:

01 02 03 04 -> 80 40 C0 20

Il est beaucoup plus facile de voir l'inversion dans la représentation binaire bien sûr:

00000001 00000010 00000011 00000100 -> 10000000 01000000 11000000 00100000

Modifier Voici le code Python PoC que j'utilise pour vérifier la précision du calcul CRC32, cependant cela inverse chaque octet (c'est-à-dire la méthode lente).

EDIT2 J'ai également inclus ma tentative échouée de générer une table de recherche permutée et d'utiliser un algorithme standard de LUT CRC32.

Le code affiche d'abord la valeur CRC de référence correcte, puis le CRC calculé incorrectement par la table de recherche.

import binascii

CRC32_POLY = 0xEDB88320

def reverse_byte_bits(x):
    '''
    Inverse l'ordre des bits de l'octet donné 'x' et renvoie le résultat
    '''
    x = ((x<<4) & 0xF0)|((x>>4) & 0x0F)
    x = ((x<<2) & 0xCC)|((x>>2) & 0x33)
    x = ((x<<1) & 0xAA)|((x>>1) & 0x55)
    return x

def reverse_bits(ba, blen):
    '''
    Inverse tous les octets dans le tableau donné d'octets
    '''
    bar = bytearray()
    for i in range(0, blen):
        bar.append(reverse_byte_bits(ba[i]))
    return bar

def crc32_reverse(ba):
    # Inverser tous les bits dans le tableau
    bar = reverse_bits(ba, len(ba))

    # Calcul de la valeur CRC
    return binascii.crc32(bar)

def gen_crc_table_msb():
    crctable = [0] * 256

    for i in range(0, 256):
        remainder = i
        for bit in range(0, 8):
            if remainder & 0x1:
                remainder = (remainder >> 1) ^ CRC32_POLY
            else:
                remainder = (remainder >> 1)

        # L'index correct pour la valeur calculée est l'inverse de l'index
        ix = reverse_byte_bits(i)
        crctable[ix] = remainder

    return crctable

def crc32_revlut(ba, lut):
    crc = 0xFFFFFFFF
    for x in ba:
        crc = lut[x ^ (crc & 0xFF)] ^ (crc >> 8)
    return ~crc

# Test de référence qui donne le CRC correct
test = bytearray([1, 2, 3, 4, 5, 6, 7, 8])
crcrev = crc32_reverse(test)
print("0x%08X" % (crcrev & 0xFFFFFFFF))

# Test en utilisant une table de recherche permutée, mais l'algorithme standard LUT CRC32
lut = gen_crc_table_msb()
crctst = crc32_revlut(test, lut)
print("0x%08X" % (crctst & 0xFFFFFFFF))

Quelqu'un a-t-il des astuces pour savoir comment cela pourrait être fait?

Answer 1

En inversant la logique du sens dans lequel le crc "coule", on peut éviter l'inversion dans le calcul principal. Ainsi, au lieu de crc >> 8, il y aurait crc << 8 et au lieu de faire un XOR avec le dernier octet du crc pour l'index de la LUT, nous prenons le premier. Comme ceci :

def reverse_dword_bits(x):
    '''
    Inverse l'ordre des bits du dword donné 'x' et renvoie le résultat
    '''
    x = ((x<<16) & 0xFFFF0000)|((x>>16) & 0x0000FFFF)
    x = ((x<<8) & 0xFF00FF00)|((x>>8) & 0x00FF00FF)
    x = ((x<<4) & 0xF0F0F0F0)|((x>>4) & 0x0F0F0F0F)
    x = ((x<<2) & 0xCCCCCCCC)|((x>>2) & 0x33333333)
    x = ((x<<1) & 0xAAAAAAAA)|((x>>1) & 0x55555555)
    return x

def gen_crc_table_msb():
    crctable = [0] * 256

    for i in range(0, 256):
        remainder = i
        for bit in range(0, 8):
            if remainder & 0x1:
                remainder = (remainder >> 1) ^ CRC32_POLY
            else:
                remainder = (remainder >> 1)

        # L'index correct pour la valeur calculée est l'inverse de l'index
        ix = reverse_byte_bits(i)
        crctable[ix] = reverse_dword_bits(remainder)

    return crctable

def crc32_revlut(ba, lut):
    crc = 0xFFFFFFFF
    for x in ba:
        crc = lut[x ^ (crc >> 24)] ^ ((crc << 8) & 0xFFFFFFFF)
    return reverse_dword_bits(~crc)