func ZigZagEncode(x int64) uint64 {
	return uint64(uint64(x<<1) ^ uint64((int64(x) >> 63)))
}
ZigZagEncode converts a int64 to a uint64 by zig zagging negative and positive values
across even and odd numbers.  Eg. [0,-1,1,-2] becomes [0, 1, 2, 3].
package tsm1
import (
	"encoding/binary"
	"fmt"
	"runtime"
	"time"
	"github.com/influxdata/influxdb/pkg/pool"
	"github.com/influxdata/influxdb/tsdb"
	"github.com/influxdata/influxql"
)
const (
	BlockFloat64 = byte(0)
	BlockInteger = byte(1)
	BlockBoolean = byte(2)
	BlockString = byte(3)
	BlockUnsigned = byte(4)
	encodedBlockHeaderSize = 1
)
func init() {
	vals := make([]interface{}, 0, runtime.NumCPU())
	for _, p := range []*pool.Generic{
		timeEncoderPool, timeDecoderPool,
		integerEncoderPool, integerDecoderPool,
		floatDecoderPool, floatDecoderPool,
		stringEncoderPool, stringEncoderPool,
		booleanEncoderPool, booleanDecoderPool,
	} {
		vals = vals[:0]
		for i := 0; i < runtime.NumCPU(); i++ {
			v := p.Get(tsdb.DefaultMaxPointsPerBlock)
			vals = append(vals, v)
		}
		for _, v := range vals {
			p.Put(v)
		}
	}
}
var (
	timeEncoderPool = pool.NewGeneric(runtime.NumCPU(), func(sz int) interface{} {
		return NewTimeEncoder(sz)
	})
	integerEncoderPool = pool.NewGeneric(runtime.NumCPU(), func(sz int) interface{} {
		return NewIntegerEncoder(sz)
	})
	floatEncoderPool = pool.NewGeneric(runtime.NumCPU(), func(sz int) interface{} {
		return NewFloatEncoder()
	})
	stringEncoderPool = pool.NewGeneric(runtime.NumCPU(), func(sz int) interface{} {
		return NewStringEncoder(sz)
	})
	booleanEncoderPool = pool.NewGeneric(runtime.NumCPU(), func(sz int) interface{} {
		return NewBooleanEncoder(sz)
	})
	timeDecoderPool = pool.NewGeneric(runtime.NumCPU(), func(sz int) interface{} {
		return &TimeDecoder{}
	})
	integerDecoderPool = pool.NewGeneric(runtime.NumCPU(), func(sz int) interface{} {
		return &IntegerDecoder{}
	})
	floatDecoderPool = pool.NewGeneric(runtime.NumCPU(), func(sz int) interface{} {
		return &FloatDecoder{}
	})
	stringDecoderPool = pool.NewGeneric(runtime.NumCPU(), func(sz int) interface{} {
		return &StringDecoder{}
	})
	booleanDecoderPool = pool.NewGeneric(runtime.NumCPU(), func(sz int) interface{} {
		return &BooleanDecoder{}
	})
)
type Value interface {
	UnixNano() int64
	Value() interface{}
	Size() int
	String() string
	internalOnly()
}
func NewValue(t int64, value interface{}) Value {
	switch v := value.(type) {
	case int64:
		return IntegerValue{unixnano: t, value: v}
	case uint64:
		return UnsignedValue{unixnano: t, value: v}
	case float64:
		return FloatValue{unixnano: t, value: v}
	case bool:
		return BooleanValue{unixnano: t, value: v}
	case string:
		return StringValue{unixnano: t, value: v}
	}
	return EmptyValue{}
}
func NewIntegerValue(t int64, v int64) Value {
	return IntegerValue{unixnano: t, value: v}
}
func NewUnsignedValue(t int64, v uint64) Value {
	return UnsignedValue{unixnano: t, value: v}
}
func NewFloatValue(t int64, v float64) Value {
	return FloatValue{unixnano: t, value: v}
}
func NewBooleanValue(t int64, v bool) Value {
	return BooleanValue{unixnano: t, value: v}
}
func NewStringValue(t int64, v string) Value {
	return StringValue{unixnano: t, value: v}
}
type EmptyValue struct{}
func (e EmptyValue) UnixNano() int64 { return tsdb.EOF }
func (e EmptyValue) Value() interface{} { return nil }
func (e EmptyValue) Size() int { return 0 }
func (e EmptyValue) String() string { return "" }
func (_ EmptyValue) internalOnly()    {}
func (_ StringValue) internalOnly()   {}
func (_ IntegerValue) internalOnly()  {}
func (_ UnsignedValue) internalOnly() {}
func (_ BooleanValue) internalOnly()  {}
func (_ FloatValue) internalOnly()    {}
func (a Values) Encode(buf []byte) ([]byte, error) {
	if len(a) == 0 {
		panic("unable to encode block type")
	}
	switch a[0].(type) {
	case FloatValue:
		return encodeFloatBlock(buf, a)
	case IntegerValue:
		return encodeIntegerBlock(buf, a)
	case UnsignedValue:
		return encodeUnsignedBlock(buf, a)
	case BooleanValue:
		return encodeBooleanBlock(buf, a)
	case StringValue:
		return encodeStringBlock(buf, a)
	}
	return nil, fmt.Errorf("unsupported value type %T", a[0])
}
func (a Values) InfluxQLType() (influxql.DataType, error) {
	if len(a) == 0 {
		return influxql.Unknown, fmt.Errorf("no values to infer type")
	}
	switch a[0].(type) {
	case FloatValue:
		return influxql.Float, nil
	case IntegerValue:
		return influxql.Integer, nil
	case UnsignedValue:
		return influxql.Unsigned, nil
	case BooleanValue:
		return influxql.Boolean, nil
	case StringValue:
		return influxql.String, nil
	}
	return influxql.Unknown, fmt.Errorf("unsupported value type %T", a[0])
}
func BlockType(block []byte) (byte, error) {
	blockType := block[0]
	switch blockType {
	case BlockFloat64, BlockInteger, BlockUnsigned, BlockBoolean, BlockString:
		return blockType, nil
	default:
		return 0, fmt.Errorf("unknown block type: %d", blockType)
	}
}
func BlockCount(block []byte) int {
	if len(block) <= encodedBlockHeaderSize {
		panic(fmt.Sprintf("count of short block: got %v, exp %v", len(block), encodedBlockHeaderSize))
	}
	tb, _, err := unpackBlock(block[1:])
	if err != nil {
		panic(fmt.Sprintf("BlockCount: error unpacking block: %s", err.Error()))
	}
	return CountTimestamps(tb)
}
func DecodeBlock(block []byte, vals []Value) ([]Value, error) {
	if len(block) <= encodedBlockHeaderSize {
		panic(fmt.Sprintf("decode of short block: got %v, exp %v", len(block), encodedBlockHeaderSize))
	}
	blockType, err := BlockType(block)
	if err != nil {
		return nil, err
	}
	switch blockType {
	case BlockFloat64:
		var buf []FloatValue
		decoded, err := DecodeFloatBlock(block, &buf)
		if len(vals) < len(decoded) {
			vals = make([]Value, len(decoded))
		}
		for i := range decoded {
			vals[i] = decoded[i]
		}
		return vals[:len(decoded)], err
	case BlockInteger:
		var buf []IntegerValue
		decoded, err := DecodeIntegerBlock(block, &buf)
		if len(vals) < len(decoded) {
			vals = make([]Value, len(decoded))
		}
		for i := range decoded {
			vals[i] = decoded[i]
		}
		return vals[:len(decoded)], err
	case BlockUnsigned:
		var buf []UnsignedValue
		decoded, err := DecodeUnsignedBlock(block, &buf)
		if len(vals) < len(decoded) {
			vals = make([]Value, len(decoded))
		}
		for i := range decoded {
			vals[i] = decoded[i]
		}
		return vals[:len(decoded)], err
	case BlockBoolean:
		var buf []BooleanValue
		decoded, err := DecodeBooleanBlock(block, &buf)
		if len(vals) < len(decoded) {
			vals = make([]Value, len(decoded))
		}
		for i := range decoded {
			vals[i] = decoded[i]
		}
		return vals[:len(decoded)], err
	case BlockString:
		var buf []StringValue
		decoded, err := DecodeStringBlock(block, &buf)
		if len(vals) < len(decoded) {
			vals = make([]Value, len(decoded))
		}
		for i := range decoded {
			vals[i] = decoded[i]
		}
		return vals[:len(decoded)], err
	default:
		panic(fmt.Sprintf("unknown block type: %d", blockType))
	}
}
type FloatValue struct {
	unixnano int64
	value    float64
}
func (v FloatValue) UnixNano() int64 {
	return v.unixnano
}
func (v FloatValue) Value() interface{} {
	return v.value
}
func (v FloatValue) Size() int {
	return 16
}
func (v FloatValue) String() string {
	return fmt.Sprintf("%v %v", time.Unix(0, v.unixnano), v.value)
}
func encodeFloatBlock(buf []byte, values []Value) ([]byte, error) {
	if len(values) == 0 {
		return nil, nil
	}
	venc := getFloatEncoder(len(values))
	tsenc := getTimeEncoder(len(values))
	b, err := encodeFloatBlockUsing(buf, values, tsenc, venc)
	putTimeEncoder(tsenc)
	putFloatEncoder(venc)
	return b, err
}
func encodeFloatBlockUsing(buf []byte, values []Value, tsenc TimeEncoder, venc *FloatEncoder) ([]byte, error) {
	tsenc.Reset()
	venc.Reset()
	for _, v := range values {
		vv := v.(FloatValue)
		tsenc.Write(vv.unixnano)
		venc.Write(vv.value)
	}
	venc.Flush()
	tb, err := tsenc.Bytes()
	if err != nil {
		return nil, err
	}
	vb, err := venc.Bytes()
	if err != nil {
		return nil, err
	}
	return packBlock(buf, BlockFloat64, tb, vb), nil
}
func DecodeFloatBlock(block []byte, a *[]FloatValue) ([]FloatValue, error) {
	blockType := block[0]
	if blockType != BlockFloat64 {
		return nil, fmt.Errorf("invalid block type: exp %d, got %d", BlockFloat64, blockType)
	}
	block = block[1:]
	tb, vb, err := unpackBlock(block)
	if err != nil {
		return nil, err
	}
	sz := CountTimestamps(tb)
	if cap(*a) < sz {
		*a = make([]FloatValue, sz)
	} else {
		*a = (*a)[:sz]
	}
	tdec := timeDecoderPool.Get(0).(*TimeDecoder)
	vdec := floatDecoderPool.Get(0).(*FloatDecoder)
	var i int
	err = func(a []FloatValue) error {
		tdec.Init(tb)
		err = vdec.SetBytes(vb)
		if err != nil {
			return err
		}
		j := 0
		for j < len(a) && tdec.Next() && vdec.Next() {
			a[j] = FloatValue{unixnano: tdec.Read(), value: vdec.Values()}
			j++
		}
		i = j
		err = tdec.Error()
		if err != nil {
			return err
		}
		return vdec.Error()
	}(*a)
	timeDecoderPool.Put(tdec)
	floatDecoderPool.Put(vdec)
	return (*a)[:i], err
}
type BooleanValue struct {
	unixnano int64
	value    bool
}
func (v BooleanValue) Size() int {
	return 9
}
func (v BooleanValue) UnixNano() int64 {
	return v.unixnano
}
func (v BooleanValue) Value() interface{} {
	return v.value
}
func (v BooleanValue) String() string {
	return fmt.Sprintf("%v %v", time.Unix(0, v.unixnano), v.Value())
}
func encodeBooleanBlock(buf []byte, values []Value) ([]byte, error) {
	if len(values) == 0 {
		return nil, nil
	}
	venc := getBooleanEncoder(len(values))
	tsenc := getTimeEncoder(len(values))
	b, err := encodeBooleanBlockUsing(buf, values, tsenc, venc)
	putTimeEncoder(tsenc)
	putBooleanEncoder(venc)
	return b, err
}
func encodeBooleanBlockUsing(buf []byte, values []Value, tenc TimeEncoder, venc BooleanEncoder) ([]byte, error) {
	tenc.Reset()
	venc.Reset()
	for _, v := range values {
		vv := v.(BooleanValue)
		tenc.Write(vv.unixnano)
		venc.Write(vv.value)
	}
	tb, err := tenc.Bytes()
	if err != nil {
		return nil, err
	}
	vb, err := venc.Bytes()
	if err != nil {
		return nil, err
	}
	return packBlock(buf, BlockBoolean, tb, vb), nil
}
func DecodeBooleanBlock(block []byte, a *[]BooleanValue) ([]BooleanValue, error) {
	blockType := block[0]
	if blockType != BlockBoolean {
		return nil, fmt.Errorf("invalid block type: exp %d, got %d", BlockBoolean, blockType)
	}
	block = block[1:]
	tb, vb, err := unpackBlock(block)
	if err != nil {
		return nil, err
	}
	sz := CountTimestamps(tb)
	if cap(*a) < sz {
		*a = make([]BooleanValue, sz)
	} else {
		*a = (*a)[:sz]
	}
	tdec := timeDecoderPool.Get(0).(*TimeDecoder)
	vdec := booleanDecoderPool.Get(0).(*BooleanDecoder)
	var i int
	err = func(a []BooleanValue) error {
		tdec.Init(tb)
		vdec.SetBytes(vb)
		j := 0
		for j < len(a) && tdec.Next() && vdec.Next() {
			a[j] = BooleanValue{unixnano: tdec.Read(), value: vdec.Read()}
			j++
		}
		i = j
		err = tdec.Error()
		if err != nil {
			return err
		}
		return vdec.Error()
	}(*a)
	timeDecoderPool.Put(tdec)
	booleanDecoderPool.Put(vdec)
	return (*a)[:i], err
}
type IntegerValue struct {
	unixnano int64
	value    int64
}
func (v IntegerValue) Value() interface{} {
	return v.value
}
func (v IntegerValue) UnixNano() int64 {
	return v.unixnano
}
func (v IntegerValue) Size() int {
	return 16
}
func (v IntegerValue) String() string {
	return fmt.Sprintf("%v %v", time.Unix(0, v.unixnano), v.Value())
}
func encodeIntegerBlock(buf []byte, values []Value) ([]byte, error) {
	tenc := getTimeEncoder(len(values))
	venc := getIntegerEncoder(len(values))
	b, err := encodeIntegerBlockUsing(buf, values, tenc, venc)
	putTimeEncoder(tenc)
	putIntegerEncoder(venc)
	return b, err
}
func encodeIntegerBlockUsing(buf []byte, values []Value, tenc TimeEncoder, venc IntegerEncoder) ([]byte, error) {
	tenc.Reset()
	venc.Reset()
	for _, v := range values {
		vv := v.(IntegerValue)
		tenc.Write(vv.unixnano)
		venc.Write(vv.value)
	}
	tb, err := tenc.Bytes()
	if err != nil {
		return nil, err
	}
	vb, err := venc.Bytes()
	if err != nil {
		return nil, err
	}
	return packBlock(buf, BlockInteger, tb, vb), nil
}
func DecodeIntegerBlock(block []byte, a *[]IntegerValue) ([]IntegerValue, error) {
	blockType := block[0]
	if blockType != BlockInteger {
		return nil, fmt.Errorf("invalid block type: exp %d, got %d", BlockInteger, blockType)
	}
	block = block[1:]
	tb, vb, err := unpackBlock(block)
	if err != nil {
		return nil, err
	}
	sz := CountTimestamps(tb)
	if cap(*a) < sz {
		*a = make([]IntegerValue, sz)
	} else {
		*a = (*a)[:sz]
	}
	tdec := timeDecoderPool.Get(0).(*TimeDecoder)
	vdec := integerDecoderPool.Get(0).(*IntegerDecoder)
	var i int
	err = func(a []IntegerValue) error {
		tdec.Init(tb)
		vdec.SetBytes(vb)
		j := 0
		for j < len(a) && tdec.Next() && vdec.Next() {
			a[j] = IntegerValue{unixnano: tdec.Read(), value: vdec.Read()}
			j++
		}
		i = j
		err = tdec.Error()
		if err != nil {
			return err
		}
		return vdec.Error()
	}(*a)
	timeDecoderPool.Put(tdec)
	integerDecoderPool.Put(vdec)
	return (*a)[:i], err
}
type UnsignedValue struct {
	unixnano int64
	value    uint64
}
func (v UnsignedValue) Value() interface{} {
	return v.value
}
func (v UnsignedValue) UnixNano() int64 {
	return v.unixnano
}
func (v UnsignedValue) Size() int {
	return 16
}
func (v UnsignedValue) String() string {
	return fmt.Sprintf("%v %v", time.Unix(0, v.unixnano), v.Value())
}
func encodeUnsignedBlock(buf []byte, values []Value) ([]byte, error) {
	tenc := getTimeEncoder(len(values))
	venc := getUnsignedEncoder(len(values))
	b, err := encodeUnsignedBlockUsing(buf, values, tenc, venc)
	putTimeEncoder(tenc)
	putUnsignedEncoder(venc)
	return b, err
}
func encodeUnsignedBlockUsing(buf []byte, values []Value, tenc TimeEncoder, venc IntegerEncoder) ([]byte, error) {
	tenc.Reset()
	venc.Reset()
	for _, v := range values {
		vv := v.(UnsignedValue)
		tenc.Write(vv.unixnano)
		venc.Write(int64(vv.value))
	}
	tb, err := tenc.Bytes()
	if err != nil {
		return nil, err
	}
	vb, err := venc.Bytes()
	if err != nil {
		return nil, err
	}
	return packBlock(buf, BlockUnsigned, tb, vb), nil
}
func DecodeUnsignedBlock(block []byte, a *[]UnsignedValue) ([]UnsignedValue, error) {
	blockType := block[0]
	if blockType != BlockUnsigned {
		return nil, fmt.Errorf("invalid block type: exp %d, got %d", BlockUnsigned, blockType)
	}
	block = block[1:]
	tb, vb, err := unpackBlock(block)
	if err != nil {
		return nil, err
	}
	sz := CountTimestamps(tb)
	if cap(*a) < sz {
		*a = make([]UnsignedValue, sz)
	} else {
		*a = (*a)[:sz]
	}
	tdec := timeDecoderPool.Get(0).(*TimeDecoder)
	vdec := integerDecoderPool.Get(0).(*IntegerDecoder)
	var i int
	err = func(a []UnsignedValue) error {
		tdec.Init(tb)
		vdec.SetBytes(vb)
		j := 0
		for j < len(a) && tdec.Next() && vdec.Next() {
			a[j] = UnsignedValue{unixnano: tdec.Read(), value: uint64(vdec.Read())}
			j++
		}
		i = j
		err = tdec.Error()
		if err != nil {
			return err
		}
		return vdec.Error()
	}(*a)
	timeDecoderPool.Put(tdec)
	integerDecoderPool.Put(vdec)
	return (*a)[:i], err
}
type StringValue struct {
	unixnano int64
	value    string
}
func (v StringValue) Value() interface{} {
	return v.value
}
func (v StringValue) UnixNano() int64 {
	return v.unixnano
}
func (v StringValue) Size() int {
	return 8 + len(v.value)
}
func (v StringValue) String() string {
	return fmt.Sprintf("%v %v", time.Unix(0, v.unixnano), v.Value())
}
func encodeStringBlock(buf []byte, values []Value) ([]byte, error) {
	tenc := getTimeEncoder(len(values))
	venc := getStringEncoder(len(values) * len(values[0].(StringValue).value))
	b, err := encodeStringBlockUsing(buf, values, tenc, venc)
	putTimeEncoder(tenc)
	putStringEncoder(venc)
	return b, err
}
func encodeStringBlockUsing(buf []byte, values []Value, tenc TimeEncoder, venc StringEncoder) ([]byte, error) {
	tenc.Reset()
	venc.Reset()
	for _, v := range values {
		vv := v.(StringValue)
		tenc.Write(vv.unixnano)
		venc.Write(vv.value)
	}
	tb, err := tenc.Bytes()
	if err != nil {
		return nil, err
	}
	vb, err := venc.Bytes()
	if err != nil {
		return nil, err
	}
	return packBlock(buf, BlockString, tb, vb), nil
}
func DecodeStringBlock(block []byte, a *[]StringValue) ([]StringValue, error) {
	blockType := block[0]
	if blockType != BlockString {
		return nil, fmt.Errorf("invalid block type: exp %d, got %d", BlockString, blockType)
	}
	block = block[1:]
	tb, vb, err := unpackBlock(block)
	if err != nil {
		return nil, err
	}
	sz := CountTimestamps(tb)
	if cap(*a) < sz {
		*a = make([]StringValue, sz)
	} else {
		*a = (*a)[:sz]
	}
	tdec := timeDecoderPool.Get(0).(*TimeDecoder)
	vdec := stringDecoderPool.Get(0).(*StringDecoder)
	var i int
	err = func(a []StringValue) error {
		tdec.Init(tb)
		err = vdec.SetBytes(vb)
		if err != nil {
			return err
		}
		j := 0
		for j < len(a) && tdec.Next() && vdec.Next() {
			a[j] = StringValue{unixnano: tdec.Read(), value: vdec.Read()}
			j++
		}
		i = j
		err = tdec.Error()
		if err != nil {
			return err
		}
		return vdec.Error()
	}(*a)
	timeDecoderPool.Put(tdec)
	stringDecoderPool.Put(vdec)
	return (*a)[:i], err
}
func packBlock(buf []byte, typ byte, ts []byte, values []byte) []byte {
	sz := 1 + binary.MaxVarintLen64 + len(ts) + len(values)
	if cap(buf) < sz {
		buf = make([]byte, sz)
	}
	b := buf[:sz]
	b[0] = typ
	i := binary.PutUvarint(b[1:1+binary.MaxVarintLen64], uint64(len(ts)))
	i += 1
	copy(b[i:], ts)
	copy(b[i+len(ts):], values)
	return b[:i+len(ts)+len(values)]
}
func unpackBlock(buf []byte) (ts, values []byte, err error) {
	tsLen, i := binary.Uvarint(buf)
	if i <= 0 {
		err = fmt.Errorf("unpackBlock: unable to read timestamp block length")
		return
	}
	tsIdx := int(i) + int(tsLen)
	if tsIdx > len(buf) {
		err = fmt.Errorf("unpackBlock: not enough data for timestamp")
		return
	}
	ts = buf[int(i):tsIdx]
	values = buf[tsIdx:]
	return
}