Differenze nel calcolo del checksum rotolante adler32 - Python

Question

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?

Answer 1

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.

Answer 2

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)

.

Answer 3

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.

Answer 4

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

.

Answer 5

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

.