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