varint_test.gno
5.11 Kb · 201 lines
1package varint
2
3import (
4 "strings"
5 "testing"
6
7 "gno.land/p/nt/uassert/v0"
8)
9
10const (
11 minInt64 = -1 << 63
12 maxInt64 = 1<<63 - 1
13 maxUint64 = 1<<64 - 1
14)
15
16// hex renders a byte string as lowercase hex, so a failing vector prints the
17// bytes rather than mojibake.
18func hex(s string) string {
19 const digits = "0123456789abcdef"
20 var b strings.Builder
21 for i := 0; i < len(s); i++ {
22 b.WriteByte(digits[s[i]>>4])
23 b.WriteByte(digits[s[i]&0x0f])
24 }
25 return b.String()
26}
27
28// The protobuf base-128 vectors, one per group boundary plus the documented
29// 300 example and the full 64-bit maximum.
30func TestUvarintVectors(t *testing.T) {
31 cases := []struct {
32 in uint64
33 want string
34 }{
35 {0, "00"},
36 {1, "01"},
37 {127, "7f"},
38 {128, "8001"},
39 {300, "ac02"},
40 {16383, "ff7f"},
41 {16384, "808001"},
42 {maxUint64, "ffffffffffffffffff01"},
43 }
44 for _, c := range cases {
45 got := PutUvarint(c.in)
46 uassert.Equal(t, c.want, hex(got))
47
48 back, n, err := Uvarint(got)
49 uassert.NoError(t, err)
50 uassert.Equal(t, c.in, back)
51 uassert.Equal(t, len(got), n)
52 }
53}
54
55func TestLenAgreesWithEncoding(t *testing.T) {
56 for _, x := range []uint64{0, 1, 127, 128, 16383, 16384, 2097151, 2097152, maxUint64} {
57 uassert.Equal(t, len(PutUvarint(x)), Len(x))
58 }
59 // The boundary is what the groups are for: one byte up to 127.
60 uassert.Equal(t, 1, Len(127))
61 uassert.Equal(t, 2, Len(128))
62 uassert.Equal(t, MaxLen, Len(maxUint64))
63}
64
65func TestZigZagVectors(t *testing.T) {
66 cases := []struct {
67 in int64
68 want uint64
69 }{
70 {0, 0},
71 {-1, 1},
72 {1, 2},
73 {-2, 3},
74 {2, 4},
75 {maxInt64, maxUint64 - 1},
76 {minInt64, maxUint64},
77 }
78 for _, c := range cases {
79 uassert.Equal(t, c.want, ZigZag(c.in))
80 uassert.Equal(t, c.in, UnZigZag(c.want))
81 }
82}
83
84func TestVarintRoundTrip(t *testing.T) {
85 for _, x := range []int64{0, -1, 1, -64, 63, -1000000, 1000000, minInt64, maxInt64} {
86 enc := PutVarint(x)
87 uassert.Equal(t, len(enc), LenVarint(x))
88
89 back, n, err := Varint(enc)
90 uassert.NoError(t, err)
91 uassert.Equal(t, x, back)
92 uassert.Equal(t, len(enc), n)
93 }
94}
95
96// Zigzag is the whole reason signed values are not encoded directly: -1 as a
97// two's complement uint64 is ten bytes, as a zigzag it is one.
98func TestZigZagKeepsSmallNegativesShort(t *testing.T) {
99 uassert.Equal(t, 1, LenVarint(-1))
100 uassert.Equal(t, 1, LenVarint(-64))
101 uassert.Equal(t, 2, LenVarint(-65))
102 uassert.Equal(t, MaxLen, Len(uint64(0xffffffffffffffff))) // the same -1, unzigzagged
103}
104
105func TestRejectsNonCanonical(t *testing.T) {
106 cases := []struct {
107 name, in string
108 }{
109 {"zero padded once", "\x80\x00"},
110 {"one padded once", "\x81\x00"},
111 {"zero padded thrice", "\x80\x80\x80\x00"},
112 {"full width padding", "\xff\xff\xff\xff\xff\xff\xff\xff\xff\x00"},
113 }
114 for _, c := range cases {
115 _, _, err := Uvarint(c.in)
116 uassert.ErrorIs(t, err, ErrNotCanonical)
117 }
118 // A single zero byte is canonical: it is the only encoding of 0.
119 x, n, err := Uvarint("\x00")
120 uassert.NoError(t, err)
121 uassert.Equal(t, uint64(0), x)
122 uassert.Equal(t, 1, n)
123}
124
125func TestRejectsTruncated(t *testing.T) {
126 for _, s := range []string{"", "\x80", "\xff\xff", strings.Repeat("\xff", 9)} {
127 _, _, err := Uvarint(s)
128 uassert.ErrorIs(t, err, ErrTruncated)
129 }
130}
131
132func TestRejectsOverflow(t *testing.T) {
133 // Ten groups carry 70 bits; the tenth may only hold the one bit left of 64.
134 _, _, err := Uvarint(strings.Repeat("\xff", 9) + "\x02")
135 uassert.ErrorIs(t, err, ErrOverflow)
136
137 // An eleventh group is unreachable, so it reads as overflow too.
138 _, _, err = Uvarint(strings.Repeat("\xff", 10) + "\x01")
139 uassert.ErrorIs(t, err, ErrOverflow)
140
141 // Exactly at the limit is fine.
142 x, n, err := Uvarint(strings.Repeat("\xff", 9) + "\x01")
143 uassert.NoError(t, err)
144 uassert.Equal(t, uint64(maxUint64), x)
145 uassert.Equal(t, MaxLen, n)
146}
147
148func TestUvarintReadsOnlyItsOwnPrefix(t *testing.T) {
149 s := PutUvarint(300) + PutUvarint(1) + "leftover"
150 x, n, err := Uvarint(s)
151 uassert.NoError(t, err)
152 uassert.Equal(t, uint64(300), x)
153 uassert.Equal(t, 2, n)
154
155 x, n, err = Uvarint(s[n:])
156 uassert.NoError(t, err)
157 uassert.Equal(t, uint64(1), x)
158 uassert.Equal(t, 1, n)
159}
160
161func TestSequences(t *testing.T) {
162 in := []uint64{0, 1, 127, 128, 300, maxUint64}
163 enc := PutUvarints(in)
164 uassert.Equal(t, 1+1+1+2+2+10, len(enc))
165
166 out, err := Uvarints(enc)
167 uassert.NoError(t, err)
168 uassert.Equal(t, len(in), len(out))
169 for i := range in {
170 uassert.Equal(t, in[i], out[i])
171 }
172
173 signed := []int64{0, -1, 1, minInt64, maxInt64}
174 back, err := Varints(PutVarints(signed))
175 uassert.NoError(t, err)
176 uassert.Equal(t, len(signed), len(back))
177 for i := range signed {
178 uassert.Equal(t, signed[i], back[i])
179 }
180}
181
182// A partial value at the end is corruption, and returning the values read so
183// far would hand a caller a silently short list.
184func TestSequenceRefusesTrailingFragment(t *testing.T) {
185 _, err := Uvarints(PutUvarint(300) + "\x80")
186 uassert.ErrorIs(t, err, ErrTrailing)
187
188 _, err = Varints(PutVarint(-5) + "\xff")
189 uassert.ErrorIs(t, err, ErrTrailing)
190
191 out, err := Uvarints("")
192 uassert.NoError(t, err)
193 uassert.Equal(t, 0, len(out))
194}
195
196func TestAppendBuildsInPlace(t *testing.T) {
197 var buf []byte
198 buf = AppendUvarint(buf, 300)
199 buf = AppendVarint(buf, -1)
200 uassert.Equal(t, "ac0201", hex(string(buf)))
201}
