openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 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" |
openvcdiff | 28db807 | 2008-10-10 23:29:11 +0000 | [diff] [blame] | 18 | #include <limits.h> // INT_MAX, INT_MIN |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 19 | #include <stdint.h> // uint32_t |
openvcdiff | 28db807 | 2008-10-10 23:29:11 +0000 | [diff] [blame] | 20 | #include <stdlib.h> // rand, srand |
openvcdiff | d184578 | 2009-03-20 21:56:15 +0000 | [diff] [blame] | 21 | #include <iostream> |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 22 | #include <string> |
| 23 | #include <vector> |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 24 | #include "testing.h" |
| 25 | #include "varint_bigendian.h" |
| 26 | #include "vcdiff_defs.h" // RESULT_ERROR |
| 27 | |
| 28 | namespace open_vcdiff { |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 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: |
openvcdiff | 28db807 | 2008-10-10 23:29:11 +0000 | [diff] [blame] | 37 | typedef std::string string; |
openvcdiff | 28db807 | 2008-10-10 23:29:11 +0000 | [diff] [blame] | 38 | |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 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 |
openvcdiff | d184578 | 2009-03-20 21:56:15 +0000 | [diff] [blame] | 52 | void BM_Setup(int test_size); |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 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 | |
openvcdiff | d184578 | 2009-03-20 21:56:15 +0000 | [diff] [blame] | 550 | void VCDiffAddressCacheTest::BM_Setup(int test_size) { |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 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_ |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 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 |
openvcdiff | d184578 | 2009-03-20 21:56:15 +0000 | [diff] [blame] | 610 | BM_Setup(test_size); |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 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; |
openvcdiff | d184578 | 2009-03-20 21:56:15 +0000 | [diff] [blame] | 618 | std::cout << "Time to encode: " |
| 619 | << (encode_time_in_ms / num_iterations) << " ms" << std::endl; |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 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; |
openvcdiff | d184578 | 2009-03-20 21:56:15 +0000 | [diff] [blame] | 628 | std::cout << "Time to decode: " |
| 629 | << (decode_time_in_ms / num_iterations) << " ms" << std::endl; |
openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 630 | } |
| 631 | } |
| 632 | |
| 633 | } // unnamed namespace |
| 634 | } // namespace open_vcdiff |