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