blob: 122f55ebeea3e3442e23e4d59f681751f80cadd6 [file] [log] [blame]
Ian Rogers500793f2013-11-14 17:49:12 -08001/*
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
Ian Rogers500793f2013-11-14 17:49:12 -080017#include "leb128.h"
Ian Rogers500793f2013-11-14 17:49:12 -080018
Ian Rogers558a6942014-02-06 16:47:14 -080019#include "gtest/gtest.h"
20#include "base/histogram-inl.h"
Vladimir Marko80afd022015-05-19 18:08:00 +010021#include "base/time_utils.h"
Ian Rogers500793f2013-11-14 17:49:12 -080022
Ian Rogers558a6942014-02-06 16:47:14 -080023namespace art {
Ian Rogers500793f2013-11-14 17:49:12 -080024
25struct DecodeUnsignedLeb128TestCase {
26 uint32_t decoded;
27 uint8_t leb128_data[5];
28};
29
30static 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
Vladimir Marko1e6cb632013-11-28 16:27:29 +000044struct DecodeSignedLeb128TestCase {
45 int32_t decoded;
46 uint8_t leb128_data[5];
47};
48
49static 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}},
Andreas Gampe58554b72015-10-20 21:08:52 -070091 {static_cast<int32_t>(0x80000000), {0x80, 0x80, 0x80, 0x80, 0x78}},
Vladimir Marko1e6cb632013-11-28 16:27:29 +000092};
93
Ian Rogers558a6942014-02-06 16:47:14 -080094TEST(Leb128Test, UnsignedSinglesVector) {
Ian Rogers500793f2013-11-14 17:49:12 -080095 // Test individual encodings.
96 for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
Vladimir Markof9f64412015-09-02 14:05:49 +010097 Leb128EncodingVector<> builder;
Vladimir Marko1e6cb632013-11-28 16:27:29 +000098 builder.PushBackUnsigned(uleb128_tests[i].decoded);
Vladimir Marko06606b92013-12-02 15:31:08 +000099 EXPECT_EQ(UnsignedLeb128Size(uleb128_tests[i].decoded), builder.GetData().size());
Ian Rogers500793f2013-11-14 17:49:12 -0800100 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
Ian Rogers558a6942014-02-06 16:47:14 -0800113TEST(Leb128Test, UnsignedSingles) {
Vladimir Marko06606b92013-12-02 15:31:08 +0000114 // 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
Ian Rogers558a6942014-02-06 16:47:14 -0800132TEST(Leb128Test, UnsignedStreamVector) {
Ian Rogers500793f2013-11-14 17:49:12 -0800133 // Encode a number of entries.
Vladimir Markof9f64412015-09-02 14:05:49 +0100134 Leb128EncodingVector<> builder;
Ian Rogers500793f2013-11-14 17:49:12 -0800135 for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
Vladimir Marko1e6cb632013-11-28 16:27:29 +0000136 builder.PushBackUnsigned(uleb128_tests[i].decoded);
Ian Rogers500793f2013-11-14 17:49:12 -0800137 }
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];
Vladimir Marko06606b92013-12-02 15:31:08 +0000141 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;
Ian Rogers500793f2013-11-14 17:49:12 -0800146 }
147 EXPECT_EQ(DecodeUnsignedLeb128(&encoded_data_ptr), uleb128_tests[i].decoded) << " i = " << i;
148 }
Vladimir Marko06606b92013-12-02 15:31:08 +0000149 EXPECT_EQ(builder.GetData().size(),
150 static_cast<size_t>(encoded_data_ptr - &builder.GetData()[0]));
Ian Rogers500793f2013-11-14 17:49:12 -0800151}
152
Ian Rogers558a6942014-02-06 16:47:14 -0800153TEST(Leb128Test, UnsignedStream) {
Vladimir Marko06606b92013-12-02 15:31:08 +0000154 // 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
Ian Rogers558a6942014-02-06 16:47:14 -0800175TEST(Leb128Test, SignedSinglesVector) {
Vladimir Marko1e6cb632013-11-28 16:27:29 +0000176 // Test individual encodings.
177 for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
Vladimir Markof9f64412015-09-02 14:05:49 +0100178 Leb128EncodingVector<> builder;
Vladimir Marko1e6cb632013-11-28 16:27:29 +0000179 builder.PushBackSigned(sleb128_tests[i].decoded);
Vladimir Marko06606b92013-12-02 15:31:08 +0000180 EXPECT_EQ(SignedLeb128Size(sleb128_tests[i].decoded), builder.GetData().size());
Vladimir Marko1e6cb632013-11-28 16:27:29 +0000181 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
Ian Rogers558a6942014-02-06 16:47:14 -0800194TEST(Leb128Test, SignedSingles) {
Vladimir Marko06606b92013-12-02 15:31:08 +0000195 // 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
Ian Rogers558a6942014-02-06 16:47:14 -0800213TEST(Leb128Test, SignedStreamVector) {
Vladimir Marko1e6cb632013-11-28 16:27:29 +0000214 // Encode a number of entries.
Vladimir Markof9f64412015-09-02 14:05:49 +0100215 Leb128EncodingVector<> builder;
Vladimir Marko1e6cb632013-11-28 16:27:29 +0000216 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];
Vladimir Marko06606b92013-12-02 15:31:08 +0000222 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;
Vladimir Marko1e6cb632013-11-28 16:27:29 +0000227 }
228 EXPECT_EQ(DecodeSignedLeb128(&encoded_data_ptr), sleb128_tests[i].decoded) << " i = " << i;
229 }
Vladimir Marko06606b92013-12-02 15:31:08 +0000230 EXPECT_EQ(builder.GetData().size(),
231 static_cast<size_t>(encoded_data_ptr - &builder.GetData()[0]));
232}
233
Ian Rogers558a6942014-02-06 16:47:14 -0800234TEST(Leb128Test, SignedStream) {
Vladimir Marko06606b92013-12-02 15:31:08 +0000235 // 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));
Vladimir Marko1e6cb632013-11-28 16:27:29 +0000254}
255
David Srbeckyb5362472015-04-08 19:37:39 +0100256TEST(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
Ian Rogers558a6942014-02-06 16:47:14 -0800275TEST(Leb128Test, Speed) {
Ian Rogers700a4022014-05-19 16:49:03 -0700276 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));
Vladimir Markof9f64412015-09-02 14:05:49 +0100278 Leb128EncodingVector<> builder;
Ian Rogers500793f2013-11-14 17:49:12 -0800279 // 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++) {
Vladimir Marko1e6cb632013-11-28 16:27:29 +0000283 builder.PushBackUnsigned((i * 1024) + j);
Ian Rogers500793f2013-11-14 17:49:12 -0800284 }
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