binary_util.go

// Copyright 2015 The Vanadium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package vom

import (
	"math"
	"reflect"
	"unsafe"

	"v.io/v23/vdl"
	"v.io/v23/verror"
)

// Binary encoding and decoding routines.

const pkgPath = "v.io/v23/vom"

var (
	errInvalid                = verror.Register(pkgPath+".errInvalid", verror.NoRetry, "{1:}{2:} vom: invalid encoding{:_}")
	errInvalidLenOrControl    = verror.Register(pkgPath+".errInvalidLenOrControl", verror.NoRetry, "{1:}{2:} vom: invalid len or control byte {3}{:_}")
	errMsgLen                 = verror.Register(pkgPath+".errMsgLen", verror.NoRetry, "{1:}{2:} vom: message larger than {3} bytes{:_}")
	errUintOverflow           = verror.Register(pkgPath+".errUintOverflow", verror.NoRetry, "{1:}{2:} vom: scalar larger than 8 bytes{:_}")
	errBadControlCode         = verror.Register(pkgPath+".errBadControlCode", verror.NoRetry, "{1:}{2:} invalid control code{:_}")
	errBadVersionByte         = verror.Register(pkgPath+".errBadVersionByte", verror.NoRetry, "{1:}{2:} bad version byte {3}")
	errEndedBeforeVersionByte = verror.Register(pkgPath+".errEndedBeforeVersionByte", verror.NoRetry, "{1:}{2:} ended before version byte received {:_}")
)

const (
	uint64Size          = 8
	maxEncodedUintBytes = uint64Size + 1 // +1 for length byte
	maxBinaryMsgLen     = 1 << 30        // 1GiB limit to each message
)

// lenUint retuns the number of bytes used to represent the provided
// uint value
func lenUint(v uint64) int {
	switch {
	case v <= 0x7f:
		return 1
	case v <= 0xff:
		return 2
	case v <= 0xffff:
		return 3
	case v <= 0xffffff:
		return 4
	case v <= 0xffffffff:
		return 5
	case v <= 0xffffffffff:
		return 6
	case v <= 0xffffffffffff:
		return 7
	case v <= 0xffffffffffffff:
		return 8
	default:
		return 9
	}
}

func binaryEncodeControl(buf *encbuf, v byte) {
	if v < 0x80 || v > 0xef {
		panic(verror.New(errBadControlCode, nil, v))
	}
	buf.WriteOneByte(v)
}

// binaryDecodeControlOnly only decodes and advances the read position if the
// next byte is a control byte.  Returns an error if the control byte doesn't
// match want.
func binaryDecodeControlOnly(buf *decbuf, want byte) (bool, error) {
	if !buf.IsAvailable(1) {
		if err := buf.Fill(1); err != nil {
			return false, err
		}
	}
	ctrl := buf.PeekAvailableByte()
	if ctrl < 0x80 || ctrl > 0xef {
		return false, nil // not a control byte
	}
	if ctrl != want {
		return false, verror.New(errBadControlCode, nil, ctrl)
	}
	buf.SkipAvailable(1)
	return true, nil
}

// binaryPeekControl returns the next byte as a control byte, or 0 if it is not
// a control byte.  Doesn't advance the read position.
func binaryPeekControl(buf *decbuf) (byte, error) {
	if !buf.IsAvailable(1) {
		if err := buf.Fill(1); err != nil {
			return 0, err
		}
	}
	ctrl := buf.PeekAvailableByte()
	if ctrl < 0x80 || ctrl > 0xef {
		return 0, nil
	}
	return ctrl, nil
}

// Bools are encoded as a byte where 0 = false and anything else is true.
func binaryEncodeBool(buf *encbuf, v bool) {
	if v {
		buf.WriteOneByte(1)
	} else {
		buf.WriteOneByte(0)
	}
}

func binaryDecodeBool(buf *decbuf) (bool, error) {
	if !buf.IsAvailable(1) {
		if err := buf.Fill(1); err != nil {
			return false, err
		}
	}
	value := buf.ReadAvailableByte()
	if value > 1 {
		return false, verror.New(errInvalid, nil) // TODO: better error
	}
	return value != 0, nil
}

