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 #include "base/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     {(-1) << 31, {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