code review 5146048: encoding/binary: support for varint encoding

src/pkg/encoding/binary/varint.go

 // 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 (
         "io"
         "os"
 )
 
-// PutUint encodes a uint64 into buf and returns the number of bytes written.
-// If the buffer is to small, the result is 0.
-func PutUint(buf []byte, x uint64) int {
-        for i := range buf {
-                if x < 128 {
+// 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, the result is the negated number of bytes required
+// (that is, -PutUvarint(nil, x) is the number of bytes required to encode x).
+func PutUvarint(buf []byte, x uint64) int {
+        var i int
+        for i = range buf {
+                if x < 0x80 {
                         buf[i] = byte(x)
                         return i + 1
                 }
-                buf[i] = byte(x) | 128
+                buf[i] = byte(x) | 0x80
                 x >>= 7
         }
-        return 0 // error: buffer too small
+        // buffer too small; compute number of bytes required
+        for x >= 0x4000 {
+                x >>= 2 * 7
+                i += 2
+        }
+        if x >= 0x80 {
+                i++
+        }
+        return -(i + 1)
 }
 
-// Uint decodes a uint64 from buf and returns that value and the
-// number of bytes read. If the buffer is too small, the value is
-// undefined and the number of bytes is 0. At most 11 bytes are read.
-func Uint(buf []byte) (uint64, int) {
+// 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 < 128 || i >= 10 {
+                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&127) << s
+                x |= uint64(b&0x7f) << s
                 s += 7
         }
-        return x, 0
+        return 0, 0
 }
 
-// PutInt encodes an int64 into buf and returns the number of bytes written.
-// If the buffer is to small, the result is 0.
-func PutInt(buf []byte, x int64) int {
+// PutVarint encodes an int64 into buf and returns the number of bytes written.
+// If the buffer is too small, the result is the negated number of bytes required
+// (that is, -PutVarint(nil, x) is the number of bytes required to encode x).
+func PutVarint(buf []byte, x int64) int {
         ux := uint64(x) << 1
         if x < 0 {
                 ux = ^ux
         }
-        return PutUint(buf, ux)
+        return PutUvarint(buf, ux)
 }
 
-// Int decodes an int64 from buf and returns that value and the
-// number of bytes read. If the buffer is too small, the value is
-// undefined and the number of bytes is 0. At most 11 bytes are read.
-func Int(buf []byte) (int64, int) {
-        ux, n := Uint(buf) // ok to continue in presence of error
+// 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
 }
 
-// WriteUint writes a uint64 to w.
-func WriteUint(w io.Writer, x uint64) os.Error {
-        var buf [10]byte
-        n := PutUint(buf[:], x) // won't fail
+// WriteUvarint encodes x and writes the result to w.
+func WriteUvarint(w io.Writer, x uint64) os.Error {
+        var buf [MaxVarintLen64]byte
+        n := PutUvarint(buf[:], x) // won't fail
         _, err := w.Write(buf[0:n])
         return err
 }
 
-var overflow = os.NewError("overflow: not a 64bit integer")
+var overflow = os.NewError("binary: varint overflows a 64-bit integer")
 
-// ReadUint reads a uint64 from r.
-func ReadUint(r io.ByteReader) (uint64, os.Error) {
+// ReadUvarint reads an encoded unsigned integer from r and returns it as a uint64.
+func ReadUvarint(r io.ByteReader) (uint64, os.Error) {
         var x uint64
         var s uint
-        for i := 0; i < 10; i++ {
+        for i := 0; ; i++ {
                 b, err := r.ReadByte()
-                if b < 128 || err != nil {
-                        return x | uint64(b)<<s, err
+                if err != nil {
+                        return x, err
                 }
-                x |= uint64(b&127) << s
+                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
         }
-        return x, overflow
+        panic("unreachable")
 }
 
-// WriteInt writes a uint64 to w.
-func WriteInt(w io.Writer, x int64) os.Error {
+// WriteVarint encodes x and writes the result to w.
+func WriteVarint(w io.Writer, x int64) os.Error {
         ux := uint64(x) << 1
         if x < 0 {
                 ux = ^ux
         }
-        return WriteUint(w, ux)
+        return WriteUvarint(w, ux)
 }
 
-// ReadInt reads a uint64 from r.
-func ReadInt(r io.ByteReader) (int64, os.Error) {
-        ux, err := ReadUint(r) // ok to continue in presence of error
+// ReadVarint reads an encoded unsigned integer from r and returns it as a uint64.
+func ReadVarint(r io.ByteReader) (int64, os.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
 }