Зеркальный табличный алгоритм CRC32 (asm x86)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 19:55, 9 августа 2015.

В заключение данного раздела обсудим "зеркальный" вариант табличного алгоритма - алгоритм CRC32(v.42 MKKTT). Этот вариант вычисления CRC обязан своим возникновением существованию последовательного интерфейса, который посылает биты, начиная с наименее значимого (бит 0) и заканчивая самым старшим (бит 7), то есть в обратном порядке. В «зеркальном» регистре все биты отражены относительно центра. Например, 10111011001 есть отражение значения 10011011101.

Вместо того чтобы менять местами биты перед их обработкой, можно зеркально отразить все значения и действия, участвующие в прямом алгоритме. При этом направление расчетов поменяется — байты теперь будут сдвигаться вправо, полином 04clldb7h зеркально отразится относительно его центра, в результате получится значение 0edb88320h. CRC32-таблица будет зеркальным отражением аналогичной таблицы для прямого алгоритма (рис. 9.10).

Для зеркального алгоритма вычисления CRC32 процесс вычисления такой же, за исключением порядка — сдвиги и заполнение регистра осуществляются вправо. Ниже приведена программа вычисления таблицы для зеркального алгоритма CRC32 и полинома 0EDB88320h.

Рис. 1. Схема зеркального табличного алгоритма
;----------------------------------------------------------------------------------------------------
Программа: prg09_08.asm. Вычисление таблицы для зеркального алгоритма CRC32 и полинома 0EDB88320h.
;----------------------------------------------------------------------------------------------------

.data
tabl_32_rmrror dd 256 dup (0)           ; СРС32-таблица для зеркального табличного алгоритма расчета CRC32 
len tabl_32_mirror = $ - tabl_32_mirror 
adr_tabl_32_mirror dd tabl_32_mirror
polinom	dd 0EDB88320h

.code
...
      les di, adr_tabl_32_mirror
      add di, len_tabl_32_mirror - 4 
      std	                        ; идем назад по таблице
      mov сx, 255
      mov ebx, polinom 

ml:	
     xor eax, eax
     mov al, cl	                       ; индекс в таблице для вычисления CRC
     push сх	                       ; вложенные циклы
     mov сх, 8 

m2:	
    shr eax, 1
    jnc m3	                       ; старшие разряды не равны - выполняем
                                       ; сдвиг (частное нас не интересует)
; ---------------старшие разряды равны - выполняем X0R
    xor eax, ebx	               ; ах XOR polinom
m3:	
    loop m2
    pop cx
    stosd 
    loop ml
;......

Для того, кто обладает солидным багажом знаний по проблеме CRC-вычислений, написание программы, реализующей зеркальный алгоритм, — дело техники. На стороне источника код будет выглядеть так:

;------------------------------------------------------------------------------------------------------------------------------
Программа: prg09_09.asm. Вычисление кода CRC32 на стороне источника для зеркального алгоритма CRC32 и полинома 0EDB88320h.
;------------------------------------------------------------------------------------------------------------------------------
.data
bit_string db '123456789'            ; исходная битовая последовательность в символах 
len_bit_string = $ - bit_string 
crc_32	dd 0	                     ; сюда поместим значение CRC32
adr bit_string dd bit_string
tabT_32_mirror dd 256 dup (0)        ; СРС32-таблица для зеркального табличного алгоритма вычисления CRC32
len_tabl_32_mirror = $ - tabl_32_mirror
adr_tabl_32_mirror dd tabl_32_mirror 
polinom	dd 0EDB88320h

.code
;---------------рассчитываем зеркальную CRC32-таблицу
     les	di, adr_tabl_32_mirror
     add	di, len_tabl_32_mirror - 4
     std                             ; идем назад по таблице
     mov	сх, 255
     mov	ebx, polinom
ml:	
     xor	eax, eax
     mov	al, cl	             ;индекс в таблице для вычисления CRC 
;---------------вложенные циклы 
     push сх 
     mov  сх, 8
m2:	
     shr еах, 1
     jnc m3	                    ; старшие разряды не равны - выполняем сдвиг (частное нас не интересует)
;---------------старшие разряды равны - выполняем X0R
     хог еах, ebx	            ; ах XOR polinom
