shithub: femtolisp

ref: ca88d4dfc3831931281ca357af4413aa5385bd5d
dir: /hashing.c/

#include "llt.h"
#include "hashing.h"

lltuint_t
nextipow2(lltuint_t i)
{
	if(i == 0)
		return 1;
	i |= i >> 1;
	i |= i >> 2;
	i |= i >> 4;
	i |= i >> 8;
	i |= i >> 16;
#ifdef BITS64
	i |= i >> 32;
#endif
	i++;
	return i ? i : TOP_BIT;
}

uint32_t
int32hash(uint32_t a)
{
	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);
	return a;
}

uint64_t
int64hash(uint64_t key)
{
	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);
	return key;
}

uint32_t
int64to32hash(uint64_t key)
{
	key = (~key) + (key << 18); // key = (key << 18) - key - 1;
	key = key ^ (key >> 31);
	key = key * 21;			 // key = (key + (key << 2)) + (key << 4);
	key = key ^ (key >> 11);
	key = key + (key << 6);
	key = key ^ (key >> 22);
	return (uint32_t)key;
}

#include "lookup3.c"

uint64_t
memhash(const char* buf, size_t n)
{
	uint32_t c = 0xcafe8881, b = 0x4d6a087c;

	hashlittle2(buf, n, &c, &b);
	return (uint64_t)c | (((uint64_t)b)<<32);
}

uint32_t
memhash32(const char* buf, size_t n)
{
	uint32_t c = 0xcafe8881, b = 0x4d6a087c;

	hashlittle2(buf, n, &c, &b);
	return c;
}