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
28namespace open_vcdiff {
29namespace {
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//
35class 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
134typedef VCDiffAddressCacheTest VCDiffAddressCacheDeathTest;
135#endif  // GTEST_HAS_DEATH_TEST
136
137// Having either or both cache size == 0 is acceptable
138TEST_F(VCDiffAddressCacheTest, ZeroCacheSizes) {
139  VCDiffAddressCache zero_cache(0, 0);
140  EXPECT_TRUE(zero_cache.Init());
141}
142
143TEST_F(VCDiffAddressCacheTest, NegativeCacheSizes) {
144  VCDiffAddressCache negative_cache(-1, -1);   // The constructor must not fail
145  EXPECT_FALSE(negative_cache.Init());
146}
147
148TEST_F(VCDiffAddressCacheTest, OnlySameCacheSizeIsNegative) {
149  VCDiffAddressCache negative_cache(0, -1);   // The constructor must not fail
150  EXPECT_FALSE(negative_cache.Init());
151}
152
153TEST_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
159TEST_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).
168TEST_F(VCDiffAddressCacheTest, NearCacheSizeIsTooBig) {
169  VCDiffAddressCache negative_cache(VCD_MAX_MODES - 1, 0);
170  EXPECT_FALSE(negative_cache.Init());
171}
172
173TEST_F(VCDiffAddressCacheTest, SameCacheSizeIsTooBig) {
174  VCDiffAddressCache negative_cache(0, VCD_MAX_MODES - 1);
175  EXPECT_FALSE(negative_cache.Init());
176}
177
178TEST_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
184TEST_F(VCDiffAddressCacheTest, MaxLegalNearCacheSize) {
185  VCDiffAddressCache negative_cache(VCD_MAX_MODES - 2, 0);
186  EXPECT_TRUE(negative_cache.Init());
187}
188
189TEST_F(VCDiffAddressCacheTest, MaxLegalSameCacheSize) {
190  VCDiffAddressCache negative_cache(0, VCD_MAX_MODES - 2);
191  EXPECT_TRUE(negative_cache.Init());
192}
193
194TEST_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
200TEST_F(VCDiffAddressCacheTest, DestroyWithoutInitialization) {
201  VCDiffAddressCache no_init_cache(4, 3);
202  // Should be destroyed without crashing
203}
204
205TEST_F(VCDiffAddressCacheTest, DestroyDefaultWithoutInitialization) {
206  VCDiffAddressCache no_init_cache;
207  // Should be destroyed without crashing
208}
209
210TEST_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//
224TEST_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
242TEST_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//
255TEST_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//
272TEST_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.
321TEST_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
342TEST_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
367TEST_F(VCDiffAddressCacheDeathTest, EncodeNegativeAddress) {
368  VCDAddress dummy_encoded_address = 0;
369  EXPECT_DEBUG_DEATH(cache_.EncodeAddress(-1, -1, &dummy_encoded_address),
370                     "negative");
371}
372
373TEST_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
381TEST_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
399TEST_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
423TEST_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
433TEST_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
443TEST_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//
468TEST_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//
485TEST_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
510TEST_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
523TEST_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
533TEST_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
550void 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
562void 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
587void 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
607TEST_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