unittests/Support/LEB128Test.cpp

   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   // Decode ULEB128
 117   EXPECT_DECODE_ULEB128_EQ(0u, "\x00");
 118   EXPECT_DECODE_ULEB128_EQ(1u, "\x01");
 119   EXPECT_DECODE_ULEB128_EQ(63u, "\x3f");
 120   EXPECT_DECODE_ULEB128_EQ(64u, "\x40");
 121   EXPECT_DECODE_ULEB128_EQ(0x7fu, "\x7f");
 122   EXPECT_DECODE_ULEB128_EQ(0x80u, "\x80\x01");
 123   EXPECT_DECODE_ULEB128_EQ(0x81u, "\x81\x01");
 124   EXPECT_DECODE_ULEB128_EQ(0x90u, "\x90\x01");
 125   EXPECT_DECODE_ULEB128_EQ(0xffu, "\xff\x01");
 126   EXPECT_DECODE_ULEB128_EQ(0x100u, "\x80\x02");
 127   EXPECT_DECODE_ULEB128_EQ(0x101u, "\x81\x02");
 128   EXPECT_DECODE_ULEB128_EQ(4294975616ULL, "\x80\xc1\x80\x80\x10");
 129
 130   // Decode ULEB128 with extra padding bytes
 131   EXPECT_DECODE_ULEB128_EQ(0u, "\x80\x00");
 132   EXPECT_DECODE_ULEB128_EQ(0u, "\x80\x80\x00");
 133   EXPECT_DECODE_ULEB128_EQ(0x7fu, "\xff\x00");
 134   EXPECT_DECODE_ULEB128_EQ(0x7fu, "\xff\x80\x00");
 135   EXPECT_DECODE_ULEB128_EQ(0x80u, "\x80\x81\x00");
 136   EXPECT_DECODE_ULEB128_EQ(0x80u, "\x80\x81\x80\x00");
 137
 138 #undef EXPECT_DECODE_ULEB128_EQ
 139 }
 140
 141 TEST(LEB128Test, DecodeSLEB128) {
 142 #define EXPECT_DECODE_SLEB128_EQ(EXPECTED, VALUE) \
 143   do { \
 144     unsigned ActualSize = 0; \
 145     int64_t Actual = decodeSLEB128(reinterpret_cast<const uint8_t *>(VALUE), \
 146                                     &ActualSize); \
 147     EXPECT_EQ(sizeof(VALUE) - 1, ActualSize); \
 148     EXPECT_EQ(EXPECTED, Actual); \
 149   } while (0)
 150
 151   // Decode SLEB128
 152   EXPECT_DECODE_SLEB128_EQ(0L, "\x00");
 153   EXPECT_DECODE_SLEB128_EQ(1L, "\x01");
 154   EXPECT_DECODE_SLEB128_EQ(63L, "\x3f");
 155   EXPECT_DECODE_SLEB128_EQ(-64L, "\x40");
 156   EXPECT_DECODE_SLEB128_EQ(-63L, "\x41");
 157   EXPECT_DECODE_SLEB128_EQ(-1L, "\x7f");
 158   EXPECT_DECODE_SLEB128_EQ(128L, "\x80\x01");
 159   EXPECT_DECODE_SLEB128_EQ(129L, "\x81\x01");
 160   EXPECT_DECODE_SLEB128_EQ(-129L, "\xff\x7e");
 161   EXPECT_DECODE_SLEB128_EQ(-128L, "\x80\x7f");
 162   EXPECT_DECODE_SLEB128_EQ(-127L, "\x81\x7f");
 163   EXPECT_DECODE_SLEB128_EQ(64L, "\xc0\x00");
 164   EXPECT_DECODE_SLEB128_EQ(-12345L, "\xc7\x9f\x7f");
 165
 166   // Decode unnormalized SLEB128 with extra padding bytes.
 167   EXPECT_DECODE_SLEB128_EQ(0L, "\x80\x00");
 168   EXPECT_DECODE_SLEB128_EQ(0L, "\x80\x80\x00");
 169   EXPECT_DECODE_SLEB128_EQ(0x7fL, "\xff\x00");
 170   EXPECT_DECODE_SLEB128_EQ(0x7fL, "\xff\x80\x00");
 171   EXPECT_DECODE_SLEB128_EQ(0x80L, "\x80\x81\x00");
 172   EXPECT_DECODE_SLEB128_EQ(0x80L, "\x80\x81\x80\x00");
 173
 174 #undef EXPECT_DECODE_SLEB128_EQ
 175 }
 176
 177 TEST(LEB128Test, SLEB128Size) {
 178   // Positive Value Testing Plan:
 179   // (1) 128 ^ n - 1 ........ need (n+1) bytes
 180   // (2) 128 ^ n ............ need (n+1) bytes
 181   // (3) 128 ^ n * 63 ....... need (n+1) bytes
 182   // (4) 128 ^ n * 64 - 1 ... need (n+1) bytes
 183   // (5) 128 ^ n * 64 ....... need (n+2) bytes
 184
 185   EXPECT_EQ(1u, getSLEB128Size(0x0LL));
 186   EXPECT_EQ(1u, getSLEB128Size(0x1LL));
 187   EXPECT_EQ(1u, getSLEB128Size(0x3fLL));
 188   EXPECT_EQ(1u, getSLEB128Size(0x3fLL));
 189   EXPECT_EQ(2u, getSLEB128Size(0x40LL));
 190
 191   EXPECT_EQ(2u, getSLEB128Size(0x7fLL));
 192   EXPECT_EQ(2u, getSLEB128Size(0x80LL));
 193   EXPECT_EQ(2u, getSLEB128Size(0x1f80LL));
 194   EXPECT_EQ(2u, getSLEB128Size(0x1fffLL));
 195   EXPECT_EQ(3u, getSLEB128Size(0x2000LL));
 196
 197   EXPECT_EQ(3u, getSLEB128Size(0x3fffLL));
 198   EXPECT_EQ(3u, getSLEB128Size(0x4000LL));
 199   EXPECT_EQ(3u, getSLEB128Size(0xfc000LL));
 200   EXPECT_EQ(3u, getSLEB128Size(0xfffffLL));
 201   EXPECT_EQ(4u, getSLEB128Size(0x100000LL));
 202
 203   EXPECT_EQ(4u, getSLEB128Size(0x1fffffLL));
 204   EXPECT_EQ(4u, getSLEB128Size(0x200000LL));
 205   EXPECT_EQ(4u, getSLEB128Size(0x7e00000LL));
 206   EXPECT_EQ(4u, getSLEB128Size(0x7ffffffLL));
 207   EXPECT_EQ(5u, getSLEB128Size(0x8000000LL));
 208
 209   EXPECT_EQ(5u, getSLEB128Size(0xfffffffLL));
 210   EXPECT_EQ(5u, getSLEB128Size(0x10000000LL));
 211   EXPECT_EQ(5u, getSLEB128Size(0x3f0000000LL));
 212   EXPECT_EQ(5u, getSLEB128Size(0x3ffffffffLL));
 213   EXPECT_EQ(6u, getSLEB128Size(0x400000000LL));
 214
 215   EXPECT_EQ(6u, getSLEB128Size(0x7ffffffffLL));
 216   EXPECT_EQ(6u, getSLEB128Size(0x800000000LL));
 217   EXPECT_EQ(6u, getSLEB128Size(0x1f800000000LL));
 218   EXPECT_EQ(6u, getSLEB128Size(0x1ffffffffffLL));
 219   EXPECT_EQ(7u, getSLEB128Size(0x20000000000LL));
 220
 221   EXPECT_EQ(7u, getSLEB128Size(0x3ffffffffffLL));
 222   EXPECT_EQ(7u, getSLEB128Size(0x40000000000LL));
 223   EXPECT_EQ(7u, getSLEB128Size(0xfc0000000000LL));
 224   EXPECT_EQ(7u, getSLEB128Size(0xffffffffffffLL));
 225   EXPECT_EQ(8u, getSLEB128Size(0x1000000000000LL));
 226
 227   EXPECT_EQ(8u, getSLEB128Size(0x1ffffffffffffLL));
 228   EXPECT_EQ(8u, getSLEB128Size(0x2000000000000LL));
 229   EXPECT_EQ(8u, getSLEB128Size(0x7e000000000000LL));
 230   EXPECT_EQ(8u, getSLEB128Size(0x7fffffffffffffLL));
 231   EXPECT_EQ(9u, getSLEB128Size(0x80000000000000LL));
 232
 233   EXPECT_EQ(9u, getSLEB128Size(0xffffffffffffffLL));
 234   EXPECT_EQ(9u, getSLEB128Size(0x100000000000000LL));
 235   EXPECT_EQ(9u, getSLEB128Size(0x3f00000000000000LL));
 236   EXPECT_EQ(9u, getSLEB128Size(0x3fffffffffffffffLL));
 237   EXPECT_EQ(10u, getSLEB128Size(0x4000000000000000LL));
 238
 239   EXPECT_EQ(10u, getSLEB128Size(0x7fffffffffffffffLL));
 240   EXPECT_EQ(10u, getSLEB128Size(INT64_MAX));
 241
 242   // Negative Value Testing Plan:
 243   // (1) - 128 ^ n - 1 ........ need (n+1) bytes
 244   // (2) - 128 ^ n ............ need (n+1) bytes
 245   // (3) - 128 ^ n * 63 ....... need (n+1) bytes
 246   // (4) - 128 ^ n * 64 ....... need (n+1) bytes (different from positive one)
 247   // (5) - 128 ^ n * 65 - 1 ... need (n+2) bytes (if n > 0)
 248   // (6) - 128 ^ n * 65 ....... need (n+2) bytes
 249
 250   EXPECT_EQ(1u, getSLEB128Size(0x0LL));
 251   EXPECT_EQ(1u, getSLEB128Size(-0x1LL));
 252   EXPECT_EQ(1u, getSLEB128Size(-0x3fLL));
 253   EXPECT_EQ(1u, getSLEB128Size(-0x40LL));
 254   EXPECT_EQ(1u, getSLEB128Size(-0x40LL)); // special case
 255   EXPECT_EQ(2u, getSLEB128Size(-0x41LL));
 256
 257   EXPECT_EQ(2u, getSLEB128Size(-0x7fLL));
 258   EXPECT_EQ(2u, getSLEB128Size(-0x80LL));
 259   EXPECT_EQ(2u, getSLEB128Size(-0x1f80LL));
 260   EXPECT_EQ(2u, getSLEB128Size(-0x2000LL));
 261   EXPECT_EQ(3u, getSLEB128Size(-0x207fLL));
 262   EXPECT_EQ(3u, getSLEB128Size(-0x2080LL));
 263
 264   EXPECT_EQ(3u, getSLEB128Size(-0x3fffLL));
 265   EXPECT_EQ(3u, getSLEB128Size(-0x4000LL));
 266   EXPECT_EQ(3u, getSLEB128Size(-0xfc000LL));
 267   EXPECT_EQ(3u, getSLEB128Size(-0x100000LL));
 268   EXPECT_EQ(4u, getSLEB128Size(-0x103fffLL));
 269   EXPECT_EQ(4u, getSLEB128Size(-0x104000LL));
 270
 271   EXPECT_EQ(4u, getSLEB128Size(-0x1fffffLL));
 272   EXPECT_EQ(4u, getSLEB128Size(-0x200000LL));
 273   EXPECT_EQ(4u, getSLEB128Size(-0x7e00000LL));
 274   EXPECT_EQ(4u, getSLEB128Size(-0x8000000LL));
 275   EXPECT_EQ(5u, getSLEB128Size(-0x81fffffLL));
 276   EXPECT_EQ(5u, getSLEB128Size(-0x8200000LL));
 277
 278   EXPECT_EQ(5u, getSLEB128Size(-0xfffffffLL));
 279   EXPECT_EQ(5u, getSLEB128Size(-0x10000000LL));
 280   EXPECT_EQ(5u, getSLEB128Size(-0x3f0000000LL));
 281   EXPECT_EQ(5u, getSLEB128Size(-0x400000000LL));
 282   EXPECT_EQ(6u, getSLEB128Size(-0x40fffffffLL));
 283   EXPECT_EQ(6u, getSLEB128Size(-0x410000000LL));
 284
 285   EXPECT_EQ(6u, getSLEB128Size(-0x7ffffffffLL));
 286   EXPECT_EQ(6u, getSLEB128Size(-0x800000000LL));
 287   EXPECT_EQ(6u, getSLEB128Size(-0x1f800000000LL));
 288   EXPECT_EQ(6u, getSLEB128Size(-0x20000000000LL));
 289   EXPECT_EQ(7u, getSLEB128Size(-0x207ffffffffLL));
 290   EXPECT_EQ(7u, getSLEB128Size(-0x20800000000LL));
 291
 292   EXPECT_EQ(7u, getSLEB128Size(-0x3ffffffffffLL));
 293   EXPECT_EQ(7u, getSLEB128Size(-0x40000000000LL));
 294   EXPECT_EQ(7u, getSLEB128Size(-0xfc0000000000LL));
 295   EXPECT_EQ(7u, getSLEB128Size(-0x1000000000000LL));
 296   EXPECT_EQ(8u, getSLEB128Size(-0x103ffffffffffLL));
 297   EXPECT_EQ(8u, getSLEB128Size(-0x1040000000000LL));
 298
 299   EXPECT_EQ(8u, getSLEB128Size(-0x1ffffffffffffLL));
 300   EXPECT_EQ(8u, getSLEB128Size(-0x2000000000000LL));
 301   EXPECT_EQ(8u, getSLEB128Size(-0x7e000000000000LL));
 302   EXPECT_EQ(8u, getSLEB128Size(-0x80000000000000LL));
 303   EXPECT_EQ(9u, getSLEB128Size(-0x81ffffffffffffLL));
 304   EXPECT_EQ(9u, getSLEB128Size(-0x82000000000000LL));
 305
 306   EXPECT_EQ(9u, getSLEB128Size(-0xffffffffffffffLL));
 307   EXPECT_EQ(9u, getSLEB128Size(-0x100000000000000LL));
 308   EXPECT_EQ(9u, getSLEB128Size(-0x3f00000000000000LL));
 309   EXPECT_EQ(9u, getSLEB128Size(-0x4000000000000000LL));
 310   EXPECT_EQ(10u, getSLEB128Size(-0x40ffffffffffffffLL));
 311   EXPECT_EQ(10u, getSLEB128Size(-0x4100000000000000LL));
 312
 313   EXPECT_EQ(10u, getSLEB128Size(-0x7fffffffffffffffLL));
 314   EXPECT_EQ(10u, getSLEB128Size(-0x8000000000000000LL));
 315   EXPECT_EQ(10u, getSLEB128Size(INT64_MIN));
 316 }
 317
 318 TEST(LEB128Test, ULEB128Size) {
 319   // Testing Plan:
 320   // (1) 128 ^ n ............ need (n+1) bytes
 321   // (2) 128 ^ n * 64 ....... need (n+1) bytes
 322   // (3) 128 ^ (n+1) - 1 .... need (n+1) bytes
 323
 324   EXPECT_EQ(1u, getULEB128Size(0)); // special case
 325
 326   EXPECT_EQ(1u, getULEB128Size(0x1ULL));
 327   EXPECT_EQ(1u, getULEB128Size(0x40ULL));
 328   EXPECT_EQ(1u, getULEB128Size(0x7fULL));
 329
 330   EXPECT_EQ(2u, getULEB128Size(0x80ULL));
 331   EXPECT_EQ(2u, getULEB128Size(0x2000ULL));
 332   EXPECT_EQ(2u, getULEB128Size(0x3fffULL));
 333
 334   EXPECT_EQ(3u, getULEB128Size(0x4000ULL));
 335   EXPECT_EQ(3u, getULEB128Size(0x100000ULL));
 336   EXPECT_EQ(3u, getULEB128Size(0x1fffffULL));
 337
 338   EXPECT_EQ(4u, getULEB128Size(0x200000ULL));
 339   EXPECT_EQ(4u, getULEB128Size(0x8000000ULL));
 340   EXPECT_EQ(4u, getULEB128Size(0xfffffffULL));
 341
 342   EXPECT_EQ(5u, getULEB128Size(0x10000000ULL));
 343   EXPECT_EQ(5u, getULEB128Size(0x400000000ULL));
 344   EXPECT_EQ(5u, getULEB128Size(0x7ffffffffULL));
 345
 346   EXPECT_EQ(6u, getULEB128Size(0x800000000ULL));
 347   EXPECT_EQ(6u, getULEB128Size(0x20000000000ULL));
 348   EXPECT_EQ(6u, getULEB128Size(0x3ffffffffffULL));
 349
 350   EXPECT_EQ(7u, getULEB128Size(0x40000000000ULL));
 351   EXPECT_EQ(7u, getULEB128Size(0x1000000000000ULL));
 352   EXPECT_EQ(7u, getULEB128Size(0x1ffffffffffffULL));
 353
 354   EXPECT_EQ(8u, getULEB128Size(0x2000000000000ULL));
 355   EXPECT_EQ(8u, getULEB128Size(0x80000000000000ULL));
 356   EXPECT_EQ(8u, getULEB128Size(0xffffffffffffffULL));
 357
 358   EXPECT_EQ(9u, getULEB128Size(0x100000000000000ULL));
 359   EXPECT_EQ(9u, getULEB128Size(0x4000000000000000ULL));
 360   EXPECT_EQ(9u, getULEB128Size(0x7fffffffffffffffULL));
 361
 362   EXPECT_EQ(10u, getULEB128Size(0x8000000000000000ULL));
 363
 364   EXPECT_EQ(10u, getULEB128Size(UINT64_MAX));
 365 }
 366
 367 }  // anonymous namespace