openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 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" |
openvcdiff | 28db807 | 2008-10-10 23:29:11 +0000 | [diff] [blame] | 18 | #include <stdlib.h> // rand, srand |
| 19 | #include <string.h> // strlen |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 20 | #include <string> |
| 21 | #include <vector> |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 22 | #include "testing.h" |
| 23 | |
| 24 | namespace open_vcdiff { |
| 25 | namespace { |
| 26 | |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 27 | class VarintBETestCommon : public testing::Test { |
| 28 | protected: |
openvcdiff | 28db807 | 2008-10-10 23:29:11 +0000 | [diff] [blame] | 29 | typedef std::string string; |
openvcdiff | 28db807 | 2008-10-10 23:29:11 +0000 | [diff] [blame] | 30 | |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 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(); |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 91 | void TemplateTestParseZero(); |
| 92 | void TemplateTestParseCADA1(); |
| 93 | void TemplateTestParseEmpty(); |
| 94 | void TemplateTestParse123456789(); |
| 95 | void TemplateTestDecode31Bits(); |
| 96 | void TemplateTestEncodeDecodeRandom(); |
openvcdiff@gmail.com | f1dd933 | 2009-10-09 22:40:32 +0000 | [diff] [blame] | 97 | void TemplateTestContinuationBytesPastEndOfInput(); |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 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 | |
openvcdiff@gmail.com | f1dd933 | 2009-10-09 22:40:32 +0000 | [diff] [blame] | 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_)); |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 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 | |
openvcdiff@gmail.com | f1dd933 | 2009-10-09 22:40:32 +0000 | [diff] [blame] | 259 | TEMPLATE_TEST_F(Test, ParseNullPointer) { |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 260 | parse_data_ptr_ = parse_data_CADA1; |
openvcdiff@gmail.com | f1dd933 | 2009-10-09 22:40:32 +0000 | [diff] [blame] | 261 | EXPECT_EQ(RESULT_ERROR, |
| 262 | VarintType::Parse((const char*) NULL, &parse_data_ptr_)); |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 263 | } |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 264 | |
| 265 | TEMPLATE_TEST_F(Test, EndPointerPrecedesBeginning) { |
| 266 | // This is not an error. |
| 267 | parse_data_ptr_ = parse_data_CADA1; |
openvcdiff@gmail.com | f1dd933 | 2009-10-09 22:40:32 +0000 | [diff] [blame] | 268 | EXPECT_EQ(RESULT_END_OF_DATA, |
| 269 | VarintType::Parse(parse_data_ptr_ - 1, &parse_data_ptr_)); |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 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 | |
openvcdiff@gmail.com | f1dd933 | 2009-10-09 22:40:32 +0000 | [diff] [blame] | 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 | |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 351 | } // anonymous namespace |
| 352 | } // namespace open_vcdiff |