// Unsigned integers are the basis for all other primitive values.  This is a
// two-state encoding.  If the number is less than 128 (0 through 0x7f), its
// value is written directly.  Otherwise the value is written in big-endian byte
// order preceded by the negated byte length.
func binaryEncodeUint(buf *encbuf, v uint64) {
	switch {
	case v <= 0x7f:
		buf.Grow(1)[0] = byte(v)
	case v <= 0xff:
		buf := buf.Grow(2)
		buf[0] = 0xff
		buf[1] = byte(v)
	case v <= 0xffff:
		buf := buf.Grow(3)
		buf[0] = 0xfe
		buf[1] = byte(v >> 8)
		buf[2] = byte(v)
	case v <= 0xffffff:
		buf := buf.Grow(4)
		buf[0] = 0xfd
		buf[1] = byte(v >> 16)
		buf[2] = byte(v >> 8)
		buf[3] = byte(v)
	case v <= 0xffffffff:
		buf := buf.Grow(5)
		buf[0] = 0xfc
		buf[1] = byte(v >> 24)
		buf[2] = byte(v >> 16)
		buf[3] = byte(v >> 8)
		buf[4] = byte(v)
	case v <= 0xffffffffff:
		buf := buf.Grow(6)
		buf[0] = 0xfb
		buf[1] = byte(v >> 32)
		buf[2] = byte(v >> 24)
		buf[3] = byte(v >> 16)
		buf[4] = byte(v >> 8)
		buf[5] = byte(v)
	case v <= 0xffffffffffff:
		buf := buf.Grow(7)
		buf[0] = 0xfa
		buf[1] = byte(v >> 40)
		buf[2] = byte(v >> 32)
		buf[3] = byte(v >> 24)
		buf[4] = byte(v >> 16)
		buf[5] = byte(v >> 8)
		buf[6] = byte(v)
	case v <= 0xffffffffffffff:
		buf := buf.Grow(8)
		buf[0] = 0xf9
		buf[1] = byte(v >> 48)
		buf[2] = byte(v >> 40)
		buf[3] = byte(v >> 32)
		buf[4] = byte(v >> 24)
		buf[5] = byte(v >> 16)
		buf[6] = byte(v >> 8)
		buf[7] = byte(v)
	default:
		buf := buf.Grow(9)
		buf[0] = 0xf8
		buf[1] = byte(v >> 56)
		buf[2] = byte(v >> 48)
		buf[3] = byte(v >> 40)
		buf[4] = byte(v >> 32)
		buf[5] = byte(v >> 24)
		buf[6] = byte(v >> 16)
		buf[7] = byte(v >> 8)
		buf[8] = byte(v)
	}
}

func binaryDecodeUint(buf *decbuf) (uint64, error) {
	if !buf.IsAvailable(1) {
		if err := buf.Fill(1); err != nil {
			return 0, err
		}
	}
	firstByte := buf.ReadAvailableByte()
	// Handle single-byte encoding.
	if firstByte <= 0x7f {
		return uint64(firstByte), nil
	}
	// Handle multi-byte encoding.
	byteLen := int(-int8(firstByte))
	if byteLen < 1 || byteLen > uint64Size {
		return 0, verror.New(errInvalidLenOrControl, nil, firstByte)
	}
	if !buf.IsAvailable(byteLen) {
		if err := buf.Fill(byteLen); err != nil {
			return 0, err
		}
	}
	bytes := buf.ReadAvailable(byteLen)
	var uvalue uint64
	for _, b := range bytes {
		uvalue = uvalue<<8 | uint64(b)
	}
	return uvalue, nil
}

func binaryPeekUint(buf *decbuf) (uint64, int, error) {
	if !buf.IsAvailable(1) {
		if err := buf.Fill(1); err != nil {
			return 0, 0, err
		}
	}
	firstByte := buf.PeekAvailableByte()
	// Handle single-byte encoding.
	if firstByte <= 0x7f {
		return uint64(firstByte), 1, nil
	}
	// Handle multi-byte encoding.
	byteLen := int(-int8(firstByte))
	if byteLen < 1 || byteLen > uint64Size {
		return 0, 0, verror.New(errInvalidLenOrControl, nil, firstByte)
	}
	byteLen++ // account for initial len byte
	if !buf.IsAvailable(byteLen) {
		if err := buf.Fill(byteLen); err != nil {
			return 0, 0, err
		}
	}
	bytes := buf.PeekAvailable(byteLen)
	var uvalue uint64
	for _, b := range bytes[1:] {
		uvalue = uvalue<<8 | uint64(b)
	}
	return uvalue, byteLen, nil
}

func binarySkipUint(buf *decbuf) error {
	if !buf.IsAvailable(1) {
		if err := buf.Fill(1); err != nil {
			return err
		}
	}
	firstByte := buf.PeekAvailableByte()
	// Handle single-byte encoding.
	if firstByte <= 0x7f {
		buf.SkipAvailable(1)
		return nil
	}
	// Handle multi-byte encoding.
	byteLen := int(-int8(firstByte))
	if byteLen < 1 || byteLen > uint64Size {
		return verror.New(errInvalidLenOrControl, nil, firstByte)
	}
	byteLen++ // account for initial len byte
	if !buf.IsAvailable(byteLen) {
		if err := buf.Fill(byteLen); err != nil {
			return err
		}
	}
	buf.SkipAvailable(byteLen)
	return nil
}

