10a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath// Copyright 2007 Google Inc. 20a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath// Authors: Jeff Dean, Lincoln Smith 30a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath// 40a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath// Licensed under the Apache License, Version 2.0 (the "License"); 50a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath// you may not use this file except in compliance with the License. 60a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath// You may obtain a copy of the License at 70a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath// 80a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath// http://www.apache.org/licenses/LICENSE-2.0 90a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath// 100a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath// Unless required by applicable law or agreed to in writing, software 110a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath// distributed under the License is distributed on an "AS IS" BASIS, 120a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 130a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath// See the License for the specific language governing permissions and 140a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath// limitations under the License. 150a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 160a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath#include <config.h> 170a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath#include "rolling_hash.h" 180a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath#include <stdint.h> // uint32_t 190a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath#include <stdlib.h> // rand, srand 200a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath#include <vector> 210a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath#include "testing.h" 220a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 230a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamathnamespace open_vcdiff { 240a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamathnamespace { 250a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 260a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamathstatic const uint32_t kBase = RollingHashUtil::kBase; 270a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 280a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamathclass RollingHashSimpleTest : public testing::Test { 290a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath protected: 300a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath RollingHashSimpleTest() { } 310a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath virtual ~RollingHashSimpleTest() { } 320a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 330a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath void TestModBase(uint32_t operand) { 340a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath EXPECT_EQ(operand % kBase, RollingHashUtil::ModBase(operand)); 350a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath EXPECT_EQ(static_cast<uint32_t>((-static_cast<int32_t>(operand)) % kBase), 360a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath RollingHashUtil::FindModBaseInverse(operand)); 370a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath EXPECT_EQ(0U, RollingHashUtil::ModBase( 380a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath operand + RollingHashUtil::FindModBaseInverse(operand))); 390a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } 400a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 410a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath void TestHashFirstTwoBytes(char first_value, char second_value) { 420a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath char buf[2]; 430a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath buf[0] = first_value; 440a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath buf[1] = second_value; 450a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath EXPECT_EQ(RollingHashUtil::HashFirstTwoBytes(buf), 460a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath RollingHashUtil::HashStep(RollingHashUtil::HashStep(0, 470a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath first_value), 480a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath second_value)); 490a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath EXPECT_EQ(RollingHashUtil::HashFirstTwoBytes(buf), 500a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath RollingHashUtil::HashStep(static_cast<unsigned char>(first_value), 510a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath second_value)); 520a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } 530a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath}; 540a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 550a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath#ifdef GTEST_HAS_DEATH_TEST 560a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamathtypedef RollingHashSimpleTest RollingHashDeathTest; 570a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath#endif // GTEST_HAS_DEATH_TEST 580a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 590a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan KamathTEST_F(RollingHashSimpleTest, KBaseIsAPowerOfTwo) { 600a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath EXPECT_EQ(0U, kBase & (kBase - 1)); 610a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath} 620a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 630a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan KamathTEST_F(RollingHashSimpleTest, TestModBaseForValues) { 640a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath TestModBase(0); 650a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath TestModBase(10); 660a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath TestModBase(static_cast<uint32_t>(-10)); 670a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath TestModBase(kBase - 1); 680a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath TestModBase(kBase); 690a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath TestModBase(kBase + 1); 700a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath TestModBase(0x7FFFFFFF); 710a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath TestModBase(0x80000000); 720a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath TestModBase(0xFFFFFFFE); 730a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath TestModBase(0xFFFFFFFF); 740a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath} 750a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 760a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan KamathTEST_F(RollingHashSimpleTest, VerifyHashFirstTwoBytes) { 770a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath TestHashFirstTwoBytes(0x00, 0x00); 780a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath TestHashFirstTwoBytes(0x00, 0xFF); 790a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath TestHashFirstTwoBytes(0xFF, 0x00); 800a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath TestHashFirstTwoBytes(0xFF, 0xFF); 810a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath TestHashFirstTwoBytes(0x00, 0x80); 820a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath TestHashFirstTwoBytes(0x7F, 0xFF); 830a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath TestHashFirstTwoBytes(0x7F, 0x80); 840a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath TestHashFirstTwoBytes(0x01, 0x8F); 850a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath} 860a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 870a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath#ifdef GTEST_HAS_DEATH_TEST 880a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan KamathTEST_F(RollingHashDeathTest, InstantiateRollingHashWithoutCallingInit) { 890a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath EXPECT_DEBUG_DEATH(RollingHash<16> bad_hash, "Init"); 900a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath} 910a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath#endif // GTEST_HAS_DEATH_TEST 920a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 930a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamathclass RollingHashTest : public testing::Test { 940a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath public: 950a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath static const int kUpdateHashBlocks = 1000; 960a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath static const int kLargestBlockSize = 128; 970a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 980a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath static void MakeRandomBuffer(char* buffer, int buffer_size) { 990a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath for (int i = 0; i < buffer_size; ++i) { 1000a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath buffer[i] = PortableRandomInRange<unsigned char>(0xFF); 1010a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } 1020a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } 1030a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 1040a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath template<int kBlockSize> static void BM_DefaultHash(int iterations, 1050a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath const char *buffer) { 1060a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath RollingHash<kBlockSize> hasher; 1070a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath static uint32_t result_array[kUpdateHashBlocks]; 1080a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath for (int iter = 0; iter < iterations; ++iter) { 1090a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath for (int i = 0; i < kUpdateHashBlocks; ++i) { 1100a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath result_array[i] = hasher.Hash(&buffer[i]); 1110a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } 1120a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } 1130a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } 1140a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 1150a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath template<int kBlockSize> static void BM_UpdateHash(int iterations, 1160a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath const char *buffer) { 1170a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath RollingHash<kBlockSize> hasher; 1180a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath static uint32_t result_array[kUpdateHashBlocks]; 1190a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath for (int iter = 0; iter < iterations; ++iter) { 1200a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath uint32_t running_hash = hasher.Hash(buffer); 1210a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath for (int i = 0; i < kUpdateHashBlocks; ++i) { 1220a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath running_hash = hasher.UpdateHash(running_hash, 1230a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath buffer[i], 1240a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath buffer[i + kBlockSize]); 1250a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath result_array[i] = running_hash; 1260a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } 1270a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } 1280a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } 1290a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 1300a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath protected: 1310a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath static const int kUpdateHashTestIterations = 400; 1320a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath static const int kTimingTestSize = 1 << 14; // 16K iterations 1330a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 1340a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath RollingHashTest() { } 1350a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath virtual ~RollingHashTest() { } 1360a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 1370a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath template<int kBlockSize> void UpdateHashMatchesHashForBlockSize() { 1380a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath RollingHash<kBlockSize>::Init(); 1390a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath RollingHash<kBlockSize> hasher; 1400a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath for (int x = 0; x < kUpdateHashTestIterations; ++x) { 1410a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath int random_buffer_size = 1420a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath PortableRandomInRange(kUpdateHashBlocks - 1) + kBlockSize; 1430a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath MakeRandomBuffer(buffer_, random_buffer_size); 1440a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath uint32_t running_hash = hasher.Hash(buffer_); 1450a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath for (int i = kBlockSize; i < random_buffer_size; ++i) { 1460a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath // UpdateHash() calculates the hash value incrementally. 1470a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath running_hash = hasher.UpdateHash(running_hash, 1480a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath buffer_[i - kBlockSize], 1490a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath buffer_[i]); 1500a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath // Hash() calculates the hash value from scratch. Verify that both 1510a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath // methods return the same hash value. 1520a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath EXPECT_EQ(running_hash, hasher.Hash(&buffer_[i + 1 - kBlockSize])); 1530a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } 1540a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } 1550a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } 1560a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 1570a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath template<int kBlockSize> double DefaultHashTimingTest() { 1580a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath // Execution time is expected to be O(kBlockSize) per hash operation, 1590a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath // so scale the number of iterations accordingly 1600a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath const int kTimingTestIterations = kTimingTestSize / kBlockSize; 1610a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath CycleTimer timer; 1620a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath timer.Start(); 1630a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath BM_DefaultHash<kBlockSize>(kTimingTestIterations, buffer_); 1640a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath timer.Stop(); 1650a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath return static_cast<double>(timer.GetInUsec()) 1660a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath / (kTimingTestIterations * kUpdateHashBlocks); 1670a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } 1680a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 1690a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath template<int kBlockSize> double RollingTimingTest() { 1700a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath // Execution time is expected to be O(1) per hash operation, 1710a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath // so leave the number of iterations constant 1720a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath const int kTimingTestIterations = kTimingTestSize; 1730a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath CycleTimer timer; 1740a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath timer.Start(); 1750a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath BM_UpdateHash<kBlockSize>(kTimingTestIterations, buffer_); 1760a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath timer.Stop(); 1770a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath return static_cast<double>(timer.GetInUsec()) 1780a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath / (kTimingTestIterations * kUpdateHashBlocks); 1790a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } 1800a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 1810a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath double FindPercentage(double original, double modified) { 1820a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath if (original < 0.0001) { 1830a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath return 0.0; 1840a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } else { 1850a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath return ((modified - original) / original) * 100.0; 1860a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } 1870a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } 1880a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 1890a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath template<int kBlockSize> void RunTimingTestForBlockSize() { 1900a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath RollingHash<kBlockSize>::Init(); 1910a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath MakeRandomBuffer(buffer_, sizeof(buffer_)); 1920a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath const double time_for_default_hash = DefaultHashTimingTest<kBlockSize>(); 1930a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath const double time_for_rolling_hash = RollingTimingTest<kBlockSize>(); 1940a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath printf("%d\t%f\t%f (%f%%)\n", 1950a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath kBlockSize, 1960a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath time_for_default_hash, 1970a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath time_for_rolling_hash, 1980a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath FindPercentage(time_for_default_hash, time_for_rolling_hash)); 1990a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath CHECK_GT(time_for_default_hash, 0.0); 2000a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath CHECK_GT(time_for_rolling_hash, 0.0); 2010a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath if (kBlockSize > 16) { 2020a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath EXPECT_GT(time_for_default_hash, time_for_rolling_hash); 2030a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } 2040a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath } 2050a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 2060a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath char buffer_[kUpdateHashBlocks + kLargestBlockSize]; 2070a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath}; 2080a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 2090a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan KamathTEST_F(RollingHashTest, UpdateHashMatchesHashFromScratch) { 2100a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath srand(1); // test should be deterministic, including calls to rand() 2110a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath UpdateHashMatchesHashForBlockSize<4>(); 2120a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath UpdateHashMatchesHashForBlockSize<8>(); 2130a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath UpdateHashMatchesHashForBlockSize<16>(); 2140a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath UpdateHashMatchesHashForBlockSize<32>(); 2150a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath UpdateHashMatchesHashForBlockSize<64>(); 2160a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath UpdateHashMatchesHashForBlockSize<128>(); 2170a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath} 2180a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 2190a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan KamathTEST_F(RollingHashTest, TimingTests) { 2200a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath srand(1); // test should be deterministic, including calls to rand() 2210a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath printf("BlkSize\tHash (us)\tUpdateHash (us)\n"); 2220a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath RunTimingTestForBlockSize<4>(); 2230a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath RunTimingTestForBlockSize<8>(); 2240a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath RunTimingTestForBlockSize<16>(); 2250a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath RunTimingTestForBlockSize<32>(); 2260a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath RunTimingTestForBlockSize<64>(); 2270a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath RunTimingTestForBlockSize<128>(); 2280a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath} 2290a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath 2300a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath} // anonymous namespace 2310a58c5c2f73e5047b36f12b5f12b12d6f2a9f69dNarayan Kamath} // namespace open_vcdiff 232