Como utilizar o método CRC de detecção de erros

Este artigo foi colocado na web por SPLat Controls, fabricantes da série SPLat de micro CLPs para uso em OEM (Original Equipment Manufacturer).
O micro CLP da SPLat é o mais econômico do mundo.
De produtos a pronta entrega, que economizam a você mais do que custam, a controladores programáveis pelo usuário personalizados, a SPLAt tem uma sensacional nova maneira de produzir controles eletrônicos para equipamentos, em quantidades de 1 a 50000 por ano.

Para conhecer a SPLat, copie e cole a seguinte URL na barra de endereços do seu navegador:
http://splatco.com.
==================================================================
Artigo reproduzido com a permissão do proprietário dos direitos autorais.
Boa leitura!
==================================================================
UM GUIA INDOLOR PARA ALGORITMOS DE DETECÇÃO DE ERROS DE CRC
===========================================================
“Tudo que você queria saber sobre algoritmos CRC, mas tinha medo de perguntar por medo de que fossem detectados erros no seu entendimento.”

Versão    : 3.
Data      : 19 Agosto 1993.
Autor     : Ross N. Williams.
e-mail    : ross@guest.adelaide.edu.au.
FTP       : ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txt
Companhia : Rocksoft^tm Pty Ltd.
Lesma     : 16 Lerwick Avenue, Hazelwood Park 5066, Australia.
Fax       : +61 8 373-4911 (c/- Internode Systems Pty Ltd).
Fone      : +61 8 379-9217 (10am to 10pm Adelaide Australia time).
Nota      : "Rocksoft" é marca registrada da Rocksoft Pty Ltd, Australia.
Status   : Copyright (C) Ross Williams, 1993. Entretanto, é permitida a distribuição de cópias idênticas deste documento, desde que este bloco de informação e nota sobre direito autoral seja incluído. Também, os módulos codificados na linguagem de programação C, incluídos neste documento, são inteiramente de domínio público.
Agradecimentos : Agradecimentos a Jean-loup Gailly (jloup@chorus.fr) e Mark Adler (me@quest.jpl.nasa.gov), que revisaram este documento e localizaram grandes quantidades de pequenos erros, bem como algumas falhas de peso.

Tabela de Conteúdos
-------------------

Resumo
 1. Introdução: Detecção de Erros
 2. A Necessidade De Complexidade
 3. A Idéia Básica Por Trás Dos Algoritmos CRC
 4. Aritmética Polinomial
 5. Aritmética Binária Sem Transporte
 6. Um Exemplo Inteiramente Resolvido
 7. Escolhendo Um Polinômio
 8. Uma Implementação CRC Direta
 9. Uma Implementação Baseada Em Tabelas
10. Uma Implementação Baseada Em Tabelas, Ligeiramente Adaptada
11. Implementações Baseadas Em Tabelas, “Refletidas”
12. Polinômios “Reversos”
13. Valor Inicial e Valor Final
14. Definindo Algoritmos Absolutamente
15. Um Modelo Parametrizado Para Algoritmos de CRC
16. Um Catálogo de Conjuntos de Parâmetros Para Padrões
17. Uma Implementação Do Algoritmo Modelo
18. Crie Sua Própria Implementação Baseada em Tabelas
19. Gerando Uma Tabela De Busca
20. Sumário
21. Correções
 A. Glossário
 B. Referências
 C. Referências Que Detectei Mas Ainda Não Li Nem Conferi

Resumo
------

Este documento explica CRCs (Cyclic Redundancy Codes – Códigos de Redundância Cíclica), e suas implementações baseadas em tabelas, em detalhes completos e precisos. Muito da literatura sobre CRCs, e em particular sobre suas implementações baseadas em tabelas, é um  pouco obscura (ou pelo menos assim me parece).
Este documento é uma tentativa de fornecer uma explicação clara e desprovida de falta de sentido sobre os CRCs, e tratar de absolutamente todos os detalhes de operação das suas implementações de alta velocidade. Além disto, este documento apresenta um algoritmo de CRC parametrizado modelo chamado “O Algoritmo CRC Modelo Rocksoft^tm”. O algoritmo modelo pode ser parametrizado para se comportar como a maioria das implementações de CRC existentes, e assim funciona como uma referência para descrever algoritmos particulares. Um implementação em baixa velocidade do algoritmo de CRC é fornecida na linguagem de programação C. Por fim, há uma seção fornecendo duas formas de implementações em alta velocidade baseadas em tabelas, e fornecendo um programa que gera tabelas de busca CRC.

1. Introdução: Detecção de Erros
--------------------------------

A finalidade de uma técnica de detecção de erros é possibilitar ao receptor de uma mensagem, transmitida através de um canal com ruído (introdutor de erro), determinar se a mensagem foi corrompida. Para fazer isto, o transmissor gera um valor (chamado checksum) que é uma função da mensagem, anexando este valor à mensagem. O receptor pode, então, usar a mesma função para calcular o checksum da mensagem recebida, e compará-lo ao checksum que veio anexado para ver se a mensagem foi corretamente recebida. Por exemplo, se escolhemos uma função de checksum que é simplesmente a soma dos bytes da mensagem mod 256 (isto é, módulo 256), então ele deverá funcionar conforme abaixo. Todos os números estão em decimal.

Mensagem : 6 23 4
Mensagem com checksum : 6 23 4 33
Mensagem após a transmissão : 6 27 4 33

No exemplo acima, o Segundo byte da mensagem foi corrompido de 23 para 27 pelo canal de comunicações. Mas, o receptor pode detectar isto comparando o checksum que foi transmitido (33) com o checksum de 37 (6 + 27 + 4). Se o próprio checksum estiver corrompido, uma mensagem corretamente transmitida poderá ser incorretamente identificada como corrompida. Mas esta é uma “falha segura”. Uma “falha perigosa” ocorre quando a mensagem e/ou o checksum são corrompidos de uma maneira que resulta em uma transmissão que é internamente consistente. Infelizmente, esta possibilidade é inteiramente inevitável, e o melhor que pode ser feito é minimizar sua probabilidade incrementando a quantidade de informações no checksum (por exemplo, ampliando o checksum de um para dois bytes).

Existem outras técnicas de detecção de erros, as quais envolvem a realização de transformações complexas na mensagem para introduzir informações redundantes. No entanto, este documento trata especificamente de algoritmos CRC, o qual recai na classe de algoritmos de detecção de erros que deixam os dados intactos e anexam um checksum ao final dos mesmos, isto é:

<mensagem original intacta> <checksum>

2. A Necessidade De Complexidade
--------------------------------
No exemplo do checksum na seção anterior, vimos como uma mensagem corrompida foi detectada usando um algoritmo de checksum que simplesmente soma os bytes em uma mensagem mod 256:

Mensagem : 6 23 4
Mensagem com checksum : 6 23 4 33
Mensagem após a transmissão : 6 27 4 33

Um problema deste algoritmo é que ele é simples demais. Se um número de corrupções aleatórias ocorrer, há uma chance de 1 em 256 de que não serão detectadas. Por exemplo:

Mensagem : 6 23 4
Mensagem com checksum : 6 23 4 33
Mensagem após a transmissão : 8 20 5 33

Para fortalecer o checksum, poderíamos mudar de um registrador de 8 bits para um registrador de 16 bits (isto é, somar os bytes mod 65536 em vez de mod 256), para aparentemente reduzir a probabilidade de falha de 1/256 para 1/65536. Embora seja basicamente uma boa idéia, neste caso falha porque a fórmula utilizada não é suficientemente aleatória; se utilizamos uma fórmula de simples soma, cada byte que entra afeta primitivamente apenas um byte do registrador de soma, não importando a sua extensão. Por exemplo, no segundo exemplo acima o registrador de soma poderia ter o tamanho de 2 Megabytes, e o erro ainda permaneceria não detectado. Este problema só pode ser resolvido substituindo-se a fórmula de soma simples por uma fórmula mais sofisticada, que fará com que cada byte que entra exerça efeito sobre o registrador de soma inteiro. Portanto, vemos que pelo menos dois aspectos são necessários, são um requisito, para criar uma função robusta de checksum:

TAMANHO: Um tamanho de registrador grande o suficiente para assegurar uma baixa probabilidade inicial de falha (por exemplo, um registrador de 32 bits fornece uma chance de 1/2^32 de falha).

CAOS: Uma fórmula que assegura a cada byte de entrada o potencial de alterar qualquer número bits no registrador.

OBSERVAÇÃO: O termo “checksum” foi presumivelmente usado para descrever antigas fórmulas de soma, mas atualmente assumiu um significado mais genérico englobando algoritmos mais sofisticados, como por exemplo os algoritmos de CRC. Os algoritmos de CRC que descreveremos satisfazem muito bem a segunda condição e podem ser configurados para funcionar com uma grande variação de tamanhos de valores de checksum.

3. A Idéia Básica Por Trás Dos Algoritmos De CRC
------------------------------------------------
Para onde poderíamos ir, em nossa pesquisa por uma função mais complexa do que uma soma? Todo tipo de esquemas vem à mente. Poderíamos construir tabelas utilizando os dígitos de pi, ou combinar cada byte que entra com todos os bytes no registrador. Poderíamos até manter uma imensa lista telefônica online, e usar cada byte que entra combinado com os bytes do registrador para indexar um novo número telefônico, o qual poderia então ser o próximo valor do registrador. As possibilidades são ilimitadas.

Entretanto, não precisamos ir tão longe; o próximo passo aritmético é suficiente. Embora a adição claramente não seja forte o suficiente para gerar um checksum efetivo, a divisão mostra-se com esta força, desde que o divisor seja tão longo quanto o registrador do checksum.

A idéia básica dos algoritmos CRC é simplesmente tratar a mensagem como um enorme número binário, dividi-lo por outro número binário fixo, e utilizar o resto desta divisão como o checksum. Quando receber a mensagem, o receptor pode efetuar a mesma divisão e comparar o resto com o “checksum” (resto transmitido).

Exemplo: Suponha a mensagem que consiste dos dois bytes (6, 23) como no exemplo anterior. Estes podem ser considerados como sendo o número hexadecimal 0617, que pode ser considerado como sendo o número binário 0000-0110-0001-0111. Suponha que utilizemos um registrador de checksum do tamanho de um byte e utilizemos um divisor constante de 1001, então o checksum é o resto da divisão de 0000-0110-0001-0111 por 1001. Embora neste caso o cálculo obviamente poderia ser executado utilizando registradores comuns de 32 bits, no cenário geral isto torna-se mais dificultoso. Assim faremos, ao invés, a divisão utilizando a divisão longa que você aprendeu na escola (lembra-se?). Exceto pelo fato de que, desta vez, a divisão está em binário:

         ...0000010101101 = 00AD = 173 = QUOCIENTE
         ____-___-___-___-
