В заключение данного раздела обсудим
«Зеркальный» табличный алгоритм 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 обратитесь к соответствующим источникам.
