1500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers/* 2500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers * Copyright (C) 2013 The Android Open Source Project 3500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers * 4500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers * Licensed under the Apache License, Version 2.0 (the "License"); 5500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers * you may not use this file except in compliance with the License. 6500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers * You may obtain a copy of the License at 7500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers * 8500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers * http://www.apache.org/licenses/LICENSE-2.0 9500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers * 10500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers * Unless required by applicable law or agreed to in writing, software 11500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers * distributed under the License is distributed on an "AS IS" BASIS, 12500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers * See the License for the specific language governing permissions and 14500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers * limitations under the License. 15500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers */ 16500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers 17500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers#include "leb128.h" 18500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers 19558a694d88866c703bac31b1f0fff2b1a5afb05dIan Rogers#include "gtest/gtest.h" 20558a694d88866c703bac31b1f0fff2b1a5afb05dIan Rogers#include "base/histogram-inl.h" 2180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko#include "base/time_utils.h" 22500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers 23558a694d88866c703bac31b1f0fff2b1a5afb05dIan Rogersnamespace art { 24500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers 25500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogersstruct DecodeUnsignedLeb128TestCase { 26500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers uint32_t decoded; 27500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers uint8_t leb128_data[5]; 28500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers}; 29500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers 30500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogersstatic DecodeUnsignedLeb128TestCase uleb128_tests[] = { 31500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers {0, {0, 0, 0, 0, 0}}, 32500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers {1, {1, 0, 0, 0, 0}}, 33500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers {0x7F, {0x7F, 0, 0, 0, 0}}, 34500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers {0x80, {0x80, 1, 0, 0, 0}}, 35500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers {0x81, {0x81, 1, 0, 0, 0}}, 36500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers {0xFF, {0xFF, 1, 0, 0, 0}}, 37500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers {0x4000, {0x80, 0x80, 1, 0, 0}}, 38500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers {0x4001, {0x81, 0x80, 1, 0, 0}}, 39500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers {0x4081, {0x81, 0x81, 1, 0, 0}}, 40500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers {0x0FFFFFFF, {0xFF, 0xFF, 0xFF, 0x7F, 0}}, 41500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers {0xFFFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0xF}}, 42500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers}; 43500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers 441e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Markostruct DecodeSignedLeb128TestCase { 451e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko int32_t decoded; 461e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko uint8_t leb128_data[5]; 471e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko}; 481e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko 491e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Markostatic DecodeSignedLeb128TestCase sleb128_tests[] = { 501e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0, {0, 0, 0, 0, 0}}, 511e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {1, {1, 0, 0, 0, 0}}, 521e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x3F, {0x3F, 0, 0, 0, 0}}, 531e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x40, {0xC0, 0 /* sign bit */, 0, 0, 0}}, 541e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x41, {0xC1, 0 /* sign bit */, 0, 0, 0}}, 551e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x80, {0x80, 1, 0, 0, 0}}, 561e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0xFF, {0xFF, 1, 0, 0, 0}}, 571e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x1FFF, {0xFF, 0x3F, 0, 0, 0}}, 581e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x2000, {0x80, 0xC0, 0 /* sign bit */, 0, 0}}, 591e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x2001, {0x81, 0xC0, 0 /* sign bit */, 0, 0}}, 601e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x2081, {0x81, 0xC1, 0 /* sign bit */, 0, 0}}, 611e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x4000, {0x80, 0x80, 1, 0, 0}}, 621e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x0FFFFF, {0xFF, 0xFF, 0x3F, 0, 0}}, 631e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x100000, {0x80, 0x80, 0xC0, 0 /* sign bit */, 0}}, 641e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x100001, {0x81, 0x80, 0xC0, 0 /* sign bit */, 0}}, 651e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x100081, {0x81, 0x81, 0xC0, 0 /* sign bit */, 0}}, 661e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x104081, {0x81, 0x81, 0xC1, 0 /* sign bit */, 0}}, 671e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x200000, {0x80, 0x80, 0x80, 1, 0}}, 681e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x7FFFFFF, {0xFF, 0xFF, 0xFF, 0x3F, 0}}, 691e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x8000000, {0x80, 0x80, 0x80, 0xC0, 0 /* sign bit */}}, 701e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x8000001, {0x81, 0x80, 0x80, 0xC0, 0 /* sign bit */}}, 711e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x8000081, {0x81, 0x81, 0x80, 0xC0, 0 /* sign bit */}}, 721e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x8004081, {0x81, 0x81, 0x81, 0xC0, 0 /* sign bit */}}, 731e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x8204081, {0x81, 0x81, 0x81, 0xC1, 0 /* sign bit */}}, 741e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x0FFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0 /* sign bit */}}, 751e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x10000000, {0x80, 0x80, 0x80, 0x80, 1}}, 761e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {0x7FFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0x7}}, 771e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {-1, {0x7F, 0, 0, 0, 0}}, 781e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {-2, {0x7E, 0, 0, 0, 0}}, 791e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {-0x3F, {0x41, 0, 0, 0, 0}}, 801e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {-0x40, {0x40, 0, 0, 0, 0}}, 811e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {-0x41, {0xBF, 0x7F, 0, 0, 0}}, 821e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {-0x80, {0x80, 0x7F, 0, 0, 0}}, 831e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {-0x81, {0xFF, 0x7E, 0, 0, 0}}, 841e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {-0x00002000, {0x80, 0x40, 0, 0, 0}}, 851e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {-0x00002001, {0xFF, 0xBF, 0x7F, 0, 0}}, 861e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {-0x00100000, {0x80, 0x80, 0x40, 0, 0}}, 871e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {-0x00100001, {0xFF, 0xFF, 0xBF, 0x7F, 0}}, 881e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {-0x08000000, {0x80, 0x80, 0x80, 0x40, 0}}, 891e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {-0x08000001, {0xFF, 0xFF, 0xFF, 0xBF, 0x7F}}, 901e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko {-0x20000000, {0x80, 0x80, 0x80, 0x80, 0x7E}}, 9158554b7de4b437ddef7ff550e62c8ec0b16f9264Andreas Gampe {static_cast<int32_t>(0x80000000), {0x80, 0x80, 0x80, 0x80, 0x78}}, 921e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko}; 931e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko 94558a694d88866c703bac31b1f0fff2b1a5afb05dIan RogersTEST(Leb128Test, UnsignedSinglesVector) { 95500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers // Test individual encodings. 96500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers for (size_t i = 0; i < arraysize(uleb128_tests); ++i) { 97f9f6441c665b5ff9004d3ed55014f46d416fb1bbVladimir Marko Leb128EncodingVector<> builder; 981e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko builder.PushBackUnsigned(uleb128_tests[i].decoded); 9906606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(UnsignedLeb128Size(uleb128_tests[i].decoded), builder.GetData().size()); 100500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0]; 101500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers const uint8_t* encoded_data_ptr = &builder.GetData()[0]; 102500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers for (size_t j = 0; j < 5; ++j) { 103500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers if (j < builder.GetData().size()) { 104500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j; 105500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers } else { 106500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j; 107500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers } 108500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers } 109500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers EXPECT_EQ(DecodeUnsignedLeb128(&data_ptr), uleb128_tests[i].decoded) << " i = " << i; 110500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers } 111500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers} 112500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers 113558a694d88866c703bac31b1f0fff2b1a5afb05dIan RogersTEST(Leb128Test, UnsignedSingles) { 11406606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko // Test individual encodings. 11506606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko for (size_t i = 0; i < arraysize(uleb128_tests); ++i) { 11606606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko uint8_t encoded_data[5]; 11706606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko uint8_t* end = EncodeUnsignedLeb128(encoded_data, uleb128_tests[i].decoded); 11806606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko size_t data_size = static_cast<size_t>(end - encoded_data); 11906606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(UnsignedLeb128Size(uleb128_tests[i].decoded), data_size); 12006606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0]; 12106606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko for (size_t j = 0; j < 5; ++j) { 12206606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko if (j < data_size) { 12306606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(data_ptr[j], encoded_data[j]) << " i = " << i << " j = " << j; 12406606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko } else { 12506606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j; 12606606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko } 12706606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko } 12806606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(DecodeUnsignedLeb128(&data_ptr), uleb128_tests[i].decoded) << " i = " << i; 12906606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko } 13006606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko} 13106606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko 132558a694d88866c703bac31b1f0fff2b1a5afb05dIan RogersTEST(Leb128Test, UnsignedStreamVector) { 133500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers // Encode a number of entries. 134f9f6441c665b5ff9004d3ed55014f46d416fb1bbVladimir Marko Leb128EncodingVector<> builder; 135500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers for (size_t i = 0; i < arraysize(uleb128_tests); ++i) { 1361e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko builder.PushBackUnsigned(uleb128_tests[i].decoded); 137500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers } 138500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers const uint8_t* encoded_data_ptr = &builder.GetData()[0]; 139500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers for (size_t i = 0; i < arraysize(uleb128_tests); ++i) { 140500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0]; 14106606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko for (size_t j = 0; j < UnsignedLeb128Size(uleb128_tests[i].decoded); ++j) { 14206606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j; 14306606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko } 14406606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko for (size_t j = UnsignedLeb128Size(uleb128_tests[i].decoded); j < 5; ++j) { 14506606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j; 146500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers } 147500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers EXPECT_EQ(DecodeUnsignedLeb128(&encoded_data_ptr), uleb128_tests[i].decoded) << " i = " << i; 148500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers } 14906606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(builder.GetData().size(), 15006606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko static_cast<size_t>(encoded_data_ptr - &builder.GetData()[0])); 151500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers} 152500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers 153558a694d88866c703bac31b1f0fff2b1a5afb05dIan RogersTEST(Leb128Test, UnsignedStream) { 15406606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko // Encode a number of entries. 15506606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko uint8_t encoded_data[5 * arraysize(uleb128_tests)]; 15606606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko uint8_t* end = encoded_data; 15706606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko for (size_t i = 0; i < arraysize(uleb128_tests); ++i) { 15806606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko end = EncodeUnsignedLeb128(end, uleb128_tests[i].decoded); 15906606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko } 16006606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko size_t data_size = static_cast<size_t>(end - encoded_data); 16106606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko const uint8_t* encoded_data_ptr = encoded_data; 16206606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko for (size_t i = 0; i < arraysize(uleb128_tests); ++i) { 16306606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0]; 16406606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko for (size_t j = 0; j < UnsignedLeb128Size(uleb128_tests[i].decoded); ++j) { 16506606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j; 16606606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko } 16706606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko for (size_t j = UnsignedLeb128Size(uleb128_tests[i].decoded); j < 5; ++j) { 16806606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j; 16906606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko } 17006606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(DecodeUnsignedLeb128(&encoded_data_ptr), uleb128_tests[i].decoded) << " i = " << i; 17106606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko } 17206606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(data_size, static_cast<size_t>(encoded_data_ptr - encoded_data)); 17306606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko} 17406606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko 175558a694d88866c703bac31b1f0fff2b1a5afb05dIan RogersTEST(Leb128Test, SignedSinglesVector) { 1761e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko // Test individual encodings. 1771e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko for (size_t i = 0; i < arraysize(sleb128_tests); ++i) { 178f9f6441c665b5ff9004d3ed55014f46d416fb1bbVladimir Marko Leb128EncodingVector<> builder; 1791e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko builder.PushBackSigned(sleb128_tests[i].decoded); 18006606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(SignedLeb128Size(sleb128_tests[i].decoded), builder.GetData().size()); 1811e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0]; 1821e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko const uint8_t* encoded_data_ptr = &builder.GetData()[0]; 1831e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko for (size_t j = 0; j < 5; ++j) { 1841e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko if (j < builder.GetData().size()) { 1851e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j; 1861e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko } else { 1871e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j; 1881e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko } 1891e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko } 1901e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko EXPECT_EQ(DecodeSignedLeb128(&data_ptr), sleb128_tests[i].decoded) << " i = " << i; 1911e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko } 1921e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko} 1931e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko 194558a694d88866c703bac31b1f0fff2b1a5afb05dIan RogersTEST(Leb128Test, SignedSingles) { 19506606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko // Test individual encodings. 19606606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko for (size_t i = 0; i < arraysize(sleb128_tests); ++i) { 19706606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko uint8_t encoded_data[5]; 19806606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko uint8_t* end = EncodeSignedLeb128(encoded_data, sleb128_tests[i].decoded); 19906606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko size_t data_size = static_cast<size_t>(end - encoded_data); 20006606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(SignedLeb128Size(sleb128_tests[i].decoded), data_size); 20106606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0]; 20206606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko for (size_t j = 0; j < 5; ++j) { 20306606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko if (j < data_size) { 20406606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(data_ptr[j], encoded_data[j]) << " i = " << i << " j = " << j; 20506606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko } else { 20606606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j; 20706606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko } 20806606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko } 20906606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(DecodeSignedLeb128(&data_ptr), sleb128_tests[i].decoded) << " i = " << i; 21006606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko } 21106606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko} 21206606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko 213558a694d88866c703bac31b1f0fff2b1a5afb05dIan RogersTEST(Leb128Test, SignedStreamVector) { 2141e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko // Encode a number of entries. 215f9f6441c665b5ff9004d3ed55014f46d416fb1bbVladimir Marko Leb128EncodingVector<> builder; 2161e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko for (size_t i = 0; i < arraysize(sleb128_tests); ++i) { 2171e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko builder.PushBackSigned(sleb128_tests[i].decoded); 2181e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko } 2191e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko const uint8_t* encoded_data_ptr = &builder.GetData()[0]; 2201e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko for (size_t i = 0; i < arraysize(sleb128_tests); ++i) { 2211e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0]; 22206606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko for (size_t j = 0; j < SignedLeb128Size(sleb128_tests[i].decoded); ++j) { 22306606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j; 22406606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko } 22506606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko for (size_t j = SignedLeb128Size(sleb128_tests[i].decoded); j < 5; ++j) { 22606606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j; 22706606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko } 22806606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(DecodeSignedLeb128(&encoded_data_ptr), sleb128_tests[i].decoded) << " i = " << i; 22906606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko } 23006606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(builder.GetData().size(), 23106606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko static_cast<size_t>(encoded_data_ptr - &builder.GetData()[0])); 23206606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko} 23306606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko 234558a694d88866c703bac31b1f0fff2b1a5afb05dIan RogersTEST(Leb128Test, SignedStream) { 23506606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko // Encode a number of entries. 23606606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko uint8_t encoded_data[5 * arraysize(sleb128_tests)]; 23706606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko uint8_t* end = encoded_data; 23806606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko for (size_t i = 0; i < arraysize(sleb128_tests); ++i) { 23906606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko end = EncodeSignedLeb128(end, sleb128_tests[i].decoded); 24006606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko } 24106606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko size_t data_size = static_cast<size_t>(end - encoded_data); 24206606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko const uint8_t* encoded_data_ptr = encoded_data; 24306606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko for (size_t i = 0; i < arraysize(sleb128_tests); ++i) { 24406606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0]; 24506606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko for (size_t j = 0; j < SignedLeb128Size(sleb128_tests[i].decoded); ++j) { 24606606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j; 24706606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko } 24806606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko for (size_t j = SignedLeb128Size(sleb128_tests[i].decoded); j < 5; ++j) { 24906606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j; 2501e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko } 2511e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko EXPECT_EQ(DecodeSignedLeb128(&encoded_data_ptr), sleb128_tests[i].decoded) << " i = " << i; 2521e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko } 25306606b9c4a1c00154ed15f719ad8ea994e54ee8eVladimir Marko EXPECT_EQ(data_size, static_cast<size_t>(encoded_data_ptr - encoded_data)); 2541e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko} 2551e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko 256b536247b1ce5de640eec81dddac47802cd074363David SrbeckyTEST(Leb128Test, UnsignedUpdate) { 257b536247b1ce5de640eec81dddac47802cd074363David Srbecky for (size_t i = 0; i < arraysize(uleb128_tests); ++i) { 258b536247b1ce5de640eec81dddac47802cd074363David Srbecky for (size_t j = 0; j < arraysize(uleb128_tests); ++j) { 259b536247b1ce5de640eec81dddac47802cd074363David Srbecky uint32_t old_value = uleb128_tests[i].decoded; 260b536247b1ce5de640eec81dddac47802cd074363David Srbecky uint32_t new_value = uleb128_tests[j].decoded; 261b536247b1ce5de640eec81dddac47802cd074363David Srbecky // We can only make the encoded value smaller. 262b536247b1ce5de640eec81dddac47802cd074363David Srbecky if (new_value <= old_value) { 263b536247b1ce5de640eec81dddac47802cd074363David Srbecky uint8_t encoded_data[5]; 264b536247b1ce5de640eec81dddac47802cd074363David Srbecky uint8_t* old_end = EncodeUnsignedLeb128(encoded_data, old_value); 265b536247b1ce5de640eec81dddac47802cd074363David Srbecky UpdateUnsignedLeb128(encoded_data, new_value); 266b536247b1ce5de640eec81dddac47802cd074363David Srbecky const uint8_t* new_end = encoded_data; 267b536247b1ce5de640eec81dddac47802cd074363David Srbecky EXPECT_EQ(DecodeUnsignedLeb128(&new_end), new_value); 268b536247b1ce5de640eec81dddac47802cd074363David Srbecky // Even if the new value needs fewer bytes, we should fill the space. 269b536247b1ce5de640eec81dddac47802cd074363David Srbecky EXPECT_EQ(new_end, old_end); 270b536247b1ce5de640eec81dddac47802cd074363David Srbecky } 271b536247b1ce5de640eec81dddac47802cd074363David Srbecky } 272b536247b1ce5de640eec81dddac47802cd074363David Srbecky } 273b536247b1ce5de640eec81dddac47802cd074363David Srbecky} 274b536247b1ce5de640eec81dddac47802cd074363David Srbecky 275558a694d88866c703bac31b1f0fff2b1a5afb05dIan RogersTEST(Leb128Test, Speed) { 276700a402244a1a423da4f3ba8032459f4b65fa18fIan Rogers std::unique_ptr<Histogram<uint64_t>> enc_hist(new Histogram<uint64_t>("Leb128EncodeSpeedTest", 5)); 277700a402244a1a423da4f3ba8032459f4b65fa18fIan Rogers std::unique_ptr<Histogram<uint64_t>> dec_hist(new Histogram<uint64_t>("Leb128DecodeSpeedTest", 5)); 278f9f6441c665b5ff9004d3ed55014f46d416fb1bbVladimir Marko Leb128EncodingVector<> builder; 279500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers // Push back 1024 chunks of 1024 values measuring encoding speed. 280500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers uint64_t last_time = NanoTime(); 281500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers for (size_t i = 0; i < 1024; i++) { 282500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers for (size_t j = 0; j < 1024; j++) { 2831e6cb63d77090ddc6aa19c755d7066f66e9ff87eVladimir Marko builder.PushBackUnsigned((i * 1024) + j); 284500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers } 285500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers uint64_t cur_time = NanoTime(); 286500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers enc_hist->AddValue(cur_time - last_time); 287500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers last_time = cur_time; 288500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers } 289500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers // Verify encoding and measure decode speed. 290500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers const uint8_t* encoded_data_ptr = &builder.GetData()[0]; 291500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers last_time = NanoTime(); 292500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers for (size_t i = 0; i < 1024; i++) { 293500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers for (size_t j = 0; j < 1024; j++) { 294500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers EXPECT_EQ(DecodeUnsignedLeb128(&encoded_data_ptr), (i * 1024) + j); 295500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers } 296500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers uint64_t cur_time = NanoTime(); 297500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers dec_hist->AddValue(cur_time - last_time); 298500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers last_time = cur_time; 299500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers } 300500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers 301500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers Histogram<uint64_t>::CumulativeData enc_data; 302500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers enc_hist->CreateHistogram(&enc_data); 303500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers enc_hist->PrintConfidenceIntervals(std::cout, 0.99, enc_data); 304500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers 305500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers Histogram<uint64_t>::CumulativeData dec_data; 306500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers dec_hist->CreateHistogram(&dec_data); 307500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers dec_hist->PrintConfidenceIntervals(std::cout, 0.99, dec_data); 308500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers} 309500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers 310500793f33b8af8bc7ccf5595a66b4b13bce766bcIan Rogers} // namespace art 311