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// PutUvarint encodes a uint64 into buf and returns the number of bytes written. 40// If the buffer is too small, PutUvarint will panic. 41func PutUvarint(buf []byte, x uint64) int { 42 i := 0 43 for x >= 0x80 { 44 buf[i] = byte(x) | 0x80 45 x >>= 7 46 i++ 47 } 48 buf[i] = byte(x) 49 return i + 1 50} 51 52// Uvarint decodes a uint64 from buf and returns that value and the 53// number of bytes read (> 0). If an error occurred, the value is 0 54// and the number of bytes n is <= 0 meaning: 55// 56// n == 0: buf too small 57// n < 0: value larger than 64 bits (overflow) 58// and -n is the number of bytes read 59// 60func Uvarint(buf []byte) (uint64, int) { 61 var x uint64 62 var s uint 63 for i, b := range buf { 64 if i == MaxVarintLen64 { 65 // Catch byte reads past MaxVarintLen64. 66 // See issue https://golang.org/issues/41185 67 return 0, -(i + 1) // overflow 68 } 69 if b < 0x80 { 70 if i == MaxVarintLen64-1 && b > 1 { 71 return 0, -(i + 1) // overflow 72 } 73 return x | uint64(b)<<s, i + 1 74 } 75 x |= uint64(b&0x7f) << s 76 s += 7 77 } 78 return 0, 0 79} 80 81// PutVarint encodes an int64 into buf and returns the number of bytes written. 82// If the buffer is too small, PutVarint will panic. 83func PutVarint(buf []byte, x int64) int { 84 ux := uint64(x) << 1 85 if x < 0 { 86 ux = ^ux 87 } 88 return PutUvarint(buf, ux) 89} 90 91// Varint decodes an int64 from buf and returns that value and the 92// number of bytes read (> 0). If an error occurred, the value is 0 93// and the number of bytes n is <= 0 with the following meaning: 94// 95// n == 0: buf too small 96// n < 0: value larger than 64 bits (overflow) 97// and -n is the number of bytes read 98// 99func Varint(buf []byte) (int64, int) { 100 ux, n := Uvarint(buf) // ok to continue in presence of error 101 x := int64(ux >> 1) 102 if ux&1 != 0 { 103 x = ^x 104 } 105 return x, n 106} 107 108var overflow = errors.New("binary: varint overflows a 64-bit integer") 109 110// ReadUvarint reads an encoded unsigned integer from r and returns it as a uint64. 111func ReadUvarint(r io.ByteReader) (uint64, error) { 112 var x uint64 113 var s uint 114 for i := 0; i < MaxVarintLen64; i++ { 115 b, err := r.ReadByte() 116 if err != nil { 117 return x, err 118 } 119 if b < 0x80 { 120 if i == MaxVarintLen64-1 && b > 1 { 121 return x, overflow 122 } 123 return x | uint64(b)<<s, nil 124 } 125 x |= uint64(b&0x7f) << s 126 s += 7 127 } 128 return x, overflow 129} 130 131// ReadVarint reads an encoded signed integer from r and returns it as an int64. 132func ReadVarint(r io.ByteReader) (int64, error) { 133 ux, err := ReadUvarint(r) // ok to continue in presence of error 134 x := int64(ux >> 1) 135 if ux&1 != 0 { 136 x = ^x 137 } 138 return x, err 139} 140