CRC32-Berechnung in Python ohne Verwendung von Bibliotheken

Question

Ich habe versucht, den Kopf über CRC32-Berechnungen ohne viel Erfolg zu bekommen, die Werte, die ich zu bekommen scheinen, stimmen nicht überein, was ich bekommen sollte.

Ich bin mir bewusst, dass Python Bibliotheken, die in der Lage, diese Prüfsummen (zlib und binascii) erzeugen kann, aber ich habe nicht den Luxus, sie zu verwenden, da die CRC-Funktionalität nicht auf dem Micropython existieren.

Bisher habe ich den folgenden Code:

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)) 

Dann bekomme ich die folgende Ausgabe:

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

Die binascii und zlib Berechnungen stimmen, wo, wie mein man nicht tut. Ich glaube, die berechnete Byte-Tabelle ist korrekt, da ich sie mit im Netz verfügbaren Beispielen verglichen habe. Das Problem muss also die Routine sein, in der jedes Byte berechnet wird. Kann mir jemand in die richtige Richtung zeigen?

Vielen Dank im Voraus!

Answer 1

Ich habe nicht genau an Ihrem Code sehe, so kann ich die genaue Ursache des Fehlers nicht ermitteln, aber man kann es leicht zwicken die gewünschte Ausgabe zu erhalten:

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 

Ausgang

'' 
00000000 
00000000 

'test' 
d87f7e0c 
d87f7e0c 

'hello world' 
0d4a1185 
0d4a1185 

'1234' 
9be3e0a3 
9be3e0a3 

'A long string to test CRC32 functions' 
d2d10e28 
d2d10e28 

---

Hier sind noch ein paar Tests, die die gezwickt crc32 das gleiche Ergebnis wie binascii.crc32 gibt überprüfen, ob.

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') 

Ausgang

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 

---

Wie in den Kommentaren diskutiert wird, die Quelle des Fehlers im ursprünglichen Code ist, dass dieser CRC-32-Algorithmus, um die anfänglichen crc Puffer invertiert und dann invertiert den endgültigen Pufferinhalt. So wird value zu 0xffffffff anstelle von Null initialisiert, und wir müssen value^0xffffffff zurückgeben, das auch als ~value & 0xffffffff geschrieben werden kann, d. H. Invertieren value und dann die niedrigwertigen 32 Bits des Ergebnisses auswählen.