| // Copyright 2006, 2008 Google Inc. |
| // Authors: Chandra Chereddi, 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 "compile_assert.h" |
| #include <stdint.h> // uint32_t |
| #include <string.h> // memcpy, memcmp |
| #include "logging.h" |
| #include "rolling_hash.h" |
| |
| namespace open_vcdiff { |
| |
| typedef unsigned long uword_t; // a machine word NOLINT |
| |
| BlockHash::BlockHash(const char* source_data, |
| size_t source_size, |
| int starting_offset) |
| : source_data_(source_data), |
| source_size_(source_size), |
| hash_table_mask_(0), |
| starting_offset_(starting_offset), |
| last_block_added_(-1) { |
| } |
| |
| BlockHash::~BlockHash() { } |
| |
| // kBlockSize must be at least 2 to be meaningful. Since it's a compile-time |
| // constant, check its value at compile time rather than wasting CPU cycles |
| // on runtime checks. |
| COMPILE_ASSERT(BlockHash::kBlockSize >= 2, kBlockSize_must_be_at_least_2); |
| |
| // kBlockSize is required to be a power of 2 because multiplication |
| // (n * kBlockSize), division (n / kBlockSize) and MOD (n % kBlockSize) |
| // are commonly-used operations. If kBlockSize is a compile-time |
| // constant and a power of 2, the compiler can convert these three operations |
| // into bit-shift (>> or <<) and bitwise-AND (&) operations, which are much |
| // more efficient than executing full integer multiply, divide, or remainder |
| // instructions. |
| COMPILE_ASSERT((BlockHash::kBlockSize & (BlockHash::kBlockSize - 1)) == 0, |
| kBlockSize_must_be_a_power_of_2); |
| |
| bool BlockHash::Init(bool populate_hash_table) { |
| if (!hash_table_.empty() || |
| !next_block_table_.empty() || |
| !last_block_table_.empty()) { |
| LOG(DFATAL) << "Init() called twice for same BlockHash object" << LOG_ENDL; |
| return false; |
| } |
| const size_t table_size = CalcTableSize(source_size_); |
| if (table_size == 0) { |
| LOG(DFATAL) << "Error finding table size for source size " << source_size_ |
| << LOG_ENDL; |
| return false; |
| } |
| // Since table_size is a power of 2, (table_size - 1) is a bit mask |
| // containing all the bits below table_size. |
| hash_table_mask_ = static_cast<uint32_t>(table_size - 1); |
| hash_table_.resize(table_size, -1); |
| next_block_table_.resize(GetNumberOfBlocks(), -1); |
| last_block_table_.resize(GetNumberOfBlocks(), -1); |
| if (populate_hash_table) { |
| AddAllBlocks(); |
| } |
| return true; |
| } |
| |
| const BlockHash* BlockHash::CreateDictionaryHash(const char* dictionary_data, |
| size_t dictionary_size) { |
| BlockHash* new_dictionary_hash = new BlockHash(dictionary_data, |
| dictionary_size, |
| 0); |
| if (!new_dictionary_hash->Init(/* populate_hash_table = */ true)) { |
| delete new_dictionary_hash; |
| return NULL; |
| } else { |
| return new_dictionary_hash; |
| } |
| } |
| |
| BlockHash* BlockHash::CreateTargetHash(const char* target_data, |
| size_t target_size, |
| size_t dictionary_size) { |
| BlockHash* new_target_hash = new BlockHash(target_data, |
| target_size, |
| static_cast<int>(dictionary_size)); |
| if (!new_target_hash->Init(/* populate_hash_table = */ false)) { |
| delete new_target_hash; |
| return NULL; |
| } else { |
| return new_target_hash; |
| } |
| } |
| |
| // Returns zero if an error occurs. |
| size_t BlockHash::CalcTableSize(const size_t dictionary_size) { |
| // Overallocate the hash table by making it the same size (in bytes) |
| // as the source data. This is a trade-off between space and time: |
| // the empty entries in the hash table will reduce the |
| // probability of a hash collision to (sizeof(int) / kblockSize), |
| // and so save time comparing false matches. |
| const size_t min_size = (dictionary_size / sizeof(int)) + 1; // NOLINT |
| size_t table_size = 1; |
| // Find the smallest power of 2 that is >= min_size, and assign |
| // that value to table_size. |
| while (table_size < min_size) { |
| table_size <<= 1; |
| // Guard against an infinite loop |
| if (table_size <= 0) { |
| LOG(DFATAL) << "Internal error: CalcTableSize(dictionary_size = " |
| << dictionary_size |
| << "): resulting table_size " << table_size |
| << " is zero or negative" << LOG_ENDL; |
| return 0; |
| } |
| } |
| // Check size sanity |
| if ((table_size & (table_size - 1)) != 0) { |
| LOG(DFATAL) << "Internal error: CalcTableSize(dictionary_size = " |
| << dictionary_size |
| << "): resulting table_size " << table_size |
| << " is not a power of 2" << LOG_ENDL; |
| return 0; |
| } |
| // The loop above tries to find the smallest power of 2 that is >= min_size. |
| // That value must lie somewhere between min_size and (min_size * 2), |
| // except for the case (dictionary_size == 0, table_size == 1). |
| if ((dictionary_size > 0) && (table_size > (min_size * 2))) { |
| LOG(DFATAL) << "Internal error: CalcTableSize(dictionary_size = " |
| << dictionary_size |
| << "): resulting table_size " << table_size |
| << " is too large" << LOG_ENDL; |
| return 0; |
| } |
| return table_size; |
| } |
| |
| // If the hash value is already available from the rolling hash, |
| // call this function to save time. |
| void BlockHash::AddBlock(uint32_t hash_value) { |
| if (hash_table_.empty()) { |
| LOG(DFATAL) << "BlockHash::AddBlock() called before BlockHash::Init()" |
| << LOG_ENDL; |
| return; |
| } |
| // The initial value of last_block_added_ is -1. |
| int block_number = last_block_added_ + 1; |
| const int total_blocks = |
| static_cast<int>(source_size_ / kBlockSize); // round down |
| if (block_number >= total_blocks) { |
| LOG(DFATAL) << "BlockHash::AddBlock() called" |
| " with block number " << block_number |
| << " that is past last block " << (total_blocks - 1) |
| << LOG_ENDL; |
| return; |
| } |
| if (next_block_table_[block_number] != -1) { |
| LOG(DFATAL) << "Internal error in BlockHash::AddBlock(): " |
| "block number = " << block_number |
| << ", next block should be -1 but is " |
| << next_block_table_[block_number] << LOG_ENDL; |
| return; |
| } |
| const uint32_t hash_table_index = GetHashTableIndex(hash_value); |
| const int first_matching_block = hash_table_[hash_table_index]; |
| if (first_matching_block < 0) { |
| // This is the first entry with this hash value |
| hash_table_[hash_table_index] = block_number; |
| last_block_table_[block_number] = block_number; |
| } else { |
| // Add this entry at the end of the chain of matching blocks |
| const int last_matching_block = last_block_table_[first_matching_block]; |
| if (next_block_table_[last_matching_block] != -1) { |
| LOG(DFATAL) << "Internal error in BlockHash::AddBlock(): " |
| "first matching block = " << first_matching_block |
| << ", last matching block = " << last_matching_block |
| << ", next block should be -1 but is " |
| << next_block_table_[last_matching_block] << LOG_ENDL; |
| return; |
| } |
| next_block_table_[last_matching_block] = block_number; |
| last_block_table_[first_matching_block] = block_number; |
| } |
| last_block_added_ = block_number; |
| } |
| |
| void BlockHash::AddAllBlocks() { |
| AddAllBlocksThroughIndex(static_cast<int>(source_size_)); |
| } |
| |
| void BlockHash::AddAllBlocksThroughIndex(int end_index) { |
| if (end_index > static_cast<int>(source_size_)) { |
| LOG(DFATAL) << "BlockHash::AddAllBlocksThroughIndex() called" |
| " with index " << end_index |
| << " higher than end index " << source_size_ << LOG_ENDL; |
| return; |
| } |
| const int last_index_added = last_block_added_ * kBlockSize; |
| if (end_index <= last_index_added) { |
| LOG(DFATAL) << "BlockHash::AddAllBlocksThroughIndex() called" |
| " with index " << end_index |
| << " <= last index added ( " << last_index_added |
| << ")" << LOG_ENDL; |
| return; |
| } |
| int end_limit = end_index; |
| // Don't allow reading any indices at or past source_size_. |
| // The Hash function extends (kBlockSize - 1) bytes past the index, |
| // so leave a margin of that size. |
| int last_legal_hash_index = static_cast<int>(source_size() - kBlockSize); |
| if (end_limit > last_legal_hash_index) { |
| end_limit = last_legal_hash_index + 1; |
| } |
| const char* block_ptr = source_data() + NextIndexToAdd(); |
| const char* const end_ptr = source_data() + end_limit; |
| while (block_ptr < end_ptr) { |
| AddBlock(RollingHash<kBlockSize>::Hash(block_ptr)); |
| block_ptr += kBlockSize; |
| } |
| } |
| |
| COMPILE_ASSERT((BlockHash::kBlockSize % sizeof(uword_t)) == 0, |
| kBlockSize_must_be_a_multiple_of_machine_word_size); |
| |
| // A recursive template to compare a fixed number |
| // of (possibly unaligned) machine words starting |
| // at addresses block1 and block2. Returns true or false |
| // depending on whether an exact match was found. |
| template<int number_of_words> |
| inline bool CompareWholeWordValues(const char* block1, |
| const char* block2) { |
| return CompareWholeWordValues<1>(block1, block2) && |
| CompareWholeWordValues<number_of_words - 1>(block1 + sizeof(uword_t), |
| block2 + sizeof(uword_t)); |
| } |
| |
| // The base of the recursive template: compare one pair of machine words. |
| template<> |
| inline bool CompareWholeWordValues<1>(const char* word1, |
| const char* word2) { |
| uword_t aligned_word1, aligned_word2; |
| memcpy(&aligned_word1, word1, sizeof(aligned_word1)); |
| memcpy(&aligned_word2, word2, sizeof(aligned_word2)); |
| return aligned_word1 == aligned_word2; |
| } |
| |
| // A block must be composed of an integral number of machine words |
| // (uword_t values.) This function takes advantage of that fact |
| // by comparing the blocks as series of (possibly unaligned) word values. |
| // A word-sized comparison can be performed as a single |
| // machine instruction. Comparing words instead of bytes means that, |
| // on a 64-bit platform, this function will use 8 times fewer test-and-branch |
| // instructions than a byte-by-byte comparison. Even with the extra |
| // cost of the calls to memcpy, this method is still at least twice as fast |
| // as memcmp (measured using gcc on a 64-bit platform, with a block size |
| // of 32.) For blocks with identical contents (a common case), this method |
| // is over six times faster than memcmp. |
| inline bool BlockCompareWordsInline(const char* block1, const char* block2) { |
| static const size_t kWordsPerBlock = BlockHash::kBlockSize / sizeof(uword_t); |
| return CompareWholeWordValues<kWordsPerBlock>(block1, block2); |
| } |
| |
| bool BlockHash::BlockCompareWords(const char* block1, const char* block2) { |
| return BlockCompareWordsInline(block1, block2); |
| } |
| |
| inline bool BlockContentsMatchInline(const char* block1, const char* block2) { |
| // Optimize for mismatch in first byte. Since this function is called only |
| // when the hash values of the two blocks match, it is very likely that either |
| // the blocks are identical, or else the first byte does not match. |
| if (*block1 != *block2) { |
| return false; |
| } |
| #ifdef VCDIFF_USE_BLOCK_COMPARE_WORDS |
| return BlockCompareWordsInline(block1, block2); |
| #else // !VCDIFF_USE_BLOCK_COMPARE_WORDS |
| return memcmp(block1, block2, BlockHash::kBlockSize) == 0; |
| #endif // VCDIFF_USE_BLOCK_COMPARE_WORDS |
| } |
| |
| bool BlockHash::BlockContentsMatch(const char* block1, const char* block2) { |
| return BlockContentsMatchInline(block1, block2); |
| } |
| |
| inline int BlockHash::SkipNonMatchingBlocks(int block_number, |
| const char* block_ptr) const { |
| int probes = 0; |
| while ((block_number >= 0) && |
| !BlockContentsMatchInline(block_ptr, |
| &source_data_[block_number * kBlockSize])) { |
| if (++probes > kMaxProbes) { |
| return -1; // Avoid too much chaining |
| } |
| block_number = next_block_table_[block_number]; |
| } |
| return block_number; |
| } |
| |
| // Init() must have been called and returned true before using |
| // FirstMatchingBlock or NextMatchingBlock. No check is performed |
| // for this condition; the code will crash if this condition is violated. |
| inline int BlockHash::FirstMatchingBlockInline(uint32_t hash_value, |
| const char* block_ptr) const { |
| return SkipNonMatchingBlocks(hash_table_[GetHashTableIndex(hash_value)], |
| block_ptr); |
| } |
| |
| int BlockHash::FirstMatchingBlock(uint32_t hash_value, |
| const char* block_ptr) const { |
| return FirstMatchingBlockInline(hash_value, block_ptr); |
| } |
| |
| int BlockHash::NextMatchingBlock(int block_number, |
| const char* block_ptr) const { |
| if (static_cast<size_t>(block_number) >= GetNumberOfBlocks()) { |
| LOG(DFATAL) << "NextMatchingBlock called for invalid block number " |
| << block_number << LOG_ENDL; |
| return -1; |
| } |
| return SkipNonMatchingBlocks(next_block_table_[block_number], block_ptr); |
| } |
| |
| // Keep a count of the number of matches found. This will throttle the |
| // number of iterations in FindBestMatch. For example, if the entire |
| // dictionary is made up of spaces (' ') and the search string is also |
| // made up of spaces, there will be one match for each block in the |
| // dictionary. |
| inline bool BlockHash::TooManyMatches(int* match_counter) { |
| ++(*match_counter); |
| return (*match_counter) > kMaxMatchesToCheck; |
| } |
| |
| // Returns the number of bytes to the left of source_match_start |
| // that match the corresponding bytes to the left of target_match_start. |
| // Will not examine more than max_bytes bytes, which is to say that |
| // the return value will be in the range [0, max_bytes] inclusive. |
| int BlockHash::MatchingBytesToLeft(const char* source_match_start, |
| const char* target_match_start, |
| int max_bytes) { |
| const char* source_ptr = source_match_start; |
| const char* target_ptr = target_match_start; |
| int bytes_found = 0; |
| while (bytes_found < max_bytes) { |
| --source_ptr; |
| --target_ptr; |
| if (*source_ptr != *target_ptr) { |
| break; |
| } |
| ++bytes_found; |
| } |
| return bytes_found; |
| } |
| |
| // Returns the number of bytes starting at source_match_end |
| // that match the corresponding bytes starting at target_match_end. |
| // Will not examine more than max_bytes bytes, which is to say that |
| // the return value will be in the range [0, max_bytes] inclusive. |
| int BlockHash::MatchingBytesToRight(const char* source_match_end, |
| const char* target_match_end, |
| int max_bytes) { |
| const char* source_ptr = source_match_end; |
| const char* target_ptr = target_match_end; |
| int bytes_found = 0; |
| while ((bytes_found < max_bytes) && (*source_ptr == *target_ptr)) { |
| ++bytes_found; |
| ++source_ptr; |
| ++target_ptr; |
| } |
| return bytes_found; |
| } |
| |
| // No NULL checks are performed on the pointer arguments. The caller |
| // must guarantee that none of the arguments is NULL, or a crash will occur. |
| // |
| // The vast majority of calls to FindBestMatch enter the loop *zero* times, |
| // which is to say that most candidate blocks find no matches in the dictionary. |
| // The important sections for optimization are therefore the code outside the |
| // loop and the code within the loop conditions. Keep this to a minimum. |
| void BlockHash::FindBestMatch(uint32_t hash_value, |
| const char* target_candidate_start, |
| const char* target_start, |
| size_t target_size, |
| Match* best_match) const { |
| int match_counter = 0; |
| for (int block_number = FirstMatchingBlockInline(hash_value, |
| target_candidate_start); |
| (block_number >= 0) && !TooManyMatches(&match_counter); |
| block_number = NextMatchingBlock(block_number, target_candidate_start)) { |
| int source_match_offset = block_number * kBlockSize; |
| const int source_match_end = source_match_offset + kBlockSize; |
| |
| int target_match_offset = |
| static_cast<int>(target_candidate_start - target_start); |
| const int target_match_end = target_match_offset + kBlockSize; |
| |
| size_t match_size = kBlockSize; |
| { |
| // Extend match start towards beginning of unencoded data |
| const int limit_bytes_to_left = std::min(source_match_offset, |
| target_match_offset); |
| const int matching_bytes_to_left = |
| MatchingBytesToLeft(source_data_ + source_match_offset, |
| target_start + target_match_offset, |
| limit_bytes_to_left); |
| source_match_offset -= matching_bytes_to_left; |
| target_match_offset -= matching_bytes_to_left; |
| match_size += matching_bytes_to_left; |
| } |
| { |
| // Extend match end towards end of unencoded data |
| const size_t source_bytes_to_right = source_size_ - source_match_end; |
| const size_t target_bytes_to_right = target_size - target_match_end; |
| const size_t limit_bytes_to_right = std::min(source_bytes_to_right, |
| target_bytes_to_right); |
| match_size += |
| MatchingBytesToRight(source_data_ + source_match_end, |
| target_start + target_match_end, |
| static_cast<int>(limit_bytes_to_right)); |
| } |
| // Update in/out parameter if the best match found was better |
| // than any match already stored in *best_match. |
| best_match->ReplaceIfBetterMatch(match_size, |
| source_match_offset + starting_offset_, |
| target_match_offset); |
| } |
| } |
| |
| } // namespace open_vcdiff |
