some fibonacci hash functions. 64 and 32 bit.

derpyhash.c

// 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;
}

fib_hash.c

/* 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;
}

randhash.c

// 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;
}