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