varint.gno

  1// Package varint implements LEB128 / protobuf-style variable-length integers
  2// over strings, with one deliberate restriction: it only accepts the canonical
  3// encoding of a value.
  4//
  5// A varint stores an integer in base 128, least significant group first. Each
  6// byte carries seven payload bits and a continuation bit in the high position,
  7// so values below 128 cost one byte, below 16384 two, and a full uint64 at most
  8// ten. Signed values go through zigzag first, which interleaves positives and
  9// negatives so that small magnitudes of either sign stay short.
 10//
 11// Live demo: [r/moul/x/daily/varintdemo](/r/moul/x/daily/varintdemo/v0).
 12package varint
 13
 14import "errors"
 15
 16// MaxLen is the longest canonical encoding of a uint64: ten groups of seven
 17// bits covers 70 bits, which is the first multiple of seven past 64.
 18const MaxLen = 10
 19
 20var (
 21	// ErrTruncated is returned when the input ends inside a varint, meaning
 22	// the last byte read still had its continuation bit set.
 23	ErrTruncated = errors.New("varint: truncated")
 24	// ErrOverflow is returned when the encoded value does not fit in 64 bits.
 25	ErrOverflow = errors.New("varint: value overflows uint64")
 26	// ErrNotCanonical is returned for an encoding that is longer than it needs
 27	// to be, such as a value padded with trailing continuation groups.
 28	ErrNotCanonical = errors.New("varint: non-canonical encoding")
 29	// ErrTrailing is returned by the all-at-once decoders when bytes remain
 30	// after the last complete value.
 31	ErrTrailing = errors.New("varint: trailing bytes")
 32)
 33
 34// PutUvarint returns the canonical encoding of x.
 35func PutUvarint(x uint64) string {
 36	return string(AppendUvarint(make([]byte, 0, MaxLen), x))
 37}
 38
 39// AppendUvarint appends the encoding of x to dst and returns the extended
 40// slice, the same shape as Go's encoding/binary.
 41//
 42// It takes a byte slice and not a string on purpose: a string accumulator
 43// copies the whole prefix on every append, which makes packing a sequence
 44// quadratic in the encoded size. On chain that is gas paid to rebuild bytes
 45// the caller already had.
 46func AppendUvarint(dst []byte, x uint64) []byte {
 47	for x >= 0x80 {
 48		dst = append(dst, byte(x)|0x80)
 49		x >>= 7
 50	}
 51	return append(dst, byte(x))
 52}
 53
 54// PutVarint returns the canonical encoding of x, zigzagged first.
 55func PutVarint(x int64) string {
 56	return PutUvarint(ZigZag(x))
 57}
 58
 59// AppendVarint appends the zigzagged encoding of x to dst.
 60func AppendVarint(dst []byte, x int64) []byte {
 61	return AppendUvarint(dst, ZigZag(x))
 62}
 63
 64// Len reports how many bytes PutUvarint(x) would produce, without encoding it.
 65func Len(x uint64) int {
 66	n := 1
 67	for x >= 0x80 {
 68		x >>= 7
 69		n++
 70	}
 71	return n
 72}
 73
 74// LenVarint reports how many bytes PutVarint(x) would produce.
 75func LenVarint(x int64) int {
 76	return Len(ZigZag(x))
 77}
 78
 79// Uvarint decodes the varint at the start of s and reports how many bytes it
 80// consumed. The rest of s is ignored, so a stream is read by reslicing.
 81func Uvarint(s string) (uint64, int, error) {
 82	var x uint64
 83	var shift uint
 84	for i := 0; i < len(s); i++ {
 85		b := s[i]
 86		if i == MaxLen-1 {
 87			// The tenth group may only carry the single bit left over from
 88			// 63; anything above that, continuation included, overflows.
 89			if b > 1 {
 90				return 0, 0, ErrOverflow
 91			}
 92		}
 93		x |= uint64(b&0x7f) << shift
 94		if b < 0x80 {
 95			if i > 0 && b == 0 {
 96				// A zero final group means the value was padded: the same
 97				// number has a shorter encoding, so this one is not canonical.
 98				return 0, 0, ErrNotCanonical
 99			}
100			return x, i + 1, nil
101		}
102		shift += 7
103	}
104	return 0, 0, ErrTruncated
105}
106
107// Varint decodes the zigzagged varint at the start of s.
108func Varint(s string) (int64, int, error) {
109	u, n, err := Uvarint(s)
110	if err != nil {
111		return 0, 0, err
112	}
113	return UnZigZag(u), n, nil
114}
115
116// ZigZag maps a signed value onto an unsigned one so that small magnitudes of
117// either sign stay small: 0, -1, 1, -2, 2 become 0, 1, 2, 3, 4.
118func ZigZag(x int64) uint64 {
119	return uint64(x<<1) ^ uint64(x>>63)
120}
121
122// UnZigZag is the inverse of [ZigZag].
123func UnZigZag(u uint64) int64 {
124	return int64(u>>1) ^ -int64(u&1)
125}
126
127// PutUvarints encodes every value in xs back to back, into one buffer.
128func PutUvarints(xs []uint64) string {
129	buf := make([]byte, 0, len(xs)+1)
130	for _, x := range xs {
131		buf = AppendUvarint(buf, x)
132	}
133	return string(buf)
134}
135
136// Uvarints decodes a string that is nothing but varints. It fails rather than
137// returning a partial result: a trailing fragment is corruption, not a value.
138func Uvarints(s string) ([]uint64, error) {
139	out := []uint64{}
140	for len(s) > 0 {
141		x, n, err := Uvarint(s)
142		if err != nil {
143			if err == ErrTruncated {
144				return nil, ErrTrailing
145			}
146			return nil, err
147		}
148		out = append(out, x)
149		s = s[n:]
150	}
151	return out, nil
152}
153
154// PutVarints encodes every value in xs back to back, zigzagged, into one
155// buffer.
156func PutVarints(xs []int64) string {
157	buf := make([]byte, 0, len(xs)+1)
158	for _, x := range xs {
159		buf = AppendVarint(buf, x)
160	}
161	return string(buf)
162}
163
164// Varints decodes a string that is nothing but zigzagged varints.
165func Varints(s string) ([]int64, error) {
166	us, err := Uvarints(s)
167	if err != nil {
168		return nil, err
169	}
170	out := make([]int64, len(us))
171	for i, u := range us {
172		out[i] = UnZigZag(u)
173	}
174	return out, nil
175}