9= 1001 ) 0000011000010111 = 0617 = 1559 = DIVIDENDO
DIVISOR   0000.,,....,.,,,
          ----.,,....,.,,,
           0000,,....,.,,,
           0000,,....,.,,,
           ----,,....,.,,,
            0001,....,.,,,
            0000,....,.,,,
            ----,....,.,,,
             0011....,.,,,
             0000....,.,,,
             ----....,.,,,
              0110...,.,,,
              0000...,.,,,
              ====...,.,,,
               1100..,.,,,
               1001..,.,,,
               ----..,.,,,
                0110.,.,,,
                0000.,.,,,
                ----.,.,,,
                 1100,.,,,
                 1001,.,,,
                 ====,.,,,
                  0111.,,,
                  0000.,,,
                  ----.,,,
                   1110,,,
                   1001,,,
                   ====,,,
                    1011,,
                    1001,,
                    ====,,
                     0101,
                     0000,
                     ----
                      1011
                      1001
                      ====
                       0010 = 02 = 2 = RESTO

Em decimal isto seria “1559 dividido por 9 é 173, com resto 2”. Embora o efeito de cada bit da mensagem de entrada no quociente não seja tão significativo, é absolutamente impossível prever durante o cálculo qual será o valor do resto (o valor 0010, de 4 bits). Se mais bytes fossem acrescentados à mensagem (dividendo), o valor do resto poderia alterar-se novamente radicalmente, e muito rapidamente. É por isto que a divisão funciona onde a adição não funciona. Para o caso de você estar se perguntando, utilizando este checksum de 4 bits a mensagem transmitida pareceria com o seguinte (em hexadecimal): 06172 (onde 0617 é a mensagem, e 2 é o checksum).  O receptor iria dividir 0617 por 9, e verificar se o resto é 2.

4. Aritmética Polinomial:
-------------------------
Enquanto o esquema de divisão descrito na seção anterior é muito, muito similar aos esquemas de cálculo do checksum chamados esquemas CRC, os esquemas CRC são, na verdade, um pouco mais esquisitos, e nós precisamos seguir em expedição adentrando alguns estranhos sistemas numéricos para entendê-los.

A palavra que você vai ouvir o tempo todo quando estiver tratando com algoritmos CRC é a palavra “polinômio”. Diz-se que um algoritmo CRC dado está utilizando um polinômio em particular, e diz-se, em geral, que os algoritmos CRC estão operando utilizando aritmética polinomial. O que isto significa?


Em vez de o divisor, o dividendo (mensagem), o quociente e o resto (como descrito na seção anterior) serem vistos como números inteiros positivos, são vistos como polinômios com coeficientes binários. Isto é feito tratando-se cada número como uma string de bits cujos bits são os coeficientes de um polinômio. Por exemplo, o número ordinal 23 (decimal) é 17 (em hexadecimal) e 10111 em binário; assim, ele corresponde ao polinômio:

1*x^4 + 0*x^3 + 1*x^2 + 1*x^1 + 1*x^0

ou, mais simplesmente:

x^4 + x^2 + x^1 + x^0

Utilizando esta técnica, a mensagem e o divisor podem ser representados como polinômios, e podemos fazer todo o cálculo aritmético exatamente como antes, exceto pelo fato de que agora tudo está atravancado com Xs. Por exemplo, suponha que queremos multiplicar 1101 por 1011. Podemos fazer isto simplesmente multiplicando os polinômios:


 (x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
 + x^5 + x^3 + x^2
 + x^3 + x^1 + x^0) = x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

Neste ponto, para obtermos a resposta correta temos que simular que x é 2 e propagar transportes binários a partir de 3*x^3 resultando em

                    x^7 + x^3 + x^2 + x^1 + x^0

É exatamente como na aritmética ordinária, exceto pelo fato de que a base é abstraída e levada para dentro de todos os cálculos explicitamente, em vez de estar lá implicitamente. Então, qual é a questão?

A  questão é que SE simularmos que NÃO sabemos qual é o valor de x, NÃO PODEMOS executar os transportes. Não sabemos que 3*x^3 é a mesma coisa que x^4 + x^3, porque não sabemos que x é 2. Nesta aritmética polinomial verdadeira, a relação entre todos os coeficientes é desconhecida, e assim o coeficiente de cada potência efetivamente tornou-se fortemente característico; os coeficientes de x^2 são efetivamente de um tipo diferente dos coeficientes de x^3.

Com os coeficientes de cada potência satisfatoriamente isolados, os matemáticos puderam alcançar toda sorte de diferentes tipos de aritmética polinomial simplesmente alterando as regras sobre como os coeficientes devem funcionar. Destes esquemas, um em particular é relevante aqui, e este é uma aritmética polinomial em que os coeficientes são calculados em MOD 2 e não há transporte; todos os coeficientes devem ser ou 0 ou 1, e não são calculados transportes. Isto é chamado “aritmética polinomial módulo 2”. Portanto, voltando ao exemplo anterior:

 (x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
 + x^5 + x^3 + x^2
 + x^3 + x^1 + x^0)
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

Na outra artimétics, o termo 3*x^3 foi propagado através de mecanismo de transporte, utilizando o conhecimento de que x=2. na “aritmética polinomial de módulo 2”, não sabemos qual é o valor de  x , não há transporte, e todos os coeficientes devem ser calculados pelo módulo 2. Então, o resultado fica:

= x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + x^0

Conforme Knuth [Kunth81] diz (pág. 400):

“O leitor deve observar a similaridade entre a aritmética polinomial a aritmética de precisão múltipla (Seção 4.3.1), onde a raiz  b  é substituída por  x. A principal diferença é que o coeficiente  u_k  de  x^k  na aritmética polinomial tem pouca ou nenhuma relação com seus coeficientes vizinhos  x^(k-1), e assim sendo a idéia de “transportar” de um lugar para outro está ausente. De fato, a aritmética polinomial de módulo b é essencialmente idêntica à aritmética de precisão múltipla de raiz b, exceto pelo fato de que todos os transportes são suprimidos.”
Portanto, a aritmética polinomial de módulo 2 é simplesmente a aritmética binária de módulo 2, sem transportes. Apesar de os polinômios proporcionarem um mecanismo matemático útil em abordagens mais analíticas aos algoritmos CRC e correção de erro, para fins de exposição e explanação eles não proporcionam nenhum entendimento importante adicional. Na verdade, colocam dificuldades extra desnecessárias, e foram descartados no restante deste documento em benefício de uma manipulação direta do sistema aritmético com o qual eles são isomorfos: aritmética binária sem transporte.

5. Aritmética Binária Sem Transporte
------------------------------------

Tendo dispensado os polinômios, podemos nos concentrar na verdadeira questão aritmética, que é o fato de que toda a aritmética executada durante os cálculos de CRC é feita no sistema binário sem transporte. Isto frequentemente é chamado aritmética polinomial mas, como eu declarei que o resto deste documento é uma área livre de polinômios, teremos que, em vez disto, denominar esta técnica de aritmética CRC. Como esta aritmética é um componente-chave dos cálculos CRC, é melhor nos acostumarmos com ela. Então, aqui vamos nós: somar dois números na aritmética CRC é a mesma coisa que somar dois números na aritmética binária normal, exceto pelo fato de que não é feito transporte. Isto significa que cada par de bits correspondentes determinam o bit de saída correspondente, sem referência a nenhum bit de nenhuma outra posição. Por exemplo:

10011011
+11001010
 --------
 01010001
 --------

Há somente quatro possibilidades para cada posição de bit:
0+0=0
0+1=1
1+0=1
1+1=0 (sem transporte)

A subtração é idêntica:
10011011
-11001010
--------
01010001
--------
com
0-0=0
0-1=1 (automaticamente alinhado)
1-0=1
1-1=0

De fato, na aritmética CRC a adição e a subtração são equivalentes à operação XOR, e a operação XOR é o seu próprio inverso. Isto efetivamente reduz as operações da primeira potência (adição e subtração) a uma simples operação que é o seu próprio inverso. Esta é uma propriedade muito conveniente da aritmética. Pelo colapso da adição e da subtração, a aritmética descarta qualquer noção de magnitude que esteja além do seu bit 1 de mais alta posição. Apesar de parecer claro que 1010 é maior do que 10, já não se pode mais dizer com certeza que 1010 é maior que 1001. Para verificar isto, observe que você pode ir de 1010 a 1001 tanto pela adição quanto pela subtração da mesma quantidade:

1010 = 1010 + 0011
1010 = 1010 - 0011

Isto torna qualquer noção de sequência uma coisa sem sentido.

Tendo definido a adição, podemos agora prosseguir para multiplicação e divisão. A multiplicação é absolutamente direta, sendo a soma do primeiro número, deslocado conforme o segundo número.

1101
x 1011
----
1101
1101.
0000..
1101...
-------
1111111 Observação: a soma utiliza adição CRC
-------

A divisão já é um pouco mais intrincada, porque precisamos saber quando “um número é divisível por outro”. Para fazer isto, lançamos mão da definição enfraquecida de magnitude estabelecida há pouco: X é igual a ou maior que Y SE o bit 1 de mais alta posição de X está na mesma posição, ou em uma posição mais alta, que o bit 1 de mais alta posição de Y.
Veja uma divisão inteiramente resolvida (extraída de [Tanenbaum81]):

1100001010
_______________
10011 ) 11010110110000
10011,,.,,....
-----,,.,,....
10011,.,,....
10011,.,,....
-----,.,,....
00001.,,....
00000.,,....
-----.,,....
00010,,....
00000,,....
-----,,....
00101,....
00000,....
-----,....
01011....
00000....
-----....
10110...
10011...
-----...
01010..
00000..
-----..
10100.
10011.
-----.
01110
00000
-----
1110 = Resto

É isto mesmo. Antes de irmos além, entretanto, vale a pena brincarmos um pouco mais com esta aritmética, para nos habituarmos com ela.
Já brincamos um pouco com a adição e a subtração, observando que são a mesma coisa. Aqui, no entanto, devemos observar que nesta aritmética A+0=A e A-0=A. Esta propriedade óbvia será muito útil mais adiante.

Lidando com a multiplicação CRC e com a divisão CRC, é útil dar um pouco mais de atenção aos conceitos de MÚLTIPLO DE   e   DIVISÍVEL POR.

Se um número A é múltiplo de B, o que isto significa em aritmética CRC é que é possível construir A a partir de zero executando a operação XOR em vários deslocamentos de B. Por exemplo, se A é 0111010110 e B é 11, poderíamos construir A a partir de B conforme demonstrado a seguir:

0111010110
= .......11.
+ ....11....
+ ...11.....
.11.......

Entretanto, se A for 0111010111, não será possível construí-lo a partir de vários deslocamentos de B (você consegue ver por que? – veja mais adiante). E então diz-se que não é divisível por B na aritmética CRC.

Portanto, vemos que a aritmética CRC é basicamente uma questão de executar operações XOR sobre valores particulares, em vários iterações de deslocamentos.


6. Um exemplo inteiramente resolvido:
-------------------------------------

Tendo definido a aritmética CRC, podemos agora estruturar uma operação CRC simplesmente como uma divisão, porque é só o que esta aritmética é realmente! Esta seção completa os detalhes, e apresenta um exemplo.

