Прямой табличный алгоритм вычисления СRC32.

Как и любой табличный алгоритм, табличный алгоритм вычисления CRC32 требует задания CRC-таблицы. Ее можно задать в програм'ме статически, явно прописав значения элементов таблицы в сегменте кода, или динамически, вычислив значения элементов таблицы перед началом расчета CRC. Ниже приведена программа вычисления CRC-таблицы для полинома 04clldb7.

Прямой табличный алгоритм CRC32 удобно рассматривать со стороны участников процесса, как это мы делали выше. Источник выполняет следующие действия.

:prgO9_O5.asm - программа вычисления CRC-таблицы для полинома 04clldb7.

.data

;С1<С32-таблица для прямого табличного алгоритма вычисления CRC32

tabl_32_direct dd 256 dup (0)

len_tabl_32_direct =$-tabl_32_direct

adr_tabl_32_direct dd tabl_32_direct

polinom dd 04clldb7h

.code

les di.adr_tabl_32_direct

add di,len_tabl_32_direct-4

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

mov ex,255

mov ebx.polinom /

ml: xor eax.eax

shrd eax.ecx,8

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

mov ex.8 m2: shl eax.l

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

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

xor eax.ebx :ax XOR polinom

шЗ:loop m2

pop ex

1. Делает начальную установку регистра, в котором будет производиться формирование CRC, значением OFFFFFFFFh.

2. Вычисляет значение CRC для каждого байта исходной последовательности, принцип которой показан на схеме (см. рис. 9.9). Читатель понимает, что хотя эта схема иллюстрирует принцип вычисления CRC16, но для 32-разрядного алгоритма нужно только увеличить размер элементов таблицы до 32 бит и задействовать весь регистр ЕАХ.

3. Объединяет по XOR итоговое значение в ЕАХ со значением OFFFFFFFFh.

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

Ниже приведена программа вычисления CRC32 по прямому табличному алгоритму.

;prg09_06.asm - программа вычисления CRC32 по прямому табличному алгоритму.

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

bit_string db "123456789"

len_bit_string=$-bit_string

сгс_32 dd 0 ;сюда мы поместим рассчитанное значение CRC32

adr_bit_string dd bit_string

;СЯС32-таблица для прямого табличного алгоритма вычисления CRC32

tabl_32_direct dd 256 dup (0)

len_tabl_32_direct =$-tabl_32_direct

adr_tabl_32_direct dd tabl_32_direct

polinom dd 04clldb7h

.code

:----.........расчитываем CRC32 таблицу

les di.adr_tabl_32_direct

add di.len_tabl_32_direct-4 * std ;идем назад по таблице

mov ex.255

mov ebx, polinom

ml: xor eax.eax

shrd eax.ecx.8

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

mov ex.8

m2: shl eax.l

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

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

xor eax.ebx :ax XOR polinom

m3: loop m2

pop ex

stosd

loop ml

:.....--......закончили расчет CRC32 таблицы

mov eax, OFFFFFFFFh

Ids si.adr_bit_string

mov cx.len_bit_string

m4: xor ebx.ebx

shld ebx.eax.8

shl eax.8

xor bl.[si]

xor eax. tabl_32_direct[bx]

inc si

1 oop m4 :запишем crc-32 в конец (или начало, см. обсуждение ниже) последовательности:

xor eax. OFFFFFFFFh

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

Значение CRC32 для строки "123456789" равно 9c970409h.

Если для источника стандарт определяет практически однозначную последовательность действий, то для приемника возможны несколько вариантов поведения. Отметим два из них.

В первом варианте критерием для вывода о целостности полученного приемником сообщения является результат сравнения или нулевой результат.

1. Выполнить начальную установку регистра, в котором будет производиться формирование значения CRC.

2. Вычислить значение CRC для каждого байта полученной последовательности, принцип которой показан на схеме (см. рис. 9.9 и замечания выше о различиях CRC16 и CRC32).

3. Объединить по XOR итоговое значение в ЕАХ со значением OFFFFFFFFh.

4. Далее можно сделать одно из двух действий:

