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 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 56 template <typename SignedIntegerType> 57 class 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 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) 132 TEMPLATE_TEST_F(DeathTest, DISABLED_EncodeNegative) { 133 TestEncodeInvalid(-1); 134 } 135 #endif // GTEST_HAS_DEATH_TEST 136 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 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 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 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) 171 TEST_F(VarintBEInt32DeathTest, DISABLED_Encode32BitsTooBig) { 172 TestEncodeInvalid(0x80000000); 173 } 174 #endif // GTEST_HAS_DEATH_TEST 175 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 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) 202 TEST_F(VarintBEInt64DeathTest, DISABLED_Encode64BitsTooBig) { 203 TestEncodeInvalid(0x8000000000000000ULL); 204 } 205 #endif // GTEST_HAS_DEATH_TEST 206 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 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 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 230 TEST_F(VarintBEInt32Test, ParseThreeFFs) { 231 EXPECT_EQ(RESULT_END_OF_DATA, VarintType::Parse(parse_data_ptr_ + 3, 232 &parse_data_ptr_)); 233 } 234 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 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 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 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 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 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. 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 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 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 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 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. 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
