Les différences dans le calcul de la adler32 de roulement la somme de python

Question

Besoin d'une clarification en regardant le calcul d'une exécution de somme de contrôle.

Supposons que j'ai données comme cela.

data = 'helloworld'

En supposant une taille de bloc de 5, j'ai besoin de calculer l'exécution de somme de contrôle.

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

Selon la documentation Python (version de python 2.7.2)

zlib.adler32(data[, value])

"Calcule un Adler-32 de la somme de contrôle des données.(L'Adler-32 de la somme de contrôle est presque aussi fiable qu'un CRC32 mais peut être calculée beaucoup plus rapidement.) Si valeur est présente, elle est utilisée comme valeur de départ de la somme de contrôle;sinon, fixe la valeur par défaut est utilisé.Cela permet le calcul d'une l'exécution de somme de contrôle sur la concaténation de plusieurs entrées."

Mais quand je donner quelque chose comme ceci,

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

La sortie est tout à fait différent.

J'ai essayé de créer une fonction personnalisée pour générer le roulement de la somme de contrôle tel que défini dans l'algorithme 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

Voici les valeurs que j'obtiens de l'exécution de ces fonctions

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

Comme vous pouvez le voir il y a une énorme différence dans ma mise en œuvre de roulement de la somme de contrôle et python, en termes de valeur.

Où vais-je tromper dans le calcul du roulement de la somme de contrôle?Suis-je en faisant usage de the rolling propriété de python adler32 fonctionner correctement?

Answer 1

L' adler32() la fonction ne fournit pas de "rolling".La documentation utilise correctement le mot "exécution" (pas de "rolling"), ce qui signifie tout simplement qu'il est possible de calculer le adler32 en morceaux par opposition à tous à la fois.Vous devez écrire votre propre code pour faire le calcul d'un "rolling" adler32 valeur, ce qui serait le adler32 d'une fenêtre coulissante sur les données.

Answer 2

dans votre méthode "roulement", le

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

devrait être

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

Selon l'explication de ADLER32 algorithme à Wikipedia, nous pouvons voir:

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

Lorsque nous roulons de la somme de contrôle, nous aurons les équations:

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

D'ailleurs, votre lambrissement def () est correct, au moins pour Python où le signe du résultat du modulo a le signe du diviseur.Cela pourrait ne pas fonctionner dans d'autres langues, où par exemple en C, le signe du résultat de% est le signe du dividende ou la mise en œuvre définie.

Vous pouvez rendre votre algorithme plus efficace en considérant à quelle distance de MODULO 65521 vous pouvez obtenir à chaque étape et en remplaçant le% avec les ajouts et les ajouts ou les soustractions de 65521, ou utilisez des types de données suffisants pour le laisser aller pour unet déterminez-vous à quel point vous pouvez rarement vous pouvez vous échapper avec un% sur les sommes pour éviter de déborder.Encore une fois, soyez prudent avec% sur les dividendes négatifs.

Answer 4

Voici la fonction de travail.Veuillez noter à quelle étape le MOD est calculé.

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

Je pense que vous avez mal calculé la valeur Adler32 dans vos tests:

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