Александр Шарахов
дата публикации 14-05-2009 10:56

---

Версия для печати

Введение

Предлагаю вашему вниманию еще один подход к построению алгоритмов вычисления CRC32. Хотя многие использованные в нем идеи в той или иной мере содержатся в известных руководствах по оптимизации кода для IA32 и вычислению CRC32, он может представлять некоторый интерес. Использование свойств CRC-арифметики позволило разработать алгоритм вычисления CRC32, имеющий производительность в 3-5 раз выше стандартной табличной реализации. Например, на компьютере с процессором E6850/3.2GHz он расходует 1.33 такта процессора на символ, т.е. скорость обработки данных при генерации CRC32 составляет 0.75 символа за такт центрального процессора или 2.4*10^9 символов в секунду.

Несколько слов о CRC-арифметике

CRC-арифметика оперирует многочленами, имеющими коэффициенты 0 и 1. Для представления таких многочленов в компьютере используются двоичные числа, имеющие соответствующие значения битов. Операции над битами этих чисел выполняются без межразрядных переносов и заемов. В качестве операций сложения и вычитания используется "исключающее или". Умножение и деление с остатком выполняются как обычно при помощи серии сдвигов и сложений.

CRC-арифметика обладает двумя важными свойствами, которые лежат в основе всех связанных с ней алгоритмов:

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

В частности, свойство 2 означает, что произведение многочлена на x^n имеет такой же остаток от деления на некоторый делитель, как и произведение на x^n остатка от деления этого многочлена на тот же делитель.

Применяя теорию

Известно, что при вычислении контрольной суммы по алгоритму CRC32 сообщение рассматривается как многочлен и что (если не учитывать инициализацию и финализацию) контрольная сумма CRC32 представляет собой остаток от деления этого многочлена, умноженного на x^32, на "магический" многочлен 32-й степени.

Делить многочлены "столбиком" со сдвигом на 1 бит на каждой итерации слишком медленно, поэтому на практике используют более быстрые алгоритмы, основанные на свойствах CRC-арифметики. Давайте рассмотрим, как это делается, на примере алгоритма, работающего с группами из восьми битов. Пусть в качестве сообщений у нас выступают ASCII-строки, и предположим, что мы уже умеем вычислять остаток для любого односимвольного сообщения. Требуется вычислить остаток для строки 'ABC'.

Будем вычислять остаток посимвольно. Присвоим текущей строке значение, равное первому символу 'A'. Это односимвольное сообщение, и по условию задачи для него мы умеем вычислять остаток. Запишем это значение в текущий остаток. Текущий остаток может храниться в 32-битной переменной, т.к. его степень всегда меньше 32. Текущая строка — понятие виртуальное, вместо нее можно хранить адрес текущего байта данных.

Припишем к текущей строке второй символ 'B'. Как теперь вычислить остаток для получившейся строки 'AB'? Мысленно разобьем ее биты на две строки: двухсимвольную 'A'#0 и односимвольную 'B'. Сумма многочленов, соответствующих этим строкам, равна многочлену, соответствующему неразбитой строке. В таком случае свойство 1 позволяет нам вычислить остатки для строк, полученных в результате разбиения, и сложить. Причем по условию задачи для односимвольной строки мы умеем вычислять остаток.

Чтобы вычислить остаток для двухсимвольной строки 'A'#0, воспользуемся свойством 2. Заметим, что ее значение получено из прежнего текущего значения приписыванием справа нулевого символа, что эквивалентно умножению соответствующего строке многочлена на x^8. Значит, мы должны просто умножить текущий остаток на x^8 (сдвинуть влево на 8 разрядов) и вычислить остаток для полученного произведения. Произведение будет состоять из двух частей: старшие 8 бит, вытолкнутые за разрядную сетку, и младшие 24 бита, сдвинутые влево. Понятно, что младшая часть сама по себе продолжает оставаться остатком, а старшая часть соответствует некоторому односимвольному сообщению (для которого мы умеем вычислять остаток), и по свойству 1 нам остается лишь сложить эти остатки.

Наконец, припишем к текущей строке третий символ и разобьем ее на две 'AB'#0 и 'C'. Снова пересчитаем текущий остаток. Задача решена.

Таким образом, для каждого байта данных мы в цикле делаем следующее:

• сдвигаем текущее значение CRC на 8 битов влево,
• прибавляем к результату значение CRC для байта, выдвинутого за разрядную сетку,
• прибавляем к результату значение CRC для очередного байта.

Если мы планируем хранить значения CRC для однобайтовых сообщений в таблице, то имеет смысл для уменьшения числа обращений к таблице еще раз применить свойство 1 и модифицировать алгоритм следующим образом:

• сдвигаем текущее значение CRC на 8 битов влево,
• складываем (по правилам CRC-арифметики) очередной байт данных и байт, выдвинутый за разрядную сетку,
• прибавляем к текущему значению CRC значение CRC для полученного байта.

