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
TEST(Leb128Test,UnsignedSinglesVector)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
TEST(Leb128Test,UnsignedSingles)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
TEST(Leb128Test,UnsignedStreamVector)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
TEST(Leb128Test,UnsignedStream)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
TEST(Leb128Test,SignedSinglesVector)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
TEST(Leb128Test,SignedSingles)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
TEST(Leb128Test,SignedStreamVector)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
TEST(Leb128Test,SignedStream)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
TEST(Leb128Test,UnsignedUpdate)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
TEST(Leb128Test,Speed)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