Source file src/pkg/encoding/binary/varint.go

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