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