m3:	
    loop m2
    pop сх
    stosd
    loop ml
;---------------закончили расчет CRC32-таблицы
    хоr bx, Ьх 
    mov еах, Offffffffh
    lds si, adr_bit_string 
    mov cx, len_bit_string
m4:
    mov bl, al
    shr eax, 8 
    хоr bl, [si]
    xor eax, tabl_32 mirror[bx]
    inc si 
    loop m4
    xor eax, Offffffffh
;---------------запишем crc-32 в конец последовательности
    mov crc_32, eax                ; добавляем в конец исходной последовательности
;......

Для исходной строки "123456789" вычислили CRC = 1b948a57h. Теперь осталось приемнику проверить целостность полученной им строки. Приемник работает по второму варианту и выполняет действия, иллюстрируемые приведенной ниже программой. Если полученная им строка совпадает с исходной, то результатом работы программы должно быть значение 6b202ca2h.

;------------------------------------------------------------------------------------------------------------------------------
Программа: prg09_10.asm. Вычисление кода CRC32 на стороне приемника для зеркального алгоритма CRC32 и полинома 0EDB88320h.
;------------------------------------------------------------------------------------------------------------------------------
.data
;---------------исходная битовая последовательность в символах 
bit_string db '123456789'
len_bit_string = $ - bit_string 
crc_32	   dd   1b948a57h         ; сюда мы поместили значение CRC32
adr_bit_string dd   bit_string
tabl_32_mirror dd 256 dup (0)     ; СRС32-таблица для зеркального табличного алгоритма рассчета CRC32
len tabl 32_m1rror = $ - tabl_32_mirror 
adr_tabl_32_mirror dd tabl_32_mirror
polinom	   dd	0EDB88320h

.code
;---------------рассчитываем зеркальную CRC32-таблицу 
    les l_32_mirror
    add       di   l_32_mirror - 4
    std                            ; идем назад по таблице
    mov	   сх, 255
    mov	   ebx, polinom
ml:	
     xor	eax, eax
     mov	al, cl	             ;индекс в таблице для вычисления CRC 
;---------------вложенные циклы 
     push сх 
     mov  сх, 8
m2:	
     shr еах, 1
     jnc m3	                    ; старшие разряды не равны - выполняем сдвиг (частное нас не интересует)
;---------------старшие разряды равны - выполняем X0R
     хог еах, ebx	            ; ах XOR polinom
m3:	
    loop m2
    pop сх
    stosd
    loop ml
;---------------закончили расчет CRC32-таблицы
    хоr bx, Ьх 
    mov еах, Offffffffh
    lds si, adr_bit_string 
    mov cx, len_bit_string + 4     ;4 - длина СRС_32
m4:
    mov bl, al
    shr eax, 8 
    хоr bl, [si]
    xor eax, tabl_32 mirror[bx]
    inc si 
    loop m4
;---------------сравнить - результат должен быть константой 6b202сa2h


Этот вариант работы алгоритма вычисления CRC32 удобен тем, что не нужно знать длину собственно исходной последовательности (без значения CRC). Достаточно просто обработать весь входной поток, не различая в строке завершающую ее подстроку с CRC. Далее необходимо сравнить содержимое регистра ЕАХ с 6b202ca2h. Если эти значения равны, значит, исходная последовательность нарушена не была. Для получения собственно строки достаточно отбросить последние 4 байта сообщения, поступившего к приемнику. И последнее замечание, которое говорит о том, что проблема вычисления CRC неоднозначна для понимания и предоставляет большое поле для проведения различных экспериментов и совершенствования существующих алгоритмов. Небольшой поправкой в алгоритме работы источника можно сделать так, что успехом целостности при принятии приемником сообщения может быть не указанная выше константа, а нуль. Для этого источнику достаточно не объединять вычисленное значение CRC32 по XOR с 0ffffffffh, а просто добавить его к исходной последовательности. Оба варианта хороши тем, что не нужно заранее знать длину анализируемого сообщения.

Здесь, пожалуй, можно и закончить обсуждение проблемы вычисления CRC. На примере этой достаточно сложной задачи были в очередной раз продемонстрированы варианты использования средств ассемблера для обработки информации на различных уровнях, вплоть до битового.