1// Copyright 2008 Google Inc.
2// Author: Lincoln Smith
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#include <config.h>
17#include "varint_bigendian.h"
18#include <stdlib.h>  // rand, srand
19#include <string.h>  // strlen
20#include <string>
21#include <vector>
22#include "testing.h"
23
24namespace open_vcdiff {
25namespace {
26
27class VarintBETestCommon : public testing::Test {
28 protected:
29  typedef std::string string;
30
31  VarintBETestCommon()
32      : varint_buf_(VarintBE<int64_t>::kMaxBytes),
33        verify_encoded_byte_index_(0),
34        verify_expected_length_(0),
35        parse_data_ptr_(parse_data_all_FFs) {
36  }
37
38  virtual ~VarintBETestCommon() { }
39
40  void ExpectEncodedByte(char expected_byte) {
41    EXPECT_EQ(expected_byte, varint_buf_[verify_encoded_byte_index_]);
42    EXPECT_EQ(expected_byte, s_[verify_encoded_byte_index_]);
43    ++verify_encoded_byte_index_;
44  }
45
46  static const char parse_data_all_FFs[];
47  static const char parse_data_CADA1[];
48
49  std::vector<char> varint_buf_;
50  string s_;
51  int verify_encoded_byte_index_;
52  int verify_expected_length_;
53  const char* parse_data_ptr_;
54};
55
56template <typename SignedIntegerType>
57class VarintBETestTemplate : public VarintBETestCommon {
58 protected:
59  VarintBETestTemplate() { }
60
61  virtual ~VarintBETestTemplate() { }
62
63  typedef SignedIntegerType SignedIntType;
64  typedef VarintBE<SignedIntegerType> VarintType;
65
66  void StartEncodingTest(SignedIntegerType v, int expected_length) {
67    verify_expected_length_ = expected_length;
68    EXPECT_EQ(expected_length, VarintType::Length(v));
69    EXPECT_EQ(expected_length, VarintType::Encode(v, &varint_buf_[0]));
70    VarintType::AppendToString(v, &s_);
71    EXPECT_EQ(static_cast<size_t>(expected_length), s_.length());
72  }
73
74  void TestEncodeInvalid(SignedIntegerType v) {
75    EXPECT_DEATH(VarintType::Length(v), "v >= 0");
76    EXPECT_DEATH(VarintType::Encode(v, &varint_buf_[0]), "v >= 0");
77    EXPECT_DEATH(VarintType::AppendToString(v, &s_), ">= 0");
78  }
79
80  // Need one function for each test type that will be applied to
81  // multiple classes
82  void TemplateTestDISABLED_EncodeNegative();
83  void TemplateTestEncodeZero();
84  void TemplateTestEncodeEightBits();
85  void TemplateTestEncodeCADAD1A();
86  void TemplateTestEncode32BitMaxInt();
87  void TemplateTestEncodeDoesNotOverwriteExistingString();
88  void TemplateTestParseNullPointer();
89  void TemplateTestEndPointerPrecedesBeginning();
90  void TemplateTestParseVarintTooLong();
91  void TemplateTestParseZero();
92  void TemplateTestParseCADA1();
93  void TemplateTestParseEmpty();
94  void TemplateTestParse123456789();
95  void TemplateTestDecode31Bits();
96  void TemplateTestEncodeDecodeRandom();
97  void TemplateTestContinuationBytesPastEndOfInput();
98};
99
100typedef VarintBETestTemplate<int32_t> VarintBEInt32Test;
101typedef VarintBETestTemplate<int64_t> VarintBEInt64Test;
102
103#ifdef GTEST_HAS_DEATH_TEST
104// These synonyms are needed for the tests that use ASSERT_DEATH
105typedef VarintBEInt32Test VarintBEInt32DeathTest;
106typedef VarintBEInt64Test VarintBEInt64DeathTest;
107#endif  // GTEST_HAS_DEATH_TEST
108
109const char VarintBETestCommon::parse_data_all_FFs[] =
110    { 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF };
111
112const char VarintBETestCommon::parse_data_CADA1[] =
113    { 0xCA, 0xDA, 0x01 };
114
115// A macro to allow defining tests once and having them run against
116// both VarintBE<int32_t> and VarintBE<int64_t>.
117//
118#define TEMPLATE_TEST_F(TEST_TYPE, TEST_NAME) \
119    TEST_F(VarintBEInt32##TEST_TYPE, TEST_NAME) { \
120      TemplateTest##TEST_NAME(); \
121    } \
122    TEST_F(VarintBEInt64##TEST_TYPE, TEST_NAME) { \
123      TemplateTest##TEST_NAME(); \
124    } \
125    template <class CacheType> \
126    void VarintBETestTemplate<CacheType>::TemplateTest##TEST_NAME()
127
128// Encoding tests: Length(), Encode(), AppendToString(), AppendToBuffer()
129
130#ifdef GTEST_HAS_DEATH_TEST
131// This test hangs for non-debug build (DeathTest threading problem)
132TEMPLATE_TEST_F(DeathTest, DISABLED_EncodeNegative) {
133  TestEncodeInvalid(-1);
134}
135#endif  // GTEST_HAS_DEATH_TEST
136
137TEMPLATE_TEST_F(Test, EncodeZero) {
138  StartEncodingTest(/* value */ 0x00, /* expected length */ 1);
139  ExpectEncodedByte(0x00);
140  EXPECT_EQ(verify_expected_length_, verify_encoded_byte_index_);
141}
142
143TEMPLATE_TEST_F(Test, EncodeEightBits) {
144  StartEncodingTest(/* value */ 0xFF, /* expected length */ 2);
145  ExpectEncodedByte(0x81);
146  ExpectEncodedByte(0x7F);
147  EXPECT_EQ(verify_expected_length_, verify_encoded_byte_index_);
148}
149
150TEMPLATE_TEST_F(Test, EncodeCADAD1A) {
151  StartEncodingTest(/* value */ 0x0CADAD1A, /* expected length */ 4);
152  ExpectEncodedByte(0xE5);
153  ExpectEncodedByte(0xB6);
154  ExpectEncodedByte(0xDA);
155  ExpectEncodedByte(0x1A);
156  EXPECT_EQ(verify_expected_length_, verify_encoded_byte_index_);
157}
158
159TEMPLATE_TEST_F(Test, Encode32BitMaxInt) {
160  StartEncodingTest(/* value */ 0x7FFFFFFF, /* expected length */ 5);
161  ExpectEncodedByte(0x87);
162  ExpectEncodedByte(0xFF);
163  ExpectEncodedByte(0xFF);
164  ExpectEncodedByte(0xFF);
165  ExpectEncodedByte(0x7F);
166  EXPECT_EQ(verify_expected_length_, verify_encoded_byte_index_);
167}
168
169#ifdef GTEST_HAS_DEATH_TEST
170// This test hangs for non-debug build (DeathTest threading problem)
171TEST_F(VarintBEInt32DeathTest, DISABLED_Encode32BitsTooBig) {
172  TestEncodeInvalid(0x80000000);
173}
174#endif  // GTEST_HAS_DEATH_TEST
175
176TEST_F(VarintBEInt64Test, Encode32Bits) {
177  StartEncodingTest(/* value */ 0x80000000, /* expected length */ 5);
178  ExpectEncodedByte(0x88);
179  ExpectEncodedByte(0x80);
180  ExpectEncodedByte(0x80);
181  ExpectEncodedByte(0x80);
182  ExpectEncodedByte(0x00);
183  EXPECT_EQ(verify_expected_length_, verify_encoded_byte_index_);
184}
185
186TEST_F(VarintBEInt64Test, Encode63Bits) {
187  StartEncodingTest(/* value */ 0x7FFFFFFFFFFFFFFFULL, /* expected length */ 9);
188  ExpectEncodedByte(0xFF);
189  ExpectEncodedByte(0xFF);
190  ExpectEncodedByte(0xFF);
191  ExpectEncodedByte(0xFF);
192  ExpectEncodedByte(0xFF);
193  ExpectEncodedByte(0xFF);
194  ExpectEncodedByte(0xFF);
195  ExpectEncodedByte(0xFF);
196  ExpectEncodedByte(0x7F);
197  EXPECT_EQ(verify_expected_length_, verify_encoded_byte_index_);
198}
199
200#ifdef GTEST_HAS_DEATH_TEST
201// This test hangs for non-debug build (DeathTest threading problem)
202TEST_F(VarintBEInt64DeathTest, DISABLED_Encode64BitsTooBig) {
203  TestEncodeInvalid(0x8000000000000000ULL);
204}
205#endif  // GTEST_HAS_DEATH_TEST
206
207TEMPLATE_TEST_F(Test, EncodeDoesNotOverwriteExistingString) {
208  s_.append("Test");
209  VarintType::AppendToString('1', &s_);
210  EXPECT_EQ(strlen("Test1"), s_.length());
211  EXPECT_EQ("Test1", s_);
212}
213
214// Decoding tests: Parse(), ParseFromBuffer()
215
216TEMPLATE_TEST_F(Test, ParseVarintTooLong) {
217  EXPECT_EQ(RESULT_ERROR,
218            VarintType::Parse(parse_data_ptr_ + VarintType::kMaxBytes,
219                              &parse_data_ptr_));
220}
221
222TEST_F(VarintBEInt32Test, ParseFourFFs) {
223  // For a 31-bit non-negative VarintBE, the sequence FF FF FF FF is invalid.
224  // Even though the largest allowable 31-bit value occupies 5 bytes as a
225  // Varint, it shouldn't have the highest bits set and so can't begin with FF.
226  EXPECT_EQ(RESULT_ERROR, VarintType::Parse(parse_data_ptr_ + 4,
227                                            &parse_data_ptr_));
228}
229
230TEST_F(VarintBEInt32Test, ParseThreeFFs) {
231  EXPECT_EQ(RESULT_END_OF_DATA, VarintType::Parse(parse_data_ptr_ + 3,
232                                                  &parse_data_ptr_));
233}
234
235TEST_F(VarintBEInt64Test, ParseEightFFs) {
236  // For a 63-bit non-negative VarintBE, a series of eight FFs is valid, because
237  // the largest allowable 63-bit value is expressed as eight FF bytes followed
238  // by a 7F byte.  This is in contrast to the 32-bit case (see ParseFourFFs,
239  // above.)
240  EXPECT_EQ(RESULT_END_OF_DATA, VarintType::Parse(parse_data_ptr_ + 8,
241                                                  &parse_data_ptr_));
242}
243
244TEMPLATE_TEST_F(Test, ParseZero) {
245  const char zero_data[] = { 0x00 };
246  parse_data_ptr_ = zero_data;
247  EXPECT_EQ(0x00, VarintType::Parse(parse_data_ptr_ + 1, &parse_data_ptr_));
248  EXPECT_EQ(zero_data + 1, parse_data_ptr_);
249}
250
251TEMPLATE_TEST_F(Test, ParseCADA1) {
252  parse_data_ptr_ = parse_data_CADA1;
253  EXPECT_EQ(0x12AD01,
254            VarintType::Parse(parse_data_CADA1 + sizeof(parse_data_CADA1),
255                              &parse_data_ptr_));
256  EXPECT_EQ(parse_data_CADA1 + 3, parse_data_ptr_);
257}
258
259TEMPLATE_TEST_F(Test, ParseNullPointer) {
260  parse_data_ptr_ = parse_data_CADA1;
261  EXPECT_EQ(RESULT_ERROR,
262            VarintType::Parse((const char*) NULL, &parse_data_ptr_));
263}
264
265TEMPLATE_TEST_F(Test, EndPointerPrecedesBeginning) {
266  // This is not an error.
267  parse_data_ptr_ = parse_data_CADA1;
268  EXPECT_EQ(RESULT_END_OF_DATA,
269            VarintType::Parse(parse_data_ptr_ - 1, &parse_data_ptr_));
270}
271
272TEMPLATE_TEST_F(Test, ParseEmpty) {
273  EXPECT_EQ(RESULT_END_OF_DATA,
274            VarintType::Parse(parse_data_ptr_, &parse_data_ptr_));
275}
276
277// This example is taken from the Varint description in RFC 3284, section 2.
278TEMPLATE_TEST_F(Test, Parse123456789) {
279  const char parse_data_123456789[] = { 0x80 + 58, 0x80 + 111, 0x80 + 26, 21 };
280  parse_data_ptr_ = parse_data_123456789;
281  EXPECT_EQ(123456789, VarintType::Parse(parse_data_123456789
282                                             + sizeof(parse_data_123456789),
283                                         &parse_data_ptr_));
284}
285
286TEMPLATE_TEST_F(Test, Decode31Bits) {
287  const char parse_data_31_bits[] = { 0x87, 0xFF, 0xFF, 0xFF, 0x7F };
288  parse_data_ptr_ = parse_data_31_bits;
289  EXPECT_EQ(0x7FFFFFFF,
290            VarintType::Parse(parse_data_31_bits + sizeof(parse_data_31_bits),
291                              &parse_data_ptr_));
292}
293
294TEST_F(VarintBEInt32Test, Decode32Bits) {
295  const char parse_data_32_bits[] = { 0x88, 0x80, 0x80, 0x80, 0x00 };
296  parse_data_ptr_ = parse_data_32_bits;
297  EXPECT_EQ(RESULT_ERROR,
298            VarintType::Parse(parse_data_32_bits + sizeof(parse_data_32_bits),
299                              &parse_data_ptr_));
300}
301
302TEST_F(VarintBEInt64Test, Decode32Bits) {
303  const char parse_data_32_bits[] = { 0x88, 0x80, 0x80, 0x80, 0x00 };
304  parse_data_ptr_ = parse_data_32_bits;
305  EXPECT_EQ(0x80000000,
306            VarintType::Parse(parse_data_32_bits + sizeof(parse_data_32_bits),
307                              &parse_data_ptr_));
308}
309
310TEMPLATE_TEST_F(Test, EncodeDecodeRandom) {
311  const int test_size = 1024;  // 1K random encode/decode operations
312  char encode_buffer[VarintType::kMaxBytes];
313  srand(1);
314  for (int i = 0; i < test_size; ++i) {
315    SignedIntType value = PortableRandomInRange(VarintType::kMaxVal);
316    int length = VarintType::Encode(value, encode_buffer);
317    EXPECT_EQ(length, VarintType::Length(value));
318    const char* parse_pointer = encode_buffer;
319    EXPECT_EQ(value, VarintType::Parse(encode_buffer + sizeof(encode_buffer),
320                                       &parse_pointer));
321    EXPECT_EQ(encode_buffer + length, parse_pointer);
322  }
323  for (int i = 0; i < test_size; ++i) {
324    s_.clear();
325    SignedIntType value = PortableRandomInRange(VarintType::kMaxVal);
326    VarintType::AppendToString(value, &s_);
327    const int varint_length = static_cast<int>(s_.length());
328    EXPECT_EQ(VarintType::Length(value), varint_length);
329    const char* parse_pointer = s_.c_str();
330    const char* const buffer_end_pointer = s_.c_str() + s_.length();
331    EXPECT_EQ(value, VarintType::Parse(buffer_end_pointer, &parse_pointer));
332    EXPECT_EQ(buffer_end_pointer, parse_pointer);
333  }
334}
335
336// If only 10 bytes of data are available, but there are 20 continuation
337// bytes, Parse() should not read to the end of the continuation bytes.  It is
338// legal (according to the RFC3284 spec) to use any number of continuation
339// bytes, but they should not cause us to read past the end of available input.
340TEMPLATE_TEST_F(Test, ContinuationBytesPastEndOfInput) {
341  const char parse_data_20_continuations[] =
342    { 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
343      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
344      0x00 };
345  parse_data_ptr_ = parse_data_20_continuations;
346  EXPECT_EQ(RESULT_END_OF_DATA,
347            VarintType::Parse(parse_data_20_continuations + 10,
348                              &parse_data_ptr_));
349}
350
351}  // anonymous namespace
352}  // namespace open_vcdiff
353