// Copyright 2011 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 binary // This file implements "varint" encoding of 64-bit integers. // The encoding is: // - unsigned integers are serialized 7 bits at a time, starting with the // least significant bits // - the most significant bit (msb) in each output byte indicates if there // is a continuation byte (msb = 1) // - signed integers are mapped to unsigned integers using "zig-zag" // encoding: Positive values x are written as 2*x + 0, negative values // are written as 2*(^x) + 1; that is, negative numbers are complemented // and whether to complement is encoded in bit 0. // // Design note: // At most 10 bytes are needed for 64-bit values. The encoding could // be more dense: a full 64-bit value needs an extra byte just to hold bit 63. // Instead, the msb of the previous byte could be used to hold bit 63 since we // know there can't be more than 64 bits. This is a trivial improvement and // would reduce the maximum encoding length to 9 bytes. However, it breaks the // invariant that the msb is always the "continuation bit" and thus makes the // format incompatible with a varint encoding for larger numbers (say 128-bit). import ( "errors" "io" ) // MaxVarintLenN is the maximum length of a varint-encoded N-bit integer. const ( MaxVarintLen16 = 3 MaxVarintLen32 = 5 MaxVarintLen64 = 10 ) // PutUvarint encodes a uint64 into buf and returns the number of bytes written. // If the buffer is too small, PutUvarint will panic. func PutUvarint(buf []byte, x uint64) int { i := 0 for x >= 0x80 { buf[i] = byte(x) | 0x80 x >>= 7 i++ } buf[i] = byte(x) return i + 1 } // Uvarint decodes a uint64 from buf and returns that value and the // number of bytes read (> 0). If an error occurred, the value is 0 // and the number of bytes n is <= 0 meaning: // // n == 0: buf too small // n < 0: value larger than 64 bits (overflow) // and -n is the number of bytes read // func Uvarint(buf []byte) (uint64, int) { var x uint64 var s uint for i, b := range buf { if i == MaxVarintLen64 { // Catch byte reads past MaxVarintLen64. // See issue https://golang.org/issues/41185 return 0, -(i + 1) // overflow } if b < 0x80 { if i == MaxVarintLen64-1 && b > 1 { return 0, -(i + 1) // overflow } return x | uint64(b)< 0). If an error occurred, the value is 0 // and the number of bytes n is <= 0 with the following meaning: // // n == 0: buf too small // n < 0: value larger than 64 bits (overflow) // and -n is the number of bytes read // func Varint(buf []byte) (int64, int) { ux, n := Uvarint(buf) // ok to continue in presence of error x := int64(ux >> 1) if ux&1 != 0 { x = ^x } return x, n } var overflow = errors.New("binary: varint overflows a 64-bit integer") // ReadUvarint reads an encoded unsigned integer from r and returns it as a uint64. func ReadUvarint(r io.ByteReader) (uint64, error) { var x uint64 var s uint for i := 0; i < MaxVarintLen64; i++ { b, err := r.ReadByte() if err != nil { return x, err } if b < 0x80 { if i == MaxVarintLen64-1 && b > 1 { return x, overflow } return x | uint64(b)<> 1) if ux&1 != 0 { x = ^x } return x, err }