1// Copyright 2023 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5//go:build purego
6
7package maphash
8
9import (
10	"crypto/rand"
11	"internal/byteorder"
12	"math/bits"
13)
14
15func rthash(buf []byte, seed uint64) uint64 {
16	if len(buf) == 0 {
17		return seed
18	}
19	return wyhash(buf, seed, uint64(len(buf)))
20}
21
22func rthashString(s string, state uint64) uint64 {
23	return rthash([]byte(s), state)
24}
25
26func randUint64() uint64 {
27	buf := make([]byte, 8)
28	_, _ = rand.Read(buf)
29	return byteorder.LeUint64(buf)
30}
31
32// This is a port of wyhash implementation in runtime/hash64.go,
33// without using unsafe for purego.
34
35const (
36	m1 = 0xa0761d6478bd642f
37	m2 = 0xe7037ed1a0b428db
38	m3 = 0x8ebc6af09c88c6e3
39	m4 = 0x589965cc75374cc3
40	m5 = 0x1d8e4e27c47d124f
41)
42
43func wyhash(key []byte, seed, len uint64) uint64 {
44	p := key
45	i := len
46	var a, b uint64
47	seed ^= m1
48
49	if i > 16 {
50		if i > 48 {
51			seed1 := seed
52			seed2 := seed
53			for ; i > 48; i -= 48 {
54				seed = mix(r8(p)^m2, r8(p[8:])^seed)
55				seed1 = mix(r8(p[16:])^m3, r8(p[24:])^seed1)
56				seed2 = mix(r8(p[32:])^m4, r8(p[40:])^seed2)
57				p = p[48:]
58			}
59			seed ^= seed1 ^ seed2
60		}
61		for ; i > 16; i -= 16 {
62			seed = mix(r8(p)^m2, r8(p[8:])^seed)
63			p = p[16:]
64		}
65	}
66	switch {
67	case i == 0:
68		return seed
69	case i < 4:
70		a = r3(p, i)
71	default:
72		n := (i >> 3) << 2
73		a = r4(p)<<32 | r4(p[n:])
74		b = r4(p[i-4:])<<32 | r4(p[i-4-n:])
75	}
76	return mix(m5^len, mix(a^m2, b^seed))
77}
78
79func r3(p []byte, k uint64) uint64 {
80	return (uint64(p[0]) << 16) | (uint64(p[k>>1]) << 8) | uint64(p[k-1])
81}
82
83func r4(p []byte) uint64 {
84	return uint64(byteorder.LeUint32(p))
85}
86
87func r8(p []byte) uint64 {
88	return byteorder.LeUint64(p)
89}
90
91func mix(a, b uint64) uint64 {
92	hi, lo := bits.Mul64(a, b)
93	return hi ^ lo
94}
95