Источник: guildalfa

Александр Шарахов

Эти заметки дополняют мою статью "Параллельное вычисление CRC32". Предлагается алгоритм вычисления CRC64, основанный на тех же идеях. Производительность алгоритма в 2-2.5 раза выше стандартной табличной реализации вычисления CRC64. На компьютере с процессором E6850/3.2GHz он расходует 2.66 такта процессора на байт, т.е. скорость обработки данных при вычислении CRC64 составляет 0.375 байта за такт центрального процессора или 1.2*10^9 байтов в секунду.

Стандартный табличный алгоритм вычисления CRC64.

Для вычисления CRC64 мы будем использовать многочлен 42F0E1EBA9EA3693 (ECMA DLT). У другого кандидата на эту роль - многочлена 000000000000001B (ISO 3309) - из-за его недостаточной плотности было обнаружено большое число коллизий на реальных данных. Стандартный табличный алгоритм вычисления CRC64 выглядит примерно так:

//Вариант 1 стандартный табличный алгоритм вычисления нормальной CRC64
procedure ReferenceRefreshCRC64(var CRC: int64; BufPtr: pointer; BufLen: integer);
asm
  test edx, edx
  jz @ret
  neg ecx
  jge @ret
  sub edx, ecx
 
  push ebx
  push esi
  push edi
  push eax
 
  mov ebx, [eax+4]
  mov esi, [eax]
  mov eax, ebx
 
@next:
  movzx edi, byte [edx + ecx]
  shr ebx, 24
  xor edi, ebx
  shld eax, esi, 8
  xor eax, [edi*8 + ReferenceTable64 + 4]
  shl esi, 8
  xor esi, [edi*8 + ReferenceTable64]
  mov ebx, eax
  add ecx, 1
  jz @done
 
  movzx edi, byte [edx + ecx]
  shr eax, 24
  xor edi, eax
  shld ebx, esi, 8
  xor ebx, [edi*8 + ReferenceTable64 + 4]
  shl esi, 8
  xor esi, [edi*8 + ReferenceTable64]
  mov eax, ebx
  add ecx, 1
  jnz @next
 
@done:
  pop eax
  mov [eax], esi
  mov [eax+4], ebx
  pop edi
  pop esi
  pop ebx
@ret:
  end;

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

Этот вариант алгоритма вычисления CRC64 мы будем использовать в качестве отправной точки, его скорость работы почти совпадает со скоростью работы стандартной реализации вычисления CRC32 на двух протестированных компьютерах (E6850 и Pentium-D).

Зачем нам кузнец.

Внимательный читатель, глядя на приведенный код, наверняка заметил, что в противоположность CRC32 при подсчете CRC64 применяется нормальная, а не зеркальная форма представления многочлена и контрольной суммы. Так велит стандарт, именно нормальная форма используется, например, в PostgreSQL и других продуктах.

Понятно, что нормальный алгоритм медленнее зеркального из-за того, что требуется выполнить две лишние операции: копирование старшего слова контрольной суммы и сдвиг старшего байта контрольной суммы. Копирование мы нейтрализовали развертыванием цикла, а вот что делать со сдвигом?

Давайте на секунду отвлечемся и посмотрим, как выглядит реализация зеркального алгоритма вычисления CRC64:

//Вариант 2 стандартный табличный алгоритм вычисления зеркальной CRC64
//на E6850 работает в 1.15 раза быстрее варианта 1
//на Pentium-D работает в 1.1 раза быстрее варианта 1
procedure ReflectedRefreshCRC64(var CRC: int64; BufPtr: pointer; BufLen: integer);
asm
  test edx, edx
  jz @ret
  neg ecx
  jge @ret
  sub edx, ecx
 
  push ebx
  push esi
  push eax
 
  mov ebx, [eax]
  mov esi, [eax+4]
  xor eax, eax
@next:
  mov al, byte [edx + ecx]
  xor al, bl
  shrd ebx, esi, 8
  xor ebx, [eax*8 + ReflectedTable64]
  shr esi, 8
  xor esi, [eax*8 + ReflectedTable64 + 4]
  add ecx, 1
  jnz @next
 
@done:
  pop eax
  mov [eax], ebx
  mov [eax+4], esi
  pop esi
  pop ebx
@ret:
  end;

Сравнивая алгоритмы 1 и 2, мы видим, что их отличия заключаются в использовании разных таблиц остатков и разных направлений в операциях сдвига. Понятно также, что нормальный и зеркальный алгоритмы по-разному извлекают очередной байт контрольной суммы для формирования индекса в таблице остатков.

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

