Adler-32 - Adler-32

Adler-32 é um algoritmo de soma de verificação que foi escrito por Mark Adler em 1995 e é uma modificação da soma de verificação de Fletcher . Comparado a uma verificação de redundância cíclica de mesmo comprimento, ele troca confiabilidade por velocidade (preferindo a última). Adler-32 é mais confiável do que Fletcher-16 e ligeiramente menos confiável do que Fletcher-32 .

História

A soma de verificação Adler-32 faz parte da amplamente usada biblioteca de compactação zlib , já que ambas foram desenvolvidas por Mark Adler . Uma versão de " soma de verificação contínua " do Adler-32 é usada no utilitário rsync .

O algoritmo

Uma soma de verificação Adler-32 é obtida calculando duas somas de verificação de 16 bits A e B e concatenando seus bits em um inteiro de 32 bits. A é a soma de todos os bytes no fluxo mais um e B é a soma dos valores individuais de A de cada etapa.

No início de uma execução do Adler-32, A é inicializado com 1, B com 0. As somas são feitas no módulo 65521 (o maior número primo menor que 2 16 ). Os bytes são armazenados na ordem da rede ( big endian ), B ocupando os dois bytes mais significativos.

A função pode ser expressa como 

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

onde D é a sequência de bytes para o qual a soma de verificação é calculado, e n é o comprimento de D .

Exemplo

A soma Adler-32 da string ASCII " Wikipedia " seria calculada da seguinte maneira:

Personagem Código ASCII UMA B
(mostrado como base 10)
C 87 1 + 87 = 88 0 + 88 = 88
eu 105 88 + 105 = 193 88 + 193 = 281
k 107 193 + 107 = 300 281 + 300 = 581
eu 105 300 + 105 = 405 581 + 405 = 986
p 112 405 + 112 = 517 986 + 517 = 1503
e 101 517 + 101 = 618 1503 + 618 = 2121
d 100 618 + 100 = 718 2121 + 718 = 2839
eu 105 718 + 105 = 823 2839 + 823 = 3662
uma 97 823 + 97 = 920 3662 + 920 = 4582 
A =  920 =  0x398  (base 16)
B = 4582 = 0x11E6
Output = 0x11E6 << 16 + 0x398 = 0x11E60398

A operação do módulo não teve efeito neste exemplo, pois nenhum dos valores atingiu 65521.

Comparação com a soma de verificação Fletcher

A primeira diferença entre os dois algoritmos é que as somas de Adler-32 são calculadas no módulo de um número primo, enquanto as somas de Fletcher são calculadas no módulo 2 4 −1, 2 8 −1 ou 2 16 −1 (dependendo do número de bits usados) , que são todos números compostos . Usar um número primo possibilita que Adler-32 capture diferenças em certas combinações de bytes que Fletcher não consegue detectar.

A segunda diferença, que tem o maior efeito na velocidade do algoritmo, é que as somas de Adler são calculadas em bytes de 8 bits em vez de palavras de 16 bits , resultando em duas vezes o número de iterações de loop. Isso resulta na soma de verificação do Adler-32 levando de uma vez e meia a duas vezes mais que a soma de verificação de Fletcher para dados alinhados de palavras de 16 bits. Para dados alinhados por byte, o Adler-32 é mais rápido do que uma soma de verificação de Fletcher implementada corretamente (por exemplo, um encontrado no Formato de Dados Hierárquico ).

Implementação de exemplo

Em C , uma implementação ineficiente, mas direta é: 

const uint32_t MOD_ADLER = 65521;

uint32_t adler32(unsigned char *data, size_t len) 
/* 
    where data is the location of the data in physical memory and 
    len is the length of the data in bytes 
*/
{
    uint32_t a = 1, b = 0;
    size_t index;
    
    // Process each byte of the data in order
    for (index = 0; index < len; ++index)
    {
        a = (a + data[index]) % MOD_ADLER;
        b = (b + a) % MOD_ADLER;
    }
    
    return (b << 16) | a;
}

Veja o código-fonte zlib para uma implementação mais eficiente que requer uma busca e duas adições por byte, com as operações de módulo adiadas com dois restos calculados a cada vários milhares de bytes, uma técnica descoberta pela primeira vez para somas de verificação de Fletcher em 1988. js-adler32 fornece uma otimização semelhante, a adição de um truque que atrasa o cálculo do "15" em 65536 - 65521 para que os módulos se tornem mais rápidos: pode-se mostrar que ((a >> 16) * 15 + (a & 65535)) % 65521 é equivalente à acumulação ingênua.

Vantagens e desvantagens

  • Como o CRC-32 padrão , a soma de verificação Adler-32 pode ser forjada facilmente e, portanto, não é segura para proteção contra modificação intencional .
  • É mais rápido que o CRC-32 em muitas plataformas.
  • O Adler-32 tem um ponto fraco para mensagens curtas com algumas centenas de bytes, porque as somas de verificação dessas mensagens têm uma cobertura insuficiente dos 32 bits disponíveis.

Fraqueza

Adler-32 é fraco para mensagens curtas porque a soma A não é agrupada. A soma máxima de uma mensagem de 128 bytes é 32640, que está abaixo do valor 65521 usado pela operação do módulo, o que significa que aproximadamente metade do espaço de saída não é usado e a distribuição dentro da parte usada é não uniforme. Uma explicação estendida pode ser encontrada na RFC   3309 , que exige o uso de CRC32C em vez de Adler-32 para SCTP , o Stream Control Transmission Protocol. Adler-32 também demonstrou ser fraco para pequenas mudanças incrementais e também fraco para strings geradas a partir de um prefixo comum e números consecutivos (como nomes de rótulos gerados automaticamente por geradores de código típicos).

Veja também

Notas

links externos