native/proto/flag.go

// Copyright 2021 Datadog, Inc.

// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package proto

import (
	"io"
)

// An encoded DD 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
}