Стандартный табличный алгоритм

Фактически в приведенном выше примере описан стандартный табличный алгоритм вычисления CRC32: обработка битов сообщения группами по 8 бит, хранение в таблице предварительно вычисленных значений остатков для всех однобайтовых сообщений. Некоторые несущественные детали остались за кадром, например, использование сдвига вправо вместо сдвига влево для совместимости с аппаратурой.

Существуют две примерно равных по скорости ассемблерных реализации стандартного табличного алгоритма, которые различаются способом загрузки в регистр очередного байта данных:

//Вариант 1 загрузка данных командой MOVZX function RefreshCRC11(OldCRC: cardinal; StPtr: pointer; StLen: integer): cardinal; asm test edx, edx jz @ret neg ecx jz @ret sub edx,ecx push ebx @next: movzx ebx, byte [edx + ecx] xor bl, al shr eax, 8 xor eax, [ebx*4 + tbl] add ecx, 1 jnz @next pop ebx @ret: end; //Вариант 2 загрузка данных командой LODSB //на E6850 работает в 1.16 раза БЫСТРЕЕ варианта 1 //на Pentium-D работает в 1.66 раза МЕДЛЕННЕЕ варианта 1 function RefreshCRC11s(OldCRC: cardinal; StPtr: pointer; StLen: integer): cardinal; asm test edx, edx jz @ret test ecx, ecx jz @ret push esi push edi mov esi, edx lea edi, tbl add ecx, edx mov edx, eax xor eax, eax @next: lodsb xor al, dl shr edx, 8 xor edx, [eax*4 + edi] cmp esi, ecx jne @next mov eax, edx pop edi pop esi @ret: end;

Соотношение скоростей этих вариантов может меняться в зависимости от процессора.

Больше незачем платить?

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

//Вариант 3 - развернутый цикл, загрузка данных командой MOVZX //на E6850 работает с той же скоростью, что и вариант 1 //Предупреждение: часть команд в теле цикла специально удалена, // вычисление CRC32 выполняется неверно @next: mov edx, [esi + ecx] movzx ebx, dl xor bl, al xor eax, [ebx*4 + tbl] movzx ebx, dh xor bl, al xor eax, [ebx*4 + tbl] shr edx, 16 movzx ebx, dl xor bl, al xor eax, [ebx*4 + tbl] movzx ebx, dh xor bl, al xor eax, [ebx*4 + tbl] add ecx, 4 jnz @next

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

Большой табличный алгоритм

Попробуем пойти другим путем. Увеличим количество битов в группе в два раза, т.е. будем работать со словами, а не с байтами. Естественно, при этом нам придется увеличить размер таблицы в 256 раз, т.к. теперь в ней будут храниться контрольные суммы для всех двухбайтовых сообщений. Размер таблицы составит 256K.

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

//Вариант 4 - пословная обработка, таблица на 64K значений CRC //на E6850 работает в 1.34 раза медленнее варианта 1 @next: lodsw xor ax, dx shr edx, 16 xor edx, [eax*4 + edi] cmp esi, ecx jne @next

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

Кусочно-параллельный алгоритм

Давайте представим себе, какой должна быть оптимальная реализация. Во-первых, скорость чтения сообщения должна быть достаточно высокой, поэтому желательно чтение сообщения выполнять двойными словами. Во-вторых, желательно уменьшить зависимость между инструкциями, относящимися к различным группам битов. Нам хотелось бы оперировать большими группами битов, например, также двойными словами. Но в этом случае таблица будет просто огромной — 2^32 элементов. Даже если ее было бы возможно поместить в памяти приложения, из-за промахов чтения скорость работы с ней была бы очень низкой.

Снова вспомним о свойстве 1 CRC-арифметики. Благодаря ему мы можем вместо обращения к большой таблице за значением остатка для четырехбайтовой строки stuv вычислить это значение на лету как сумму остатков для строк s#0#0#0, t#0#0, u#0, v. Естественно, для этого нам потребуются еще 3 дополнительных таблицы остатков, содержащие по 256 элементов каждая. Работа с 32-битными порциями данных упрощает алгоритм и может дополнительно увеличить его скорость, т.к. теперь все инструкции логического сложения становятся 32-битными, а сдвиг текущего остатка на 32 бита можно опустить:

//Вариант 5 - таблица на 1K значений CRC //на E6850 работает примерно в 2.5 раза быстрее варианта 1 @next: mov edx, [esi + ecx] xor edx, eax movzx ebx, dl mov eax, [ebx*4 + tbl + 1024*3] movzx ebx, dh xor eax, [ebx*4 + tbl + 1024*2] shr edx, 16 movzx ebx, dl xor eax, [ebx*4 + tbl + 1024*1] movzx ebx, dh xor eax, [ebx*4 + tbl + 1024*0] add ecx, 4 jnz @next

