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
22namespace art {
23
24struct DecodeUnsignedLeb128TestCase {
25  uint32_t decoded;
26  uint8_t leb128_data[5];
27};
28
29static 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
43struct DecodeSignedLeb128TestCase {
44  int32_t decoded;
45  uint8_t leb128_data[5];
46};
47
48static 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
93TEST(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
112TEST(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
131TEST(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
152TEST(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
174TEST(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
193TEST(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
212TEST(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
233TEST(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
255TEST(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