Para executar um cálculo CRC, precisamos escolher um divisor. Na linguagem de marketing da matemática, diz-se que o divisor é o “polinômio gerador”, ou simplesmente o “polinômio”, e é um parâmetro chave de qualquer algoritmo CRC. Provavelmente seria mais amigável denominar o divisor de alguma outra coisa, mas a linguagem dos polinômios é tão profundamente enraizada neste campo, que evitá-la agora criaria muita confusão. Como compromisso, nós nos referiremos aos polinômios CRC como “poli”. Apenas pense neste número como uma espécie de papagaio. “Olá, poli!”.

Você pode escolher qualquer poli, e daí tirar um algoritmo. Mas, alguns polis são melhores que outros, assim será mais inteligente procurar fazer uso dos que já foram tentados e testados. Uma seção mais adiante tratará deste aspecto.

O comprimento (posição mais alta de um bit 1) do poli é muito importante, porque ele domina todo o cálculo. Como método, em geral escolhem-se comprimentos de 16 ou 32 para simplificar a implementação em computadores modernos. O comprimento de um poli é a posição mais alta real do bit de maior valor. Por exemplo, o comprimento de 10011 é 4, não 5. Para fins de exemplo, vamos escolher um poli de 1011 (de comprimento C de 4). Tendo escolhido um poli, podemos prosseguir com os cálculos. Estes cálculos são simplesmente uma divisão (na aritmética CRC) da mensagem pelo poli. O único truque é que W bits zero são anexados ao final da mensagem, antes de o CRC ser calculado. Assim, temos:

Mensagem original : 1101011011
Poli : 10011
Mensagem após acrescentar W zeros: 11010110110000

Agora, nós simplesmente dividimos a mensagem aumentada pelo poli, utilizando a aritmética CRC. Isto é a mesma divisão de antes:

1100001010 = Quociente (ninguém se importa com o quociente)
_______________
10011 ) 11010110110000 = Mensagem aumentada (1101011011 + 0000)
=Poli 10011,,.,,....
-----,,.,,....
10011,.,,....
10011,.,,....
-----,.,,....
00001.,,....
00000.,,....
-----.,,....
00010,,....
00000,,....
-----,,....
00101,....
00000,....
-----,....
01011....
00000....
-----....
10110...
10011...
-----...
01010..
00000..
-----..
10100.
10011.
-----.
01110
00000
-----
1110 = Resto = O CHECKSUM!!!!

A divisão produz um quociente (que jogamos fora), e um resto, que é o checksum calculado. Isto encerra o cálculo. Em geral, o checksum é então acrescentado ao final da mensagem, e o resultado é transmitido. Neste caso, a transmissão seria
11010110111110. Na outra extremidade, o receptor pode fazer uma, de duas coisas:
a. Separar a mensagem e o checksum. Calcular o checksum da mensagem (depois de acrescentar os C zeros no final da mesma), e comparar os dois checksums.
b. Calcular o checksum da string inteira (sem acrescentar os zeros), e ver se resulta em zero!

Estas duas opções são equivalentes. Entretanto, na próxima seção assumiremos a opção b porque isto torna a matemática associada mais clara e limpa.

Sumário da operação dos algoritmos da classe CRC:
1. Escolha um comprimento W e um poli G (de comprimento W).
2. Acrescente W zeros ao final da mensagem. Chame isto de M’.
3. Divida M’ por G utilizando aritmética CRC. O resto é o checksum.
É tudo o que há para este assunto.






7. Escolhendo um Poli
---------------------

Escolher um poli é meio que uma arte negra, e indicamos ao leitor consultar
[Tanenbaum81] (p.130-132), que contém uma discussão muito clara deste tópico. Esta seção tem meramente o objetivo de instilar o medo da morte em qualquer um que ache muito divertida a idéia de construir o seu próprio poli. Se não importa a você saber o porquê de um poli ser melhor do que outro, e você só quer aprender sobre implementações de alta velocidade, escolha um dos polis aritmeticamente excelentes listados ao final desta seção, e pule para a próxima.

Para começar, observe que a mensagem transmitida T é um múltiplo do poli. Para ver isto, note que 1) os últimos W bits de T são o resto, após dividir-se a mensagem aumentada (com zeros, lembre-se) pelo poli e 2) a adição é o mesmo que a subtração, e então somar o resto eleva o valor para o próximo múltiplo. Agora perceba que, se a mensagem transmitida for corrompida na transmissão, o conteúdo que receberemos será T+E, onde E é um vetor erro e + é uma adição CRC (isto é, um XOR). Ao receber a mensagem, o receptor divide T+E por G. Como T mod G é 0, (T+E) mod G = E mod G. Portanto, a capacidade do poli que escolhemos de pegar tipos particulares de erros será determinada pelo conjunto de múltiplos de G, para qualquer corrupção E que seja múltiplo de G que não seja detectada. Nossa tarefa, então, é encontrar classes de G cujos múltiplos pareçam o menos possível como ruído da linha (que é o que estará criando as corrupções). Assim, vamos examinar os tipos de ruídos de linha que podemos esperar.

ERRO DE BIT ÚNICO: Um erro de bit único significa E=10000...0000. Podemos assegurar que esta classe de erro sempre seja detectada, tendo certeza de que G tem pelo menos dois bits com o valor 1. Qualquer valor de G será obtido utilizando deslocamento e soma, e é impossível construir um valor com um único bit deslocando e somando um valor simples com mais de um bit ligado, porque os dois bits finais sempre vão persistir.

ERROS DE DOIS BITS: Para detectar todos os erros da forma 100...000100...000 (isto é, E contém dois bits 1) escolha um G que não tenha múltiplos que sejam 11, 101, 1001, 10001, 100001, etc. Não está claro para mim como alguém se ocupa desta tarefa (não tenho o embasamento da matemática pura), mas Tanenbaum nos garante que este G existe, os G com bits 1 ligados (15, 14, 1) como exemplos de G que não dividem nenhum valor menor que 1...1, onde ... são 32767 zeros.

ERROS COM UM NÚMERO ÍMPAR DE BITS: podemos pegar todas as corrupções onde E tem um número ímpar de bits, escolhendo um G que tem um número ímpar de bits. Para verificar isto, observe que 1) a multiplicação CRC é simplesmente a aplicação da operação XOR com um valor constante a um registrador em várias iterações,  2) a operação XOR é simplesmente uma operação de bit-flip e 3) se você executa uma operação XOR com um valor par de bits em um registrador, a quantidade ímpar de bits 1 no registrador permanece invariável. Exemplo: começando com E=111, tente mudar todos os três bits para zero, pela aplicação repetida da operação XOR sobre 11 em uma das duas iterações (isto é, “E=E XOR 011” e “E=E XOR 110”). Isto é bastante isomorfo à brincadeira de festas “o que há no copo”, onde você desafia alguém a descobrir o conteúdo de três copos pela aplicação repetida da operação de descobrir o conteúdo de dois quaisquer deles. A maioria dos polis CRC mais  utilizados contém um número par de bits 1. (Observação: Tanenbaum afirma, mais especificamente, que todos os erros com um número ímpar de bits podem ser detectados pelo uso de um G múltiplo de 11).

ERROS DE ESTOURO: Um erro de estouro tem a aparência E=000...000111...11110000.00. Isto é, E consiste de um valor em que todos os bits estão zerados, exceto por uma “descarga” de 1s em algum lugar dentro desta sequência de zeros. Isto pode ser redistribuído como E=(10000...00)(1111111...111), onde há Z zeros na parte ESQUERDA e n 1s na parte DIREITA. Para pegar erros deste tipo, simplesmente fixamos em 1 o valor do bit mais baixo. Isto assegura que a parte ESQUERDA não pode ser um fator de G. Então, uma vez que G é mais comprido do que a parte DIREITA, o erro será detectado. Veja Tanenbaum para uma explicação mais completa e mais clara deste ponto; minha explicação não ficou muito nítida. Observação: Tanenbaum assevera que a probabilidade de um estouro de comprimento maior do que W chegar ao seu destino é de (0,5)^C.

Isto encerra a seção sobre a refinada arte de selecionar polis.

Alguns dos polis mais utilizados são:
16 bits: (16,12,5,0) [X25 standard]
(16,15,2,0) ["CRC-16"]
32 bits: (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) [Ethernet]


8. Uma Implementação CRC Direta
-------------------------------

Este é o fim da teoria; agora, vamos para a implementação. Para começarmos, examinaremos uma aplicação absolutamente entediante, que é uma implementação direta de baixa velocidade e não utiliza nenhuma técnica de aceleração da velocidade da comunicação. Então, nós vamos transformar progressivamente este programa, até termos em mãos o código compacto orientado para tabelas que todos nós conhecemos e amamos, e que alguns de nós gostariam de entender.

Para implementar um algoritmo CRC, tudo que temos que fazer é implementar uma divisão CRC. Há duas razões por que não podemos simplesmente utilizar a instrução de divisão da máquina, qualquer que seja esta nossa máquina. A primeira, é que temos que executar a divisão na aritmética CRC. A segunda, é que o dividendo poderá ter o comprimento de 10 megabytes, e os processadores atuais não têm registradores tão grandes. Para implementar uma divisão CRC, temos que alimentar a mensagem através de um registrador de divisão. Neste ponto, temos que ser absolutamente precisos sobre os dados da mensagem. Em todos os exemplos abaixo, a mensagem será considerada como sendo um fluxo de bytes (cada 8 bits) com o bit 7 de cada byte sendo considerado o bit mais significativo (MSB – do inglês “most significant bit”). O fluxo de bits formado com estes bytes será o fluxo de bits com o MSB (bit 7) do primeiro byte primeiro, indo para o bit 0 do primeiro byte, então o MSB do segundo byte, e assim por diante.

Com isto em mente, podemos esboçar uma implementação da divisão CRC. Para fins de exemplo, considere um poli com W=4 e o poli=10111. Assim, para executar a divisão precisamos de um registrador de 4 bits:

3 2 1 0 Bits
+---+---+---+---+
Pop! <-- | | | | | <----- Mensagem aumentada
+---+---+---+---+
1 0 1 1 1 = O poli

(Lembrete: A mensagem aumentada é a mensagem seguida de W bits zero.) Para executar a divisão, execute a seguinte sequência:
Carregue o registrador com bits zero.
Aumente a mensagem, anexando W bits zero ao final desta.

While (mais bits da mensagem)
Begin
Desloque o conteúdo do registrador em um bit, lendo o próximo bit da mensagem aumentada para o bit de posição 0 do registrador. If (um bit 1 eliminado do registrador no passo 3)
Register = Register XOR Poly.
End

Agora, o registrador contém o resto.

(Observação: Na prática, a condição IF pode ser testada verificando-se o bit mais alto do registrador, antes de executar o deslocamento.)

Denominaremos este algoritmo “SIMPLES”.

Isto pode parecer pouco preciso, mas tudo que estamos fazenda é “subtrair” várias potências (isto é, deslocamentos) do poli fora da mensagem, até que não haja mais nada a não ser o resto. Procure algum material de estudo sobre a divisão longa, se não estiver entendendo este ponto. Deve estar claro que o algoritmo acima funcionará para qualquer comprimento W.



9. Uma Implementação Orientada a Tabelas
----------------------------------------

