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