• Home
  • History
  • Annotate
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
24 namespace open_vcdiff {
25 namespace {
26 
27 class VarintBETestCommon : public testing::Test {
28  protected:
29   typedef std::string string;
30 
VarintBETestCommon()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 
~VarintBETestCommon()38   virtual ~VarintBETestCommon() { }
39 
ExpectEncodedByte(char expected_byte)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 
56 template <typename SignedIntegerType>
57 class VarintBETestTemplate : public VarintBETestCommon {
58  protected:
VarintBETestTemplate()59   VarintBETestTemplate() { }
60 
~VarintBETestTemplate()61   virtual ~VarintBETestTemplate() { }
62 
63   typedef SignedIntegerType SignedIntType;
64   typedef VarintBE<SignedIntegerType> VarintType;
65 
StartEncodingTest(SignedIntegerType v,int expected_length)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 
TestEncodeInvalid(SignedIntegerType v)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 
100 typedef VarintBETestTemplate<int32_t> VarintBEInt32Test;
101 typedef VarintBETestTemplate<int64_t> VarintBEInt64Test;
102 
103 #ifdef GTEST_HAS_DEATH_TEST
104 // These synonyms are needed for the tests that use ASSERT_DEATH
105 typedef VarintBEInt32Test VarintBEInt32DeathTest;
106 typedef VarintBEInt64Test VarintBEInt64DeathTest;
107 #endif  // GTEST_HAS_DEATH_TEST
108 
109 const char VarintBETestCommon::parse_data_all_FFs[] =
110     { 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF };
111 
112 const 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)
TEMPLATE_TEST_F(DeathTest,DISABLED_EncodeNegative)132 TEMPLATE_TEST_F(DeathTest, DISABLED_EncodeNegative) {
133   TestEncodeInvalid(-1);
134 }
135 #endif  // GTEST_HAS_DEATH_TEST
136 
TEMPLATE_TEST_F(Test,EncodeZero)137 TEMPLATE_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 
TEMPLATE_TEST_F(Test,EncodeEightBits)143 TEMPLATE_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 
TEMPLATE_TEST_F(Test,EncodeCADAD1A)150 TEMPLATE_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 
TEMPLATE_TEST_F(Test,Encode32BitMaxInt)159 TEMPLATE_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)
TEST_F(VarintBEInt32DeathTest,DISABLED_Encode32BitsTooBig)171 TEST_F(VarintBEInt32DeathTest, DISABLED_Encode32BitsTooBig) {
172   TestEncodeInvalid(0x80000000);
173 }
174 #endif  // GTEST_HAS_DEATH_TEST
175 
TEST_F(VarintBEInt64Test,Encode32Bits)176 TEST_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 
TEST_F(VarintBEInt64Test,Encode63Bits)186 TEST_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)
TEST_F(VarintBEInt64DeathTest,DISABLED_Encode64BitsTooBig)202 TEST_F(VarintBEInt64DeathTest, DISABLED_Encode64BitsTooBig) {
203   TestEncodeInvalid(0x8000000000000000ULL);
204 }
205 #endif  // GTEST_HAS_DEATH_TEST
206 
TEMPLATE_TEST_F(Test,EncodeDoesNotOverwriteExistingString)207 TEMPLATE_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 
TEMPLATE_TEST_F(Test,ParseVarintTooLong)216 TEMPLATE_TEST_F(Test, ParseVarintTooLong) {
217   EXPECT_EQ(RESULT_ERROR,
218             VarintType::Parse(parse_data_ptr_ + VarintType::kMaxBytes,
219                               &parse_data_ptr_));
220 }
221 
TEST_F(VarintBEInt32Test,ParseFourFFs)222 TEST_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 
TEST_F(VarintBEInt32Test,ParseThreeFFs)230 TEST_F(VarintBEInt32Test, ParseThreeFFs) {
231   EXPECT_EQ(RESULT_END_OF_DATA, VarintType::Parse(parse_data_ptr_ + 3,
232                                                   &parse_data_ptr_));
233 }
234 
TEST_F(VarintBEInt64Test,ParseEightFFs)235 TEST_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 
TEMPLATE_TEST_F(Test,ParseZero)244 TEMPLATE_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 
TEMPLATE_TEST_F(Test,ParseCADA1)251 TEMPLATE_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 
TEMPLATE_TEST_F(Test,ParseNullPointer)259 TEMPLATE_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 
TEMPLATE_TEST_F(Test,EndPointerPrecedesBeginning)265 TEMPLATE_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 
TEMPLATE_TEST_F(Test,ParseEmpty)272 TEMPLATE_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.
TEMPLATE_TEST_F(Test,Parse123456789)278 TEMPLATE_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 
TEMPLATE_TEST_F(Test,Decode31Bits)286 TEMPLATE_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 
TEST_F(VarintBEInt32Test,Decode32Bits)294 TEST_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 
TEST_F(VarintBEInt64Test,Decode32Bits)302 TEST_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 
TEMPLATE_TEST_F(Test,EncodeDecodeRandom)310 TEMPLATE_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.
TEMPLATE_TEST_F(Test,ContinuationBytesPastEndOfInput)340 TEMPLATE_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