O algoritmo SIMPLES acima é um bom ponto de início, porque corresponde diretamente à teoria apresentada até agora, e porque é muito SIMPLES. No entanto, pelo fato de operar no nível do bit, torna-se mais trabalhoso para ser codificado (mesmo em C), e ineficiente de executar (executará um loop para cada bit). Para torná-lo mais rápido, precisamos encontrar uma forma de tornar o algoritmo capaz de processar a mensagem em unidades maiores do que um bit. As quantidades candidatas são os nibbles (4 bits), os bytes (8 bits), palavras (16 bits) e palavras longas (32 bits), ou maiores, se isto for possível. Destas, seria melhor evitar a opção de 4 bits porque não corresponde à família dos bytes. No mínimo, qualquer otimização deveria permitir-nos operar em termos do byte, e de fato a maioria dos algoritmos orientados a tabelas operam a um byte por vez.

Para fins de discussão, vamos alterar de um poli de 4 bits para um de 32 bits. A aparência de nosso registrador permanece a mesma, exceto pelo fato de que os espaços representam bytes em vez de bits, e o poli tem 33 bits (um bit 1 implícito no alto, e 32 bits “ativos”) (W=32)

3 2 1 0 Bytes
+----+----+----+----+
Pop! <-- | | | | | <----- Mensagem aumentada
+----+----+----+----+
1<------32 bits------>

O algoritmo SIMPLES ainda se aplica. Vamos examinar o que ele faz.

Imagine que o algoritmo SIMPLES está em pleno processamento, e considere que os 8 bits mais altos do registrador de 32 bits (byte 3) tenham os seguintes valores:
t7 t6 t5 t4 t3 t2 t1 t0

Na próxima iteração do SIMPLE, t7 irá determinar se será executada a operação XOR do poli no registrador inteiro. Se t7=1, isto será feito, de outro modo não será. Suponha que os oito bits mais altos do poli sejam g7 g6 ... g0, então após a próxima iteração, o byte mais alto será:
t6 t5 t4 t3 t2 t1 t0 ?? + t7 * (g7 g6 g5 g4 g3 g2 g1 g0) [Resto: + é XOR]
O NOVO bit mais alto (que controlará o que acontece na próxima iteração) agora tem o valor t6 + t7*g7. O importante de se prestar atenção aqui é que, do ponto de vista da informação, toda a informação necessária para se calcular o NOVO bit mais alto já estava presente nos dois bits mais altos do byte mais alto original. Da mesma forma, o PRÓXIMO pode ser calculado antecipadamente APENAS com os três bits mais altos t7, t6 e t5. De fato, em geral, o valor do bit mais alto no registrador em k iterações pode ser calculado dos k bits mais altos do registrador. Vamos considerar isto como uma certeza, por enquanto.

Assuma, por um momento, que usamos os 8 bits mais altos do registrador para calcular o valor do bit mais alto do registrador nas próximas 8 iterações. Suponha que resolvemos as próximas 8 iterações usando os valores calculados (que talvez poderíamos armazenar em um registrador de um byte, e deslocar para ir eliminando cada bit). Então, percebemos três coisas:
* O byte mais alto do registrador agora não tem importância. Não importa quantas vezes ou em qual iteração é executada a operação XOR entre o poli e os 8 bits mais altos, todos eles serão deslocados de tal maneira que “sairão” do registrador pelo lado direito nas próximas 8 iterações, de qualquer maneira.
* O bits que permanecerem serão deslocados em uma posição à esquerda, e o byte mais à direita do registrador será deslocado para se tornar o próximo byte E
* Enquanto tudo isto está acontecendo, o registrador será sujeito a uma série de operações XOR de acordo com os bits do byte de controle pré-calculado.

Agora, considere o efeito da operação XOR sobre um valor constante em várias iterações em um registrador. Por exemplo:

0100010 Registrador
...0110 XOR este
..0110. XOR este
0110... XOR este
-------
0011000
-------

O importante aqui é que você pode executar a operação XOR com valores constantes sobre um registrador tanto quanto o seu coração assim o pedir e, ao final, haverá um valor que, quando utilizado em uma operação XOR com o registrador original, produzirá o mesmo efeito de todos os outros XOR.

Talvez você possa ver a solução, agora. Juntando todas as peças, temos um algoritmo que funciona assim:


While (mensagem aumentada ainda não terminou)
Begin
Examine o byte mais alto do registrador
Calcule o byte de controle a partir do byte mais alto do registrador
Some todos os polis das várias iterações que deverão ser processadas com o operador lógico XOR sobre o registrador, de acordo com o byte de controle
Desloque o registrador um byte para a esquerda, lendo o próximo byte da mensagem para o byte mais à direita do registrador
Execute a operação XOR sobre o registrador, utilizando os polis somados
End

Da forma como está, isto não é muito melhor do que o algoritmo SIMPLES.

Mas podemos ver que a maioria dos cálculos podem ser pré-computados e montados em uma tabela. Como resultado, O algoritmo acima pode ser reduzido a:

While (mensagem aumentada ainda não terminou)
Begin
Top = top_byte(Register);
Register = (Register << 24) | próximo byte da mensagem aumentada;
Register = Register XOR precomputed_table[Top];
End
Aí está! Se você compreende isto, então captou a idéia principal dos algoritmos CRC baseados em tabelas. O fluxo acima é um algoritmo muito eficiente que requer apenas um deslocamento, um OR, um XOR, e uma pesquisa em tabela por byte. Graficamente, pode ser ilustrado da seguinte forma:

3 2 1 0 Bytes
+----+----+----+----+
+-----<| | | | | <----- Mensagem aumentada
| +----+----+----+----+
| ^
| |
| XOR
| |
| 0+----+----+----+----+ Algoritmo
v +----+----+----+----+ ---------
| +----+----+----+----+ 1. Desloque o registrador um byte para a esquerda,
| +----+----+----+----+    para a esquerda, lendo o próximo
| +----+----+----+----+    byte da mensagem.
| +----+----+----+----+ 2. Use o byte mais alto que saiu agora
| +----+----+----+----+    do registrador para indexar a tabela
+----->+----+----+----+----+              de 256 valores de 32 bits.
+----+----+----+----+ 3. Execute a operação XOR do valor da tabela
+----+----+----+----+    sobre o registrador.
+----+----+----+----+ 4. Se houver mais bytes na mensagem aumentada
+----+----+----+----+       vá para 1.
255+----+----+----+----+

Em C, o loop principal do algoritmo parece-se com o seguinte:

r=0;
while (len--)
{
byte t = (r >> 24)&0xFF;
r = (r << 8) | *p++;
r^=table[t];
}

Onde len é o comprimento em bytes da mensagem aumentada, p aponta para a mensagem aumentada, r é o registrador, t é uma variável temporária, e table é a tabela computada. Este código pode ser escrito de maneira mais ilegível ainda, como se vê abaixo:

r=0; while (len--) r = ((r << 8) | *p++) ^ t[(r >> 24) & 0xFF];

Este é um loop muito limpo e eficiente, embora não seja nada óbvio para o observador casual, não versado na teoria CRC. Chamaremos a este processo de algoritmo de TABELA.



10. Uma Implementação Orientada a Tabelas Ligeiramente Adaptada
-----------------------------------------------------------------

A despeito da beleza concisa da linha

r=0; while (len--) r = ((r << 8) | *p++) ^ t[(r >> 24) & 0xFF];

os hackers otimizadores não poderiam deixá-la em paz. O problema, veja você, é que o loop opera sobre a mensagem AUMENTADA e, para utilizar este código, você tem que acrescentar W/8 bytes zero ao final da mensagem, antes de apontar p para ela. Dependendo do ambiente de execução, isto poderá ou não ser um problema; se o bloco de dados nos foi entregue por algum outro código, poderia ser um GRANDE problema. Uma alternativa é simplesmente acrescentar a linha seguinte ao final do loop acima, uma vez para cada byte zero:

for (i=0; i<< 8) ^ t[(r >> 24) & 0xFF];

Esta parece uma solução mentalmente sadia o suficiente para mim. Mas, às custas adicionais da clareza (que, você deve admitir, é um artigo para bons sobressaltos neste código), podemos reorganizar um pouco mais este artigo para bem de evitar tanto o aumento da mensagem com bytes zero, quanto o processamento explícito dos bytes zero no final, conforme acima. Para explicar esta otimização, voltamos ao diagrama de processamento apresentado anteriormente:

3 2 1 0 Bytes
+----+----+----+----+
+-----<| | | | | <----- Mensagem aumentada
| +----+----+----+----+
| ^
| |
| XOR
| |
| 0+----+----+----+----+ Algoritmo
v +----+----+----+----+ ---------
| +----+----+----+----+ 1. Desloque o registrador um byte para a esquerda,
| +----+----+----+----+    para a esquerda, lendo o próximo
| +----+----+----+----+    byte da mensagem.
| +----+----+----+----+ 2. Use o byte mais alto que saiu agora
| +----+----+----+----+    do registrador para indexar a tabela
+----->+----+----+----+----+  de 256 valores de 32 bits.
+----+----+----+----+ 3. Execute a operação XOR do valor da tabela
+----+----+----+----+    sobre o registrador.
+----+----+----+----+ 4. Se houver mais bytes na mensagem aumentada
+----+----+----+----+       vá para 1.
255+----+----+----+----+

Agora, observe os seguintes fatos:

PEDAÇO FINAL: Os bytes zero C/4 aumentados que aparecem no final da mensagem serão alimentados no registrador pela direita, da mesma forma como todos os outros bytes são, mas o seu valor (0) não terá efeito sobre o que quer que esteja no registrador porque 1) a operação XOR com zero não altera o byte de destino e 2) os quatro bytes nunca são propagados para fora do lado esquerdo do registrador, onde os seus valores de zero poderiam ter algum tipo de influência. Portanto, a única função dos bytes zero W/4 aumentados é conduzir o cálculo a outros ciclos de bytes W/4, para que a parte final dos dados REAIS percorram todo o caminho através do registrador.

CABEÇALHO: Se o valor inicial do registrador é zero, as primeiras quatro iterações do loop terão o único efeito de deslocar os primeiros quatro bytes da mensagem aumentada para dentro do registrador pela direita. Isto ocorre porque os primeiros 32 bits de controle são todos zero, e então nenhuma operação XOR é executada sobre o registrador. Mesmo se o valor inicial não for zero, as iterações dos primeiros 4 bytes do algoritmo terão o único efeito de deslocar os primeiros 4 bytes da mensagem para dentro do registrador, e então executar a operação XOR deles sobre algum valor constante (esta é uma função do valor inicial do registrador).
Estes fatos, combinados com a propriedade do XOR

 (A xor B) xor C = A xor (B xor C)

significam que os bytes da mensagem não precisam realmente transitar pelos W/4 bytes do registrador. Ao invés disto, pode ser executada uma operação XOR deles sobre o byte mais alto, imediatamente antes de este ser usado para indexar a tabela de busca. Isso nos leva à seguinte versão modificada do algoritmo:

