Табличная реализация CRC.

Теорию и простейшие реализации CRC смотри_Тут_

Алгоритм SIMPLE - хорошее начало - ведь он опирается непосредственно на теорию и поэтому он прост. Возможно,так как он основан на битовых операциях, многим покажется этот алгоритм недостаточно эффективным - на каждый бит необходимо выполнить сдвиг. Чтобы поднять скорость нам нужно создать алгоритм, оперирующий не отдельными битами, а ,например, целыми байтами.

Будем рассматривать 32-битные полиномы (на самом деле они конечно 33- битные, но старший бит всегда равен 1 - поэтому реально влияют остальные 32 бита).

                  Операнд (Register)

                   3    2    1    0   Байты

                +----+----+----+----+

            <-- |    |    |    |    | <----- Следующий байт

                +----+----+----+----+



               1<------32 бит ------>

Алгоритм SIMPLE здесь тоже применим. Посмотрим, что он делает. Допустим, что старшие 8 бит операнда равны:

       t7 t6 t5 t4 t3 t2 t1 t0

В следующей итерации SIMPLE t7 определяет, будет-ли произведена операция XOR операнда с полиномом (t7=1) или нет (t7=0). Предполагая, что старшие 8 бит полинома g7..g0 после следующей итерации получим:

        t6 t5 t4 t3 t2 t1 t0 ??

+ t7 * (g7 g6 g5 g4 g3 g2 g1 g0)              

Новый старший бит (который контролирует, что произойдет при следующей итерации) теперь принимает значение t6+t7*g7. Важно понять, что вся информация, необходимая чтобы сосчитать новый старший бит, была в 2 старших битах исходного старшего байта. Т.о. значение старшего бита в операнде в k-ой итерации может быть вычислено из k битов операнда.

Допустим теперь, что мы сделали 8 итераций. Заметим следующее:

Теперь посмотрим, как работает XOR :

((A xor B) xor C) xor D = A xor ( B xor C xor D)
Например:
       0100010  Операнд

       ...0110  XOR

       ..0110.  XOR

       0110...  XOR

       -------

       0011000

       -------


Суть в том, что вместо того, чтобы ксорить последовательно, можно сначала отксорить полиномы (B,C,D в примере) а потом получившееся отксорить с операндом.

Возможно, Вам уже ясна идея. Давайте подведём итог в виде алгоритма:

   While (не конец сообщения)

      Begin

      Берем старший байт операнда

      Считаем контрольный байт из старшего байта операнда

      Суммируем все полиномы с различными смещениями чтобы ксорить

         операнд в соответствии с контрольным байтом

      Сдвигаем регистр влево на один байт, занося следующий с сообщении байт

         в младший байт операнда

      XOR просуммированные полиномы с операндом

      End

Хотя это уже не SIMPLE, но это ничем его не лучше. Но возможно большую часть вычислений предварительно занести в таблицу. В результате получаем:

   While (пока не кончилось сообщение)

      Begin

      Top = top_byte(Register);

      Register = (Register << 24) | next_augmessage_byte;

      Register = Register XOR precomputed_table[Top];

      End

//(Register == Операнд)

И всё!!! Если вы это поняли - вы поняли идею CRC алгоритма с таблицей. Это очень быстрый алгоритм требующий всего сдвиг, OR, XOR и обращение к таблице на один байт.

                  3    2    1    0   Байты

                +----+----+----+----+

         +-----<|    |    |    |    | <----- Следующий в сообщении байт

         |      +----+----+----+----+

         |                ^

         |                |

         |               XOR

         |                |

         |     0+----+----+----+----+       Алгоритм

         v      +----+----+----+----+       ---------

         |      +----+----+----+----+       1. Сдвиг операнда влево на байт,

         |      +----+----+----+----+          дочитывая новый байт в

         |      +----+----+----+----+          сообщении.

         |      +----+----+----+----+       2. Используем старший байт, только что

         |      +----+----+----+----+          вылетевший при сдвиге как индекс

         +----->+----+----+----+----+          таблицы из 256 32-битных значений.

                +----+----+----+----+       3. XOR табличное значение с

                +----+----+----+----+          операндом.

                +----+----+----+----+       4. Goto 1 если ещё есть непрочитанные

                +----+----+----+----+          байты в сообщении.

             255+----+----+----+----+





На C, этот алгоритм выглядит примерно так:



   r=0;

   while (len--)

     {

      byte t = (r >> 24) & 0xFF;

      r = (r << 8) | *p++;

      r^=table[t];

     }



len - длина сообщения в байтах, p - указывает на сообщение, r - операнд,

t - временная переменная,table - заранее просчитанная таблица. Если всё

слишком понятно - приведенную выше программку запишем так:



   r=0; while (len--) r = ((r << 8) | *p++) ^ t[(r >> 24) & 0xFF];

Не смотря на краткость и красоту строчки

   r=0; while (len--) r = ((r << 8) | *p++) ^ t[(r >> 24) & 0xFF];

опасно всё оставлять именно так. Проблема в том, что цикл оперирует с УВЕЛИЧЕННЫМ сообщением и для того чтобы использовать этот код вам необходимо добавить W/4 нулевых байта в конец сообщения и после указать p на него. В зависимости от обстановки это может быть или не быть проблемой; если блок с данными передается вам откуда-то извне, это будет БОЛЬШОЙ проблемой. Выходом может быть добавление следующей строчки после верхнего цикла, по одной на каждый нулевой байт:

      for (i=0; i<W/4; i++) r = (r << 8) ^ t[(r >> 24) & 0xFF];

