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

View as plain text