Home | History | Annotate | Download | only in src
      1 // Copyright 2007 Google Inc.
      2 // Authors: Jeff Dean, 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 "rolling_hash.h"
     18 #include <stdint.h>  // uint32_t
     19 #include <stdlib.h>  // rand, srand
     20 #include <vector>
     21 #include "testing.h"
     22 
     23 namespace open_vcdiff {
     24 namespace {
     25 
     26 static const uint32_t kBase = RollingHashUtil::kBase;
     27 
     28 class RollingHashSimpleTest : public testing::Test {
     29  protected:
     30   RollingHashSimpleTest() { }
     31   virtual ~RollingHashSimpleTest() { }
     32 
     33   void TestModBase(uint32_t operand) {
     34     EXPECT_EQ(operand % kBase, RollingHashUtil::ModBase(operand));
     35     EXPECT_EQ(static_cast<uint32_t>((-static_cast<int32_t>(operand)) % kBase),
     36               RollingHashUtil::FindModBaseInverse(operand));
     37     EXPECT_EQ(0U, RollingHashUtil::ModBase(
     38         operand + RollingHashUtil::FindModBaseInverse(operand)));
     39   }
     40 
     41   void TestHashFirstTwoBytes(char first_value, char second_value) {
     42     char buf[2];
     43     buf[0] = first_value;
     44     buf[1] = second_value;
     45     EXPECT_EQ(RollingHashUtil::HashFirstTwoBytes(buf),
     46               RollingHashUtil::HashStep(RollingHashUtil::HashStep(0,
     47                                                                   first_value),
     48                                         second_value));
     49     EXPECT_EQ(RollingHashUtil::HashFirstTwoBytes(buf),
     50               RollingHashUtil::HashStep(static_cast<unsigned char>(first_value),
     51                                         second_value));
     52   }
     53 };
     54 
     55 #ifdef GTEST_HAS_DEATH_TEST
     56 typedef RollingHashSimpleTest RollingHashDeathTest;
     57 #endif  // GTEST_HAS_DEATH_TEST
     58 
     59 TEST_F(RollingHashSimpleTest, KBaseIsAPowerOfTwo) {
     60   EXPECT_EQ(0U, kBase & (kBase - 1));
     61 }
     62 
     63 TEST_F(RollingHashSimpleTest, TestModBaseForValues) {
     64   TestModBase(0);
     65   TestModBase(10);
     66   TestModBase(static_cast<uint32_t>(-10));
     67   TestModBase(kBase - 1);
     68   TestModBase(kBase);
     69   TestModBase(kBase + 1);
     70   TestModBase(0x7FFFFFFF);
     71   TestModBase(0x80000000);
     72   TestModBase(0xFFFFFFFE);
     73   TestModBase(0xFFFFFFFF);
     74 }
     75 
     76 TEST_F(RollingHashSimpleTest, VerifyHashFirstTwoBytes) {
     77   TestHashFirstTwoBytes(0x00, 0x00);
     78   TestHashFirstTwoBytes(0x00, 0xFF);
     79   TestHashFirstTwoBytes(0xFF, 0x00);
     80   TestHashFirstTwoBytes(0xFF, 0xFF);
     81   TestHashFirstTwoBytes(0x00, 0x80);
     82   TestHashFirstTwoBytes(0x7F, 0xFF);
     83   TestHashFirstTwoBytes(0x7F, 0x80);
     84   TestHashFirstTwoBytes(0x01, 0x8F);
     85 }
     86 
     87 #ifdef GTEST_HAS_DEATH_TEST
     88 TEST_F(RollingHashDeathTest, InstantiateRollingHashWithoutCallingInit) {
     89   EXPECT_DEBUG_DEATH(RollingHash<16> bad_hash, "Init");
     90 }
     91 #endif  // GTEST_HAS_DEATH_TEST
     92 
     93 class RollingHashTest : public testing::Test {
     94  public:
     95   static const int kUpdateHashBlocks = 1000;
     96   static const int kLargestBlockSize = 128;
     97 
     98   static void MakeRandomBuffer(char* buffer, int buffer_size) {
     99     for (int i = 0; i < buffer_size; ++i) {
    100       buffer[i] = PortableRandomInRange<unsigned char>(0xFF);
    101     }
    102   }
    103 
    104   template<int kBlockSize> static void BM_DefaultHash(int iterations,
    105                                                       const char *buffer) {
    106     RollingHash<kBlockSize> hasher;
    107     static uint32_t result_array[kUpdateHashBlocks];
    108     for (int iter = 0; iter < iterations; ++iter) {
    109       for (int i = 0; i < kUpdateHashBlocks; ++i) {
    110         result_array[i] = hasher.Hash(&buffer[i]);
    111       }
    112     }
    113   }
    114 
    115   template<int kBlockSize> static void BM_UpdateHash(int iterations,
    116                                                      const char *buffer) {
    117     RollingHash<kBlockSize> hasher;
    118     static uint32_t result_array[kUpdateHashBlocks];
    119     for (int iter = 0; iter < iterations; ++iter) {
    120       uint32_t running_hash = hasher.Hash(buffer);
    121       for (int i = 0; i < kUpdateHashBlocks; ++i) {
    122         running_hash = hasher.UpdateHash(running_hash,
    123                                          buffer[i],
    124                                          buffer[i + kBlockSize]);
    125         result_array[i] = running_hash;
    126       }
    127     }
    128   }
    129 
    130  protected:
    131   static const int kUpdateHashTestIterations = 400;
    132   static const int kTimingTestSize = 1 << 14;  // 16K iterations
    133 
    134   RollingHashTest() { }
    135   virtual ~RollingHashTest() { }
    136 
    137   template<int kBlockSize> void UpdateHashMatchesHashForBlockSize() {
    138     RollingHash<kBlockSize>::Init();
    139     RollingHash<kBlockSize> hasher;
    140     for (int x = 0; x < kUpdateHashTestIterations; ++x) {
    141       int random_buffer_size =
    142           PortableRandomInRange(kUpdateHashBlocks - 1) + kBlockSize;
    143       MakeRandomBuffer(buffer_, random_buffer_size);
    144       uint32_t running_hash = hasher.Hash(buffer_);
    145       for (int i = kBlockSize; i < random_buffer_size; ++i) {
    146         // UpdateHash() calculates the hash value incrementally.
    147         running_hash = hasher.UpdateHash(running_hash,
    148                                          buffer_[i - kBlockSize],
    149                                          buffer_[i]);
    150         // Hash() calculates the hash value from scratch.  Verify that both
    151         // methods return the same hash value.
    152         EXPECT_EQ(running_hash, hasher.Hash(&buffer_[i + 1 - kBlockSize]));
    153       }
    154     }
    155   }
    156 
    157   template<int kBlockSize> double DefaultHashTimingTest() {
    158     // Execution time is expected to be O(kBlockSize) per hash operation,
    159     // so scale the number of iterations accordingly
    160     const int kTimingTestIterations = kTimingTestSize / kBlockSize;
    161     CycleTimer timer;
    162     timer.Start();
    163     BM_DefaultHash<kBlockSize>(kTimingTestIterations, buffer_);
    164     timer.Stop();
    165     return static_cast<double>(timer.GetInUsec())
    166         / (kTimingTestIterations * kUpdateHashBlocks);
    167   }
    168 
    169   template<int kBlockSize> double RollingTimingTest() {
    170     // Execution time is expected to be O(1) per hash operation,
    171     // so leave the number of iterations constant
    172     const int kTimingTestIterations = kTimingTestSize;
    173     CycleTimer timer;
    174     timer.Start();
    175     BM_UpdateHash<kBlockSize>(kTimingTestIterations, buffer_);
    176     timer.Stop();
    177     return static_cast<double>(timer.GetInUsec())
    178         / (kTimingTestIterations * kUpdateHashBlocks);
    179   }
    180 
    181   double FindPercentage(double original, double modified) {
    182     if (original < 0.0001) {
    183       return 0.0;
    184     } else {
    185       return ((modified - original) / original) * 100.0;
    186     }
    187   }
    188 
    189   template<int kBlockSize> void RunTimingTestForBlockSize() {
    190     RollingHash<kBlockSize>::Init();
    191     MakeRandomBuffer(buffer_, sizeof(buffer_));
    192     const double time_for_default_hash = DefaultHashTimingTest<kBlockSize>();
    193     const double time_for_rolling_hash = RollingTimingTest<kBlockSize>();
    194     printf("%d\t%f\t%f (%f%%)\n",
    195            kBlockSize,
    196            time_for_default_hash,
    197            time_for_rolling_hash,
    198            FindPercentage(time_for_default_hash, time_for_rolling_hash));
    199     CHECK_GT(time_for_default_hash, 0.0);
    200     CHECK_GT(time_for_rolling_hash, 0.0);
    201     if (kBlockSize > 16) {
    202       EXPECT_GT(time_for_default_hash, time_for_rolling_hash);
    203     }
    204   }
    205 
    206   char buffer_[kUpdateHashBlocks + kLargestBlockSize];
    207 };
    208 
    209 TEST_F(RollingHashTest, UpdateHashMatchesHashFromScratch) {
    210   srand(1);  // test should be deterministic, including calls to rand()
    211   UpdateHashMatchesHashForBlockSize<4>();
    212   UpdateHashMatchesHashForBlockSize<8>();
    213   UpdateHashMatchesHashForBlockSize<16>();
    214   UpdateHashMatchesHashForBlockSize<32>();
    215   UpdateHashMatchesHashForBlockSize<64>();
    216   UpdateHashMatchesHashForBlockSize<128>();
    217 }
    218 
    219 TEST_F(RollingHashTest, TimingTests) {
    220   srand(1);  // test should be deterministic, including calls to rand()
    221   printf("BlkSize\tHash (us)\tUpdateHash (us)\n");
    222   RunTimingTestForBlockSize<4>();
    223   RunTimingTestForBlockSize<8>();
    224   RunTimingTestForBlockSize<16>();
    225   RunTimingTestForBlockSize<32>();
    226   RunTimingTestForBlockSize<64>();
    227   RunTimingTestForBlockSize<128>();
    228 }
    229 
    230 }  // anonymous namespace
    231 }  // namespace open_vcdiff
    232