Это уже довольно неплохо. Однако, для большей компактности мы можем реорганизовать этот цикл так, чтобы избежать добавления нулевых байтов в конец сообщения и дополнительной обработки последних байтов. Чтобы объяснить эту оптимизацию вернемся к диаграмме, рассмотренной нами ранее.

                   3    2    1    0   Байты

                +----+----+----+----+

         +-----<|    |    |    |    | <----- Увеличенное сообщение

         |      +----+----+----+----+

         |                ^

         |                |

         |               XOR

         |                |

         |     0+----+----+----+----+       Алгоритм

         v      +----+----+----+----+       --------

         |      +----+----+----+----+       1. Сдвиг операнда влево на байт,

         |      +----+----+----+----+          дочитывая новый байт в

         |      +----+----+----+----+          сообщении.

         |      +----+----+----+----+       2. Используем старший байт, только что

         |      +----+----+----+----+          вылетевший при сдвиге как индекс

         +----->+----+----+----+----+          таблицы из 256 32-битных значений.

                +----+----+----+----+       3. XOR табличное значение с

                +----+----+----+----+          операндом.

                +----+----+----+----+       4. Goto 1 если ещё есть непрочитанные

                +----+----+----+----+          байты в сообщении.

             255+----+----+----+----+

Теперь отметим следующие факты:

Хвост сообщения:

W/4 нулевых байта, дописанных в конец сообщения, будут добавлены справа в операнд, но их значения (0) не будут влиять на результат поскольку 1) XOR байта с нулем не меняет этот байт, и 2) W/4 байта никогда не выйдут за границы операнда где их значение могло бы на что-нибудь повлиять. Поэтому единственная функция W/4 дополнительных байтов это доведение до конца расчетов, связанных с проходом через операнд настоящего сообщения.

Начальное значение:

Начальное значение опнранда - 0, первые четыре итерации цикла нужны лишь для того, чтобы загнать первые четыре байта сообщения в операнд. Это так поскольку первые 32 бита все нули и в операнде ничего не ксорится. Даже если начальное значение не 0, первые 4 итерации алгоритма додут лишь эффект сдвига первых четырех байт в операнд и XOR'а их с какой-то константой (это функция начального значения операнда).

Эти факты в комбинации со свойством операции XOR

   (A xor B) xor C = A xor (B xor C)

означают, что байтам сообщения в действительности не надо путешествовать через W/4 байта операнда. Вместо этого, они могут ксориться со старшим байтом операнда перед выбором индекса из таблицы. Это приводит к следующей модификации алгоритма.

         +-----<Сообщение (не нарощенное)

         |

         v         3    2    1    0   Байты

         |      +----+----+----+----+

        XOR----<|    |    |    |    |

         |      +----+----+----+----+

         |                ^

         |                |

         |               XOR

         |                |

         |     0+----+----+----+----+       Алгоритм

         v      +----+----+----+----+       --------

         |      +----+----+----+----+       1. Сдвиг операнда влево на байт,

         |      +----+----+----+----+          дочитывая новый байт в

         |      +----+----+----+----+          сообщении.

         |      +----+----+----+----+       2. XOR старшего байта, только что

         |      +----+----+----+----+          вылетевший при сдвиге со следующим

         +----->+----+----+----+----+          байтом сообщения чтобы вычислить

                +----+----+----+----+          индекс тавлицы ([0,255]).

                +----+----+----+----+       3. XOR табличное значение с

                +----+----+----+----+          операндом.

                +----+----+----+----+       4. Goto 1 если ещё есть непрочитанные

             255+----+----+----+----+          байты в сообщении.

Это ИДЕНТИЧНЫЕ алгоритмы и они приводят к ИДЕНТИЧНЫМ результатам. Код на C в данном случае будет выглядеть примерно так:

   r=0; while (len--) r = (r<<8) ^ t[(r >> 24) ^ *p++];

и ЭТО тот код, который вы скорее всего встретите в реализациях алгоритмов CRC.

Начальные и конечные значеня

В добавок к уже рассмотренному, CRC алгоритмы отличаются друг от друга еще по двум признакам:

   * Начальное значение операнда.



   * Величина XOR'ящаяся с финальным значение операнда.

Например, алгоритм "CRC32" инициализирует операнд значением FFFFFFFF и ксорит финальное значение операнда с FFFFFFFF.

Большинство CRC алгоритмов инициализируют свой операнд нулем. Однако, есть алгоритмы делающие не так. В теории (т.е. не предполагая ничего о сообщении), начальное значение не влияет на эффективность CRC алгоритма, начальное значение лишь обеспечивает определенную стартовую точку с которой значение операнда начинает меняться. На практике одни сообщения более вероятны чем другие и было бы правильно инициализировать операнд значением, не имеющим "белых пятен", часто получающихся на практике. Под "белым пятном" имеется в виду последовательность байтов сообщения не меняющих значение операнда. В частности, любой CRC алгоритм, инициализирующий свой операнд нулем, будет иметь "белое пятно" если сообщение начинается с последоветельности нулей. Так как последоветельность нулей не редкость в реальных сообщениях, полезно стартовать алгоритм с ненулевого значения операнда.