func binaryPeekUintByteLen(buf *decbuf) (int, error) {
	if !buf.IsAvailable(1) {
		if err := buf.Fill(1); err != nil {
			return 0, err
		}
	}
	firstByte := buf.PeekAvailableByte()
	// Handle single-byte encoding.
	if firstByte <= 0x7f {
		return 1, nil
	}
	// Handle multi-byte encoding.
	byteLen := int(-int8(firstByte))
	if byteLen < 1 || byteLen > uint64Size {
		return 0, verror.New(errInvalidLenOrControl, nil, firstByte)
	}
	return 1 + byteLen, nil
}

func binaryDecodeLen(buf *decbuf) (int, error) {
	ulen, err := binaryDecodeUint(buf)
	switch {
	case err != nil:
		return 0, err
	case ulen > maxBinaryMsgLen:
		return 0, verror.New(errMsgLen, nil, maxBinaryMsgLen)
	}
	return int(ulen), nil
}

func binaryDecodeLenOrArrayLen(buf *decbuf, t *vdl.Type) (int, error) {
	len, err := binaryDecodeLen(buf)
	if err != nil {
		return 0, err
	}
	if t.Kind() == vdl.Array {
		if len != 0 {
			return 0, verror.New(errInvalid, nil) // TODO(toddw): better error
		}
		return t.Len(), nil
	}
	return len, nil
}

// Signed integers are encoded as unsigned integers, where the low bit says
// whether to complement the other bits to recover the int.
func binaryEncodeInt(buf *encbuf, v int64) {
	var uvalue uint64
	if v < 0 {
		uvalue = uint64(^v<<1) | 1
	} else {
		uvalue = uint64(v << 1)
	}
	binaryEncodeUint(buf, uvalue)
}

func binaryDecodeInt(buf *decbuf) (int64, error) {
	if !buf.IsAvailable(1) {
		if err := buf.Fill(1); err != nil {
			return 0, err
		}
	}
	firstByte := buf.ReadAvailableByte()
	// Handle single-byte encoding.
	if firstByte <= 0x7f {
		if firstByte&1 == 1 {
			return ^int64(firstByte >> 1), nil
		}
		return int64(firstByte >> 1), nil
	}
	// Handle multi-byte encoding.
	byteLen := int(-int8(firstByte))
	if byteLen < 1 || byteLen > uint64Size {
		return 0, verror.New(errInvalidLenOrControl, nil, firstByte)
	}
	if !buf.IsAvailable(byteLen) {
		if err := buf.Fill(byteLen); err != nil {
			return 0, err
		}
	}
	bytes := buf.ReadAvailable(byteLen)
	var uvalue uint64
	for _, b := range bytes {
		uvalue = uvalue<<8 | uint64(b)
	}
	if uvalue&1 == 1 {
		return ^int64(uvalue >> 1), nil
	}
	return int64(uvalue >> 1), nil
}

func binaryPeekInt(buf *decbuf) (int64, int, error) {
	if !buf.IsAvailable(1) {
		if err := buf.Fill(1); err != nil {
			return 0, 0, err
		}
	}
	firstByte := buf.PeekAvailableByte()
	// Handle single-byte encoding.
	if firstByte <= 0x7f {
		if firstByte&1 == 1 {
			return ^int64(firstByte >> 1), 1, nil
		}
		return int64(firstByte >> 1), 1, nil
	}
	// Handle multi-byte encoding.
	byteLen := int(-int8(firstByte))
	if byteLen < 1 || byteLen > uint64Size {
		return 0, 0, verror.New(errInvalidLenOrControl, nil, firstByte)
	}
	byteLen++ // account for initial len byte
	if !buf.IsAvailable(byteLen) {
		if err := buf.Fill(byteLen); err != nil {
			return 0, 0, err
		}
	}
	bytes := buf.PeekAvailable(byteLen)
	var uvalue uint64
	for _, b := range bytes[1:] {
		uvalue = uvalue<<8 | uint64(b)
	}
	if uvalue&1 == 1 {
		return ^int64(uvalue >> 1), byteLen, nil
	}
	return int64(uvalue >> 1), byteLen, nil
}

// Floating point numbers are encoded as byte-reversed ieee754.
func binaryEncodeFloat(buf *encbuf, v float64) {
	ieee := math.Float64bits(v)
	// Manually-unrolled byte-reversing.
	uvalue := (ieee&0xff)<<56 |
		(ieee&0xff00)<<40 |
		(ieee&0xff0000)<<24 |
		(ieee&0xff000000)<<8 |
		(ieee&0xff00000000)>>8 |
		(ieee&0xff0000000000)>>24 |
		(ieee&0xff000000000000)>>40 |
		(ieee&0xff00000000000000)>>56
	binaryEncodeUint(buf, uvalue)
}

