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