Calcul CRC32 en Python sans utiliser les bibliothèques

Question

J'ai essayé de comprendre les calculs de CRC32 sans grand succès, les valeurs que je semble obtenir ne correspondent pas à ce que je devrais obtenir. Je suis conscient que Python a des bibliothèques capables de générer ces checksums (à savoir zlib et binascii) mais je n'ai pas le luxe de pouvoir les utiliser car la fonctionnalité CRC n'existe pas sur le micropython.

Jusqu'à présent, j'ai le code suivant:

import binascii 
import zlib 
from array import array 

poly = 0xEDB88320 

table = array('L') 
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) 

def crc32(string): 
    value = 0xffffffffL 

    for ch in string: 
     value = table[(ord(ch)^value) & 0x000000ffL]^(value >> 8) 

    return value 

teststring = "test" 

print "binascii calc: 0x%08x" % (binascii.crc32(teststring) & 0xffffffff) 
print "zlib calc:  0x%08x" % (zlib.crc32(teststring) & 0xffffffff) 
print "my calc:  0x%08x" % (crc32(teststring)) 

Puis-je obtenir la sortie suivante:

binascii calc: 0xd87f7e0c 
zlib calc:  0xd87f7e0c 
my calc:  0x2780810c 

Les calculs de binascii et zlib d'accord alors que mon seul ne fonctionne pas. Je crois que la table calculée des octets est correcte car je l'ai comparée aux exemples disponibles sur le net. Donc le problème doit être la routine où chaque octet est calculé, est-ce que quelqu'un pourrait me pointer dans la bonne direction?

Merci d'avance!

Answer 1

Je ne l'ai pas regardé attentivement votre code, donc je ne peux pas identifier la source exacte de l'erreur, mais vous pouvez facilement modifier pour obtenir la sortie désirée:

import binascii 
from array import array 

poly = 0xEDB88320 

table = array('L') 
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) 

def crc32(string): 
    value = 0xffffffffL 
    for ch in string: 
     value = table[(ord(ch)^value) & 0xff]^(value >> 8) 

    return -1 - value 

# test 

data = (
    '', 
    'test', 
    'hello world', 
    '1234', 
    'A long string to test CRC32 functions', 
) 

for s in data: 
    print repr(s) 
    a = binascii.crc32(s) 
    print '%08x' % (a & 0xffffffffL) 
    b = crc32(s) 
    print '%08x' % (b & 0xffffffffL) 
    print 

sortie

'' 
00000000 
00000000 

'test' 
d87f7e0c 
d87f7e0c 

'hello world' 
0d4a1185 
0d4a1185 

'1234' 
9be3e0a3 
9be3e0a3 

'A long string to test CRC32 functions' 
d2d10e28 
d2d10e28 

---

Voici quelques autres tests qui permettent de vérifier que le crc32 peaufiné donne le même résultat que binascii.crc32.

from random import seed, randrange 

print 'Single byte tests...', 
for i in range(256): 
     s = chr(i) 
     a = binascii.crc32(s) & 0xffffffffL 
     b = crc32(s) & 0xffffffffL 
     assert a == b, (repr(s), a, b) 

print('ok') 

seed(42) 

print 'Multi-byte tests...' 
for width in range(2, 20): 
    print 'Width', width 
    r = range(width) 
    for n in range(1000): 
     s = ''.join([chr(randrange(256)) for i in r]) 
     a = binascii.crc32(s) & 0xffffffffL 
     b = crc32(s) & 0xffffffffL 
     assert a == b, (repr(s), a, b) 
print('ok') 

sortie

Single byte tests... ok 
Multi-byte tests... 
Width 2 
Width 3 
Width 4 
Width 5 
Width 6 
Width 7 
Width 8 
Width 9 
Width 10 
Width 11 
Width 12 
Width 13 
Width 14 
Width 15 
Width 16 
Width 17 
Width 18 
Width 19 
ok 

---

Comme indiqué dans les commentaires, la source de l'erreur dans le code original est que cet algorithme CRC-32 inverse le tampon crc initiale, puis Inverse le contenu final du tampon. Donc value est initialisé à 0xffffffff au lieu de zéro, et nous devons retourner value^0xffffffff, qui peut également être écrit comme ~value & 0xffffffff, c'est-à-dire inverser value, puis sélectionner les 32 bits de poids faible du résultat.