-
Notifications
You must be signed in to change notification settings - Fork 26
/
encoding.go
208 lines (188 loc) · 6.17 KB
/
encoding.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
// Unless explicitly stated otherwise all files in this repository are licensed
// under the Apache License 2.0.
// This product includes software developed at Datadog (https://www.datadoghq.com/).
// Copyright 2021 Datadog, Inc.
package encoding
import (
"encoding/binary"
"errors"
"io"
"math"
"math/bits"
)
// Encoding functions append bytes to the provided *[]byte, allowing avoiding
// allocations if the slice initially has a large enough capacity.
// Decoding functions also take *[]byte as input, and when they do not return an
// error, advance the slice so that it starts at the immediate byte after the
// decoded part (or so that it is empty if there is no such byte).
const (
MaxVarLen64 = 9
varfloat64Rotate = 6
)
var uvarint64Sizes = initUvarint64Sizes()
var varfloat64Sizes = initVarfloat64Sizes()
// EncodeUvarint64 serializes 64-bit unsigned integers 7 bits at a time,
// starting with the least significant bits. The most significant bit in each
// output byte is the continuation bit and indicates whether there are
// additional non-zero bits encoded in following bytes. There are at most 9
// output bytes and the last one does not have a continuation bit, allowing for
// it to encode 8 bits (8*7+8 = 64).
func EncodeUvarint64(b *[]byte, v uint64) {
for i := 0; i < MaxVarLen64-1; i++ {
if v < 0x80 {
break
}
*b = append(*b, byte(v)|byte(0x80))
v >>= 7
}
*b = append(*b, byte(v))
}
// DecodeUvarint64 deserializes 64-bit unsigned integers that have been encoded
// using EncodeUvarint64.
func DecodeUvarint64(b *[]byte) (uint64, error) {
x := uint64(0)
s := uint(0)
for i := 0; ; i++ {
if len(*b) <= i {
return 0, io.EOF
}
n := (*b)[i]
if n < 0x80 || i == MaxVarLen64-1 {
*b = (*b)[i+1:]
return x | uint64(n)<<s, nil
}
x |= uint64(n&0x7F) << s
s += 7
}
}
// Uvarint64Size returns the number of bytes that EncodeUvarint64 encodes a
// 64-bit unsigned integer into.
func Uvarint64Size(v uint64) int {
return uvarint64Sizes[bits.LeadingZeros64(v)]
}
func initUvarint64Sizes() [65]int {
var sizes [65]int
b := []byte{}
for i := 0; i <= 64; i++ {
b = b[:0]
EncodeUvarint64(&b, ^uint64(0)>>i)
sizes[i] = len(b)
}
return sizes
}
// EncodeVarint64 serializes 64-bit signed integers using zig-zag encoding,
// which ensures small-scale integers are turned into unsigned integers that
// have leading zeros, whether they are positive or negative, hence allows for
// space-efficient varuint encoding of those values.
func EncodeVarint64(b *[]byte, v int64) {
EncodeUvarint64(b, uint64(v>>(64-1)^(v<<1)))
}
// DecodeVarint64 deserializes 64-bit signed integers that have been encoded
// using EncodeVarint32.
func DecodeVarint64(b *[]byte) (int64, error) {
v, err := DecodeUvarint64(b)
return int64((v >> 1) ^ -(v & 1)), err
}
// Varint64Size returns the number of bytes that EncodeVarint64 encodes a 64-bit
// signed integer into.
func Varint64Size(v int64) int {
return Uvarint64Size(uint64(v>>(64-1) ^ (v << 1)))
}
var errVarint32Overflow = errors.New("varint overflows a 32-bit integer")
// DecodeVarint32 deserializes 32-bit signed integers that have been encoded
// using EncodeVarint64.
func DecodeVarint32(b *[]byte) (int32, error) {
v, err := DecodeVarint64(b)
if err != nil {
return 0, err
}
if v > math.MaxInt32 || v < math.MinInt32 {
return 0, errVarint32Overflow
}
return int32(v), nil
}
// EncodeFloat64LE serializes 64-bit floating-point values, starting with the
// least significant bytes.
func EncodeFloat64LE(b *[]byte, v float64) {
*b = append(*b, make([]byte, 8)...)
binary.LittleEndian.PutUint64((*b)[len(*b)-8:], math.Float64bits(v))
}
// DecodeFloat64LE deserializes 64-bit floating-point values that have been
// encoded with EncodeFloat64LE.
func DecodeFloat64LE(b *[]byte) (float64, error) {
if len(*b) < 8 {
return 0, io.EOF
}
v := math.Float64frombits(binary.LittleEndian.Uint64(*b))
*b = (*b)[8:]
return v, nil
}
// EncodeVarfloat64 serializes 64-bit floating-point values using a method that
// is similar to the varuint encoding and that is space-efficient for
// non-negative integer values. The output takes at most 9 bytes.
// Input values are first shifted as floating-point values (+1), then transmuted
// to integer values, then shifted again as integer values (-Float64bits(1)).
// That is in order to minimize the number of non-zero bits when dealing with
// non-negative integer values.
// After that transformation, any input integer value no greater than 2^53 (the
// largest integer value that can be encoded exactly as a 64-bit floating-point
// value) will have at least 6 leading zero bits. By rotating bits to the left,
// those bits end up at the right of the binary representation.
// The resulting bits are then encoded similarly to the varuint method, but
// starting with the most significant bits.
func EncodeVarfloat64(b *[]byte, v float64) {
x := bits.RotateLeft64(math.Float64bits(v+1)-math.Float64bits(1), varfloat64Rotate)
for i := 0; i < MaxVarLen64-1; i++ {
n := byte(x >> (8*8 - 7))
x <<= 7
if x == 0 {
*b = append(*b, n)
return
}
*b = append(*b, n|byte(0x80))
}
n := byte(x >> (8 * 7))
*b = append(*b, n)
}
// DecodeVarfloat64 deserializes 64-bit floating-point values that have been
// encoded with EncodeVarfloat64.
func DecodeVarfloat64(b *[]byte) (float64, error) {
x := uint64(0)
i := int(0)
s := uint(8*8 - 7)
for {
if len(*b) <= i {
return 0, io.EOF
}
n := (*b)[i]
if i == MaxVarLen64-1 {
x |= uint64(n)
break
}
if n < 0x80 {
x |= uint64(n) << s
break
}
x |= uint64(n&0x7F) << s
i++
s -= 7
}
*b = (*b)[i+1:]
return math.Float64frombits(bits.RotateLeft64(x, -varfloat64Rotate)+math.Float64bits(1)) - 1, nil
}
// Varfloat64Size returns the number of bytes that EncodeVarfloat64 encodes a
// 64-bit floating-point value into.
func Varfloat64Size(v float64) int {
x := bits.RotateLeft64(math.Float64bits(v+1)-math.Float64bits(1), varfloat64Rotate)
return varfloat64Sizes[bits.TrailingZeros64(x)]
}
func initVarfloat64Sizes() [65]int {
var sizes [65]int
b := []byte{}
for i := 0; i <= 64; i++ {
b = b[:0]
EncodeVarfloat64(&b, math.Float64frombits(bits.RotateLeft64(^uint64(0)<<i, -varfloat64Rotate)+math.Float64bits(1))-1)
sizes[i] = len(b)
}
return sizes
}