O que é uma alternativa mais rápida a um CRC?

27

Estou fazendo alguma transmissão de dados de um dsPIC para um PC e estou fazendo um CRC de 8 bits para cada bloco de 512 bytes para garantir que não haja erros. Com o meu código CRC ativado, recebo cerca de 33 KB / s, sem ele recebo 67 KB / s.

Quais são alguns algoritmos alternativos de detecção de erros para verificar que seriam mais rápidos?

FigBug
fonte
5
Como o próprio CRC é implementado? Bitwise? Em seguida, mude para um método baseado em tabela. Bytewise? Considere a troca de espaço, complexidade e tempo envolvida no aumento do tamanho da tabela para, digamos, 16 bits (que operaria em dois bytes de uma vez, mas consumiria 64 KB de armazenamento de tabela).
Aidan Cully
Eu tenho apenas 16 KB de RAM e 128 KB de ROM, portanto, uma tabela de 64 KB não é uma opção.
FigBug
1
Então você está usando uma tabela de 256 bytes? ou CRC bit a bit? Se você estiver trabalhando bit a bit, bytewise (com uma tabela de 256 bytes) seria 8 vezes mais rápido.
Aidan Cully
Bit a bit atualmente, vou tentar uma mesa 256
FigBug
1
67kb / sa 33kb / s? Não tenho certeza do que seu outro processamento envolve, mas isso parece um pouco de sobrecarga, mesmo para um PIC. Talvez haja outros problemas que dificultem o seu desempenho?
Rei Miyasaka 26/07

Respostas:

41

Embora possa haver opções mais rápidas que o CRC, se você usá-las, é provável que acabe sacrificando algum grau de capacidade de detecção de erros. Dependendo dos requisitos de detecção de erros, uma alternativa pode ser usar o código CRC otimizado para o seu aplicativo.

Para uma comparação do CRC com outras opções, consulte a excelente resposta de Martin Thompson .

Uma opção para ajudar nisso é o pycrc, que é uma ferramenta (escrita em python 1 ) que pode gerar código-fonte C para dezenas de combinações de modelo e algoritmo crc . Isso permite otimizar a velocidade e o tamanho do seu próprio aplicativo, selecionando e comparando diferentes combinações. 1: Requer Python 2.6 ou posterior.

Ele suporta o crc-8 modelo , mas também suporta crc-5, crc-16e crc-32entre outros. Quanto aos algoritmos , ele suporta bit-by-bit, bit-by-bit-faste table-driven.

Por exemplo (baixando o arquivo):

$ wget --quiet http://sourceforge.net/projects/pycrc/files/pycrc/pycrc-0.8/pycrc-0.8.tar.gz/download
$ tar -xf pycrc-0.8.tar.gz
$ cd pycrc-0.8
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit      --generate c -o crc8-byb.c
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit-fast --generate c -o crc8-bybf.c
$ ./pycrc.py --model=crc-8 --algorithm=table-driven    --generate c -o crc8-table.c
$ ./pycrc.py --model=crc-16 --algorithm=table-driven   --generate c -o crc16-table.c
$ wc *.c
   72   256  1790 crc8-byb.c
   54   190  1392 crc8-bybf.c
   66   433  2966 crc8-table.c
  101   515  4094 crc16-table.c
  293  1394 10242 total

Você pode até fazer coisas descoladas, como especificar usando pesquisas de mordidelas duplas (com uma tabela de pesquisa de 16 bytes) em vez de pesquisa de byte único, com tabela de pesquisa de 256 bytes.

Por exemplo (clonando o repositório git):

$ git clone http://github.com/tpircher/pycrc.git
$ cd pycrc
$ git branch
* master
$ git describe
v0.8-3-g7a041cd
$ ./pycrc.py --model=crc-8 --algorithm=table-driven --table-idx-width=4 --generate c -o crc8-table4.c
$ wc crc8-table4.c
  53  211 1562 crc8-table4.c

