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