В этой статье мы представим свою попытку реализации интересного алгоритма хэширования PolymurHash. Этот алгоритм представляет собой хэш-функцию с очень низкой вероятностью коллизии, а из-за малого размера хэша и некоторых ухищрений создателей такая функция подойдет для реализации хэш-таблиц.
Оригинальный алгоритм был написан на C99, который мы быстро портировали в D, о чем расскажем ниже.
PolymurHash – это, согласно заверением авторов алгоритма, универсальная хэш-функция, которая пригодна для использования в хэш-таблицах. Также этот алгоритм обладает следующими свойствами:
- Математически доказанная низкая вероятность коллизий: При инициализации с независимо выбранным случайным начальным значением, для любой пары различных входных данных m и m′ длиной до n байт вероятность того, что h(m)=h(m′), не превышает n×2−60.2. Это свойство известно как почти универсальная хеш-функция. На самом деле, PolymurHash обладает более сильным свойством: эта функция почти парно независима. Для любых двух различных входных данных m и m’ вероятность того, что они будут хешироваться в пару конкретных 64-битных хеш-значений (x,y), не превышает n×2−124.2;
- Высокая скорость для коротких входных данных, при этом не медленная для длинных входных данных: На машине Apple M1 она может хешировать любые входные данные длиной до 49 байт за 21 цикл, и обрабатывает 33.3 GiB/сек (11.6 байт/цикл) для длинных входных данных;
- Кроссплатформенность: Не использует расширенные наборы инструкций, такие как CLMUL или AES-NI. Для хорошей скорости требуется только нативное 64 x 64 -> 128 битное умножение, которое поддерживается почти всеми 64-битными процессорами.
- Компактность кода и памяти: Игнорируя определения для кроссплатформенной совместимости, хеш-функция и процедура инициализации занимают чуть более 100 строк кода на C. Инициализированная хеш-функция использует 32 байта памяти для хранения своих параметров и требует только небольшого постоянного объема стековой памяти при вычислении хеша.
Подобные определения, мы оставляем на совести авторов алгоритма, но тем не менее описание свойств алгоритма нас заинтересовало. Особенно то, что сама реализация обещает быть компактной.
И алгоритм действительно небольшой: сам PolymurHash представляет собой один заголовочный файл на C, в котором представлены несколько функций, уже пригодных к использованию. Этих функций три:
- void polymur_init_params(PolymurHashParams* p, ulong k, ulong s) – инициализация структуры с параметрами алгоритма, а также загрузка двух 64-битных секретов;
- void polymur_init_params_from_seed(PolymurHashParams* p, ulong seed) – инициализация структуры с параметрами алгоритма, и использование одного 64-битного секрета;
- ulong polymur_hash(const ubyte* buf, size_t len, const PolymurHashParams* p, ulong tweak) – получение 64-битного хэша (это и есть результат PolymurHash) из массива байтов buf длиной len и с использованием прединициализированных параметров p и уникальной величины донастройки алгоритма tweak.
Это необходимый минимум для работы с хэш-функцией PolymurHash и это все, что надо реализовать. Однако, небольшой набор пояснений: функция хэширования принимает произвольный набор байтов и выполняет его хэширование, для работы которого необходимо подготовка. Подготовка заключается в том, что требуется задать значения для структуры PolymurHashParams и выполнить ее инициализацию с помощью любой из двух первых функций. Инициализация происходит с помощью одного или двух специальных значений (секретов или seed), которые выбираются случайным образом. Стоит заметить, что выбор инициализации только с одним секретом никак не ослабит функцию – поскольку один секрет разворачивается в два полноценных значения.
После инициализации, мы можем вычислять любые хэши, предоставляя байтовый буфер с его длиной и некоторое выбранное нами значение донастройки (так называемый tweak). Это значение мы фиксируем, и при операциях хэширования и сравнения хэша, это значение не должно меняться. Как правило, значение донастройки используется для того, чтобы дополнительно усилить алгоритм, делая его слегка параметризуемым.
PolymurHash состоит из стандартных побитовых операций, базовой арифметики со 128-битным целыми, функции смешивания, а также базовой инициализации и самого хэширования.
Побитовые операции используются для разных целей и в основном стандартных: определение порядка байтов, построение 32-битных чисел, перестановка байтов в 32-битном числе и компоновка их в 64 битное значение и тому подобных:
static bool polymur_is_little_endian()
{
uint v = 1;
return cast(bool)*(cast(ubyte*)&v);
}
static uint polymur_bswap32(uint v)
{
return ((v >> 24) & 0x000000ff) | ((v >> 8) & 0x0000ff00UL) | ((v << 8) & 0x00ff0000) | ((v << 24) & 0xff000000);
}
static ulong polymur_bswap64(ulong v)
{
return (cast(ulong) polymur_bswap32(cast(uint) v)) << 32 | polymur_bswap32(cast(uint)(v >> 32));
}
static uint polymur_load_le_u32(const ubyte* p)
{
uint v = 0;
memcpy(&v, p, 4);
return polymur_is_little_endian() ? v : polymur_bswap32(v);
}
static ulong polymur_load_le_u64(const ubyte* p)
{
ulong v = 0;
memcpy(&v, p, 8);
return polymur_is_little_endian() ? v : polymur_bswap64(v);
}
// Loads 0 to 8 bytes from buf with length len as a 64-bit little-endian integer.
static ulong polymur_load_le_u64_0_8(const ubyte* buf, size_t len)
{
if (len < 4)
{
if (len == 0)
return 0;
ulong v = buf[0];
v |= buf[len / 2] << 8 * (len / 2);
v |= buf[len - 1] << 8 * (len - 1);
return v;
}
uint lo = polymur_load_le_u32(buf);
uint hi = polymur_load_le_u32(buf + len - 4);
return lo | (hi << 8 * (len - 4));
}Реализация арифметики над 128-битными числами в PolymurHash ограничивается весьма узким набором операций: определением структуры для представления 128-битного типа данных, сложением и умножением двух чисел такого типа:
struct polymur_u128_t
{
ulong lo;
ulong hi;
}
static polymur_u128_t polymur_add128(polymur_u128_t a, polymur_u128_t b)
{
a.lo += b.lo;
a.hi += b.hi + (a.lo < b.lo);
return a;
}
static polymur_u128_t polymur_mul128(ulong a, ulong b)
{
polymur_u128_t ret;
ulong lo_lo = (a & 0xffffffffUL) * (b & 0xffffffffUL);
ulong hi_lo = (a >> 32) * (b & 0xffffffffUL);
ulong lo_hi = (a & 0xffffffffUL) * (b >> 32);
ulong hi_hi = (a >> 32) * (b >> 32);
ulong cross = (lo_lo >> 32) + (hi_lo & 0xffffffffUL) + lo_hi;
ret.hi = (hi_lo >> 32) + (cross >> 32) + hi_hi;
ret.lo = (cross << 32) | (lo_lo & 0xffffffffUL);
return ret;
}Функция смешивания в PolymurHash очень компактная и выглядит следующим образом:
static ulong polymur_mix(ulong x)
{
// Mixing function from https://jonkagstrom.com/mx3/mx3_rev2.html.
x ^= x >> 32;
x *= 0xe9846af9b1a615dUL;
x ^= x >> 32;
x *= 0xe9846af9b1a615dUL;
x ^= x >> 28;
return x;
}Функция инициализации использует ряд констант и представляет собой операции с полиномами:
enum POLYMUR_P611 = ((1UL << 61) - 1);
static ulong polymur_red611(polymur_u128_t x)
{
return (x.lo & POLYMUR_P611) + ((x.lo >> 61) | (x.hi << 3));
}
static ulong polymur_extrared611(ulong x)
{
return (x & POLYMUR_P611) + (x >> 61);
}
enum POLYMUR_ARBITRARY1 = 0x6a09e667f3bcc908UL; // Completely arbitrary, these
enum POLYMUR_ARBITRARY2 = 0xbb67ae8584caa73bUL; // are taken from SHA-2, and
enum POLYMUR_ARBITRARY3 = 0x3c6ef372fe94f82bUL; // are the fractional bits of
enum POLYMUR_ARBITRARY4 = 0xa54ff53a5f1d36f1UL; // sqrt(p), p = 2, 3, 5, 7.
struct PolymurHashParams
{
ulong k, k2, k7, s;
}
static void polymur_init_params(PolymurHashParams* p, ulong k_seed, ulong s_seed)
{
p.s = s_seed ^ POLYMUR_ARBITRARY1; // People love to pass zero.
// POLYMUR_POW37[i] = 37^(2^i) mod (2^61 - 1)
// Could be replaced by a 512 byte LUT, costs ~400 byte overhead but 2x
// faster seeding. However, seeding is rather rare, so I chose not to.
ulong[64] POLYMUR_POW37;
POLYMUR_POW37[0] = 37;
POLYMUR_POW37[32] = 559096694736811184UL;
for (int i = 0; i < 31; ++i)
{
POLYMUR_POW37[i + 1] = polymur_extrared611(polymur_red611(polymur_mul128(POLYMUR_POW37[i], POLYMUR_POW37[i])));
POLYMUR_POW37[i + 33] = polymur_extrared611(polymur_red611(polymur_mul128(POLYMUR_POW37[i + 32], POLYMUR_POW37[i + 32])));
}
while (1)
{
// Choose a random exponent coprime to 2^61 - 2. ~35.3% success rate.
k_seed += POLYMUR_ARBITRARY2;
ulong e = (k_seed >> 3) | 1; // e < 2^61, odd.
if (e % 3 == 0)
continue;
if (!(e % 5 && e % 7))
continue;
if (!(e % 11 && e % 13 && e % 31))
continue;
if (!(e % 41 && e % 61 && e % 151 && e % 331 && e % 1321))
continue;
// Compute k = 37^e mod 2^61 - 1. Since e is coprime with the order of
// the multiplicative group mod 2^61 - 1 and 37 is a generator, this
// results in another generator of the group.
ulong ka = 1, kb = 1;
for (int i = 0; e; i += 2, e >>= 2)
{
if (e & 1)
ka = polymur_extrared611(polymur_red611(polymur_mul128(ka, POLYMUR_POW37[i])));
if (e & 2)
kb = polymur_extrared611(polymur_red611(polymur_mul128(kb, POLYMUR_POW37[i + 1])));
}
ulong k = polymur_extrared611(polymur_red611(polymur_mul128(ka, kb)));
// ~46.875% success rate. Bound on k^7 needed for efficient reduction.
p.k = polymur_extrared611(k);
p.k2 = polymur_extrared611(polymur_red611(polymur_mul128(p.k, p.k)));
ulong k3 = polymur_red611(polymur_mul128(p.k, p.k2));
ulong k4 = polymur_red611(polymur_mul128(p.k2, p.k2));
p.k7 = polymur_extrared611(polymur_red611(polymur_mul128(k3, k4)));
if (p.k7 < (1UL << 60) - (1UL << 56))
break;
// Our key space is log2(totient(2^61 - 2) * (2^60-2^56)/2^61) ~= 57.4 bits.
}
}С этой функции начинается старт алгоритма хэширования и эта функция заполняет структуру PolymurHashParams рекомендованными значениями, а также использует предоставленные пользователем два 64-битных секрета. Как уже упоминалось ранее, есть сокращенный вариант функции инициализации, которая использует только один секрет:
static void polymur_init_params_from_seed(PolymurHashParams* p, ulong seed)
{
polymur_init_params(p, polymur_mix(seed + POLYMUR_ARBITRARY3), polymur_mix(seed + POLYMUR_ARBITRARY4));
}Функция хэширования PolymurHash выглядит следующим образом:
static ulong polymur_hash_poly611(const(ubyte)* buf, size_t len, const PolymurHashParams* p, ulong tweak)
{
ulong[7] m;
ulong poly_acc = tweak;
if (len <= 7)
{
m[0] = polymur_load_le_u64_0_8(buf, len);
return poly_acc + polymur_red611(polymur_mul128(p.k + m[0], p.k2 + len));
}
ulong k3 = polymur_red611(polymur_mul128(p.k, p.k2));
ulong k4 = polymur_red611(polymur_mul128(p.k2, p.k2));
if (len >= 50)
{
const ulong k5 = polymur_extrared611(polymur_red611(polymur_mul128(p.k, k4)));
const ulong k6 = polymur_extrared611(polymur_red611(polymur_mul128(p.k2, k4)));
k3 = polymur_extrared611(k3);
k4 = polymur_extrared611(k4);
ulong h = 0;
do
{
for (int i = 0; i < 7; ++i)
m[i] = polymur_load_le_u64(buf + 7 * i) & 0x00ffffffffffffffUL;
polymur_u128_t t0 = polymur_mul128(p.k + m[0], k6 + m[1]);
polymur_u128_t t1 = polymur_mul128(p.k2 + m[2], k5 + m[3]);
polymur_u128_t t2 = polymur_mul128(k3 + m[4], k4 + m[5]);
polymur_u128_t t3 = polymur_mul128(h + m[6], p.k7);
polymur_u128_t s = polymur_add128(polymur_add128(t0, t1), polymur_add128(t2, t3));
h = polymur_red611(s);
len -= 49;
buf += 49;
}
while (len >= 50);
const ulong k14 = polymur_red611(polymur_mul128(p.k7, p.k7));
ulong hk14 = polymur_red611(polymur_mul128(polymur_extrared611(h), k14));
poly_acc += polymur_extrared611(hk14);
}
if (len >= 8)
{
m[0] = polymur_load_le_u64(buf) & 0x00ffffffffffffffUL;
m[1] = polymur_load_le_u64(buf + (len - 7) / 2) & 0x00ffffffffffffffUL;
m[2] = polymur_load_le_u64(buf + len - 8) >> 8;
polymur_u128_t t0 = polymur_mul128(p.k2 + m[0], p.k7 + m[1]);
polymur_u128_t t1 = polymur_mul128(p.k + m[2], k3 + len);
if (len <= 21)
return poly_acc + polymur_red611(polymur_add128(t0, t1));
m[3] = polymur_load_le_u64(buf + 7) & 0x00ffffffffffffffUL;
m[4] = polymur_load_le_u64(buf + 14) & 0x00ffffffffffffffUL;
m[5] = polymur_load_le_u64(buf + len - 21) & 0x00ffffffffffffffUL;
m[6] = polymur_load_le_u64(buf + len - 14) & 0x00ffffffffffffffUL;
ulong t0r = polymur_red611(t0);
polymur_u128_t t2 = polymur_mul128(p.k2 + m[3], p.k7 + m[4]);
polymur_u128_t t3 = polymur_mul128(t0r + m[5], k4 + m[6]);
polymur_u128_t s = polymur_add128(polymur_add128(t1, t2), t3);
return poly_acc + polymur_red611(s);
}
m[0] = polymur_load_le_u64_0_8(buf, len);
return poly_acc + polymur_red611(polymur_mul128(p.k + m[0], p.k2 + len));
}
static ulong polymur_hash(const ubyte* buf, size_t len, const PolymurHashParams* p, ulong tweak)
{
ulong h = polymur_hash_poly611(buf, len, p, tweak);
return polymur_mix(h) + p.s;
}Детали работы этого механизма внутри хэш-функции представлены в репозитории проекта и в их работу мы далее погружаться не будем, а только лишь опишем наш тест, который можно выполнить собрав следующий код:
import std.stdio;
import core.stdc.string : memcpy;
struct PolymurHashParams
{
ulong k, k2, k7, s;
}
static bool polymur_is_little_endian()
{
uint v = 1;
return cast(bool)*(cast(ubyte*)&v);
}
static uint polymur_bswap32(uint v)
{
return ((v >> 24) & 0x000000ff) | ((v >> 8) & 0x0000ff00UL) | ((v << 8) & 0x00ff0000) | ((v << 24) & 0xff000000);
}
static ulong polymur_bswap64(ulong v)
{
return (cast(ulong) polymur_bswap32(cast(uint) v)) << 32 | polymur_bswap32(cast(uint)(v >> 32));
}
static uint polymur_load_le_u32(const ubyte* p)
{
uint v = 0;
memcpy(&v, p, 4);
return polymur_is_little_endian() ? v : polymur_bswap32(v);
}
static ulong polymur_load_le_u64(const ubyte* p)
{
ulong v = 0;
memcpy(&v, p, 8);
return polymur_is_little_endian() ? v : polymur_bswap64(v);
}
// Loads 0 to 8 bytes from buf with length len as a 64-bit little-endian integer.
static ulong polymur_load_le_u64_0_8(const ubyte* buf, size_t len)
{
if (len < 4)
{
if (len == 0)
return 0;
ulong v = buf[0];
v |= buf[len / 2] << 8 * (len / 2);
v |= buf[len - 1] << 8 * (len - 1);
return v;
}
uint lo = polymur_load_le_u32(buf);
uint hi = polymur_load_le_u32(buf + len - 4);
return lo | (hi << 8 * (len - 4));
}
enum POLYMUR_P611 = ((1UL << 61) - 1);
struct polymur_u128_t
{
ulong lo;
ulong hi;
}
static polymur_u128_t polymur_add128(polymur_u128_t a, polymur_u128_t b)
{
a.lo += b.lo;
a.hi += b.hi + (a.lo < b.lo);
return a;
}
static polymur_u128_t polymur_mul128(ulong a, ulong b)
{
polymur_u128_t ret;
ulong lo_lo = (a & 0xffffffffUL) * (b & 0xffffffffUL);
ulong hi_lo = (a >> 32) * (b & 0xffffffffUL);
ulong lo_hi = (a & 0xffffffffUL) * (b >> 32);
ulong hi_hi = (a >> 32) * (b >> 32);
ulong cross = (lo_lo >> 32) + (hi_lo & 0xffffffffUL) + lo_hi;
ret.hi = (hi_lo >> 32) + (cross >> 32) + hi_hi;
ret.lo = (cross << 32) | (lo_lo & 0xffffffffUL);
return ret;
}
static ulong polymur_red611(polymur_u128_t x)
{
return (x.lo & POLYMUR_P611) + ((x.lo >> 61) | (x.hi << 3));
}
static ulong polymur_extrared611(ulong x)
{
return (x & POLYMUR_P611) + (x >> 61);
}
enum POLYMUR_ARBITRARY1 = 0x6a09e667f3bcc908UL; // Completely arbitrary, these
enum POLYMUR_ARBITRARY2 = 0xbb67ae8584caa73bUL; // are taken from SHA-2, and
enum POLYMUR_ARBITRARY3 = 0x3c6ef372fe94f82bUL; // are the fractional bits of
enum POLYMUR_ARBITRARY4 = 0xa54ff53a5f1d36f1UL; // sqrt(p), p = 2, 3, 5, 7.
static ulong polymur_mix(ulong x)
{
// Mixing function from https://jonkagstrom.com/mx3/mx3_rev2.html.
x ^= x >> 32;
x *= 0xe9846af9b1a615dUL;
x ^= x >> 32;
x *= 0xe9846af9b1a615dUL;
x ^= x >> 28;
return x;
}
static void polymur_init_params(PolymurHashParams* p, ulong k_seed, ulong s_seed)
{
p.s = s_seed ^ POLYMUR_ARBITRARY1; // People love to pass zero.
// POLYMUR_POW37[i] = 37^(2^i) mod (2^61 - 1)
// Could be replaced by a 512 byte LUT, costs ~400 byte overhead but 2x
// faster seeding. However, seeding is rather rare, so I chose not to.
ulong[64] POLYMUR_POW37;
POLYMUR_POW37[0] = 37;
POLYMUR_POW37[32] = 559096694736811184UL;
for (int i = 0; i < 31; ++i)
{
POLYMUR_POW37[i + 1] = polymur_extrared611(polymur_red611(polymur_mul128(POLYMUR_POW37[i], POLYMUR_POW37[i])));
POLYMUR_POW37[i + 33] = polymur_extrared611(polymur_red611(polymur_mul128(POLYMUR_POW37[i + 32], POLYMUR_POW37[i + 32])));
}
while (1)
{
// Choose a random exponent coprime to 2^61 - 2. ~35.3% success rate.
k_seed += POLYMUR_ARBITRARY2;
ulong e = (k_seed >> 3) | 1; // e < 2^61, odd.
if (e % 3 == 0)
continue;
if (!(e % 5 && e % 7))
continue;
if (!(e % 11 && e % 13 && e % 31))
continue;
if (!(e % 41 && e % 61 && e % 151 && e % 331 && e % 1321))
continue;
// Compute k = 37^e mod 2^61 - 1. Since e is coprime with the order of
// the multiplicative group mod 2^61 - 1 and 37 is a generator, this
// results in another generator of the group.
ulong ka = 1, kb = 1;
for (int i = 0; e; i += 2, e >>= 2)
{
if (e & 1)
ka = polymur_extrared611(polymur_red611(polymur_mul128(ka, POLYMUR_POW37[i])));
if (e & 2)
kb = polymur_extrared611(polymur_red611(polymur_mul128(kb, POLYMUR_POW37[i + 1])));
}
ulong k = polymur_extrared611(polymur_red611(polymur_mul128(ka, kb)));
// ~46.875% success rate. Bound on k^7 needed for efficient reduction.
p.k = polymur_extrared611(k);
p.k2 = polymur_extrared611(polymur_red611(polymur_mul128(p.k, p.k)));
ulong k3 = polymur_red611(polymur_mul128(p.k, p.k2));
ulong k4 = polymur_red611(polymur_mul128(p.k2, p.k2));
p.k7 = polymur_extrared611(polymur_red611(polymur_mul128(k3, k4)));
if (p.k7 < (1UL << 60) - (1UL << 56))
break;
// Our key space is log2(totient(2^61 - 2) * (2^60-2^56)/2^61) ~= 57.4 bits.
}
}
static void polymur_init_params_from_seed(PolymurHashParams* p, ulong seed)
{
polymur_init_params(p, polymur_mix(seed + POLYMUR_ARBITRARY3), polymur_mix(seed + POLYMUR_ARBITRARY4));
}
static ulong polymur_hash_poly611(const(ubyte)* buf, size_t len, const PolymurHashParams* p, ulong tweak)
{
ulong[7] m;
ulong poly_acc = tweak;
if (len <= 7)
{
m[0] = polymur_load_le_u64_0_8(buf, len);
return poly_acc + polymur_red611(polymur_mul128(p.k + m[0], p.k2 + len));
}
ulong k3 = polymur_red611(polymur_mul128(p.k, p.k2));
ulong k4 = polymur_red611(polymur_mul128(p.k2, p.k2));
if (len >= 50)
{
const ulong k5 = polymur_extrared611(polymur_red611(polymur_mul128(p.k, k4)));
const ulong k6 = polymur_extrared611(polymur_red611(polymur_mul128(p.k2, k4)));
k3 = polymur_extrared611(k3);
k4 = polymur_extrared611(k4);
ulong h = 0;
do
{
for (int i = 0; i < 7; ++i)
m[i] = polymur_load_le_u64(buf + 7 * i) & 0x00ffffffffffffffUL;
polymur_u128_t t0 = polymur_mul128(p.k + m[0], k6 + m[1]);
polymur_u128_t t1 = polymur_mul128(p.k2 + m[2], k5 + m[3]);
polymur_u128_t t2 = polymur_mul128(k3 + m[4], k4 + m[5]);
polymur_u128_t t3 = polymur_mul128(h + m[6], p.k7);
polymur_u128_t s = polymur_add128(polymur_add128(t0, t1), polymur_add128(t2, t3));
h = polymur_red611(s);
len -= 49;
buf += 49;
}
while (len >= 50);
const ulong k14 = polymur_red611(polymur_mul128(p.k7, p.k7));
ulong hk14 = polymur_red611(polymur_mul128(polymur_extrared611(h), k14));
poly_acc += polymur_extrared611(hk14);
}
if (len >= 8)
{
m[0] = polymur_load_le_u64(buf) & 0x00ffffffffffffffUL;
m[1] = polymur_load_le_u64(buf + (len - 7) / 2) & 0x00ffffffffffffffUL;
m[2] = polymur_load_le_u64(buf + len - 8) >> 8;
polymur_u128_t t0 = polymur_mul128(p.k2 + m[0], p.k7 + m[1]);
polymur_u128_t t1 = polymur_mul128(p.k + m[2], k3 + len);
if (len <= 21)
return poly_acc + polymur_red611(polymur_add128(t0, t1));
m[3] = polymur_load_le_u64(buf + 7) & 0x00ffffffffffffffUL;
m[4] = polymur_load_le_u64(buf + 14) & 0x00ffffffffffffffUL;
m[5] = polymur_load_le_u64(buf + len - 21) & 0x00ffffffffffffffUL;
m[6] = polymur_load_le_u64(buf + len - 14) & 0x00ffffffffffffffUL;
ulong t0r = polymur_red611(t0);
polymur_u128_t t2 = polymur_mul128(p.k2 + m[3], p.k7 + m[4]);
polymur_u128_t t3 = polymur_mul128(t0r + m[5], k4 + m[6]);
polymur_u128_t s = polymur_add128(polymur_add128(t1, t2), t3);
return poly_acc + polymur_red611(s);
}
m[0] = polymur_load_le_u64_0_8(buf, len);
return poly_acc + polymur_red611(polymur_mul128(p.k + m[0], p.k2 + len));
}
static ulong polymur_hash(const ubyte* buf, size_t len, const PolymurHashParams* p, ulong tweak)
{
ulong h = polymur_hash_poly611(buf, len, p, tweak);
return polymur_mix(h) + p.s;
}
auto polymur_test()
{
// тестовые векторы
static string[] POLYMUR_TEST_STRINGS =
[
"",
"i",
"es",
"vca",
"bdxa",
"bbbmc",
"vn5719",
"lpvif62",
"1fcjgark",
"1jlz2nr6w",
"g4q6ebxvod",
"ehiybujo2n1",
"6u2990ulzi7m",
"c3xcb4ew8v678",
"bhcaqrm221pea1",
"oyl3iqxqr85eeve",
"b41kacwmnim8rup5",
"563ug64z3zdtlj438",
"3spvl57qfg4udw2l3s",
"297r1bqesqdhb3jd50g",
"kbc5btot9x1fqslddmha",
"r0vxw6kk8tc6pk0oxnr6m",
"wkgmmma9icgky3bnj5bjir",
"5eslfmq1w3i7wvd89ls7nvf",
"40ytv0ye8cq49no6ys1pdrot",
"p3mbto6bl36g3cx9sstyiugsd",
"m0ylpn0wh5krbebs0j5trzgveb",
"qsy8gpheo76vb8g0ivaojk1zgk4",
"dwqf8tpad4k3x69sah7pstrg8zxx",
"ls3zrsjf1o3cr5sjy7dzp98198i3y",
"xvhvx3wbzer9b7kr4jqg2ok9e3mv5d",
"yapzlwab361wvh0xf1rydn5ynqx8cz0",
"nj56v1p9dc7qdmcn2wksfg5kic1uegm2",
"hlebeoafjqtqxfwd9ge94z3ofk88c4a5x",
"6li8qyu0n8nwoggm4hqzqdamem5barzjyw",
"wj7sp7dhpfapsd8w2nzn8s7xtnro9g45x7t",
"ahio6so1x30oziw54ux5iojjdfvkwpw2v14d",
"wm6yacnl6k3kj3c6i1jeajuwmquv9yujms0wq",
"kzs6xfhmc4ifmstnekcze4y1l83ddvxust2r0o",
"ckamexupx7cmsuza9nssw6n45e7go4s3osr1903",
"nob5bj9tok346dg62jbfjfrhg5l6itsno2hkhfru",
"vgo0ko42n5jvrvnv3ddpwg8h7gkqoxbllv2fdy0no",
"dgs47djqzq3czo0i0v1u3d3x72vtvi3w2tsf9shx6k",
"8vjrw7jz90kf969txb5qrh0u5332zf5epsp8aes4aqh",
"3ni9vtqiq6vnxipfa2wag8vfwq2nyce1kgq5nj3razx9",
"u29xjkod6rtu5j5tlwkydt9khih6o2do84q6ukwlr00xf",
"yxxubvyxuusw827qctqr6tmm69rij5ex2zk1etps8qh61e",
"p7lh4mvadnp6uw0vt7bnzcbv1wjswuuc6gjmu684yznx8lp",
"8c27lotvnab6ra8pq9aon0w30ydyulesinew3akqrhhmm39e",
"ttipbm97gpk7tiog1doncalwgpb7alk16dapga2ekzjt59pv6",
"mbbtplseab2mgtgh8uwlhbmdrwxae3tc2mtf98bwuhmz4bfjnf",
"shnjeydnj8awrkz3rd69wqqd9srie4eo6gc6ylhz2ouv4t4qbar",
"lckl12agnpr6q5053h9v38lyk71emkvwdzrv0ic3a4a4pn3w3o4x",
"7927wqjo5jiecfk0bbtt6065j5jl7x0vv1mcxxxl0j1oatrom44zp",
"bajk3ff026vx0u7o5d7ry7w7n07sqdy4urv4psr79jp13e0mxsks1r",
"en6j5o90gmgj7ssbz6jv3kzdsbzczu518c3zmezkp02rtvo1s88n9pu",
"58fkwyf44tjnrytgplb5qfbvlwtav3zutxowoor2mklkr2up4nzpefos",
"cep02qfl6swv1j3mwy5kprm4p8drszchufrkyr5ejbtzgu5cti6fqab5c",
"lr5q0p1dljga8h4vruy1doa79hntwbdyolnh1fbe3phfk7f5rgs4815foj",
"hmnjq6h1sslivjzmbxbpqba29f6kvbea6n6c4sanm40nzmrxt8hm61ooq3e",
"ae43xxu1mqrbynmctit7m4wf02o0kf2vvw1l3y51n4cu5v5ba4dia67wf0bo",
"qz9ye2ur849obmm23d5tnfc3xdaeajil0gm2pz8z9psedj50h5hcwbcn8n2lo",
"w3xar1pzaff7fhyw6cshdgechm2pj1ebwrbkdct5xfbmxskr3937dodvky62i8",
"ypy5k197quc9ypqoj9kle2eky307jnnd7tu52hqhn6mo7jj1fvmi42kkgq40iy6",
"k1bp6qwiul8fnd6rfe42ge6gskk0jkr9fjgmuujey3kn8ie88h9qguw2gboo7i80",
"begb64jkzfujx7ch3ain1iixidnbhcbcglcuf7nys8eansnkewtiye9xv7s2ksuev",
"vf5d8vdjtwp5vo1ocb274nkl6h8vg97m4v5htfwv02tj9u68vdnteeim6q0zllxflj",
"dcg9osulcdw9sqaue4cfz6k990vpstoxmvwbxzhzichkhdujy36v556u7oxug51gdup",
"1rtgdtibcaos4ebzrbl1fkjahtbel6fyqipuu8lxfrwnggjr8wgoscfxp46wv9wjk315",
"r27qj342zj4anpkqpr9yqo7udnldwiqqpq667zzjgw33yia3wt2p6t221onq4pvfaywbj",
"2yzxskad06pt9zvjmiobfz12a3q6wqgpj4450rpxj0jvjk3cx39qo6cbpukxqsy6idqd40",
"813zultj26k3gn6gibolpuozgaxu8exfatf4iqqugelcf6k8dnzvsjb9s25g3gyess2uscc",
"i4p0jkxf3ajc02x330y3tg8l521fzootabn53ovru20ph3n17hfygaz1axs61jxipz6jac5z",
"5bk748kkvww7toeyeueukk2qyin2o5ohnvj7l1cqs9zgy92n6ujxg6sxdjw81hfd29nzrb4kh",
"uvhy62avo1wqms1rrtefth84xhnv1a59aez6r4xq0pla74036o3vznihxexwydnfjojmk6ipl6",
"0t0dlfopg27cqv1xp4qfgwdlivvgqz204hkh5ianbb4abgk0yjolcwhhitrcksha5s6otmps0hd",
"vrbhcwrmn5xbq8f518ntvmaeg89n7nh1uxebfsmd7smoog3k2w12zv0px32pf4b78er5f3pgy7b9",
"x5bmnefocbtxm8avt22ekuy5hcdyxh86is5fnns9ycfm7o25x9frwv9kfv2ohyd3txlc8zlg5rjjx",
"ttfrgnfvvj552vjymrqqd1yjlyff7vkffprnvu3co4vuah8y0s56tziih3yowm64ja810gb1sgk0um",
"a66t43i9vrr3cmg5qf52akuk8bxl4rm3i86rm7h5brjou9k2egrzy3h19hh8kqr2queyvrwb673qikj",
"mfuwhbvd88n21obpmwx273mmeqiz98qfmb04z0ute54kc1d9bbdyfbx2sc4em6t4pfektm05qs7bgc9z",
"x8wbm0kjpyua8wpgsejgxc06geitm1c0bxihvcwnxnif63dj7cygzk7led0z49ol6zf2xwcmf99n4osip",
"fvba43myr0ozab882crozdz0zx4lfl2h7xe2phfqte97g58fake2fzi87mpftz9qdmt45gm79xl43k1hji",
"wnr0pz08rm3j65b7pl116l59pxy6prnydf9xod1qdi3hp3lod2vuzy1v7gt2g72sejaomn5u53daxjrr9xk",
"bwo7nfqda6w56voyvg1nr7vkq61zi7gy0aggn6pic3gup7uy18zzsc7y5yz3ptvp5cd53i95dj521k4n6n7t",
"mromebynw459uydhhgcgrate6hnst5srng9knfjc02vtg1vywok3rdbw935pf1qwghnh0nibyb60l9elkmajg",
"59dcjawsd4kjjcceco3hphizua88l0qtrfd000iam3rnb4tmy6kzf5bhkc9ud1hsg3dd53tlsxarcl0n59081h",
"odgdgfkwcpz0zjcwsz9is5h4nhebzht7fqa1b4g8e2snb6bn5hu3ixyd2pk1ey5g3eab0m3aoknfi9ctkpxz07j",
"0ljqm7r10ns2pjo8x69oi0zuqss9y7301yd6rmex8djwrbqmvh2mbwscgj9pmrgul5ao0tvpefpe5a9cac5xbdwb",
"b449ak3ihp8tdrbteffru5vboeh1z63c55at3qz70p13d2fim50q8i06zjyb53i4gqzunx6rsl07jxjd9g77me1ww",
"oqzf6c40snvrjz4v0f4h8p0ozjfy1y4xihxwaz16vbxf3qsa805xodw8z5xq3hb7dag8fnxtlsc62150kk253i3buj",
"2eicp9a5aq2uycq55y7rsixlg3pfk7gyin65fghf03kks18dixbckxmbv5xnhyrir7qm8maz4rk2bi3zs9chidlhehf",
"7k1wyjs6fxss4e0ywqfurgop6f7y7e97f3mr5hnb0hlhqkqbqvi1e1z3qfyxc3te75r67fc4h9li06rl9zadg3v9zmz6",
"k3e403zdtia8i0gpodm00yaujr1w474bh3985o3csbfjp3dll4t98i5lesloo6rqjec2aycb3ttx1t6lg0cl9hrjkgheb",
"2fv8zdl1ljmpjbvaan0nt99tra48yjmc5pv91n1c5l8qp5pv77zwsx75ouay7bmgy2tjc1aazyu5zj7oimesavv9n2h7ky",
"ghxs7uejpzpbxjsdmc2w9fabrg4j4pwwbn0wjxux2luk1k0ciror4gcvww18e610u2wpczuwrcphy2xr1129vweqhhgitge",
"vk7wfi9hhi0j9n2grs8rxgq68kw54dbdviuxnvtwgz77h0qkbzqw7pgm7zgn21cxlxnyzigeyz2rzrj3awloq86tqe60e070",
"d1aot9216s547uk1rg651iscb1bjpgth5j4f6arx1902npcykk8niz3ffpbed47idgzvt4u59fyi5e0e2afpjb5gjk4rysn8j",
"2jef2xl4o9yub0z6jnxu8gm87g9iv9zdtu9yolvxtensjrtgplnmnuhz43nsxztk8s936k6eruckkiwc5hnch4qdzft093986x",
"oo70ed77jci4bgodhnyf37axrx4f8gf8qs94f4l9xi9h0jkdl2ozoi2p7q7qu1945l21dzj6rhvqearzrmblfo3ljjldj0m9fue",
];
// значения для тестовых векторов
static const ulong[] POLYMUR_REFERENCE_VALUES =
[
0x1a6ef9f9d6c576fbUL, 0xd16d059771c65e13UL, 0x5ee4e0c09f562f87UL, 0x535b5311db007b0bUL ,
0xd17124f14bd16b5dUL, 0xe84c87105c5b5cadUL, 0xb16ce684b89df9c0UL, 0x656525cace200667UL ,
0x92b460794885d16dUL, 0xe6cc0fd9725b46b9UL, 0xc875ade1929bc93dUL, 0x68a2686ced37268aUL ,
0x1d1809fd7e7e14efUL, 0x699b8f31fc40c137UL, 0xd10dca2605654d2dUL, 0xd6bc75cb729f18d7UL ,
0xfe0c617e7cb1bffeUL, 0xf5f14c731c1b9a22UL, 0x7a0382228d248631UL, 0x6c3a5f49d8a48bc0UL ,
0x3606ebe637bb4ebcUL, 0xeb4854d75431ad1dUL, 0xfa8ff1a34793ebb0UL, 0x7e46ad8e2338cc38UL ,
0xf8ff088ada3154b4UL, 0x706669bf0925914fUL, 0x70fc5fbcd3485aceUL, 0x96fd279baed2f2abUL ,
0x6403a64c68d7bf68UL, 0x3f8f532e1df472e5UL, 0xbfc49c083515596fUL, 0xd678a4b338fbf03bUL ,
0x127142a2f38b70a1UL, 0x8a1a56fbb85b71f6UL, 0x961d22b14e6f1932UL, 0xa166b0326c942c30UL ,
0x0f3d837dddb86ae2UL, 0x0f8164504b4ea8b1UL, 0xe4f6475d5a739af4UL, 0xbf535ad625c0d51fUL ,
0x47f10a5a13be50adUL, 0x3dc5ce9c148969b3UL, 0x8dc071fb4df8e144UL, 0x9d0a83586cbed3b8UL ,
0xc4379e22f2809b99UL, 0x42010c7dd7657650UL, 0xcc31a6fbcdab8be8UL, 0x7bad06c38400138aUL ,
0x0178b41584eb483dUL, 0x78afc38d52514efcUL, 0x65a57c4e59288dc7UL, 0x86e7cc3e273e4e47UL ,
0xeb99661fb41a6bd2UL, 0xea0979aa6cd70febUL, 0xa64a347c0b8e007bUL, 0x3692969270fe8fa4UL ,
0x17640c6052e26555UL, 0xdf9e0fd276291357UL, 0x64cca6ebf4580720UL, 0xf82b33f6399c3f49UL ,
0xbe3ccb7526561379UL, 0x8c796fce8509c043UL, 0x9849fded8c92ce51UL, 0xa0e744d838dbc4efUL ,
0x8e4602d33a961a65UL, 0xda381d6727886a7eUL, 0xa503a344fc066833UL, 0xbf8ff5bc36d5dc7bUL ,
0x795ae9ed95bca7e9UL, 0x19c80807dc900762UL, 0xea7d27083e6ca641UL, 0xeba7e4a637fe4fb5UL ,
0x34ac9bde50ce9087UL, 0xe290dd0393f2586aUL, 0xbd7074e9843d9dcaUL, 0x66c17140a05887e6UL ,
0x4ad7b3e525e37f94UL, 0xde0d009c18880dd6UL, 0x1516bbb1caca46d3UL, 0xe9c907ec28f89499UL ,
0xd677b655085e1e14UL, 0xac5f949b08f29553UL, 0xd353b06cb49b5503UL, 0x9c25eb30ffa8cc78UL ,
0x6cf18c91658e0285UL, 0x99264d2b2cc86a77UL, 0x8b438cd1bb8fb65dUL , 0xdfd56cf20b217732UL ,
0x71f4e35bf761bacfUL, 0x87d7c01f2b11659cUL, 0x95de608c3ad2653cUL, 0x51b50e6996b8de93UL ,
0xd21e837b2121e8c9UL, 0x73d07c7cb3fa0ba7UL, 0x8113fab03cab6df3UL, 0x57cdddea972cc490UL ,
0xc3df94778f1eec30UL, 0x7509771e4127701eUL, 0x28240c74c56f8f7cUL, 0x194fa4f68aab8e27UL
];
PolymurHashParams params;
polymur_init_params_from_seed(¶ms, 0xfedbca9876543210UL);
foreach (i, e; POLYMUR_TEST_STRINGS) {
import std.string : representation;
ubyte[] w = cast(ubyte[]) e.representation;
ulong x = polymur_hash(w.ptr, w.length, ¶ms, 0xabcdef0123456789UL);
writefln(
"%4d %-100s %016x %016x %s",
i, e, x, POLYMUR_REFERENCE_VALUES[i], x == POLYMUR_REFERENCE_VALUES[i]
);
}
}
void main()
{
import std.string;
ubyte[] test = cast(ubyte[]) "".representation;
PolymurHashParams params;
polymur_init_params_from_seed(¶ms, 0xfedbca9876543210UL);
ulong q = polymur_hash(test.ptr, test.length, ¶ms, 0xabcdef0123456789UL);
writefln("%0.8x", q);
polymur_test();
}
Результат работы представлен ниже:
1a6ef9f9d6c576fb 0 1a6ef9f9d6c576fb 1a6ef9f9d6c576fb true 1 i d16d059771c65e13 d16d059771c65e13 true 2 es 5ee4e0c09f562f87 5ee4e0c09f562f87 true 3 vca 535b5311db007b0b 535b5311db007b0b true 4 bdxa d17124f14bd16b5d d17124f14bd16b5d true 5 bbbmc 02cb646d16325c22 e84c87105c5b5cad false 6 vn5719 94750defd7b34fdb b16ce684b89df9c0 false 7 lpvif62 143fcbfca63c5d3c 656525cace200667 false 8 1fcjgark 92b460794885d16d 92b460794885d16d true 9 1jlz2nr6w e6cc0fd9725b46b9 e6cc0fd9725b46b9 true 10 g4q6ebxvod c875ade1929bc93d c875ade1929bc93d true 11 ehiybujo2n1 68a2686ced37268a 68a2686ced37268a true 12 6u2990ulzi7m 1d1809fd7e7e14ef 1d1809fd7e7e14ef true 13 c3xcb4ew8v678 699b8f31fc40c137 699b8f31fc40c137 true 14 bhcaqrm221pea1 d10dca2605654d2d d10dca2605654d2d true 15 oyl3iqxqr85eeve d6bc75cb729f18d7 d6bc75cb729f18d7 true 16 b41kacwmnim8rup5 fe0c617e7cb1bffe fe0c617e7cb1bffe true 17 563ug64z3zdtlj438 f5f14c731c1b9a22 f5f14c731c1b9a22 true 18 3spvl57qfg4udw2l3s 7a0382228d248631 7a0382228d248631 true 19 297r1bqesqdhb3jd50g 6c3a5f49d8a48bc0 6c3a5f49d8a48bc0 true 20 kbc5btot9x1fqslddmha 3606ebe637bb4ebc 3606ebe637bb4ebc true 21 r0vxw6kk8tc6pk0oxnr6m eb4854d75431ad1d eb4854d75431ad1d true 22 wkgmmma9icgky3bnj5bjir fa8ff1a34793ebb0 fa8ff1a34793ebb0 true 23 5eslfmq1w3i7wvd89ls7nvf 7e46ad8e2338cc38 7e46ad8e2338cc38 true 24 40ytv0ye8cq49no6ys1pdrot f8ff088ada3154b4 f8ff088ada3154b4 true 25 p3mbto6bl36g3cx9sstyiugsd 706669bf0925914f 706669bf0925914f true 26 m0ylpn0wh5krbebs0j5trzgveb 70fc5fbcd3485ace 70fc5fbcd3485ace true 27 qsy8gpheo76vb8g0ivaojk1zgk4 96fd279baed2f2ab 96fd279baed2f2ab true 28 dwqf8tpad4k3x69sah7pstrg8zxx 6403a64c68d7bf68 6403a64c68d7bf68 true 29 ls3zrsjf1o3cr5sjy7dzp98198i3y 3f8f532e1df472e5 3f8f532e1df472e5 true 30 xvhvx3wbzer9b7kr4jqg2ok9e3mv5d bfc49c083515596f bfc49c083515596f true 31 yapzlwab361wvh0xf1rydn5ynqx8cz0 d678a4b338fbf03b d678a4b338fbf03b true 32 nj56v1p9dc7qdmcn2wksfg5kic1uegm2 127142a2f38b70a1 127142a2f38b70a1 true 33 hlebeoafjqtqxfwd9ge94z3ofk88c4a5x 8a1a56fbb85b71f6 8a1a56fbb85b71f6 true 34 6li8qyu0n8nwoggm4hqzqdamem5barzjyw 961d22b14e6f1932 961d22b14e6f1932 true 35 wj7sp7dhpfapsd8w2nzn8s7xtnro9g45x7t a166b0326c942c30 a166b0326c942c30 true 36 ahio6so1x30oziw54ux5iojjdfvkwpw2v14d 0f3d837dddb86ae2 0f3d837dddb86ae2 true 37 wm6yacnl6k3kj3c6i1jeajuwmquv9yujms0wq 0f8164504b4ea8b1 0f8164504b4ea8b1 true 38 kzs6xfhmc4ifmstnekcze4y1l83ddvxust2r0o e4f6475d5a739af4 e4f6475d5a739af4 true 39 ckamexupx7cmsuza9nssw6n45e7go4s3osr1903 bf535ad625c0d51f bf535ad625c0d51f true 40 nob5bj9tok346dg62jbfjfrhg5l6itsno2hkhfru 47f10a5a13be50ad 47f10a5a13be50ad true 41 vgo0ko42n5jvrvnv3ddpwg8h7gkqoxbllv2fdy0no 3dc5ce9c148969b3 3dc5ce9c148969b3 true 42 dgs47djqzq3czo0i0v1u3d3x72vtvi3w2tsf9shx6k 8dc071fb4df8e144 8dc071fb4df8e144 true 43 8vjrw7jz90kf969txb5qrh0u5332zf5epsp8aes4aqh 9d0a83586cbed3b8 9d0a83586cbed3b8 true 44 3ni9vtqiq6vnxipfa2wag8vfwq2nyce1kgq5nj3razx9 c4379e22f2809b99 c4379e22f2809b99 true 45 u29xjkod6rtu5j5tlwkydt9khih6o2do84q6ukwlr00xf 42010c7dd7657650 42010c7dd7657650 true 46 yxxubvyxuusw827qctqr6tmm69rij5ex2zk1etps8qh61e cc31a6fbcdab8be8 cc31a6fbcdab8be8 true 47 p7lh4mvadnp6uw0vt7bnzcbv1wjswuuc6gjmu684yznx8lp 7bad06c38400138a 7bad06c38400138a true 48 8c27lotvnab6ra8pq9aon0w30ydyulesinew3akqrhhmm39e 0178b41584eb483d 0178b41584eb483d true 49 ttipbm97gpk7tiog1doncalwgpb7alk16dapga2ekzjt59pv6 78afc38d52514efc 78afc38d52514efc true 50 mbbtplseab2mgtgh8uwlhbmdrwxae3tc2mtf98bwuhmz4bfjnf 65a57c4e59288dc7 65a57c4e59288dc7 true 51 shnjeydnj8awrkz3rd69wqqd9srie4eo6gc6ylhz2ouv4t4qbar 86e7cc3e273e4e47 86e7cc3e273e4e47 true 52 lckl12agnpr6q5053h9v38lyk71emkvwdzrv0ic3a4a4pn3w3o4x eb99661fb41a6bd2 eb99661fb41a6bd2 true 53 7927wqjo5jiecfk0bbtt6065j5jl7x0vv1mcxxxl0j1oatrom44zp ea0979aa6cd70feb ea0979aa6cd70feb true 54 bajk3ff026vx0u7o5d7ry7w7n07sqdy4urv4psr79jp13e0mxsks1r d18f9c6098441c26 a64a347c0b8e007b false 55 en6j5o90gmgj7ssbz6jv3kzdsbzczu518c3zmezkp02rtvo1s88n9pu 39ec128ea95fa3ba 3692969270fe8fa4 false 56 58fkwyf44tjnrytgplb5qfbvlwtav3zutxowoor2mklkr2up4nzpefos 8538d38cbeeb2396 17640c6052e26555 false 57 cep02qfl6swv1j3mwy5kprm4p8drszchufrkyr5ejbtzgu5cti6fqab5c df9e0fd276291357 df9e0fd276291357 true 58 lr5q0p1dljga8h4vruy1doa79hntwbdyolnh1fbe3phfk7f5rgs4815foj 64cca6ebf4580720 64cca6ebf4580720 true 59 hmnjq6h1sslivjzmbxbpqba29f6kvbea6n6c4sanm40nzmrxt8hm61ooq3e f82b33f6399c3f49 f82b33f6399c3f49 true 60 ae43xxu1mqrbynmctit7m4wf02o0kf2vvw1l3y51n4cu5v5ba4dia67wf0bo be3ccb7526561379 be3ccb7526561379 true 61 qz9ye2ur849obmm23d5tnfc3xdaeajil0gm2pz8z9psedj50h5hcwbcn8n2lo 8c796fce8509c043 8c796fce8509c043 true 62 w3xar1pzaff7fhyw6cshdgechm2pj1ebwrbkdct5xfbmxskr3937dodvky62i8 9849fded8c92ce51 9849fded8c92ce51 true 63 ypy5k197quc9ypqoj9kle2eky307jnnd7tu52hqhn6mo7jj1fvmi42kkgq40iy6 a0e744d838dbc4ef a0e744d838dbc4ef true 64 k1bp6qwiul8fnd6rfe42ge6gskk0jkr9fjgmuujey3kn8ie88h9qguw2gboo7i80 8e4602d33a961a65 8e4602d33a961a65 true 65 begb64jkzfujx7ch3ain1iixidnbhcbcglcuf7nys8eansnkewtiye9xv7s2ksuev da381d6727886a7e da381d6727886a7e true 66 vf5d8vdjtwp5vo1ocb274nkl6h8vg97m4v5htfwv02tj9u68vdnteeim6q0zllxflj a503a344fc066833 a503a344fc066833 true 67 dcg9osulcdw9sqaue4cfz6k990vpstoxmvwbxzhzichkhdujy36v556u7oxug51gdup bf8ff5bc36d5dc7b bf8ff5bc36d5dc7b true 68 1rtgdtibcaos4ebzrbl1fkjahtbel6fyqipuu8lxfrwnggjr8wgoscfxp46wv9wjk315 795ae9ed95bca7e9 795ae9ed95bca7e9 true 69 r27qj342zj4anpkqpr9yqo7udnldwiqqpq667zzjgw33yia3wt2p6t221onq4pvfaywbj 19c80807dc900762 19c80807dc900762 true 70 2yzxskad06pt9zvjmiobfz12a3q6wqgpj4450rpxj0jvjk3cx39qo6cbpukxqsy6idqd40 ea7d27083e6ca641 ea7d27083e6ca641 true 71 813zultj26k3gn6gibolpuozgaxu8exfatf4iqqugelcf6k8dnzvsjb9s25g3gyess2uscc eba7e4a637fe4fb5 eba7e4a637fe4fb5 true 72 i4p0jkxf3ajc02x330y3tg8l521fzootabn53ovru20ph3n17hfygaz1axs61jxipz6jac5z 34ac9bde50ce9087 34ac9bde50ce9087 true 73 5bk748kkvww7toeyeueukk2qyin2o5ohnvj7l1cqs9zgy92n6ujxg6sxdjw81hfd29nzrb4kh e290dd0393f2586a e290dd0393f2586a true 74 uvhy62avo1wqms1rrtefth84xhnv1a59aez6r4xq0pla74036o3vznihxexwydnfjojmk6ipl6 bd7074e9843d9dca bd7074e9843d9dca true 75 0t0dlfopg27cqv1xp4qfgwdlivvgqz204hkh5ianbb4abgk0yjolcwhhitrcksha5s6otmps0hd 66c17140a05887e6 66c17140a05887e6 true 76 vrbhcwrmn5xbq8f518ntvmaeg89n7nh1uxebfsmd7smoog3k2w12zv0px32pf4b78er5f3pgy7b9 4ad7b3e525e37f94 4ad7b3e525e37f94 true 77 x5bmnefocbtxm8avt22ekuy5hcdyxh86is5fnns9ycfm7o25x9frwv9kfv2ohyd3txlc8zlg5rjjx de0d009c18880dd6 de0d009c18880dd6 true 78 ttfrgnfvvj552vjymrqqd1yjlyff7vkffprnvu3co4vuah8y0s56tziih3yowm64ja810gb1sgk0um 1516bbb1caca46d3 1516bbb1caca46d3 true 79 a66t43i9vrr3cmg5qf52akuk8bxl4rm3i86rm7h5brjou9k2egrzy3h19hh8kqr2queyvrwb673qikj e9c907ec28f89499 e9c907ec28f89499 true 80 mfuwhbvd88n21obpmwx273mmeqiz98qfmb04z0ute54kc1d9bbdyfbx2sc4em6t4pfektm05qs7bgc9z d677b655085e1e14 d677b655085e1e14 true 81 x8wbm0kjpyua8wpgsejgxc06geitm1c0bxihvcwnxnif63dj7cygzk7led0z49ol6zf2xwcmf99n4osip ac5f949b08f29553 ac5f949b08f29553 true 82 fvba43myr0ozab882crozdz0zx4lfl2h7xe2phfqte97g58fake2fzi87mpftz9qdmt45gm79xl43k1hji d353b06cb49b5503 d353b06cb49b5503 true 83 wnr0pz08rm3j65b7pl116l59pxy6prnydf9xod1qdi3hp3lod2vuzy1v7gt2g72sejaomn5u53daxjrr9xk 9c25eb30ffa8cc78 9c25eb30ffa8cc78 true 84 bwo7nfqda6w56voyvg1nr7vkq61zi7gy0aggn6pic3gup7uy18zzsc7y5yz3ptvp5cd53i95dj521k4n6n7t 6cf18c91658e0285 6cf18c91658e0285 true 85 mromebynw459uydhhgcgrate6hnst5srng9knfjc02vtg1vywok3rdbw935pf1qwghnh0nibyb60l9elkmajg 99264d2b2cc86a77 99264d2b2cc86a77 true 86 59dcjawsd4kjjcceco3hphizua88l0qtrfd000iam3rnb4tmy6kzf5bhkc9ud1hsg3dd53tlsxarcl0n59081h 8b438cd1bb8fb65d 8b438cd1bb8fb65d true 87 odgdgfkwcpz0zjcwsz9is5h4nhebzht7fqa1b4g8e2snb6bn5hu3ixyd2pk1ey5g3eab0m3aoknfi9ctkpxz07j dfd56cf20b217732 dfd56cf20b217732 true 88 0ljqm7r10ns2pjo8x69oi0zuqss9y7301yd6rmex8djwrbqmvh2mbwscgj9pmrgul5ao0tvpefpe5a9cac5xbdwb 71f4e35bf761bacf 71f4e35bf761bacf true 89 b449ak3ihp8tdrbteffru5vboeh1z63c55at3qz70p13d2fim50q8i06zjyb53i4gqzunx6rsl07jxjd9g77me1ww 87d7c01f2b11659c 87d7c01f2b11659c true 90 oqzf6c40snvrjz4v0f4h8p0ozjfy1y4xihxwaz16vbxf3qsa805xodw8z5xq3hb7dag8fnxtlsc62150kk253i3buj 95de608c3ad2653c 95de608c3ad2653c true 91 2eicp9a5aq2uycq55y7rsixlg3pfk7gyin65fghf03kks18dixbckxmbv5xnhyrir7qm8maz4rk2bi3zs9chidlhehf 51b50e6996b8de93 51b50e6996b8de93 true 92 7k1wyjs6fxss4e0ywqfurgop6f7y7e97f3mr5hnb0hlhqkqbqvi1e1z3qfyxc3te75r67fc4h9li06rl9zadg3v9zmz6 d21e837b2121e8c9 d21e837b2121e8c9 true 93 k3e403zdtia8i0gpodm00yaujr1w474bh3985o3csbfjp3dll4t98i5lesloo6rqjec2aycb3ttx1t6lg0cl9hrjkgheb 73d07c7cb3fa0ba7 73d07c7cb3fa0ba7 true 94 2fv8zdl1ljmpjbvaan0nt99tra48yjmc5pv91n1c5l8qp5pv77zwsx75ouay7bmgy2tjc1aazyu5zj7oimesavv9n2h7ky 8113fab03cab6df3 8113fab03cab6df3 true 95 ghxs7uejpzpbxjsdmc2w9fabrg4j4pwwbn0wjxux2luk1k0ciror4gcvww18e610u2wpczuwrcphy2xr1129vweqhhgitge 57cdddea972cc490 57cdddea972cc490 true 96 vk7wfi9hhi0j9n2grs8rxgq68kw54dbdviuxnvtwgz77h0qkbzqw7pgm7zgn21cxlxnyzigeyz2rzrj3awloq86tqe60e070 c3df94778f1eec30 c3df94778f1eec30 true 97 d1aot9216s547uk1rg651iscb1bjpgth5j4f6arx1902npcykk8niz3ffpbed47idgzvt4u59fyi5e0e2afpjb5gjk4rysn8j 7509771e4127701e 7509771e4127701e true 98 2jef2xl4o9yub0z6jnxu8gm87g9iv9zdtu9yolvxtensjrtgplnmnuhz43nsxztk8s936k6eruckkiwc5hnch4qdzft093986x 28240c74c56f8f7c 28240c74c56f8f7c true 99 oo70ed77jci4bgodhnyf37axrx4f8gf8qs94f4l9xi9h0jkdl2ozoi2p7q7qu1945l21dzj6rhvqearzrmblfo3ljjldj0m9fue 194fa4f68aab8e27 194fa4f68aab8e27 true
Тест проходит так: мы берем те строковые значения, которые представлены авторами алгоритма, и пробуем получить для них хэш PolymurHash. После получения хэша мы выводим четыре колонки: номер значения, строковое значение, его вычисленный хэш , эталонное значение хэша, а также колонку true/false. показывающую совпал ли хэш с эталонным.
Реализацию теста мы написали сами (взяв строки и эталонные значения из репозитория PolymurHash) и она показывает как можно применить нашу реализацию хэш-функции – в функцию нужно передать указатель на байтовый буфер (используя свойство .ptr для массива в D), длину массива байтов, инициализированные параметры PolymurHashParams и значение донастройки.
Стоит заметить, что тест почти успешен – так как мы получили шесть значений, которые помечены словом false. Судя по всему, расхождение связано с тем, что в условиях оригинального алгоритма, был использован ряд специфических макросов, срабатывающих на основе вероятного предсказания срабатывания условий (это почти все условия больше/меньше в функции хэширования), однако, это лишь наша догадка. И догадка остается догадкой, так как оригинальную реализацию алгоритма на предмет прохождения собственных тестов нам запустить не удалось: оригинальный код просто не запускается и падает на части системных вызовов…
Но…Несмотря на это, алгоритм полностью рабочий и стоящий, несмотря на то, что эталонная реализация на C подводит и хэш является 64-битным. Мы считаем алгоритм весьма перспективным, и крайне рекомендуем к изучению, и если он вас заинтересовал рекомендуем обратится к первоисточнику.