encoding/binary: add Append, Encode and Decode

Add a function which appends the binary representation of a value to the end of a slice.
This allows users to encode values with zero allocations. Also add Encode and Decode
functions which mimic unicode/utf8.

goos: darwin
goarch: arm64
pkg: encoding/binary
cpu: Apple M1 Pro
                            │   base.txt    │             append.txt              │
                            │    sec/op     │    sec/op     vs base               │
ReadSlice1000Int32s-10         2.690µ ±  0%    2.532µ ± 3%   -5.86% (p=0.002 n=6)
ReadStruct-10                  205.8n ±  0%    201.4n ± 1%   -2.14% (p=0.002 n=6)
WriteStruct-10                 159.1n ±  0%    153.5n ± 0%   -3.55% (p=0.002 n=6)
WriteSlice1000Structs-10       129.8µ ±  0%    124.2µ ± 0%   -4.34% (p=0.002 n=6)
ReadSlice1000Structs-10        161.7µ ±  0%    160.3µ ± 0%   -0.89% (p=0.002 n=6)
ReadInts-10                    156.8n ±  0%    161.6n ± 0%   +3.09% (p=0.002 n=6)
WriteInts-10                   134.5n ±  0%    139.5n ± 2%   +3.72% (p=0.002 n=6)
WriteSlice1000Int32s-10        2.691µ ± 16%    2.551µ ± 4%   -5.20% (p=0.002 n=6)
PutUint16-10                  0.6448n ±  4%   0.6212n ± 1%        ~ (p=0.093 n=6)
AppendUint16-10                1.414n ±  0%    1.424n ± 1%        ~ (p=0.115 n=6)
PutUint32-10                  0.6210n ±  0%   0.6211n ± 0%        ~ (p=0.833 n=6)
AppendUint32-10                1.414n ±  0%    1.426n ± 1%   +0.85% (p=0.017 n=6)
PutUint64-10                  0.6210n ±  0%   0.6394n ± 1%   +2.95% (p=0.002 n=6)
AppendUint64-10                1.414n ±  0%    1.427n ± 2%        ~ (p=0.052 n=6)
LittleEndianPutUint16-10      0.6239n ±  0%   0.6271n ± 1%        ~ (p=0.063 n=6)
LittleEndianAppendUint16-10    1.421n ±  0%    1.432n ± 1%   +0.81% (p=0.002 n=6)
LittleEndianPutUint32-10      0.6240n ±  0%   0.6240n ± 0%        ~ (p=0.766 n=6)
LittleEndianAppendUint32-10    1.422n ±  1%    1.425n ± 0%        ~ (p=0.673 n=6)
LittleEndianPutUint64-10      0.6242n ±  0%   0.6238n ± 0%   -0.08% (p=0.030 n=6)
LittleEndianAppendUint64-10    1.420n ±  0%    1.449n ± 1%   +2.04% (p=0.002 n=6)
ReadFloats-10                  39.36n ±  0%    42.54n ± 1%   +8.08% (p=0.002 n=6)
WriteFloats-10                 33.65n ±  0%    35.27n ± 1%   +4.80% (p=0.002 n=6)
ReadSlice1000Float32s-10       2.656µ ±  0%    2.526µ ± 1%   -4.91% (p=0.002 n=6)
WriteSlice1000Float32s-10      2.765µ ±  0%    2.857µ ± 3%   +3.31% (p=0.002 n=6)
ReadSlice1000Uint8s-10         129.1n ±  1%    130.4n ± 1%        ~ (p=0.126 n=6)
WriteSlice1000Uint8s-10       144.90n ±  3%    18.67n ± 2%  -87.12% (p=0.002 n=6)
PutUvarint32-10                12.11n ±  0%    12.12n ± 0%        ~ (p=0.675 n=6)
PutUvarint64-10                30.82n ±  0%    30.79n ± 1%        ~ (p=0.658 n=6)
AppendStruct-10                                107.8n ± 0%
AppendSlice1000Structs-10                      119.0µ ± 0%
AppendInts-10                                  55.29n ± 0%
AppendSlice1000Int32s-10                       2.211µ ± 1%
geomean                        33.07n          48.18n        -7.03%

Fixes #60023

Change-Id: Ife3f217b11d5f3eaa5a53fe8a7e877552f751f94
Reviewed-on: https://go-review.googlesource.com/c/go/+/579157
Reviewed-by: Keith Randall <khr@google.com>
Auto-Submit: Austin Clements <austin@google.com>
Reviewed-by: Ingo Oeser <nightlyone@googlemail.com>
Reviewed-by: Austin Clements <austin@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

1 files changed, 312 insertions, 192 deletions

