unittests/Support/LEB128Test.cpp

   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
 110   // Decode ULEB128 with extra padding bytes
 111   EXPECT_DECODE_ULEB128_EQ(0u, "\x80\x00");
 112   EXPECT_DECODE_ULEB128_EQ(0u, "\x80\x80\x00");
 113   EXPECT_DECODE_ULEB128_EQ(0x7fu, "\xff\x00");
 114   EXPECT_DECODE_ULEB128_EQ(0x7fu, "\xff\x80\x00");
 115   EXPECT_DECODE_ULEB128_EQ(0x80u, "\x80\x81\x00");
 116   EXPECT_DECODE_ULEB128_EQ(0x80u, "\x80\x81\x80\x00");
 117
 118 #undef EXPECT_DECODE_ULEB128_EQ
 119 }
 120
 121 TEST(LEB128Test, SLEB128Size) {
 122   // Positive Value Testing Plan:
 123   // (1) 128 ^ n - 1 ........ need (n+1) bytes
 124   // (2) 128 ^ n ............ need (n+1) bytes
 125   // (3) 128 ^ n * 63 ....... need (n+1) bytes
 126   // (4) 128 ^ n * 64 - 1 ... need (n+1) bytes
 127   // (5) 128 ^ n * 64 ....... need (n+2) bytes
 128
 129   EXPECT_EQ(1u, getSLEB128Size(0x0LL));
 130   EXPECT_EQ(1u, getSLEB128Size(0x1LL));
 131   EXPECT_EQ(1u, getSLEB128Size(0x3fLL));
 132   EXPECT_EQ(1u, getSLEB128Size(0x3fLL));
 133   EXPECT_EQ(2u, getSLEB128Size(0x40LL));
 134
 135   EXPECT_EQ(2u, getSLEB128Size(0x7fLL));
 136   EXPECT_EQ(2u, getSLEB128Size(0x80LL));
 137   EXPECT_EQ(2u, getSLEB128Size(0x1f80LL));
 138   EXPECT_EQ(2u, getSLEB128Size(0x1fffLL));
 139   EXPECT_EQ(3u, getSLEB128Size(0x2000LL));
 140
 141   EXPECT_EQ(3u, getSLEB128Size(0x3fffLL));
 142   EXPECT_EQ(3u, getSLEB128Size(0x4000LL));
 143   EXPECT_EQ(3u, getSLEB128Size(0xfc000LL));
 144   EXPECT_EQ(3u, getSLEB128Size(0xfffffLL));
 145   EXPECT_EQ(4u, getSLEB128Size(0x100000LL));
 146
 147   EXPECT_EQ(4u, getSLEB128Size(0x1fffffLL));
 148   EXPECT_EQ(4u, getSLEB128Size(0x200000LL));
 149   EXPECT_EQ(4u, getSLEB128Size(0x7e00000LL));
 150   EXPECT_EQ(4u, getSLEB128Size(0x7ffffffLL));
 151   EXPECT_EQ(5u, getSLEB128Size(0x8000000LL));
 152
 153   EXPECT_EQ(5u, getSLEB128Size(0xfffffffLL));
 154   EXPECT_EQ(5u, getSLEB128Size(0x10000000LL));
 155   EXPECT_EQ(5u, getSLEB128Size(0x3f0000000LL));
 156   EXPECT_EQ(5u, getSLEB128Size(0x3ffffffffLL));
 157   EXPECT_EQ(6u, getSLEB128Size(0x400000000LL));
 158
 159   EXPECT_EQ(6u, getSLEB128Size(0x7ffffffffLL));
 160   EXPECT_EQ(6u, getSLEB128Size(0x800000000LL));
 161   EXPECT_EQ(6u, getSLEB128Size(0x1f800000000LL));
 162   EXPECT_EQ(6u, getSLEB128Size(0x1ffffffffffLL));
 163   EXPECT_EQ(7u, getSLEB128Size(0x20000000000LL));
 164
 165   EXPECT_EQ(7u, getSLEB128Size(0x3ffffffffffLL));
 166   EXPECT_EQ(7u, getSLEB128Size(0x40000000000LL));
 167   EXPECT_EQ(7u, getSLEB128Size(0xfc0000000000LL));
 168   EXPECT_EQ(7u, getSLEB128Size(0xffffffffffffLL));
 169   EXPECT_EQ(8u, getSLEB128Size(0x1000000000000LL));
 170
 171   EXPECT_EQ(8u, getSLEB128Size(0x1ffffffffffffLL));
 172   EXPECT_EQ(8u, getSLEB128Size(0x2000000000000LL));
 173   EXPECT_EQ(8u, getSLEB128Size(0x7e000000000000LL));
 174   EXPECT_EQ(8u, getSLEB128Size(0x7fffffffffffffLL));
 175   EXPECT_EQ(9u, getSLEB128Size(0x80000000000000LL));
 176
 177   EXPECT_EQ(9u, getSLEB128Size(0xffffffffffffffLL));
 178   EXPECT_EQ(9u, getSLEB128Size(0x100000000000000LL));
 179   EXPECT_EQ(9u, getSLEB128Size(0x3f00000000000000LL));
 180   EXPECT_EQ(9u, getSLEB128Size(0x3fffffffffffffffLL));
 181   EXPECT_EQ(10u, getSLEB128Size(0x4000000000000000LL));
 182
 183   EXPECT_EQ(10u, getSLEB128Size(0x7fffffffffffffffLL));
 184   EXPECT_EQ(10u, getSLEB128Size(INT64_MAX));
 185
 186   // Negative Value Testing Plan:
 187   // (1) - 128 ^ n - 1 ........ need (n+1) bytes
 188   // (2) - 128 ^ n ............ need (n+1) bytes
 189   // (3) - 128 ^ n * 63 ....... need (n+1) bytes
 190   // (4) - 128 ^ n * 64 ....... need (n+1) bytes (different from positive one)
 191   // (5) - 128 ^ n * 65 - 1 ... need (n+2) bytes (if n > 0)
 192   // (6) - 128 ^ n * 65 ....... need (n+2) bytes
 193
 194   EXPECT_EQ(1u, getSLEB128Size(0x0LL));
 195   EXPECT_EQ(1u, getSLEB128Size(-0x1LL));
 196   EXPECT_EQ(1u, getSLEB128Size(-0x3fLL));
 197   EXPECT_EQ(1u, getSLEB128Size(-0x40LL));
 198   EXPECT_EQ(1u, getSLEB128Size(-0x40LL)); // special case
 199   EXPECT_EQ(2u, getSLEB128Size(-0x41LL));
 200
 201   EXPECT_EQ(2u, getSLEB128Size(-0x7fLL));
 202   EXPECT_EQ(2u, getSLEB128Size(-0x80LL));
 203   EXPECT_EQ(2u, getSLEB128Size(-0x1f80LL));
 204   EXPECT_EQ(2u, getSLEB128Size(-0x2000LL));
 205   EXPECT_EQ(3u, getSLEB128Size(-0x207fLL));
 206   EXPECT_EQ(3u, getSLEB128Size(-0x2080LL));
 207
 208   EXPECT_EQ(3u, getSLEB128Size(-0x3fffLL));
 209   EXPECT_EQ(3u, getSLEB128Size(-0x4000LL));
 210   EXPECT_EQ(3u, getSLEB128Size(-0xfc000LL));
 211   EXPECT_EQ(3u, getSLEB128Size(-0x100000LL));
 212   EXPECT_EQ(4u, getSLEB128Size(-0x103fffLL));
 213   EXPECT_EQ(4u, getSLEB128Size(-0x104000LL));
 214
 215   EXPECT_EQ(4u, getSLEB128Size(-0x1fffffLL));
 216   EXPECT_EQ(4u, getSLEB128Size(-0x200000LL));
 217   EXPECT_EQ(4u, getSLEB128Size(-0x7e00000LL));
 218   EXPECT_EQ(4u, getSLEB128Size(-0x8000000LL));
 219   EXPECT_EQ(5u, getSLEB128Size(-0x81fffffLL));
 220   EXPECT_EQ(5u, getSLEB128Size(-0x8200000LL));
 221
 222   EXPECT_EQ(5u, getSLEB128Size(-0xfffffffLL));
 223   EXPECT_EQ(5u, getSLEB128Size(-0x10000000LL));
 224   EXPECT_EQ(5u, getSLEB128Size(-0x3f0000000LL));
 225   EXPECT_EQ(5u, getSLEB128Size(-0x400000000LL));
 226   EXPECT_EQ(6u, getSLEB128Size(-0x40fffffffLL));
 227   EXPECT_EQ(6u, getSLEB128Size(-0x410000000LL));
 228
 229   EXPECT_EQ(6u, getSLEB128Size(-0x7ffffffffLL));
 230   EXPECT_EQ(6u, getSLEB128Size(-0x800000000LL));
 231   EXPECT_EQ(6u, getSLEB128Size(-0x1f800000000LL));
 232   EXPECT_EQ(6u, getSLEB128Size(-0x20000000000LL));
 233   EXPECT_EQ(7u, getSLEB128Size(-0x207ffffffffLL));
 234   EXPECT_EQ(7u, getSLEB128Size(-0x20800000000LL));
 235
 236   EXPECT_EQ(7u, getSLEB128Size(-0x3ffffffffffLL));
 237   EXPECT_EQ(7u, getSLEB128Size(-0x40000000000LL));
 238   EXPECT_EQ(7u, getSLEB128Size(-0xfc0000000000LL));
 239   EXPECT_EQ(7u, getSLEB128Size(-0x1000000000000LL));
 240   EXPECT_EQ(8u, getSLEB128Size(-0x103ffffffffffLL));
 241   EXPECT_EQ(8u, getSLEB128Size(-0x1040000000000LL));
 242
 243   EXPECT_EQ(8u, getSLEB128Size(-0x1ffffffffffffLL));
 244   EXPECT_EQ(8u, getSLEB128Size(-0x2000000000000LL));
 245   EXPECT_EQ(8u, getSLEB128Size(-0x7e000000000000LL));
 246   EXPECT_EQ(8u, getSLEB128Size(-0x80000000000000LL));
 247   EXPECT_EQ(9u, getSLEB128Size(-0x81ffffffffffffLL));
 248   EXPECT_EQ(9u, getSLEB128Size(-0x82000000000000LL));
 249
 250   EXPECT_EQ(9u, getSLEB128Size(-0xffffffffffffffLL));
 251   EXPECT_EQ(9u, getSLEB128Size(-0x100000000000000LL));
 252   EXPECT_EQ(9u, getSLEB128Size(-0x3f00000000000000LL));
 253   EXPECT_EQ(9u, getSLEB128Size(-0x4000000000000000LL));
 254   EXPECT_EQ(10u, getSLEB128Size(-0x40ffffffffffffffLL));
 255   EXPECT_EQ(10u, getSLEB128Size(-0x4100000000000000LL));
 256
 257   EXPECT_EQ(10u, getSLEB128Size(-0x7fffffffffffffffLL));
 258   EXPECT_EQ(10u, getSLEB128Size(-0x8000000000000000LL));
 259   EXPECT_EQ(10u, getSLEB128Size(INT64_MIN));
 260 }
 261
 262 TEST(LEB128Test, ULEB128Size) {
 263   // Testing Plan:
 264   // (1) 128 ^ n ............ need (n+1) bytes
 265   // (2) 128 ^ n * 64 ....... need (n+1) bytes
 266   // (3) 128 ^ (n+1) - 1 .... need (n+1) bytes
 267
 268   EXPECT_EQ(1u, getULEB128Size(0)); // special case
 269
 270   EXPECT_EQ(1u, getULEB128Size(0x1ULL));
 271   EXPECT_EQ(1u, getULEB128Size(0x40ULL));
 272   EXPECT_EQ(1u, getULEB128Size(0x7fULL));
 273
 274   EXPECT_EQ(2u, getULEB128Size(0x80ULL));
 275   EXPECT_EQ(2u, getULEB128Size(0x2000ULL));
 276   EXPECT_EQ(2u, getULEB128Size(0x3fffULL));
 277
 278   EXPECT_EQ(3u, getULEB128Size(0x4000ULL));
 279   EXPECT_EQ(3u, getULEB128Size(0x100000ULL));
 280   EXPECT_EQ(3u, getULEB128Size(0x1fffffULL));
 281
 282   EXPECT_EQ(4u, getULEB128Size(0x200000ULL));
 283   EXPECT_EQ(4u, getULEB128Size(0x8000000ULL));
 284   EXPECT_EQ(4u, getULEB128Size(0xfffffffULL));
 285
 286   EXPECT_EQ(5u, getULEB128Size(0x10000000ULL));
 287   EXPECT_EQ(5u, getULEB128Size(0x400000000ULL));
 288   EXPECT_EQ(5u, getULEB128Size(0x7ffffffffULL));
 289
 290   EXPECT_EQ(6u, getULEB128Size(0x800000000ULL));
 291   EXPECT_EQ(6u, getULEB128Size(0x20000000000ULL));
 292   EXPECT_EQ(6u, getULEB128Size(0x3ffffffffffULL));
 293
 294   EXPECT_EQ(7u, getULEB128Size(0x40000000000ULL));
 295   EXPECT_EQ(7u, getULEB128Size(0x1000000000000ULL));
 296   EXPECT_EQ(7u, getULEB128Size(0x1ffffffffffffULL));
 297
 298   EXPECT_EQ(8u, getULEB128Size(0x2000000000000ULL));
 299   EXPECT_EQ(8u, getULEB128Size(0x80000000000000ULL));
 300   EXPECT_EQ(8u, getULEB128Size(0xffffffffffffffULL));
 301
 302   EXPECT_EQ(9u, getULEB128Size(0x100000000000000ULL));
 303   EXPECT_EQ(9u, getULEB128Size(0x4000000000000000ULL));
 304   EXPECT_EQ(9u, getULEB128Size(0x7fffffffffffffffULL));
 305
 306   EXPECT_EQ(10u, getULEB128Size(0x8000000000000000ULL));
 307
 308   EXPECT_EQ(10u, getULEB128Size(UINT64_MAX));
 309 }
 310
 311 }  // anonymous namespace