upscheme/c/hashing.c

84 lines
1.7 KiB
C
Raw Permalink Normal View History

2008-06-30 21:53:51 -04:00
/*
Hashing
2008-06-30 21:53:51 -04:00
*/
#include <sys/types.h>
2008-06-30 21:53:51 -04:00
#include <math.h>
#include <setjmp.h>
#include <stdarg.h>
#include <stdint.h>
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include "scheme.h"
2008-06-30 21:53:51 -04:00
uintptr_t nextipow2(uintptr_t i)
2008-06-30 21:53:51 -04:00
{
if (i == 0)
return 1;
if ((i & (i - 1)) == 0)
return i;
if (i & TOP_BIT)
return TOP_BIT;
2008-06-30 21:53:51 -04:00
// repeatedly clear bottom bit
while (i & (i - 1))
i = i & (i - 1);
2008-06-30 21:53:51 -04:00
return i << 1;
2008-06-30 21:53:51 -04:00
}
uint32_t int32hash(uint32_t a)
2008-06-30 21:53:51 -04:00
{
a = (a + 0x7ed55d16) + (a << 12);
a = (a ^ 0xc761c23c) ^ (a >> 19);
a = (a + 0x165667b1) + (a << 5);
a = (a + 0xd3a2646c) ^ (a << 9);
a = (a + 0xfd7046c5) + (a << 3);
a = (a ^ 0xb55a4f09) ^ (a >> 16);
2008-06-30 21:53:51 -04:00
return a;
}
uint64_t int64hash(uint64_t key)
2008-06-30 21:53:51 -04:00
{
key = (~key) + (key << 21); // key = (key << 21) - key - 1;
key = key ^ (key >> 24);
key = (key + (key << 3)) + (key << 8); // key * 265
key = key ^ (key >> 14);
key = (key + (key << 2)) + (key << 4); // key * 21
key = key ^ (key >> 28);
key = key + (key << 31);
2008-06-30 21:53:51 -04:00
return key;
}
uint32_t int64to32hash(uint64_t key)
2008-06-30 21:53:51 -04:00
{
key = (~key) + (key << 18); // key = (key << 18) - key - 1;
key = key ^ (key >> 31);
key = key * 21; // key = (key + (key << 2)) + (key << 4);
2008-06-30 21:53:51 -04:00
key = key ^ (key >> 11);
key = key + (key << 6);
key = key ^ (key >> 22);
return (uint32_t)key;
2008-06-30 21:53:51 -04:00
}
#include "lookup3.h"
2008-06-30 21:53:51 -04:00
uint64_t memhash(const char *buf, size_t n)
2008-06-30 21:53:51 -04:00
{
uint32_t c = 0xcafe8881, b = 0x4d6a087c;
2008-06-30 21:53:51 -04:00
hashlittle2(buf, n, &c, &b);
return (uint64_t)c | (((uint64_t)b) << 32);
2008-06-30 21:53:51 -04:00
}
uint32_t memhash32(const char *buf, size_t n)
{
uint32_t c = 0xcafe8881, b = 0x4d6a087c;
hashlittle2(buf, n, &c, &b);
return c;
}