1 // Copyright 2007 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 "addrcache.h" 18 #include <limits.h> // INT_MAX, INT_MIN 19 #include <stdint.h> // uint32_t 20 #include <stdlib.h> // rand, srand 21 #include <iostream> 22 #include <string> 23 #include <vector> 24 #include "testing.h" 25 #include "varint_bigendian.h" 26 #include "vcdiff_defs.h" // RESULT_ERROR 27 28 namespace open_vcdiff { 29 namespace { 30 31 // Provides an address_stream_ buffer and functions to manually encode 32 // values into the buffer, and to manually decode and verify test results 33 // from the buffer. 34 // 35 class VCDiffAddressCacheTest : public testing::Test { 36 public: 37 typedef std::string string; 38 39 VCDiffAddressCacheTest() : decode_position_(NULL), 40 decode_position_end_(NULL), 41 verify_encode_position_(NULL), 42 last_encode_size_(0), 43 last_decode_position_(NULL) { } 44 45 virtual ~VCDiffAddressCacheTest() { } 46 47 virtual void SetUp() { 48 EXPECT_TRUE(cache_.Init()); 49 } 50 51 // Benchmarks for timing encode/decode operations 52 void BM_Setup(int test_size); 53 void BM_CacheEncode(int iterations, int test_size); 54 void BM_CacheDecode(int iterations, int test_size); 55 56 protected: 57 virtual void TestBody() { } // to allow instantiation of this class 58 59 void BeginDecode() { 60 decode_position_ = address_stream_.data(); 61 EXPECT_TRUE(decode_position_ != NULL); 62 last_decode_position_ = decode_position_; 63 decode_position_end_ = decode_position_ + address_stream_.size(); 64 } 65 66 void ExpectEncodedSizeInBytes(int n) { 67 EXPECT_EQ(last_encode_size_ + n, address_stream_.size()); 68 last_encode_size_ = address_stream_.size(); 69 } 70 71 void ExpectDecodedSizeInBytes(int n) { 72 EXPECT_EQ(last_decode_position_ + n, decode_position_); 73 last_decode_position_ = decode_position_; 74 } 75 76 void ManualEncodeVarint(VCDAddress value) { 77 VarintBE<VCDAddress>::AppendToString(value, &address_stream_); 78 } 79 80 void ManualEncodeByte(unsigned char byte) { 81 address_stream_.push_back(byte); 82 } 83 84 void ExpectEncodedVarint(VCDAddress expected_value, int expected_size) { 85 if (!verify_encode_position_) { 86 verify_encode_position_ = address_stream_.data(); 87 } 88 EXPECT_EQ(expected_size, VarintBE<VCDAddress>::Length(expected_value)); 89 VCDAddress output_val = VarintBE<VCDAddress>::Parse( 90 address_stream_.data() + address_stream_.size(), 91 &verify_encode_position_); 92 EXPECT_EQ(expected_value, output_val); 93 } 94 95 void ExpectEncodedByte(unsigned char expected_value) { 96 if (!verify_encode_position_) { 97 verify_encode_position_ = address_stream_.data(); 98 } 99 EXPECT_EQ(expected_value, *verify_encode_position_); 100 ++verify_encode_position_; 101 } 102 103 void TestEncode(VCDAddress address, 104 VCDAddress here_address, 105 unsigned char mode, 106 int size) { 107 VCDAddress encoded_addr = 0; 108 EXPECT_EQ(mode, cache_.EncodeAddress(address, here_address, &encoded_addr)); 109 if (cache_.WriteAddressAsVarintForMode(mode)) { 110 ManualEncodeVarint(encoded_addr); 111 } else { 112 EXPECT_GT(256, encoded_addr); 113 ManualEncodeByte(static_cast<unsigned char>(encoded_addr)); 114 } 115 ExpectEncodedSizeInBytes(size); 116 } 117 118 VCDiffAddressCache cache_; 119 string address_stream_; 120 const char* decode_position_; 121 const char* decode_position_end_; 122 string large_address_stream_; 123 std::vector<unsigned char> mode_stream_; 124 std::vector<VCDAddress> verify_stream_; 125 126 private: 127 const char* verify_encode_position_; 128 string::size_type last_encode_size_; 129 const char* last_decode_position_; 130 }; 131 132 #ifdef GTEST_HAS_DEATH_TEST 133 // This synonym is needed for the tests that use ASSERT_DEATH 134 typedef VCDiffAddressCacheTest VCDiffAddressCacheDeathTest; 135 #endif // GTEST_HAS_DEATH_TEST 136 137 // Having either or both cache size == 0 is acceptable 138 TEST_F(VCDiffAddressCacheTest, ZeroCacheSizes) { 139 VCDiffAddressCache zero_cache(0, 0); 140 EXPECT_TRUE(zero_cache.Init()); 141 } 142 143 TEST_F(VCDiffAddressCacheTest, NegativeCacheSizes) { 144 VCDiffAddressCache negative_cache(-1, -1); // The constructor must not fail 145 EXPECT_FALSE(negative_cache.Init()); 146 } 147 148 TEST_F(VCDiffAddressCacheTest, OnlySameCacheSizeIsNegative) { 149 VCDiffAddressCache negative_cache(0, -1); // The constructor must not fail 150 EXPECT_FALSE(negative_cache.Init()); 151 } 152 153 TEST_F(VCDiffAddressCacheTest, ExtremePositiveCacheSizes) { 154 // The constructor must not fail 155 VCDiffAddressCache int_max_cache(INT_MAX, INT_MAX); 156 EXPECT_FALSE(int_max_cache.Init()); 157 } 158 159 TEST_F(VCDiffAddressCacheTest, ExtremeNegativeCacheSizes) { 160 // The constructor must not fail 161 VCDiffAddressCache int_min_cache(INT_MIN, INT_MIN); 162 EXPECT_FALSE(int_min_cache.Init()); 163 } 164 165 // VCD_MAX_MODES is the maximum number of modes, including SAME and HERE modes. 166 // So neither the SAME cache nor the HERE cache can be larger than 167 // (VCD_MAX_MODES - 2). 168 TEST_F(VCDiffAddressCacheTest, NearCacheSizeIsTooBig) { 169 VCDiffAddressCache negative_cache(VCD_MAX_MODES - 1, 0); 170 EXPECT_FALSE(negative_cache.Init()); 171 } 172 173 TEST_F(VCDiffAddressCacheTest, SameCacheSizeIsTooBig) { 174 VCDiffAddressCache negative_cache(0, VCD_MAX_MODES - 1); 175 EXPECT_FALSE(negative_cache.Init()); 176 } 177 178 TEST_F(VCDiffAddressCacheTest, CombinedSizesAreTooBig) { 179 VCDiffAddressCache negative_cache((VCD_MAX_MODES / 2), 180 (VCD_MAX_MODES / 2) - 1); 181 EXPECT_FALSE(negative_cache.Init()); 182 } 183 184 TEST_F(VCDiffAddressCacheTest, MaxLegalNearCacheSize) { 185 VCDiffAddressCache negative_cache(VCD_MAX_MODES - 2, 0); 186 EXPECT_TRUE(negative_cache.Init()); 187 } 188 189 TEST_F(VCDiffAddressCacheTest, MaxLegalSameCacheSize) { 190 VCDiffAddressCache negative_cache(0, VCD_MAX_MODES - 2); 191 EXPECT_TRUE(negative_cache.Init()); 192 } 193 194 TEST_F(VCDiffAddressCacheTest, MaxLegalCombinedSizes) { 195 VCDiffAddressCache negative_cache((VCD_MAX_MODES / 2) - 1, 196 (VCD_MAX_MODES / 2) - 1); 197 EXPECT_TRUE(negative_cache.Init()); 198 } 199 200 TEST_F(VCDiffAddressCacheTest, DestroyWithoutInitialization) { 201 VCDiffAddressCache no_init_cache(4, 3); 202 // Should be destroyed without crashing 203 } 204 205 TEST_F(VCDiffAddressCacheTest, DestroyDefaultWithoutInitialization) { 206 VCDiffAddressCache no_init_cache; 207 // Should be destroyed without crashing 208 } 209 210 TEST_F(VCDiffAddressCacheTest, CacheContentsInitiallyZero) { 211 VCDAddress test_address = 0; 212 // Check that caches are initially set to zero 213 for (test_address = 0; test_address < 4; ++test_address) { 214 EXPECT_EQ(0, cache_.NearAddress(test_address)); 215 } 216 for (test_address = 0; test_address < 256 * 3; ++test_address) { 217 EXPECT_EQ(0, cache_.SameAddress(test_address)); 218 } 219 } 220 221 // Inserts values 1, 2, ... , 10 into the cache and tests its entire 222 // contents for consistency. 223 // 224 TEST_F(VCDiffAddressCacheTest, InsertFirstTen) { 225 VCDAddress test_address = 0; 226 for (test_address = 1; test_address <= 10; ++test_address) { 227 cache_.UpdateCache(test_address); 228 } 229 EXPECT_EQ(9, cache_.NearAddress(0)); // slot 0: 1 => 5 => 9 230 EXPECT_EQ(10, cache_.NearAddress(1)); // slot 1: 2 => 6 => 10 231 EXPECT_EQ(7, cache_.NearAddress(2)); // slot 2: 3 => 7 232 EXPECT_EQ(8, cache_.NearAddress(3)); // slot 3: 4 => 8 233 EXPECT_EQ(0, cache_.SameAddress(0)); 234 for (test_address = 1; test_address <= 10; ++test_address) { 235 EXPECT_EQ(test_address, cache_.SameAddress(test_address)); 236 } 237 for (test_address = 11; test_address < 256 * 3; ++test_address) { 238 EXPECT_EQ(0, cache_.SameAddress(test_address)); 239 } 240 } 241 242 TEST_F(VCDiffAddressCacheTest, InsertIntMax) { 243 cache_.UpdateCache(INT_MAX); 244 EXPECT_EQ(INT_MAX, cache_.NearAddress(0)); 245 EXPECT_EQ(INT_MAX, cache_.SameAddress(INT_MAX % (256 * 3))); 246 EXPECT_EQ(0, cache_.SameAddress((INT_MAX - 256) % (256 * 3))); 247 EXPECT_EQ(0, cache_.SameAddress((INT_MAX - 512) % (256 * 3))); 248 } 249 250 // Exercises all four addressing mode types by encoding five values 251 // with EncodeAddress. 252 // Checks to see that the proper mode was selected in each case, 253 // and that the encoding is correct. 254 // 255 TEST_F(VCDiffAddressCacheTest, EncodeAddressModes) { 256 TestEncode(0x0000FFFF, 0x10000000, VCD_SELF_MODE, 3); 257 TestEncode(0x10000000, 0x10000010, VCD_HERE_MODE, 1); 258 TestEncode(0x10000004, 0x10000020, cache_.FirstNearMode() + 0x01, 1); 259 TestEncode(0x0FFFFFFE, 0x10000030, VCD_HERE_MODE, 1); 260 TestEncode(0x10000004, 0x10000040, cache_.FirstSameMode() + 0x01, 1); 261 ExpectEncodedVarint(0xFFFF, 3); // SELF mode: addr 0x0000FFFF 262 ExpectEncodedVarint(0x10, 1); // HERE mode: here - 0x10 = 0x10000000 263 ExpectEncodedVarint(0x04, 1); // NEAR cache #1: 264 // last addr + 0x4 = 0x10000004 265 ExpectEncodedVarint(0x32, 1); // HERE mode: here - 0x32 = 0x0FFFFFFE 266 ExpectEncodedByte(0x04); // SAME cache #1: 0x10000004 hits 267 } 268 269 // Exercises all four addressing mode types by manually encoding six values 270 // and calling DecodeAddress on each one. 271 // 272 TEST_F(VCDiffAddressCacheTest, DecodeAddressModes) { 273 ManualEncodeVarint(0xCAFE); 274 ManualEncodeVarint(0xCAFE); 275 ManualEncodeVarint(0x1000); 276 ManualEncodeByte(0xFE); // SAME mode uses a byte, not a Varint 277 ManualEncodeVarint(0xFE); 278 ManualEncodeVarint(0x1000); 279 BeginDecode(); 280 EXPECT_EQ(0xCAFE, 281 cache_.DecodeAddress(0x10000, 282 VCD_SELF_MODE, 283 &decode_position_, 284 decode_position_end_)); 285 ExpectDecodedSizeInBytes(VarintBE<VCDAddress>::Length(0xCAFE)); 286 EXPECT_EQ(0x20000 - 0xCAFE, 287 cache_.DecodeAddress(0x20000, 288 VCD_HERE_MODE, 289 &decode_position_, 290 decode_position_end_)); 291 ExpectDecodedSizeInBytes(VarintBE<VCDAddress>::Length(0xCAFE)); 292 EXPECT_EQ(0xDAFE, 293 cache_.DecodeAddress(0x30000, 294 cache_.FirstNearMode(), 295 &decode_position_, 296 decode_position_end_)); 297 ExpectDecodedSizeInBytes(VarintBE<VCDAddress>::Length(0x1000)); 298 EXPECT_EQ(0xCAFE, 299 cache_.DecodeAddress(0x40000, 300 cache_.FirstSameMode() + (0xCA % 3), 301 &decode_position_, 302 decode_position_end_)); 303 ExpectDecodedSizeInBytes(sizeof(unsigned char)); // a byte, not a Varint 304 EXPECT_EQ(0xFE, 305 cache_.DecodeAddress(0x50000, 306 VCD_SELF_MODE, 307 &decode_position_, 308 decode_position_end_)); 309 ExpectDecodedSizeInBytes(VarintBE<VCDAddress>::Length(0xFE)); 310 // NEAR mode #0 has been overwritten by fifth computed addr (wrap around) 311 EXPECT_EQ(0x10FE, 312 cache_.DecodeAddress(0x60000, 313 cache_.FirstNearMode(), 314 &decode_position_, 315 decode_position_end_)); 316 ExpectDecodedSizeInBytes(VarintBE<VCDAddress>::Length(0x1000)); 317 } 318 319 // Test with both cache sizes == 0. The encoder should not choose 320 // a SAME or NEAR mode under these conditions. 321 TEST_F(VCDiffAddressCacheTest, EncodeAddressZeroCacheSizes) { 322 VCDAddress encoded_addr = 0; 323 VCDiffAddressCache zero_cache(0, 0); 324 EXPECT_TRUE(zero_cache.Init()); 325 EXPECT_EQ(VCD_SELF_MODE, 326 zero_cache.EncodeAddress(0x0000FFFF, 0x10000000, &encoded_addr)); 327 EXPECT_EQ(0xFFFF, encoded_addr); 328 EXPECT_EQ(VCD_HERE_MODE, 329 zero_cache.EncodeAddress(0x10000000, 0x10000010, &encoded_addr)); 330 EXPECT_EQ(0x10, encoded_addr); 331 EXPECT_EQ(VCD_HERE_MODE, 332 zero_cache.EncodeAddress(0x10000004, 0x10000020, &encoded_addr)); 333 EXPECT_EQ(0x1C, encoded_addr); 334 EXPECT_EQ(VCD_HERE_MODE, 335 zero_cache.EncodeAddress(0x0FFFFFFE, 0x10000030, &encoded_addr)); 336 EXPECT_EQ(0x32, encoded_addr); 337 EXPECT_EQ(VCD_HERE_MODE, 338 zero_cache.EncodeAddress(0x10000004, 0x10000040, &encoded_addr)); 339 EXPECT_EQ(0x3C, encoded_addr); 340 } 341 342 TEST_F(VCDiffAddressCacheTest, DecodeAddressZeroCacheSizes) { 343 VCDiffAddressCache zero_cache(0, 0); 344 EXPECT_TRUE(zero_cache.Init()); 345 ManualEncodeVarint(0xCAFE); 346 ManualEncodeVarint(0xCAFE); 347 ManualEncodeVarint(0xDAFE); 348 BeginDecode(); 349 EXPECT_EQ(0xCAFE, zero_cache.DecodeAddress(0x10000, 350 VCD_SELF_MODE, 351 &decode_position_, 352 decode_position_end_)); 353 ExpectDecodedSizeInBytes(VarintBE<VCDAddress>::Length(0xCAFE)); 354 EXPECT_EQ(0x20000 - 0xCAFE, zero_cache.DecodeAddress(0x20000, 355 VCD_HERE_MODE, 356 &decode_position_, 357 decode_position_end_)); 358 ExpectDecodedSizeInBytes(VarintBE<VCDAddress>::Length(0xCAFE)); 359 EXPECT_EQ(0xDAFE, zero_cache.DecodeAddress(0x30000, 360 VCD_SELF_MODE, 361 &decode_position_, 362 decode_position_end_)); 363 ExpectDecodedSizeInBytes(VarintBE<VCDAddress>::Length(0xDAFE)); 364 } 365 366 #ifdef GTEST_HAS_DEATH_TEST 367 TEST_F(VCDiffAddressCacheDeathTest, EncodeNegativeAddress) { 368 VCDAddress dummy_encoded_address = 0; 369 EXPECT_DEBUG_DEATH(cache_.EncodeAddress(-1, -1, &dummy_encoded_address), 370 "negative"); 371 } 372 373 TEST_F(VCDiffAddressCacheDeathTest, EncodeAddressPastHereAddress) { 374 VCDAddress dummy_encoded_address = 0; 375 EXPECT_DEBUG_DEATH(cache_.EncodeAddress(0x100, 0x100, &dummy_encoded_address), 376 "address.*<.*here_address"); 377 EXPECT_DEBUG_DEATH(cache_.EncodeAddress(0x200, 0x100, &dummy_encoded_address), 378 "address.*<.*here_address"); 379 } 380 381 TEST_F(VCDiffAddressCacheDeathTest, DecodeInvalidMode) { 382 ManualEncodeVarint(0xCAFE); 383 BeginDecode(); 384 EXPECT_DEBUG_DEATH(EXPECT_EQ(RESULT_ERROR, 385 cache_.DecodeAddress(0x10000000, 386 cache_.LastMode() + 1, 387 &decode_position_, 388 decode_position_end_)), 389 "mode"); 390 EXPECT_DEBUG_DEATH(EXPECT_EQ(RESULT_ERROR, 391 cache_.DecodeAddress(0x10000000, 392 0xFF, 393 &decode_position_, 394 decode_position_end_)), 395 "mode"); 396 ExpectDecodedSizeInBytes(0); // Should not modify decode_position_ 397 } 398 399 TEST_F(VCDiffAddressCacheDeathTest, DecodeZeroOrNegativeHereAddress) { 400 ManualEncodeVarint(0xCAFE); 401 ManualEncodeVarint(0xCAFE); 402 BeginDecode(); 403 // Using a Debug build, the check will fail; using a Release build, 404 // the check will not occur, and the SELF mode does not depend on 405 // the value of here_address, so DecodeAddress() will succeed. 406 EXPECT_DEBUG_DEATH(cache_.DecodeAddress(-1, 407 VCD_SELF_MODE, 408 &decode_position_, 409 decode_position_end_), 410 "negative"); 411 // A zero value for here_address should not kill the decoder, 412 // but instead should return an error value. A delta file may contain 413 // a window that has no source segment and that (erroneously) 414 // uses a COPY instruction as its first instruction. This should 415 // cause an error to be reported, not a debug check failure. 416 EXPECT_EQ(RESULT_ERROR, cache_.DecodeAddress(0, 417 VCD_SELF_MODE, 418 &decode_position_, 419 decode_position_end_)); 420 } 421 #endif // GTEST_HAS_DEATH_TEST 422 423 TEST_F(VCDiffAddressCacheTest, DecodeAddressPastHereAddress) { 424 ManualEncodeVarint(0xCAFE); 425 BeginDecode(); 426 EXPECT_EQ(RESULT_ERROR, cache_.DecodeAddress(0x1000, 427 VCD_SELF_MODE, 428 &decode_position_, 429 decode_position_end_)); 430 ExpectDecodedSizeInBytes(0); // Should not modify decode_position_ 431 } 432 433 TEST_F(VCDiffAddressCacheTest, HereModeAddressTooLarge) { 434 ManualEncodeVarint(0x10001); // here_address + 1 435 BeginDecode(); 436 EXPECT_EQ(RESULT_ERROR, cache_.DecodeAddress(0x10000, 437 VCD_HERE_MODE, 438 &decode_position_, 439 decode_position_end_)); 440 ExpectDecodedSizeInBytes(0); // Should not modify decode_position_ 441 } 442 443 TEST_F(VCDiffAddressCacheTest, NearModeAddressOverflow) { 444 ManualEncodeVarint(0xCAFE); 445 ManualEncodeVarint(0x7FFFFFFF); 446 BeginDecode(); 447 EXPECT_EQ(0xCAFE, cache_.DecodeAddress(0x10000, 448 VCD_SELF_MODE, 449 &decode_position_, 450 decode_position_end_)); 451 ExpectDecodedSizeInBytes(VarintBE<VCDAddress>::Length(0xCAFE)); 452 // Now decode a NEAR mode address of base address 0xCAFE 453 // (the first decoded address) + offset 0x7FFFFFFF. This will cause 454 // an integer overflow and should signal an error. 455 EXPECT_EQ(RESULT_ERROR, cache_.DecodeAddress(0x10000000, 456 cache_.FirstNearMode(), 457 &decode_position_, 458 decode_position_end_)); 459 ExpectDecodedSizeInBytes(0); // Should not modify decode_position_ 460 } 461 462 // A Varint should contain at most 9 bytes that have their continuation bit 463 // (the uppermost, or 7 bit) set. A longer string of bytes that all have 464 // bit 7 set is not a valid Varint. Try to parse such a string as a Varint 465 // and confirm that it does not run off the end of the input buffer and 466 // it returns an error value (RESULT_ERROR). 467 // 468 TEST_F(VCDiffAddressCacheTest, DecodeInvalidVarint) { 469 address_stream_.clear(); 470 // Write 512 0xFE bytes 471 address_stream_.append(512, static_cast<char>(0xFE)); 472 BeginDecode(); 473 EXPECT_EQ(RESULT_ERROR, cache_.DecodeAddress(0x10000000, 474 VCD_SELF_MODE, 475 &decode_position_, 476 decode_position_end_)); 477 ExpectDecodedSizeInBytes(0); // Should not modify decode_position_ 478 } 479 480 // If only part of a Varint appears in the data to be decoded, 481 // then DecodeAddress should return RESULT_END_OF_DATA, 482 // which means that the Varint *may* be valid if there is more 483 // data expected to be returned. 484 // 485 TEST_F(VCDiffAddressCacheTest, DecodePartialVarint) { 486 address_stream_.clear(); 487 ManualEncodeByte(0xFE); 488 ManualEncodeByte(0xFE); 489 ManualEncodeByte(0xFE); 490 BeginDecode(); 491 EXPECT_EQ(RESULT_END_OF_DATA, 492 cache_.DecodeAddress(0x10000000, 493 VCD_SELF_MODE, 494 &decode_position_, 495 decode_position_end_)); 496 ExpectDecodedSizeInBytes(0); // Should not modify decode_position_ 497 // Now add the missing last byte (supposedly read from a stream of data) 498 // and verify that the Varint is now valid. 499 ManualEncodeByte(0x01); // End the Varint with an additional byte 500 BeginDecode(); // Reset read position to start of data 501 EXPECT_EQ(0xFDFBF01, 502 cache_.DecodeAddress(0x10000000, 503 VCD_SELF_MODE, 504 &decode_position_, 505 decode_position_end_)); 506 ExpectDecodedSizeInBytes(4); // ManualEncodeByte was called for 4 byte values 507 } 508 509 #ifdef GTEST_HAS_DEATH_TEST 510 TEST_F(VCDiffAddressCacheDeathTest, DecodeBadMode) { 511 ManualEncodeVarint(0xCAFE); 512 BeginDecode(); 513 EXPECT_DEBUG_DEATH(EXPECT_EQ(RESULT_ERROR, 514 cache_.DecodeAddress(0x10000, 515 cache_.LastMode() + 1, 516 &decode_position_, 517 decode_position_end_)), 518 "maximum"); 519 ExpectDecodedSizeInBytes(0); 520 } 521 #endif // GTEST_HAS_DEATH_TEST 522 523 TEST_F(VCDiffAddressCacheTest, DecodeInvalidHereAddress) { 524 ManualEncodeVarint(0x10001); // offset larger than here_address 525 BeginDecode(); 526 EXPECT_EQ(RESULT_ERROR, cache_.DecodeAddress(0x10000, 527 VCD_HERE_MODE, 528 &decode_position_, 529 decode_position_end_)); 530 ExpectDecodedSizeInBytes(0); 531 } 532 533 TEST_F(VCDiffAddressCacheTest, DecodeInvalidNearAddress) { 534 ManualEncodeVarint(0xCAFE); 535 ManualEncodeVarint(INT_MAX); // offset will cause integer overflow 536 BeginDecode(); 537 EXPECT_EQ(0xCAFE, 538 cache_.DecodeAddress(0x10000, 539 VCD_SELF_MODE, 540 &decode_position_, 541 decode_position_end_)); 542 ExpectDecodedSizeInBytes(VarintBE<VCDAddress>::Length(0xCAFE)); 543 EXPECT_EQ(RESULT_ERROR, cache_.DecodeAddress(0x10000, 544 cache_.FirstNearMode(), 545 &decode_position_, 546 decode_position_end_)); 547 ExpectDecodedSizeInBytes(0); 548 } 549 550 void VCDiffAddressCacheTest::BM_Setup(int test_size) { 551 mode_stream_.resize(test_size); 552 verify_stream_.resize(test_size); 553 VCDAddress here_address = 1; 554 srand(1); 555 for (int i = 0; i < test_size; ++i) { 556 verify_stream_[i] = PortableRandomInRange(here_address - 1); 557 here_address += 4; 558 } 559 BM_CacheEncode(1, test_size); // populate large_address_stream_, mode_stream_ 560 } 561 562 void VCDiffAddressCacheTest::BM_CacheEncode(int iterations, int test_size) { 563 VCDAddress here_address = 1; 564 VCDAddress encoded_addr = 0; 565 for (int test_iteration = 0; test_iteration < iterations; ++test_iteration) { 566 cache_.Init(); 567 large_address_stream_.clear(); 568 here_address = 1; 569 for (int i = 0; i < test_size; ++i) { 570 const unsigned char mode = cache_.EncodeAddress(verify_stream_[i], 571 here_address, 572 &encoded_addr); 573 if (cache_.WriteAddressAsVarintForMode(mode)) { 574 VarintBE<VCDAddress>::AppendToString(encoded_addr, 575 &large_address_stream_); 576 } else { 577 EXPECT_GT(256, encoded_addr); 578 large_address_stream_.push_back( 579 static_cast<unsigned char>(encoded_addr)); 580 } 581 mode_stream_[i] = mode; 582 here_address += 4; 583 } 584 } 585 } 586 587 void VCDiffAddressCacheTest::BM_CacheDecode(int iterations, int test_size) { 588 VCDAddress here_address = 1; 589 for (int test_iteration = 0; test_iteration < iterations; ++test_iteration) { 590 cache_.Init(); 591 const char* large_decode_pointer = large_address_stream_.data(); 592 const char* const end_of_encoded_data = 593 large_decode_pointer + large_address_stream_.size(); 594 here_address = 1; 595 for (int i = 0; i < test_size; ++i) { 596 EXPECT_EQ(verify_stream_[i], 597 cache_.DecodeAddress(here_address, 598 mode_stream_[i], 599 &large_decode_pointer, 600 end_of_encoded_data)); 601 here_address += 4; 602 } 603 EXPECT_EQ(end_of_encoded_data, large_decode_pointer); 604 } 605 } 606 607 TEST_F(VCDiffAddressCacheTest, PerformanceTest) { 608 const int test_size = 20 * 1024; // 20K random encode/decode operations 609 const int num_iterations = 40; // run test 40 times and take average 610 BM_Setup(test_size); 611 { 612 CycleTimer encode_timer; 613 encode_timer.Start(); 614 BM_CacheEncode(num_iterations, test_size); 615 encode_timer.Stop(); 616 double encode_time_in_ms = 617 static_cast<double>(encode_timer.GetInUsec()) / 1000; 618 std::cout << "Time to encode: " 619 << (encode_time_in_ms / num_iterations) << " ms" << std::endl; 620 } 621 { 622 CycleTimer decode_timer; 623 decode_timer.Start(); 624 BM_CacheDecode(num_iterations, test_size); 625 decode_timer.Stop(); 626 double decode_time_in_ms = 627 static_cast<double>(decode_timer.GetInUsec()) / 1000; 628 std::cout << "Time to decode: " 629 << (decode_time_in_ms / num_iterations) << " ms" << std::endl; 630 } 631 } 632 633 } // unnamed namespace 634 } // namespace open_vcdiff 635
