runtime/leb128_test.cc

   1 /*
   2  * Copyright (C) 2013 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include "leb128.h"
  18
  19 #include "gtest/gtest.h"
  20 #include "base/histogram-inl.h"
  21 #include "base/time_utils.h"
  22
  23 namespace art {
  24
  25 struct DecodeUnsignedLeb128TestCase {
  26   uint32_t decoded;
  27   uint8_t leb128_data[5];
  28 };
  29
  30 static DecodeUnsignedLeb128TestCase uleb128_tests[] = {
  31     {0,          {0, 0, 0, 0, 0}},
  32     {1,          {1, 0, 0, 0, 0}},
  33     {0x7F,       {0x7F, 0, 0, 0, 0}},
  34     {0x80,       {0x80, 1, 0, 0, 0}},
  35     {0x81,       {0x81, 1, 0, 0, 0}},
  36     {0xFF,       {0xFF, 1, 0, 0, 0}},
  37     {0x4000,     {0x80, 0x80, 1, 0, 0}},
  38     {0x4001,     {0x81, 0x80, 1, 0, 0}},
  39     {0x4081,     {0x81, 0x81, 1, 0, 0}},
  40     {0x0FFFFFFF, {0xFF, 0xFF, 0xFF, 0x7F, 0}},
  41     {0xFFFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0xF}},
  42 };
  43
  44 struct DecodeSignedLeb128TestCase {
  45   int32_t decoded;
  46   uint8_t leb128_data[5];
  47 };
  48
  49 static DecodeSignedLeb128TestCase sleb128_tests[] = {
  50     {0,          {0, 0, 0, 0, 0}},
  51     {1,          {1, 0, 0, 0, 0}},
  52     {0x3F,       {0x3F, 0, 0, 0, 0}},
  53     {0x40,       {0xC0, 0 /* sign bit */, 0, 0, 0}},
  54     {0x41,       {0xC1, 0 /* sign bit */, 0, 0, 0}},
  55     {0x80,       {0x80, 1, 0, 0, 0}},
  56     {0xFF,       {0xFF, 1, 0, 0, 0}},
  57     {0x1FFF,     {0xFF, 0x3F, 0, 0, 0}},
  58     {0x2000,     {0x80, 0xC0, 0 /* sign bit */, 0, 0}},
  59     {0x2001,     {0x81, 0xC0, 0 /* sign bit */, 0, 0}},
  60     {0x2081,     {0x81, 0xC1, 0 /* sign bit */, 0, 0}},
  61     {0x4000,     {0x80, 0x80, 1, 0, 0}},
  62     {0x0FFFFF,   {0xFF, 0xFF, 0x3F, 0, 0}},
  63     {0x100000,   {0x80, 0x80, 0xC0, 0 /* sign bit */, 0}},
  64     {0x100001,   {0x81, 0x80, 0xC0, 0 /* sign bit */, 0}},
  65     {0x100081,   {0x81, 0x81, 0xC0, 0 /* sign bit */, 0}},
  66     {0x104081,   {0x81, 0x81, 0xC1, 0 /* sign bit */, 0}},
  67     {0x200000,   {0x80, 0x80, 0x80, 1, 0}},
  68     {0x7FFFFFF,  {0xFF, 0xFF, 0xFF, 0x3F, 0}},
  69     {0x8000000,  {0x80, 0x80, 0x80, 0xC0, 0 /* sign bit */}},
  70     {0x8000001,  {0x81, 0x80, 0x80, 0xC0, 0 /* sign bit */}},
  71     {0x8000081,  {0x81, 0x81, 0x80, 0xC0, 0 /* sign bit */}},
  72     {0x8004081,  {0x81, 0x81, 0x81, 0xC0, 0 /* sign bit */}},
  73     {0x8204081,  {0x81, 0x81, 0x81, 0xC1, 0 /* sign bit */}},
  74     {0x0FFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0 /* sign bit */}},
  75     {0x10000000, {0x80, 0x80, 0x80, 0x80, 1}},
  76     {0x7FFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0x7}},
  77     {-1,         {0x7F, 0, 0, 0, 0}},
  78     {-2,         {0x7E, 0, 0, 0, 0}},
  79     {-0x3F,      {0x41, 0, 0, 0, 0}},
  80     {-0x40,      {0x40, 0, 0, 0, 0}},
  81     {-0x41,      {0xBF, 0x7F, 0, 0, 0}},
  82     {-0x80,      {0x80, 0x7F, 0, 0, 0}},
  83     {-0x81,      {0xFF, 0x7E, 0, 0, 0}},
  84     {-0x00002000, {0x80, 0x40, 0, 0, 0}},
  85     {-0x00002001, {0xFF, 0xBF, 0x7F, 0, 0}},
  86     {-0x00100000, {0x80, 0x80, 0x40, 0, 0}},
  87     {-0x00100001, {0xFF, 0xFF, 0xBF, 0x7F, 0}},
  88     {-0x08000000, {0x80, 0x80, 0x80, 0x40, 0}},
  89     {-0x08000001, {0xFF, 0xFF, 0xFF, 0xBF, 0x7F}},
  90     {-0x20000000, {0x80, 0x80, 0x80, 0x80, 0x7E}},
  91     {static_cast<int32_t>(0x80000000), {0x80, 0x80, 0x80, 0x80, 0x78}},
  92 };
  93
  94 TEST(Leb128Test, UnsignedSinglesVector) {
  95   // Test individual encodings.
  96   for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
  97     Leb128EncodingVector<> builder;
  98     builder.PushBackUnsigned(uleb128_tests[i].decoded);
  99     EXPECT_EQ(UnsignedLeb128Size(uleb128_tests[i].decoded), builder.GetData().size());
 100     const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0];
 101     const uint8_t* encoded_data_ptr = &builder.GetData()[0];
 102     for (size_t j = 0; j < 5; ++j) {
 103       if (j < builder.GetData().size()) {
 104         EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
 105       } else {
 106         EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
 107       }
 108     }
 109     EXPECT_EQ(DecodeUnsignedLeb128(&data_ptr), uleb128_tests[i].decoded) << " i = " << i;
 110   }
 111 }
 112
 113 TEST(Leb128Test, UnsignedSingles) {
 114   // Test individual encodings.
 115   for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
 116     uint8_t encoded_data[5];
 117     uint8_t* end = EncodeUnsignedLeb128(encoded_data, uleb128_tests[i].decoded);
 118     size_t data_size = static_cast<size_t>(end - encoded_data);
 119     EXPECT_EQ(UnsignedLeb128Size(uleb128_tests[i].decoded), data_size);
 120     const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0];
 121     for (size_t j = 0; j < 5; ++j) {
 122       if (j < data_size) {
 123         EXPECT_EQ(data_ptr[j], encoded_data[j]) << " i = " << i << " j = " << j;
 124       } else {
 125         EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
 126       }
 127     }
 128     EXPECT_EQ(DecodeUnsignedLeb128(&data_ptr), uleb128_tests[i].decoded) << " i = " << i;
 129   }
 130 }
 131
 132 TEST(Leb128Test, UnsignedStreamVector) {
 133   // Encode a number of entries.
 134   Leb128EncodingVector<> builder;
 135   for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
 136     builder.PushBackUnsigned(uleb128_tests[i].decoded);
 137   }
 138   const uint8_t* encoded_data_ptr = &builder.GetData()[0];
 139   for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
 140     const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0];
 141     for (size_t j = 0; j < UnsignedLeb128Size(uleb128_tests[i].decoded); ++j) {
 142       EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
 143     }
 144     for (size_t j = UnsignedLeb128Size(uleb128_tests[i].decoded); j < 5; ++j) {
 145       EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j;
 146     }
 147     EXPECT_EQ(DecodeUnsignedLeb128(&encoded_data_ptr), uleb128_tests[i].decoded) << " i = " << i;
 148   }
 149   EXPECT_EQ(builder.GetData().size(),
 150             static_cast<size_t>(encoded_data_ptr - &builder.GetData()[0]));
 151 }
 152
 153 TEST(Leb128Test, UnsignedStream) {
 154   // Encode a number of entries.
 155   uint8_t encoded_data[5 * arraysize(uleb128_tests)];
 156   uint8_t* end = encoded_data;
 157   for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
 158     end = EncodeUnsignedLeb128(end, uleb128_tests[i].decoded);
 159   }
 160   size_t data_size = static_cast<size_t>(end - encoded_data);
 161   const uint8_t* encoded_data_ptr = encoded_data;
 162   for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
 163     const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0];
 164     for (size_t j = 0; j < UnsignedLeb128Size(uleb128_tests[i].decoded); ++j) {
 165       EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
 166     }
 167     for (size_t j = UnsignedLeb128Size(uleb128_tests[i].decoded); j < 5; ++j) {
 168       EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j;
 169     }
 170     EXPECT_EQ(DecodeUnsignedLeb128(&encoded_data_ptr), uleb128_tests[i].decoded) << " i = " << i;
 171   }
 172   EXPECT_EQ(data_size, static_cast<size_t>(encoded_data_ptr - encoded_data));
 173 }
 174
 175 TEST(Leb128Test, SignedSinglesVector) {
 176   // Test individual encodings.
 177   for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
 178     Leb128EncodingVector<> builder;
 179     builder.PushBackSigned(sleb128_tests[i].decoded);
 180     EXPECT_EQ(SignedLeb128Size(sleb128_tests[i].decoded), builder.GetData().size());
 181     const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0];
 182     const uint8_t* encoded_data_ptr = &builder.GetData()[0];
 183     for (size_t j = 0; j < 5; ++j) {
 184       if (j < builder.GetData().size()) {
 185         EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
 186       } else {
 187         EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
 188       }
 189     }
 190     EXPECT_EQ(DecodeSignedLeb128(&data_ptr), sleb128_tests[i].decoded) << " i = " << i;
 191   }
 192 }
 193
 194 TEST(Leb128Test, SignedSingles) {
 195   // Test individual encodings.
 196   for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
 197     uint8_t encoded_data[5];
 198     uint8_t* end = EncodeSignedLeb128(encoded_data, sleb128_tests[i].decoded);
 199     size_t data_size = static_cast<size_t>(end - encoded_data);
 200     EXPECT_EQ(SignedLeb128Size(sleb128_tests[i].decoded), data_size);
 201     const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0];
 202     for (size_t j = 0; j < 5; ++j) {
 203       if (j < data_size) {
 204         EXPECT_EQ(data_ptr[j], encoded_data[j]) << " i = " << i << " j = " << j;
 205       } else {
 206         EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
 207       }
 208     }
 209     EXPECT_EQ(DecodeSignedLeb128(&data_ptr), sleb128_tests[i].decoded) << " i = " << i;
 210   }
 211 }
 212
 213 TEST(Leb128Test, SignedStreamVector) {
 214   // Encode a number of entries.
 215   Leb128EncodingVector<> builder;
 216   for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
 217     builder.PushBackSigned(sleb128_tests[i].decoded);
 218   }
 219   const uint8_t* encoded_data_ptr = &builder.GetData()[0];
 220   for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
 221     const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0];
 222     for (size_t j = 0; j < SignedLeb128Size(sleb128_tests[i].decoded); ++j) {
 223       EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
 224     }
 225     for (size_t j = SignedLeb128Size(sleb128_tests[i].decoded); j < 5; ++j) {
 226       EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j;
 227     }
 228     EXPECT_EQ(DecodeSignedLeb128(&encoded_data_ptr), sleb128_tests[i].decoded) << " i = " << i;
 229   }
 230   EXPECT_EQ(builder.GetData().size(),
 231             static_cast<size_t>(encoded_data_ptr - &builder.GetData()[0]));
 232 }
 233
 234 TEST(Leb128Test, SignedStream) {
 235   // Encode a number of entries.
 236   uint8_t encoded_data[5 * arraysize(sleb128_tests)];
 237   uint8_t* end = encoded_data;
 238   for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
 239     end = EncodeSignedLeb128(end, sleb128_tests[i].decoded);
 240   }
 241   size_t data_size = static_cast<size_t>(end - encoded_data);
 242   const uint8_t* encoded_data_ptr = encoded_data;
 243   for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
 244     const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0];
 245     for (size_t j = 0; j < SignedLeb128Size(sleb128_tests[i].decoded); ++j) {
 246       EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
 247     }
 248     for (size_t j = SignedLeb128Size(sleb128_tests[i].decoded); j < 5; ++j) {
 249       EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j;
 250     }
 251     EXPECT_EQ(DecodeSignedLeb128(&encoded_data_ptr), sleb128_tests[i].decoded) << " i = " << i;
 252   }
 253   EXPECT_EQ(data_size, static_cast<size_t>(encoded_data_ptr - encoded_data));
 254 }
 255
 256 TEST(Leb128Test, UnsignedUpdate) {
 257   for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
 258     for (size_t j = 0; j < arraysize(uleb128_tests); ++j) {
 259       uint32_t old_value = uleb128_tests[i].decoded;
 260       uint32_t new_value = uleb128_tests[j].decoded;
 261       // We can only make the encoded value smaller.
 262       if (new_value <= old_value) {
 263         uint8_t encoded_data[5];
 264         uint8_t* old_end = EncodeUnsignedLeb128(encoded_data, old_value);
 265         UpdateUnsignedLeb128(encoded_data, new_value);
 266         const uint8_t* new_end = encoded_data;
 267         EXPECT_EQ(DecodeUnsignedLeb128(&new_end), new_value);
 268         // Even if the new value needs fewer bytes, we should fill the space.
 269         EXPECT_EQ(new_end, old_end);
 270       }
 271     }
 272   }
 273 }
 274
 275 TEST(Leb128Test, Speed) {
 276   std::unique_ptr<Histogram<uint64_t>> enc_hist(new Histogram<uint64_t>("Leb128EncodeSpeedTest", 5));
 277   std::unique_ptr<Histogram<uint64_t>> dec_hist(new Histogram<uint64_t>("Leb128DecodeSpeedTest", 5));
 278   Leb128EncodingVector<> builder;
 279   // Push back 1024 chunks of 1024 values measuring encoding speed.
 280   uint64_t last_time = NanoTime();
 281   for (size_t i = 0; i < 1024; i++) {
 282     for (size_t j = 0; j < 1024; j++) {
 283       builder.PushBackUnsigned((i * 1024) + j);
 284     }
 285     uint64_t cur_time = NanoTime();
 286     enc_hist->AddValue(cur_time - last_time);
 287     last_time = cur_time;
 288   }
 289   // Verify encoding and measure decode speed.
 290   const uint8_t* encoded_data_ptr = &builder.GetData()[0];
 291   last_time = NanoTime();
 292   for (size_t i = 0; i < 1024; i++) {
 293     for (size_t j = 0; j < 1024; j++) {
 294       EXPECT_EQ(DecodeUnsignedLeb128(&encoded_data_ptr), (i * 1024) + j);
 295     }
 296     uint64_t cur_time = NanoTime();
 297     dec_hist->AddValue(cur_time - last_time);
 298     last_time = cur_time;
 299   }
 300
 301   Histogram<uint64_t>::CumulativeData enc_data;
 302   enc_hist->CreateHistogram(&enc_data);
 303   enc_hist->PrintConfidenceIntervals(std::cout, 0.99, enc_data);
 304
 305   Histogram<uint64_t>::CumulativeData dec_data;
 306   dec_hist->CreateHistogram(&dec_data);
 307   dec_hist->PrintConfidenceIntervals(std::cout, 0.99, dec_data);
 308 }
 309
 310 }  // namespace art