shithub: mc

ref: 4e656a4f039b9230c820f12d3b1e4a5c8e55cf47
dir: /libstd/hashfuncs.myr/

use "die.use"
use "sleq.use"
use "types.use"

pkg std =
	const strhash	: (s : byte[:]	-> uint32)
	const streq	: (a : byte[:], b : byte[:]	-> bool)

	generic ptrhash	: (p : @a#	-> uint32)
	generic ptreq	: (a : @a#, b : @a#	-> bool)

	generic inthash	: (v : @a::(integral,numeric)	-> uint32)
	generic inteq	: (a : @a::(integral,numeric), b : @a::(integral,numeric) -> bool)

	const murmurhash2	: (data : byte[:], seed : uint32 -> uint32)

	generic slhash	: (sl : @a[:] -> uint32)
	generic tobytes	: (sl : @a[:] -> byte[:])
;;

const Seed = 1234

generic slhash = {data : @a[:]
	-> strhash(slbytes(data))
}

generic slbytes = {data : @a[:]
	var n

	n = data.len * sizeof(@a)
	-> (data castto(byte#))[:n]
}

/* Supremely simple djb hash. */
const strhash = {s
	-> murmurhash2(s, Seed)
}

const streq = {a, b
	-> sleq(a, b)
}

generic ptrhash = {p : @a#
	var x

	x = &p castto(byte#)
	-> murmurhash2(x[0:sizeof(@a)], Seed)
}

generic ptreq = {a, b
	-> a == b
}

generic inthash = {v : @a::(integral,numeric)
	var p

	p = &v castto(byte#)
	-> murmurhash2(p[0:sizeof(@a)], Seed)
}

generic inteq = {a, b
	-> a == b
}

const murmurhash2 = {data, seed
	const m = 0x5bd1e995;
	const r = 24
	var h, k
	
	h = seed ^ data.len
	while data.len >= 4
		k = (data[0] castto(uint32))
		k |= (data[1] castto(uint32)) << 8
		k |= (data[2] castto(uint32)) << 16
		k |= (data[3] castto(uint32)) << 24

		k *= m
		k ^= k >> r
		k *= m

		h *= m
		h ^= k
		data = data[4:]
	;;

	match data.len
	| 3:
		h ^= (data[2] castto(uint32)) << 16
		h ^= (data[1] castto(uint32)) <<8
		h ^= (data[0] castto(uint32))
	| 2:
		h ^= (data[1] castto(uint32)) <<8
		h ^= (data[0] castto(uint32))
	| 1:
		h ^= (data[0] castto(uint32))
	| 0:	/* nothing */
	| _:	die("0 < len < 4 must be true")
	;;
	h *= m

	h ^= h >> 13
	h *= m
	h ^= h >> 15

	-> h
}