Diferencias en el cálculo de Adl32 Rolling CheckSum - Python

Question

Necesito una aclaración mientras mira calculando una suma de comprobación en funcionamiento.

Supongamos que tengo datos como este.

data = 'helloworld'

Suponiendo un bloque de bloques de 5, necesito calcular la suma de comprobación en funcionamiento.

>>> zlib.adler32('hello')
103547413
>>> zlib.adler32('ellow')
105316900

Según la documentación de Python (Python versión 2.7.2)

zlib.adler32(data[, value])

"Calcula una suma de comprobación de datos Adler-32. (Una suma de comprobación Adler-32 es casi tan confiable como un CRC32, pero se puede calcular mucho más rápidamente). Si El valor está presente, se utiliza como el valor de partida de la suma de comprobación; De lo contrario, se utiliza un valor predeterminado fijo. Esto permite computar un Corriendo suma de comprobación sobre la concatenación de varias entradas ".

pero cuando proporcione algo como esto,

>>> zlib.adler32('ellow', zlib.adler32('hello'))
383190072

La salida es completamente diferente.

Intenté crear una función personalizada para generar la suma de comprobación enrollable como se define en el 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

Aquí hay los valores que obtengo de ejecutar estas funciones

Weak for hello: 103547413
Rolling for ellow: 105382436
Weak for ellow: 105316900

Como puede ver, hay una gran diferencia en mi implementación de la suma de comprobación y la de Python, en términos de valor.

¿Dónde estoy equivocado al calcular la suma de comprobación enrollable? ¿Estoy haciendo uso de la propiedad rodante de la función Adler32 de Python correctamente?

Answer 1

La función adler32() no proporciona "rodamiento".La documentación utiliza correctamente la palabra "en ejecución" (no "rodante"), lo que significa simplemente que puede calcular el Adler32 en trozos en lugar de todos a la vez.Debe escribir su propio código para computar un valor de "Rolling" Adler32, que sería el Adler32 de una ventana deslizante sobre los datos.

Answer 2

en su método "Rolling", el

b = (b - (block_size * ord(removed)) + a) % MOD_VALUE

debe ser

b = (b - (block_size * ord(removed)) + a - 1) % MOD_VALUE

Según la explicación de adler32 algoritmo en Wikipedia, podemos ver:

A = 1 + D1 + D2 + ... + Dn (mod 65521)
B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
  = n×D1 + (n−1)×D2 + (n−2)×D3 + ... + Dn + n (mod 65521)

Adler-32(D) = B × 65536 + A

Cuando rodamos suma de comprobación, tendremos las ecuaciones:

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

Por cierto, su definición de definición () es correcta, al menos para Python donde el signo del resultado del módulo tiene el signo del divisor.Puede que no funcione en otros idiomas, donde, por ejemplo, en C, el signo del resultado del% es el signo del dividendo o se define la implementación.

Puede hacer que su algoritmo sea más eficiente al considerar lo lejos de Modulo 65521, puede obtener en cada paso, y reemplazar el% con IF y adiciones o sustracciones de 65521, o usar los tipos de datos suficientes suficientes para dejarlo pasar por unMientras y descubra qué tan frecuente puede salirse con un% en las sumas para evitar desbordarse.Nuevamente, tenga cuidado con% en dividendos negativos.

Answer 4

Aquí está la función de trabajo.Tenga en cuenta que en qué paso se calcula el 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

Creo que ha calculado mal el valor de Adler32 en sus pruebas:

>>> import zlib
>>> zlib.adler32("helloworld")
389415997
>>> zlib.adler32("world",zlib.adler32("hello"))
389415997