Differenze nel calcolo del checksum rotolante adler32 - Python
Domanda
Hai bisogno di un chiarimento mentre si guarda il calcolo di un checksum in esecuzione.
Assumi che ho dati come questo.
data = 'helloworld'
.
Assumendo un blocksize di 5, ho bisogno di calcolare il checksum di esecuzione.
>>> zlib.adler32('hello')
103547413
>>> zlib.adler32('ellow')
105316900
.
Secondo la documentazione Python (Python versione 2.7.2)
zlib.adler32(data[, value])
.
."Computer un checksum di dati ADLER-32. (Un checksum ADLER-32 è quasi Affidabile come un CRC32 ma può essere calcolato molto più rapidamente.) Se Il valore è presente, è usato come valore iniziale del checksum; In caso contrario, viene utilizzato un valore predefinito fisso. Ciò consente di calcolare a Esecuzione del checksum sulla concatenazione di diversi ingressi. "
Ma quando fornisco qualcosa del genere,
>>> zlib.adler32('ellow', zlib.adler32('hello'))
383190072
.
L'uscita è completamente diversa.
Ho provato a creare una funzione personalizzata per generare il checksum rotolante come definito nell'algoritmo rsync.
def weakchecksum(data):
a = 1
b = 0
for char in data:
a += (ord(char)) % MOD_VALUE
b += a % MOD_VALUE
return (b << 16) | a
def rolling(checksum, removed, added, block_size):
a = checksum
b = (a >> 16) & 0xffff
a &= 0xffff
a = (a - ord(removed) + ord(added)) % MOD_VALUE
b = (b - (block_size * ord(removed)) + a) % MOD_VALUE
return (b << 16) | a
.
Ecco i valori che ottengo da eseguire queste funzioni
Weak for hello: 103547413
Rolling for ellow: 105382436
Weak for ellow: 105316900
.
Come puoi vedere c'è qualche grande differenza nella mia implementazione del checksum rotolante e del Python, in termini di valore.
Dove sto andando male nel calcolo del checksum rotolante? Sto facendo uso della proprietà rotolante della funzione Adler32 di Python correttamente?
Soluzione
La funzione adler32()
non fornisce "rotolamento".La documentazione utilizza correttamente la parola "in esecuzione" (non "rotolamento"), il che significa semplicemente che può calcolare l'ADLER32 in blocchi rispetto a tutti contemporaneamente.È necessario scrivere il proprio codice per calcolare un valore adler32 "rotolante", che sarebbe l'ADLER32 di una finestra scorrevole sui dati.
Altri suggerimenti
Nel tuo metodo "Rolling",
b = (b - (block_size * ord(removed)) + a) % MOD_VALUE
.
dovrebbe essere
b = (b - (block_size * ord(removed)) + a - 1) % MOD_VALUE
.
Secondo la spiegazione di adler32 algoritmo in wikipedia, possiamo vedere: Quando giremo il checksum, avremo le equazioni:
A1 = (1 + D2 + D3 + … + Dn + Dn+1)(mod 65521)
= (1 + D1 + D2 + D3 + … + Dn) – D1 + Dn+1(mod 65521)
= A – D1 + Dn+1(mod 65521)
B1 = (1 + D2) + (1 + D2 + D3) + … + (1 + D2 + D3 + … + Dn + Dn+1)(mod 65521)
= (1 + D1) – D1 – 1 + (1 + D1 + D2) – D1 + ... +(1 + D1 + D2 + … + Dn) – D1 + (1 + D1 + D2 + … + Dn + Dn+1) – D1(mod 65521)
= B – nD1 – 1 + A1 + D1 – D1(mod 65521)
= B – nD1 + A1 – 1(mod 65521)
. A proposito, il tuo rotolamento DEF () è corretto, almeno per Python dove il segno del risultato Modulo ha il segno del divisore.Potrebbe non funzionare in altre lingue, dove ad esempio nel C il segno del risultato della% è il segno del dividendo o è definito l'implementazione.
È possibile rendere il tuo algoritmo più efficiente considerando quanto lontano da Modulo 65521 è possibile ottenere ad ogni passaggio, e sostituire il% con IF e aggiunte o sottrazioni di 65521 o utilizzare i tipi di dati sufficienti di grandi dimensioni per lasciarlo andare aMentre e capire quanto raramente puoi allontanarti con un% sulle somme per evitare traboccamenti.Ancora una volta, fai attenzione con% sui dividendi negativi.
Ecco la funzione di lavoro.Si prega di notare in quale punto è calcolato la mod.
def myadler32(data):
a = 1
b = 0
for c in data:
a += c
b += a
a %= MOD_ADLER
b %= MOD_ADLER
return b<<16 | a
. Credo che tu abbia calcolato male il valore ADLER32 nei tuoi test:
>>> import zlib
>>> zlib.adler32("helloworld")
389415997
>>> zlib.adler32("world",zlib.adler32("hello"))
389415997
.