1//  Copyright (c) 2018 Couchbase, Inc.
2//  Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file
3//  except in compliance with the License. You may obtain a copy of the License at
4//    http://www.apache.org/licenses/LICENSE-2.0
5//  Unless required by applicable law or agreed to in writing, software distributed under the
6//  License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND,
7//  either express or implied. See the License for the specific language governing permissions
8//  and limitations under the License.
9
10package util
11
12// based on seahash, see https://ticki.github.io/blog/seahash-explained
13
14const (
15	seed1  = 0x16f11fe89b0d677c
16	seed2  = 0xb480a793d8e6c86c
17	seed3  = 0x6fe2e5aaf078ebc9
18	seed4  = 0x14f994a4c5259381
19	pcgRNG = 0x6eed0e9da4d94a4f
20)
21
22// Given a byte slice, compute a 64 bit checksum (hash value)
23func SeaHashSum64(b []byte) uint64 {
24	s := NewSeaHash()
25	s.write(b)
26	return diffuse(s.a ^ s.b ^ s.c ^ s.d ^ uint64(s.inputLen))
27}
28
29type seaHash struct {
30	a uint64
31	b uint64
32	c uint64
33	d uint64
34
35	inputLen uint64
36}
37
38func NewSeaHash() *seaHash {
39	return &seaHash{
40		a: seed1,
41		b: seed2,
42		c: seed3,
43		d: seed4,
44	}
45}
46
47func (this *seaHash) write(p []byte) {
48	var i int
49	// handle chucks of 8
50	for ; i < len(p)-7; i += 8 {
51		this.update(readInt64(p[i : i+8]))
52	}
53	// handle any remaining bytes
54	if i < len(p) {
55		this.update(readInt64(p[i:]))
56	}
57
58	this.inputLen += uint64(len(p))
59	return
60}
61
62func (this *seaHash) update(x uint64) {
63	a := diffuse(this.a ^ x)
64
65	this.a = this.b
66	this.b = this.c
67	this.c = this.d
68	this.d = a
69}
70
71func diffuse(x uint64) uint64 {
72	x *= pcgRNG
73	a, b := x>>32, x>>60
74	x ^= a >> b
75	x *= pcgRNG
76	return x
77}
78
79// caller to ensure len(b) <= 8
80func readInt64(b []uint8) uint64 {
81	var x uint64
82
83	for i := len(b) - 1; i >= 0; i-- {
84		x <<= 8
85		x |= uint64(b[i])
86	}
87
88	return x
89}
90