Различия в вычислении скользящей контрольной суммы 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

Как вы можете видеть, есть некоторая огромная разница в моей реализации rolling checksum и python с точки зрения ценности.

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

Answer 1

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

Answer 2

В вашем методе «Rolling», то

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 3

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

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

Answer 4

Вот работающая функция.Пожалуйста, обратите внимание на то, на каком шаге рассчитан мод.

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

.