func binaryDecodeFloat(buf *decbuf) (float64, error) {
	uvalue, err := binaryDecodeUint(buf)
	if err != nil {
		return 0, err
	}
	// Manually-unrolled byte-reversing.
	ieee := (uvalue&0xff)<<56 |
		(uvalue&0xff00)<<40 |
		(uvalue&0xff0000)<<24 |
		(uvalue&0xff000000)<<8 |
		(uvalue&0xff00000000)>>8 |
		(uvalue&0xff0000000000)>>24 |
		(uvalue&0xff000000000000)>>40 |
		(uvalue&0xff00000000000000)>>56
	return math.Float64frombits(ieee), nil
}

// Strings are encoded as the byte count followed by uninterpreted bytes.
func binaryEncodeString(buf *encbuf, s string) {
	binaryEncodeUint(buf, uint64(len(s)))
	buf.WriteString(s)
}

func binaryDecodeString(buf *decbuf) (string, error) {
	len, err := binaryDecodeLen(buf)
	if len == 0 || err != nil {
		return "", err
	}
	data := make([]byte, len)
	if err := buf.ReadIntoBuf(data); err != nil {
		return "", err
	}
	// Go makes an extra copy if we simply perform the conversion string(data), so
	// we use unsafe to transfer the contents from data into s without a copy.
	s := ""
	p := (*reflect.StringHeader)(unsafe.Pointer(&s))
	p.Data = uintptr(unsafe.Pointer(&data[0]))
	p.Len = len
	return s, nil
}

func binarySkipString(buf *decbuf) error {
	len, err := binaryDecodeLen(buf)
	if err != nil {
		return err
	}
	return buf.Skip(len)
}

// binaryEncodeUintEnd writes into the trailing part of buf and returns the start
// index of the encoded data.
//
// REQUIRES: buf is big enough to hold the encoded value.
func binaryEncodeUintEnd(buf []byte, v uint64) int {
	end := len(buf) - 1
	switch {
	case v <= 0x7f:
		buf[end] = byte(v)
		return end
	case v <= 0xff:
		buf[end-1] = 0xff
		buf[end] = byte(v)
		return end - 1
	case v <= 0xffff:
		buf[end-2] = 0xfe
		buf[end-1] = byte(v >> 8)
		buf[end] = byte(v)
		return end - 2
	case v <= 0xffffff:
		buf[end-3] = 0xfd
		buf[end-2] = byte(v >> 16)
		buf[end-1] = byte(v >> 8)
		buf[end] = byte(v)
		return end - 3
	case v <= 0xffffffff:
		buf[end-4] = 0xfc
		buf[end-3] = byte(v >> 24)
		buf[end-2] = byte(v >> 16)
		buf[end-1] = byte(v >> 8)
		buf[end] = byte(v)
		return end - 4
	case v <= 0xffffffffff:
		buf[end-5] = 0xfb
		buf[end-4] = byte(v >> 32)
		buf[end-3] = byte(v >> 24)
		buf[end-2] = byte(v >> 16)
		buf[end-1] = byte(v >> 8)
		buf[end] = byte(v)
		return end - 5
	case v <= 0xffffffffffff:
		buf[end-6] = 0xfa
		buf[end-5] = byte(v >> 40)
		buf[end-4] = byte(v >> 32)
		buf[end-3] = byte(v >> 24)
		buf[end-2] = byte(v >> 16)
		buf[end-1] = byte(v >> 8)
		buf[end] = byte(v)
		return end - 6
	case v <= 0xffffffffffffff:
		buf[end-7] = 0xf9
		buf[end-6] = byte(v >> 48)
		buf[end-5] = byte(v >> 40)
		buf[end-4] = byte(v >> 32)
		buf[end-3] = byte(v >> 24)
		buf[end-2] = byte(v >> 16)
		buf[end-1] = byte(v >> 8)
		buf[end] = byte(v)
		return end - 7
	default:
		buf[end-8] = 0xf8
		buf[end-7] = byte(v >> 56)
		buf[end-6] = byte(v >> 48)
		buf[end-5] = byte(v >> 40)
		buf[end-4] = byte(v >> 32)
		buf[end-3] = byte(v >> 24)
		buf[end-2] = byte(v >> 16)
		buf[end-1] = byte(v >> 8)
		buf[end] = byte(v)
		return end - 8
	}
}

// binaryEncodeIntEnd writes into the trailing part of buf and returns the start
// index of the encoded data.
//
// REQUIRES: buf is big enough to hold the encoded value.
func binaryEncodeIntEnd(buf []byte, v int64) int {
	var uvalue uint64
	if v < 0 {
		uvalue = uint64(^v<<1) | 1
	} else {
		uvalue = uint64(v << 1)
	}
	return binaryEncodeUintEnd(buf, uvalue)
}