runtime/leb128_test.cc - platform/art - Git at Google

 /*
  * Copyright (C) 2013 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #include "leb128.h"

 #include "gtest/gtest.h"
 #include "base/histogram-inl.h"
 #include "base/time_utils.h"

 namespace art {

 struct DecodeUnsignedLeb128TestCase {
   uint32_t decoded;
   uint8_t leb128_data[5];
 };

 static DecodeUnsignedLeb128TestCase uleb128_tests[] = {
     {0,          {0, 0, 0, 0, 0}},
     {1,          {1, 0, 0, 0, 0}},
     {0x7F,       {0x7F, 0, 0, 0, 0}},
     {0x80,       {0x80, 1, 0, 0, 0}},
     {0x81,       {0x81, 1, 0, 0, 0}},
     {0xFF,       {0xFF, 1, 0, 0, 0}},
     {0x4000,     {0x80, 0x80, 1, 0, 0}},
     {0x4001,     {0x81, 0x80, 1, 0, 0}},
     {0x4081,     {0x81, 0x81, 1, 0, 0}},
     {0x0FFFFFFF, {0xFF, 0xFF, 0xFF, 0x7F, 0}},
     {0xFFFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0xF}},
 };

 struct DecodeSignedLeb128TestCase {
   int32_t decoded;
   uint8_t leb128_data[5];
 };

 static DecodeSignedLeb128TestCase sleb128_tests[] = {
     {0,          {0, 0, 0, 0, 0}},
     {1,          {1, 0, 0, 0, 0}},
     {0x3F,       {0x3F, 0, 0, 0, 0}},
     {0x40,       {0xC0, 0 /* sign bit */, 0, 0, 0}},
     {0x41,       {0xC1, 0 /* sign bit */, 0, 0, 0}},
     {0x80,       {0x80, 1, 0, 0, 0}},
     {0xFF,       {0xFF, 1, 0, 0, 0}},
     {0x1FFF,     {0xFF, 0x3F, 0, 0, 0}},
     {0x2000,     {0x80, 0xC0, 0 /* sign bit */, 0, 0}},
     {0x2001,     {0x81, 0xC0, 0 /* sign bit */, 0, 0}},
     {0x2081,     {0x81, 0xC1, 0 /* sign bit */, 0, 0}},
     {0x4000,     {0x80, 0x80, 1, 0, 0}},
     {0x0FFFFF,   {0xFF, 0xFF, 0x3F, 0, 0}},
     {0x100000,   {0x80, 0x80, 0xC0, 0 /* sign bit */, 0}},
     {0x100001,   {0x81, 0x80, 0xC0, 0 /* sign bit */, 0}},
     {0x100081,   {0x81, 0x81, 0xC0, 0 /* sign bit */, 0}},
     {0x104081,   {0x81, 0x81, 0xC1, 0 /* sign bit */, 0}},
     {0x200000,   {0x80, 0x80, 0x80, 1, 0}},
     {0x7FFFFFF,  {0xFF, 0xFF, 0xFF, 0x3F, 0}},
     {0x8000000,  {0x80, 0x80, 0x80, 0xC0, 0 /* sign bit */}},
     {0x8000001,  {0x81, 0x80, 0x80, 0xC0, 0 /* sign bit */}},
     {0x8000081,  {0x81, 0x81, 0x80, 0xC0, 0 /* sign bit */}},
     {0x8004081,  {0x81, 0x81, 0x81, 0xC0, 0 /* sign bit */}},
     {0x8204081,  {0x81, 0x81, 0x81, 0xC1, 0 /* sign bit */}},
     {0x0FFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0 /* sign bit */}},
     {0x10000000, {0x80, 0x80, 0x80, 0x80, 1}},
     {0x7FFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0x7}},
     {-1,         {0x7F, 0, 0, 0, 0}},
     {-2,         {0x7E, 0, 0, 0, 0}},
     {-0x3F,      {0x41, 0, 0, 0, 0}},
     {-0x40,      {0x40, 0, 0, 0, 0}},
     {-0x41,      {0xBF, 0x7F, 0, 0, 0}},
     {-0x80,      {0x80, 0x7F, 0, 0, 0}},
     {-0x81,      {0xFF, 0x7E, 0, 0, 0}},
     {-0x00002000, {0x80, 0x40, 0, 0, 0}},
     {-0x00002001, {0xFF, 0xBF, 0x7F, 0, 0}},
     {-0x00100000, {0x80, 0x80, 0x40, 0, 0}},
     {-0x00100001, {0xFF, 0xFF, 0xBF, 0x7F, 0}},
     {-0x08000000, {0x80, 0x80, 0x80, 0x40, 0}},
     {-0x08000001, {0xFF, 0xFF, 0xFF, 0xBF, 0x7F}},
     {-0x20000000, {0x80, 0x80, 0x80, 0x80, 0x7E}},
     {(-1) << 31, {0x80, 0x80, 0x80, 0x80, 0x78}},
 };

 TEST(Leb128Test, UnsignedSinglesVector) {
   // Test individual encodings.
   for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
     Leb128EncodingVector builder;
     builder.PushBackUnsigned(uleb128_tests[i].decoded);
     EXPECT_EQ(UnsignedLeb128Size(uleb128_tests[i].decoded), builder.GetData().size());
     const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0];
     const uint8_t* encoded_data_ptr = &builder.GetData()[0];
     for (size_t j = 0; j < 5; ++j) {
       if (j < builder.GetData().size()) {
         EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
       } else {
         EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
       }
     }
     EXPECT_EQ(DecodeUnsignedLeb128(&data_ptr), uleb128_tests[i].decoded) << " i = " << i;
   }
 }

 TEST(Leb128Test, UnsignedSingles) {
   // Test individual encodings.
   for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
     uint8_t encoded_data[5];
     uint8_t* end = EncodeUnsignedLeb128(encoded_data, uleb128_tests[i].decoded);
     size_t data_size = static_cast<size_t>(end - encoded_data);
     EXPECT_EQ(UnsignedLeb128Size(uleb128_tests[i].decoded), data_size);
     const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0];
     for (size_t j = 0; j < 5; ++j) {
       if (j < data_size) {
         EXPECT_EQ(data_ptr[j], encoded_data[j]) << " i = " << i << " j = " << j;
       } else {
         EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
       }
     }
     EXPECT_EQ(DecodeUnsignedLeb128(&data_ptr), uleb128_tests[i].decoded) << " i = " << i;
   }
 }

 TEST(Leb128Test, UnsignedStreamVector) {
   // Encode a number of entries.
   Leb128EncodingVector builder;
   for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
     builder.PushBackUnsigned(uleb128_tests[i].decoded);
   }
   const uint8_t* encoded_data_ptr = &builder.GetData()[0];
   for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
     const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0];
     for (size_t j = 0; j < UnsignedLeb128Size(uleb128_tests[i].decoded); ++j) {
       EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
     }
     for (size_t j = UnsignedLeb128Size(uleb128_tests[i].decoded); j < 5; ++j) {
       EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j;
     }
     EXPECT_EQ(DecodeUnsignedLeb128(&encoded_data_ptr), uleb128_tests[i].decoded) << " i = " << i;
   }
   EXPECT_EQ(builder.GetData().size(),
             static_cast<size_t>(encoded_data_ptr - &builder.GetData()[0]));
 }

 TEST(Leb128Test, UnsignedStream) {
   // Encode a number of entries.
   uint8_t encoded_data[5 * arraysize(uleb128_tests)];
   uint8_t* end = encoded_data;
   for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
     end = EncodeUnsignedLeb128(end, uleb128_tests[i].decoded);
   }
   size_t data_size = static_cast<size_t>(end - encoded_data);
   const uint8_t* encoded_data_ptr = encoded_data;
   for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
     const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0];
     for (size_t j = 0; j < UnsignedLeb128Size(uleb128_tests[i].decoded); ++j) {
       EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
     }
     for (size_t j = UnsignedLeb128Size(uleb128_tests[i].decoded); j < 5; ++j) {
       EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j;
     }
     EXPECT_EQ(DecodeUnsignedLeb128(&encoded_data_ptr), uleb128_tests[i].decoded) << " i = " << i;
   }
   EXPECT_EQ(data_size, static_cast<size_t>(encoded_data_ptr - encoded_data));
 }

 TEST(Leb128Test, SignedSinglesVector) {
   // Test individual encodings.
   for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
     Leb128EncodingVector builder;
     builder.PushBackSigned(sleb128_tests[i].decoded);
     EXPECT_EQ(SignedLeb128Size(sleb128_tests[i].decoded), builder.GetData().size());
     const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0];
     const uint8_t* encoded_data_ptr = &builder.GetData()[0];
     for (size_t j = 0; j < 5; ++j) {
       if (j < builder.GetData().size()) {
         EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
       } else {
         EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
       }
     }
     EXPECT_EQ(DecodeSignedLeb128(&data_ptr), sleb128_tests[i].decoded) << " i = " << i;
   }
 }

 TEST(Leb128Test, SignedSingles) {
   // Test individual encodings.
   for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
     uint8_t encoded_data[5];
     uint8_t* end = EncodeSignedLeb128(encoded_data, sleb128_tests[i].decoded);
     size_t data_size = static_cast<size_t>(end - encoded_data);
     EXPECT_EQ(SignedLeb128Size(sleb128_tests[i].decoded), data_size);
     const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0];
     for (size_t j = 0; j < 5; ++j) {
       if (j < data_size) {
         EXPECT_EQ(data_ptr[j], encoded_data[j]) << " i = " << i << " j = " << j;
       } else {
         EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
       }
     }
     EXPECT_EQ(DecodeSignedLeb128(&data_ptr), sleb128_tests[i].decoded) << " i = " << i;
   }
 }

 TEST(Leb128Test, SignedStreamVector) {
   // Encode a number of entries.
   Leb128EncodingVector builder;
   for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
     builder.PushBackSigned(sleb128_tests[i].decoded);
   }
   const uint8_t* encoded_data_ptr = &builder.GetData()[0];
   for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
     const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0];
     for (size_t j = 0; j < SignedLeb128Size(sleb128_tests[i].decoded); ++j) {
       EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
     }
     for (size_t j = SignedLeb128Size(sleb128_tests[i].decoded); j < 5; ++j) {
       EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j;
     }
     EXPECT_EQ(DecodeSignedLeb128(&encoded_data_ptr), sleb128_tests[i].decoded) << " i = " << i;
   }
   EXPECT_EQ(builder.GetData().size(),
             static_cast<size_t>(encoded_data_ptr - &builder.GetData()[0]));
 }

 TEST(Leb128Test, SignedStream) {
   // Encode a number of entries.
   uint8_t encoded_data[5 * arraysize(sleb128_tests)];
   uint8_t* end = encoded_data;
   for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
     end = EncodeSignedLeb128(end, sleb128_tests[i].decoded);
   }
   size_t data_size = static_cast<size_t>(end - encoded_data);
   const uint8_t* encoded_data_ptr = encoded_data;
   for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
     const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0];
     for (size_t j = 0; j < SignedLeb128Size(sleb128_tests[i].decoded); ++j) {
       EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
     }
     for (size_t j = SignedLeb128Size(sleb128_tests[i].decoded); j < 5; ++j) {
       EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j;
     }
     EXPECT_EQ(DecodeSignedLeb128(&encoded_data_ptr), sleb128_tests[i].decoded) << " i = " << i;
   }
   EXPECT_EQ(data_size, static_cast<size_t>(encoded_data_ptr - encoded_data));
 }

 TEST(Leb128Test, UnsignedUpdate) {
   for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
     for (size_t j = 0; j < arraysize(uleb128_tests); ++j) {
       uint32_t old_value = uleb128_tests[i].decoded;
       uint32_t new_value = uleb128_tests[j].decoded;
       // We can only make the encoded value smaller.
       if (new_value <= old_value) {
         uint8_t encoded_data[5];
         uint8_t* old_end = EncodeUnsignedLeb128(encoded_data, old_value);
         UpdateUnsignedLeb128(encoded_data, new_value);
         const uint8_t* new_end = encoded_data;
         EXPECT_EQ(DecodeUnsignedLeb128(&new_end), new_value);
         // Even if the new value needs fewer bytes, we should fill the space.
         EXPECT_EQ(new_end, old_end);
       }
     }
   }
 }

 TEST(Leb128Test, Speed) {
   std::unique_ptr<Histogram<uint64_t>> enc_hist(new Histogram<uint64_t>("Leb128EncodeSpeedTest", 5));
   std::unique_ptr<Histogram<uint64_t>> dec_hist(new Histogram<uint64_t>("Leb128DecodeSpeedTest", 5));
   Leb128EncodingVector builder;
   // Push back 1024 chunks of 1024 values measuring encoding speed.
   uint64_t last_time = NanoTime();
   for (size_t i = 0; i < 1024; i++) {
     for (size_t j = 0; j < 1024; j++) {
       builder.PushBackUnsigned((i * 1024) + j);
     }
     uint64_t cur_time = NanoTime();
     enc_hist->AddValue(cur_time - last_time);
     last_time = cur_time;
   }
   // Verify encoding and measure decode speed.
   const uint8_t* encoded_data_ptr = &builder.GetData()[0];
   last_time = NanoTime();
   for (size_t i = 0; i < 1024; i++) {
     for (size_t j = 0; j < 1024; j++) {
       EXPECT_EQ(DecodeUnsignedLeb128(&encoded_data_ptr), (i * 1024) + j);
     }
     uint64_t cur_time = NanoTime();
     dec_hist->AddValue(cur_time - last_time);
     last_time = cur_time;
   }

   Histogram<uint64_t>::CumulativeData enc_data;
   enc_hist->CreateHistogram(&enc_data);
   enc_hist->PrintConfidenceIntervals(std::cout, 0.99, enc_data);

   Histogram<uint64_t>::CumulativeData dec_data;
   dec_hist->CreateHistogram(&dec_data);
   dec_hist->PrintConfidenceIntervals(std::cout, 0.99, dec_data);
 }

 }  // namespace art
	/*
	* Copyright (C) 2013 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#include "leb128.h"

	#include "gtest/gtest.h"
	#include "base/histogram-inl.h"
	#include "base/time_utils.h"

	namespace art {

	struct DecodeUnsignedLeb128TestCase {
	uint32_t decoded;
	uint8_t leb128_data[5];
	};

	static DecodeUnsignedLeb128TestCase uleb128_tests[] = {
	{0, {0, 0, 0, 0, 0}},
	{1, {1, 0, 0, 0, 0}},
	{0x7F, {0x7F, 0, 0, 0, 0}},
	{0x80, {0x80, 1, 0, 0, 0}},
	{0x81, {0x81, 1, 0, 0, 0}},
	{0xFF, {0xFF, 1, 0, 0, 0}},
	{0x4000, {0x80, 0x80, 1, 0, 0}},
	{0x4001, {0x81, 0x80, 1, 0, 0}},
	{0x4081, {0x81, 0x81, 1, 0, 0}},
	{0x0FFFFFFF, {0xFF, 0xFF, 0xFF, 0x7F, 0}},
	{0xFFFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0xF}},
	};

	struct DecodeSignedLeb128TestCase {
	int32_t decoded;
	uint8_t leb128_data[5];
	};

	static DecodeSignedLeb128TestCase sleb128_tests[] = {
	{0, {0, 0, 0, 0, 0}},
	{1, {1, 0, 0, 0, 0}},
	{0x3F, {0x3F, 0, 0, 0, 0}},
	{0x40, {0xC0, 0 /* sign bit */, 0, 0, 0}},
	{0x41, {0xC1, 0 /* sign bit */, 0, 0, 0}},
	{0x80, {0x80, 1, 0, 0, 0}},
	{0xFF, {0xFF, 1, 0, 0, 0}},
	{0x1FFF, {0xFF, 0x3F, 0, 0, 0}},
	{0x2000, {0x80, 0xC0, 0 /* sign bit */, 0, 0}},
	{0x2001, {0x81, 0xC0, 0 /* sign bit */, 0, 0}},
	{0x2081, {0x81, 0xC1, 0 /* sign bit */, 0, 0}},
	{0x4000, {0x80, 0x80, 1, 0, 0}},
	{0x0FFFFF, {0xFF, 0xFF, 0x3F, 0, 0}},
	{0x100000, {0x80, 0x80, 0xC0, 0 /* sign bit */, 0}},
	{0x100001, {0x81, 0x80, 0xC0, 0 /* sign bit */, 0}},
	{0x100081, {0x81, 0x81, 0xC0, 0 /* sign bit */, 0}},
	{0x104081, {0x81, 0x81, 0xC1, 0 /* sign bit */, 0}},
	{0x200000, {0x80, 0x80, 0x80, 1, 0}},
	{0x7FFFFFF, {0xFF, 0xFF, 0xFF, 0x3F, 0}},
	{0x8000000, {0x80, 0x80, 0x80, 0xC0, 0 /* sign bit */}},
	{0x8000001, {0x81, 0x80, 0x80, 0xC0, 0 /* sign bit */}},
	{0x8000081, {0x81, 0x81, 0x80, 0xC0, 0 /* sign bit */}},
	{0x8004081, {0x81, 0x81, 0x81, 0xC0, 0 /* sign bit */}},
	{0x8204081, {0x81, 0x81, 0x81, 0xC1, 0 /* sign bit */}},
	{0x0FFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0 /* sign bit */}},
	{0x10000000, {0x80, 0x80, 0x80, 0x80, 1}},
	{0x7FFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0x7}},
	{-1, {0x7F, 0, 0, 0, 0}},
	{-2, {0x7E, 0, 0, 0, 0}},
	{-0x3F, {0x41, 0, 0, 0, 0}},
	{-0x40, {0x40, 0, 0, 0, 0}},
	{-0x41, {0xBF, 0x7F, 0, 0, 0}},
	{-0x80, {0x80, 0x7F, 0, 0, 0}},
	{-0x81, {0xFF, 0x7E, 0, 0, 0}},
	{-0x00002000, {0x80, 0x40, 0, 0, 0}},
	{-0x00002001, {0xFF, 0xBF, 0x7F, 0, 0}},
	{-0x00100000, {0x80, 0x80, 0x40, 0, 0}},
	{-0x00100001, {0xFF, 0xFF, 0xBF, 0x7F, 0}},
	{-0x08000000, {0x80, 0x80, 0x80, 0x40, 0}},
	{-0x08000001, {0xFF, 0xFF, 0xFF, 0xBF, 0x7F}},
	{-0x20000000, {0x80, 0x80, 0x80, 0x80, 0x7E}},
	{(-1) << 31, {0x80, 0x80, 0x80, 0x80, 0x78}},
	};

	TEST(Leb128Test, UnsignedSinglesVector) {
	// Test individual encodings.
	for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
	Leb128EncodingVector builder;
	builder.PushBackUnsigned(uleb128_tests[i].decoded);
	EXPECT_EQ(UnsignedLeb128Size(uleb128_tests[i].decoded), builder.GetData().size());
	const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0];
	const uint8_t* encoded_data_ptr = &builder.GetData()[0];
	for (size_t j = 0; j < 5; ++j) {
	if (j < builder.GetData().size()) {
	EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
	} else {
	EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
	}
	}
	EXPECT_EQ(DecodeUnsignedLeb128(&data_ptr), uleb128_tests[i].decoded) << " i = " << i;
	}
	}

	TEST(Leb128Test, UnsignedSingles) {
	// Test individual encodings.
	for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
	uint8_t encoded_data[5];
	uint8_t* end = EncodeUnsignedLeb128(encoded_data, uleb128_tests[i].decoded);
	size_t data_size = static_cast<size_t>(end - encoded_data);
	EXPECT_EQ(UnsignedLeb128Size(uleb128_tests[i].decoded), data_size);
	const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0];
	for (size_t j = 0; j < 5; ++j) {
	if (j < data_size) {
	EXPECT_EQ(data_ptr[j], encoded_data[j]) << " i = " << i << " j = " << j;
	} else {
	EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
	}
	}
	EXPECT_EQ(DecodeUnsignedLeb128(&data_ptr), uleb128_tests[i].decoded) << " i = " << i;
	}
	}

	TEST(Leb128Test, UnsignedStreamVector) {
	// Encode a number of entries.
	Leb128EncodingVector builder;
	for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
	builder.PushBackUnsigned(uleb128_tests[i].decoded);
	}
	const uint8_t* encoded_data_ptr = &builder.GetData()[0];
	for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
	const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0];
	for (size_t j = 0; j < UnsignedLeb128Size(uleb128_tests[i].decoded); ++j) {
	EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
	}
	for (size_t j = UnsignedLeb128Size(uleb128_tests[i].decoded); j < 5; ++j) {
	EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j;
	}
	EXPECT_EQ(DecodeUnsignedLeb128(&encoded_data_ptr), uleb128_tests[i].decoded) << " i = " << i;
	}
	EXPECT_EQ(builder.GetData().size(),
	static_cast<size_t>(encoded_data_ptr - &builder.GetData()[0]));
	}

	TEST(Leb128Test, UnsignedStream) {
	// Encode a number of entries.
	uint8_t encoded_data[5 * arraysize(uleb128_tests)];
	uint8_t* end = encoded_data;
	for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
	end = EncodeUnsignedLeb128(end, uleb128_tests[i].decoded);
	}
	size_t data_size = static_cast<size_t>(end - encoded_data);
	const uint8_t* encoded_data_ptr = encoded_data;
	for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
	const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0];
	for (size_t j = 0; j < UnsignedLeb128Size(uleb128_tests[i].decoded); ++j) {
	EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
	}
	for (size_t j = UnsignedLeb128Size(uleb128_tests[i].decoded); j < 5; ++j) {
	EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j;
	}
	EXPECT_EQ(DecodeUnsignedLeb128(&encoded_data_ptr), uleb128_tests[i].decoded) << " i = " << i;
	}
	EXPECT_EQ(data_size, static_cast<size_t>(encoded_data_ptr - encoded_data));
	}

	TEST(Leb128Test, SignedSinglesVector) {
	// Test individual encodings.
	for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
	Leb128EncodingVector builder;
	builder.PushBackSigned(sleb128_tests[i].decoded);
	EXPECT_EQ(SignedLeb128Size(sleb128_tests[i].decoded), builder.GetData().size());
	const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0];
	const uint8_t* encoded_data_ptr = &builder.GetData()[0];
	for (size_t j = 0; j < 5; ++j) {
	if (j < builder.GetData().size()) {
	EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
	} else {
	EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
	}
	}
	EXPECT_EQ(DecodeSignedLeb128(&data_ptr), sleb128_tests[i].decoded) << " i = " << i;
	}
	}

	TEST(Leb128Test, SignedSingles) {
	// Test individual encodings.
	for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
	uint8_t encoded_data[5];
	uint8_t* end = EncodeSignedLeb128(encoded_data, sleb128_tests[i].decoded);
	size_t data_size = static_cast<size_t>(end - encoded_data);
	EXPECT_EQ(SignedLeb128Size(sleb128_tests[i].decoded), data_size);
	const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0];
	for (size_t j = 0; j < 5; ++j) {
	if (j < data_size) {
	EXPECT_EQ(data_ptr[j], encoded_data[j]) << " i = " << i << " j = " << j;
	} else {
	EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
	}
	}
	EXPECT_EQ(DecodeSignedLeb128(&data_ptr), sleb128_tests[i].decoded) << " i = " << i;
	}
	}

	TEST(Leb128Test, SignedStreamVector) {
	// Encode a number of entries.
	Leb128EncodingVector builder;
	for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
	builder.PushBackSigned(sleb128_tests[i].decoded);
	}
	const uint8_t* encoded_data_ptr = &builder.GetData()[0];
	for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
	const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0];
	for (size_t j = 0; j < SignedLeb128Size(sleb128_tests[i].decoded); ++j) {
	EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
	}
	for (size_t j = SignedLeb128Size(sleb128_tests[i].decoded); j < 5; ++j) {
	EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j;
	}
	EXPECT_EQ(DecodeSignedLeb128(&encoded_data_ptr), sleb128_tests[i].decoded) << " i = " << i;
	}
	EXPECT_EQ(builder.GetData().size(),
	static_cast<size_t>(encoded_data_ptr - &builder.GetData()[0]));
	}

	TEST(Leb128Test, SignedStream) {
	// Encode a number of entries.
	uint8_t encoded_data[5 * arraysize(sleb128_tests)];
	uint8_t* end = encoded_data;
	for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
	end = EncodeSignedLeb128(end, sleb128_tests[i].decoded);
	}
	size_t data_size = static_cast<size_t>(end - encoded_data);
	const uint8_t* encoded_data_ptr = encoded_data;
	for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
	const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0];
	for (size_t j = 0; j < SignedLeb128Size(sleb128_tests[i].decoded); ++j) {
	EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
	}
	for (size_t j = SignedLeb128Size(sleb128_tests[i].decoded); j < 5; ++j) {
	EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j;
	}
	EXPECT_EQ(DecodeSignedLeb128(&encoded_data_ptr), sleb128_tests[i].decoded) << " i = " << i;
	}
	EXPECT_EQ(data_size, static_cast<size_t>(encoded_data_ptr - encoded_data));
	}

	TEST(Leb128Test, UnsignedUpdate) {
	for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
	for (size_t j = 0; j < arraysize(uleb128_tests); ++j) {
	uint32_t old_value = uleb128_tests[i].decoded;
	uint32_t new_value = uleb128_tests[j].decoded;
	// We can only make the encoded value smaller.
	if (new_value <= old_value) {
	uint8_t encoded_data[5];
	uint8_t* old_end = EncodeUnsignedLeb128(encoded_data, old_value);
	UpdateUnsignedLeb128(encoded_data, new_value);
	const uint8_t* new_end = encoded_data;
	EXPECT_EQ(DecodeUnsignedLeb128(&new_end), new_value);
	// Even if the new value needs fewer bytes, we should fill the space.
	EXPECT_EQ(new_end, old_end);
	}
	}
	}
	}

	TEST(Leb128Test, Speed) {
	std::unique_ptr<Histogram<uint64_t>> enc_hist(new Histogram<uint64_t>("Leb128EncodeSpeedTest", 5));
	std::unique_ptr<Histogram<uint64_t>> dec_hist(new Histogram<uint64_t>("Leb128DecodeSpeedTest", 5));
	Leb128EncodingVector builder;
	// Push back 1024 chunks of 1024 values measuring encoding speed.
	uint64_t last_time = NanoTime();
	for (size_t i = 0; i < 1024; i++) {
	for (size_t j = 0; j < 1024; j++) {
	builder.PushBackUnsigned((i * 1024) + j);
	}
	uint64_t cur_time = NanoTime();
	enc_hist->AddValue(cur_time - last_time);
	last_time = cur_time;
	}
	// Verify encoding and measure decode speed.
	const uint8_t* encoded_data_ptr = &builder.GetData()[0];
	last_time = NanoTime();
	for (size_t i = 0; i < 1024; i++) {
	for (size_t j = 0; j < 1024; j++) {
	EXPECT_EQ(DecodeUnsignedLeb128(&encoded_data_ptr), (i * 1024) + j);
	}
	uint64_t cur_time = NanoTime();
	dec_hist->AddValue(cur_time - last_time);
	last_time = cur_time;
	}

	Histogram<uint64_t>::CumulativeData enc_data;
	enc_hist->CreateHistogram(&enc_data);
	enc_hist->PrintConfidenceIntervals(std::cout, 0.99, enc_data);

	Histogram<uint64_t>::CumulativeData dec_data;
	dec_hist->CreateHistogram(&dec_data);
	dec_hist->PrintConfidenceIntervals(std::cout, 0.99, dec_data);
	}

	} // namespace art