Этот вариант алгоритма показывает скорость примерно в 2.5 раза выше, чем первый. Такой скачек производительности стал возможен потому, что здесь уже нет зависимости между вычислениями для байтов в одном двойном слове. Соответствующие микрокоманды процессор исполняет параллельно. Но зависимость между вычислениями для двойных слов сохраняется. Попробуем развернуть цикл и занять процессор полезной работой во время вынужденных простоев:

//Вариант 6 - таблица на 1K значений CRC, развернутый цикл //на E6850 работает примерно в 2.7 раза быстрее варианта 1 @next: xor eax, [edx + ecx - 8] mov ebx, [edx + ecx - 4] movzx esi, al movzx edi, ah xor ebx, [esi*4 + tbl + 1024*3] xor ebx, [edi*4 + tbl + 1024*2] shr eax, 16 movzx esi, al movzx edi, ah xor ebx, [esi*4 + tbl + 1024*1] xor ebx, [edi*4 + tbl + 1024*0] movzx esi, bl mov eax, [esi*4 + tbl + 1024*3] movzx esi, bh shr ebx, 16 xor eax, [esi*4 + tbl + 1024*2] movzx esi, bl xor eax, [esi*4 + tbl + 1024*1] movzx esi, bh xor eax, [esi*4 + tbl + 1024*0] add ecx, 8 jle @next

Нам удалось повысить скорость еще на 10%, но так и не удалось устранить зависимость вычислений при переходе через границу двойного слова.

Параллельный алгоритм

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

Фактически мы будем обрабатывать сообщение 64-битными блоками. Аналогично предыдущему варианту алгоритма мы будем рассматривать каждый блок как восьмибайтовое сообщение и разбивать его на 8 сообщений, для которых будем брать значение CRC из таблицы.

Таблица остатков содержит 2K значений и представляет собой матрицу 8x256, каждая цепочка инструкций использует половину строк этой таблицы. Значения в первой строке матрицы совпадают со значениями в таблице стандартного табличного алгоритма — это остатки для всевозможных однобайтовых сообщений. Во второй строке содержатся остатки для всевозможных двухбайтовых сообщений, оканчивающихся нулевым байтом. В третьей — остатки для трехбайтовых сообщений, оканчивающихся двумя нулевыми байтами, и т.д.

Чтобы исключить операции пересылки текущего значения остатка, основной цикл алгоритма пришлось развернуть:

//Вариант 7 - таблица на 2K значений CRC, развернутый цикл //на E6850 работает примерно в 4.65 раза быстрее варианта 1 //0.75 символа за такт на E6850 @next: mov ebx, [edi + ecx - 4] xor edx, [edi + ecx - 8] movzx esi, bl mov eax, [esi*4 + tbl + 1024*3] movzx esi, bh xor eax, [esi*4 + tbl + 1024*2] shr ebx, 16 movzx esi, bl xor eax, [esi*4 + tbl + 1024*1] movzx esi, bh xor eax, [esi*4 + tbl + 1024*0] movzx esi, dl xor eax, [esi*4 + tbl + 1024*7] movzx esi, dh xor eax, [esi*4 + tbl + 1024*6] shr edx, 16 movzx esi, dl xor eax, [esi*4 + tbl + 1024*5] movzx esi, dh xor eax, [esi*4 + tbl + 1024*4] add ecx, 8 jg @done mov ebx, [edi + ecx - 4] xor eax, [edi + ecx - 8] movzx esi, bl mov edx, [esi*4 + tbl + 1024*3] movzx esi, bh xor edx, [esi*4 + tbl + 1024*2] shr ebx, 16 movzx esi, bl xor edx, [esi*4 + tbl + 1024*1] movzx esi, bh xor edx, [esi*4 + tbl + 1024*0] movzx esi, al xor edx, [esi*4 + tbl + 1024*7] movzx esi, ah xor edx, [esi*4 + tbl + 1024*6] shr eax, 16 movzx esi, al xor edx, [esi*4 + tbl + 1024*5] movzx esi, ah xor edx, [esi*4 + tbl + 1024*4] add ecx, 8 jle @next mov eax, edx @done:

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

Соответствующие результаты для процессора Pentium-D не так впечатляют (3.13 и 1.48). Читатели, используя прилагаемые к статье исходные тексты, могут проверить работу алгоритма на других процессорах. Буду признателен, если результаты тестов будут ими добавлены на мою страничку.

Заключение

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

На свойствах CRC-арифметики построены и другие алгоритмические трюки. В ряде публикаций, например, приводится описание алгоритма подгонки CRC файла к заданному значению при помощи изменения четырех смежных байтов. Если вы дочитали до этого места, то, вероятно, вам будет интересно самим разобраться, как это делается. А может быть, вы предложите алгоритм вычисления CRC нескольких сцепленных файлов? Или алгоритм вычисления CRC всех фраз предложения, состоящих из N последовательных слов? Или собственную реализацию CRC64?

К статье прилагается пример