//Вариант 3 усовершенствованный алгоритм вычисления нормальной CRC64
//используется таблица остатков с зеркально переставленными байтами  
//на E6850 работает в 1.15 раза быстрее варианта 1
//на Pentium-D работает в 1.1 раза быстрее варианта 1
procedure NormalRefreshCRC64(var CRC: int64; BufPtr: pointer; BufLen: integer);
asm
  test edx, edx
  jz @ret
  neg ecx
  jge @ret
  sub edx, ecx
 
  push ebx
  push esi
  push eax
 
  mov ebx, [eax+4]
  mov esi, [eax]
  bswap ebx
  bswap esi
  xor eax, eax
@next:
  mov al, byte [edx + ecx]
  xor al, bl
  shrd ebx, esi, 8
  xor ebx, [eax*8 + ByteSwappedTable64]
  shr esi, 8
  xor esi, [eax*8 + ByteSwappedTable64 + 4]
  add ecx, 1
  jnz @next
 
@done:
  bswap ebx
  bswap esi
  pop eax
  mov [eax+4], ebx
  mov [eax], esi
  pop esi
  pop ebx
@ret:
  end;

Скорость этого варианта алгоритма равна скорости зеркального и на процессоре E6850 примерно в 1.15 раза выше, чем у первого варианта.

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

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

Но сначала заметим, что в случае вычисления CRC64 нет необходимости создавать полностью параллельный алгоритм, как мы это делали для CRC32. Вполне достаточно и кусочно-параллельного алгоритма: ведь если мы будем обрабатывать сообщение порциями по 64 бита, то старшая и младшая части контрольной суммы будут обрабатываться независимо. Причем, по сравнению с CRC32, количество операций чтения табличных данных увеличится в 2 раза, а количество операций, необходимых для формирования адреса, останется прежним, поэтому задержка генерации адреса представляется маловероятной.

Основной цикл алгоритма мы позаимствуем из кусочно-параллельного алгоритма вычисления CRC32. В случае CRC64 он будет выглядеть так:

//Вариант 4 вычисления нормальной CRC64, работа с 64-битными блоками сообщения
//используется таблица остатков с зеркально переставленными байтами  
//на E6850 работает в 2.45 раза быстрее варианта 1
//на Pentium-D работает в 2.0 раза быстрее варианта 1
@bodyloop:
  mov eax, [edx + ebp - 8]
  xor eax, ebx
  movzx edi, al
  mov ecx, [edx + ebp - 4]
  xor ecx, esi
  mov ebx, [edi*8 + ByteSwappedTable64 + 2048*7]
  mov esi, [edi*8 + ByteSwappedTable64 + 2048*7 + 4]
  movzx edi, ah
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*6]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*6 + 4]
  shr eax, 16
  movzx edi, al
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*5]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*5 + 4]
  movzx edi, ah
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*4]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*4 + 4]
 
  movzx edi, cl
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*3]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*3 + 4]
  movzx edi, ch
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*2]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*2 + 4]
  shr ecx, 16
  movzx edi, cl
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*1]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*1 + 4]
  movzx edi, ch
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*0]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*0 + 4]
 
  add ebp, 8
  jle @bodyloop

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

Мы используем таблицу остатков размером 8x256 учетверенных слов, построенную аналогично таблице параллельного алгоритма вычисления CRC32. Еще раз заметим, что только от этой таблицы зависит, какая контрольная сумма (нормальная или зеркальная) вычисляется в основном цикле.

Скорость этого варианта алгоритма вычисления CRC64 на процессоре E6850 примерно в 2.45 раза выше, чем у первого варианта, и по очевидной причине примерно в 2 раза ниже достигнутой нами ранее скорости вычисления CRC32.

Заключение.

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

Читатели, используя прилагаемые к статье исходные тексты, могут проверить работу алгоритмов на других процессорах. Буду признателен, если результаты тестов будут ими добавлены на мою страничку (http://guildalfa.ru/alsha/node/4).

Те, кто дочитал до конца, могут снять комментарии кое-где в исходных текстах и поэкспериментировать с зеркальной формой многочлена, который предложил David T. Jones в качестве замены ISO 3309 для хеширования белковых последовательностей. По идее этот многочлен должен хорошо хешировать текстовые данные. При сравнении результатов имейте ввиду, что David T. Jones не выполняет инвертирование значений битов результата в конце вычислений.

Ссылки по теме

Параллельное вычисление CRC64

Стандартный табличный алгоритм вычисления CRC64.

Зачем нам кузнец.

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

Заключение.