Сборник по задачам и примерам Assembler

     

В заключение данного раздела обсудим



«Зеркальный» табличный алгоритм CRC32

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

Вместо того чтобы менять местами биты перед их обработкой, можно зеркально отразить все значения и действия, участвующие в прямом алгоритме. При этом

направление расчетов поменяется — байты теперь будут сдвигаться вправо, полином 04clldb7h зеркально отразится относительно его центра, в результате получится значение 0edb88320h. С11С32-таблица будет зеркальным отражением аналогичной таблицы для прямого алгоритма (Рисунок 9.10).



Рисунок 9.10. Схема «Зеркального» табличного алгоритма

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

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

.data

:СРС32-таблица для зеркального табличного алгоритма вычисления CRC32

tabl_32_mirror dd 256 dup (0)

len_tabl_32jrrirror=$-tabl_32_mirror

adr_tabl_32jTrirror dd tabl_32_mirror

polinom dd 0EDB88320h



.code

les di.adr_tabl_32_mirror

add di,len_tabl_32_mirror-4

std ;идем назад по таблице

mov ex.255

mov ebx.polinom

ml: xor eax.eax

mov al.cl ;индекс в таблице для вычисления CRC

push ex сложенные циклы

mov ex.8

m2: shr eax.l

jnc m3 ;старшие разряды не равны - выполняем сдвиг (частное нас не интересует)

;старшие разряды равны - выполняем XOR:

xor eax.ebx:ax XOR polinom

m3: loop m2

pop ex stosd

loop ml

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



;prgO9_O9.asm - программа вычисления кода CRC32 на стороне источника :для зеркального алгоритма CRC32 и полинома 0EDB88320h.

.data

исходная битовая последовательность в символах bit_stnng db "123456789" 1en_bi t_string=$-bi t_string

crc_32 dd 0 :сюда мы поместим рассчитанное значение CRC32 adr_bit_string dd bit_string

:СРС32-таблица для зеркального табличного алгоритма вычисления CRC32 .. tab1_32_mirror dd 256 dup (0) len_tabl_32_mirror=$-tabl_32_mirror adr_tabl_32_mirror dd tabl_32_mirror polinom dd 0EDB88320h .code

:-------......расчитываем зеркальную СКС32-таблицу.........

les di.adr_tabl_32_mirror

add di,len_tabl_32_mirror-4

std :идем назад по таблице

mov ex.255

mov ebx.polinom

ml: xor eax.eax

mov al.cl ;индекс в таблице для вычисления CRC

push ex ;вложенные циклы

mov ex.8

m2: shr eax.l

jnc m3 ;старшие разряды не равны - выполняем сдвиг (частное нас не интересует) :старшие разряды равны - выполняем XOR:

xor eax.ebx:ax XOR polinom

m3: loop m2

pop сх

stosd ' '

loop ml закончили расчет СРС32-таблицы

xor bx.bx

mov eax. OFFFFFFFFh

Ids si,adr_bit_string

mov cx,len_bit_string

m4: mov Ы .al

shr eax.8

xor bl.[si]

xor eax.tabl_32_mirror[bx]

inc si

1 oop m4

xor eax. OFFFFFFFFh ;запишем сгс-32 в конец последовательности:

mov сгс_32.еах добавляем в конец исходной последовательности

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

:prg09_10.asm - программа вычисления кода CRC32 на стороне приемника ;для зеркального алгоритма CRC32 и полинома 0EDB88320h.

1

:исходная битовая последовательность в символах

bit_string db "123456789"

1en_bit_string=$-bit_string

сгс_32 dd Ib948a57h :сюда мы поместили рассчитанное значение CRC32

adr_bit_string dd bit_string



:С(}С32- таблица для зеркального табличного алгоритма вычисления CRC32

tabl_32_mirror dd 256 dup (0)

1 en_tabl_32_mi rror=$-tabl_32_nii rror

adr_tabl_32_mirror dd tabl_32_mirror

polinom dd 0EDB88320h

.code

:.........

;----........расчитываем зеркальную CRC32-Ta6flnuy.........

les di,adr_tabl_32_mirror

add di,len_tabl_32_mirror-4

std ;идем назад по таблице

mov ex.255

mov ebx.poli nom ml: xor eax.eax

mov al.cl :индекс в таблице для вычисления CRC

push сх сложенные циклы

mov сх,8 m2: shr eax.l

jnc m3 ;старшие разряды не равны - выполняем сдвиг (частное нас не интересует) :старшие разряды равны - выполняем XOR: * xor eax,ebx:ax XOR polinom m3: loop m2

pop ex

stosd

loop ml закончили расчет (Ж32-таблицы

xor bx.bx

mov eax. OFFFFFFFFh

Ids si.adr_bit_string

mov cx.len_bit_string+4 ;4 - длина crc_32 m4: mov bl.al

shr eax.8

xor bl.[si]

xor eax.tabl_32_mirror[bx]

inc si loop m4 :сравнить - результат должен быть константой 6b202ca2h

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

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

 

Содержание раздела