+-----
|
v 3 2 1 0 Bytes
| +----+----+----+----+
XOR----<| | | | |
| +----+----+----+----+
| ^
| |
| XOR
| |
| 0+----+----+----+----+ Algoritmo
v +----+----+----+----+ ---------
| +----+----+----+----+ 1. Desloque o registrador um byte para a esquerda,
| +----+----+----+----+    para a esquerda, lendo o próximo
| +----+----+----+----+    byte da mensagem.
| +----+----+----+----+ 2. Execute a operação XOR sobre o byte mais alto que
| +----+----+----+----+    saiu agora do registrador, sobre o próximo byte
+----->+----+----+----+----+ da mensagem para produzir um índice
+----+----+----+----+        para a tabela ([0,255]).
+----+----+----+----+ 3. Execute uma operação XOR do valor da tabela
+----+----+----+----+    sobre o registrador.
+----+----+----+----+ 4. Se houver mais bytes na mensagem aumentada
255+----+----+----+----+ vá para 1.


Observação: O valor inicial do registrador para este algoritmo deve ser o valor inicial do registrador para o algoritmo anterior, alimentado através da tabela quatro vezes.

Observação: A tabela é tal que, se o algoritmo anterior utilizou zero, o novo algoritmo também utilizará. O algoritmo é IDÊNTICO, e produzirá resultados IDÊNTICOS. O código em C terá a seguinte aparência:

r=0; while (len--) r = (r<<8) ^ t[(r >> 24) ^ *p++];

e ESTE é o código que você provavelmente vai encontrar nas implementações CRC atuais baseadas em tabelas. Algumas máscaras FF poderão ser necessárias aqui e ali para fins de portabilidade mas, basicamente, o loop acima É O QUE É. Chamaremos a este o ALGORITMO DE TABELAS DIRETO. Durante o processo de tentar entender isto tudo, eu administrei para derivar o algoritmo SIMPLES e a versão orientada para tabelas derivada deste algoritmo. No entanto, quando eu comparei meu código com o código encontrado em implementações reais, fiquei completamente perdido e embaraçado por verificar que a operação XOR estava sendo executada na extremidade errada do registrador! Demorou um bocado até eu me dar conta de que o algoritmo “deles” e o meu eram, na verdade, o mesmo. Parte dos motivos pelos quais estou escrevendo este artigo é que, se a ligação entre a divisão e meu código anterior orientado a tabelas é apenas vagamente aparente, qualquer ligação some completamente quando você começa a movimentar bytes na “extremidade errada” do registrador. Tudo parece estar errado! Se você já passou por isto, então não apenas compreendeu a teoria, a prática, a prática otimizada, como também entendeu o verdadeiro código com o qual é mais provável você se deparar. Isto poderia se tornar mais complicado? Sim, poderia.
11. Implementações Orientadas a Tabelas “Refletidas”
----------------------------------------------------

A despeito do fato de que o código acima provavelmente já está tão otimizado quanto poderia chegar a estar, isto não evitou que indivíduos empreendedores tornassem as coisas ainda mais complicadas. Para entender como isto aconteceu, temos que entrar no mundo do hardware.

DEFINIÇÃO: Um valor/registrador está refletido se os seus bits são trocados ao redor do seu centro. Por exemplo: 0101 é a reflexão de 4 bits de 1010.
0011 é a reflexão de 1100.
0111-0101-1010-1111-0010-0101-1011-1100 é a reflexão de
0011-1101-1010-0100-1111-0101-1010-1110.

Verificamos, portanto, que as UARTs (aqueles pequenos chips que executam IO serial) têm o hábito de transmitir cada byte com o bit menos significativo (bit 0) primeiro e o bit mais significativo (bit 7) por último (isto é, refletido). Um efeito desta convenção, é que os engenheiros de hardware que estão construindo calculadoras CRC que operam no nível do bit realizaram os cálculos CRC de fluxos de bytes com cada um dos bytes refletidos dentro de si mesmo. Os bytes são processados na mesma ordem, mas os bits em cada byte são permutados; agora, o bit 0 é o bit 7, o bit 1 é o bit 6, e assim por diante. Isto não teria muita importância, se esta convenção fosse restrita à terra do hardware. Entretanto, parece que em algum momento alguns destes valores CRC apresentaram-se no nível do software, e alguém teve de escrever algum código que iria operar em conjunto com o cálculo CRC feito no hardware.

Nesta situação, um engenheiro de software sadio normal iria simplesmente refletir cada byte antes d processá-lo. Mas, parece que estes engenheiros de software sadios normais andavam bem escassos porque, em vez de refletir os bytes, quem quer que fosse o responsável, manteve os bytes como estavam e refletiu o mundo, chegando ao seguinte algoritmo “refletido”, que é idêntico ao anterior exceto pelo fato de que tudo está refletido exceto os bytes de entrada.


Mensagem (não aumentada) >-----+
|
Bytes 0 1 2 3 v
+----+----+----+----+ |
| | | | |>----XOR
+----+----+----+----+ |
^ |
| |
XOR |
| |
+----+----+----+----+0 |
+----+----+----+----+ v
+----+----+----+----+ |
+----+----+----+----+ |
+----+----+----+----+ |
+----+----+----+----+ |
+----+----+----+----+ |
+----+----+----+----+<-----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+255


Observações:

* A tabela é idêntica à do algoritmo anterior, exceto pelo fato de que cada entrada foi refletida.
* O valor inicial do registrador é o mesmo do algoritmo anterior, exceto pelo fato de que foi refletido.
* Os bytes da mensagem são processados na mesma ordem que antes (isto é, a mensagem em si mesma não é refletida).
* Os bytes da mensagem, eles próprios, não precisam ser explicitamente refletidos, porque tudo o mais foi refletido!

Ao final da execução, o registrador contém a reflexão do valor CRC final (resto). Na verdade, eu estou sendo um tanto severo sobre o que engendrou isto, porque parece que as implementações de hardware do algoritmo CRC utilizaram o valor de checksum refletido, produzindo então um CRC refletido válido. De fato, refletir o mundo provavelmente foi uma boa solução de engenharia – embora uma solução confusa.

Chamaremos a isto o algoritmo REFLETIDO.

Quer isto tenha feito sentido ou não na época, o efeito de ter algoritmos refletidos circulando pelos sites de FTP no mundo foi que metade das implementações que as pessoas utilizam são refletidas, e a outra metade não é. È, verdadeiramente, uma grande, imensa, terrível confusão. Particularmente, para mim pareceria que o leitor casual que tenta entender uma implementação de software orientada para tabelas, refletida, teria a chance de Buckley de algum dia relacionar o código ao conceito de divisão binária de módulo 2.

Não poderia se tornar mais confuso do que isto, poderia? Sim, poderia.



12. Polis “Reversos”
--------------------

Como se uma implementação refletida não fosse o suficiente, há outro conceito circulando pelo mundo, que torna a situação bizarramente mais confusa. É o conceito de Polis reversos.

O que ocorre, é que a reflexão de bons polis tendem a ser bons polis, também! Isto é, se G=11101 é um bom valor para um polinômio, então 10111 também será. Como consequência, parece que cada vez que uma organização (como por exemplo a CCITT) padroniza o uso de um poli particularmente bom (“polinômio”), os outros, no mundo real, também não podem deixar em paz a reflexão deste polinômio. Eles simplesmente TÊM que utilizá-la. Como resultado, o conjunto de polis “padrão” tem um correspondente conjunto de reflexões, que também estão em uso. Para evitar confusão, chamaremos a estes de polinômios “reversos”.

X25 padrão: 1-0001-0000-0010-0001
X25 reverso: 1-0000-1000-0001-0001
CRC16 padrão: 1-1000-0000-0000-0101
CRC16 reverso: 1-0100-0000-0000-0011

Observe que aqui é o poli inteiro que está sendo refletido/revertido, não apenas os W bits mais baixos. Esta é uma distinção importante. No algoritmo refletido descrito na seção anterior, o poli utilizado no algoritmo refletido era realmente idêntico ao utilizado no algoritmo não refletido; a única coisa que tinha acontecido era que os bytes tinham sido efetivamente refletidos. Desta forma, todos os números de 16 bits e de 32 bits no algoritmo tinham que ser refletidos. Ao contrário disto, o poli INTEIRO inclui o bit 1 implícito no alto, e assim reverter o poli não é a mesma coisa que refletir os seus 16 ou 32 bits mais baixos. O desfecho de tudo isto é que um algoritmo refletido não é equivalente ao algoritmo original, com o poli refletido. Na verdade, isto seria provavelmente menos confuso se eles fossem duais.

Se isto tudo parece um pouco sem clareza, não se preocupe, porque vamos colocar tudo sito em ordem logo, logo. Só precisamos de mais uma seção antes disto.



13. Valor Inicial e Valor Final
-------------------------------

Além da complexidade já vista, os algoritmos CRC diferem uns dos outros em dois outros aspectos:
* O valor inicial do registrador
* O valor a ser utilizado na operação XOR executada sobre o valor final do registrador.

Por exemplo, o algoritmo “CRC32” inicializa o registrador com FFFFFFFF, e executa a operação XOR sobre o valor final do registrador com FFFFFFFF. A maioria dos algoritmos CRC inicializa o registrador com zero. No entanto, alguns inicializam com um valor não-zero. Em teoria (isto é, sem se presumir nada sobre a mensagem), o valor inicial não afeta a força do algoritmo CRC, sendo que o valor inicial meramente provê um ponto de partida fixo a partir do qual o valor do registrador pode progredir. No entanto, na prática algumas mensagens são mais prováveis do que outras, e é mais inteligente inicializar o registrador do algoritmo CRC com um valor que não contém “pontos cegos” que sejam prováveis de ocorrer na prática. Por “ponto cego” queremos dizer uma sequência de bytes na mensagem que não fazem o registrador mudar o seu valor. Particularmente, qualquer algoritmo CRC que inicializa o seu registrador em zero terá um ponto cego de zero quando começa a processar, e não será capaz de contar uma execução inicial de bytes zero. Como uma execução inicial de bytes zero é muito comum nas mensagens reais, seria mais inteligente inicializar o registrador do algoritmo com um valor não-sero.



14. Definindo Algoritmos Absolutamente
--------------------------------------

Neste ponto, já cobrimos todos os diferentes aspectos dos algoritmos CRC orientados para tabelas.Como existem muitas variações destes algoritmos, vale a pena estabelecer uma nomenclatura para eles. É o que esta seção tenta fazer.

Vimos que os algoritmos CRC variam em:

* Comprimento do poli (polinômio)
* Valor do poli
* Valor inicial do registrador
* A questão sobre se os bits de cada byte são refletidos antes de serem processados
* A questão sobre se o algoritmo alimenta os bytes de entrada no registrador, ou executa a operação XOR sobre um byte em uma extremidade e então pesquisa diretamente na tabela.
* A questão sobre se o valor final do registrador deve ser revertido (como nas versões refletidas)
* O valor da operação XOR sobre o valor final do registrador.

Para podermos falar sobre algoritmos CRC em particular, precisamos ser capazes de defini-los com mais precisão do que isto. Por esta razão, a próxima seção procura fornecer um modelo parametrizado bem-definido para algoritmos CRC. Para nos referirmos a um algoritmo em particular, precisamos então simplesmente especificar o algoritmo em termos de parâmetros para o modelo.



15. Um Modelo Parametrizado Para Algoritmos CRC
-----------------------------------------------

