Last active
August 18, 2021 17:07
-
-
Save serialhex/ddbaf64fa9942a6c41b29618974f5b3a to your computer and use it in GitHub Desktop.
some fibonacci hash functions. 64 and 32 bit.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// this runs nicely on SMHasher | |
// fails a few tests, but overall is fast and passes most tests | |
size_t derpy_hash(const char *key, int len, uint32_t seed) { | |
const uint64_t *data = (const uint64_t *)key; | |
const uint64_t fib = 11400714819323198485llu; | |
// 8 bytes in a 64-bit value, so take the last 7 bits | |
uint8_t m = len & 7; | |
// initialize | |
uint64_t h = (seed ^ len) * fib; | |
for (int i = 0; i < len/8; i++) { | |
h = (h + data[i]) * fib; | |
} | |
if (m) { | |
uint8_t rem = len - m; | |
const uint8_t *d = (const uint8_t *)key; | |
uint64_t last = 0; | |
switch (m) { | |
case 7: last = d[rem++]; | |
case 6: last = (last << 8) | d[rem++]; | |
case 5: last = (last << 8) | d[rem++]; | |
case 4: last = (last << 8) | d[rem++]; | |
case 3: last = (last << 8) | d[rem++]; | |
case 2: last = (last << 8) | d[rem++]; | |
case 1: last = (last << 8) | d[rem++]; | |
} | |
h = (h + last) * fib; | |
} | |
// from pcg_output_rxs_m_xs_64_64: | |
uint64_t word = ((h >> ((h >> 59u) + 5u)) ^ h) * 12605985483714917081ull; | |
return (word >> 43u) ^ word; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* just some stuff for later, on smhasher-style hash functions | |
* here is the fibonacci hash, inspired by this: | |
* https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ | |
* oh, and this is cool also: | |
* https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ | |
* have fun! | |
*/ | |
#include <stdint.h> | |
/* some Fibonacci constants for a number of bits b | |
* floor(2^(b)/ ((1 + √5)/2)) | |
* 2^8 = 158 | |
* 2^16 = 40503 | |
* 2^32 = 2654435769 | |
* 2^64 = 11400714819323198485 | |
* 2^128 = 210306068529402873165736369884012333108 | |
* 2^256 = 71563446777022297856526126342750658392501306254664949883333486863006233104021 | |
* 2^512 = 8286481015334893988907527251732611664457280877896990125350747801032912124181934735572335005532987901856694870697621088413914768940958605061563703415234102 | |
* 2^1024 = 111103545868725975185578674770941253548085647175230593275709448371553253006147314587817210981315418038152651252381241848663172381125005611474547150822121573954448475698342462132071640602726690043967503533098589415135032684552325470109005299145741049782192534336153650840562560032276382145192816865771520714469 | |
*/ | |
void fib_hash64(const void * key, int len, uint32_t seed, void * out ) { | |
const uint64_t fib = 11400714819323198485llu; | |
const uint64_t *data = (const uint64_t *)key; | |
// 8 bytes in a 64-bit value, so take the last 7 bits | |
uint8_t m = len & 7; | |
// initialize | |
uint64_t h = seed + len; | |
for (int i = 0; i < len/8; i++) { | |
h = h * fib + data[i]; | |
} | |
if (m) { | |
uint8_t rem = len - m; | |
const uint8_t *d = (const uint8_t *)key; | |
uint64_t last = 0; | |
switch (m) { | |
case 7: last = d[rem++]; | |
case 6: last = (last << 8) | d[rem++]; | |
case 5: last = (last << 8) | d[rem++]; | |
case 4: last = (last << 8) | d[rem++]; | |
case 3: last = (last << 8) | d[rem++]; | |
case 2: last = (last << 8) | d[rem++]; | |
case 1: last = (last << 8) | d[rem++]; | |
} | |
h = h * fib + last; | |
} | |
*(uint64_t *) out = h; | |
} | |
void fib_hash32(const void * key, int len, uint32_t seed, void * out ) { | |
const uint32_t fib = 2654435769u; | |
const uint32_t *data = (const uint32_t *)key; | |
// 4 bytes in a 32-bit value, so take the last 3 bits | |
uint8_t m = len & 3; | |
// initalize | |
uint32_t h = seed + len; | |
for (int i = 0; i < len/4; i++) { | |
h = h * fib + data[i]; | |
} | |
if (m) { | |
uint8_t rem = len - m; | |
const uint8_t *d = (const uint8_t *)key; | |
uint32_t last = 0; | |
switch (m) { | |
case 3: last = d[rem++]; | |
case 2: last = (last << 8) | d[rem++]; | |
case 1: last = (last << 8) | d[rem++]; | |
} | |
h = h * fib + last; | |
} | |
*(uint32_t *) out = h; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// alternately, something like this might be good! | |
#include <stdint.h> | |
#include <stdio.h> | |
#include <time.h> | |
const uint16_t fib16 = 40503; | |
const uint16_t fib16_1 = 25031; | |
const uint32_t fib32 = 2654435769; | |
const uint32_t fib32_1 = 1640531527; | |
const uint64_t fib64 = 11400714819323198485; | |
const uint64_t fib64_1 = 7046029254386353131; | |
const uint16_t fib_seq[] = {1, 2, 3, 5, 8, 13, 21, 34, 55}; | |
//0 1 2 3 4 5 6 7 8 | |
inline uint16_t hash_fib16_x(uint16_t n, uint16_t s) { | |
uint16_t tmp = n + fib16_1; | |
tmp += s; | |
tmp ^= tmp >> 9; | |
tmp *= fib16; | |
tmp ^= tmp << 7; | |
return tmp * fib16; | |
} | |
inline uint16_t hash_fib16(uint16_t n, uint16_t s) { | |
n ^= fib16; | |
n ^= s; | |
// n *= (s ^ 3) + s; | |
return n * fib16; | |
} | |
inline uint32_t hash_fib32(uint32_t n, uint32_t s) { | |
n ^= fib32; | |
n *= (s ^ 3) + s; | |
return n * fib32; | |
} | |
uint32_t Squirrel3( int position, uint32_t seed) { | |
const uint32_t BIT_NOISE1 = 0xb5297a4d; | |
const uint32_t BIT_NOISE2 = 0x68e31da4; | |
const uint32_t BIT_NOISE3 = 0x1b56c4e9; | |
uint32_t mangled = position; | |
mangled *= BIT_NOISE1; | |
mangled += seed; | |
mangled ^= (mangled >> 8); | |
mangled += BIT_NOISE2; | |
mangled ^= (mangled << 8); | |
mangled *= BIT_NOISE3; | |
mangled ^= (mangled >> 8); | |
return mangled; | |
} | |
typedef struct MinMax { | |
uint64_t val; | |
uint64_t init; | |
uint64_t seed; | |
uint64_t count; | |
} MinMax; | |
int main(int argc, char* argv) { | |
clock_t start_time, end_time; | |
double cpu_time_used; | |
MinMax max; | |
MinMax min; | |
max.val = 0; | |
max.init = 0; | |
max.seed = 0; | |
max.count = 1; | |
min.val = UINT16_MAX; | |
min.init = 0; | |
min.seed = 0; | |
min.count = 1; | |
// printf("Should take: %f sec\n", 9.2 * UINT16_MAX); | |
// start_time = clock(); | |
for (uint64_t init = 0; init < UINT16_MAX; init++) { | |
uint64_t start = init; | |
uint64_t prev; | |
uint64_t seed = init; | |
uint64_t i = 0; | |
printf("starting at: %I64u\n", start); | |
start_time = clock(); | |
do { | |
prev = start; | |
start = hash_fib16(start, seed); | |
i++; | |
} while ( i < UINT16_MAX && start != init); | |
if (i == max.val) { | |
max.count++; | |
} | |
if (i == min.val) { | |
min.count++; | |
} | |
if (i > max.val) { | |
max.val = i; | |
max.init = init; | |
max.seed = seed; | |
max.count = 1; | |
} | |
if (i < min.val) { | |
min.val = i; | |
min.init = init; | |
min.seed = seed; | |
min.count = 1; | |
} | |
// if (i == UINT16_MAX) { | |
// break; | |
// } | |
printf("%s; Took %I64u iterations to loop around with init %I64u, prev: %I64u\n", | |
(i == UINT16_MAX) ? "WIN!" : "Fail!", | |
i, init, prev); | |
end_time = clock(); | |
cpu_time_used = ((double) (end_time - start_time)) / CLOCKS_PER_SEC; | |
printf("time: %f sec, time per loop: %f ms\n", | |
cpu_time_used, (cpu_time_used * 1000)/ (double)UINT16_MAX); | |
} | |
end_time = clock(); | |
cpu_time_used = ((double) (end_time - start_time)) / CLOCKS_PER_SEC; | |
printf("took: %f sec, time per loop: %f sec, " | |
"Max %I64u, init %I64u, count %I64u; Min %I64u, init %I64u, count %I64u\n", | |
cpu_time_used, | |
cpu_time_used / UINT16_MAX, | |
max.val, max.init, max.count, | |
min.val, min.init, min.count); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment