Python'da kütüphaneleri kullanmadan CRC32 hesaplaması

Question

Kafamdaki CRC32 hesaplamalarını baştan çıkarmaya çalışıyorum, elde ettiğim değerler, almam gerekenlerle uyuşmuyor.

Python'un bu sağlama toplamlarını (yani, zlib ve binascii) oluşturabilen kitaplıklara sahip olduğunun farkındayım, ancak mikroişlemde CRC işlevselliği olmadığından bunları kullanabilme lüksüne sahip değilim.

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

Sonra aşağıdaki çıktıyı almak: benim bir değil yaptığı gibi

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

binascii ve zlib hesapları uyuyor

Şimdiye kadar aşağıdaki kodu var. Nette bulunan örneklerle karşılaştırdığım için hesaplanan bayt tablosunun doğru olduğuna inanıyorum. Yani konu her baytın hesaplandığı rutin olmalı, kimse bana doğru yönde işaret edebilir mi?

Şimdiden teşekkürler!

Answer 1

Kuralların yakından bakmadım, bu yüzden hatanın tam kaynağını saptamak olamaz, ancak kolayca istenilen çıktıyı almak için ince ayar yapabilirsiniz:

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 

çıkışı

İşte

'' 
00000000 
00000000 

'test' 
d87f7e0c 
d87f7e0c 

'hello world' 
0d4a1185 
0d4a1185 

'1234' 
9be3e0a3 
9be3e0a3 

'A long string to test CRC32 functions' 
d2d10e28 
d2d10e28 

---

tweaked crc32binascii.crc32 aynı sonucu verir doğrulamak bir çift daha testlerdir.

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

çıkış

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 

açıklamalarda tarif edildiği gibi

---

, orijinal kodu hata kaynağı bu CRC-32 algoritması ilk soğuk tampon tersine çevirir ve ardından olmasıdır son arabellek içeriğini tersine çevirir. Bu nedenle value sıfır yerine 0xffffffff olarak başlatılır ve value^0xffffffff'u döndürmemiz gerekir, bu da ~value & 0xffffffff olarak yazılabilir, yani value'u ters çevirebilir ve daha sonra sonucun düşük dereceli 32 bitini seçebiliriz.