Dadas as restrições de memória e velocidade, essa opção pode ser o melhor compromisso entre velocidade e tamanho do código. A única maneira de ter certeza seria compará-lo.


O repositório pycrc git está no github , assim como seu rastreador de problemas , mas também pode ser baixado no sourceforge .

Mark Booth
fonte
Não acredito que a maioria das pessoas que escreve coisas para o PIC esteja usando C, mas isso pode funcionar se assim for.
Billy ONeal
4
@Billy - Sério? Eu não acho que encontrei alguém desenvolvendo comercialmente para o PIC que não estava usando C. Eu certamente não tenho paciência para assembler atualmente e C bem estruturado pode acabar bem compacto.
27511 Mark Booth
Eu estou usando um dsPIC e estou usando C.
FigBug
@FigBug - Obrigado, feliz que você gostou da minha resposta. Se você executar alguns testes de benchmark, sinta-se à vontade para editar minha resposta com seus resultados. Gostaria de saber quanta diferença cada um dos algoritmos faz em termos de taxa de transferência do seu aplicativo e pegada de memória.
22611 Mark Booth
1
Outro voto para pyCrc aqui. usá-lo em vários projetos com diferentes restrições e é ótimo.
Vicky
11

A paridade simples de um bit (basicamente XORing os dados repetidamente) é quase o mais rápido possível. Você perde muito a verificação de erros de um CRC.

No pseudocódigo:

char checksum = 0;
for each (char c in buffer)
{
    checksum ^= c;
    SendToPC(c);
}
SendToPc(checksum);
Billy ONeal
fonte
1
Eu olhei para isso há um tempo atrás. Eu acredito que a soma em vez de xor realmente funciona um pouco melhor. (normalmente, somar tudo e depois transmitir o complemento 2 da soma como soma de verificação. No receptor, somar tudo, incluindo a soma de verificação recebida. O resultado é 0 se tudo estiver bom, e não 0 caso contrário.)
quick_now
1
@ rapidamente: Eu não acho que exista uma diferença significativa entre os dois - nenhum método fornece uma garantia tão boa de que as coisas não foram corrompidas. Se o add for mais rápido na arquitetura de destino, use-o em todos os aspectos.
Billy ONeal
7
Lembrei: A principal diferença entre ADD e XOR é que há menos detectabilidade de erros de vários bits. No caso de um fluxo de bytes, os erros na mesma posição de bit são cancelados usando o XOR. Ao usar ADD, a propagação de bits por meio de um byte de soma de verificação significa que esse caso é mais detectável. (No entanto, erros de vários bits em diferentes bits espalhados pelo fluxo de bytes provavelmente serão menos detectáveis ​​- dependendo das circunstâncias da época). Qualquer organização de soma de verificação como essa é TERRÍVEL para erros de vários bits; portanto, é um argumento bastante pequeno.
quickly_now
O XOR é muito menos útil que o CRC.
3
@ Thorbjørn: Eu acredito que reconheci isso na minha resposta. :)
Billy ONeal
10

Um artigo realmente bom comparando o desempenho de várias somas de verificação e CRCs em um contexto incorporado:

A eficácia das somas de verificação para redes incorporadas

Algumas citações das conclusões (baseadas em seus estudos de probabilidades de erro não detectadas):

Quando erros de burst dominam

XOR, adição de complemento de dois e somas de verificação CRC fornecem melhor desempenho de detecção de erros do que as somas de verificação de adição de complemento, Fletcher e Adler.

Em outras aplicações

um polinômio CRC “bom”, sempre que possível, deve ser usado para fins de detecção de erros

Se o custo da computação for muito restrito

(como no seu caso), use (em ordem de eficácia):

Outras citações:

A soma de verificação Fletcher tem um custo computacional menor que a soma de verificação Adler e, contrariamente à crença popular, também é mais eficaz na maioria das situações.

e

