1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
package cuckoofilter
import (
"encoding/binary"
"hash/fnv"
"sync"
"github.com/leemcloughlin/gofarmhash"
)
var hashera = fnv.New64()
var hlock sync.Mutex
func getAltIndex(fp fingerprint, i uint, numBuckets uint) uint {
bytes := make([]byte, 64, 64)
for i, b := range fp {
bytes[i] = b
}
hash := binary.LittleEndian.Uint64(bytes)
return uint(uint64(i)^(hash*0x5bd1e995)) % numBuckets
}
func getFingerprint(data []byte) fingerprint {
hlock.Lock()
defer hlock.Unlock()
hashera.Reset()
hashera.Write(data)
hash := hashera.Sum(nil)
fp := fingerprint{}
for i := 0; i < fingerprintSize; i++ {
fp[i] = hash[i]
}
if fp == nullFp {
fp[0] += 7
}
return fp
}
// getIndicesAndFingerprint returns the 2 bucket indices and fingerprint to be used
func getIndicesAndFingerprint(data []byte, numBuckets uint) (uint, uint, fingerprint) {
hash := farmhash.Hash64(data)
f := getFingerprint(data)
i1 := uint(hash) % numBuckets
i2 := getAltIndex(f, i1, numBuckets)
return i1, i2, f
}
func getNextPow2(n uint64) uint {
n--
n |= n >> 1
n |= n >> 2
n |= n >> 4
n |= n >> 8
n |= n >> 16
n |= n >> 32
n++
return uint(n)
}
|
