city hash odin

city.odin

city64 :: proc(data: []byte) -> u64 {

	// Some primes between 2^63 and 2^64 for various uses.
	K0 :: 0xc3a5c85c97cb3127
	K1 :: 0xb492b66fbe98f273
	K2 :: 0x9ae16a3b2f90404f

	fetch64 :: proc(p: [^]byte) -> u64 {
		res := intrinsics.unaligned_load((^u64)(p))
		when ODIN_ENDIAN == .Big {
			res = intrinsics.byte_swap(res)
		}
		return res
	}

	fetch32 :: proc(p: [^]byte) -> u32 {
		res := intrinsics.unaligned_load((^u32)(p))
		when ODIN_ENDIAN == .Big {
			res = intrinsics.byte_swap(res)
		}
		return res
	}

	rotate :: proc(val: u64, shift: u32) -> u64 {
		return shift == 0 ? val : ((val >> shift) | (val << (64 - shift)))
	}

	shift_mix :: proc(val: u64) -> u64 {
		return val ~ (val >> 47)
	}

	hash_len_16 :: proc(u, v: u64) -> u64 {
		KMUL :: 0x9ddfea08eb382d69
		a := (u ~ v) * KMUL
		a ~= a >> 47
		b := (v ~ a) * KMUL
		b ~= b >> 47
		b *= KMUL
		return b
	}

	hash_len_16_mul :: proc(u, v, mul: u64) -> u64 {
		a := (u ~ v) * mul
		a ~= a >> 47
		b := (v ~ a) * mul
		b ~= b >> 47
		b *= mul
		return b
	}


	hash_len_0_to_16 :: proc(data: []byte) -> u64 {
		len := u64(len(data))
		if len >= 8 {
			mul := K2 + len * 2
			a := fetch64(raw_data(data)) + K2
			b := fetch64(raw_data(data[len-8:]))
			c := rotate(b, 37) * mul + a
			d := (rotate(a, 25) + b) * mul
			return hash_len_16_mul(c, d, mul)
		}
		if len >= 4 {
			mul := K2 + len * 2
			a := u64(fetch32(raw_data(data)))
			return hash_len_16_mul(len + (a << 3), u64(fetch32(raw_data(data[len-4:]))), mul)
		}
		if len > 0 {
			a := data[0]
			b := data[len >> 1]
			c := data[len - 1]
			y := u32(a) + (u32(b) << 8)
			z := u32(len) + (u32(c) << 2)
			return shift_mix(u64(y) * K2 ~ u64(z) * K0) * K2
		}
		return K2
	}

	hash_len_17_to_32 :: proc(data: []byte) -> u64 {
		len := u64(len(data))
		mul := K2 + len * 2
		a := fetch64(raw_data(data)) * K1
		b := fetch64(raw_data(data[8:]))
		c := fetch64(raw_data(data[len-8:])) * mul
		d := fetch64(raw_data(data[len-16:])) * K2
		return hash_len_16_mul(
			rotate(a + b, 43) + rotate(c, 30) + d,
			a + rotate(b + K2, 18) + c,
			mul,
		)
	}

	hash_len_33_to_64 :: proc(data: []byte) -> u64 {
		len := u64(len(data))
		mul := K2 + len * 2
		a := fetch64(raw_data(data)) * K2
		b := fetch64(raw_data(data[8:]))
		c := fetch64(raw_data(data[len-24:]))
		d := fetch64(raw_data(data[len-32:]))
		e := fetch64(raw_data(data[16:])) * K2
		f := fetch64(raw_data(data[24:])) * 9
		g := fetch64(raw_data(data[len-8:]))
		h := fetch64(raw_data(data[len-16:])) * mul
		u := rotate(a + g, 43) + (rotate(b, 30) + c) * 9
		v := ((a + g) ~ d) + f + 1
		w := intrinsics.byte_swap((u + v) * mul) + h
		x := rotate(e + f, 42) + c
		y := (intrinsics.byte_swap((v + w) * mul) + g) * mul
		z := e + f + c
		a = intrinsics.byte_swap((x + z) * mul + y) + b
		b = shift_mix((z + a) * mul + d + h) * mul
		return b + x
	}

	weak_hash_len_32_with_seeds :: proc(w, x, y, z, a, b: u64) -> [2]u64 {
		a, b := a, b
		a += w
		b = rotate(b + a + z, 21)
		c := a
		a += x
		a += y
		b += rotate(a, 44)
		return {a + z, b + c}
	}

	weak_hash_len_32_with_seeds_str :: proc(data: [^]byte, a, b: u64) -> [2]u64 {
		return weak_hash_len_32_with_seeds(
			fetch64(data),
			fetch64(data[8:]),
			fetch64(data[16:]),
			fetch64(data[24:]),
			a,
			b,
		)
	}

	data := data
	len := u64(len(data))
	if len <= 32 {
		if len <= 16 {
			return hash_len_0_to_16(data)
		} else {
			return hash_len_17_to_32(data)
		}
	} else if len <= 64 {
		return hash_len_33_to_64(data)
	}

	x := fetch64(raw_data(data[len-40:]))
	y := fetch64(raw_data(data[len-16:])) + fetch64(raw_data(data[len-56:]))
	z := hash_len_16(fetch64(raw_data(data[len-48:])) + len, fetch64(raw_data(data[len-24:])))
	v := weak_hash_len_32_with_seeds_str(raw_data(data[len-64:]), len, z)
	w := weak_hash_len_32_with_seeds_str(raw_data(data[len-32:]), y + K1, x)
	x = x * K1 + fetch64(raw_data(data))

	len = (len - 1) & ~u64(63)
	for {
		x = rotate(x + y + v.x + fetch64(raw_data(data[8:])), 37) * K1
		y = rotate(y + v.y + fetch64(raw_data(data[48:])), 42) * K1
		x ~= w.y
		y += v.x + fetch64(raw_data(data[40:]))
		z = rotate(z + w.x, 33) * K1
		v = weak_hash_len_32_with_seeds_str(raw_data(data), v.y * K1, x + w.y)
		w = weak_hash_len_32_with_seeds_str(raw_data(data[32:]), z + w.y, y + fetch64(raw_data(data[16:])))
		z, x = x, z

		data = data[64:]
		len -= 64

		if len == 0 { break }
	}

	return hash_len_16(
		hash_len_16(v.x, w.x) + shift_mix(y) * K1 + z,
		hash_len_16(v.y, w.y) + x,
	)
}