-
Notifications
You must be signed in to change notification settings - Fork 26
/
flag.go
160 lines (137 loc) · 4.83 KB
/
flag.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
// 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 (
"io"
)
// An encoded DDSketch comprises multiple contiguous blocks (sequences of
// bytes). Each block is prefixed with a flag that indicates what the block
// contains and how the data is encoded in the block.
//
// A flag is a single byte, which itself contains two parts:
// - the flag type (the 2 least significant bits),
// - the subflag (the 6 most significant bits).
//
// There are four flag types, for:
// - sketch features,
// - index mapping,
// - positive value store,
// - negative value store.
//
// The meaning of the subflag depends on the flag type:
// - for the sketch feature flag type, it indicates what feature is encoded,
// - for the index mapping flag type, it indicates what mapping is encoded and
// how,
// - for the store flag types, it indicates how bins are encoded.
const (
numBitsForType byte = 2
flagTypeMask byte = (1 << numBitsForType) - 1
subFlagMask byte = ^flagTypeMask
)
type Flag struct{ byte }
type FlagType struct{ byte } // mask: 0b00000011
type SubFlag struct{ byte } // mask: 0b11111100
var (
// FLAG TYPES
flagTypeSketchFeatures = FlagType{0b00}
FlagTypeIndexMapping = FlagType{0b10}
FlagTypePositiveStore = FlagType{0b01}
FlagTypeNegativeStore = FlagType{0b11}
// SKETCH FEATURES
// Encodes the count of the zero bin.
// Encoding format:
// - [byte] flag
// - [varfloat64] count of the zero bin
FlagZeroCountVarFloat = NewFlag(flagTypeSketchFeatures, newSubFlag(1))
// Encode the total count.
// Encoding format:
// - [byte] flag
// - [varfloat64] total count
FlagCount = NewFlag(flagTypeSketchFeatures, newSubFlag(0x28))
// Encode the summary statistics.
// Encoding format:
// - [byte] flag
// - [float64LE] summary stat
FlagSum = NewFlag(flagTypeSketchFeatures, newSubFlag(0x21))
FlagMin = NewFlag(flagTypeSketchFeatures, newSubFlag(0x22))
FlagMax = NewFlag(flagTypeSketchFeatures, newSubFlag(0x23))
// INDEX MAPPING
// Encodes log-like index mappings, specifying the base (gamma) and the index offset
// The subflag specifies the interpolation method.
// Encoding format:
// - [byte] flag
// - [float64LE] gamma
// - [float64LE] index offset
FlagIndexMappingBaseLogarithmic = NewFlag(FlagTypeIndexMapping, newSubFlag(0))
FlagIndexMappingBaseLinear = NewFlag(FlagTypeIndexMapping, newSubFlag(1))
FlagIndexMappingBaseQuadratic = NewFlag(FlagTypeIndexMapping, newSubFlag(2))
FlagIndexMappingBaseCubic = NewFlag(FlagTypeIndexMapping, newSubFlag(3))
FlagIndexMappingBaseQuartic = NewFlag(FlagTypeIndexMapping, newSubFlag(4))
// BINS
// Encodes N bins, each one with its index and its count.
// Indexes are delta-encoded.
// Encoding format:
// - [byte] flag
// - [uvarint64] number of bins N
// - [varint64] index of first bin
// - [varfloat64] count of first bin
// - [varint64] difference between the index of the second bin and the index
// of the first bin
// - [varfloat64] count of second bin
// - ...
// - [varint64] difference between the index of the N-th bin and the index
// of the (N-1)-th bin
// - [varfloat64] count of N-th bin
BinEncodingIndexDeltasAndCounts = newSubFlag(1)
// Encodes N bins whose counts are each equal to 1.
// Indexes are delta-encoded.
// Encoding format:
// - [byte] flag
// - [uvarint64] number of bins N
// - [varint64] index of first bin
// - [varint64] difference between the index of the second bin and the index
// of the first bin
// - ...
// - [varint64] difference between the index of the N-th bin and the index
// of the (N-1)-th bin
BinEncodingIndexDeltas = newSubFlag(2)
// Encodes N contiguous bins, specifiying the count of each one
// Encoding format:
// - [byte] flag
// - [uvarint64] number of bins N
// - [varint64] index of first bin
// - [varint64] difference between two successive indexes
// - [varfloat64] count of first bin
// - [varfloat64] count of second bin
// - ...
// - [varfloat64] count of N-th bin
BinEncodingContiguousCounts = newSubFlag(3)
)
func NewFlag(t FlagType, s SubFlag) Flag {
return Flag{t.byte | s.byte}
}
func (f Flag) Type() FlagType {
return FlagType{f.byte & flagTypeMask}
}
func (f Flag) SubFlag() SubFlag {
return SubFlag{f.byte & subFlagMask}
}
func newSubFlag(b byte) SubFlag {
return SubFlag{b << numBitsForType}
}
// EncodeFlag encodes a flag and appends its content to the provided []byte.
func EncodeFlag(b *[]byte, f Flag) {
*b = append(*b, f.byte)
}
// DecodeFlag decodes a flag and updates the provided []byte so that it starts
// immediately after the encoded flag.
func DecodeFlag(b *[]byte) (Flag, error) {
if len(*b) == 0 {
return Flag{}, io.EOF
}
flag := Flag{(*b)[0]}
*b = (*b)[1:]
return flag, nil
}