Existem muitas opções para calcular a soma de verificação CRC na Internet. Mas o que exatamente é uma soma de verificação e por que ela é calculada dessa forma? Vamos descobrir.
Instruções
Passo 1
Primeiro, vamos obter um pouco de teoria. Então, o que exatamente é CRC? Resumindo, esta é uma das variedades de cálculo de checksum. Checksum é um método para verificar a integridade das informações recebidas no lado do receptor ao transmitir pelos canais de comunicação. Por exemplo, uma das verificações mais simples é usar o bit de paridade. É quando todos os bits da mensagem transmitida são somados, e se a soma for par, então 0 é adicionado ao final da mensagem, se for ímpar, então 1. Ao receber, a soma dos os bits de mensagem também são contados e comparados com o bit de paridade recebido. Se forem diferentes, isso significa que ocorreram erros durante a transmissão e as informações transmitidas foram distorcidas.
Mas este método de detectar a presença de erros é muito pouco informativo e nem sempre funciona, porque se vários bits da mensagem forem distorcidos, a paridade da soma não pode mudar. Portanto, há muito mais verificações "avançadas", incluindo CRC.
Na verdade, o CRC não é uma soma, mas o resultado da divisão de uma determinada quantidade de informação (mensagem de informação) por uma constante, ou melhor, o restante da divisão de uma mensagem por uma constante. No entanto, o CRC também é historicamente conhecido como "checksum". Cada bit da mensagem contribui para o valor CRC. Ou seja, se pelo menos um bit da mensagem original mudar durante a transmissão, a soma de verificação também mudará e significativamente. Essa é uma grande vantagem dessa verificação, pois permite determinar sem ambigüidade se a mensagem original foi distorcida durante a transmissão ou não.
Passo 2
Antes de começarmos a calcular o CRC, é necessário um pouco mais de teoria.
Qual é a mensagem original deve ser clara. É uma sequência contígua de bits de comprimento arbitrário.
Qual é a constante pela qual devemos dividir a mensagem original? Este número também tem qualquer comprimento, mas geralmente são usados múltiplos de 1 byte - 8, 16 e 32 bits. É apenas mais fácil de contar, porque os computadores trabalham com bytes, não com bits.
A constante divisora geralmente é escrita como um polinômio (polinômio) assim: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Aqui, o grau do número "x" significa a posição de um bit no número, começando do zero, e o bit mais significativo indica o grau do polinômio e é descartado ao interpretar o número. Ou seja, o número escrito anteriormente não é nada mais do que (1) 00000111 em binário ou 7 em decimal. Entre parênteses, indiquei o dígito mais significativo implícito do número.
Aqui está outro exemplo: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Normalmente, alguns polinômios padrão são usados para diferentes tipos de CRCs.
etapa 3
Então, como você calcula a soma de verificação? Existe um método básico - dividir uma mensagem em um polinômio "frontal" - e suas modificações para reduzir o número de cálculos e, consequentemente, agilizar o cálculo do CRC. Veremos o método básico.
Em geral, a divisão de um número por um polinômio é realizada de acordo com o seguinte algoritmo:
1) um array (registrador) é criado, preenchido com zeros, igual em comprimento ao comprimento da largura do polinômio;
2) a mensagem original é complementada com zeros nos bits menos significativos, em quantidade igual ao número de bits do polinômio;
3) um bit mais significativo da mensagem é inserido no bit menos significativo do registro, e um bit é movido do bit mais significativo do registro;
4) se o bit estendido for igual a "1", então os bits são invertidos (operação XOR, OU exclusivo) nos bits de registro que correspondem aos do polinômio;
5) se ainda houver bits na mensagem, vá para a etapa 3);
6) quando todos os bits da mensagem entraram no registrador e foram processados por este algoritmo, o restante da divisão permanece no registrador, que é o checksum do CRC.
A figura ilustra a divisão da sequência de bits original pelo número (1) 00000111, ou o polinômio x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Passo 4
Ainda faltam alguns toques adicionais. Como você deve ter notado, a mensagem pode ser dividida por qualquer número. Como escolher? Existem vários polinômios padrão usados para calcular o CRC. Por exemplo, para CRC32 pode ser 0x04C11DB7 e para CRC16 pode ser 0x8005.
Além disso, no registro no início do cálculo, você pode escrever não zeros, mas algum outro número.
Além disso, durante os cálculos, imediatamente antes de emitir a soma de verificação CRC final, eles podem ser divididos por algum outro número.
E a última coisa. Os bytes da mensagem ao escrever no registrador podem ser colocados como o bit mais significativo "para a frente" e vice-versa, o menos significativo.
Etapa 5
Com base em tudo o que foi exposto acima, vamos escrever uma função. NET básica que calcula a soma de verificação CRC tomando alguns parâmetros que descrevi acima e retornando o valor CRC como um número sem sinal de 32 bits.
Public Shared Function GetCrc (ByVal bytes As Byte (), ByVal poly As UInteger, Opcional ByVal largura As Integer = 32, Opcional ByVal initReg As UInteger = & HFFFFFFFFUI, Opcional ByVal finalXor As UInteger = & HFFFFFFFFUI, Opcional ByVal reverseBytes, Opcional ByVal reverseBytes, Opcional reverseCrc As Boolean = True) As UInteger
Dim widthInBytes As Integer = largura / 8
'Complemente a largura da mensagem com zeros (cálculo em bytes):
ReDim Preserve bytes (bytes. Length - 1 + widthInBytes)
'Crie uma fila de bits a partir da mensagem:
Dim msgFifo As New Queue (Of Boolean) (bytes. Count * 8 - 1)
Para cada b como byte em bytes
Dim ba como novo BitArray ({b})
If reverseBytes Then
For i As Integer = 0 a 7
msgFifo. Enqueue (ba (i))
Próximo
Outro
For i As Integer = 7 To 0 Step -1
msgFifo. Enqueue (ba (i))
Próximo
Fim se
Próximo
'Crie uma fila a partir dos bits de preenchimento iniciais do registro:
Dim initBytes As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (De b As Byte em initBytes Take widthInBytes). Reverse
Dim initFifo As New Queue (Of Boolean) (largura - 1)
Para cada b As Byte em initBytesReversed
Dim ba como novo BitArray ({b})
If Not reverseBytes Then
For i As Integer = 0 a 7
initFifo. Enqueue (ba (i))
Próximo
Outro
For i As Integer = 7 To 0 Step -1
initFifo. Enqueue (ba (i))
Próximo
Fim se
Próximo
'Shift e XOR:
Dim register As UInteger = 0 'preencha o registro de bit de largura com zeros.
Fazer enquanto msgFifo. Count> 0
Dim poppedBit As Integer = CInt (registrador >> (largura - 1)) E 1 'define antes do registrador de deslocamento.
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Se initFifo. Count> 0 Então
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xor b
Fim se
registrar = registrar << 1
registrar = registrar ou shiftedBit
Se poppedBit = 1 Then
registrar = registrar X ou poli
Fim se
Ciclo
'Conversões finais:
Dim crc As UInteger = register 'O registro contém o resto da divisão == checksum.
If reverseCrc Then
crc = refletir (crc, largura)
Fim se
crc = crc Xor finalXor
crc = crc And (& HFFFFFFFFUI >> (32 - largura)) 'mascara os bits menos significativos.
Retornar crc
Função Final
