Unterschiede in der Berechnung der adler32 rollierenden Prüfsumme - python

Question

Benötigen Sie eine Klarstellung bei der Berechnung einer laufenden Prüfsumme.

Angenommen, ich habe solche Daten.

data = 'helloworld'

Unter der Annahme einer Blockgröße von 5 muss ich die laufende Prüfsumme berechnen.

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

Laut Python-Dokumentation (Python Version 2.7.2)

zlib.adler32(data[, value])

"Berechnet eine Adler-32-Prüfsumme von Daten.(Eine Adler-32-Prüfsumme ist fast so zuverlässig wie ein CRC32, kann aber viel schneller berechnet werden.) Wenn wert vorhanden ist, wird er als Startwert der Prüfsumme verwendet;andernfalls wird ein fester Standardwert verwendet.Dies ermöglicht die Berechnung einer laufende Prüfsumme über die Verkettung mehrerer Eingänge."

Aber wenn ich so etwas anbiete,

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

Die Ausgabe ist völlig anders.

Ich habe versucht, eine benutzerdefinierte Funktion zu erstellen, um die fortlaufende Prüfsumme wie im rsync-Algorithmus definiert zu generieren.

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

Hier sind die Werte, die ich beim Ausführen dieser Funktionen erhalte

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

Wie Sie sehen, gibt es einen großen Unterschied in meiner Implementierung von rollierender Prüfsumme und Python in Bezug auf den Wert.

Wo mache ich bei der Berechnung der fortlaufenden Prüfsumme einen Fehler?Nutze ich die rollierende Eigenschaft von Pythons Adler32-Funktion korrekt?

Answer 1

Der adler32() funktion bietet kein "Rollen".In der Dokumentation wird korrekt das Wort "Laufen" (nicht "Rollen") verwendet, was einfach bedeutet, dass der adler32 in Blöcken und nicht auf einmal berechnet werden kann.Sie müssen Ihren eigenen Code schreiben, um einen "rollenden" adler32-Wert zu berechnen, der der adler32 eines Schiebefensters über den Daten wäre.

Answer 2

in Ihrer Methode "Rolling", das

generasacodicetagpre.

sollte

sein generasacodicetagpre.

Nach dem Erklären von adler32 Algorithmus in Wikipedia, wir können sehen:

. generasacodicetagpre.

Wenn wir die Prüfsumme rollen, haben wir die Gleichungen:

generasacodicetagpre.

Answer 3

Übrigens ist Ihr def-Rolling () richtig, zumindest für Python, in dem das Zeichen des Modulo-Ergebniss das Zeichen des Divisors hat.Es funktioniert möglicherweise nicht in anderen Sprachen, wo beispielsweise in C das Vorzeichen des Ergebnisses von% entweder das Zeichen der Dividende ist oder die Implementierung definiert ist.

Sie können Ihren Algorithmus effizienter machen, indem Sie in Betracht ziehen, wie weit von MODULO 65521 Sie in jedem Schritt erhalten können, und entweder ersetzen Sie den% mit IF-und Ergänzungen oder Subtrahien von 65521 oder verwenden Sie groß genug Datentypen, um es für eineWährend und herausfinden, wie selten Sie mit einem% auf den Summen davonkommen können, um überflutet zu vermeiden.Seien Sie wieder vorsichtig mit% auf negativen Dividenden.

Answer 4

Hier ist die Arbeitsfunktion.Bitte beachten Sie, in welchem Schritt der Mod berechnet wird.

generasacodicetagpre.

Answer 5

Ich glaube, Sie haben den ADLER32-Wert in Ihrem Testen falsch berechnet:

generasacodicetagpre.