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
5package 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
27import (
28	"errors"
29	"io"
30)
31
32// MaxVarintLenN is the maximum length of a varint-encoded N-bit integer.
33const (
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.
41func 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//
60func 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.
78func 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//
94func 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
103var 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.
106func 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}
124
125// ReadVarint reads an encoded signed integer from r and returns it as an int64.
126func ReadVarint(r io.ByteReader) (int64, error) {
127	ux, err := ReadUvarint(r) // ok to continue in presence of error
128	x := int64(ux >> 1)
129	if ux&1 != 0 {
130		x = ^x
131	}
132	return x, err
133}
134