quic: varint encoding and decoding
Functions to encode and decode QUIC variable-length integers
(RFC 9000, Section 16), as well as a few other common operations.
For golang/go#58547
Change-Id: I2a738e8798b8013a7b13d7c1e1385bf846c6c2cd
Reviewed-on: https://go-review.googlesource.com/c/net/+/478258
Run-TryBot: Damien Neil <dneil@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Jonathan Amsterdam <jba@google.com>
diff --git a/internal/quic/wire.go b/internal/quic/wire.go
new file mode 100644
index 0000000..2494ad0
--- /dev/null
+++ b/internal/quic/wire.go
@@ -0,0 +1,145 @@
+// Copyright 2023 The Go 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 quic
+
+import "encoding/binary"
+
+const maxVarintSize = 8
+
+// consumeVarint parses a variable-length integer, reporting its length.
+// It returns a negative length upon an error.
+//
+// https://www.rfc-editor.org/rfc/rfc9000.html#section-16
+func consumeVarint(b []byte) (v uint64, n int) {
+ if len(b) < 1 {
+ return 0, -1
+ }
+ b0 := b[0] & 0x3f
+ switch b[0] >> 6 {
+ case 0:
+ return uint64(b0), 1
+ case 1:
+ if len(b) < 2 {
+ return 0, -1
+ }
+ return uint64(b0)<<8 | uint64(b[1]), 2
+ case 2:
+ if len(b) < 4 {
+ return 0, -1
+ }
+ return uint64(b0)<<24 | uint64(b[1])<<16 | uint64(b[2])<<8 | uint64(b[3]), 4
+ case 3:
+ if len(b) < 8 {
+ return 0, -1
+ }
+ return uint64(b0)<<56 | uint64(b[1])<<48 | uint64(b[2])<<40 | uint64(b[3])<<32 | uint64(b[4])<<24 | uint64(b[5])<<16 | uint64(b[6])<<8 | uint64(b[7]), 8
+ }
+ return 0, -1
+}
+
+// consumeVarint64 parses a variable-length integer as an int64.
+func consumeVarintInt64(b []byte) (v int64, n int) {
+ u, n := consumeVarint(b)
+ // QUIC varints are 62-bits large, so this conversion can never overflow.
+ return int64(u), n
+}
+
+// appendVarint appends a variable-length integer to b.
+//
+// https://www.rfc-editor.org/rfc/rfc9000.html#section-16
+func appendVarint(b []byte, v uint64) []byte {
+ switch {
+ case v <= 63:
+ return append(b, byte(v))
+ case v <= 16383:
+ return append(b, (1<<6)|byte(v>>8), byte(v))
+ case v <= 1073741823:
+ return append(b, (2<<6)|byte(v>>24), byte(v>>16), byte(v>>8), byte(v))
+ case v <= 4611686018427387903:
+ return append(b, (3<<6)|byte(v>>56), byte(v>>48), byte(v>>40), byte(v>>32), byte(v>>24), byte(v>>16), byte(v>>8), byte(v))
+ default:
+ panic("varint too large")
+ }
+}
+
+// sizeVarint returns the size of the variable-length integer encoding of f.
+func sizeVarint(v uint64) int {
+ switch {
+ case v <= 63:
+ return 1
+ case v <= 16383:
+ return 2
+ case v <= 1073741823:
+ return 4
+ case v <= 4611686018427387903:
+ return 8
+ default:
+ panic("varint too large")
+ }
+}
+
+// consumeUint32 parses a 32-bit fixed-length, big-endian integer, reporting its length.
+// It returns a negative length upon an error.
+func consumeUint32(b []byte) (uint32, int) {
+ if len(b) < 4 {
+ return 0, -1
+ }
+ return binary.BigEndian.Uint32(b), 4
+}
+
+// consumeUint64 parses a 64-bit fixed-length, big-endian integer, reporting its length.
+// It returns a negative length upon an error.
+func consumeUint64(b []byte) (uint64, int) {
+ if len(b) < 8 {
+ return 0, -1
+ }
+ return binary.BigEndian.Uint64(b), 8
+}
+
+// consumeUint8Bytes parses a sequence of bytes prefixed with an 8-bit length,
+// reporting the total number of bytes consumed.
+// It returns a negative length upon an error.
+func consumeUint8Bytes(b []byte) ([]byte, int) {
+ if len(b) < 1 {
+ return nil, -1
+ }
+ size := int(b[0])
+ const n = 1
+ if size > len(b[n:]) {
+ return nil, -1
+ }
+ return b[n:][:size], size + n
+}
+
+// appendUint8Bytes appends a sequence of bytes prefixed by an 8-bit length.
+func appendUint8Bytes(b, v []byte) []byte {
+ if len(v) > 0xff {
+ panic("uint8-prefixed bytes too large")
+ }
+ b = append(b, uint8(len(v)))
+ b = append(b, v...)
+ return b
+}
+
+// consumeVarintBytes parses a sequence of bytes preceded by a variable-length integer length,
+// reporting the total number of bytes consumed.
+// It returns a negative length upon an error.
+func consumeVarintBytes(b []byte) ([]byte, int) {
+ size, n := consumeVarint(b)
+ if n < 0 {
+ return nil, -1
+ }
+ if size > uint64(len(b[n:])) {
+ return nil, -1
+ }
+ return b[n:][:size], int(size) + n
+}
+
+// appendVarintBytes appends a sequence of bytes prefixed by a variable-length integer length.
+func appendVarintBytes(b, v []byte) []byte {
+ b = appendVarint(b, uint64(len(v)))
+ b = append(b, v...)
+ return b
+}
diff --git a/internal/quic/wire_test.go b/internal/quic/wire_test.go
new file mode 100644
index 0000000..a5dd836
--- /dev/null
+++ b/internal/quic/wire_test.go
@@ -0,0 +1,223 @@
+// Copyright 2023 The Go 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 quic
+
+import (
+ "bytes"
+ "testing"
+)
+
+func TestConsumeVarint(t *testing.T) {
+ for _, test := range []struct {
+ b []byte
+ want uint64
+ wantLen int
+ }{
+ {[]byte{0x00}, 0, 1},
+ {[]byte{0x3f}, 63, 1},
+ {[]byte{0x40, 0x00}, 0, 2},
+ {[]byte{0x7f, 0xff}, 16383, 2},
+ {[]byte{0x80, 0x00, 0x00, 0x00}, 0, 4},
+ {[]byte{0xbf, 0xff, 0xff, 0xff}, 1073741823, 4},
+ {[]byte{0xc0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}, 0, 8},
+ {[]byte{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}, 4611686018427387903, 8},
+ // Example cases from https://www.rfc-editor.org/rfc/rfc9000.html#section-a.1
+ {[]byte{0xc2, 0x19, 0x7c, 0x5e, 0xff, 0x14, 0xe8, 0x8c}, 151288809941952652, 8},
+ {[]byte{0x9d, 0x7f, 0x3e, 0x7d}, 494878333, 4},
+ {[]byte{0x7b, 0xbd}, 15293, 2},
+ {[]byte{0x25}, 37, 1},
+ {[]byte{0x40, 0x25}, 37, 2},
+ } {
+ got, gotLen := consumeVarint(test.b)
+ if got != test.want || gotLen != test.wantLen {
+ t.Errorf("consumeVarint(%x) = %v, %v; want %v, %v", test.b, got, gotLen, test.want, test.wantLen)
+ }
+ // Extra data in the buffer is ignored.
+ b := append(test.b, 0)
+ got, gotLen = consumeVarint(b)
+ if got != test.want || gotLen != test.wantLen {
+ t.Errorf("consumeVarint(%x) = %v, %v; want %v, %v", b, got, gotLen, test.want, test.wantLen)
+ }
+ // Short buffer results in an error.
+ for i := 1; i <= len(test.b); i++ {
+ b = test.b[:len(test.b)-i]
+ got, gotLen = consumeVarint(b)
+ if got != 0 || gotLen >= 0 {
+ t.Errorf("consumeVarint(%x) = %v, %v; want 0, -1", b, got, gotLen)
+ }
+ }
+ }
+}
+
+func TestAppendVarint(t *testing.T) {
+ for _, test := range []struct {
+ v uint64
+ want []byte
+ }{
+ {0, []byte{0x00}},
+ {63, []byte{0x3f}},
+ {16383, []byte{0x7f, 0xff}},
+ {1073741823, []byte{0xbf, 0xff, 0xff, 0xff}},
+ {4611686018427387903, []byte{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}},
+ // Example cases from https://www.rfc-editor.org/rfc/rfc9000.html#section-a.1
+ {151288809941952652, []byte{0xc2, 0x19, 0x7c, 0x5e, 0xff, 0x14, 0xe8, 0x8c}},
+ {494878333, []byte{0x9d, 0x7f, 0x3e, 0x7d}},
+ {15293, []byte{0x7b, 0xbd}},
+ {37, []byte{0x25}},
+ } {
+ got := appendVarint([]byte{}, test.v)
+ if !bytes.Equal(got, test.want) {
+ t.Errorf("AppendVarint(nil, %v) = %x, want %x", test.v, got, test.want)
+ }
+ if gotLen, wantLen := sizeVarint(test.v), len(got); gotLen != wantLen {
+ t.Errorf("SizeVarint(%v) = %v, want %v", test.v, gotLen, wantLen)
+ }
+ }
+}
+
+func TestConsumeUint32(t *testing.T) {
+ for _, test := range []struct {
+ b []byte
+ want uint32
+ wantLen int
+ }{
+ {[]byte{0x01, 0x02, 0x03, 0x04}, 0x01020304, 4},
+ {[]byte{0x01, 0x02, 0x03}, 0, -1},
+ } {
+ if got, n := consumeUint32(test.b); got != test.want || n != test.wantLen {
+ t.Errorf("consumeUint32(%x) = %v, %v; want %v, %v", test.b, got, n, test.want, test.wantLen)
+ }
+ }
+}
+
+func TestConsumeUint64(t *testing.T) {
+ for _, test := range []struct {
+ b []byte
+ want uint64
+ wantLen int
+ }{
+ {[]byte{0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08}, 0x0102030405060708, 8},
+ {[]byte{0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07}, 0, -1},
+ } {
+ if got, n := consumeUint64(test.b); got != test.want || n != test.wantLen {
+ t.Errorf("consumeUint32(%x) = %v, %v; want %v, %v", test.b, got, n, test.want, test.wantLen)
+ }
+ }
+}
+
+func TestConsumeVarintBytes(t *testing.T) {
+ for _, test := range []struct {
+ b []byte
+ want []byte
+ wantLen int
+ }{
+ {[]byte{0x00}, []byte{}, 1},
+ {[]byte{0x40, 0x00}, []byte{}, 2},
+ {[]byte{0x04, 0x01, 0x02, 0x03, 0x04}, []byte{0x01, 0x02, 0x03, 0x04}, 5},
+ {[]byte{0x40, 0x04, 0x01, 0x02, 0x03, 0x04}, []byte{0x01, 0x02, 0x03, 0x04}, 6},
+ } {
+ got, gotLen := consumeVarintBytes(test.b)
+ if !bytes.Equal(got, test.want) || gotLen != test.wantLen {
+ t.Errorf("consumeVarintBytes(%x) = {%x}, %v; want {%x}, %v", test.b, got, gotLen, test.want, test.wantLen)
+ }
+ // Extra data in the buffer is ignored.
+ b := append(test.b, 0)
+ got, gotLen = consumeVarintBytes(b)
+ if !bytes.Equal(got, test.want) || gotLen != test.wantLen {
+ t.Errorf("consumeVarintBytes(%x) = {%x}, %v; want {%x}, %v", b, got, gotLen, test.want, test.wantLen)
+ }
+ // Short buffer results in an error.
+ for i := 1; i <= len(test.b); i++ {
+ b = test.b[:len(test.b)-i]
+ got, gotLen := consumeVarintBytes(b)
+ if len(got) > 0 || gotLen > 0 {
+ t.Errorf("consumeVarintBytes(%x) = {%x}, %v; want {}, -1", b, got, gotLen)
+ }
+ }
+
+ }
+}
+
+func TestConsumeVarintBytesErrors(t *testing.T) {
+ for _, b := range [][]byte{
+ {0x01},
+ {0x40, 0x01},
+ } {
+ got, gotLen := consumeVarintBytes(b)
+ if len(got) > 0 || gotLen > 0 {
+ t.Errorf("consumeVarintBytes(%x) = {%x}, %v; want {}, -1", b, got, gotLen)
+ }
+ }
+}
+
+func TestConsumeUint8Bytes(t *testing.T) {
+ for _, test := range []struct {
+ b []byte
+ want []byte
+ wantLen int
+ }{
+ {[]byte{0x00}, []byte{}, 1},
+ {[]byte{0x01, 0x00}, []byte{0x00}, 2},
+ {[]byte{0x04, 0x01, 0x02, 0x03, 0x04}, []byte{0x01, 0x02, 0x03, 0x04}, 5},
+ } {
+ got, gotLen := consumeUint8Bytes(test.b)
+ if !bytes.Equal(got, test.want) || gotLen != test.wantLen {
+ t.Errorf("consumeUint8Bytes(%x) = {%x}, %v; want {%x}, %v", test.b, got, gotLen, test.want, test.wantLen)
+ }
+ // Extra data in the buffer is ignored.
+ b := append(test.b, 0)
+ got, gotLen = consumeUint8Bytes(b)
+ if !bytes.Equal(got, test.want) || gotLen != test.wantLen {
+ t.Errorf("consumeUint8Bytes(%x) = {%x}, %v; want {%x}, %v", b, got, gotLen, test.want, test.wantLen)
+ }
+ // Short buffer results in an error.
+ for i := 1; i <= len(test.b); i++ {
+ b = test.b[:len(test.b)-i]
+ got, gotLen := consumeUint8Bytes(b)
+ if len(got) > 0 || gotLen > 0 {
+ t.Errorf("consumeUint8Bytes(%x) = {%x}, %v; want {}, -1", b, got, gotLen)
+ }
+ }
+
+ }
+}
+
+func TestConsumeUint8BytesErrors(t *testing.T) {
+ for _, b := range [][]byte{
+ {0x01},
+ {0x04, 0x01, 0x02, 0x03},
+ } {
+ got, gotLen := consumeUint8Bytes(b)
+ if len(got) > 0 || gotLen > 0 {
+ t.Errorf("consumeUint8Bytes(%x) = {%x}, %v; want {}, -1", b, got, gotLen)
+ }
+ }
+}
+
+func TestAppendUint8Bytes(t *testing.T) {
+ var got []byte
+ got = appendUint8Bytes(got, []byte{})
+ got = appendUint8Bytes(got, []byte{0xaa, 0xbb})
+ want := []byte{
+ 0x00,
+ 0x02, 0xaa, 0xbb,
+ }
+ if !bytes.Equal(got, want) {
+ t.Errorf("appendUint8Bytes {}, {aabb} = {%x}; want {%x}", got, want)
+ }
+}
+
+func TestAppendVarintBytes(t *testing.T) {
+ var got []byte
+ got = appendVarintBytes(got, []byte{})
+ got = appendVarintBytes(got, []byte{0xaa, 0xbb})
+ want := []byte{
+ 0x00,
+ 0x02, 0xaa, 0xbb,
+ }
+ if !bytes.Equal(got, want) {
+ t.Errorf("appendVarintBytes {}, {aabb} = {%x}; want {%x}", got, want)
+ }
+}
