-
Notifications
You must be signed in to change notification settings - Fork 7
/
bloom2048b.go
84 lines (74 loc) · 2.21 KB
/
bloom2048b.go
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// Copyright (c) 2019 IoTeX
// This is an alpha (internal) release and is not suitable for production. This source code is provided 'as is' and no
// warranties are given as to title or non-infringement, merchantability or fitness for purpose and, to the extent
// permitted by law, all liability for your use of the code is disclaimed. This source code is governed by Apache
// License 2.0 that can be found in the LICENSE file.
package bloom
import (
"github.com/iotexproject/go-pkgs/hash"
"github.com/pkg/errors"
)
type (
// bloom2048b implements a 2048-bit bloom filter
bloom2048b struct {
array [256]byte
numHash uint // number of hash function
}
)
// newBloom2048 returns a 2048-bit bloom filter
func newBloom2048(h uint) (BloomFilter, error) {
if h == 0 || h > 16 {
return nil, errors.New("expecting 0 < number of hash functions <= 16")
}
return &bloom2048b{numHash: h}, nil
}
// bloom2048FromBytes constructs a 2048-bit bloom filter from bytes
func bloom2048FromBytes(b []byte, h uint) (BloomFilter, error) {
if h == 0 || h > 16 {
return nil, errors.New("expecting 0 < number of hash functions <= 16")
}
if len(b) != 256 {
return nil, errors.Errorf("wrong length %d, expecting 256", len(b))
}
f := bloom2048b{numHash: h}
copy(f.array[:], b[:])
return &f, nil
}
// Add 32-byte key into bloom filter
func (f *bloom2048b) Add(key []byte) {
if key == nil {
return
}
h := hash.Hash256b(key)
// each 2-byte pair used as output of hash function
for i := uint(0); i < f.numHash; i++ {
f.setBit(h[2*i], h[2*i+1])
}
}
// Exist checks if a key is in bloom filter
func (f *bloom2048b) Exist(key []byte) bool {
if key == nil {
return false
}
h := hash.Hash256b(key)
for i := uint(0); i < f.numHash; i++ {
if !f.chkBit(h[2*i], h[2*i+1]) {
return false
}
}
return true
}
// Bytes returns the bytes of bloom filter
func (f *bloom2048b) Bytes() []byte {
return f.array[:]
}
func (f *bloom2048b) setBit(bytePos, bitPos byte) {
// bytePos indicates which byte to set
// lower 3-bit of bitPos indicates which bit to set
mask := 1 << (bitPos & 7)
f.array[bytePos] |= byte(mask)
}
func (f *bloom2048b) chkBit(bytePos, bitPos byte) bool {
mask := 1 << (bitPos & 7)
return (f.array[bytePos] & byte(mask)) != 0
}