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