Nesta seção, definimos um algoritmo CRC modelo parametrizado preciso que, para termos um nome melhor, chamaremos de “Algoritmo CRC Modelo Rocksoft^tm” (e por que não? Rocksoft^tm poderia dar bons resultados com um pouco de publicidade gratuita :-).

O aspecto mais importante do algoritmo modelo é que ele foca exclusivamente na funcionalidade, ignorando todos os detalhes de implementação. O objetivo do exercício é construir uma maneira de referirmo-nos precisamente a algoritmos CRC particulares, independentemente de o quanto confusamente eles são implementados. Para este fim, o modelo precisa ser tão simples e preciso quanto possível, com o mínimo de confusão possível.

O Algoritmo CRC Rocksoft^tm Modelo é baseado essencialmente no ALGORITMO DE TABELA DIRETO especificado anteriormente. No entanto, o algoritmo deve ser um pouco mais parametrizado para capacitá-lo a comportar-se do mesmo modo como alguns dos algoritmos mais enrolados que encontramos no mundo real lá fora.

Para habilitar o algoritmo a comportar-se como os algoritmos refletidos, nós criaremos uma opção booleana para refletir (processar, executar a reflexão) os bytes de entrada, e uma opção booleana para refletir (processar, executar a reflexão) o valor de saída do checksum. Estruturando a reflexão como uma transformação nos dados de entrada/saída, nós evitamos a confusão de mapear mentalmente os parâmetros dos algoritmos refletidos e não-refletidos.

Um parâmetro extra permite ao registrador do algoritmo ser inicializado com um valor particular. Mais um parâmetro ainda é submetido ao processamento de uma operação XOR com o valor final, antes de este valor final ser retornado (liberado como resultado do processamento).

Juntando todas estas peças, temos então os parâmetros necessários para o algoritmo:

NOME: É o nome dado ao algoritmo. Um valor string.

WIDTH: O comprimento do algoritmo, expresso em bits. È uma unidade a menos do que o comprimento do Poly.

POLY: Este parâmetro é o poli. É um valor binário, que deve ser especificado como um número hexadecimal. O bit mais alto do poli deve ser omitido. Por exemplo, se o poli é 10110, você deve especificar 6. Um aspecto importante deste parâmetro é que ele representa o poli não-refletido; o bit mais baixo deste parâmetro é sempre o LSB (least significant bit, bit menos significativo) do divisor durante a divisão, independentemente de se o algoritmo sendo modelado é refletido.

INIT: Este parâmetro especifica o valor inicial do registrador, quando o algoritmo começa. Este é o valor que deve ser atribuído ao registrador no algoritmo de tabela direta. No algoritmo de tabela, podemos pensar no registrador sempre começando com o valor zero, e uma operação XOR sendo executada com este valor sobre o registrador, após a iteração do enésimo bit. Este parâmetro deve ser especificado como um número hexadecimal.

REFIN: Este é um parâmetro booleano. Se for FALSE, os bytes de entrada são processados com o bit 7 sendo tratado como o bit mais significativo (MSB) e o bit 0 sendo tratado como o bit menos significativo. Se este parâmetro for TRUE, cada byte é refletido antes de ser processado.

REFOUT: Este é um parâmetro booleano. Se for FALSE, o valor final no registrador é alimentado diretamente ao estágio XOROUT. Caso contrário, se este parâmetro for TRUE, o valor final do registrador primeiro é refletido.

XOROUT: Este é um valor W-bit (comprimento, em bits) que deve ser especificado como um número hexadecimal. Deve ser executada uma operação XOR, com este valor, sobre o valor final do registrador (após a fase do REFOUT), antes de o valor ser retornado como o checksum oficial.

CHECK: Este campo não é estritamente parte da definição e, no caso de inconsistência entre este e o outro campo, o outro deve ter a precedência. Este campo é um valor de verificação, que pode ser utilizado como um validador fraco de implementações do algoritmo. O campo contém o checksum obtido quando a string ASCII “123456789” é alimentada através do algoritmo específico (isto é, 313233... – hexadecimal).


Com estes parâmetros definidos, o modelo agora pode ser usado para especificar um algoritmo CRC particular, exatamente. Veja abaixo uma especificação exemplo para uma forma bastante popular do algoritmo CRC-16:

Width : 16
Poly : 8005
Init : 0000
RefIn : True
RefOut : True
XorOut : 0000
Check : BB3D


16. Um Catálogo de Conjuntos de Parâmetros Para Padrões
-------------------------------------------------------

Neste ponto, eu gostaria de fornecer uma lista das especificações para algoritmos CRC utilizados comumente. No entanto, a maioria dos algoritmos com os quais tive contato até agora, são especificados de maneira tão vaga, que isto não foi possível. O que eu posso fornecer é uma lista de polis para vários padrões de CRC dos quais tive conhecimento:

Padrão X25 : 1021 [CRC-CCITT, ADCCP, SDLC/HDLC]
X25 reverso : 0811
Padrão CRC16 : 8005
CRC16 reverso : 4003 [LHA]
CRC32 : 04C11DB7 [PKZIP, AUTODIN II, Ethernet, FDDI]

Eu estaria interessado em saber de qualquer pessoa lá fora, quem poderia reunir e enfeixar o conjunto completo dos parâmetros do modelo, para qualquer um destes padrões. No entanto, um programa que andou circulando por aí parecia implicar as seguintes especificações. A questão, é se alguém poderia confirmá-las ou refutá-las, ou apresentar os valores de checksum (de maneira que codificar e calcular não me entediassem...).

Name : "CRC-16/CITT"
Width : 16
Poly : 1021
Init : FFFF
RefIn : False
RefOut : False
XorOut : 0000
Check : ?

Name : "XMODEM"
Width : 16
Poly : 8408
Init : 0000
RefIn : True
RefOut : True
XorOut : 0000
Check : ?

Name : "ARC"
Width : 16
Poly : 8005
Init : 0000
RefIn : True
RefOut : True
XorOut : 0000
Check : ?

Veja abaixo a especificação para o algoritmo CRC-32, que muitos relataram que é utilizado em PKZip, AUTODIN II, Ethernet, and FDDI.

Name : "CRC-32"
Width : 32
Poly : 04C11DB7
Init : FFFFFFFF
RefIn : True
RefOut : True
XorOut : FFFFFFFF
Check : CBF43926


17. Uma Implementação do Algoritmo Modelo
-----------------------------------------

Esta é uma implementação do algoritmo modelo na linguagem de programação C. A implementação consiste em um arquivo de header (.h) e um arquivo de implementação (.c).
Para ter certeza de que o código a seguir está funcionando, configure-o para os algoritmos CRC-16 e CRC-32 apresentados acima, e procure certificar-se de que eles produzem o checksum “CHECK” especificado quando a string de teste “123456789” é alimentada (veja discussão sobre este tópico em uma seção anterior, onde se fala sobre parâmetros para uma implementação parametrizada).