diff --git a/src/encoding/binary/binary.go b/src/encoding/binary/binary.go
index 291e494dd4..55aa880ea5 100644
--- a/src/encoding/binary/binary.go
+++ b/src/encoding/binary/binary.go
@@ -26,9 +26,12 @@ import (
 	"io"
 	"math"
 	"reflect"
+	"slices"
 	"sync"
 )
 
+var errBufferTooSmall = errors.New("buffer too small")
+
 // A ByteOrder specifies how to convert byte slices into
 // 16-, 32-, or 64-bit unsigned integers.
 //
@@ -236,80 +239,13 @@ func (nativeEndian) GoString() string { return "binary.NativeEndian" }
 // Read returns [io.ErrUnexpectedEOF].
 func Read(r io.Reader, order ByteOrder, data any) error {
 	// Fast path for basic types and slices.
-	if n := intDataSize(data); n != 0 {
+	if n, _ := intDataSize(data); n != 0 {
 		bs := make([]byte, n)
 		if _, err := io.ReadFull(r, bs); err != nil {
 			return err
 		}
-		switch data := data.(type) {
-		case *bool:
-			*data = bs[0] != 0
-		case *int8:
-			*data = int8(bs[0])
-		case *uint8:
-			*data = bs[0]
-		case *int16:
-			*data = int16(order.Uint16(bs))
-		case *uint16:
-			*data = order.Uint16(bs)
-		case *int32:
-			*data = int32(order.Uint32(bs))
-		case *uint32:
-			*data = order.Uint32(bs)
-		case *int64:
-			*data = int64(order.Uint64(bs))
-		case *uint64:
-			*data = order.Uint64(bs)
-		case *float32:
-			*data = math.Float32frombits(order.Uint32(bs))
-		case *float64:
-			*data = math.Float64frombits(order.Uint64(bs))
-		case []bool:
-			for i, x := range bs { // Easier to loop over the input for 8-bit values.
-				data[i] = x != 0
-			}
-		case []int8:
-			for i, x := range bs {
-				data[i] = int8(x)
-			}
-		case []uint8:
-			copy(data, bs)
-		case []int16:
-			for i := range data {
-				data[i] = int16(order.Uint16(bs[2*i:]))
-			}
-		case []uint16:
-			for i := range data {
-				data[i] = order.Uint16(bs[2*i:])
-			}
-		case []int32:
-			for i := range data {
-				data[i] = int32(order.Uint32(bs[4*i:]))
-			}
-		case []uint32:
-			for i := range data {
-				data[i] = order.Uint32(bs[4*i:])
-			}
-		case []int64:
-			for i := range data {
-				data[i] = int64(order.Uint64(bs[8*i:]))
-			}
-		case []uint64:
-			for i := range data {
-				data[i] = order.Uint64(bs[8*i:])
-			}
-		case []float32:
-			for i := range data {
-				data[i] = math.Float32frombits(order.Uint32(bs[4*i:]))
-			}
-		case []float64:
-			for i := range data {
-				data[i] = math.Float64frombits(order.Uint64(bs[8*i:]))
-			}
-		default:
-			n = 0 // fast path doesn't apply
-		}
-		if n != 0 {
+
+		if decodeFast(bs, order, data) {
 			return nil
 		}
 	}
@@ -327,6 +263,7 @@ func Read(r io.Reader, order ByteOrder, data any) error {
 	if size < 0 {
 		return errors.New("binary.Read: invalid type " + reflect.TypeOf(data).String())
 	}
+
 	d := &decoder{order: order, buf: make([]byte, size)}
 	if _, err := io.ReadFull(r, d.buf); err != nil {
 		return err
@@ -335,6 +272,115 @@ func Read(r io.Reader, order ByteOrder, data any) error {
 	return nil
 }
 
+// Decode binary data from buf into data according to the given byte order.
+//
+// Returns an error if buf is too small, otherwise the number of
+// bytes consumed from buf.
+func Decode(buf []byte, order ByteOrder, data any) (int, error) {
+	if n, _ := intDataSize(data); n != 0 {
+		if len(buf) < n {
+			return 0, errBufferTooSmall
+		}
+
+		if decodeFast(buf, order, data) {
+			return n, nil
+		}
+	}
+
+	// Fallback to reflect-based decoding.
+	v := reflect.ValueOf(data)
+	size := -1
+	switch v.Kind() {
+	case reflect.Pointer:
+		v = v.Elem()
+		size = dataSize(v)
+	case reflect.Slice:
+		size = dataSize(v)
+	}
+	if size < 0 {
+		return 0, errors.New("binary.Decode: invalid type " + reflect.TypeOf(data).String())
+	}
+
+	if len(buf) < size {
+		return 0, errBufferTooSmall
+	}
+	d := &decoder{order: order, buf: buf[:size]}
+	d.value(v)
+	return size, nil
+}
+
+func decodeFast(bs []byte, order ByteOrder, data any) bool {
+	switch data := data.(type) {
+	case *bool:
+		*data = bs[0] != 0
+	case *int8:
+		*data = int8(bs[0])
+	case *uint8:
+		*data = bs[0]
+	case *int16:
+		*data = int16(order.Uint16(bs))
+	case *uint16:
+		*data = order.Uint16(bs)
+	case *int32:
+		*data = int32(order.Uint32(bs))
+	case *uint32:
+		*data = order.Uint32(bs)
+	case *int64:
+		*data = int64(order.Uint64(bs))
+	case *uint64:
+		*data = order.Uint64(bs)
+	case *float32:
+		*data = math.Float32frombits(order.Uint32(bs))
+	case *float64:
+		*data = math.Float64frombits(order.Uint64(bs))
+	case []bool:
+		for i, x := range bs { // Easier to loop over the input for 8-bit values.
+			data[i] = x != 0
+		}
+	case []int8:
+		for i, x := range bs {
+			data[i] = int8(x)
+		}
+	case []uint8:
+		copy(data, bs)
+	case []int16:
+		for i := range data {
+			data[i] = int16(order.Uint16(bs[2*i:]))
+		}
+	case []uint16:
+		for i := range data {
+			data[i] = order.Uint16(bs[2*i:])
+		}
+	case []int32:
+		for i := range data {
+			data[i] = int32(order.Uint32(bs[4*i:]))
+		}
+	case []uint32:
+		for i := range data {
+			data[i] = order.Uint32(bs[4*i:])
+		}
+	case []int64:
+		for i := range data {
+			data[i] = int64(order.Uint64(bs[8*i:]))
+		}
+	case []uint64:
+		for i := range data {
+			data[i] = order.Uint64(bs[8*i:])
+		}
+	case []float32:
+		for i := range data {
+			data[i] = math.Float32frombits(order.Uint32(bs[4*i:]))
+		}
+	case []float64:
+		for i := range data {
+			data[i] = math.Float64frombits(order.Uint64(bs[8*i:]))
+		}
+	default:
+		return false
+	}
+	return true
+}
+
 // Write writes the binary representation of data into w.
 // Data must be a fixed-size value or a slice of fixed-size
 // values, or a pointer to such data.
@@ -345,108 +391,12 @@ func Read(r io.Reader, order ByteOrder, data any) error {
 // with blank (_) field names.
 func Write(w io.Writer, order ByteOrder, data any) error {
 	// Fast path for basic types and slices.
-	if n := intDataSize(data); n != 0 {
-		bs := make([]byte, n)
-		switch v := data.(type) {
-		case *bool:
-			if *v {
-				bs[0] = 1
-			} else {
-				bs[0] = 0
-			}
-		case bool:
-			if v {
-				bs[0] = 1
-			} else {
-				bs[0] = 0
-			}
-		case []bool:
-			for i, x := range v {
-				if x {
-					bs[i] = 1
-				} else {
-					bs[i] = 0
-				}
-			}
-		case *int8:
-			bs[0] = byte(*v)
-		case int8:
-			bs[0] = byte(v)
-		case []int8:
-			for i, x := range v {
-				bs[i] = byte(x)
-			}
-		case *uint8:
-			bs[0] = *v
-		case uint8:
-			bs[0] = v
-		case []uint8:
-			bs = v
-		case *int16:
-			order.PutUint16(bs, uint16(*v))
-		case int16:
-			order.PutUint16(bs, uint16(v))
-		case []int16:
-			for i, x := range v {
-				order.PutUint16(bs[2*i:], uint16(x))
-			}
-		case *uint16:
-			order.PutUint16(bs, *v)
-		case uint16:
-			order.PutUint16(bs, v)
-		case []uint16:
-			for i, x := range v {
-				order.PutUint16(bs[2*i:], x)
-			}
-		case *int32:
-			order.PutUint32(bs, uint32(*v))
-		case int32:
-			order.PutUint32(bs, uint32(v))
-		case []int32:
-			for i, x := range v {
-				order.PutUint32(bs[4*i:], uint32(x))
-			}
-		case *uint32:
-			order.PutUint32(bs, *v)
-		case uint32:
-			order.PutUint32(bs, v)
-		case []uint32:
-			for i, x := range v {
-				order.PutUint32(bs[4*i:], x)
-			}
-		case *int64:
-			order.PutUint64(bs, uint64(*v))
-		case int64:
-			order.PutUint64(bs, uint64(v))
-		case []int64:
-			for i, x := range v {
-				order.PutUint64(bs[8*i:], uint64(x))
-			}
-		case *uint64:
-			order.PutUint64(bs, *v)
-		case uint64:
-			order.PutUint64(bs, v)
-		case []uint64:
-			for i, x := range v {
-				order.PutUint64(bs[8*i:], x)
-			}
-		case *float32:
-			order.PutUint32(bs, math.Float32bits(*v))
-		case float32:
-			order.PutUint32(bs, math.Float32bits(v))
-		case []float32:
-			for i, x := range v {
-				order.PutUint32(bs[4*i:], math.Float32bits(x))
-			}
-		case *float64:
-			order.PutUint64(bs, math.Float64bits(*v))
-		case float64:
-			order.PutUint64(bs, math.Float64bits(v))
-		case []float64:
-			for i, x := range v {
-				order.PutUint64(bs[8*i:], math.Float64bits(x))
-			}
+	if n, bs := intDataSize(data); n != 0 {
+		if bs == nil {
+			bs = make([]byte, n)
+			encodeFast(bs, order, data)
 		}
+
 		_, err := w.Write(bs)
 		return err
 	}
@@ -457,6 +407,7 @@ func Write(w io.Writer, order ByteOrder, data any) error {
 	if size < 0 {
 		return errors.New("binary.Write: some values are not fixed-sized in type " + reflect.TypeOf(data).String())
 	}
+
 	buf := make([]byte, size)
 	e := &encoder{order: order, buf: buf}
 	e.value(v)
@@ -464,6 +415,166 @@ func Write(w io.Writer, order ByteOrder, data any) error {
 	return err
 }
 
+// Encode the binary representation of data into buf according to the given byte order.
+//
+// Returns an error if the buffer is too short, otherwise the number of bytes
+// written into buf.
+func Encode(buf []byte, order ByteOrder, data any) (int, error) {
+	// Fast path for basic types and slices.
+	if n, _ := intDataSize(data); n != 0 {
+		if len(buf) < n {
+			return 0, errBufferTooSmall
+		}
+
+		encodeFast(buf, order, data)
+		return n, nil
+	}
+
+	// Fallback to reflect-based encoding.
+	v := reflect.Indirect(reflect.ValueOf(data))
+	size := dataSize(v)
+	if size < 0 {
+		return 0, errors.New("binary.Encode: some values are not fixed-sized in type " + reflect.TypeOf(data).String())
+	}
+
+	if len(buf) < size {
+		return 0, errBufferTooSmall
+	}
+	e := &encoder{order: order, buf: buf}
+	e.value(v)
+	return size, nil
+}
+
+// Append the binary representation of data to buf.
+//
+// buf may be nil, in which case a new buffer will be allocated.
+// See [Write] on which data are acceptable.
+//
+// Returns the (possibily extended) buffer containing data or an error.
+func Append(buf []byte, order ByteOrder, data any) ([]byte, error) {
+	// Fast path for basic types and slices.
+	if n, _ := intDataSize(data); n != 0 {
+		buf, pos := ensure(buf, n)
+		encodeFast(pos, order, data)
+		return buf, nil
+	}
+
+	// Fallback to reflect-based encoding.
+	v := reflect.Indirect(reflect.ValueOf(data))
+	size := dataSize(v)
+	if size < 0 {
+		return nil, errors.New("binary.Append: some values are not fixed-sized in type " + reflect.TypeOf(data).String())
+	}
+
+	buf, pos := ensure(buf, size)
+	e := &encoder{order: order, buf: pos}
+	e.value(v)
+	return buf, nil
+}
+
+func encodeFast(bs []byte, order ByteOrder, data any) {
+	switch v := data.(type) {
+	case *bool:
+		if *v {
+			bs[0] = 1
+		} else {
+			bs[0] = 0
+		}
+	case bool:
+		if v {
+			bs[0] = 1
+		} else {
+			bs[0] = 0
+		}
+	case []bool:
+		for i, x := range v {
+			if x {
+				bs[i] = 1
+			} else {
+				bs[i] = 0
+			}
+		}
+	case *int8:
+		bs[0] = byte(*v)
+	case int8:
+		bs[0] = byte(v)
+	case []int8:
+		for i, x := range v {
+			bs[i] = byte(x)
+		}
+	case *uint8:
+		bs[0] = *v
+	case uint8:
+		bs[0] = v
+	case []uint8:
+		copy(bs, v)
+	case *int16:
+		order.PutUint16(bs, uint16(*v))
+	case int16:
+		order.PutUint16(bs, uint16(v))
+	case []int16:
+		for i, x := range v {
+			order.PutUint16(bs[2*i:], uint16(x))
+		}
+	case *uint16:
+		order.PutUint16(bs, *v)
+	case uint16:
+		order.PutUint16(bs, v)
+	case []uint16:
+		for i, x := range v {
+			order.PutUint16(bs[2*i:], x)
+		}
+	case *int32:
+		order.PutUint32(bs, uint32(*v))
+	case int32:
+		order.PutUint32(bs, uint32(v))
+	case []int32:
+		for i, x := range v {
+			order.PutUint32(bs[4*i:], uint32(x))
+		}
+	case *uint32:
+		order.PutUint32(bs, *v)
+	case uint32:
+		order.PutUint32(bs, v)
+	case []uint32:
+		for i, x := range v {
+			order.PutUint32(bs[4*i:], x)
+		}
+	case *int64:
+		order.PutUint64(bs, uint64(*v))
+	case int64:
+		order.PutUint64(bs, uint64(v))
+	case []int64:
+		for i, x := range v {
+			order.PutUint64(bs[8*i:], uint64(x))
+		}
+	case *uint64:
+		order.PutUint64(bs, *v)
+	case uint64:
+		order.PutUint64(bs, v)
+	case []uint64:
+		for i, x := range v {
+			order.PutUint64(bs[8*i:], x)
+		}
+	case *float32:
+		order.PutUint32(bs, math.Float32bits(*v))
+	case float32:
+		order.PutUint32(bs, math.Float32bits(v))
+	case []float32:
+		for i, x := range v {
+			order.PutUint32(bs[4*i:], math.Float32bits(x))
+		}
+	case *float64:
+		order.PutUint64(bs, math.Float64bits(*v))
+	case float64:
+		order.PutUint64(bs, math.Float64bits(v))
+	case []float64:
+		for i, x := range v {
+			order.PutUint64(bs[8*i:], math.Float64bits(x))
+		}
+	}
+}
+
 // Size returns how many bytes [Write] would generate to encode the value v, which
 // must be a fixed-size value or a slice of fixed-size values, or a pointer to such data.
 // If v is neither of these, Size returns -1.
@@ -766,44 +877,53 @@ func (e *encoder) skip(v reflect.Value) {
 	e.offset += n
 }
 
-// intDataSize returns the size of the data required to represent the data when encoded.
-// It returns zero if the type cannot be implemented by the fast path in Read or Write.
-func intDataSize(data any) int {
+// intDataSize returns the size of the data required to represent the data when encoded,
+// and optionally a byte slice containing the encoded data if no conversion is necessary.
+// It returns zero, nil if the type cannot be implemented by the fast path in Read or Write.
+func intDataSize(data any) (int, []byte) {
 	switch data := data.(type) {
 	case bool, int8, uint8, *bool, *int8, *uint8:
-		return 1
+		return 1, nil
 	case []bool:
-		return len(data)
+		return len(data), nil
 	case []int8:
-		return len(data)
+		return len(data), nil
 	case []uint8:
-		return len(data)
+		return len(data), data
 	case int16, uint16, *int16, *uint16:
-		return 2
+		return 2, nil
 	case []int16:
-		return 2 * len(data)
+		return 2 * len(data), nil
 	case []uint16:
-		return 2 * len(data)
+		return 2 * len(data), nil
 	case int32, uint32, *int32, *uint32:
-		return 4
+		return 4, nil
 	case []int32:
-		return 4 * len(data)
+		return 4 * len(data), nil
 	case []uint32:
-		return 4 * len(data)
+		return 4 * len(data), nil
 	case int64, uint64, *int64, *uint64:
-		return 8
+		return 8, nil
 	case []int64:
-		return 8 * len(data)
+		return 8 * len(data), nil
 	case []uint64:
-		return 8 * len(data)
+		return 8 * len(data), nil
 	case float32, *float32:
-		return 4
+		return 4, nil
 	case float64, *float64:
-		return 8
+		return 8, nil
 	case []float32:
-		return 4 * len(data)
+		return 4 * len(data), nil
 	case []float64:
-		return 8 * len(data)
+		return 8 * len(data), nil
 	}
-	return 0
+	return 0, nil
+}
+
+// ensure grows buf to length len(buf) + n and returns the grown buffer
+// and a slice starting at the original length of buf (that is, buf2[len(buf):]).
+func ensure(buf []byte, n int) (buf2, pos []byte) {
+	l := len(buf)
+	buf = slices.Grow(buf, n)[:l+n]
+	return buf, buf[l:]
 }