Алгоритм хеширования FNV (Fowler-Noll-Vo) на Ассемблере

FNV (Fowler-Noll-Vo) - это семейство некриптографических хеш-функций, разработанное в 1990-х годах программистами Glenn Fowler, Landon Curt Noll и Kiem-Phong Vo. Изначально алгоритм создавался для быстрого и эффективного хеширования строк в системных утилитах и языках программирования, например, в Perl для реализации хеш-таблиц. Основные достоинства FNV - крайняя простота реализации, высокая производительность даже на слабых процессорах и хорошее распределение хешей для типичных данных: строк, идентификаторов, путей к файлам и подобных структур. При этом FNV не предназначен для криптографического применения: он подвержен коллизиям, предсказуем и не обеспечивает свойств, необходимых для защиты информации.

Алгоритм FNV работает исключительно с двумя простыми операциями - умножением на фиксированную константу (FNV prime) и побитовым исключающим ИЛИ (XOR). Благодаря такой минималистичной арифметике он отличается высокой скоростью и легко реализуется даже на архитектурах с ограниченными ресурсами. При этом FNV является потоковым: входные данные обрабатываются по одному байту за раз, без необходимости загружать весь объем в память, что делает его особенно удобным для обработки больших массивов или непрерывных потоков.

Исторически первой была версия FNV-0, в которой хеш инициализировался нулем. Однако этот подход оказался неудачным: для пустой строки и ряда коротких входов результат оказывался нулевым или легко предсказуемым. В ответ на это была введена версия FNV-1, использующая ненулевое начальное значение, известное как "offset basis". Сегодня в практическом применении доминируют две модификации: FNV-1 и FNV-1a. В FNV-1 на каждой итерации сначала происходит умножение текущего хеша на константу "FNV prime", а затем - XOR с очередным байтом входных данных. В FNV-1a порядок операций обратный: сначала выполняется XOR с байтом, затем - умножение. Несмотря на кажущуюся незначительность этого различия, FNV-1a обеспечивает значительно лучшее перемешивание хеш-значений, особенно для коротких ключей и строк с общими префиксами, что и объясняет его повсеместное предпочтение в современных системах.

Для 32-битной реализации начальное значение (offset basis) равно 0x811C9DC5, а константа (FNV prime) - 0x01000193. В 64-битной версии используются соответственно 0xCBF29CE484222325 и 0x100000001B3. Во всех случаях арифметика выполняется с естественным целочисленным переполнением: результат автоматически берётся по модулю 2³² или 2⁶⁴ в зависимости от разрядности. Это поведение аппаратно поддерживается большинством процессоров и не требует дополнительных операций маскирования. FNV-1a использует те же константы и начальные значения, что и FNV-1, но благодаря измененному порядку операций демонстрирует более равномерное распределение хешей, что особенно важно при работе с типичными данными, такими как идентификаторы, пути к файлам или короткие текстовые ключи.

Функция обрабатывает входной буфер побайтово, применяя операции умножения на FNV-простое число и XOR с каждым байтом в зависимости от выбранного варианта алгоритма (FNV-1 или FNV-1a).32-битный вариант функции принимает два параметра: lpData - указатель на входные данные (значение типа DWORD), и dSize - длина этих данных в байтах. Результат вычисления возвращается в регистре EAX в виде 32-битного хеш-значения.64-битный вариант функции принимает два параметра: lpData - указатель на входные данные (значение типа DWORD), и dSize - длина буфера в байтах. Результат вычисления возвращается в паре регистров EDX:EAX, где EAX содержит младшие 32 бита хеша, а EDX - старшие, образуя совместно 64-битное хеш-значение.

Поскольку официальной 128-битной спецификации FNV не существует, реализация основана на неофициальных эвристических константах.128-битный вариант функции принимает два параметра: lpData - указатель на входные данные (значение типа DWORD), и dSize - длина буфера в байтах. Результат возвращается в виде 128-битного хеш-значения, распределенного по четырем 32-битным регистрам: младшие 32 бита в EAX, следующие в EBX, затем в ECX, а старшие 32 бита в EDX (представление в порядке little-endian по регистрам).

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

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

Комментарии

Добавить комментарий

Для вставки цитаты выделите текст и нажмите сюда

Имя*:

Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.

Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.