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 311
