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 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 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 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 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 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 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