Табличные алгоритмы вычисления CRC
Основы
Для того чтобы лучше понять суть табличного алгоритма вычисления CRC, обратимся опять к прямому методу, точнее к той схеме его вычисления (см. рис. 9.6), которая была реализована в приведенной выше программе.
Из этой схемы видно, что для текущего содержимого старшей половины регистра ЕАХ можно прогнозировать, как будет изменяться содержимое его битов по мере их сдвига. Для этого достаточно подвергнуть анализу его биты начиная с самого старшего. Допустим, что старшие 8 бит ЕАХ равны а7 а6 а5 а4 а3 а2 а, а,,. При следующем сдвиге (см. рис. 9.6) прямой алгоритм определяет, будет ли произведена операция XOR операнда с полиномом b7 b6 b5 b4 b3 b2 b, bо в ВХ (а7=1) или нет (а7=0).
Если выдвинутый бит был равен 1, то прежнее содержимое старшей половины регистра ЕАХ будет подвергнуто операции XOR с соответствующими битами полинома. В обратном случае, если выдвинутый бит был равен 0, значения битов будут не изменены, а просто сдвинуты влево на одни разряд. В принципе, имея большое желание, можно рассчитать заранее, каким будет содержимое к-го бита в к-й итерации сдвига. К примеру, значение нового старшего бита, определяющего действия алгоритма в следующей итерации, можно рассчитать по содержимому двух старших битов старшего байта исходного операнда – а6 XOR а7 AND b7, где b7 – старший бит полинома (всегда равный единице).
Теперь остановимся для того, чтобы рассмотреть и обсудить очередную схему (рис. 9.7).
Рис. 9.7. Влияние на регистр ЕАХ серии операций XOR при вычислении CRC
Из рассуждений выше следует, что если взять для рассмотрения старший байт операнда, то по его содержимому можно однозначно предположить, сколько операций XOR и когда будет выполнено (см. рисунок). Обозначим старшую половину регистра ЕАХ как переменную А, а операнды со значениями полинома, объединяемые с А при единичном состоянии очередного выдвигаемого слева бита, обозначим соответственно как В, С, D (помним, что В = С = D). Тогда формирование результата Е можно представить формулой:
Е-((А [сдвиги| XOR В) |сдвиги| XOR С) |сдвиги| XOR D
Здесь | сдвиги | представляют собой значение от 0 до 7 и определяются текущим содержимым старшего байта операнда (регистра ЕАХ). Благодаря ассоциативному свойству операции XOR тот же самый результат можно получить, если предварительно выполнить операцию XOR над полиномами В, С, D с соответствующими значениями сдвигов, а затем результат объединить по XOR с А:
F: = 1 сдвиги| XOR (В |сдвиги| XOR С |сдвиги| XOR D) Е: = A XOR F
Из этих рассуждений следуют важные выводы:
- величина F является совершенно точно предсказуемой по содержимому старшего байта операнда;
- если величина F определяется содержимым старшего байта операнда и собственно значением полинома, то существует всего 256 возможных значений этой величины (по количеству значений, представимых беззнаковым байтом);
- исходя из первых двух положений величина F не зависит от значения операнда и может быть рассчитана заранее, при этом результаты ее расчетов можно свести в таблицу (!).