-
Notifications
You must be signed in to change notification settings - Fork 6
/
marshal.go
210 lines (190 loc) · 5.13 KB
/
marshal.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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
package dagpb
import (
"io"
math_bits "math/bits"
"sort"
"github.com/ipfs/go-cid"
ipld "github.com/ipld/go-ipld-prime"
cidlink "github.com/ipld/go-ipld-prime/linking/cid"
"golang.org/x/xerrors"
)
type pbLink struct {
hash cid.Cid
name string
hasName bool
tsize uint64
hasTsize bool
}
// Marshal provides an IPLD codec encode interface for DAG-PB data. Provide a
// conforming Node and a destination for bytes to marshal a DAG-PB IPLD Node.
// The Node must strictly conform to the DAG-PB schema
// (https://github.com/ipld/specs/blob/master/block-layer/codecs/dag-pb.md).
// For safest use, build Nodes using the Type.PBNode type.
func Marshal(inNode ipld.Node, out io.Writer) error {
// Wrap in a typed node for some basic schema form checking
builder := Type.PBNode.NewBuilder()
if err := builder.AssignNode(inNode); err != nil {
return err
}
node := builder.Build()
links, err := node.LookupByString("Links")
if err != nil {
return err
}
if links.Length() > 0 {
// collect links into a slice so we can properly sort for encoding
pbLinks := make([]pbLink, links.Length())
linksIter := links.ListIterator()
for !linksIter.Done() {
ii, link, err := linksIter.Next()
if err != nil {
return err
}
{ // Hash (required)
d, err := link.LookupByString("Hash")
if err != nil {
return err
}
l, err := d.AsLink()
if err != nil {
return err
}
if err != nil {
return err
}
cl, ok := l.(cidlink.Link)
if !ok {
// this _should_ be taken care of by the Typed conversion above with
// "missing required fields: Hash"
return xerrors.Errorf("invalid DAG-PB form (link must have a Hash)")
}
pbLinks[ii].hash = cl.Cid
}
{ // Name (optional)
nameNode, err := link.LookupByString("Name")
if err != nil {
return err
}
if !nameNode.IsAbsent() {
name, err := nameNode.AsString()
if err != nil {
return err
}
pbLinks[ii].name = name
pbLinks[ii].hasName = true
}
}
{ // Tsize (optional)
tsizeNode, err := link.LookupByString("Tsize")
if err != nil {
return err
}
if !tsizeNode.IsAbsent() {
tsize, err := tsizeNode.AsInt()
if err != nil {
return err
}
if tsize < 0 {
return xerrors.Errorf("Link has negative Tsize value [%v]", tsize)
}
utsize := uint64(tsize)
pbLinks[ii].tsize = utsize
pbLinks[ii].hasTsize = true
}
}
} // for
// links must be strictly sorted by Name before encoding, leaving stable
// ordering where the names are the same (or absent)
sortLinks(pbLinks)
for _, link := range pbLinks {
size := link.encodedSize()
chunk := make([]byte, size+sizeOfVarint(uint64(size))+1)
chunk[0] = 0x12 // field & wire type for Links
offset := encodeVarint(chunk, 1, uint64(size))
wrote, err := link.marshal(chunk, offset)
if err != nil {
return err
}
if wrote != size {
return xerrors.Errorf("bad PBLink marshal, wrote wrong number of bytes")
}
out.Write(chunk)
}
} // if links
// Data (optional)
data, err := node.LookupByString("Data")
if err != nil {
return err
}
if !data.IsAbsent() {
byts, err := data.AsBytes()
if err != nil {
return err
}
size := uint64(len(byts))
lead := make([]byte, sizeOfVarint(size)+1)
lead[0] = 0xa // field and wireType for Data
encodeVarint(lead, 1, size)
out.Write(lead)
out.Write(byts)
}
return nil
}
// predict the byte size of the encoded Link
func (link pbLink) encodedSize() (n int) {
l := link.hash.ByteLen()
n += 1 + l + sizeOfVarint(uint64(l))
if link.hasName {
l = len(link.name)
n += 1 + l + sizeOfVarint(uint64(l))
}
if link.hasTsize {
n += 1 + sizeOfVarint(uint64(link.tsize))
}
return n
}
// encode a Link to PB
func (link pbLink) marshal(data []byte, offset int) (int, error) {
base := offset
data[offset] = 0xa // field and wireType for Hash
byts := link.hash.Bytes()
offset = encodeVarint(data, offset+1, uint64(len(byts)))
copy(data[offset:], byts)
offset += len(byts)
if link.hasName {
data[offset] = 0x12 // field and wireType for Name
offset = encodeVarint(data, offset+1, uint64(len(link.name)))
copy(data[offset:], link.name)
offset += len(link.name)
}
if link.hasTsize {
data[offset] = 0x18 // field and wireType for Tsize
offset = encodeVarint(data, offset+1, uint64(link.tsize))
}
return offset - base, nil
}
// predict the size of a varint for PB before creating it
func sizeOfVarint(x uint64) (n int) {
return (math_bits.Len64(x|1) + 6) / 7
}
// encode a varint to a PB chunk
func encodeVarint(data []byte, offset int, v uint64) int {
for v >= 1<<7 {
data[offset] = uint8(v&0x7f | 0x80)
v >>= 7
offset++
}
data[offset] = uint8(v)
return offset + 1
}
// stable sorting of Links using the strict sorting rules
func sortLinks(links []pbLink) {
sort.Stable(pbLinkSlice(links))
}
type pbLinkSlice []pbLink
func (ls pbLinkSlice) Len() int { return len(ls) }
func (ls pbLinkSlice) Swap(a, b int) { ls[a], ls[b] = ls[b], ls[a] }
func (ls pbLinkSlice) Less(a, b int) bool { return pbLinkLess(ls[a], ls[b]) }
func pbLinkLess(a pbLink, b pbLink) bool {
return a.name < b.name
}