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 5 package 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 27 import (
28 "errors"
29 "io"
30 )
31 32 // MaxVarintLenN is the maximum length of a varint-encoded N-bit integer.
33 const (
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.
41 func 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.
51 func 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.
68 func 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.
91 func 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.
101 func 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.
115 func 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 124 var 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].
130 func 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].
157 func 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