Отличия в расчете скользящей контрольной суммы adler32 - python

Question

Требуется пояснение при рассмотрении расчета текущей контрольной суммы.

Предположим, у меня есть такие данные.

data = 'helloworld'

Предполагая размер блока 5, мне нужно вычислить текущую контрольную сумму.

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

Согласно документации Python (версия Python 2.7.2)

zlib.adler32(data[, value])

"Вычисляет контрольную сумму данных Adler-32. (Контрольная сумма Adler-32 почти равнанадежен как CRC32, но может быть вычислен намного быстрее.) Если значение присутствует, оно используется в качестве начального значения контрольной суммы, в противном случае используется фиксированное значение по умолчанию. Это позволяет вычислить текущую контрольную сумму по объединению нескольких входов. "

Но когда я предоставляю что-то вроде этого,

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

Вывод совершенно другой.

Я попытался создать пользовательскую функцию для генерации скользящегоконтрольная сумма, как определено в алгоритме 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

Вот значения, которые я получаю при запуске этих функций

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

Как вы можете видеть, есть некоторые большие различияВ моей реализации скользящей контрольной суммы и Python в стоимостном выражении.

Где я ошибаюсь при вычислении скользящей контрольной суммы?Правильно ли я использую свойство rolling функции adler32 в Python?

Answer 1

В вашем методе "roll" значение

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

должно быть

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

Согласно объяснению алгоритма adler32 в Википедии, мы можем увидеть:

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

Когда мы проверяем контрольную сумму, у нас будут уравнения:

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 2

Функция adler32() не обеспечивает "прокатку". В документации правильно используется слово «работает» (не «катится»), что означает просто, что он может вычислять adler32 порциями, а не все сразу. Вам нужно написать собственный код, чтобы вычислить «скользящее» значение adler32, которое будет adler32 скользящего окна над данными.

Answer 3

Кстати, ваш def roll () верен, по крайней мере, для Python, где знак результата по модулю имеет знак делителя. Он может не работать в других языках, где, например, в C знак результата% является либо знаком дивиденда, либо определен реализацией.

Вы можете сделать свой алгоритм более эффективным, учитывая, как далеко от модуля 65521 вы можете получить на каждом шаге, и либо заменить% на if, а также добавить или вычитать 65521, либо использовать достаточно большие типы данных, чтобы позволить ему перейти на время и выяснить, как редко вы можете избежать с% на суммы, чтобы избежать переполнения. Опять же, будьте осторожны с% на отрицательных дивидендах.

Answer 4

Вот рабочая функция.Обратите внимание, на каком этапе рассчитывается 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

Я полагаю, что вы неправильно рассчитали значение adler32 в своем тестировании:

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