-
Notifications
You must be signed in to change notification settings - Fork 5
/
util.go
130 lines (108 loc) · 2.9 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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
package hamt
// adapted from https://github.com/ipfs/go-unixfs/blob/master/hamt/util.go
import (
"fmt"
"math/bits"
"github.com/Stebalien/go-bitfield"
"github.com/ipfs/go-unixfsnode/data"
dagpb "github.com/ipld/go-codec-dagpb"
"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 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, ErrHAMTTooDeep
}
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
}
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)
}
out := int(mkmask(leftb) & curb)
out <<= uint(i - leftb)
hb.consumed += leftb
out += hb.next(i - leftb)
return out
}
func validateHAMTData(nd data.UnixFSData) error {
if nd.FieldDataType().Int() != data.Data_HAMTShard {
return data.ErrWrongNodeType{Expected: data.Data_HAMTShard, Actual: nd.FieldDataType().Int()}
}
if !nd.FieldHashType().Exists() || uint64(nd.FieldHashType().Must().Int()) != HashMurmur3 {
return ErrInvalidHashType
}
if !nd.FieldData().Exists() {
return ErrNoDataField
}
if !nd.FieldFanout().Exists() {
return ErrNoFanoutField
}
if err := checkLogTwo(int(nd.FieldFanout().Must().Int())); err != nil {
return err
}
return nil
}
func log2Size(nd data.UnixFSData) int {
return bits.TrailingZeros(uint(nd.FieldFanout().Must().Int()))
}
func maxPadLength(nd data.UnixFSData) int {
return len(fmt.Sprintf("%X", nd.FieldFanout().Must().Int()-1))
}
func bitField(nd data.UnixFSData) bitfield.Bitfield {
bf := bitfield.NewBitfield(int(nd.FieldFanout().Must().Int()))
bf.SetBytes(nd.FieldData().Must().Bytes())
return bf
}
func checkLogTwo(v int) error {
if v <= 0 {
return ErrHAMTSizeInvalid
}
lg2 := bits.TrailingZeros(uint(v))
if 1<<uint(lg2) != v {
return ErrHAMTSizeInvalid
}
return nil
}
func hash(val []byte) []byte {
h := murmur3.New64()
h.Write(val)
return h.Sum(nil)
}
func isValueLink(pbLink dagpb.PBLink, maxPadLen int) (bool, error) {
if !pbLink.FieldName().Exists() {
return false, ErrMissingLinkName
}
name := pbLink.FieldName().Must().String()
if len(name) < maxPadLen {
return false, ErrInvalidLinkName{name}
}
if len(name) == maxPadLen {
return false, nil
}
return true, nil
}
func MatchKey(pbLink dagpb.PBLink, key string, maxPadLen int) bool {
return pbLink.FieldName().Must().String()[maxPadLen:] == key
}