Самый быстрый и наименее ресурсоёмкий алгоритм расчёта контрольных сумм?

Question

[Александр Шишенко]

Блоки, которые необходимо хешировать занимают не более 128 килобайт. Предполагается использовать в сетевом приложении для проверки целостности данных.

Answer 1

[fossdev]

CRC32-C (это разновидность crc32 с полиномом 0x82F63B78), он самый быстрый на новых Intel'ах потому что в в набор sse4.2 входит инструкция для его аппаратной поддержки. На других процессорах он по скорости равен обычному crc32, т.е. тоже очень быстрый.

Comments

[homm]

Ну а xor есть в процессорах с 8086.

[Александр Шишенко]

Спасибо! Пожалуй, стоит использовать именно его. А как на с++ написать код, который использовал бы sse4.2 с помощью gcc?

[gribozavr]

#include <nmmintrin.h>

Answer 2

[darkdimius]

посмотрите в сторону CRC

Comments

[darkdimius]

Есть еще более быстрые, например Adler-32 и Murmur2. Но они менее «стандартны». Murmur2 достаточно новый и его популярность растет(она используется в Scala, nginx, libstdc++, Hadoop).

[Maxim Avanov]

Murmur2 достаточно старый и в нём есть алгоритмические недостатки, приводящие к 97% вероятности коллизий на синтетических тестах. Используйте MurmurHash3, если нужен именно он. Или CRC32, т.к. он разрабатывался как раз для обнаружения битовых ошибок.

Answer 3

[homm]

xor

Answer 4

[zapimir]

Тут еще многое от реализации алгоритма зависит, к примеру, в hash функции встроенной в PHP, самый быстрый алгоритм md5, а crc32 почти в 2 раза медленнее, а тот же adler32 в 4 раза медленнее, хотя по описаниям в той же wiki должен быть одним из самых быстрых как раз adler32.