"Зеркальный" табличный алгоритм CRC32
Для того, кто обладает солидным багажом знаний по проблеме CRC-вычислений, написание программы, реализующей зеркальный алгоритм, – дело техники. На стороне источника код будет выглядеть так:
;prg09_09.asm – программа вычисления кода CRC32 на стороне источника :для зеркального алгоритма CRC32 и полинома 0EDB88320h. .data ;исходная битовая последовательность в символах bit_stnng db "123456789" len_bit_string=$-bit_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. :исходная битовая последовательность в символах 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-Таблицу……… 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 закончили расчет (CRC32-таблицы 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 обратитесь к соответствующим источникам.