сравнить значение в ЕАХ со значением CRC, полученным вместе с сообщением, — если они равны, то полученное сообщение идентично исходному;

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

Во втором варианте критерием для вывода о целостности полученного приемником сообщения является фиксированная двоичная константа 6b202ca2h.

1. Выполнить начальную установку регистра, в котором будет производиться формирование CRC, в значение OFFFFFFFFh;

2. Вычислить значение CRC32 для каждого байта полученной последовательности (вместе со значением CRC32 в конце), принцип которой показан на схеме (см. рис. 9.9 и замечания выше о различиях CRC16 и CRC32). Должно получиться фиксированное двоичное значение — 6b202ca2h. Необ ходимо заметить, что в литературе можно встретить другое значение — 0debb20e3h, но у автора получалось первое.

Основное отличие этих двух вариантов в том, что нужно каким-то образом отделять контролируемую строку и ее значение CRC32. Избежать прямого отслеживания длины принимаемой строки на стороне приемника можно путем формирования источником значения CRC32 в начале исходной строки либо вообще вне строки. Последний случай, например, характерен для программы, которая отслеживает целостность файлов в некотором каталоге. Тогда результаты подсчета CRC для каждого файла хранятся в некотором служебном файле. Если такой вариант вас не устраивает, тогда следует написать код приемника для прямого табличного алгоритма так, как это сделано для приемника в зеркальном табличном алгоритме. Попробуйте самостоятельно определить константу, соответствующую успешному принятию приемником исходной строки.

Учитывая практическую важность обоих вариантов и для демонстрации разнообразия подходов к проблеме вычисления CRC32, работу приемника для прямого табличного алгоритма продемонстрируем на примере первого варианта, приемник «зеркального» табличного алгоритма CRC32 разработаем исходя из положений второго варианта. Но вы должны понимать, что правильное понимание принципов расчета CRC позволяет вам при соответствующей доработке кода поменять варианты работы приемников. В поле сгс_32 должно быть значение CRC32, рассчитанное предыдущей программой. Автор специально не стал объединять эти программы. Пусть это сделает читатель в нужном для его текущей работы контексте.

;prg09_06.asm - программа вычисления CRC32 по прямому табличному алгоритму.

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

bit_string db "123456789"

len_bit_string=$-bit_string

сгс_32 dd 0 ;сюда мы поместим рассчитанное значение CRC32

adr_bit_string dd bit_string

;СЯС32-таблица для прямого табличного алгоритма вычисления CRC32

tabl_32_direct dd 256 dup (0)

len_tabl_32_direct =$-tabl_32_direct

adr_tabl_32_direct dd tabl_32_direct

polinom dd 04clldb7h

.code

:----.........расчитываем CRC32 таблицу

les di.adr_tabl_32_direct

add di.len_tabl_32_direct-4 * std ;идем назад по таблице

mov ex.255

mov ebx, polinom

ml: xor eax.eax

shrd eax.ecx.8

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

mov ex.8

m2: shl eax.l

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

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

xor eax.ebx :ax XOR polinom

m3: loop m2

pop ex

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

mov ex,8 m2: shl eax.l

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

хог eax.ebx:ax XOR polinom m3: loop m2

pop сх

stosd

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

mov eax. OFFFFFFFFh

Ids si,adr_bit_string

mov cx,len_bit_string m4: xor ebx.ebx

shld ebx.eax,8

shl eax.8

xor bl.[si]

xor eax. tabl_32_direct[bx]

inc si

1 oop m4

xor eax. OFFFFFFFFh

;если исходная последовательность цела, то должно получиться значение crc32=9c970409h ;его можно сравнить с исходным и на этом закончить работу или продолжить до победного. :то есть до 0:

mov ex.4 : 4 (длина сгс_32) :в si адрес сгс_32

mov ebx.crc_32

bswap ebx

mov crc_32.ebx m5: xor ebx.ebx

shld ebx.eax.8

shl eax.8

xor bl.[si]

xor eax. tabl_32_direct[bx]

inc si

loop m5 :должен быть О

Заметьте, что для получения нулевого результата нам пришлось использовать команду BSWAP, чтобы «перевернуть» "значение в поле сгс_32.