marshal.go 4.18 KB
Newer Older
Rod Vagg's avatar
Rod Vagg committed
1 2 3 4 5
package dagpb

import (
	"fmt"
	"io"
Rod Vagg's avatar
Rod Vagg committed
6 7
	math_bits "math/bits"
	"sort"
Rod Vagg's avatar
Rod Vagg committed
8

Rod Vagg's avatar
Rod Vagg committed
9
	"github.com/ipfs/go-cid"
Rod Vagg's avatar
Rod Vagg committed
10 11 12 13
	ipld "github.com/ipld/go-ipld-prime"
	cidlink "github.com/ipld/go-ipld-prime/linking/cid"
)

Rod Vagg's avatar
Rod Vagg committed
14 15 16 17 18 19 20 21
type pbLink struct {
	hash     cid.Cid
	name     string
	hasName  bool
	tsize    uint64
	hasTsize bool
}

Rod Vagg's avatar
Rod Vagg committed
22
func Marshal(inNode ipld.Node, out io.Writer) error {
Rod Vagg's avatar
Rod Vagg committed
23
	// Wrap in a typed node for some basic schema form checking
Rod Vagg's avatar
Rod Vagg committed
24 25 26 27 28 29
	builder := Type.PBNode.NewBuilder()
	if err := builder.AssignNode(inNode); err != nil {
		return err
	}
	node := builder.Build()

Rod Vagg's avatar
Rod Vagg committed
30 31 32 33 34 35 36
	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())
Rod Vagg's avatar
Rod Vagg committed
37

Rod Vagg's avatar
Rod Vagg committed
38 39 40
		linksIter := links.ListIterator()
		for !linksIter.Done() {
			ii, link, err := linksIter.Next()
Rod Vagg's avatar
Rod Vagg committed
41
			if err != nil {
Rod Vagg's avatar
Rod Vagg committed
42
				return err
Rod Vagg's avatar
Rod Vagg committed
43 44
			}

Rod Vagg's avatar
Rod Vagg committed
45
			{ // Hash
Rod Vagg's avatar
Rod Vagg committed
46 47
				d, err := link.LookupByString("Hash")
				if err != nil {
Rod Vagg's avatar
Rod Vagg committed
48
					return err
Rod Vagg's avatar
Rod Vagg committed
49
				}
Rod Vagg's avatar
Rod Vagg committed
50 51
				// TODO:
				// 		return 0, fmt.Errorf("invalid DAG-PB form (link must have a Hash)")
Rod Vagg's avatar
Rod Vagg committed
52 53
				l, err := d.AsLink()
				if err != nil {
Rod Vagg's avatar
Rod Vagg committed
54
					return err
Rod Vagg's avatar
Rod Vagg committed
55
				}
Rod Vagg's avatar
Rod Vagg committed
56 57
				if err != nil {
					return err
Rod Vagg's avatar
Rod Vagg committed
58
				}
Rod Vagg's avatar
Rod Vagg committed
59 60 61 62 63
				cl, ok := l.(cidlink.Link)
				if !ok {
					return fmt.Errorf("unexpected Link type [%v]", l)
				}
				pbLinks[ii].hash = cl.Cid
Rod Vagg's avatar
Rod Vagg committed
64 65
			}

Rod Vagg's avatar
Rod Vagg committed
66
			{ // Name
Rod Vagg's avatar
Rod Vagg committed
67 68
				nameNode, err := link.LookupByString("Name")
				if err != nil {
Rod Vagg's avatar
Rod Vagg committed
69
					return err
Rod Vagg's avatar
Rod Vagg committed
70 71 72 73
				}
				if !nameNode.IsAbsent() {
					name, err := nameNode.AsString()
					if err != nil {
Rod Vagg's avatar
Rod Vagg committed
74
						return err
Rod Vagg's avatar
Rod Vagg committed
75
					}
Rod Vagg's avatar
Rod Vagg committed
76 77
					pbLinks[ii].name = name
					pbLinks[ii].hasName = true
Rod Vagg's avatar
Rod Vagg committed
78 79 80
				}
			}

Rod Vagg's avatar
Rod Vagg committed
81
			{ // Tsize
Rod Vagg's avatar
Rod Vagg committed
82 83
				tsizeNode, err := link.LookupByString("Tsize")
				if err != nil {
Rod Vagg's avatar
Rod Vagg committed
84
					return err
Rod Vagg's avatar
Rod Vagg committed
85 86 87 88
				}
				if !tsizeNode.IsAbsent() {
					tsize, err := tsizeNode.AsInt()
					if err != nil {
Rod Vagg's avatar
Rod Vagg committed
89
						return err
Rod Vagg's avatar
Rod Vagg committed
90 91
					}
					if tsize < 0 {
Rod Vagg's avatar
Rod Vagg committed
92
						return fmt.Errorf("Link has negative Tsize value [%v]", tsize)
Rod Vagg's avatar
Rod Vagg committed
93
					}
Rod Vagg's avatar
Rod Vagg committed
94 95 96
					utsize := uint64(tsize)
					pbLinks[ii].tsize = utsize
					pbLinks[ii].hasTsize = true
Rod Vagg's avatar
Rod Vagg committed
97 98
				}
			}
Rod Vagg's avatar
Rod Vagg committed
99 100 101 102 103 104 105 106 107 108 109
		} // for

		sortLinks(pbLinks)
		for _, link := range pbLinks {
			size := link.encodedSize()
			chunk := make([]byte, size+sizeOfVarint(uint64(size))+1)
			chunk[0] = 0x12
			offset := encodeVarint(chunk, 1, uint64(size))
			wrote, err := link.marshal(chunk, offset)
			if err != nil {
				return err
Rod Vagg's avatar
Rod Vagg committed
110
			}
Rod Vagg's avatar
Rod Vagg committed
111 112
			if wrote != size {
				return fmt.Errorf("bad PBLink marshal, wrote wrong number of bytes")
Rod Vagg's avatar
Rod Vagg committed
113
			}
Rod Vagg's avatar
Rod Vagg committed
114 115 116 117 118 119 120 121 122 123 124 125
			out.Write(chunk)
		}
	} // if links

	data, err := node.LookupByString("Data")
	if err != nil {
		return err
	}
	if !data.IsAbsent() {
		byts, err := data.AsBytes()
		if err != nil {
			return err
Rod Vagg's avatar
Rod Vagg committed
126
		}
Rod Vagg's avatar
Rod Vagg committed
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
		size := uint64(len(byts))
		lead := make([]byte, sizeOfVarint(size)+1)
		lead[0] = 0xa
		encodeVarint(lead, 1, size)
		out.Write(lead)
		out.Write(byts)
	}

	return nil
}

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
}

func (link pbLink) marshal(data []byte, offset int) (int, error) {
	base := offset
	data[offset] = 0xa
	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
		offset = encodeVarint(data, offset+1, uint64(len(link.name)))
		copy(data[offset:], link.name)
		offset += len(link.name)
Rod Vagg's avatar
Rod Vagg committed
163
	}
Rod Vagg's avatar
Rod Vagg committed
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
	if link.hasTsize {
		data[offset] = 0x18
		offset = encodeVarint(data, offset+1, uint64(link.tsize))
	}
	return offset - base, nil
}

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
}

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
}
Rod Vagg's avatar
Rod Vagg committed
194

Rod Vagg's avatar
Rod Vagg committed
195 196
func sizeOfVarint(x uint64) (n int) {
	return (math_bits.Len64(x|1) + 6) / 7
Rod Vagg's avatar
Rod Vagg committed
197
}