Как правильно рассчитать большой CRC32?
Вот статья, которая описывает, как вычислить CRC32 с максимальными 1024 байтами, используя встроенную инструкцию CRC32, найденную в современных процессорах x86-64. Тем не менее, мне нужно рассчитать CRC32 более 1024 байтов. Будет ли правильным вычислять CRC32 каждого блока из 1024 байтов и в итоге суммировать их, или это неверно? Если так, то как правильно это сделать?
2 ответа
Нет, просто добавление не сделает работу.
В статье, на которую вы ссылаетесь, рассказывается, как это сделать:
Вывод CRC одного вычисления используется в качестве начального CRC для следующего вычисления [...]
Чтобы охватить случай, когда конечный результат будет больше, чем 0xffffffff просто делать crc32 = ~crc32 & 0xffffffff после окончательного расчета.
Цитирую информацию из белой книги Intel, в которой упоминается ваша статья,
Вместо того, чтобы вычислять CRC всего сообщения традиционным линейным методом, мы используем более быстрый метод для разделения буфера произвольной длины на несколько меньших сегментов фиксированного размера, вычисляем CRC для этих сегментов параллельно с последующим этапом рекомбинации для вычисления эффективный CRC с использованием частичных CRC сегментов.
Также,
Окончательная рекомбинация CRC добавляет накладные расходы и может быть реализована с помощью таблиц поиска на микроархитектуре Nehalem - мы покажем, как это сделать, используя как можно меньше таблиц, в то же время обеспечивая превосходную общую производительность в диапазоне размеров. Инструкция PCLMULQDQ в микроархитектуре Westmere позволяет эффективно рекомбинировать CRC без таблиц поиска. Различные методы подробно объясняются в этой статье на реальных примерах кода.
Итак, вам нужно подробно изучить эту статью: Быстрые вычисления CRC для полинома iSCSI с использованием инструкции CRC32