/******************************************************************************/
/* Começo de crcmodel.h */
/******************************************************************************/
/* */
/* Autor  : Ross Williams (ross@guest.adelaide.edu.au.). */
/* Data : 3 Junho 1993. */
/* Status : Domínio público. */
/* */
/* Descrição : Este é o arquivo header (.h) para a implementação de */
/* referência do Algoritmo CRC Modelo Rocksoft^tm. Para mais */
/* informações sobre o Algoritmo CRC Modelo Rocksoft^tm, veja o documento */
/* intitulado "Um Guia Indolor Para Algoritmos CRC De Detecção De Erros" */
/* de Ross Williams (ross@guest.adelaide.edu.au.). É muito provável que este */
/* documento esteja em "ftp.adelaide.edu.au/pub/rocksoft". */
/* */
/* Observação: Rocksoft é uma marca registrada de Rocksoft Pty Ltd, */
/* Adelaide, Australia. */
/* */
/******************************************************************************/
/* */
/* Como Usar Este Pacote */
/* --------------------- */
/* Passo 1: Declare uma variável de tipo cm_t. Declare outra variável */
/* (p_cm say) de tipo p_cm_t e inicialize-a para apontar para a primeira */
/* variável (por exemplo, p_cm_t p_cm = &cm_t). */
/* */
/* Passo 2: Atribua valores aos campos de parâmetros da estrutura. */
/* Se você não sabe o que atribuir, leia o documento mencionado acima. */
/* Por exemplo: */
/* p_cm->cm_width = 16; */
/* p_cm->cm_poly = 0x8005L; */
/* p_cm->cm_init = 0L; */
/* p_cm->cm_refin = TRUE; */
/* p_cm->cm_refot = TRUE; */
/* p_cm->cm_xorot = 0L; */
/* Observação: Poly é especificado sem o seu bit mais alto */
/* (18005 fica 8005). */
/* Note: Width é um bit a menos do que o comprimento do poli. */
/* */
/* Passo 3: Inicialize a instância com uma chamada cm_ini(p_cm); */
/* */
/* Passo 4: Processe zero ou mais bytes da mensagem executando zero ou mais */
/* chamadas sucessivas a cm_nxt. Exemplo: cm_nxt(p_cm,ch); */
/* */
/* Passo 5: Extraia o valor CRC a qualquer tempo chamando */
/*          crc = cm_crc(p_cm); */
/* Se o CRC for um valor de 16 bits, estará nos 16 bits mais baixos. */
/* */
/******************************************************************************/
/* */
/* Notas de Projeto */
/* ---------------- */
/* PORTABILIDADE: este pacote foi codificado muito conservadoramente, */
/* para que execute em tantas máquinas quanto possível. Por exemplo, todos */
/* os identificadores externos foram restritos a 6 caracteres, e todos os */
/* internos a 8 caracteres. O prefixo cm (para CRC model – modelo CRC) é */
/* utilizado como uma tentativa de evitar colisões de namespaces. Este */
/* pacote é independente de índios. */
/* */
/* EFICIÊNCIA: Este pacote (e sua interface) não é projetado para */
/* velocidade. O propósito deste pacote é funcionar como um modelo bem */
/* definido de referência para a especificação de algoritmos CRC. Se você */
/* deseja velocidade, invente uma implementação específica orientada */
/* a tabelas, conforme descrito no documento mencionado acima. Este pacote */
/* é projetado para validação, apenas; se você encontrou ou implementou um */
/* algoritmo CRC e gostaria de descrevê-lo como um conjunto de parâmetros */
/* para o Algoritmo CRC Modelo Rocksoft^tm, a sua implementação de algoritmo */
/* CRC deve comportar-se identicamente a este pacote, e sob estes */
/* parâmetros. */
/* */
/******************************************************************************/
/* O #ifndef a seguir engloba este arquivo inteiro de header, */
/* o que o torna idempotente. */
#ifndef CM_DONE
#define CM_DONE
/******************************************************************************/
/* As definições a seguir são extraídas de meu arquivo de estilos de header, */
/* que não seria nada prático distribuir juntamente com este pacote.  */
/* DONE_STYLE é o símbolo para idempotência utilizado em meu arquivo de */
/* estilos de header. */
#ifndef DONE_STYLE
typedef unsigned long ulong;
typedef unsigned bool;
typedef unsigned char * p_ubyte_;
#ifndef TRUE
#define FALSE 0
#define TRUE 1
#endif
/* Mude a segunda definição se você não tem protótipos */
#define P_(A) A
/* #define P_(A) () */
/* Remova o comentário desta definição se você não tem void */
/* typedef int void; */
#endif
/******************************************************************************/
/* Resumo de Tipos Para Um Modelo CRC
/* ---------------------------------- */
/* O commando type a seguir armazena o contexto de uma instância em execução */
/* do algoritmo modelo. A maioria dos campos são parâmetros do modelo, que */
/* devem ser inicializados antes da primeira chamada de */
/* inicialização a cm_ini. */
typedef struct
{
int cm_width; /* Parameter: Width in bits [8,32]. */
ulong cm_poly; /* Parameter: The algorithm's polynomial. */
ulong cm_init; /* Parameter: Initial register value. */
bool cm_refin; /* Parameter: Reflect input bytes? */
bool cm_refot; /* Parameter: Reflect output CRC? */
ulong cm_xorot; /* Parameter: XOR this to output CRC. */
ulong cm_reg; /* Context: Context during execution. */
} cm_t;
typedef cm_t *p_cm_t;
/******************************************************************************/
/* Funções Que Implementam O Modelo */
/* -------------------------------- */
/* As funções a seguir animam a abstração cm_t */
void cm_ini P_((p_cm_t p_cm));
/* Inicializa a instância argumento do modelo CRC */
/* Todos os campos parâmetro devem ser setados antes desta chamada
void cm_nxt P_((p_cm_t p_cm,int ch));
/* Processa um únici byte de mensagem [0,255]. */
void cm_blk P_((p_cm_t p_cm,p_ubyte_ blk_adr,ulong blk_len));
/* Processa um bloco de bytes de mensagem. */
ulong cm_crc P_((p_cm_t p_cm));
/* Retorna o valor CRC para os bytes de mensagem processados até */
/* este ponto. */
/******************************************************************************/
/* Funções Para Cálculos Com Tabelas */
/* --------------------------------- */
/* A função a seguir podem ser utilizadas para calcular uma tabela */
/* de busca CRC. Também pode ser utilizada em tempo de execução, para */
/* criar ou verificar tabelas estáticas. */
ulong cm_tab P_((p_cm_t p_cm,int index));
/* Retorna a iésima entrada para a tabela de busca, para o algoritmo */
/* especificado. A função examina os campos cm_width, cm_poly, cm_refin e o */
/* índice da tabela de argumento no intervalo [0-255], e retorna a entrada */
/* da tabela nos bytes mais baixos de cm_width do valor retornado. */
/******************************************************************************/
/* Fim do arquivo de header idempotência #ifndef */
#endif
/******************************************************************************/
/* Fim de crcmodel.h */
/******************************************************************************/
/******************************************************************************/
/* Começo de crcmodel.c */
/******************************************************************************/
/* */
/* Autor  : Ross Williams (ross@guest.adelaide.edu.au.). */
/* Data   : 3 Junho 1993. */
/* Status : Domínio Público. */
/* */
/* Descrição: Este é o arquivo de implementação (.c) para a implementação de */
/* referência do Algoritmo CRC Modelo Rocksoft^tm. Para mais informações */
/* sobre o Algoritmo CRC Modelo Rocksoft^tm, leia o documento */
/* intitulado "Um Guia Indolor Para Algoritmos CRC De Detecção De Erros" */
/* de Ross Williams (ross@guest.adelaide.edu.au.). É muito provável que este */
/* documento esteja em "ftp.adelaide.edu.au/pub/rocksoft". */
/* */
/* Observação: Rocksoft é uma marca registrada de Rocksoft Pty Ltd, */
/* Adelaide, Australia. */
/* */
/******************************************************************************/
/* */
/* Notas de Implementação */
/* ---------------------- */
/* Para evitar inconsistências, as especificações de cada função não são */
/* incluídas novamente aqui. Veja o arquivo de header para descrições */
/* destas funções. Este pacote contém poucas verificações porque quero */
/* mantê-lo breve, simples e portável (isto é, uma grande confusão seria */
/* criada, se eu distribuísse toda a minha cultura em C (por exemplo, */
/* pacotes de declarações) juntamente com este pacote. */
/* */
/******************************************************************************/
#include "crcmodel.h"
/******************************************************************************/
/* As definições a seguir tornam o código mais legível. */
#define BITMASK(X) (1L << (X))
#define MASK32 0xFFFFFFFFL
#define LOCAL static
/******************************************************************************/
LOCAL ulong reflect P_((ulong v,int b));
LOCAL ulong reflect (v,b)
/* Retorna o valor v com os bits mais baixos b [0,32] refletidos. */
/* Exemplo: reflect(0x3e23L,3) == 0x3e26 */
ulong v;
int b;
{
int i;
ulong t = v;
for (i=0; i
{
if (t & 1L)
v|= BITMASK((b-1)-i);
else
v&= ~BITMASK((b-1)-i);
t>>=1;
}
return v;
}
/******************************************************************************/
LOCAL ulong widmask P_((p_cm_t));
LOCAL ulong widmask (p_cm)
/* Retorna uma longword cujo valor é (2^p cm->cm_width)-1. */
/* O truque é escrever um código portável (por exemplo, não fazendo <<32). */
p_cm_t p_cm;
{
return (((1L<<(p_cm->cm_width-1))-1L)<<1)|1L;
}
/******************************************************************************/
void cm_ini (p_cm)
p_cm_t p_cm;
{
p_cm->cm_reg = p_cm->cm_init;
}
/******************************************************************************/
void cm_nxt (p_cm,ch)
p_cm_t p_cm;
int ch;
{
int i;
ulong uch = (ulong) ch;
ulong topbit = BITMASK(p_cm->cm_width-1);
if (p_cm->cm_refin) uch = reflect(uch,8);
p_cm->cm_reg ^= (uch << (p_cm->cm_width-8));
for (i=0; i<8; i++)
{
if (p_cm->cm_reg & topbit)
p_cm->cm_reg = (p_cm->cm_reg << 1) ^ p_cm->cm_poly;
else
p_cm->cm_reg <<= 1;
p_cm->cm_reg &= widmask(p_cm);
}
}
/******************************************************************************/
void cm_blk (p_cm,blk_adr,blk_len)
p_cm_t p_cm;
p_ubyte_ blk_adr;
ulong blk_len;
{
while (blk_len--) cm_nxt(p_cm,*blk_adr++);
}
/******************************************************************************/
ulong cm_crc (p_cm)
p_cm_t p_cm;
{
if (p_cm->cm_refot)
return p_cm->cm_xorot ^ reflect(p_cm->cm_reg,p_cm->cm_width);
else
return p_cm->cm_xorot ^ p_cm->cm_reg;
}
/******************************************************************************/
ulong cm_tab (p_cm,index)
p_cm_t p_cm;
int index;
{
int i;
ulong r;
ulong topbit = BITMASK(p_cm->cm_width-1);
ulong inbyte = (ulong) index;
if (p_cm->cm_refin) inbyte = reflect(inbyte,8);
r = inbyte << (p_cm->cm_width-8);
for (i=0; i<8; i++)
if (r & topbit)
r = (r << 1) ^ p_cm->cm_poly;
else
r<<=1;
if (p_cm->cm_refin) r = reflect(r,p_cm->cm_width);
return r & widmask(p_cm);
}
/******************************************************************************/
/* End of crcmodel.c */
/******************************************************************************/



18. Crie Sua Própria Implementação Baseada em Tabelas
-----------------------------------------------------

A despeito de todo o rebuliço que fiz sobre entender e definir algoritmos CRC, a mecânica da sua implementação em alta velocidade permanece trivial. Há somente duas formas, realmente: normal e refletida. A forma normal desloca os bits para a esquerda, e inclui os casos de algoritmos com Refin=FALSE e Refout=FALSE. A forma refletida desloca os bits para a direita, e inclui os algoritmos com estes dois parâmetros TRUE. (Se você quer um parâmetro TRUE e o outro FALSE, terá de descobrir por si mesmo como fazê-lo!). O polinômio está embutido na tabela de busca (a ser discutida). Os outros parâmetros, Init e Xorout podem ser codificados como macros. Veja abaixo a forma normal do CRC de 32 bits (a forma de 16 bits é similar):

unsigned long crc_normal ();
unsigned long crc_normal (blk_adr,blk_len)
unsigned char *blk_adr;
unsigned long blk_len;
{
unsigned long crc = INIT;
while (blk_len--)
crc = crctable[((crc>>24) ^ *blk_adr++) & 0xFFL] ^ (crc << 8);
return crc ^ XOROT;
}

Veja abaixo a forma refletida:
unsigned long crc_reflected ();
unsigned long crc_reflected (blk_adr,blk_len)
unsigned char *blk_adr;
unsigned long blk_len;
{
unsigned long crc = INIT_REFLECTED;
while (blk_len--)
crc = crctable[(crc ^ *blk_adr++) & 0xFFL] ^ (crc >> 8));
return crc ^ XOROT;
}

Observação: eu verifiquei muito atentamente os dois fragmentos de código acima, mas não os compilei nem testei, realmente. Isto não deverá ser um problema para você porque, independentemente do QUE você codificar, sempre poderá dizer se ficou correto ou não executando o código que criou e comparando-o com o modelo de referência apresentado neste documento. Na verdade, os fragmentos de código acima são apenas um guia esboçado em linhas gerais. O modelo de referência é o guia definitivo.
Observação: se você não se preocupa muito com velocidade, apenas use o código modelo.



19. Gerando Uma Tabela de Busca
-------------------------------

O único componente dos fragmentos de código das formas normal e refletida na seção anterior, que ainda está faltando, é a tabela de busca. A tabela de busca pode ser computada em tempo de execução utilizando-se a função cm_tab do pacote modelo apresentado anteriormente, ou pode ser pré-computada e inserida no programa C. Em qualquer um dos casos, você deve observar que a tabela de busca depende apenas dos parâmetros POLY e Refin (e Refout). Basicamente, o polinômio determina a tabela, mas você também pode gerar uma tabela refletida, se quiser utilizar a forma refletida acima.
O programa a seguir gera qualquer tabela de 16 bits ou de 32 bits desejada. Vá diretamente para a palavra “Sumário”, se quiser pular este código.

