-
Notifications
You must be signed in to change notification settings - Fork 0
/
util.go
80 lines (68 loc) · 1.76 KB
/
util.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
package hamt
import (
"fmt"
"math/bits"
"github.com/gocnpan/boxo/ipld/unixfs/internal"
"github.com/spaolacci/murmur3"
)
// hashBits is a helper that allows the reading of the 'next n bits' as an integer.
type hashBits struct {
b []byte
consumed int
}
func newHashBits(val string) *hashBits {
return &hashBits{b: internal.HAMTHashFunction([]byte(val))}
}
func newConsumedHashBits(val string, consumed int) *hashBits {
hv := &hashBits{b: internal.HAMTHashFunction([]byte(val))}
hv.consumed = consumed
return hv
}
func mkmask(n int) byte {
return (1 << uint(n)) - 1
}
// Next returns the next 'i' bits of the hashBits value as an integer, or an
// error if there aren't enough bits.
func (hb *hashBits) Next(i int) (int, error) {
if hb.consumed+i > len(hb.b)*8 {
return 0, fmt.Errorf("sharded directory too deep")
}
return hb.next(i), nil
}
func (hb *hashBits) next(i int) int {
curbi := hb.consumed / 8
leftb := 8 - (hb.consumed % 8)
curb := hb.b[curbi]
if i == leftb {
out := int(mkmask(i) & curb)
hb.consumed += i
return out
} else if i < leftb {
a := curb & mkmask(leftb) // mask out the high bits we don't want
b := a & ^mkmask(leftb-i) // mask out the low bits we don't want
c := b >> uint(leftb-i) // shift whats left down
hb.consumed += i
return int(c)
} else {
out := int(mkmask(leftb) & curb)
out <<= uint(i - leftb)
hb.consumed += leftb
out += hb.next(i - leftb)
return out
}
}
func Logtwo(v int) (int, error) {
if v <= 0 {
return 0, fmt.Errorf("hamt size should be a power of two")
}
lg2 := bits.TrailingZeros(uint(v))
if 1<<uint(lg2) != v {
return 0, fmt.Errorf("hamt size should be a power of two")
}
return lg2, nil
}
func murmur3Hash(val []byte) []byte {
h := murmur3.New64()
h.Write(val)
return h.Sum(nil)
}