blob: 196cc8fd4982761e132fa3843202dd1ab57c8d33 [file] [log] [blame]
// 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 (
"io"
"math"
"v.io/v23/vdl"
"v.io/v23/verror"
)
// TODO(toddw) Reduce the number of functions and optimize.
const pkgPath = "v.io/v23/vom"
var (
errInvalid = verror.Register(pkgPath+".errInvalid", verror.NoRetry, "{1:}{2:} vom: invalid encoding{:_}")
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 {:_}")
)
// Binary encoding and decoding routines. The binary format is identical to the
// encoding/gob package, and much of the implementation is similar.
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 intToUint(v int64) uint64 {
var uval uint64
if v < 0 {
uval = uint64(^v<<1) | 1
} else {
uval = uint64(v << 1)
}
return uval
}
func uintToInt(uval uint64) int64 {
if uval&1 == 1 {
return ^int64(uval >> 1)
}
return int64(uval >> 1)
}
func binaryEncodeControl(buf *encbuf, v byte) {
if v < 0x80 || v > 0xef {
panic(verror.New(errBadControlCode, nil, v))
}
buf.WriteOneByte(v)
}
// If the byte is not a control, this will return 0.
func binaryPeekControl(buf *decbuf) (byte, error) {
v, err := buf.PeekByte()
if err != nil {
return 0, err
}
if v < 0x80 || v > 0xef {
return 0, nil
}
return v, 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) {
v, err := buf.ReadByte()
if err != nil {
return false, err
}
if v > 0x7f {
return false, verror.New(errInvalid, nil)
}
return v != 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 byteSliceBinaryPeekUint(p []byte) (val uint64, byteLen int, err error) {
v, cr, bytelen, err := byteSliceBinaryPeekUintWithControl(p)
if err != nil {
return 0, 0, err
}
if cr != 0 {
return 0, 0, verror.New(errInvalid, nil)
}
return v, bytelen, nil
}
func binaryDecodeUint(buf *decbuf) (uint64, error) {
v, bytelen, err := binaryPeekUint(buf)
if err != nil {
return 0, err
}
return v, buf.Skip(bytelen)
}
func byteSliceBinaryPeekUintWithControl(b []byte) (val uint64, cr byte, lenRead int, err error) {
if len(b) == 0 {
return 0, 0, 0, io.EOF
}
firstByte := b[0]
// Handle single-byte encoding.
if firstByte <= 0x7f {
return uint64(firstByte), 0, 1, nil
}
// Handle control code.
if firstByte <= 0xef {
return 0, byte(firstByte), 1, nil
}
// Handle multi-byte encoding.
byteLen := int(-int8(firstByte))
if byteLen < 1 || byteLen > uint64Size {
return 0, 0, 0, verror.New(errUintOverflow, nil)
}
if byteLen >= len(b) {
return 0, 0, 0, io.EOF
}
var v uint64
for _, b := range b[1 : byteLen+1] {
v = v<<8 | uint64(b)
}
return v, 0, byteLen + 1, nil
}
func byteSliceBinaryPeekIntWithControl(b []byte) (val int64, cr byte, lenRead int, err error) {
var uval uint64
uval, cr, lenRead, err = byteSliceBinaryPeekUintWithControl(b)
val = uintToInt(uval)
return
}
func binaryPeekUint(buf *decbuf) (uint64, int, error) {
firstByte, err := buf.PeekByte()
if err != nil {
return 0, 0, err
}
// Handle single-byte encoding.
if firstByte <= 0x7f {
return uint64(firstByte), 1, nil
}
// Verify not a control code.
if firstByte <= 0xef {
return 0, 0, verror.New(errInvalid, nil)
}
// Handle multi-byte encoding.
byteLen := int(-int8(firstByte))
if byteLen < 1 || byteLen > uint64Size {
return 0, 0, verror.New(errUintOverflow, nil)
}
byteLen++ // account for initial len byte
bytes, err := buf.PeekSmall(byteLen)
if err != nil {
return 0, 0, err
}
var v uint64
for _, b := range bytes[1:byteLen] {
v = v<<8 | uint64(b)
}
return v, byteLen, nil
}
func binaryDecodeUintWithControl(buf *decbuf) (uint64, byte, error) {
v, c, bytelen, err := binaryPeekUintWithControl(buf)
if err != nil {
return 0, 0, err
}
return v, c, buf.Skip(bytelen)
}
func binaryDecodeIntWithControl(buf *decbuf) (int64, byte, error) {
v, c, bytelen, err := binaryPeekUintWithControl(buf)
if err != nil {
return 0, 0, err
}
return uintToInt(v), c, buf.Skip(bytelen)
}
func binaryPeekUintWithControl(buf *decbuf) (uint64, byte, int, error) {
firstByte, err := buf.PeekByte()
if err != nil {
return 0, 0, 0, err
}
// Handle single-byte encoding.
if firstByte <= 0x7f {
return uint64(firstByte), 0, 1, nil
}
// Handle control code.
if firstByte <= 0xef {
return 0, byte(firstByte), 1, nil
}
// Handle multi-byte encoding.
byteLen := int(-int8(firstByte))
if byteLen < 1 || byteLen > uint64Size {
return 0, 0, 0, verror.New(errUintOverflow, nil)
}
byteLen++ // account for initial len byte
bytes, err := buf.PeekSmall(byteLen)
if err != nil {
return 0, 0, 0, err
}
var v uint64
for _, b := range bytes[1:byteLen] {
v = v<<8 | uint64(b)
}
return v, 0, byteLen, nil
}
func binaryPeekIntWithControl(buf *decbuf) (int64, byte, int, error) {
v, cr, l, err := binaryPeekUintWithControl(buf)
return uintToInt(v), cr, l, err
}
func binaryPeekUintByteLen(buf *decbuf) (int, error) {
firstByte, err := buf.PeekByte()
if err != nil {
return 0, err
}
if firstByte <= 0xef {
return 1, nil
}
byteLen := int(-int8(firstByte))
if byteLen > uint64Size {
return 0, verror.New(errUintOverflow, nil)
}
return 1 + byteLen, nil
}
func binaryIgnoreUint(buf *decbuf) error {
byteLen, err := binaryPeekUintByteLen(buf)
if err != nil {
return err
}
return buf.Skip(byteLen)
}
func byteSliceBinaryPeekLen(b []byte) (len, byteLen int, err error) {
ulen, byteLen, err := byteSliceBinaryPeekUint(b)
switch {
case err != nil:
return 0, 0, err
case ulen > maxBinaryMsgLen:
return 0, 0, verror.New(errMsgLen, nil, maxBinaryMsgLen)
}
return int(ulen), 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)
}
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 uval uint64
if v < 0 {
uval = uint64(^v<<1) | 1
} else {
uval = uint64(v << 1)
}
binaryEncodeUint(buf, uval)
}
func binaryDecodeInt(buf *decbuf) (int64, error) {
uval, err := binaryDecodeUint(buf)
return uintToInt(uval), err
}
func binaryPeekInt(buf *decbuf) (int64, int, error) {
uval, bytelen, err := binaryPeekUint(buf)
if err != nil {
return 0, 0, err
}
return uintToInt(uval), bytelen, err
}
// Floating point numbers are encoded as byte-reversed ieee754.
func binaryEncodeFloat(buf *encbuf, v float64) {
ieee := math.Float64bits(v)
// Manually-unrolled byte-reversing.
uval := (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, uval)
}
func binaryDecodeFloat(buf *decbuf) (float64, error) {
uval, err := binaryDecodeUint(buf)
if err != nil {
return 0, err
}
// Manually-unrolled byte-reversing.
ieee := (uval&0xff)<<56 |
(uval&0xff00)<<40 |
(uval&0xff0000)<<24 |
(uval&0xff000000)<<8 |
(uval&0xff00000000)>>8 |
(uval&0xff0000000000)>>24 |
(uval&0xff000000000000)>>40 |
(uval&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.Write([]byte(s))
}
func binaryDecodeString(buf *decbuf) (string, error) {
len, err := binaryDecodeLen(buf)
if err != nil {
return "", err
}
p := make([]byte, len)
if err := buf.ReadIntoBuf(p); err != nil {
return "", err
}
return string(p), nil
}
func binaryIgnoreString(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 {
return binaryEncodeUintEnd(buf, intToUint(v))
}