1 //===- llvm/unittest/Support/LEB128Test.cpp - LEB128 function tests -------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "llvm/Support/LEB128.h"
10 #include "llvm/Support/DataTypes.h"
11 #include "llvm/Support/raw_ostream.h"
12 #include "gtest/gtest.h"
13 #include <string>
14 using namespace llvm;
15
16 namespace {
17
TEST(LEB128Test,EncodeSLEB128)18 TEST(LEB128Test, EncodeSLEB128) {
19 #define EXPECT_SLEB128_EQ(EXPECTED, VALUE, PAD) \
20 do { \
21 std::string Expected(EXPECTED, sizeof(EXPECTED) - 1); \
22 \
23 /* encodeSLEB128(uint64_t, raw_ostream &, unsigned) */ \
24 std::string Actual1; \
25 raw_string_ostream Stream(Actual1); \
26 encodeSLEB128(VALUE, Stream, PAD); \
27 Stream.flush(); \
28 EXPECT_EQ(Expected, Actual1); \
29 \
30 /* encodeSLEB128(uint64_t, uint8_t *, unsigned) */ \
31 uint8_t Buffer[32]; \
32 unsigned Size = encodeSLEB128(VALUE, Buffer, PAD); \
33 std::string Actual2(reinterpret_cast<const char *>(Buffer), Size); \
34 EXPECT_EQ(Expected, Actual2); \
35 } while (0)
36
37 // Encode SLEB128
38 EXPECT_SLEB128_EQ("\x00", 0, 0);
39 EXPECT_SLEB128_EQ("\x01", 1, 0);
40 EXPECT_SLEB128_EQ("\x7f", -1, 0);
41 EXPECT_SLEB128_EQ("\x3f", 63, 0);
42 EXPECT_SLEB128_EQ("\x41", -63, 0);
43 EXPECT_SLEB128_EQ("\x40", -64, 0);
44 EXPECT_SLEB128_EQ("\xbf\x7f", -65, 0);
45 EXPECT_SLEB128_EQ("\xc0\x00", 64, 0);
46
47 // Encode SLEB128 with some extra padding bytes
48 EXPECT_SLEB128_EQ("\x80\x00", 0, 2);
49 EXPECT_SLEB128_EQ("\x80\x80\x00", 0, 3);
50 EXPECT_SLEB128_EQ("\xff\x80\x00", 0x7f, 3);
51 EXPECT_SLEB128_EQ("\xff\x80\x80\x00", 0x7f, 4);
52 EXPECT_SLEB128_EQ("\x80\x81\x00", 0x80, 3);
53 EXPECT_SLEB128_EQ("\x80\x81\x80\x00", 0x80, 4);
54 EXPECT_SLEB128_EQ("\xc0\x7f", -0x40, 2);
55
56 EXPECT_SLEB128_EQ("\xc0\xff\x7f", -0x40, 3);
57 EXPECT_SLEB128_EQ("\x80\xff\x7f", -0x80, 3);
58 EXPECT_SLEB128_EQ("\x80\xff\xff\x7f", -0x80, 4);
59
60 #undef EXPECT_SLEB128_EQ
61 }
62
TEST(LEB128Test,EncodeULEB128)63 TEST(LEB128Test, EncodeULEB128) {
64 #define EXPECT_ULEB128_EQ(EXPECTED, VALUE, PAD) \
65 do { \
66 std::string Expected(EXPECTED, sizeof(EXPECTED) - 1); \
67 \
68 /* encodeULEB128(uint64_t, raw_ostream &, unsigned) */ \
69 std::string Actual1; \
70 raw_string_ostream Stream(Actual1); \
71 encodeULEB128(VALUE, Stream, PAD); \
72 Stream.flush(); \
73 EXPECT_EQ(Expected, Actual1); \
74 \
75 /* encodeULEB128(uint64_t, uint8_t *, unsigned) */ \
76 uint8_t Buffer[32]; \
77 unsigned Size = encodeULEB128(VALUE, Buffer, PAD); \
78 std::string Actual2(reinterpret_cast<const char *>(Buffer), Size); \
79 EXPECT_EQ(Expected, Actual2); \
80 } while (0)
81
82 // Encode ULEB128
83 EXPECT_ULEB128_EQ("\x00", 0, 0);
84 EXPECT_ULEB128_EQ("\x01", 1, 0);
85 EXPECT_ULEB128_EQ("\x3f", 63, 0);
86 EXPECT_ULEB128_EQ("\x40", 64, 0);
87 EXPECT_ULEB128_EQ("\x7f", 0x7f, 0);
88 EXPECT_ULEB128_EQ("\x80\x01", 0x80, 0);
89 EXPECT_ULEB128_EQ("\x81\x01", 0x81, 0);
90 EXPECT_ULEB128_EQ("\x90\x01", 0x90, 0);
91 EXPECT_ULEB128_EQ("\xff\x01", 0xff, 0);
92 EXPECT_ULEB128_EQ("\x80\x02", 0x100, 0);
93 EXPECT_ULEB128_EQ("\x81\x02", 0x101, 0);
94
95 // Encode ULEB128 with some extra padding bytes
96 EXPECT_ULEB128_EQ("\x80\x00", 0, 2);
97 EXPECT_ULEB128_EQ("\x80\x80\x00", 0, 3);
98 EXPECT_ULEB128_EQ("\xff\x00", 0x7f, 2);
99 EXPECT_ULEB128_EQ("\xff\x80\x00", 0x7f, 3);
100 EXPECT_ULEB128_EQ("\x80\x81\x00", 0x80, 3);
101 EXPECT_ULEB128_EQ("\x80\x81\x80\x00", 0x80, 4);
102
103 #undef EXPECT_ULEB128_EQ
104 }
105
TEST(LEB128Test,DecodeULEB128)106 TEST(LEB128Test, DecodeULEB128) {
107 #define EXPECT_DECODE_ULEB128_EQ(EXPECTED, VALUE) \
108 do { \
109 unsigned ActualSize = 0; \
110 uint64_t Actual = decodeULEB128(reinterpret_cast<const uint8_t *>(VALUE), \
111 &ActualSize); \
112 EXPECT_EQ(sizeof(VALUE) - 1, ActualSize); \
113 EXPECT_EQ(EXPECTED, Actual); \
114 } while (0)
115
116 // Don't crash
117 EXPECT_EQ(0u, decodeULEB128(nullptr, nullptr, nullptr));
118
119 // Decode ULEB128
120 EXPECT_DECODE_ULEB128_EQ(0u, "\x00");
121 EXPECT_DECODE_ULEB128_EQ(1u, "\x01");
122 EXPECT_DECODE_ULEB128_EQ(63u, "\x3f");
123 EXPECT_DECODE_ULEB128_EQ(64u, "\x40");
124 EXPECT_DECODE_ULEB128_EQ(0x7fu, "\x7f");
125 EXPECT_DECODE_ULEB128_EQ(0x80u, "\x80\x01");
126 EXPECT_DECODE_ULEB128_EQ(0x81u, "\x81\x01");
127 EXPECT_DECODE_ULEB128_EQ(0x90u, "\x90\x01");
128 EXPECT_DECODE_ULEB128_EQ(0xffu, "\xff\x01");
129 EXPECT_DECODE_ULEB128_EQ(0x100u, "\x80\x02");
130 EXPECT_DECODE_ULEB128_EQ(0x101u, "\x81\x02");
131 EXPECT_DECODE_ULEB128_EQ(4294975616ULL, "\x80\xc1\x80\x80\x10");
132
133 // Decode ULEB128 with extra padding bytes
134 EXPECT_DECODE_ULEB128_EQ(0u, "\x80\x00");
135 EXPECT_DECODE_ULEB128_EQ(0u, "\x80\x80\x00");
136 EXPECT_DECODE_ULEB128_EQ(0x7fu, "\xff\x00");
137 EXPECT_DECODE_ULEB128_EQ(0x7fu, "\xff\x80\x00");
138 EXPECT_DECODE_ULEB128_EQ(0x80u, "\x80\x81\x00");
139 EXPECT_DECODE_ULEB128_EQ(0x80u, "\x80\x81\x80\x00");
140
141 #undef EXPECT_DECODE_ULEB128_EQ
142 }
143
TEST(LEB128Test,DecodeSLEB128)144 TEST(LEB128Test, DecodeSLEB128) {
145 #define EXPECT_DECODE_SLEB128_EQ(EXPECTED, VALUE) \
146 do { \
147 unsigned ActualSize = 0; \
148 int64_t Actual = decodeSLEB128(reinterpret_cast<const uint8_t *>(VALUE), \
149 &ActualSize); \
150 EXPECT_EQ(sizeof(VALUE) - 1, ActualSize); \
151 EXPECT_EQ(EXPECTED, Actual); \
152 } while (0)
153
154 // Don't crash
155 EXPECT_EQ(0, decodeSLEB128(nullptr, nullptr, nullptr));
156
157 // Decode SLEB128
158 EXPECT_DECODE_SLEB128_EQ(0L, "\x00");
159 EXPECT_DECODE_SLEB128_EQ(1L, "\x01");
160 EXPECT_DECODE_SLEB128_EQ(63L, "\x3f");
161 EXPECT_DECODE_SLEB128_EQ(-64L, "\x40");
162 EXPECT_DECODE_SLEB128_EQ(-63L, "\x41");
163 EXPECT_DECODE_SLEB128_EQ(-1L, "\x7f");
164 EXPECT_DECODE_SLEB128_EQ(128L, "\x80\x01");
165 EXPECT_DECODE_SLEB128_EQ(129L, "\x81\x01");
166 EXPECT_DECODE_SLEB128_EQ(-129L, "\xff\x7e");
167 EXPECT_DECODE_SLEB128_EQ(-128L, "\x80\x7f");
168 EXPECT_DECODE_SLEB128_EQ(-127L, "\x81\x7f");
169 EXPECT_DECODE_SLEB128_EQ(64L, "\xc0\x00");
170 EXPECT_DECODE_SLEB128_EQ(-12345L, "\xc7\x9f\x7f");
171
172 // Decode unnormalized SLEB128 with extra padding bytes.
173 EXPECT_DECODE_SLEB128_EQ(0L, "\x80\x00");
174 EXPECT_DECODE_SLEB128_EQ(0L, "\x80\x80\x00");
175 EXPECT_DECODE_SLEB128_EQ(0x7fL, "\xff\x00");
176 EXPECT_DECODE_SLEB128_EQ(0x7fL, "\xff\x80\x00");
177 EXPECT_DECODE_SLEB128_EQ(0x80L, "\x80\x81\x00");
178 EXPECT_DECODE_SLEB128_EQ(0x80L, "\x80\x81\x80\x00");
179
180 #undef EXPECT_DECODE_SLEB128_EQ
181 }
182
TEST(LEB128Test,SLEB128Size)183 TEST(LEB128Test, SLEB128Size) {
184 // Positive Value Testing Plan:
185 // (1) 128 ^ n - 1 ........ need (n+1) bytes
186 // (2) 128 ^ n ............ need (n+1) bytes
187 // (3) 128 ^ n * 63 ....... need (n+1) bytes
188 // (4) 128 ^ n * 64 - 1 ... need (n+1) bytes
189 // (5) 128 ^ n * 64 ....... need (n+2) bytes
190
191 EXPECT_EQ(1u, getSLEB128Size(0x0LL));
192 EXPECT_EQ(1u, getSLEB128Size(0x1LL));
193 EXPECT_EQ(1u, getSLEB128Size(0x3fLL));
194 EXPECT_EQ(1u, getSLEB128Size(0x3fLL));
195 EXPECT_EQ(2u, getSLEB128Size(0x40LL));
196
197 EXPECT_EQ(2u, getSLEB128Size(0x7fLL));
198 EXPECT_EQ(2u, getSLEB128Size(0x80LL));
199 EXPECT_EQ(2u, getSLEB128Size(0x1f80LL));
200 EXPECT_EQ(2u, getSLEB128Size(0x1fffLL));
201 EXPECT_EQ(3u, getSLEB128Size(0x2000LL));
202
203 EXPECT_EQ(3u, getSLEB128Size(0x3fffLL));
204 EXPECT_EQ(3u, getSLEB128Size(0x4000LL));
205 EXPECT_EQ(3u, getSLEB128Size(0xfc000LL));
206 EXPECT_EQ(3u, getSLEB128Size(0xfffffLL));
207 EXPECT_EQ(4u, getSLEB128Size(0x100000LL));
208
209 EXPECT_EQ(4u, getSLEB128Size(0x1fffffLL));
210 EXPECT_EQ(4u, getSLEB128Size(0x200000LL));
211 EXPECT_EQ(4u, getSLEB128Size(0x7e00000LL));
212 EXPECT_EQ(4u, getSLEB128Size(0x7ffffffLL));
213 EXPECT_EQ(5u, getSLEB128Size(0x8000000LL));
214
215 EXPECT_EQ(5u, getSLEB128Size(0xfffffffLL));
216 EXPECT_EQ(5u, getSLEB128Size(0x10000000LL));
217 EXPECT_EQ(5u, getSLEB128Size(0x3f0000000LL));
218 EXPECT_EQ(5u, getSLEB128Size(0x3ffffffffLL));
219 EXPECT_EQ(6u, getSLEB128Size(0x400000000LL));
220
221 EXPECT_EQ(6u, getSLEB128Size(0x7ffffffffLL));
222 EXPECT_EQ(6u, getSLEB128Size(0x800000000LL));
223 EXPECT_EQ(6u, getSLEB128Size(0x1f800000000LL));
224 EXPECT_EQ(6u, getSLEB128Size(0x1ffffffffffLL));
225 EXPECT_EQ(7u, getSLEB128Size(0x20000000000LL));
226
227 EXPECT_EQ(7u, getSLEB128Size(0x3ffffffffffLL));
228 EXPECT_EQ(7u, getSLEB128Size(0x40000000000LL));
229 EXPECT_EQ(7u, getSLEB128Size(0xfc0000000000LL));
230 EXPECT_EQ(7u, getSLEB128Size(0xffffffffffffLL));
231 EXPECT_EQ(8u, getSLEB128Size(0x1000000000000LL));
232
233 EXPECT_EQ(8u, getSLEB128Size(0x1ffffffffffffLL));
234 EXPECT_EQ(8u, getSLEB128Size(0x2000000000000LL));
235 EXPECT_EQ(8u, getSLEB128Size(0x7e000000000000LL));
236 EXPECT_EQ(8u, getSLEB128Size(0x7fffffffffffffLL));
237 EXPECT_EQ(9u, getSLEB128Size(0x80000000000000LL));
238
239 EXPECT_EQ(9u, getSLEB128Size(0xffffffffffffffLL));
240 EXPECT_EQ(9u, getSLEB128Size(0x100000000000000LL));
241 EXPECT_EQ(9u, getSLEB128Size(0x3f00000000000000LL));
242 EXPECT_EQ(9u, getSLEB128Size(0x3fffffffffffffffLL));
243 EXPECT_EQ(10u, getSLEB128Size(0x4000000000000000LL));
244
245 EXPECT_EQ(10u, getSLEB128Size(0x7fffffffffffffffLL));
246 EXPECT_EQ(10u, getSLEB128Size(INT64_MAX));
247
248 // Negative Value Testing Plan:
249 // (1) - 128 ^ n - 1 ........ need (n+1) bytes
250 // (2) - 128 ^ n ............ need (n+1) bytes
251 // (3) - 128 ^ n * 63 ....... need (n+1) bytes
252 // (4) - 128 ^ n * 64 ....... need (n+1) bytes (different from positive one)
253 // (5) - 128 ^ n * 65 - 1 ... need (n+2) bytes (if n > 0)
254 // (6) - 128 ^ n * 65 ....... need (n+2) bytes
255
256 EXPECT_EQ(1u, getSLEB128Size(0x0LL));
257 EXPECT_EQ(1u, getSLEB128Size(-0x1LL));
258 EXPECT_EQ(1u, getSLEB128Size(-0x3fLL));
259 EXPECT_EQ(1u, getSLEB128Size(-0x40LL));
260 EXPECT_EQ(1u, getSLEB128Size(-0x40LL)); // special case
261 EXPECT_EQ(2u, getSLEB128Size(-0x41LL));
262
263 EXPECT_EQ(2u, getSLEB128Size(-0x7fLL));
264 EXPECT_EQ(2u, getSLEB128Size(-0x80LL));
265 EXPECT_EQ(2u, getSLEB128Size(-0x1f80LL));
266 EXPECT_EQ(2u, getSLEB128Size(-0x2000LL));
267 EXPECT_EQ(3u, getSLEB128Size(-0x207fLL));
268 EXPECT_EQ(3u, getSLEB128Size(-0x2080LL));
269
270 EXPECT_EQ(3u, getSLEB128Size(-0x3fffLL));
271 EXPECT_EQ(3u, getSLEB128Size(-0x4000LL));
272 EXPECT_EQ(3u, getSLEB128Size(-0xfc000LL));
273 EXPECT_EQ(3u, getSLEB128Size(-0x100000LL));
274 EXPECT_EQ(4u, getSLEB128Size(-0x103fffLL));
275 EXPECT_EQ(4u, getSLEB128Size(-0x104000LL));
276
277 EXPECT_EQ(4u, getSLEB128Size(-0x1fffffLL));
278 EXPECT_EQ(4u, getSLEB128Size(-0x200000LL));
279 EXPECT_EQ(4u, getSLEB128Size(-0x7e00000LL));
280 EXPECT_EQ(4u, getSLEB128Size(-0x8000000LL));
281 EXPECT_EQ(5u, getSLEB128Size(-0x81fffffLL));
282 EXPECT_EQ(5u, getSLEB128Size(-0x8200000LL));
283
284 EXPECT_EQ(5u, getSLEB128Size(-0xfffffffLL));
285 EXPECT_EQ(5u, getSLEB128Size(-0x10000000LL));
286 EXPECT_EQ(5u, getSLEB128Size(-0x3f0000000LL));
287 EXPECT_EQ(5u, getSLEB128Size(-0x400000000LL));
288 EXPECT_EQ(6u, getSLEB128Size(-0x40fffffffLL));
289 EXPECT_EQ(6u, getSLEB128Size(-0x410000000LL));
290
291 EXPECT_EQ(6u, getSLEB128Size(-0x7ffffffffLL));
292 EXPECT_EQ(6u, getSLEB128Size(-0x800000000LL));
293 EXPECT_EQ(6u, getSLEB128Size(-0x1f800000000LL));
294 EXPECT_EQ(6u, getSLEB128Size(-0x20000000000LL));
295 EXPECT_EQ(7u, getSLEB128Size(-0x207ffffffffLL));
296 EXPECT_EQ(7u, getSLEB128Size(-0x20800000000LL));
297
298 EXPECT_EQ(7u, getSLEB128Size(-0x3ffffffffffLL));
299 EXPECT_EQ(7u, getSLEB128Size(-0x40000000000LL));
300 EXPECT_EQ(7u, getSLEB128Size(-0xfc0000000000LL));
301 EXPECT_EQ(7u, getSLEB128Size(-0x1000000000000LL));
302 EXPECT_EQ(8u, getSLEB128Size(-0x103ffffffffffLL));
303 EXPECT_EQ(8u, getSLEB128Size(-0x1040000000000LL));
304
305 EXPECT_EQ(8u, getSLEB128Size(-0x1ffffffffffffLL));
306 EXPECT_EQ(8u, getSLEB128Size(-0x2000000000000LL));
307 EXPECT_EQ(8u, getSLEB128Size(-0x7e000000000000LL));
308 EXPECT_EQ(8u, getSLEB128Size(-0x80000000000000LL));
309 EXPECT_EQ(9u, getSLEB128Size(-0x81ffffffffffffLL));
310 EXPECT_EQ(9u, getSLEB128Size(-0x82000000000000LL));
311
312 EXPECT_EQ(9u, getSLEB128Size(-0xffffffffffffffLL));
313 EXPECT_EQ(9u, getSLEB128Size(-0x100000000000000LL));
314 EXPECT_EQ(9u, getSLEB128Size(-0x3f00000000000000LL));
315 EXPECT_EQ(9u, getSLEB128Size(-0x4000000000000000LL));
316 EXPECT_EQ(10u, getSLEB128Size(-0x40ffffffffffffffLL));
317 EXPECT_EQ(10u, getSLEB128Size(-0x4100000000000000LL));
318
319 EXPECT_EQ(10u, getSLEB128Size(-0x7fffffffffffffffLL));
320 EXPECT_EQ(10u, getSLEB128Size(-0x8000000000000000LL));
321 EXPECT_EQ(10u, getSLEB128Size(INT64_MIN));
322 }
323
TEST(LEB128Test,ULEB128Size)324 TEST(LEB128Test, ULEB128Size) {
325 // Testing Plan:
326 // (1) 128 ^ n ............ need (n+1) bytes
327 // (2) 128 ^ n * 64 ....... need (n+1) bytes
328 // (3) 128 ^ (n+1) - 1 .... need (n+1) bytes
329
330 EXPECT_EQ(1u, getULEB128Size(0)); // special case
331
332 EXPECT_EQ(1u, getULEB128Size(0x1ULL));
333 EXPECT_EQ(1u, getULEB128Size(0x40ULL));
334 EXPECT_EQ(1u, getULEB128Size(0x7fULL));
335
336 EXPECT_EQ(2u, getULEB128Size(0x80ULL));
337 EXPECT_EQ(2u, getULEB128Size(0x2000ULL));
338 EXPECT_EQ(2u, getULEB128Size(0x3fffULL));
339
340 EXPECT_EQ(3u, getULEB128Size(0x4000ULL));
341 EXPECT_EQ(3u, getULEB128Size(0x100000ULL));
342 EXPECT_EQ(3u, getULEB128Size(0x1fffffULL));
343
344 EXPECT_EQ(4u, getULEB128Size(0x200000ULL));
345 EXPECT_EQ(4u, getULEB128Size(0x8000000ULL));
346 EXPECT_EQ(4u, getULEB128Size(0xfffffffULL));
347
348 EXPECT_EQ(5u, getULEB128Size(0x10000000ULL));
349 EXPECT_EQ(5u, getULEB128Size(0x400000000ULL));
350 EXPECT_EQ(5u, getULEB128Size(0x7ffffffffULL));
351
352 EXPECT_EQ(6u, getULEB128Size(0x800000000ULL));
353 EXPECT_EQ(6u, getULEB128Size(0x20000000000ULL));
354 EXPECT_EQ(6u, getULEB128Size(0x3ffffffffffULL));
355
356 EXPECT_EQ(7u, getULEB128Size(0x40000000000ULL));
357 EXPECT_EQ(7u, getULEB128Size(0x1000000000000ULL));
358 EXPECT_EQ(7u, getULEB128Size(0x1ffffffffffffULL));
359
360 EXPECT_EQ(8u, getULEB128Size(0x2000000000000ULL));
361 EXPECT_EQ(8u, getULEB128Size(0x80000000000000ULL));
362 EXPECT_EQ(8u, getULEB128Size(0xffffffffffffffULL));
363
364 EXPECT_EQ(9u, getULEB128Size(0x100000000000000ULL));
365 EXPECT_EQ(9u, getULEB128Size(0x4000000000000000ULL));
366 EXPECT_EQ(9u, getULEB128Size(0x7fffffffffffffffULL));
367
368 EXPECT_EQ(10u, getULEB128Size(0x8000000000000000ULL));
369
370 EXPECT_EQ(10u, getULEB128Size(UINT64_MAX));
371 }
372
373 } // anonymous namespace
374