| // Copyright 2008 Google Inc. |
| // Author: Lincoln Smith |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| #include <config.h> |
| #include "blockhash.h" |
| #include <limits.h> // INT_MIN |
| #include <string.h> // memcpy, memcmp, strlen |
| #include <iostream> |
| #include <memory> // auto_ptr |
| #include "encodetable.h" |
| #include "rolling_hash.h" |
| #include "testing.h" |
| |
| namespace open_vcdiff { |
| |
| const int kBlockSize = BlockHash::kBlockSize; |
| |
| class BlockHashTest : public testing::Test { |
| protected: |
| static const int kTimingTestSize = 1 << 21; // 2M |
| static const int kTimingTestIterations = 32; |
| |
| BlockHashTest() { |
| dh_.reset(BlockHash::CreateDictionaryHash(sample_text, |
| strlen(sample_text))); |
| th_.reset(BlockHash::CreateTargetHash(sample_text, strlen(sample_text), 0)); |
| EXPECT_TRUE(dh_.get() != NULL); |
| EXPECT_TRUE(th_.get() != NULL); |
| } |
| |
| // BlockHashTest is a friend to BlockHash. Expose the protected functions |
| // that will be tested by the children of BlockHashTest. |
| static bool BlockContentsMatch(const char* block1, const char* block2) { |
| return BlockHash::BlockContentsMatch(block1, block2); |
| } |
| |
| int FirstMatchingBlock(const BlockHash& block_hash, |
| uint32_t hash_value, |
| const char* block_ptr) const { |
| return block_hash.FirstMatchingBlock(hash_value, block_ptr); |
| } |
| |
| int NextMatchingBlock(const BlockHash& block_hash, |
| int block_number, |
| const char* block_ptr) const { |
| return block_hash.NextMatchingBlock(block_number, block_ptr); |
| } |
| |
| static int MatchingBytesToLeft(const char* source_match_start, |
| const char* target_match_start, |
| int max_bytes) { |
| return BlockHash::MatchingBytesToLeft(source_match_start, |
| target_match_start, |
| max_bytes); |
| } |
| |
| static int MatchingBytesToRight(const char* source_match_end, |
| const char* target_match_end, |
| int max_bytes) { |
| return BlockHash::MatchingBytesToRight(source_match_end, |
| target_match_end, |
| max_bytes); |
| } |
| |
| static int StringLengthAsInt(const char* s) { |
| return static_cast<int>(strlen(s)); |
| } |
| |
| void InitBlocksToDifferAtNthByte(int n) { |
| CHECK(n < kBlockSize); |
| memset(compare_buffer_1_, 0xBE, kTimingTestSize); |
| memset(compare_buffer_2_, 0xBE, kTimingTestSize); |
| for (int index = n; index < kTimingTestSize; index += kBlockSize) { |
| compare_buffer_1_[index] = 0x00; |
| compare_buffer_2_[index] = 0x01; |
| } |
| } |
| |
| void TestAndPrintTimesForCompareFunctions(bool should_be_identical); |
| |
| void TimingTestForBlocksThatDifferAtByte(int n) { |
| InitBlocksToDifferAtNthByte(n); |
| std::cout << "Comparing blocks that differ at byte " << n << std::endl; |
| TestAndPrintTimesForCompareFunctions(false); |
| } |
| |
| // Copy sample_text_without_spaces and search_string_without_spaces |
| // into newly allocated sample_text and search_string buffers, |
| // but pad them with space characters so that every character |
| // in sample_text_without_spaces matches (kBlockSize - 1) |
| // space characters in sample_text, followed by that character. |
| // For example: |
| // Since sample_text_without_spaces begins "The only thing"..., |
| // if kBlockSize is 4, then 3 space characters will be inserted |
| // between each letter of sample_text, as follows: |
| // " T h e o n l y t h i n g"... |
| // This makes testing simpler, because finding a kBlockSize-byte match |
| // between the sample text and search string only depends on the |
| // trailing letter in each block. |
| static void MakeEachLetterABlock(const char* string_without_spaces, |
| const char** result) { |
| const size_t length_without_spaces = strlen(string_without_spaces); |
| char* padded_text = new char[(kBlockSize * length_without_spaces) + 1]; |
| memset(padded_text, ' ', kBlockSize * length_without_spaces); |
| char* padded_text_ptr = padded_text + (kBlockSize - 1); |
| for (size_t i = 0; i < length_without_spaces; ++i) { |
| *padded_text_ptr = string_without_spaces[i]; |
| padded_text_ptr += kBlockSize; |
| } |
| padded_text[kBlockSize * length_without_spaces] = '\0'; |
| *result = padded_text; |
| } |
| |
| static void SetUpTestCase() { |
| MakeEachLetterABlock(sample_text_without_spaces, &sample_text); |
| MakeEachLetterABlock(search_string_without_spaces, &search_string); |
| MakeEachLetterABlock(search_string_altered_without_spaces, |
| &search_string_altered); |
| MakeEachLetterABlock(search_to_end_without_spaces, &search_to_end_string); |
| MakeEachLetterABlock(search_to_beginning_without_spaces, |
| &search_to_beginning_string); |
| MakeEachLetterABlock(sample_text_many_matches_without_spaces, |
| &sample_text_many_matches); |
| MakeEachLetterABlock(search_string_many_matches_without_spaces, |
| &search_string_many_matches); |
| MakeEachLetterABlock("y", &test_string_y); |
| MakeEachLetterABlock("e", &test_string_e); |
| char* new_test_string_unaligned_e = new char[kBlockSize]; |
| memset(new_test_string_unaligned_e, ' ', kBlockSize); |
| new_test_string_unaligned_e[kBlockSize - 2] = 'e'; |
| test_string_unaligned_e = new_test_string_unaligned_e; |
| char* new_test_string_all_Qs = new char[kBlockSize]; |
| memset(new_test_string_all_Qs, 'Q', kBlockSize); |
| test_string_all_Qs = new_test_string_all_Qs; |
| hashed_y = RollingHash<kBlockSize>::Hash(test_string_y); |
| hashed_e = RollingHash<kBlockSize>::Hash(test_string_e); |
| hashed_f = |
| RollingHash<kBlockSize>::Hash(&search_string[index_of_f_in_fearsome]); |
| hashed_unaligned_e = RollingHash<kBlockSize>::Hash(test_string_unaligned_e); |
| hashed_all_Qs = RollingHash<kBlockSize>::Hash(test_string_all_Qs); |
| } |
| |
| static void TearDownTestCase() { |
| delete[] sample_text; |
| delete[] search_string; |
| delete[] search_string_altered; |
| delete[] search_to_end_string; |
| delete[] search_to_beginning_string; |
| delete[] sample_text_many_matches; |
| delete[] search_string_many_matches; |
| delete[] test_string_y; |
| delete[] test_string_e; |
| delete[] test_string_unaligned_e; |
| delete[] test_string_all_Qs; |
| } |
| |
| // Each block in the sample text and search string is kBlockSize bytes long, |
| // and consists of (kBlockSize - 1) space characters |
| // followed by a single letter of text. |
| |
| // Block numbers of certain characters within the sample text: |
| // All six occurrences of "e", in order. |
| static const int block_of_first_e = 2; |
| static const int block_of_second_e = 16; |
| static const int block_of_third_e = 21; |
| static const int block_of_fourth_e = 27; |
| static const int block_of_fifth_e = 35; |
| static const int block_of_sixth_e = 42; |
| |
| static const int block_of_y_in_only = 7; |
| // The block number is multiplied by kBlockSize to arrive at the |
| // index, which points to the (kBlockSize - 1) space characters before |
| // the letter specified. |
| // Indices of certain characters within the sample text. |
| static const int index_of_first_e = block_of_first_e * kBlockSize; |
| static const int index_of_fourth_e = block_of_fourth_e * kBlockSize; |
| static const int index_of_sixth_e = block_of_sixth_e * kBlockSize; |
| static const int index_of_y_in_only = block_of_y_in_only * kBlockSize; |
| static const int index_of_space_before_fear_is_fear = 25 * kBlockSize; |
| static const int index_of_longest_match_ear_is_fear = 27 * kBlockSize; |
| static const int index_of_i_in_fear_is_fear = 31 * kBlockSize; |
| static const int index_of_space_before_fear_itself = 33 * kBlockSize; |
| static const int index_of_space_before_itself = 38 * kBlockSize; |
| static const int index_of_ababc = 4 * kBlockSize; |
| |
| // Indices of certain characters within the search strings. |
| static const int index_of_second_w_in_what_we = 5 * kBlockSize; |
| static const int index_of_second_e_in_what_we_hear = 9 * kBlockSize; |
| static const int index_of_f_in_fearsome = 16 * kBlockSize; |
| static const int index_of_space_in_eat_itself = 12 * kBlockSize; |
| static const int index_of_i_in_itself = 13 * kBlockSize; |
| static const int index_of_t_in_use_the = 4 * kBlockSize; |
| static const int index_of_o_in_online = 8 * kBlockSize; |
| |
| static const char sample_text_without_spaces[]; |
| static const char search_string_without_spaces[]; |
| static const char search_string_altered_without_spaces[]; |
| static const char search_to_end_without_spaces[]; |
| static const char search_to_beginning_without_spaces[]; |
| static const char sample_text_many_matches_without_spaces[]; |
| static const char search_string_many_matches_without_spaces[]; |
| |
| static const char* sample_text; |
| static const char* search_string; |
| static const char* search_string_altered; |
| static const char* search_to_end_string; |
| static const char* search_to_beginning_string; |
| static const char* sample_text_many_matches; |
| static const char* search_string_many_matches; |
| |
| static const char* test_string_y; |
| static const char* test_string_e; |
| static const char* test_string_all_Qs; |
| static const char* test_string_unaligned_e; |
| |
| static uint32_t hashed_y; |
| static uint32_t hashed_e; |
| static uint32_t hashed_f; |
| static uint32_t hashed_unaligned_e; |
| static uint32_t hashed_all_Qs; |
| |
| // Boost scoped_ptr, if available, could be used instead of std::auto_ptr. |
| std::auto_ptr<const BlockHash> dh_; // hash table is populated at startup |
| std::auto_ptr<BlockHash> th_; // hash table not populated; |
| // used to test incremental adds |
| |
| BlockHash::Match best_match_; |
| char* compare_buffer_1_; |
| char* compare_buffer_2_; |
| int prime_result_; |
| }; |
| |
| #ifdef GTEST_HAS_DEATH_TEST |
| typedef BlockHashTest BlockHashDeathTest; |
| #endif // GTEST_HAS_DEATH_TEST |
| |
| // The C++ standard requires a separate definition of these static const values, |
| // even though their initializers are given within the class definition. |
| const int BlockHashTest::block_of_first_e; |
| const int BlockHashTest::block_of_second_e; |
| const int BlockHashTest::block_of_third_e; |
| const int BlockHashTest::block_of_fourth_e; |
| const int BlockHashTest::block_of_fifth_e; |
| const int BlockHashTest::block_of_sixth_e; |
| const int BlockHashTest::block_of_y_in_only; |
| const int BlockHashTest::index_of_first_e; |
| const int BlockHashTest::index_of_fourth_e; |
| const int BlockHashTest::index_of_sixth_e; |
| const int BlockHashTest::index_of_y_in_only; |
| const int BlockHashTest::index_of_space_before_fear_is_fear; |
| const int BlockHashTest::index_of_longest_match_ear_is_fear; |
| const int BlockHashTest::index_of_i_in_fear_is_fear; |
| const int BlockHashTest::index_of_space_before_fear_itself; |
| const int BlockHashTest::index_of_space_before_itself; |
| const int BlockHashTest::index_of_ababc; |
| const int BlockHashTest::index_of_second_w_in_what_we; |
| const int BlockHashTest::index_of_second_e_in_what_we_hear; |
| const int BlockHashTest::index_of_f_in_fearsome; |
| const int BlockHashTest::index_of_space_in_eat_itself; |
| const int BlockHashTest::index_of_i_in_itself; |
| const int BlockHashTest::index_of_t_in_use_the; |
| const int BlockHashTest::index_of_o_in_online; |
| |
| const char BlockHashTest::sample_text_without_spaces[] = |
| "The only thing we have to fear is fear itself"; |
| |
| const char BlockHashTest::search_string_without_spaces[] = |
| "What we hear is fearsome"; |
| |
| const char BlockHashTest::search_string_altered_without_spaces[] = |
| "Vhat ve hear is fearsomm"; |
| |
| const char BlockHashTest::search_to_end_without_spaces[] = |
| "Pop will eat itself, eventually"; |
| |
| const char BlockHashTest::search_to_beginning_without_spaces[] = |
| "Use The online dictionary"; |
| |
| const char BlockHashTest::sample_text_many_matches_without_spaces[] = |
| "ababababcab"; |
| |
| const char BlockHashTest::search_string_many_matches_without_spaces[] = |
| "ababc"; |
| |
| const char* BlockHashTest::sample_text = NULL; |
| const char* BlockHashTest::search_string = NULL; |
| const char* BlockHashTest::search_string_altered = NULL; |
| const char* BlockHashTest::search_to_end_string = NULL; |
| const char* BlockHashTest::search_to_beginning_string = NULL; |
| const char* BlockHashTest::sample_text_many_matches = NULL; |
| const char* BlockHashTest::search_string_many_matches = NULL; |
| |
| const char* BlockHashTest::test_string_y = NULL; |
| const char* BlockHashTest::test_string_e = NULL; |
| const char* BlockHashTest::test_string_unaligned_e = NULL; |
| const char* BlockHashTest::test_string_all_Qs = NULL; |
| |
| uint32_t BlockHashTest::hashed_y = 0; |
| uint32_t BlockHashTest::hashed_e = 0; |
| uint32_t BlockHashTest::hashed_f = 0; |
| uint32_t BlockHashTest::hashed_unaligned_e = 0; |
| uint32_t BlockHashTest::hashed_all_Qs = 0; |
| |
| void BlockHashTest::TestAndPrintTimesForCompareFunctions( |
| bool should_be_identical) { |
| CHECK(compare_buffer_1_ != NULL); |
| CHECK(compare_buffer_2_ != NULL); |
| // Prime the memory cache. |
| prime_result_ = |
| memcmp(compare_buffer_1_, compare_buffer_2_, kTimingTestSize); |
| const char* const block1_limit = |
| &compare_buffer_1_[kTimingTestSize - kBlockSize]; |
| int block_compare_words_result = 0; |
| CycleTimer block_compare_words_timer; |
| block_compare_words_timer.Start(); |
| for (int i = 0; i < kTimingTestIterations; ++i) { |
| const char* block1 = compare_buffer_1_; |
| const char* block2 = compare_buffer_2_; |
| while (block1 < block1_limit) { |
| if (!BlockHash::BlockCompareWords(block1, block2)) { |
| ++block_compare_words_result; |
| } |
| block1 += kBlockSize; |
| block2 += kBlockSize; |
| } |
| } |
| block_compare_words_timer.Stop(); |
| double time_for_block_compare_words = |
| static_cast<double>(block_compare_words_timer.GetInUsec()) |
| / ((kTimingTestSize / kBlockSize) * kTimingTestIterations); |
| int block_contents_match_result = 0; |
| CycleTimer block_contents_match_timer; |
| block_contents_match_timer.Start(); |
| for (int i = 0; i < kTimingTestIterations; ++i) { |
| const char* block1 = compare_buffer_1_; |
| const char* block2 = compare_buffer_2_; |
| while (block1 < block1_limit) { |
| if (!BlockHash::BlockContentsMatch(block1, block2)) { |
| ++block_contents_match_result; |
| } |
| block1 += kBlockSize; |
| block2 += kBlockSize; |
| } |
| } |
| block_contents_match_timer.Stop(); |
| double time_for_block_contents_match = |
| static_cast<double>(block_contents_match_timer.GetInUsec()) |
| / ((kTimingTestSize / kBlockSize) * kTimingTestIterations); |
| EXPECT_EQ(block_contents_match_result, block_compare_words_result); |
| if (should_be_identical) { |
| CHECK_EQ(0, block_compare_words_result); |
| } else { |
| CHECK_GT(block_compare_words_result, 0); |
| } |
| std::cout << "BlockHash::BlockCompareWords: " |
| << time_for_block_compare_words << " us per operation" << std::endl; |
| std::cout << "BlockHash::BlockContentsMatch: " |
| << time_for_block_contents_match << " us per operation" |
| << std::endl; |
| if (time_for_block_compare_words > 0) { |
| double percent_change = |
| (((time_for_block_contents_match - time_for_block_compare_words) |
| / time_for_block_compare_words) * 100.0); |
| if (percent_change >= 0.0) { |
| std::cout << "BlockContentsMatch is " << percent_change << "%" |
| << " SLOWER than BlockCompareWords" << std::endl; |
| } else { |
| std::cout << "BlockContentsMatch is " << (-percent_change) << "%" |
| << " FASTER than BlockCompareWords" << std::endl; |
| } |
| } |
| #if defined(NDEBUG) && !defined(VCDIFF_USE_BLOCK_COMPARE_WORDS) |
| // Only check timings for optimized build. There's plenty of margin: this |
| // check will fail only if BlockContentsMatch is at least twice as slow as |
| // BlockCompareWords. |
| EXPECT_GT(time_for_block_compare_words * 2.0, time_for_block_contents_match); |
| #endif // NDEBUG && !VCDIFF_USE_BLOCK_COMPARE_WORDS |
| } |
| |
| // The two strings passed to BlockHash::MatchingBytesToLeft do have matching |
| // characters -- in fact, they're the same string -- but since max_bytes is zero |
| // or negative, BlockHash::MatchingBytesToLeft should not read from the strings |
| // and should return 0. |
| TEST_F(BlockHashTest, MaxBytesZeroDoesNothing) { |
| EXPECT_EQ(0, MatchingBytesToLeft( |
| &search_string[index_of_f_in_fearsome], |
| &search_string[index_of_f_in_fearsome], |
| 0)); |
| EXPECT_EQ(0, MatchingBytesToRight( |
| &search_string[index_of_f_in_fearsome], |
| &search_string[index_of_f_in_fearsome], |
| 0)); |
| } |
| |
| TEST_F(BlockHashTest, MaxBytesNegativeDoesNothing) { |
| EXPECT_EQ(0, MatchingBytesToLeft( |
| &search_string[index_of_f_in_fearsome], |
| &search_string[index_of_f_in_fearsome], |
| -1)); |
| EXPECT_EQ(0, MatchingBytesToLeft( |
| &search_string[index_of_f_in_fearsome], |
| &search_string[index_of_f_in_fearsome], |
| INT_MIN)); |
| EXPECT_EQ(0, MatchingBytesToRight( |
| &search_string[index_of_f_in_fearsome], |
| &search_string[index_of_f_in_fearsome], |
| -1)); |
| EXPECT_EQ(0, MatchingBytesToRight( |
| &search_string[index_of_f_in_fearsome], |
| &search_string[index_of_f_in_fearsome], |
| INT_MIN)); |
| } |
| |
| TEST_F(BlockHashTest, MaxBytesOneMatch) { |
| EXPECT_EQ(1, MatchingBytesToLeft( |
| &search_string[index_of_f_in_fearsome], |
| &search_string[index_of_f_in_fearsome], |
| 1)); |
| EXPECT_EQ(1, MatchingBytesToRight( |
| &search_string[index_of_f_in_fearsome], |
| &search_string[index_of_f_in_fearsome], |
| 1)); |
| } |
| |
| TEST_F(BlockHashTest, MaxBytesOneNoMatch) { |
| EXPECT_EQ(0, MatchingBytesToLeft( |
| &search_string[index_of_f_in_fearsome], |
| &search_string[index_of_second_e_in_what_we_hear], |
| 1)); |
| EXPECT_EQ(0, MatchingBytesToRight( |
| &search_string[index_of_f_in_fearsome], |
| &search_string[index_of_second_e_in_what_we_hear - 1], |
| 1)); |
| } |
| |
| TEST_F(BlockHashTest, LeftLimitedByMaxBytes) { |
| // The number of bytes that match between the original "we hear is fearsome" |
| // and the altered "ve hear is fearsome". |
| const int expected_length = kBlockSize * StringLengthAsInt("e hear is "); |
| const int max_bytes = expected_length - 1; |
| EXPECT_EQ(max_bytes, MatchingBytesToLeft( |
| &search_string[index_of_f_in_fearsome], |
| &search_string_altered[index_of_f_in_fearsome], |
| max_bytes)); |
| } |
| |
| TEST_F(BlockHashTest, LeftNotLimited) { |
| // The number of bytes that match between the original "we hear is fearsome" |
| // and the altered "ve hear is fearsome". |
| const int expected_length = kBlockSize * StringLengthAsInt("e hear is "); |
| const int max_bytes = expected_length + 1; |
| EXPECT_EQ(expected_length, MatchingBytesToLeft( |
| &search_string[index_of_f_in_fearsome], |
| &search_string_altered[index_of_f_in_fearsome], |
| max_bytes)); |
| EXPECT_EQ(expected_length, MatchingBytesToLeft( |
| &search_string[index_of_f_in_fearsome], |
| &search_string_altered[index_of_f_in_fearsome], |
| INT_MAX)); |
| } |
| |
| TEST_F(BlockHashTest, RightLimitedByMaxBytes) { |
| // The number of bytes that match between the original "fearsome" |
| // and the altered "fearsomm". |
| const int expected_length = (kBlockSize * StringLengthAsInt("fearsom")) |
| + (kBlockSize - 1); // spacing between letters |
| const int max_bytes = expected_length - 1; |
| EXPECT_EQ(max_bytes, MatchingBytesToRight( |
| &search_string[index_of_f_in_fearsome], |
| &search_string_altered[index_of_f_in_fearsome], |
| max_bytes)); |
| } |
| |
| TEST_F(BlockHashTest, RightNotLimited) { |
| // The number of bytes that match between the original "we hear is fearsome" |
| // and the altered "ve hear is fearsome". |
| const int expected_length = (kBlockSize * StringLengthAsInt("fearsom")) |
| + (kBlockSize - 1); // spacing between letters |
| const int max_bytes = expected_length + 1; |
| EXPECT_EQ(expected_length, MatchingBytesToRight( |
| &search_string[index_of_f_in_fearsome], |
| &search_string_altered[index_of_f_in_fearsome], |
| max_bytes)); |
| EXPECT_EQ(expected_length, MatchingBytesToRight( |
| &search_string[index_of_f_in_fearsome], |
| &search_string_altered[index_of_f_in_fearsome], |
| INT_MAX)); |
| } |
| |
| // If this test fails in a non-x86 or non-gcc environment, consider adding |
| // -DVCDIFF_USE_BLOCK_COMPARE_WORDS to AM_CXXFLAGS in Makefile.am and |
| // Makefile.in, and reconstructing the Makefile. That will cause blockhash.cc |
| // to use a special implementation (BlockCompareWords) to compare blocks |
| // rather than using standard memcmp. |
| TEST_F(BlockHashTest, BlockContentsMatchIsAsFastAsBlockCompareWords) { |
| compare_buffer_1_ = new char[kTimingTestSize]; |
| compare_buffer_2_ = new char[kTimingTestSize]; |
| |
| // The value 0xBE is arbitrarily chosen. First test with identical contents |
| // in the buffers, so that the comparison functions cannot short-circuit |
| // and will return true. |
| memset(compare_buffer_1_, 0xBE, kTimingTestSize); |
| memset(compare_buffer_2_, 0xBE, kTimingTestSize); |
| std::cout << "Comparing " |
| << (kTimingTestSize / kBlockSize) << " identical values:" |
| << std::endl; |
| TestAndPrintTimesForCompareFunctions(true); |
| |
| // Now change one value in the middle of one buffer, so that the contents |
| // are no longer the same. |
| compare_buffer_1_[kTimingTestSize / 2] = 0x00; |
| std::cout << "Comparing " |
| << ((kTimingTestSize / kBlockSize) - 1) << " identical values" |
| << " and one mismatch:" << std::endl; |
| TestAndPrintTimesForCompareFunctions(false); |
| |
| // Set one of the bytes of each block to differ so that |
| // none of the compare operations will return true, and run timing tests. |
| // In practice, BlockHash::BlockContentsMatch will only be called |
| // for two blocks whose hash values match, and the two most important |
| // cases are: (1) the blocks are identical, or (2) none of their bytes match. |
| TimingTestForBlocksThatDifferAtByte(0); |
| TimingTestForBlocksThatDifferAtByte(1); |
| TimingTestForBlocksThatDifferAtByte(kBlockSize / 2); |
| TimingTestForBlocksThatDifferAtByte(kBlockSize - 1); |
| |
| delete[] compare_buffer_1_; |
| delete[] compare_buffer_2_; |
| } |
| |
| TEST_F(BlockHashTest, FindFailsBeforeHashing) { |
| EXPECT_EQ(-1, FirstMatchingBlock(*th_, hashed_y, test_string_y)); |
| } |
| |
| TEST_F(BlockHashTest, HashOneFindOne) { |
| for (int i = 0; i <= index_of_y_in_only; ++i) { |
| th_->AddOneIndexHash(i, RollingHash<kBlockSize>::Hash(&sample_text[i])); |
| } |
| EXPECT_EQ(block_of_y_in_only, FirstMatchingBlock(*th_, hashed_y, |
| test_string_y)); |
| EXPECT_EQ(-1, NextMatchingBlock(*th_, block_of_y_in_only, test_string_y)); |
| } |
| |
| TEST_F(BlockHashTest, HashAllFindOne) { |
| EXPECT_EQ(block_of_y_in_only, FirstMatchingBlock(*dh_, hashed_y, |
| test_string_y)); |
| EXPECT_EQ(-1, NextMatchingBlock(*dh_, block_of_y_in_only, test_string_y)); |
| } |
| |
| TEST_F(BlockHashTest, NonMatchingTextNotFound) { |
| EXPECT_EQ(-1, FirstMatchingBlock(*dh_, hashed_all_Qs, test_string_all_Qs)); |
| } |
| |
| // Search for unaligned text. The test string is contained in the |
| // sample text (unlike the non-matching string in NonMatchingTextNotFound, |
| // above), but it is not aligned on a block boundary. FindMatchingBlock |
| // will only work if the test string is aligned on a block boundary. |
| // |
| // " T h e o n l y" |
| // ^^^^ Here is the test string |
| // |
| TEST_F(BlockHashTest, UnalignedTextNotFound) { |
| EXPECT_EQ(-1, FirstMatchingBlock(*dh_, hashed_unaligned_e, |
| test_string_unaligned_e)); |
| } |
| |
| TEST_F(BlockHashTest, FindSixMatches) { |
| EXPECT_EQ(block_of_first_e, FirstMatchingBlock(*dh_, hashed_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_second_e, NextMatchingBlock(*dh_, block_of_first_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_third_e, NextMatchingBlock(*dh_, block_of_second_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_fourth_e, NextMatchingBlock(*dh_, block_of_third_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_fifth_e, NextMatchingBlock(*dh_, block_of_fourth_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_sixth_e, NextMatchingBlock(*dh_, block_of_fifth_e, |
| test_string_e)); |
| EXPECT_EQ(-1, NextMatchingBlock(*dh_, block_of_sixth_e, test_string_e)); |
| |
| // Starting over gives same result |
| EXPECT_EQ(block_of_first_e, FirstMatchingBlock(*dh_, hashed_e, |
| test_string_e)); |
| } |
| |
| TEST_F(BlockHashTest, AddRangeFindThreeMatches) { |
| // Add hash values only for those characters before the fourth instance |
| // of "e" in the sample text. Tests that the ending index |
| // of AddAllBlocksThroughIndex() is not inclusive: only three matches |
| // for "e" should be found. |
| th_->AddAllBlocksThroughIndex(index_of_fourth_e); |
| EXPECT_EQ(block_of_first_e, FirstMatchingBlock(*th_, hashed_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_second_e, NextMatchingBlock(*th_, block_of_first_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_third_e, NextMatchingBlock(*th_, block_of_second_e, |
| test_string_e)); |
| EXPECT_EQ(-1, NextMatchingBlock(*th_, block_of_third_e, test_string_e)); |
| |
| // Starting over gives same result |
| EXPECT_EQ(block_of_first_e, FirstMatchingBlock(*th_, hashed_e, |
| test_string_e)); |
| } |
| |
| // Try indices that are not even multiples of the block size. |
| // Add three ranges and verify the results after each |
| // call to AddAllBlocksThroughIndex(). |
| TEST_F(BlockHashTest, AddRangeWithUnalignedIndices) { |
| th_->AddAllBlocksThroughIndex(index_of_first_e + 1); |
| EXPECT_EQ(block_of_first_e, FirstMatchingBlock(*th_, hashed_e, |
| test_string_e)); |
| EXPECT_EQ(-1, NextMatchingBlock(*th_, block_of_first_e, test_string_e)); |
| |
| // Starting over gives same result |
| EXPECT_EQ(block_of_first_e, FirstMatchingBlock(*th_, hashed_e, |
| test_string_e)); |
| |
| // Add the second range to expand the result set |
| th_->AddAllBlocksThroughIndex(index_of_fourth_e - 3); |
| EXPECT_EQ(block_of_first_e, FirstMatchingBlock(*th_, hashed_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_second_e, NextMatchingBlock(*th_, block_of_first_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_third_e, NextMatchingBlock(*th_, block_of_second_e, |
| test_string_e)); |
| EXPECT_EQ(-1, NextMatchingBlock(*th_, block_of_third_e, test_string_e)); |
| |
| // Starting over gives same result |
| EXPECT_EQ(block_of_first_e, FirstMatchingBlock(*th_, hashed_e, |
| test_string_e)); |
| |
| // Add the third range to expand the result set |
| th_->AddAllBlocksThroughIndex(index_of_fourth_e + 1); |
| |
| EXPECT_EQ(block_of_first_e, FirstMatchingBlock(*th_, hashed_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_second_e, NextMatchingBlock(*th_, block_of_first_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_third_e, NextMatchingBlock(*th_, block_of_second_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_fourth_e, NextMatchingBlock(*th_, block_of_third_e, |
| test_string_e)); |
| EXPECT_EQ(-1, NextMatchingBlock(*th_, block_of_fourth_e, test_string_e)); |
| |
| // Starting over gives same result |
| EXPECT_EQ(block_of_first_e, FirstMatchingBlock(*th_, hashed_e, |
| test_string_e)); |
| } |
| |
| #ifdef GTEST_HAS_DEATH_TEST |
| TEST_F(BlockHashDeathTest, AddingRangesInDescendingOrderNoEffect) { |
| th_->AddAllBlocksThroughIndex(index_of_fourth_e + 1); |
| |
| EXPECT_EQ(block_of_first_e, FirstMatchingBlock(*th_, hashed_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_second_e, NextMatchingBlock(*th_, block_of_first_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_third_e, NextMatchingBlock(*th_, block_of_second_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_fourth_e, NextMatchingBlock(*th_, block_of_third_e, |
| test_string_e)); |
| EXPECT_EQ(-1, NextMatchingBlock(*th_, block_of_fourth_e, test_string_e)); |
| |
| // Starting over gives same result |
| EXPECT_EQ(block_of_first_e, FirstMatchingBlock(*th_, hashed_e, |
| test_string_e)); |
| |
| // These calls will produce DFATAL error messages, and will do nothing, |
| // since the ranges have already been added. |
| EXPECT_DEBUG_DEATH(th_->AddAllBlocksThroughIndex(index_of_fourth_e - 3), |
| "<"); |
| EXPECT_DEBUG_DEATH(th_->AddAllBlocksThroughIndex(index_of_first_e + 1), |
| "<"); |
| |
| EXPECT_EQ(block_of_first_e, FirstMatchingBlock(*th_, hashed_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_second_e, NextMatchingBlock(*th_, block_of_first_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_third_e, NextMatchingBlock(*th_, block_of_second_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_fourth_e, NextMatchingBlock(*th_, block_of_third_e, |
| test_string_e)); |
| EXPECT_EQ(-1, NextMatchingBlock(*th_, block_of_fourth_e, test_string_e)); |
| |
| // Starting over gives same result |
| EXPECT_EQ(block_of_first_e, FirstMatchingBlock(*th_, hashed_e, |
| test_string_e)); |
| } |
| #endif // GTEST_HAS_DEATH_TEST |
| |
| TEST_F(BlockHashTest, AddEntireRangeFindSixMatches) { |
| th_->AddAllBlocksThroughIndex(StringLengthAsInt(sample_text)); |
| EXPECT_EQ(block_of_first_e, FirstMatchingBlock(*th_, hashed_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_second_e, NextMatchingBlock(*th_, block_of_first_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_third_e, NextMatchingBlock(*th_, block_of_second_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_fourth_e, NextMatchingBlock(*th_, block_of_third_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_fifth_e, NextMatchingBlock(*th_, block_of_fourth_e, |
| test_string_e)); |
| EXPECT_EQ(block_of_sixth_e, NextMatchingBlock(*th_, block_of_fifth_e, |
| test_string_e)); |
| EXPECT_EQ(-1, NextMatchingBlock(*th_, block_of_sixth_e, test_string_e)); |
| |
| // Starting over gives same result |
| EXPECT_EQ(block_of_first_e, FirstMatchingBlock(*th_, hashed_e, |
| test_string_e)); |
| } |
| |
| TEST_F(BlockHashTest, ZeroSizeSourceAccepted) { |
| BlockHash zero_sized_hash(sample_text, 0, 0); |
| EXPECT_EQ(true, zero_sized_hash.Init(true)); |
| EXPECT_EQ(-1, FirstMatchingBlock(*th_, hashed_y, test_string_y)); |
| } |
| |
| #ifdef GTEST_HAS_DEATH_TEST |
| TEST_F(BlockHashDeathTest, BadNextMatchingBlockReturnsNoMatch) { |
| EXPECT_DEBUG_DEATH(EXPECT_EQ(-1, NextMatchingBlock(*dh_, 0xFFFFFFFE, " ")), |
| "invalid"); |
| } |
| |
| TEST_F(BlockHashDeathTest, CallingInitTwiceIsIllegal) { |
| BlockHash bh(sample_text, strlen(sample_text), 0); |
| EXPECT_TRUE(bh.Init(false)); |
| EXPECT_DEBUG_DEATH(EXPECT_FALSE(bh.Init(false)), "twice"); |
| } |
| |
| TEST_F(BlockHashDeathTest, CallingAddBlockBeforeInitIsIllegal) { |
| BlockHash bh(sample_text, strlen(sample_text), 0); |
| EXPECT_DEBUG_DEATH(bh.AddAllBlocksThroughIndex(index_of_first_e), |
| "called before"); |
| } |
| |
| TEST_F(BlockHashDeathTest, AddAllBlocksThroughIndexOutOfRange) { |
| EXPECT_DEBUG_DEATH(th_->AddAllBlocksThroughIndex(strlen(sample_text) + 1), |
| "higher than end"); |
| } |
| #endif // GTEST_HAS_DEATH_TEST |
| |
| TEST_F(BlockHashTest, UnknownFingerprintReturnsNoMatch) { |
| EXPECT_EQ(-1, FirstMatchingBlock(*dh_, 0xFAFAFAFA, "FAFA")); |
| } |
| |
| TEST_F(BlockHashTest, FindBestMatch) { |
| dh_->FindBestMatch(hashed_f, |
| &search_string[index_of_f_in_fearsome], |
| search_string, |
| strlen(search_string), |
| &best_match_); |
| EXPECT_EQ(index_of_longest_match_ear_is_fear, best_match_.source_offset()); |
| EXPECT_EQ(index_of_second_e_in_what_we_hear, best_match_.target_offset()); |
| // The match includes the spaces after the final character, |
| // which is why (kBlockSize - 1) is added to the expected best size. |
| EXPECT_EQ((strlen("ear is fear") * kBlockSize) + (kBlockSize - 1), |
| best_match_.size()); |
| } |
| |
| TEST_F(BlockHashTest, FindBestMatchWithStartingOffset) { |
| BlockHash th2(sample_text, strlen(sample_text), 0x10000); |
| th2.Init(true); // hash all blocks |
| th2.FindBestMatch(hashed_f, |
| &search_string[index_of_f_in_fearsome], |
| search_string, |
| strlen(search_string), |
| &best_match_); |
| // Offset should begin with dictionary_size |
| EXPECT_EQ(0x10000 + (index_of_longest_match_ear_is_fear), |
| best_match_.source_offset()); |
| EXPECT_EQ(index_of_second_e_in_what_we_hear, best_match_.target_offset()); |
| // The match includes the spaces after the final character, |
| // which is why (kBlockSize - 1) is added to the expected best size. |
| EXPECT_EQ((strlen("ear is fear") * kBlockSize) + (kBlockSize - 1), |
| best_match_.size()); |
| } |
| |
| TEST_F(BlockHashTest, BestMatchReachesEndOfDictionary) { |
| // Hash the "i" in "fear itself" |
| uint32_t hash_value = RollingHash<kBlockSize>::Hash( |
| &search_to_end_string[index_of_i_in_itself]); |
| dh_->FindBestMatch(hash_value, |
| &search_to_end_string[index_of_i_in_itself], |
| search_to_end_string, |
| strlen(search_to_end_string), |
| &best_match_); |
| EXPECT_EQ(index_of_space_before_itself, best_match_.source_offset()); |
| EXPECT_EQ(index_of_space_in_eat_itself, best_match_.target_offset()); |
| EXPECT_EQ(strlen(" itself") * kBlockSize, best_match_.size()); |
| } |
| |
| TEST_F(BlockHashTest, BestMatchReachesStartOfDictionary) { |
| // Hash the "i" in "fear itself" |
| uint32_t hash_value = RollingHash<kBlockSize>::Hash( |
| &search_to_beginning_string[index_of_o_in_online]); |
| dh_->FindBestMatch(hash_value, |
| &search_to_beginning_string[index_of_o_in_online], |
| search_to_beginning_string, |
| strlen(search_to_beginning_string), |
| &best_match_); |
| EXPECT_EQ(0, best_match_.source_offset()); // beginning of dictionary |
| EXPECT_EQ(index_of_t_in_use_the, best_match_.target_offset()); |
| // The match includes the spaces after the final character, |
| // which is why (kBlockSize - 1) is added to the expected best size. |
| EXPECT_EQ((strlen("The onl") * kBlockSize) + (kBlockSize - 1), |
| best_match_.size()); |
| } |
| |
| TEST_F(BlockHashTest, BestMatchWithManyMatches) { |
| BlockHash many_matches_hash(sample_text_many_matches, |
| strlen(sample_text_many_matches), |
| 0); |
| EXPECT_TRUE(many_matches_hash.Init(true)); |
| // Hash the " a" at the beginning of the search string "ababc" |
| uint32_t hash_value = |
| RollingHash<kBlockSize>::Hash(search_string_many_matches); |
| many_matches_hash.FindBestMatch(hash_value, |
| search_string_many_matches, |
| search_string_many_matches, |
| strlen(search_string_many_matches), |
| &best_match_); |
| EXPECT_EQ(index_of_ababc, best_match_.source_offset()); |
| EXPECT_EQ(0, best_match_.target_offset()); |
| EXPECT_EQ(strlen(search_string_many_matches), best_match_.size()); |
| } |
| |
| TEST_F(BlockHashTest, HashCollisionFindsNoMatch) { |
| char* collision_search_string = new char[strlen(search_string) + 1]; |
| memcpy(collision_search_string, search_string, strlen(search_string) + 1); |
| char* fearsome_location = &collision_search_string[index_of_f_in_fearsome]; |
| |
| // Tweak the collision string so that it has the same hash value |
| // but different text. The last four characters of the search string |
| // should be " f", and the bytes given below have the same hash value |
| // as those characters. |
| CHECK_GE(kBlockSize, 4); |
| fearsome_location[kBlockSize - 4] = 0x84; |
| fearsome_location[kBlockSize - 3] = 0xF1; |
| fearsome_location[kBlockSize - 2] = 0x51; |
| fearsome_location[kBlockSize - 1] = 0x00; |
| EXPECT_EQ(hashed_f, RollingHash<kBlockSize>::Hash(fearsome_location)); |
| EXPECT_NE(0, memcmp(&search_string[index_of_f_in_fearsome], |
| fearsome_location, |
| kBlockSize)); |
| // No match should be found this time. |
| dh_->FindBestMatch(hashed_f, |
| fearsome_location, |
| collision_search_string, |
| strlen(search_string), // since collision_search_string has embedded \0 |
| &best_match_); |
| EXPECT_EQ(-1, best_match_.source_offset()); |
| EXPECT_EQ(-1, best_match_.target_offset()); |
| EXPECT_EQ(0U, best_match_.size()); |
| delete[] collision_search_string; |
| } |
| |
| // If the footprint passed to FindBestMatch does not actually match |
| // the search string, it should not find any matches. |
| TEST_F(BlockHashTest, WrongFootprintFindsNoMatch) { |
| dh_->FindBestMatch(hashed_e, // Using hashed value of "e" instead of "f"! |
| &search_string[index_of_f_in_fearsome], |
| search_string, |
| strlen(search_string), |
| &best_match_); |
| EXPECT_EQ(-1, best_match_.source_offset()); |
| EXPECT_EQ(-1, best_match_.target_offset()); |
| EXPECT_EQ(0U, best_match_.size()); |
| } |
| |
| // Use a dictionary containing 1M copies of the letter 'Q', |
| // and target data that also contains 1M Qs. If FindBestMatch |
| // is not throttled to find a maximum number of matches, this |
| // will take a very long time -- several seconds at least. |
| // If this test appears to hang, it is because the throttling code |
| // (see BlockHash::kMaxMatchesToCheck for details) is not working. |
| TEST_F(BlockHashTest, SearchStringFindsTooManyMatches) { |
| const int kTestSize = 1 << 20; // 1M |
| char* huge_dictionary = new char[kTestSize]; |
| memset(huge_dictionary, 'Q', kTestSize); |
| BlockHash huge_bh(huge_dictionary, kTestSize, 0); |
| EXPECT_TRUE(huge_bh.Init(/* populate_hash_table = */ true)); |
| char* huge_target = new char[kTestSize]; |
| memset(huge_target, 'Q', kTestSize); |
| CycleTimer timer; |
| timer.Start(); |
| huge_bh.FindBestMatch(hashed_all_Qs, |
| huge_target + (kTestSize / 2), // middle of target |
| huge_target, |
| kTestSize, |
| &best_match_); |
| timer.Stop(); |
| double elapsed_time_in_us = static_cast<double>(timer.GetInUsec()); |
| std::cout << "Time to search for best match with 1M matches: " |
| << elapsed_time_in_us << " us" << std::endl; |
| // All blocks match the candidate block. FindBestMatch should have checked |
| // a certain number of matches before giving up. The best match |
| // should include at least half the source and target, since the candidate |
| // block was in the middle of the target data. |
| EXPECT_GT((kTestSize / 2), best_match_.source_offset()); |
| EXPECT_GT((kTestSize / 2), best_match_.target_offset()); |
| EXPECT_LT(static_cast<size_t>(kTestSize / 2), best_match_.size()); |
| EXPECT_GT(5000000, elapsed_time_in_us); // < 5 seconds |
| #ifdef NDEBUG |
| EXPECT_GT(1000000, elapsed_time_in_us); // < 1 second |
| #endif // NDEBUG |
| delete[] huge_target; |
| delete[] huge_dictionary; |
| } |
| |
| #ifdef GTEST_HAS_DEATH_TEST |
| TEST_F(BlockHashDeathTest, AddTooManyBlocks) { |
| for (int i = 0; i < StringLengthAsInt(sample_text_without_spaces); ++i) { |
| th_->AddOneIndexHash(i * kBlockSize, hashed_e); |
| } |
| // Didn't expect another block to be added |
| EXPECT_DEBUG_DEATH(th_->AddOneIndexHash(StringLengthAsInt(sample_text), |
| hashed_e), |
| "AddBlock"); |
| } |
| #endif // GTEST_HAS_DEATH_TEST |
| |
| } // namespace open_vcdiff |
