Diferenças no cálculo da soma de verificação contínua do adler32 - python

Question

Precisa de um esclarecimento ao calcular uma soma de verificação em execução.

Suponha que eu tenha dados como este.

data = 'helloworld'

Supondo um tamanho de bloco de 5, preciso calcular a soma de verificação em execução.

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

De acordo com a documentação do Python (python versão 2.7.2)

zlib.adler32(data[, value])

"Calcula uma soma de verificação de dados Adler-32.(Uma soma de verificação ADLER-32 é quase tão confiável quanto um CRC32, mas pode ser calculada muito mais rapidamente.) Se o valor estiver presente, ele será usado como o valor inicial da soma de verificação;caso contrário, um valor padrão fixo será usado.Isso permite calcular uma soma de verificação em execução sobre a concatenação de várias entradas. "

Mas quando eu forneço algo assim,

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

A saída é totalmente diferente.

Tentei criar uma função personalizada para gerar a soma de verificação contínua conforme definido no 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

Aqui estão os valores que obtenho ao executar essas funções

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

Como você pode ver, há uma grande diferença na minha implementação de soma de verificação contínua e python, em termos de valor.

Onde estou errando ao calcular a soma de verificação contínua?Estou usando a propriedade rolante da função adler32 do python corretamente?

Answer 1

O adler32() função não fornece "rolamento".A documentação usa corretamente a palavra "running" (não "rolling"), o que significa simplesmente que ele pode calcular o adler32 em pedaços, em vez de tudo de uma vez.Você precisa escrever seu próprio código para calcular um valor adler32 "rolante", que seria o adler32 de uma janela deslizante sobre os dados.

Answer 2

No seu método "rolling", o

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

deveria estar

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

De acordo com a explicação de Adler32 algoritmo na 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

Ao rolar o checksum, teremos as equações:

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

A propósito, seu def rolling() está correto, pelo menos para Python onde o sinal do resultado do módulo tem o sinal do divisor.Pode não funcionar em outras línguas, onde, por exemplo, em C, o sinal do resultado de% é o sinal do dividendo ou é definido pela implementação.

Você pode tornar seu algoritmo mais eficiente considerando o quão longe do módulo 65521 você pode chegar em cada etapa, e substituindo o% por if's e adições ou subtrações de 65521, ou usando tipos de dados grandes o suficiente para deixá-lo passar por um tempo e descobrir descubra com que frequência você consegue obter uma% das somas para evitar transbordamento.Novamente, tome cuidado com% sobre dividendos negativos.

Answer 4

Aqui está a função de trabalho.Observe em que etapa o MOD é calculado.

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

Acredito que você calculou mal o valor adler32 em seus testes:

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