Использование SuperFastHash вместо CRC32?

Question

Примечание: я не пытаюсь использовать SuperFastHash и ожидаю, что он выдаст те же выходные значения, что и CRC32.

Я пишу простое LZSS Процедура сжатия / распаковки, обеспечивающая очень быструю распаковку и не требующую дополнительной памяти при распаковке.Входные данные разбиваются на блоки длиной 4096 байт и сжимаются последовательно.

Моя проблема: я хочу добавить обнаружение ошибок для каждого сжатого блока (размер блока <= 4096 байт).Время ограничено, и поэтому процедура контрольной суммы должна быть очень быстрой.Я избегал криптографических алгоритмов (MD5, SHA1), потому что они требуют большого количества вычислений, и я выбрал CRC32 (более простой и очевидный алгоритм).</p>

После нескольких тестов я обнаружил, что CRC32 слишком медленный в отношении ограничений моего проекта.Я использовал enwik9 (10 ^ 9-байтовый текстовый дамп википедии) из здесь .Я сжал его, используя мою подпрограмму LZSS, и получил файл 570Mb.Я измерил следующие длительности (однопоточный, исключая дисковый ввод-вывод, все данные, загруженные в память перед обработкой, в среднем из 10 испытаний):

|          Operation            |  Time (GCC4.4.5/Linux)   |  Time (MSVC2010/Win7)  |
|-------------------------------+--------------------------+------------------------|
|        Decompression          |        6.8 seconds       |      6.95 seconds      |
|  CRC32 on decompressed result |        4.9 seconds       |      4.62 seconds      |
|   CRC32 on compressed result  |        2.8 seconds       |      2.69 seconds      |

Затем я протестировал SuperFastHash, просто из любопытства:

|          Operation            |  Time (GCC4.4.5/Linux)   |  Time (MSVC2010/Win7)  |
|-------------------------------+--------------------------+------------------------|
|  SFH on decompressed result   |        1.1 seconds       |      1.33 seconds      |
|   SFH on compressed result    |        0.7 seconds       |      0.75 seconds      |

А вот моя реализация CRC32 (я следовал описаниям из следующего документа: http://www.ross.net/crc/download/crc_v3.txt):

# include <stdint.h>

// CRC32 lookup table (corresponding to the polynom 0x04C11DB7)
static const uint32_t  crc32_lookup_table[256] =
{
    0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA,
    0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
    0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
    // many lines skipped
    // ...
    0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
} ;

uint32_t crc32_hash(const uint8_t * data, size_t len)
{
    uint32_t crc32_register = 0xFFFFFFFF ;
    while( len-- )
    {
        crc32_register = (crc32_register >> 8)
                       ^ crc32_lookup_table[(crc32_register & 0x000000FF) ^ *data++] ;
    }
    return crc32_register ^ 0xFFFFFFFF ;
}

Мой вопрос:

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

Спасибо за любой совет!

Answer 1

В SuperFastHash обнаружены некоторые проблемы, а также функция быстрого хэширования murmur2.Если вы ищете что-то настроенное для больших блоков данных с низким уровнем коллизий, вы можете попробовать 128-битные варианты хеш-кодов города Google (http://code.google.com/p/cityhash/) или murmur3.Есть также еще несколько нестандартных, таких как crap8 и crapwow, которые утверждают, что обеспечивают почти идеальное лавинное распределение битов и воронку и, таким образом, имеют почти нулевые коллизии, вы можете прочитать об этом и других нешифрованных хэш-функциях здесь:1004 *

Answer 2

Поскольку ваша проблема не в безопасности, вы можете использовать «сломанные» криптографические хеш-функции, которые не защищены от атакующего, но все же очень хороши при обнаружении ошибок передачи.Я имею в виду MD4 , который был измерен быстрее некоторых CRC32 на некоторых платформах.Вы также можете проверить RadioGatún и Панаму;см. эту библиотеку для реализации с открытым исходным кодом в C и Java различных криптографических хеш-функций.

Если ваша целевая архитектура - достаточно новый / достаточно большой x86-процессор с AES-NI инструкций, тогда вы могли бы чертовски быстро и очень хорошую контрольную сумму просто вычислить CBC-MAC с блочным шифром AES и обычным ключом (например, ключом с нулевым ключом);поскольку это не для безопасности, вы можете использовать меньше раундов, чем стандартное AES (например, 5 раундов вместо стандартных 10).

Answer 3

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

Я думаю, что SuperFastHash обладает этим свойством. Он может быть немного более уязвим для коллизий (поскольку он, по-видимому, менее анализируется сообществом), но это не должно препятствовать использованию, которое вы имеете в виду.

Удачи:)