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
VCDiffAddressCacheTest()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
~VCDiffAddressCacheTest()45 virtual ~VCDiffAddressCacheTest() { }
46
SetUp()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:
TestBody()57 virtual void TestBody() { } // to allow instantiation of this class
58
BeginDecode()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
ExpectEncodedSizeInBytes(int n)66 void ExpectEncodedSizeInBytes(int n) {
67 EXPECT_EQ(last_encode_size_ + n, address_stream_.size());
68 last_encode_size_ = address_stream_.size();
69 }
70
ExpectDecodedSizeInBytes(int n)71 void ExpectDecodedSizeInBytes(int n) {
72 EXPECT_EQ(last_decode_position_ + n, decode_position_);
73 last_decode_position_ = decode_position_;
74 }
75
ManualEncodeVarint(VCDAddress value)76 void ManualEncodeVarint(VCDAddress value) {
77 VarintBE<VCDAddress>::AppendToString(value, &address_stream_);
78 }
79
ManualEncodeByte(unsigned char byte)80 void ManualEncodeByte(unsigned char byte) {
81 address_stream_.push_back(byte);
82 }
83
ExpectEncodedVarint(VCDAddress expected_value,int expected_size)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
ExpectEncodedByte(unsigned char expected_value)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
TestEncode(VCDAddress address,VCDAddress here_address,unsigned char mode,int size)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
TEST_F(VCDiffAddressCacheTest,ZeroCacheSizes)138 TEST_F(VCDiffAddressCacheTest, ZeroCacheSizes) {
139 VCDiffAddressCache zero_cache(0, 0);
140 EXPECT_TRUE(zero_cache.Init());
141 }
142
TEST_F(VCDiffAddressCacheTest,NegativeCacheSizes)143 TEST_F(VCDiffAddressCacheTest, NegativeCacheSizes) {
144 VCDiffAddressCache negative_cache(-1, -1); // The constructor must not fail
145 EXPECT_FALSE(negative_cache.Init());
146 }
147
TEST_F(VCDiffAddressCacheTest,OnlySameCacheSizeIsNegative)148 TEST_F(VCDiffAddressCacheTest, OnlySameCacheSizeIsNegative) {
149 VCDiffAddressCache negative_cache(0, -1); // The constructor must not fail
150 EXPECT_FALSE(negative_cache.Init());
151 }
152
TEST_F(VCDiffAddressCacheTest,ExtremePositiveCacheSizes)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
TEST_F(VCDiffAddressCacheTest,ExtremeNegativeCacheSizes)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).
TEST_F(VCDiffAddressCacheTest,NearCacheSizeIsTooBig)168 TEST_F(VCDiffAddressCacheTest, NearCacheSizeIsTooBig) {
169 VCDiffAddressCache negative_cache(VCD_MAX_MODES - 1, 0);
170 EXPECT_FALSE(negative_cache.Init());
171 }
172
TEST_F(VCDiffAddressCacheTest,SameCacheSizeIsTooBig)173 TEST_F(VCDiffAddressCacheTest, SameCacheSizeIsTooBig) {
174 VCDiffAddressCache negative_cache(0, VCD_MAX_MODES - 1);
175 EXPECT_FALSE(negative_cache.Init());
176 }
177
TEST_F(VCDiffAddressCacheTest,CombinedSizesAreTooBig)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
TEST_F(VCDiffAddressCacheTest,MaxLegalNearCacheSize)184 TEST_F(VCDiffAddressCacheTest, MaxLegalNearCacheSize) {
185 VCDiffAddressCache negative_cache(VCD_MAX_MODES - 2, 0);
186 EXPECT_TRUE(negative_cache.Init());
187 }
188
TEST_F(VCDiffAddressCacheTest,MaxLegalSameCacheSize)189 TEST_F(VCDiffAddressCacheTest, MaxLegalSameCacheSize) {
190 VCDiffAddressCache negative_cache(0, VCD_MAX_MODES - 2);
191 EXPECT_TRUE(negative_cache.Init());
192 }
193
TEST_F(VCDiffAddressCacheTest,MaxLegalCombinedSizes)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
TEST_F(VCDiffAddressCacheTest,DestroyWithoutInitialization)200 TEST_F(VCDiffAddressCacheTest, DestroyWithoutInitialization) {
201 VCDiffAddressCache no_init_cache(4, 3);
202 // Should be destroyed without crashing
203 }
204
TEST_F(VCDiffAddressCacheTest,DestroyDefaultWithoutInitialization)205 TEST_F(VCDiffAddressCacheTest, DestroyDefaultWithoutInitialization) {
206 VCDiffAddressCache no_init_cache;
207 // Should be destroyed without crashing
208 }
209
TEST_F(VCDiffAddressCacheTest,CacheContentsInitiallyZero)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 //
TEST_F(VCDiffAddressCacheTest,InsertFirstTen)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
TEST_F(VCDiffAddressCacheTest,InsertIntMax)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 //
TEST_F(VCDiffAddressCacheTest,EncodeAddressModes)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 //
TEST_F(VCDiffAddressCacheTest,DecodeAddressModes)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.
TEST_F(VCDiffAddressCacheTest,EncodeAddressZeroCacheSizes)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
TEST_F(VCDiffAddressCacheTest,DecodeAddressZeroCacheSizes)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
TEST_F(VCDiffAddressCacheDeathTest,EncodeNegativeAddress)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
TEST_F(VCDiffAddressCacheDeathTest,EncodeAddressPastHereAddress)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
TEST_F(VCDiffAddressCacheDeathTest,DecodeInvalidMode)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
TEST_F(VCDiffAddressCacheDeathTest,DecodeZeroOrNegativeHereAddress)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
TEST_F(VCDiffAddressCacheTest,DecodeAddressPastHereAddress)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
TEST_F(VCDiffAddressCacheTest,HereModeAddressTooLarge)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
TEST_F(VCDiffAddressCacheTest,NearModeAddressOverflow)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 //
TEST_F(VCDiffAddressCacheTest,DecodeInvalidVarint)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 //
TEST_F(VCDiffAddressCacheTest,DecodePartialVarint)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
TEST_F(VCDiffAddressCacheDeathTest,DecodeBadMode)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
TEST_F(VCDiffAddressCacheTest,DecodeInvalidHereAddress)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
TEST_F(VCDiffAddressCacheTest,DecodeInvalidNearAddress)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
BM_Setup(int test_size)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
BM_CacheEncode(int iterations,int test_size)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
BM_CacheDecode(int iterations,int test_size)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
TEST_F(VCDiffAddressCacheTest,PerformanceTest)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