// 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 b < 0x80 {			if i > 9 || i == 9 && b > 1 {				return 0, -(i + 1) // overflow			}			return x | uint64(b)<<s, i + 1		}		x |= uint64(b&0x7f) << s		s += 7	}	return 0, 0} // PutVarint encodes an int64 into buf and returns the number of bytes written.// If the buffer is too small, PutVarint will panic.func PutVarint(buf []byte, x int64) int {	ux := uint64(x) << 1	if x < 0 {		ux = ^ux	}	return PutUvarint(buf, ux)} // Varint decodes an int64 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 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++ {		b, err := r.ReadByte()		if err != nil {			return x, err		}		if b < 0x80 {			if i > 9 || i == 9 && b > 1 {				return x, overflow			}			return x | uint64(b)<<s, nil		}		x |= uint64(b&0x7f) << s		s += 7	}} // ReadVarint reads an encoded signed integer from r and returns it as an int64.func ReadVarint(r io.ByteReader) (int64, error) {	ux, err := ReadUvarint(r) // ok to continue in presence of error	x := int64(ux >> 1)	if ux&1 != 0 {		x = ^x	}	return x, err}