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