fasm : Алгоритм расчета CRC-16

Алгоритмы CRC (Cyclic Redundancy Code, циклический избыточный код) используются для определения контрольной суммы сообщения и предназначены для проверки его целостности.

Подробнее о CRC можно почитать на Википедии или в статье Росса Н. Вильямса "Элементарное руководство по CRC алгоритмам обнаружения ошибок", в которой довольно полно и точно, а, главное, понятно рассказано о принципах работы и методах реализации и использования этих алгоритмов.

Алгоритм CRC-16-CCITT

Параметры.

Name   : CRC-16-CCITT

Width  : 16
Poly   : 1021
Init   : FFFF
RefIn  : False
RefOut : False
XorOut : 0000

Описание.

Чтобы наглядно продемонстрировать принцип расчета контрольной суммы по алгоритму CRC-CCITT, приведу схему пошагового выполнения алгоритма для расчета CRC для однобайтового сообщения "A" (ASCII код: 0x41):

1. Исходное сообщение "A" (в двоичной с/с: 01000001) дополняется справа нулевыми битами количеством степени порождающего многочлена:

010000010000000000000000

2. Задается начальное значение (Init): 0xFFFF, в результате чего сообщение примет следующий вид:

1111111111111111010000010000000000000000

3. Наконец, выполняется деление (в терминах CRC) сообщения на порождающий многочлен:

 1111111111111111010000010000000000000000
⊻
 10001000000100001                      .
 -----------------
  11101111110111111                     .
 ⊻
  10001000000100001                     .
  -----------------
   11001111100111100                    .
  ⊻
   10001000000100001                    .
   -----------------
    10001111000111010                   .
   ⊻
    10001000000100001                   .
    -----------------
     00001110000110110                  .
    ⊻
     00000000000000000                  .
     -----------------
      00011100001101100                 .
     
                              (и так далее, и так далее)
    
                        11000010001011000
                       ⊻
                        10001000000100001 
                        ----------------- 
                         1001010001111001 = 0x9479 - CRC

Реализация.

Реализация для определения CRC двоичного файла или его части во время компиляции:
(в директивах препроцессора fasm)

;---------------------------------------------------------------------------- ; compute CRC16 (CRC-CCITT) and append it to the end of the binary file ; result = 0xffff offset = <смещение начала сообщения относительно начала файла> size = crc16 - offset + 2 while (size > 0)   if (size > 2)     load b byte from (offset)   else     b = 0   end if   repeat 8     result = result shl 1     if (b and 0x80)       result = result + 1     end if     b = b shl 1     if (result and 0x10000)       result = result and 0xffff xor 0x1021     end if   end repeat   offset = offset + 1   size = size - 1 end while crc16 dw result

Реализация для определения CRC блока данных во время выполнения:
(подпрограмма для микропроцессора, работающего в реальном режиме, полностью совместима с набором команд 8086)

;---------------------------------------------------------------------------- ; Compute CRC16 (CRC-CCITT) ;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ; INPUT: ;   CX      - data length in bytes ;   DS:SI   - pointer to data ; ; OUTPUT: ;   AX      - computed CRC ; ; AFFECTS: ;   CX, DX, SI ;---------------------------------------------------------------------------- crc16ccitt:   mov ax, 0xffff   add cx, 2 .start:   test cx, cx   jz short .ret   xor dx, dx   cmp cx, 2   jbe short @f   mov dl, [si] @@:   mov dh, 8 .next:   shl dl, 1   rcl ax, 1   jnc short @f   xor ax, 0x1021 @@:   dec dh   jnz short .next   inc si   dec cx   jmp short .start .ret:   ret

Для проверки правильности работы алгоритма можно воспользоваться проверочными значениями:

Сообщение	Значение CRC
A	0x9479
123456789	0xE5CC
Строка из 256 символов “A”	0xE938