Skip to content

Instantly share code, notes, and snippets.

@serialhex
Last active Aug 18, 2021
Embed
What would you like to do?
some fibonacci hash functions. 64 and 32 bit.
// 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;
}
/* 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;
}
// 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