1// Copyright 2011 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package binary
6
7// This file implements "varint" encoding of 64-bit integers.
8// The encoding is:
9// - unsigned integers are serialized 7 bits at a time, starting with the
10//   least significant bits
11// - the most significant bit (msb) in each output byte indicates if there
12//   is a continuation byte (msb = 1)
13// - signed integers are mapped to unsigned integers using "zig-zag"
14//   encoding: Positive values x are written as 2*x + 0, negative values
15//   are written as 2*(^x) + 1; that is, negative numbers are complemented
16//   and whether to complement is encoded in bit 0.
17//
18// Design note:
19// At most 10 bytes are needed for 64-bit values. The encoding could
20// be more dense: a full 64-bit value needs an extra byte just to hold bit 63.
21// Instead, the msb of the previous byte could be used to hold bit 63 since we
22// know there can't be more than 64 bits. This is a trivial improvement and
23// would reduce the maximum encoding length to 9 bytes. However, it breaks the
24// invariant that the msb is always the "continuation bit" and thus makes the
25// format incompatible with a varint encoding for larger numbers (say 128-bit).
26
27import (
28	"errors"
29	"io"
30)
31
32// MaxVarintLenN is the maximum length of a varint-encoded N-bit integer.
33const (
34	MaxVarintLen16 = 3
35	MaxVarintLen32 = 5
36	MaxVarintLen64 = 10
37)
38
39// AppendUvarint appends the varint-encoded form of x,
40// as generated by [PutUvarint], to buf and returns the extended buffer.
41func AppendUvarint(buf []byte, x uint64) []byte {
42	for x >= 0x80 {
43		buf = append(buf, byte(x)|0x80)
44		x >>= 7
45	}
46	return append(buf, byte(x))
47}
48
49// PutUvarint encodes a uint64 into buf and returns the number of bytes written.
50// If the buffer is too small, PutUvarint will panic.
51func PutUvarint(buf []byte, x uint64) int {
52	i := 0
53	for x >= 0x80 {
54		buf[i] = byte(x) | 0x80
55		x >>= 7
56		i++
57	}
58	buf[i] = byte(x)
59	return i + 1
60}
61
62// Uvarint decodes a uint64 from buf and returns that value and the
63// number of bytes read (> 0). If an error occurred, the value is 0
64// and the number of bytes n is <= 0 meaning:
65//   - n == 0: buf too small;
66//   - n < 0: value larger than 64 bits (overflow) and -n is the number of
67//     bytes read.
68func Uvarint(buf []byte) (uint64, int) {
69	var x uint64
70	var s uint
71	for i, b := range buf {
72		if i == MaxVarintLen64 {
73			// Catch byte reads past MaxVarintLen64.
74			// See issue https://golang.org/issues/41185
75			return 0, -(i + 1) // overflow
76		}
77		if b < 0x80 {
78			if i == MaxVarintLen64-1 && b > 1 {
79				return 0, -(i + 1) // overflow
80			}
81			return x | uint64(b)<<s, i + 1
82		}
83		x |= uint64(b&0x7f) << s
84		s += 7
85	}
86	return 0, 0
87}
88
89// AppendVarint appends the varint-encoded form of x,
90// as generated by [PutVarint], to buf and returns the extended buffer.
91func AppendVarint(buf []byte, x int64) []byte {
92	ux := uint64(x) << 1
93	if x < 0 {
94		ux = ^ux
95	}
96	return AppendUvarint(buf, ux)
97}
98
99// PutVarint encodes an int64 into buf and returns the number of bytes written.
100// If the buffer is too small, PutVarint will panic.
101func PutVarint(buf []byte, x int64) int {
102	ux := uint64(x) << 1
103	if x < 0 {
104		ux = ^ux
105	}
106	return PutUvarint(buf, ux)
107}
108
109// Varint decodes an int64 from buf and returns that value and the
110// number of bytes read (> 0). If an error occurred, the value is 0
111// and the number of bytes n is <= 0 with the following meaning:
112//   - n == 0: buf too small;
113//   - n < 0: value larger than 64 bits (overflow)
114//     and -n is the number of bytes read.
115func Varint(buf []byte) (int64, int) {
116	ux, n := Uvarint(buf) // ok to continue in presence of error
117	x := int64(ux >> 1)
118	if ux&1 != 0 {
119		x = ^x
120	}
121	return x, n
122}
123
124var errOverflow = errors.New("binary: varint overflows a 64-bit integer")
125
126// ReadUvarint reads an encoded unsigned integer from r and returns it as a uint64.
127// The error is [io.EOF] only if no bytes were read.
128// If an [io.EOF] happens after reading some but not all the bytes,
129// ReadUvarint returns [io.ErrUnexpectedEOF].
130func ReadUvarint(r io.ByteReader) (uint64, error) {
131	var x uint64
132	var s uint
133	for i := 0; i < MaxVarintLen64; i++ {
134		b, err := r.ReadByte()
135		if err != nil {
136			if i > 0 && err == io.EOF {
137				err = io.ErrUnexpectedEOF
138			}
139			return x, err
140		}
141		if b < 0x80 {
142			if i == MaxVarintLen64-1 && b > 1 {
143				return x, errOverflow
144			}
145			return x | uint64(b)<<s, nil
146		}
147		x |= uint64(b&0x7f) << s
148		s += 7
149	}
150	return x, errOverflow
151}
152
153// ReadVarint reads an encoded signed integer from r and returns it as an int64.
154// The error is [io.EOF] only if no bytes were read.
155// If an [io.EOF] happens after reading some but not all the bytes,
156// ReadVarint returns [io.ErrUnexpectedEOF].
157func ReadVarint(r io.ByteReader) (int64, error) {
158	ux, err := ReadUvarint(r) // ok to continue in presence of error
159	x := int64(ux >> 1)
160	if ux&1 != 0 {
161		x = ^x
162	}
163	return x, err
164}
165