// 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 (
	
	
)

// MaxVarintLenN is the maximum length of a varint-encoded N-bit integer.
const (
	MaxVarintLen16 = 3
	MaxVarintLen32 = 5
	MaxVarintLen64 = 10
)

// AppendUvarint appends the varint-encoded form of x,
// as generated by PutUvarint, to buf and returns the extended buffer.
func ( []byte,  uint64) []byte {
	for  >= 0x80 {
		 = append(, byte()|0x80)
		 >>= 7
	}
	return append(, byte())
}

// PutUvarint encodes a uint64 into buf and returns the number of bytes written.
// If the buffer is too small, PutUvarint will panic.
func ( []byte,  uint64) int {
	 := 0
	for  >= 0x80 {
		[] = byte() | 0x80
		 >>= 7
		++
	}
	[] = byte()
	return  + 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 ( []byte) (uint64, int) {
	var  uint64
	var  uint
	for ,  := range  {
		if  == MaxVarintLen64 {
			// Catch byte reads past MaxVarintLen64.
			// See issue https://golang.org/issues/41185
			return 0, -( + 1) // overflow
		}
		if  < 0x80 {
			if  == MaxVarintLen64-1 &&  > 1 {
				return 0, -( + 1) // overflow
			}
			return  | uint64()<<,  + 1
		}
		 |= uint64(&0x7f) << 
		 += 7
	}
	return 0, 0
}

// AppendVarint appends the varint-encoded form of x,
// as generated by PutVarint, to buf and returns the extended buffer.
func ( []byte,  int64) []byte {
	 := uint64() << 1
	if  < 0 {
		 = ^
	}
	return AppendUvarint(, )
}

// PutVarint encodes an int64 into buf and returns the number of bytes written.
// If the buffer is too small, PutVarint will panic.
func ( []byte,  int64) int {
	 := uint64() << 1
	if  < 0 {
		 = ^
	}
	return PutUvarint(, )
}

// 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 ( []byte) (int64, int) {
	,  := Uvarint() // ok to continue in presence of error
	 := int64( >> 1)
	if &1 != 0 {
		 = ^
	}
	return , 
}

var errOverflow = errors.New("binary: varint overflows a 64-bit integer")

// ReadUvarint reads an encoded unsigned integer from r and returns it as a uint64.
// The error is EOF only if no bytes were read.
// If an EOF happens after reading some but not all the bytes,
// ReadUvarint returns io.ErrUnexpectedEOF.
func ( io.ByteReader) (uint64, error) {
	var  uint64
	var  uint
	for  := 0;  < MaxVarintLen64; ++ {
		,  := .ReadByte()
		if  != nil {
			if  > 0 &&  == io.EOF {
				 = io.ErrUnexpectedEOF
			}
			return , 
		}
		if  < 0x80 {
			if  == MaxVarintLen64-1 &&  > 1 {
				return , errOverflow
			}
			return  | uint64()<<, nil
		}
		 |= uint64(&0x7f) << 
		 += 7
	}
	return , errOverflow
}

// ReadVarint reads an encoded signed integer from r and returns it as an int64.
// The error is EOF only if no bytes were read.
// If an EOF happens after reading some but not all the bytes,
// ReadVarint returns io.ErrUnexpectedEOF.
func ( io.ByteReader) (int64, error) {
	,  := ReadUvarint() // ok to continue in presence of error
	 := int64( >> 1)
	if &1 != 0 {
		 = ^
	}
	return , 
}