Иллюстрированный самоучитель по задачам и примерам Assembler

Табличные алгоритмы вычисления CRC

Вот мы и выяснили, на чем основано название табличного алгоритма расчета CRC. Теперь со знанием сути дела приведем его общее описание (рис. 9.8). В качестве основы для рассуждений по-прежнему используем программу прямого вычисления значения CRC и соответствующую схему (см. рис. 9.6).

Иллюстрированный самоучитель по задачам и примерам Assembler › Вычисление CRC › Табличные алгоритмы вычисления CRC
Рис. 9.8. Общая схема табличного алгоритма

На схеме, показанной на рисунке, цифрами обозначена последовательность шагов табличного алгоритма. Шаги 1 и 2 выполняются одновременно и означают, что старший байт из регистра ЕАХ выдвигается в переменную R, а младший байт этого регистра заполняется очередным байтом исходной последовательности. Значение переменной R используется на шаге 3 в качестве индекса в таблице TABL_F для извлечения 16-битного значения, которое на шаге 4 будет объединено операцией XOR с содержимым старших 16 битов регистра ЕАХ.

Таким образом, в отличие от прямого алгоритма процесс преобразования вырастает до уровня байтов и содержит три операции: сдвига, доступа к таблице для извлечения нужного значения и операции XOR извлеченного значения с содержимым старшей половины ЕАХ. По окончании процесса в старшей половине ЕАХ будет содержаться значение CRC. Сообщение по-прежнему должно быть выровненным, то есть дополненным количеством битов, равным степени полинома, или для данного случая – 16.

Для практических приложений это крайне неудобно, и решение этой проблемы будет показано чуть ниже. Пока же разработаем программу вычисления содержимого таблицы на основе полинома 1021h степени 16.

:prg09_03.asm – программа вычисления содержимого таблицы:на основе полинома 1021h степени 16.
.data
tabl_16 dw 256 dup (0):CRC-таблица
len_tabl_16=$-tabl_16
adr_tabl_16 dd tabl_16
polinom dw 1021h
.code
les di,adr_tabl_16
add di.len_tabl_16-2
std:идем назад по таблице
mov ex.255
mov bx.polinom
ml: xor ax.ax
mov ah.cl:индекс в таблице для вычисления CRC
push ex сложенные циклы
mov ex. 8
m2: shl ax.l
jnc m3:старшие разряды не равны – выполняем сдвиг
: (частное нас не интересует);старшие разряды равны – выполняем XOR:
xor ax.bx:ax XOR polinom
m3: loop m2 _^
pop ex
stosw
loop ml

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

Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.