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