Rivoreo Source Code Repositories
src.rivoreo.one / net / facil.io / dc8264f02bd6c6be9081bd86f20d803a3fb2c26a / . / tests / collisions.c
blob: 0f2ca0cdde171e91c01a858783e0dbba4a17a6d9 [file] [log] [blame] [raw]
/*
Copyright: Boaz Segev, 2018-2019
License: MIT
Feel free to copy, use and enjoy according to the license provided.
*/
#define FIO_INCLUDE_STR
#include <fio.h>
#include <fio_cli.h>
#ifndef TEST_XXHASH
#define TEST_XXHASH 1
#endif
/* *****************************************************************************
State machine and types
***************************************************************************** */
static uint8_t print_flag = 1;
static inline int fio_str_eq_print(fio_str_s *a, fio_str_s *b) {
/* always return 1, to avoid internal set collision mitigation. */
if (print_flag)
fprintf(stderr, "* Collision Detected: %s vs. %s\n", fio_str_data(a),
fio_str_data(b));
return 1;
}
// static inline void destroy_collision_object(fio_str_s *a) {
// fprintf(stderr, "* Collision Detected: %s\n", fio_str_data(a));
// fio_str_free2(a);
// }
#define FIO_SET_NAME collisions
#define FIO_SET_OBJ_TYPE fio_str_s *
#define FIO_SET_OBJ_COPY(dest, src) ((dest) = fio_str_new_copy2((src)))
#define FIO_SET_OBJ_COMPARE(a, b) fio_str_eq_print((a), (b))
#define FIO_SET_OBJ_DESTROY(a) fio_str_free2((a))
#include <fio.h>
typedef uintptr_t (*hashing_func_fn)(char *, size_t);
#define FIO_SET_NAME hash_name
#define FIO_SET_OBJ_TYPE hashing_func_fn
#include <fio.h>
#define FIO_ARY_NAME words
#define FIO_ARY_TYPE fio_str_s
#define FIO_ARY_COMPARE(a, b) fio_str_iseq(&(a), &(b))
#define FIO_ARY_COPY(dest, src) \
do { \
fio_str_clear(&(dest)), fio_str_concat(&(dest), &(src)); \
} while (0)
#define FIO_ARY_DESTROY(a) fio_str_free((&a))
#include <fio.h>
static hash_name_s hash_names = FIO_SET_INIT;
static words_s words = FIO_SET_INIT;
/* *****************************************************************************
Main
***************************************************************************** */
static void test_hash_function(hashing_func_fn h);
static void initialize_cli(int argc, char const *argv[]);
static void load_words(void);
static void initialize_hash_names(void);
static void print_hash_names(void);
static char *hash_name(hashing_func_fn fn);
static void cleanup(void);
int main(int argc, char const *argv[]) {
// FIO_LOG_LEVEL = FIO_LOG_LEVEL_DEBUG;
initialize_cli(argc, argv);
load_words();
initialize_hash_names();
if (fio_cli_get("-t")) {
fio_str_s tmp = FIO_STR_INIT_STATIC(fio_cli_get("-t"));
hashing_func_fn h = hash_name_find(&hash_names, fio_str_hash(&tmp), NULL);
if (h) {
test_hash_function(h);
} else {
FIO_LOG_ERROR("Test function %s unknown.", tmp.data);
fprintf(stderr, "Try any of the following:\n");
print_hash_names();
}
} else {
FIO_SET_FOR_LOOP(&hash_names, pos) { test_hash_function(pos->obj); }
}
cleanup();
return 0;
}
/* *****************************************************************************
CLI
***************************************************************************** */
static void initialize_cli(int argc, char const *argv[]) {
fio_cli_start(
argc, argv, 0, 0,
"This is a Hash algorythm collision test program. It accepts the "
"following arguments:",
FIO_CLI_STRING(
"-test -t test only the specified algorithm. Options include:"),
FIO_CLI_PRINT("\t\tsiphash13"), FIO_CLI_PRINT("\t\tsiphash24"),
FIO_CLI_PRINT("\t\tsha1"),
FIO_CLI_PRINT("\t\trisky (fio_str_hash_risky)"),
FIO_CLI_PRINT("\t\trisky2 (fio_str_hash_risky alternative)"),
// FIO_CLI_PRINT("\t\txor (xor all bytes and length)"),
FIO_CLI_STRING(
"-dictionary -d a text file containing words separated by an "
"EOL marker."),
FIO_CLI_BOOL("-v make output more verbouse (debug mode)"));
if (fio_cli_get_bool("-v"))
FIO_LOG_LEVEL = FIO_LOG_LEVEL_DEBUG;
FIO_LOG_DEBUG("initialized CLI.");
}
/* *****************************************************************************
Dictionary management
***************************************************************************** */
static void add_bad_words(void);
static void load_words(void) {
add_bad_words();
fio_str_s filename = FIO_STR_INIT;
fio_str_s data = FIO_STR_INIT;
if (fio_cli_get("-d")) {
fio_str_write(&filename, fio_cli_get("-d"), strlen(fio_cli_get("-d")));
} else {
fio_str_info_s tmp = fio_str_write(&filename, __FILE__, strlen(__FILE__));
while (tmp.len && tmp.data[tmp.len - 1] != '/') {
--tmp.len;
}
fio_str_resize(&filename, tmp.len);
fio_str_write(&filename, "words.txt", 9);
}
fio_str_readfile(&data, fio_str_data(&filename), 0, 0);
fio_str_info_s d = fio_str_info(&data);
if (d.len == 0) {
FIO_LOG_FATAL("Couldn't find / read dictionary file (or no words?)");
FIO_LOG_FATAL("\tmissing or empty: %s", fio_str_data(&filename));
cleanup();
fio_str_free(&filename);
exit(-1);
}
while (d.len) {
char *eol = memchr(d.data, '\n', d.len);
if (!eol) {
/* push what's left */
words_push(&words, FIO_STR_INIT_STATIC2(d.data, d.len));
break;
}
if (eol == d.data || (eol == d.data + 1 && eol[-1] == '\r')) {
/* empty line */
++d.data;
--d.len;
continue;
}
words_push(&words, FIO_STR_INIT_STATIC2(
d.data, (eol - (d.data + (eol[-1] == '\r')))));
d.len -= (eol + 1) - d.data;
d.data = eol + 1;
}
fio_free(&filename);
fio_free(&data);
FIO_LOG_INFO("Loaded %zu words.", words_count(&words));
}
/* *****************************************************************************
Cleanup
***************************************************************************** */
static void cleanup(void) {
print_flag = 0;
hash_name_free(&hash_names);
words_free(&words);
}
/* *****************************************************************************
Hash functions
***************************************************************************** */
static uintptr_t siphash13(char *data, size_t len) {
return fio_siphash13(data, len, 0, 0);
}
static uintptr_t siphash24(char *data, size_t len) {
return fio_siphash24(data, len, 0, 0);
}
static uintptr_t sha1(char *data, size_t len) {
fio_sha1_s s = fio_sha1_init();
fio_sha1_write(&s, data, len);
return ((uintptr_t *)fio_sha1_result(&s))[0];
}
static uintptr_t counter(char *data, size_t len) {
static uintptr_t counter = 0;
const size_t len_256 = len & (((size_t)-1) << 5);
for (size_t i = 0; i < len_256; i += 8) {
/* vectorized 32 bytes / 256 bit access */
uint64_t t0 = fio_str2u64(data);
uint64_t t1 = fio_str2u64(data + 8);
uint64_t t2 = fio_str2u64(data + 16);
uint64_t t3 = fio_str2u64(data + 24);
__asm__ volatile("" ::: "memory");
(void)t0;
(void)t1;
(void)t2;
(void)t3;
data += 32;
}
uint64_t tmp;
/* 64 bit words */
switch (len & 24) {
case 24:
tmp = fio_str2u64(data + 16);
__asm__ volatile("" ::: "memory");
case 16: /* overflow */
tmp = fio_str2u64(data + 8);
__asm__ volatile("" ::: "memory");
case 8: /* overflow */
tmp = fio_str2u64(data);
__asm__ volatile("" ::: "memory");
data += len & 24;
}
tmp = 0;
/* leftover bytes */
switch ((len & 7)) {
case 7: /* overflow */
tmp |= ((uint64_t)data[6]) << 8;
case 6: /* overflow */
tmp |= ((uint64_t)data[5]) << 16;
case 5: /* overflow */
tmp |= ((uint64_t)data[4]) << 24;
case 4: /* overflow */
tmp |= ((uint64_t)data[3]) << 32;
case 3: /* overflow */
tmp |= ((uint64_t)data[2]) << 40;
case 2: /* overflow */
tmp |= ((uint64_t)data[1]) << 48;
case 1: /* overflow */
tmp |= ((uint64_t)data[0]) << 56;
}
__asm__ volatile("" ::: "memory");
return ++counter;
}
#if TEST_XXHASH
#include "xxhash.h"
static uintptr_t xxhash_test(char *data, size_t len) {
return XXH64(data, len, 0);
}
#endif
/**
Working version.
*/
inline FIO_FUNC uintptr_t fio_risky_hash2(const void *data, size_t len,
uint64_t salt);
inline FIO_FUNC uintptr_t risky2(char *data, size_t len) {
return fio_risky_hash2(data, len, 0);
}
inline FIO_FUNC uintptr_t risky(char *data, size_t len) {
return fio_risky_hash(data, len, 0);
}
/* *****************************************************************************
Hash setup and testing...
***************************************************************************** */
struct hash_fn_names_s {
char *name;
hashing_func_fn fn;
} hash_fn_list[] = {
{"counter (no hash, RAM access test)", counter},
{"siphash13", siphash13},
{"siphash24", siphash24},
{"sha1", sha1},
#if TEST_XXHASH
{"xxhash", xxhash_test},
#endif
{"risky", risky},
{"risky2", risky2},
{NULL, NULL},
};
static void initialize_hash_names(void) {
for (size_t i = 0; hash_fn_list[i].name; ++i) {
fio_str_s tmp = FIO_STR_INIT_STATIC(hash_fn_list[i].name);
hash_name_insert(&hash_names, fio_str_hash(&tmp), hash_fn_list[i].fn);
FIO_LOG_DEBUG("Registered %s hashing function.\n\t\t(%zu registered)",
hash_fn_list[i].name, hash_name_count(&hash_names));
}
}
static char *hash_name(hashing_func_fn fn) {
for (size_t i = 0; hash_fn_list[i].name; ++i) {
if (hash_fn_list[i].fn == fn)
return hash_fn_list[i].name;
}
return NULL;
}
static void print_hash_names(void) {
for (size_t i = 0; hash_fn_list[i].name; ++i) {
fprintf(stderr, "* %s\n", hash_fn_list[i].name);
}
}
static void test_hash_function_speed(hashing_func_fn h, char *name) {
FIO_LOG_DEBUG("Speed testing for %s", name);
/* test based on code from BearSSL with credit to Thomas Pornin */
uint8_t buffer[8192];
memset(buffer, 'T', sizeof(buffer));
/* warmup */
uint64_t hash = 0;
for (size_t i = 0; i < 4; i++) {
hash += h((char *)buffer, sizeof(buffer));
memcpy(buffer, &hash, sizeof(hash));
}
/* loop until test runs for more than 2 seconds */
for (uint64_t cycles = (8192 << 4);;) {
clock_t start, end;
start = clock();
for (size_t i = cycles; i > 0; i--) {
hash += h((char *)buffer, sizeof(buffer));
__asm__ volatile("" ::: "memory");
}
end = clock();
memcpy(buffer, &hash, sizeof(hash));
if ((end - start) >= (2 * CLOCKS_PER_SEC) ||
cycles >= ((uint64_t)1 << 62)) {
fprintf(stderr, "%-20s %8.2f MB/s\n", name,
(double)(sizeof(buffer) * cycles) /
(((end - start) * (1000000.0 / CLOCKS_PER_SEC))));
break;
}
cycles <<= 2;
}
}
static void test_hash_function(hashing_func_fn h) {
size_t best_count = 0, best_capa = 1024;
#define test_for_best() \
if (collisions_capa(&c) > 1024 && \
(collisions_count(&c) * (double)1 / collisions_capa(&c)) > \
(best_count * (double)1 / best_capa)) { \
best_count = collisions_count(&c); \
best_capa = collisions_capa(&c); \
}
char *name = NULL;
for (size_t i = 0; hash_fn_list[i].name; ++i) {
if (hash_fn_list[i].fn == h) {
name = hash_fn_list[i].name;
break;
}
}
if (!name)
name = "unknown";
fprintf(stderr, "======= %s\n", name);
/* Speed test */
test_hash_function_speed(h, name);
/* Collision test */
collisions_s c = FIO_SET_INIT;
size_t count = 0;
FIO_ARY_FOR(&words, w) {
fio_str_info_s i = fio_str_info(w);
// fprintf(stderr, "%s\n", i.data);
printf("\33[2K [%zu] %s\r", ++count, i.data);
collisions_overwrite(&c, h(i.data, i.len), w, NULL);
test_for_best();
}
printf("\33[2K\r\n");
fprintf(stderr, "* Total collisions detected for %s: %zu\n", name,
words_count(&words) - collisions_count(&c));
fprintf(stderr, "* Final set utilization ratio (over 1024) %zu/%zu\n",
collisions_count(&c), collisions_capa(&c));
fprintf(stderr, "* Best set utilization ratio %zu/%zu\n", best_count,
best_capa);
collisions_free(&c);
}
/* *****************************************************************************
Finsing a mod64 inverse
See: https://lemire.me/blog/2017/09/18/computing-the-inverse-of-odd-integers/
***************************************************************************** */
/* will return `inv` if `inv` is inverse of `n` */
static uint64_t inverse64_test(uint64_t n, uint64_t inv) {
uint64_t result = inv * (2 - (n * inv));
return result;
}
static uint64_t inverse64(uint64_t x) {
uint64_t y = (3 * x) ^ 2;
y = inverse64_test(x, y);
y = inverse64_test(x, y);
y = inverse64_test(x, y);
y = inverse64_test(x, y);
if (FIO_LOG_LEVEL >= FIO_LOG_LEVEL_DEBUG) {
char buff[64];
fio_str_s t = FIO_STR_INIT;
fio_str_write(&t, "\n\t\tinverse for:\t", 16);
fio_str_write(&t, buff, fio_ltoa(buff, x, 16));
fio_str_write(&t, "\n\t\tis:\t\t\t", 8);
fio_str_write(&t, buff, fio_ltoa(buff, y, 16));
fio_str_write(&t, "\n\t\tsanity inverse test: 1==", 27);
fio_str_write_i(&t, x * y);
FIO_LOG_DEBUG("%s", fio_str_data(&t));
}
return y;
}
/* *****************************************************************************
Hash Breaking Word Workshop
***************************************************************************** */
/**
* Attacking 8 byte words, which follow this code path:
* h64 = seed + PRIME64_5;
* h64 += len; // len == 8
* if (p + 4 <= bEnd) {
* h64 ^= (U64)(XXH_get32bits(p)) * PRIME64_1;
* h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
* p += 4;
* }
*
* while (p < bEnd) {
* h64 ^= (*p) * PRIME64_5;
* h64 = XXH_rotl64(h64, 11) * PRIME64_1;
* p++;
* }
*
* h64 ^= h64 >> 33;
* h64 *= PRIME64_2;
* h64 ^= h64 >> 29;
* h64 *= PRIME64_3;
* h64 ^= h64 >> 32;
*/
FIO_FUNC void attack_xxhash2(void) {
/* POC - forcing XXHash to return seed only data (here, seed = 0) */
const uint64_t PRIME64_1 = 11400714785074694791ULL;
const uint64_t PRIME64_2 = 14029467366897019727ULL;
// const uint64_t PRIME64_3 = 1609587929392839161ULL;
// const uint64_t PRIME64_4 = 9650029242287828579ULL;
// const uint64_t PRIME64_5 = 2870177450012600261ULL;
const uint64_t PRIME64_1_INV = inverse64(PRIME64_1);
const uint64_t PRIME64_2_INV = inverse64(PRIME64_2);
// const uint64_t PRIME64_3_INV = inverse64(PRIME64_3);
// const uint64_t PRIME64_4_INV = inverse64(PRIME64_4);
// const uint64_t PRIME64_5_INV = inverse64(PRIME64_5);
const uint64_t seed_manipulation[4] = {PRIME64_1 + PRIME64_2, PRIME64_2, 0,
-PRIME64_1};
uint64_t v[4] = {0, 0, 0, 0};
/* attack v *= PRIME64_1 */
v[0] = v[0] * PRIME64_1_INV;
v[1] = v[1] * PRIME64_1_INV;
v[2] = v[2] * PRIME64_1_INV;
v[3] = v[3] * PRIME64_1_INV;
/* attack v = XXH_rotl64(v, 31) */
v[0] = (v[0] >> 31) | (v[0] << (64 - 31));
v[1] = (v[1] >> 31) | (v[1] << (64 - 31));
v[2] = (v[2] >> 31) | (v[2] << (64 - 31));
v[3] = (v[3] >> 31) | (v[3] << (64 - 31));
/* attack seed manipulation */
v[0] = v[0] - seed_manipulation[0];
v[1] = v[1] - seed_manipulation[1];
v[2] = v[2] - seed_manipulation[2];
v[3] = v[3] - seed_manipulation[3];
/* attack v += XXH_get64bits(p) * PRIME64_2 */
v[0] = v[0] * PRIME64_2_INV;
v[1] = v[1] * PRIME64_2_INV;
v[2] = v[2] * PRIME64_2_INV;
v[3] = v[3] * PRIME64_2_INV;
uint64_t seed_data = XXH64(v, 32, 0);
if (seed_data == 0)
fprintf(stderr, "XXHash seed data extracted for seed == 0!\n");
else
fprintf(stderr, "Seed extraction failed %llu\n", seed_data);
}
FIO_FUNC void attack_xxhash(void) {
/* POC - forcing XXHash to return seed only data (here, seed = 0) */
const uint64_t PRIME64_1 = 11400714785074694791ULL;
const uint64_t PRIME64_2 = 14029467366897019727ULL;
const uint64_t PRIME64_3 = 1609587929392839161ULL;
const uint64_t PRIME64_4 = 9650029242287828579ULL;
const uint64_t PRIME64_2_INV = 0x0BA79078168D4BAFULL;
const uint64_t seed_manipulation[4] = {PRIME64_1 + PRIME64_2, PRIME64_2, 0,
-PRIME64_1};
uint64_t v[4] = {0, 0, 0, 0};
/* attack seed manipulation */
v[0] = v[0] - seed_manipulation[0];
v[1] = v[1] - seed_manipulation[1];
v[2] = v[2] - seed_manipulation[2];
v[3] = v[3] - seed_manipulation[3];
/* attack v += XXH_get64bits(p) * PRIME64_2 */
v[0] = v[0] * PRIME64_2_INV;
v[1] = v[1] * PRIME64_2_INV;
v[2] = v[2] * PRIME64_2_INV;
v[3] = v[3] * PRIME64_2_INV;
uint64_t seed = 2870177450012600261ULL;
uint64_t expected_seed;
/* I didn't work out how to extract the seeed from this part */
expected_seed = fio_lrot(seed, 1) + fio_lrot(seed, 7) + fio_lrot(seed, 12) +
fio_lrot(seed, 18);
uint64_t tmp = seed * PRIME64_2;
tmp = fio_lrot(tmp, 31);
tmp *= PRIME64_1;
expected_seed ^= tmp;
expected_seed = expected_seed * PRIME64_1 + PRIME64_4;
expected_seed ^= tmp;
expected_seed = expected_seed * PRIME64_1 + PRIME64_4;
expected_seed ^= tmp;
expected_seed = expected_seed * PRIME64_1 + PRIME64_4;
expected_seed ^= tmp;
expected_seed = expected_seed * PRIME64_1 + PRIME64_4;
expected_seed += 32;
expected_seed ^= expected_seed >> 33;
expected_seed *= PRIME64_2;
expected_seed ^= expected_seed >> 29;
expected_seed *= PRIME64_3;
expected_seed ^= expected_seed >> 32;
uint64_t seed_data = XXH64(v, 32, 0);
if (seed_data == expected_seed)
fprintf(stderr, "XXHash extraxted seed data matches expectations!\n");
else
fprintf(stderr, "Seed extraction failed %llu\n", seed_data);
// char b[128] = {0};
// fio_ltoa(b, v[0], 16);
// fio_ltoa(b + 32, v[1], 16);
// fio_ltoa(b + 64, v[2], 16);
// fio_ltoa(b + 96, v[3], 16);
// fprintf(stderr, "Message was:\n%s\n%s\n%s\n%s\n", b, b + 32, b + 64, b +
// 96);
// Output (message):
// 0xFB9FE7DB392000B6
// 0xFFFFFFFFFFFFFFFF
// 0x0000000000000000
// 0x04601824C6DFFF49
}
/**
* Attacking 64 byte messages where the last 32 bytes are the same and the first
* 32 bytes use rotating 8 byte words. This is attcking the following part in
* the code:
*
* U64 v1 = seed + PRIME64_1 + PRIME64_2;
* U64 v2 = seed + PRIME64_2;
* U64 v3 = seed + 0;
* U64 v4 = seed - PRIME64_1;
*
* do {
* v1 += XXH_get64bits(p) * PRIME64_2;
* p += 8;
* v1 = XXH_rotl64(v1, 31);
* v1 *= PRIME64_1;
* //... v2, v3, v4 same;
* } while (p <= limit);
*
* h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) +
* XXH_rotl64(v4, 18);
*/
FIO_FUNC void add_bad4xxhash(void) {
attack_xxhash();
const uint64_t PRIME64_1 = 11400714785074694791ULL;
const uint64_t PRIME64_2 = 14029467366897019727ULL;
const uint64_t PRIME64_1_INV = inverse64(PRIME64_1);
const uint64_t PRIME64_2_INV = inverse64(PRIME64_2);
const uint64_t seed_manipulation[4] = {PRIME64_1 + PRIME64_2, PRIME64_2, 0,
-PRIME64_1};
uint64_t rotating[4] = {0x1, 0x20, 0x300, 0x4000};
uint8_t results[32][16] = {{0}};
uint8_t results_count = 0;
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
if (i == j) /* all 4 rotating words must be present */
continue;
/* mix rotating word order */
uint64_t v[4] = {rotating[i], rotating[j], rotating[3 - i],
rotating[3 - j]};
/* prepare vector against h64 = XXH_rotl64... */
v[0] = (v[0] >> 1) | (v[0] << (64 - 1));
v[1] = (v[1] >> 7) | (v[1] << (64 - 7));
v[2] = (v[2] >> 12) | (v[2] << (64 - 12));
v[3] = (v[3] >> 18) | (v[3] << (64 - 18));
/* attack v *= PRIME64_1 */
v[0] = v[0] * PRIME64_1_INV;
v[1] = v[1] * PRIME64_1_INV;
v[2] = v[2] * PRIME64_1_INV;
v[3] = v[3] * PRIME64_1_INV;
/* attack v = XXH_rotl64(v, 31) */
v[0] = (v[0] >> 31) | (v[0] << (64 - 31));
v[1] = (v[1] >> 31) | (v[1] << (64 - 31));
v[2] = (v[2] >> 31) | (v[2] << (64 - 31));
v[3] = (v[3] >> 31) | (v[3] << (64 - 31));
/* attack seed manipulation */
v[0] = v[0] - seed_manipulation[0];
v[1] = v[1] - seed_manipulation[1];
v[2] = v[2] - seed_manipulation[2];
v[3] = v[3] - seed_manipulation[3];
/* attack v += XXH_get64bits(p) * PRIME64_2 */
v[0] = v[0] * PRIME64_2_INV;
v[1] = v[1] * PRIME64_2_INV;
v[2] = v[2] * PRIME64_2_INV;
v[3] = v[3] * PRIME64_2_INV;
/* copy to results, if unique */
uint8_t unique = 1;
for (int t = 0; t < results_count; ++t) {
if (!memcmp(&results[0][t], v, 32))
unique = 0;
}
if (unique) {
memcpy(&results[0][results_count], v, 32);
++results_count;
}
}
}
if (results_count) {
fprintf(stderr, "Created %u vectors, now testing...\n", results_count);
uint64_t origin = XXH64(&results[0][0], 32, 0);
for (int i = 0; i < results_count; ++i) {
words_push(&words, FIO_STR_INIT_STATIC2(&results[0][i], 32));
if (i && origin == XXH64(&results[0][i], 32, 0))
fprintf(stderr, "Possible collision [%d]\n", i);
}
fprintf(stderr, "Done testing.\n");
}
}
FIO_FUNC void add_bad4risky(void) {}
FIO_FUNC void find_bit_collisions(hashing_func_fn fn, size_t collision_count,
uint8_t bit_count) {
words_s c = FIO_ARY_INIT;
const uint64_t mask = (1ULL << bit_count) - 1;
time_t start = clock();
while (words_count(&c) < collision_count) {
uint64_t rnd = fio_rand64();
if ((fn((char *)&rnd, 8) & mask) == mask) {
words_push(&c, FIO_STR_INIT_STATIC2((char *)&rnd, 8));
}
}
time_t end = clock();
char *name = hash_name(fn);
if (!name)
name = "unknown";
fprintf(stderr,
"* It took %zu cycles to find %zu (%u bit) collisions for %s (brute "
"fource):\n",
end - start, words_count(&c), bit_count, name);
FIO_ARY_FOR(&c, pos) {
uint64_t tmp = fio_str2u64(fio_str_data(pos));
fprintf(stderr, "* %p => %p\n", (void *)tmp,
(void *)fn(fio_str_data(pos), 8));
}
words_free(&c);
}
static void add_bad_words(void) {
if (!fio_cli_get("-t")) {
find_bit_collisions(risky, 16, 16);
find_bit_collisions(xxhash_test, 16, 16);
find_bit_collisions(siphash13, 16, 16);
find_bit_collisions(sha1, 16, 16);
}
add_bad4xxhash();
add_bad4risky();
}
/* *****************************************************************************
Hash experimentation workspace
***************************************************************************** */
/* Risky Hash consumption round, accepts a state word s and an input word w */
#define fio_risky_consume(s, w) \
(s) ^= (w); \
(s) = fio_lrot64((s), 33) + (w); \
(s) *= primes[0];
/* Computes a facil.io Risky Hash. */
static inline uintptr_t fio_risky_hash2(const void *data_, size_t len,
uint64_t seed) {
/* The primes used by Risky Hash */
const uint64_t primes[] = {
0xFBBA3FA15B22113B, // 1111101110111010001111111010000101011011001000100001000100111011
0xAB137439982B86C9, // 1010101100010011011101000011100110011000001010111000011011001001
};
/* The consumption vectors initialized state */
uint64_t v[4] = {
seed ^ primes[1],
~seed + primes[1],
fio_lrot64(seed, 17) ^ (primes[1] + primes[0]),
fio_lrot64(seed, 33) + (~primes[1]),
};
/* reading position */
const uint8_t *data = (uint8_t *)data_;
/* consume 256bit blocks */
for (size_t i = len >> 5; i; --i) {
fio_risky_consume(v[0], fio_str2u64(data));
fio_risky_consume(v[1], fio_str2u64(data + 8));
fio_risky_consume(v[2], fio_str2u64(data + 16));
fio_risky_consume(v[3], fio_str2u64(data + 24));
data += 32;
}
/* Consume any remaining 64 bit words. */
switch (len & 24) {
case 24:
fio_risky_consume(v[2], fio_str2u64(data + 16));
case 16: /* overflow */
fio_risky_consume(v[1], fio_str2u64(data + 8));
case 8: /* overflow */
fio_risky_consume(v[0], fio_str2u64(data));
data += len & 24;
}
uint64_t tmp = 0;
/* consume leftover bytes, if any */
switch ((len & 7)) {
case 7: /* overflow */
tmp |= ((uint64_t)data[6]) << 8;
case 6: /* overflow */
tmp |= ((uint64_t)data[5]) << 16;
case 5: /* overflow */
tmp |= ((uint64_t)data[4]) << 24;
case 4: /* overflow */
tmp |= ((uint64_t)data[3]) << 32;
case 3: /* overflow */
tmp |= ((uint64_t)data[2]) << 40;
case 2: /* overflow */
tmp |= ((uint64_t)data[1]) << 48;
case 1: /* overflow */
tmp |= ((uint64_t)data[0]) << 56;
/* ((len & 24) >> 3) is a 0-3 value representing the next state vector */
/* `switch` allows v[i] to be a register without a memory address */
/* using v[(len & 24) >> 3] forces implementation to use memory */
switch ((len & 24) >> 3) {
case 3:
fio_risky_consume(v[3], tmp);
break;
case 2:
fio_risky_consume(v[2], tmp);
break;
case 1:
fio_risky_consume(v[1], tmp);
break;
case 0:
fio_risky_consume(v[0], tmp);
break;
}
}
/* merge and mix */
uint64_t result = fio_lrot64(v[0], 17) + fio_lrot64(v[1], 13) +
fio_lrot64(v[2], 47) + fio_lrot64(v[3], 57);
result += len;
result += v[0] * primes[1];
result ^= fio_lrot64(result, 13);
result += v[1] * primes[1];
result ^= fio_lrot64(result, 29);
result += v[2] * primes[1];
result ^= fio_lrot64(result, 33);
result += v[3] * primes[1];
result ^= fio_lrot64(result, 51);
/* irreversible avalanche... I think */
result ^= (result >> 29) * primes[0];
return result;
}
#undef fio_risky_consume
inline FIO_FUNC uintptr_t fio_risky_hash_old(void *data_, size_t len,
uint64_t seed) {
/* inspired by xxHash: Yann Collet, Maciej Adamczyk... */
/* so I borrowed their primes as homage ;-) */
/* more primes at: https://asecuritysite.com/encryption/random3?val=64 */
const uint64_t primes[] = {
/* xxHash Primes */
14029467366897019727ULL, 11400714785074694791ULL, 1609587929392839161ULL,
9650029242287828579ULL, 2870177450012600261ULL,
};
/*
* 4 x 64 bit vectors for 256bit block consumption.
* When implementing a streaming variation, more fields might be required.
*/
struct risky_state_s {
uint64_t v[4];
} s = {{
(seed + primes[0] + primes[1]),
((~seed) + primes[0]),
((seed << 9) ^ primes[3]),
((seed >> 17) ^ primes[2]),
}};
/* A single data-consuming round, wrd is the data in big-endian 64 bit */
/* the design follows the xxHash basic round scheme and is easy to vectorize */
#define fio_risky_round_single(wrd, i) \
s.v[(i)] += (wrd)*primes[0]; \
s.v[(i)] = fio_lrot64(s.v[(i)], 33); \
s.v[(i)] *= primes[1];
/* an unrolled (vectorizable) 256bit round */
#define fio_risky_round_256(w0, w1, w2, w3) \
fio_risky_round_single(w0, 0); \
fio_risky_round_single(w1, 1); \
fio_risky_round_single(w2, 2); \
fio_risky_round_single(w3, 3);
uint8_t *data = (uint8_t *)data_;
/* loop over 256 bit "blocks" */
const size_t len_256 = len & (((size_t)-1) << 5);
for (size_t i = 0; i < len_256; i += 32) {
/* perform round for block */
fio_risky_round_256(fio_str2u64(data), fio_str2u64(data + 8),
fio_str2u64(data + 16), fio_str2u64(data + 24));
data += 32;
}
/* process last 64bit words in each vector */
switch (len & 24UL) {
case 24:
fio_risky_round_single(fio_str2u64(data), 0);
fio_risky_round_single(fio_str2u64(data + 8), 1);
fio_risky_round_single(fio_str2u64(data + 16), 2);
data += 24;
break;
case 16:
fio_risky_round_single(fio_str2u64(data), 0);
fio_risky_round_single(fio_str2u64(data + 8), 1);
data += 16;
break;
case 8:
fio_risky_round_single(fio_str2u64(data), 0);
data += 8;
break;
}
/* always process the last 64bits, if any, in the 4th vector */
uint64_t last_bytes = 0;
switch (len & 7) {
case 7:
last_bytes |= ((uint64_t)data[6] & 0xFF) << 56;
case 6: /* overflow */
last_bytes |= ((uint64_t)data[5] & 0xFF) << 48;
case 5: /* overflow */
last_bytes |= ((uint64_t)data[4] & 0xFF) << 40;
case 4: /* overflow */
last_bytes |= ((uint64_t)data[3] & 0xFF) << 32;
case 3: /* overflow */
last_bytes |= ((uint64_t)data[2] & 0xFF) << 24;
case 2: /* overflow */
last_bytes |= ((uint64_t)data[1] & 0xFF) << 16;
case 1: /* overflow */
last_bytes |= ((uint64_t)data[0] & 0xFF) << 8;
fio_risky_round_single(last_bytes, 3);
}
/* mix stage */
uint64_t result = (fio_lrot64(s.v[3], 63) + fio_lrot64(s.v[2], 57) +
fio_lrot64(s.v[1], 52) + fio_lrot64(s.v[0], 46));
result += len * primes[4];
result = ((result ^ s.v[0]) * primes[3]) + primes[2];
result = ((result ^ s.v[1]) * primes[3]) + primes[2];
result = ((result ^ s.v[2]) * primes[3]) + primes[2];
result = ((result ^ s.v[3]) * primes[3]) + primes[2];
/* avalanche */
result ^= (result >> 33);
result *= primes[1];
result ^= (result >> 29);
result *= primes[2];
return result;
#undef fio_risky_round_single
#undef fio_risky_round_256
}
#if TEST_XXHASH
#include "xxhash.c"
#endif