Geralmente, não há razão para continuar a prática comum de usar uma soma de verificação XOR em novos designs, porque ela tem o mesmo custo computacional de software que uma soma de verificação baseada em adição, mas tem apenas metade da eficácia na detecção de erros.

Martin Thompson
fonte
1
Como bônus, uma soma de verificação Fletcher é muito fácil de implementar.
precisa saber é o seguinte
6

A soma de verificação Adler deve ser suficiente para verificar distorções na transmissão. É usado pela biblioteca de compactação Zlib e foi adotado pelo Java 3D Mobile Graphics Standard para fornecer uma verificação rápida mas eficaz da integridade dos dados.

Na página da Wikipedia :

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 número inteiro de 32 bits. A é a soma de todos os bytes na string 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 e 0. As somas são feitas no módulo 65521 (o maior número primo menor que 2 ^ 16 ou 65536). Os bytes são armazenados em ordem de rede (big endian), 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 cadeia de bytes para a qual a soma de verificação deve ser calculada en é o comprimento de D.

Gnawme
fonte
Observe que o Adler32 é quase inútil para pequenas execuções de dados. Até cerca de 180 bytes, produz inúmeras colisões.
greyfade 27/07
+1 - um meio termo razoável entre uma CRC e a paridade de bits simples.
Billy ONeal
@greyfade - FigBug mencionado usando blocos de 512 bytes, então isso não deve ser um problema para o OP. É bom notar isso para pessoas com outros requisitos.
27611 Mark Booth
5

Não tenho conhecimento de nada que seja tão eficaz na detecção de erros quanto um CRC e mais rápido - se houvesse, as pessoas o usariam.

Você pode tentar uma soma de verificação simples, mas é muito menos provável detectar erros.

Bob Murphy
fonte
2
Estou disposto a desistir da eficácia da velocidade.
FigBug
3

Bem, a própria lógica de soma de verificação é boa e as pessoas podem ajudar com algoritmos mais rápidos.

Se você deseja melhorar a velocidade do seu componente, pode ser necessário alterar sua técnica geral para separar o componente de transferência do componente de validação.

Se você tiver esses dois itens independentes (em threads diferentes), poderá obter toda a velocidade de transferência e reenviar apenas pacotes com falha.

Algoritmo seria algo como:

  • O servidor divide-se em tamanhos de pacotes conhecidos (por exemplo, 1K em pedaços). Coloca-os em uma fila de "a serem enviados".
  • Cada pacote é enviado com um ID de 16 ou 32 bits E sua soma de verificação.
  • O cliente recebe cada pacote e o coloca em uma fila para ser processado.
  • Em um thread separado, o cliente obtém um pacote de cada vez, faz a validação.
    • Em caso de sucesso, ele é adicionado à coleção final de pacotes (em ordem de ID) sendo
    • Em caso de falha, ele reporta o ID com falha de volta ao servidor, que enfileira o pacote para reenvio.
  • Depois de receber e validar os pacotes e os IDs na sequência correta (começando em 1), você pode começar a gravá-los no disco (ou fazer o que for necessário).

Isso permitirá que você transmita na velocidade mais alta possível e, se você jogar com o tamanho do pacote, poderá calcular a taxa de falhas otimizada VS, validar / reenviar a taxa.

Robin Vessey
fonte
2

Checksums são tradicionais

(reduzir # '+ stream)

XOR, como indicado acima, também funcionaria

(reduzir o fluxo XOR # ')

Um esquema um pouco mais elaborado (mais lento) é a verificação de paridade padrão para conexões seriais.

Nesse nível, você está trocando correção por velocidade. Estes irão ocasionalmente falhar.

No próximo nível mais sofisticado, você pode usar algumas coisas do tipo crc / hash.

Outro design seria aumentar o tamanho do bloco usado para o fluxo.

Você deve ter uma estimativa da taxa de erro real para ajustar a seleção do algoritmo e os parâmetros para o tamanho do bloco.

Paul Nathan
fonte