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 "histogram-inl.h"
21 #include "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 const 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 Decode64bitUnsignedLeb128TestCase {
45 uint64_t decoded;
46 uint8_t leb128_data[10];
47 };
48
49 static const Decode64bitUnsignedLeb128TestCase uleb128_64bit_tests[] = {
50 {0, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}},
51 {1, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0}},
52 {0x7F, {0x7F, 0, 0, 0, 0, 0, 0, 0, 0, 0}},
53 {0x80, {0x80, 1, 0, 0, 0, 0, 0, 0, 0, 0}},
54 {0x81, {0x81, 1, 0, 0, 0, 0, 0, 0, 0, 0}},
55 {0xFF, {0xFF, 1, 0, 0, 0, 0, 0, 0, 0, 0}},
56 {0x4000, {0x80, 0x80, 1, 0, 0, 0, 0, 0, 0, 0}},
57 {0x4001, {0x81, 0x80, 1, 0, 0, 0, 0, 0, 0, 0}},
58 {0x4081, {0x81, 0x81, 1, 0, 0, 0, 0, 0, 0, 0}},
59 {0x0FFFFFFF, {0xFF, 0xFF, 0xFF, 0x7F, 0, 0, 0, 0, 0, 0}},
60 {0xFFFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0xF, 0, 0, 0, 0, 0}},
61 {0x1FFFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0x1F, 0, 0, 0, 0, 0}},
62 {0x100000000, {0x80, 0x80, 0x80, 0x80, 0x10, 0, 0, 0, 0, 0}},
63 {0x8FFFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0x8F, 0x01, 0, 0, 0, 0}},
64 {0x8000000000000000, {0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x01}},
65 {0xFFFFFFFFFFFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x01}},
66 };
67
68 struct DecodeSignedLeb128TestCase {
69 int32_t decoded;
70 uint8_t leb128_data[5];
71 };
72
73 static const DecodeSignedLeb128TestCase sleb128_tests[] = {
74 {0, {0, 0, 0, 0, 0}},
75 {1, {1, 0, 0, 0, 0}},
76 {0x3F, {0x3F, 0, 0, 0, 0}},
77 {0x40, {0xC0, 0 /* sign bit */, 0, 0, 0}},
78 {0x41, {0xC1, 0 /* sign bit */, 0, 0, 0}},
79 {0x80, {0x80, 1, 0, 0, 0}},
80 {0xFF, {0xFF, 1, 0, 0, 0}},
81 {0x1FFF, {0xFF, 0x3F, 0, 0, 0}},
82 {0x2000, {0x80, 0xC0, 0 /* sign bit */, 0, 0}},
83 {0x2001, {0x81, 0xC0, 0 /* sign bit */, 0, 0}},
84 {0x2081, {0x81, 0xC1, 0 /* sign bit */, 0, 0}},
85 {0x4000, {0x80, 0x80, 1, 0, 0}},
86 {0x0FFFFF, {0xFF, 0xFF, 0x3F, 0, 0}},
87 {0x100000, {0x80, 0x80, 0xC0, 0 /* sign bit */, 0}},
88 {0x100001, {0x81, 0x80, 0xC0, 0 /* sign bit */, 0}},
89 {0x100081, {0x81, 0x81, 0xC0, 0 /* sign bit */, 0}},
90 {0x104081, {0x81, 0x81, 0xC1, 0 /* sign bit */, 0}},
91 {0x200000, {0x80, 0x80, 0x80, 1, 0}},
92 {0x7FFFFFF, {0xFF, 0xFF, 0xFF, 0x3F, 0}},
93 {0x8000000, {0x80, 0x80, 0x80, 0xC0, 0 /* sign bit */}},
94 {0x8000001, {0x81, 0x80, 0x80, 0xC0, 0 /* sign bit */}},
95 {0x8000081, {0x81, 0x81, 0x80, 0xC0, 0 /* sign bit */}},
96 {0x8004081, {0x81, 0x81, 0x81, 0xC0, 0 /* sign bit */}},
97 {0x8204081, {0x81, 0x81, 0x81, 0xC1, 0 /* sign bit */}},
98 {0x0FFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0 /* sign bit */}},
99 {0x10000000, {0x80, 0x80, 0x80, 0x80, 1}},
100 {0x7FFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0x7}},
101 {-1, {0x7F, 0, 0, 0, 0}},
102 {-2, {0x7E, 0, 0, 0, 0}},
103 {-0x3F, {0x41, 0, 0, 0, 0}},
104 {-0x40, {0x40, 0, 0, 0, 0}},
105 {-0x41, {0xBF, 0x7F, 0, 0, 0}},
106 {-0x80, {0x80, 0x7F, 0, 0, 0}},
107 {-0x81, {0xFF, 0x7E, 0, 0, 0}},
108 {-0x00002000, {0x80, 0x40, 0, 0, 0}},
109 {-0x00002001, {0xFF, 0xBF, 0x7F, 0, 0}},
110 {-0x00100000, {0x80, 0x80, 0x40, 0, 0}},
111 {-0x00100001, {0xFF, 0xFF, 0xBF, 0x7F, 0}},
112 {-0x08000000, {0x80, 0x80, 0x80, 0x40, 0}},
113 {-0x08000001, {0xFF, 0xFF, 0xFF, 0xBF, 0x7F}},
114 {-0x20000000, {0x80, 0x80, 0x80, 0x80, 0x7E}},
115 {static_cast<int32_t>(0x80000000), {0x80, 0x80, 0x80, 0x80, 0x78}},
116 };
117
118 struct Decode64bitSignedLeb128TestCase {
119 int64_t decoded;
120 uint8_t leb128_data[10];
121 };
122
123 static const Decode64bitSignedLeb128TestCase sleb128_64bit_tests[] = {
124 {0, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}},
125 {1, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0}},
126 {0x3F, {0x3F, 0, 0, 0, 0, 0, 0, 0, 0, 0}},
127 {0x40, {0xC0, 0 /* sign bit */, 0, 0, 0, 0, 0, 0, 0, 0}},
128 {0x800000000, {0x80, 0x80, 0x80, 0x80, 0x80, 0x01, 0, 0, 0, 0}},
129 {0x100000000, {0x80, 0x80, 0x80, 0x80, 0x10, 0, 0, 0, 0, 0}},
130 {0x700000000, {0x80, 0x80, 0x80, 0x80, 0xF0, 0 /* sign bit */, 0, 0, 0, 0}},
131 {0x704081002, {0x82, 0xA0, 0xA0, 0xA0, 0xF0, 0 /* sign bit*/, 0, 0, 0}},
132 {0x07FFFFFFFFFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x07, 0}},
133 {0x23FFFFFFFFFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x23, 0}},
134 {0x0800000000000000, {0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x08, 0}},
135 {0x0800000008400421, {0xA1, 0x88, 0x80, 0xC2, 0x80, 0x80, 0x80, 0x80, 0x08, 0}},
136 {0x70FFFFFFFFFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xF0, 0 /* sign bit*/}},
137 {0x7000000000000081, {0x81, 0x81, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0xF0, 0 /* sign bit*/}},
138 {0x0FFFFFFFFFFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x0F, 0}},
139 {-1, {0x7F, 0, 0, 0, 0, 0, 0, 0, 0, 0}},
140 {-2, {0x7E, 0, 0, 0, 0, 0, 0, 0, 0, 0}},
141 {-0x3F, {0x41, 0, 0, 0, 0, 0, 0, 0, 0, 0}},
142 {-0x40, {0x40, 0, 0, 0, 0, 0, 0, 0, 0, 0}},
143 {-0x200000000, {0x80, 0x80, 0x80, 0x80, 0x60, 0, 0, 0, 0}},
144 {-0x200000001, {0xFF, 0xFF, 0xFF, 0xFF, 0x5F, 0, 0, 0, 0}},
145 {-0x0800000000000000, {0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x78, 0}},
146 {-0x0800000000000001, {0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x77, 0}},
147 {-0x2000000000000000, {0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x60, 0}},
148 {static_cast<int64_t>(0x8000000000000000),
149 {0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x7F}},
150 };
151
TEST(Leb128Test,UnsignedSinglesVector)152 TEST(Leb128Test, UnsignedSinglesVector) {
153 // Test individual encodings.
154 for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
155 Leb128EncodingVector<> builder;
156 builder.PushBackUnsigned(uleb128_tests[i].decoded);
157 EXPECT_EQ(UnsignedLeb128Size(uleb128_tests[i].decoded), builder.GetData().size());
158 const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0];
159 const uint8_t* encoded_data_ptr = &builder.GetData()[0];
160 for (size_t j = 0; j < 5; ++j) {
161 if (j < builder.GetData().size()) {
162 EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
163 } else {
164 EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
165 }
166 }
167 EXPECT_EQ(DecodeUnsignedLeb128(&data_ptr), uleb128_tests[i].decoded) << " i = " << i;
168 }
169 }
170
TEST(Leb128Test,UnsignedSingles)171 TEST(Leb128Test, UnsignedSingles) {
172 // Test individual encodings.
173 for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
174 uint8_t encoded_data[5];
175 uint8_t* end = EncodeUnsignedLeb128(encoded_data, uleb128_tests[i].decoded);
176 size_t data_size = static_cast<size_t>(end - encoded_data);
177 EXPECT_EQ(UnsignedLeb128Size(uleb128_tests[i].decoded), data_size);
178 const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0];
179 for (size_t j = 0; j < 5; ++j) {
180 if (j < data_size) {
181 EXPECT_EQ(data_ptr[j], encoded_data[j]) << " i = " << i << " j = " << j;
182 } else {
183 EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
184 }
185 }
186 EXPECT_EQ(DecodeUnsignedLeb128(&data_ptr), uleb128_tests[i].decoded) << " i = " << i;
187 }
188 }
189
TEST(Leb128Test,UnsignedSingles64bit)190 TEST(Leb128Test, UnsignedSingles64bit) {
191 // Test individual encodings.
192 for (size_t i = 0; i < arraysize(uleb128_64bit_tests); ++i) {
193 uint8_t encoded_data[10];
194 uint8_t* end = EncodeUnsignedLeb128(encoded_data, uleb128_64bit_tests[i].decoded);
195 size_t data_size = static_cast<size_t>(end - encoded_data);
196 EXPECT_EQ(UnsignedLeb128Size(uleb128_64bit_tests[i].decoded), data_size);
197 const uint8_t* data_ptr = &uleb128_64bit_tests[i].leb128_data[0];
198 for (size_t j = 0; j < 10; ++j) {
199 if (j < data_size) {
200 EXPECT_EQ(data_ptr[j], encoded_data[j]) << " i = " << i << " j = " << j;
201 } else {
202 EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
203 }
204 }
205 EXPECT_EQ(DecodeUnsignedLeb128<uint64_t>(&data_ptr), uleb128_64bit_tests[i].decoded)
206 << " i = " << i;
207 }
208 }
209
TEST(Leb128Test,UnsignedStreamVector)210 TEST(Leb128Test, UnsignedStreamVector) {
211 // Encode a number of entries.
212 Leb128EncodingVector<> builder;
213 for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
214 builder.PushBackUnsigned(uleb128_tests[i].decoded);
215 }
216 const uint8_t* encoded_data_ptr = &builder.GetData()[0];
217 for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
218 const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0];
219 for (size_t j = 0; j < UnsignedLeb128Size(uleb128_tests[i].decoded); ++j) {
220 EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
221 }
222 for (size_t j = UnsignedLeb128Size(uleb128_tests[i].decoded); j < 5; ++j) {
223 EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j;
224 }
225 EXPECT_EQ(DecodeUnsignedLeb128(&encoded_data_ptr), uleb128_tests[i].decoded) << " i = " << i;
226 }
227 EXPECT_EQ(builder.GetData().size(),
228 static_cast<size_t>(encoded_data_ptr - &builder.GetData()[0]));
229 }
230
TEST(Leb128Test,UnsignedStream)231 TEST(Leb128Test, UnsignedStream) {
232 // Encode a number of entries.
233 uint8_t encoded_data[5 * arraysize(uleb128_tests)];
234 uint8_t* end = encoded_data;
235 for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
236 end = EncodeUnsignedLeb128(end, uleb128_tests[i].decoded);
237 }
238 size_t data_size = static_cast<size_t>(end - encoded_data);
239 const uint8_t* encoded_data_ptr = encoded_data;
240 for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
241 const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0];
242 for (size_t j = 0; j < UnsignedLeb128Size(uleb128_tests[i].decoded); ++j) {
243 EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
244 }
245 for (size_t j = UnsignedLeb128Size(uleb128_tests[i].decoded); j < 5; ++j) {
246 EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j;
247 }
248 EXPECT_EQ(DecodeUnsignedLeb128(&encoded_data_ptr), uleb128_tests[i].decoded) << " i = " << i;
249 }
250 EXPECT_EQ(data_size, static_cast<size_t>(encoded_data_ptr - encoded_data));
251 }
252
TEST(Leb128Test,Unsigned64bitStream)253 TEST(Leb128Test, Unsigned64bitStream) {
254 // Encode a number of entries.
255 uint8_t encoded_data[10 * arraysize(uleb128_64bit_tests)];
256 uint8_t* end = encoded_data;
257 for (size_t i = 0; i < arraysize(uleb128_64bit_tests); ++i) {
258 end = EncodeUnsignedLeb128(end, uleb128_64bit_tests[i].decoded);
259 }
260 size_t data_size = static_cast<size_t>(end - encoded_data);
261 const uint8_t* encoded_data_ptr = encoded_data;
262 for (size_t i = 0; i < arraysize(uleb128_64bit_tests); ++i) {
263 const uint8_t* data_ptr = &uleb128_64bit_tests[i].leb128_data[0];
264 for (size_t j = 0; j < UnsignedLeb128Size(uleb128_64bit_tests[i].decoded); ++j) {
265 EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
266 }
267 for (size_t j = UnsignedLeb128Size(uleb128_64bit_tests[i].decoded); j < 10; ++j) {
268 EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
269 }
270 EXPECT_EQ(DecodeUnsignedLeb128<uint64_t>(&encoded_data_ptr), uleb128_64bit_tests[i].decoded)
271 << " i = " << i;
272 }
273 EXPECT_EQ(data_size, static_cast<size_t>(encoded_data_ptr - encoded_data));
274 }
275
TEST(Leb128Test,SignedSinglesVector)276 TEST(Leb128Test, SignedSinglesVector) {
277 // Test individual encodings.
278 for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
279 Leb128EncodingVector<> builder;
280 builder.PushBackSigned(sleb128_tests[i].decoded);
281 EXPECT_EQ(SignedLeb128Size(sleb128_tests[i].decoded), builder.GetData().size());
282 const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0];
283 const uint8_t* encoded_data_ptr = &builder.GetData()[0];
284 for (size_t j = 0; j < 5; ++j) {
285 if (j < builder.GetData().size()) {
286 EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
287 } else {
288 EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
289 }
290 }
291 EXPECT_EQ(DecodeSignedLeb128(&data_ptr), sleb128_tests[i].decoded) << " i = " << i;
292 }
293 }
294
TEST(Leb128Test,SignedSingles)295 TEST(Leb128Test, SignedSingles) {
296 // Test individual encodings.
297 for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
298 uint8_t encoded_data[5];
299 uint8_t* end = EncodeSignedLeb128(encoded_data, sleb128_tests[i].decoded);
300 size_t data_size = static_cast<size_t>(end - encoded_data);
301 EXPECT_EQ(SignedLeb128Size(sleb128_tests[i].decoded), data_size);
302 const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0];
303 for (size_t j = 0; j < 5; ++j) {
304 if (j < data_size) {
305 EXPECT_EQ(data_ptr[j], encoded_data[j]) << " i = " << i << " j = " << j;
306 } else {
307 EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
308 }
309 }
310 EXPECT_EQ(DecodeSignedLeb128(&data_ptr), sleb128_tests[i].decoded) << " i = " << i;
311 }
312 }
313
TEST(Leb128Test,SignedSingles64bit)314 TEST(Leb128Test, SignedSingles64bit) {
315 // Test individual encodings.
316 for (size_t i = 0; i < arraysize(sleb128_64bit_tests); ++i) {
317 uint8_t encoded_data[10];
318 uint8_t* end = EncodeSignedLeb128(encoded_data, sleb128_64bit_tests[i].decoded);
319 size_t data_size = static_cast<size_t>(end - encoded_data);
320 EXPECT_EQ(SignedLeb128Size(sleb128_64bit_tests[i].decoded), data_size);
321 const uint8_t* data_ptr = &sleb128_64bit_tests[i].leb128_data[0];
322 for (size_t j = 0; j < 10; ++j) {
323 if (j < data_size) {
324 EXPECT_EQ(data_ptr[j], encoded_data[j]) << " i = " << i << " j = " << j;
325 } else {
326 EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
327 }
328 }
329 EXPECT_EQ(DecodeSignedLeb128<int64_t>(&data_ptr), sleb128_64bit_tests[i].decoded)
330 << " i = " << i;
331 }
332 }
333
TEST(Leb128Test,SignedStreamVector)334 TEST(Leb128Test, SignedStreamVector) {
335 // Encode a number of entries.
336 Leb128EncodingVector<> builder;
337 for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
338 builder.PushBackSigned(sleb128_tests[i].decoded);
339 }
340 const uint8_t* encoded_data_ptr = &builder.GetData()[0];
341 for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
342 const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0];
343 for (size_t j = 0; j < SignedLeb128Size(sleb128_tests[i].decoded); ++j) {
344 EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
345 }
346 for (size_t j = SignedLeb128Size(sleb128_tests[i].decoded); j < 5; ++j) {
347 EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j;
348 }
349 EXPECT_EQ(DecodeSignedLeb128(&encoded_data_ptr), sleb128_tests[i].decoded) << " i = " << i;
350 }
351 EXPECT_EQ(builder.GetData().size(),
352 static_cast<size_t>(encoded_data_ptr - &builder.GetData()[0]));
353 }
354
TEST(Leb128Test,SignedStream)355 TEST(Leb128Test, SignedStream) {
356 // Encode a number of entries.
357 uint8_t encoded_data[5 * arraysize(sleb128_tests)];
358 uint8_t* end = encoded_data;
359 for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
360 end = EncodeSignedLeb128(end, sleb128_tests[i].decoded);
361 }
362 size_t data_size = static_cast<size_t>(end - encoded_data);
363 const uint8_t* encoded_data_ptr = encoded_data;
364 for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
365 const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0];
366 for (size_t j = 0; j < SignedLeb128Size(sleb128_tests[i].decoded); ++j) {
367 EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
368 }
369 for (size_t j = SignedLeb128Size(sleb128_tests[i].decoded); j < 5; ++j) {
370 EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j;
371 }
372 EXPECT_EQ(DecodeSignedLeb128(&encoded_data_ptr), sleb128_tests[i].decoded) << " i = " << i;
373 }
374 EXPECT_EQ(data_size, static_cast<size_t>(encoded_data_ptr - encoded_data));
375 }
376
TEST(Leb128Test,SignedStream64bit)377 TEST(Leb128Test, SignedStream64bit) {
378 // Encode a number of entries.
379 uint8_t encoded_data[10 * arraysize(sleb128_64bit_tests)];
380 uint8_t* end = encoded_data;
381 for (size_t i = 0; i < arraysize(sleb128_64bit_tests); ++i) {
382 end = EncodeSignedLeb128(end, sleb128_64bit_tests[i].decoded);
383 }
384 size_t data_size = static_cast<size_t>(end - encoded_data);
385 const uint8_t* encoded_data_ptr = encoded_data;
386 for (size_t i = 0; i < arraysize(sleb128_64bit_tests); ++i) {
387 const uint8_t* data_ptr = &sleb128_64bit_tests[i].leb128_data[0];
388 for (size_t j = 0; j < SignedLeb128Size(sleb128_64bit_tests[i].decoded); ++j) {
389 EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
390 }
391 for (size_t j = SignedLeb128Size(sleb128_64bit_tests[i].decoded); j < 10; ++j) {
392 EXPECT_EQ(data_ptr[j], 0) << " i = " << i << " j = " << j;
393 }
394 EXPECT_EQ(DecodeSignedLeb128<int64_t>(&encoded_data_ptr), sleb128_64bit_tests[i].decoded)
395 << " i = " << i;
396 }
397 EXPECT_EQ(data_size, static_cast<size_t>(encoded_data_ptr - encoded_data));
398 }
399
TEST(Leb128Test,UnsignedUpdate)400 TEST(Leb128Test, UnsignedUpdate) {
401 for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
402 for (size_t j = 0; j < arraysize(uleb128_tests); ++j) {
403 uint32_t old_value = uleb128_tests[i].decoded;
404 uint32_t new_value = uleb128_tests[j].decoded;
405 // We can only make the encoded value smaller.
406 if (new_value <= old_value) {
407 uint8_t encoded_data[5];
408 uint8_t* old_end = EncodeUnsignedLeb128(encoded_data, old_value);
409 UpdateUnsignedLeb128(encoded_data, new_value);
410 const uint8_t* new_end = encoded_data;
411 EXPECT_EQ(DecodeUnsignedLeb128(&new_end), new_value);
412 // Even if the new value needs fewer bytes, we should fill the space.
413 EXPECT_EQ(new_end, old_end);
414 }
415 }
416 }
417 }
418
TEST(Leb128Test,Speed)419 TEST(Leb128Test, Speed) {
420 std::unique_ptr<Histogram<uint64_t>> enc_hist(new Histogram<uint64_t>("Leb128EncodeSpeedTest", 5));
421 std::unique_ptr<Histogram<uint64_t>> dec_hist(new Histogram<uint64_t>("Leb128DecodeSpeedTest", 5));
422 Leb128EncodingVector<> builder;
423 // Push back 1024 chunks of 1024 values measuring encoding speed.
424 uint64_t last_time = NanoTime();
425 for (size_t i = 0; i < 1024; i++) {
426 for (size_t j = 0; j < 1024; j++) {
427 builder.PushBackUnsigned((i * 1024) + j);
428 }
429 uint64_t cur_time = NanoTime();
430 enc_hist->AddValue(cur_time - last_time);
431 last_time = cur_time;
432 }
433 // Verify encoding and measure decode speed.
434 const uint8_t* encoded_data_ptr = &builder.GetData()[0];
435 last_time = NanoTime();
436 for (size_t i = 0; i < 1024; i++) {
437 for (size_t j = 0; j < 1024; j++) {
438 EXPECT_EQ(DecodeUnsignedLeb128(&encoded_data_ptr), (i * 1024) + j);
439 }
440 uint64_t cur_time = NanoTime();
441 dec_hist->AddValue(cur_time - last_time);
442 last_time = cur_time;
443 }
444
445 Histogram<uint64_t>::CumulativeData enc_data;
446 enc_hist->CreateHistogram(&enc_data);
447 enc_hist->PrintConfidenceIntervals(std::cout, 0.99, enc_data);
448
449 Histogram<uint64_t>::CumulativeData dec_data;
450 dec_hist->CreateHistogram(&dec_data);
451 dec_hist->PrintConfidenceIntervals(std::cout, 0.99, dec_data);
452 }
453
454 } // namespace art
455