leb128_test.cc revision f9f6441c665b5ff9004d3ed55014f46d416fb1bb 
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
23namespace art {
24
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
44struct 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}},
91    {(-1) << 31, {0x80, 0x80, 0x80, 0x80, 0x78}},
92};
93
94TEST(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
113TEST(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
132TEST(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
153TEST(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
175TEST(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
194TEST(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
213TEST(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
234TEST(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
256TEST(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
275TEST(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