| // 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 ( |
| "errors" |
| "io" |
| ) |
| |
| // 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, PutUvarint will panic. |
| func PutUvarint(buf []byte, x uint64) int { |
| i := 0 |
| for x >= 0x80 { |
| buf[i] = byte(x) | 0x80 |
| x >>= 7 |
| i++ |
| } |
| buf[i] = byte(x) |
| return i + 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 Uvarint(buf []byte) (uint64, int) { |
| var x uint64 |
| var s uint |
| for i, b := range buf { |
| 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&0x7f) << s |
| s += 7 |
| } |
| return 0, 0 |
| } |
| |
| // PutVarint encodes an int64 into buf and returns the number of bytes written. |
| // If the buffer is too small, PutVarint will panic. |
| func PutVarint(buf []byte, x int64) int { |
| ux := uint64(x) << 1 |
| if x < 0 { |
| ux = ^ux |
| } |
| return PutUvarint(buf, ux) |
| } |
| |
| // 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 |
| } |
| |
| var overflow = errors.New("binary: varint overflows a 64-bit integer") |
| |
| // ReadUvarint reads an encoded unsigned integer from r and returns it as a uint64. |
| func ReadUvarint(r io.ByteReader) (uint64, error) { |
| var x uint64 |
| var s uint |
| for i := 0; ; i++ { |
| b, err := r.ReadByte() |
| if err != nil { |
| return x, err |
| } |
| 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 |
| } |
| panic("unreachable") |
| } |
| |
| // ReadVarint reads an encoded unsigned integer from r and returns it as a uint64. |
| func ReadVarint(r io.ByteReader) (int64, 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 |
| } |