/******************************************************************************/
/* Começo de crctable.c */
/******************************************************************************/
/* */
/* Autor : Ross Williams (ross@guest.adelaide.edu.au.). */
/* Data  : 3 Junho 1993. */
/* Version : 1.0. */
/* Status : Domínio público. */
/* */
/* Descrição: Este programa escreve uma tabela de busca CRC (própria para */
/* inclusão em um programa C) em um arquivo de saída designado. O programa */
/* pode ser configurado estaticamente para produzir qualquer tabela coberta */
/* pelo Algoritmo CRC Modelo Rocksoft^tm. Para mais informações sobre o */
/* Algoritmo CRC Modelo Rocksoft^tm, leia o documento intitulado */
/* "Um Guia Indolor Para Algoritmos CRC De Detecção De Erros" de Ross */
/* Williams (ross@guest.adelaide.edu.au.). É muito provável que este */
/* documento esteja em "ftp.adelaide.edu.au/pub/rocksoft". */
/* */
/* Observação: Rocksoft é uma marca registrada de Rocksoft Pty Ltd, */
/* Adelaide, Australia. */
/* */
/******************************************************************************/
#include
#include
#include "crcmodel.h"
/******************************************************************************/
/* TABLE PARAMETERS */
/* ================ */
/* Os parâmetros a seguir determinam inteiramente a tabela a ser gerada. */
/* Você somente precisará modificar as definições nesta seção antes de */
/* executar este programa. */
/* */
/* TB_FILE é o nome do arquivo de saída. */
/* TB_WIDTH é o comprimento da tabela em bytes (ou 2, ou 4). */
/* TB_POLY é o polinômio, que deve ter o comprimento de TB_WIDTH bytes. */
/* TB_REVER indica se a tabela deve ser refletida. */
/* */
/* Exemplo: */
/* */
/* #define TB_FILE "crctable.out" */
/* #define TB_WIDTH 2 */
/* #define TB_POLY 0x8005L */
/* #define TB_REVER TRUE */
#define TB_FILE "crctable.out"
#define TB_WIDTH 4
#define TB_POLY 0x04C11DB7L
#define TB_REVER TRUE
/******************************************************************************/
/* Miscelânea de definições. */
#define LOCAL static
FILE *outfile;
#define WR(X) fprintf(outfile,(X))
#define WP(X,Y) fprintf(outfile,(X),(Y))
/******************************************************************************/
LOCAL void chk_err P_((char *));
LOCAL void chk_err (mess)
/* Se mess não estiver vazia, escreva-a e aborte o processamento. Caso */
/* contrário, verifique o status de erro do arquivo de saída, e aborte se */
/* tiver ocorrido um erro. */
char *mess;
{
if (mess[0] != 0 ) {printf("%s\n",mess); exit(EXIT_FAILURE);}
if (ferror(outfile)) {perror("chk_err"); exit(EXIT_FAILURE);}
}
/******************************************************************************/
LOCAL void chkparam P_((void));
LOCAL void chkparam ()
{
if ((TB_WIDTH != 2) && (TB_WIDTH != 4))
chk_err("chkparam: Comprimento do parâmetro é ilegal.");
if ((TB_WIDTH == 2) && (TB_POLY & 0xFFFF0000L))
chk_err("chkparam: parâmetro Poly comprido demais.");
if ((TB_REVER != FALSE) && (TB_REVER != TRUE))
chk_err("chkparam: Parâmetro reverso não é booleano.");
}
/******************************************************************************/
LOCAL void gentable P_((void));
LOCAL void gentable ()
{
WR("/*****************************************************************/\n");
WR("/* */\n");
WR("/* CRC LOOKUP TABLE */\n");
WR("/* ================ */\n");
WR("/* A tabela de busca CRC a seguir foi gerada automagicamente */\n");
WR("/* pela Geração de Tabelas do Algoritmo CRC Modelo Rocksoft^tm */\n");
WR("/* Programa V1.0 utilizando os seguintes parâmetros do modelo: */\n");
WR("/* */\n");
WP("/* Width : %1lu bytes. */\n",
(ulong) TB_WIDTH);
if (TB_WIDTH == 2)
WP("/* Poly : 0x%04lX */\n",
(ulong) TB_POLY);
else
WP("/* Poly : 0x%08lXL */\n",
(ulong) TB_POLY);
if (TB_REVER)
WR("/* Reverse : TRUE. */\n");
else
WR("/* Reverse : FALSE. */\n");
WR("/* */\n");
WR("/* Para mais informações sobre o Algoritmo CRC Modelo Rocksoft^tm */\n");
WR("/* leia o documento intitulado \"Um Guia Indolor Para */\n");
WR("/* Algoritmos CRC De Detecção de Erros\" de Ross Williams */\n");
WR("/* (ross@guest.adelaide.edu.au.). É muito provável que este */\n");
WR("/* documento esteja no arquivo FTP */
WR("/* \"ftp.adelaide.edu.au/pub/rocksoft\". */\n");
WR("/* */\n");
WR("/*****************************************************************/\n");
WR("\n");
switch (TB_WIDTH)
{
case 2: WR("unsigned short crctable[256] =\n{\n"); break;
case 4: WR("unsigned long crctable[256] =\n{\n"); break;
default: chk_err("gentable: TB_WIDTH inválido.");
}
chk_err("");
{
int i;
cm_t cm;
char *form = (TB_WIDTH==2) ? "0x%04lX" : "0x%08lXL";
int perline = (TB_WIDTH==2) ? 8 : 4;
cm.cm_width = TB_WIDTH*8;
cm.cm_poly = TB_POLY;
cm.cm_refin = TB_REVER;
for (i=0; i<256; i++)
{
WR(" ");
WP(form,(ulong) cm_tab(&cm,i));
if (i != 255) WR(",");
if (((i+1) % perline) == 0) WR("\n");
chk_err("");
}
WR("};\n");
WR("\n");
WR("/*****************************************************************/\n");
WR("/* Fim da Tabela de Busca CRC */\n");
WR("/*****************************************************************/\n");
WR("");
chk_err("");
}
}
/******************************************************************************/
main ()
{
printf("\n");
printf("Programa de Geração de Tabela do Algoritmo CRC Modelo \n");
printf("Rocksoft^tm V1.0\n");
printf("-------------------------------------------------------------\n");
printf("Arquivo de saída é \"%s\".\n",TB_FILE);
chkparam();
outfile = fopen(TB_FILE,"w"); chk_err("");
gentable();
if (fclose(outfile) != 0)
chk_err("main: Não foi possível fechar o arquivo de saída.");
printf("\nSUCCESS: A tabela foi gravada com sucesso.\n");
}
/******************************************************************************/
/* Fim de crctable.c */
/******************************************************************************/



20. Sumário
-----------

Este documento forneceu uma explicação detalhada sobre algoritmos CRC, explicando a sua teoria, e prosseguindo através de implementações crescentemente sofisticadas, variando desde o deslocamento de um simples bit até implementações baseadas em tabelas processadas byte a byte. As várias implementações dos diferentes algoritmos CRC, que tornam confuso o seu manejo e uso, foram explicadas. Um algoritmo modelo parametrizado foi descrito, e pode ser utilizado para definir precisamente um algoritmo CRC em particular, e uma implementação de referência foi fornecida. Por fim, foi fornecido um programa para gerar tabelas CRC.


21. Correções
-------------

Se você achar que qualquer parte deste documento está incorreta ou não está clara, ou tem qualquer outra informação, ou sugestões sobre como este documento poderia ser melhorado, por favor contate o autor. Particularmente, eu gostaria de ter notícia de qualquer pessoa que possa fornecer parâmetros para o Algoritmo CRC Modelo Rocksoft^tm para algoritmos padrão.


A. Glossário
------------

CHECKSUM – Um número que foi calculado como uma função de alguma mensagem. A interpretação literal da palavra “checksum” indica que a função deveria envolver a adição simples de bytes da mensagem. Talvez isto seja o que os primeiros checksum eram, realmente. No entanto, atualmente, embora fórmula mais sofisticadas sejam utilizadas, o termo “checksum” ainda permanece em uso.

CRC – É o acrônimo para "Cyclic Redundancy Code" (Código de Redundância Cíclica). Ao passo que o termo “checksum” parece ser utilizado para referir-se a qualquer unidade não-ciptográfica de verificação de informação, o termo “CRC” parece ser reservado apenas para algoritmos que sejam baseados na idéia de divisão “polinomial”.

G – O símbolo utilizado neste documento para representar o Poli.

Mensagem – O dado de entrada sobre o qual o checksum está sendo calculado. Geralmente é estruturada como uma sequência de bytes. Os algoritmos CRC estabelecem uma informação relativamente ao bit mais alto ou mais baixo de cada byte, e sobre se este bit será considerado o mais significativo ou o menos significativo, utilizando então esta informação como um parâmetro de processamento.

Poli – Meu termo amigável para o polinômio de um CRC.

Polinômio – O “polinômio” de um algoritmo CRC é simplesmente o divisor na divisão que implementa o algoritmo CRC.

Refletir – Um número binário é refletido trocando-se todos os seus bits de lugar, simetricamente, em volta do ponto central. Por exemplo, 1101 é a reflexão de 1011.

ALGORITMO CRC MODELO ROCKSOFT^TM – Um algoritmo parametrizado cujo propósito é funcionar como uma sólida referência para descrever algoritmos CRC. Tipicamente, os algoritmos CRC são especificados pela escolha de um polinômio. No entanto, para realmente construir uma implementação precisa, é preciso conhecer valores de inicialização, e assim por diante.

COMPRIMENTO – O comprimento de um algoritmo CRC é o comprimento de seu polinômio, menos um. Por exemplo, se o polinômio pe 11010, o comprimento seria de 4 bits. Geralmente procura-se escolher um polinômio que resulte em um comprimento que seja múltiplo de 8 bits.



B. Referências
--------------

[Griffiths87] Griffiths, G., Carlyle Stones, G., "The Tea-Leaf Reader
Algorithm: An Efficient Implementation of CRC-16 and CRC-32",
Communications of the ACM, 30(7), pp.617-620. Comentário: Este documento descreve uma implementação baseada em tabelas, de alta velocidade, de algoritmos CRC. A técnica parece ser bem complicada e confusa, e é suplantada pelo algoritmo de Sarwete.

[Knuth81] Knuth, D.E., "The Art of Computer Programming", Volume 2:
Seminumerical Algorithms, Section 4.6.

[Nelson 91] Nelson, M., "The Data Compression Book", M&T Books, (501
Galveston Drive, Redwood City, CA 94063), 1991, ISBN: 1-55851-214-4.
Comentário: se você quer ver uma implementação real de um algoritmo real de checksum de 32 bits, olhe nas páginas 440, e 446-448.

[Sarwate88] Sarwate, D.V., "Computation of Cyclic Redundancy Checks
via Table Look-Up", Communications of the ACM, 31(8), pp.1008-1013.
Comentário: Este documento descreve uma implementação baseada em tabelas, de alta velocidade, para algoritmos CRC que é superior ao algoritmo da folha de chá. Embora este texto descreva a técnica usada pela maioria das modernas implementações de CRC, eu achei o apêndice (onde todo o material bom está) difícil de entender.


[Tanenbaum81] Tanenbaum, A.S., "Computer Networks", Prentice Hall,
1981, ISBN: 0-13-164699-0. Comentário: A seção 3.5.3, nas páginas 128 a 132, fornece uma descrição muito clara de códigos CRC. No entanto, não descreve técnicas de implementação baseadas em tabelas.


C. Referências Que Detectei Mas Ainda Não Li Nem Conferi
--------------------------------------------------------
Boudreau, Steen, "Cyclic Redundancy Checking by Program," AFIPS
Proceedings, Vol. 39, 1971.

Davies, Barber, "Computer Networks and Their Protocols," J. Wiley &
Sons, 1979.

Higginson, Kirstein, "On the Computation of Cyclic Redundancy Checks
by Program," The Computer Journal (British), Vol. 16, No. 1, Feb 1973.