// Copyright 2006 Google Inc.
// Authors: Sanjay Ghemawat, Jeff Dean, 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.
//
// Implementation of the Bentley/McIlroy algorithm for finding differences.
// Bentley, McIlroy. DCC 1999. Data Compression Using Long Common Strings.
// http://citeseer.ist.psu.edu/555557.html
#ifndef OPEN_VCDIFF_BLOCKHASH_H_
#define OPEN_VCDIFF_BLOCKHASH_H_
#include <config.h>
#include <stddef.h> // size_t
#include <stdint.h> // uint32_t
#include <vector>
namespace open_vcdiff {
// A generic hash table which will be used to keep track of byte runs
// of size kBlockSize in both the incrementally processed target data
// and the preprocessed source dictionary.
//
// A custom hash table implementation is used instead of the standard
// hash_map template because we know that there will be exactly one
// entry in the BlockHash corresponding to each kBlockSize bytes
// in the source data, which makes certain optimizations possible:
// * The memory for the hash table and for all hash entries can be allocated
// in one step rather than incrementally for each insert operation.
// * A single integer can be used to represent both
// the index of the next hash entry in the chain
// and the position of the entry within the source data
// (== kBlockSize * block_number). This greatly reduces the size
// of a hash entry.
//
class BlockHash {
public:
// Block size as per Bentley/McIlroy; must be a power of two.
//
// Using (for example) kBlockSize = 4 guarantees that no match smaller
// than size 4 will be identified, that some matches having sizes
// 4, 5, or 6 may be identified, and that all matches
// having size 7 or greater will be identified (because any string of
// 7 bytes must contain a complete aligned block of 4 bytes.)
//
// Increasing kBlockSize by a factor of two will halve the amount of
// memory needed for the next block table, and will halve the setup time
// for a new BlockHash. However, it also doubles the minimum
// match length that is guaranteed to be found in FindBestMatch(),
// so that function will be less effective in finding matches.
//
// Computational effort in FindBestMatch (which is the inner loop of
// the encoding algorithm) will be proportional to the number of
// matches found, and a low value of kBlockSize will waste time
// tracking down small matches. On the other hand, if this value
// is set too high, no matches will be found at all.
//
// It is suggested that different values of kBlockSize be tried against
// a representative data set to find the best tradeoff between
// memory/CPU and the effectiveness of FindBestMatch().
//
// If you change kBlockSize to a smaller value, please increase
// kMaxMatchesToCheck accordingly.
static const int kBlockSize = 16;
// This class is used to store the best match found by FindBestMatch()
// and return it to the caller.
class Match {
public:
Match() : size_(0), source_offset_(-1), target_offset_(-1) { }
void ReplaceIfBetterMatch(size_t candidate_size,
int candidate_source_offset,
int candidate_target_offset) {
if (candidate_size > size_) {
size_ = candidate_size;
source_offset_ = candidate_source_offset;
target_offset_ = candidate_target_offset;
}
}
size_t size() const { return size_; }
int source_offset() const { return source_offset_; }
int target_offset() const { return target_offset_; }
private:
// The size of the best (longest) match passed to ReplaceIfBetterMatch().
size_t size_;
// The source offset of the match, including the starting_offset_
// of the BlockHash for which the match was found.
int source_offset_;
// The target offset of the match. An offset of 0 corresponds to the
// data at target_start, which is an argument of FindBestMatch().
int target_offset_;
// Making these private avoids implicit copy constructor
// & assignment operator
Match(const Match&); // NOLINT
void operator=(const Match&);
};
// A BlockHash is created using a buffer of source data. The hash table
// will contain one entry for each kBlockSize-byte block in the
// source data.
//
// See the comments for starting_offset_, below, for a description of
// the starting_offset argument. For a hash of source (dictionary) data,
// starting_offset_ will be zero; for a hash of previously encoded
// target data, starting_offset_ will be equal to the dictionary size.
//
BlockHash(const char* source_data, size_t source_size, int starting_offset);
~BlockHash();
// Initializes the object before use.
// This method must be called after constructing a BlockHash object,
// and before any other method may be called. This is because
// Init() dynamically allocates hash_table_ and next_block_table_.
// Returns true if initialization succeeded, or false if an error occurred,
// in which case no other method except the destructor may then be used
// on the object.
//
// If populate_hash_table is true, then AddAllBlocks() will be called
// to populate the hash table. If populate_hash_table is false, then
// classes that inherit from BlockHash are expected to call AddBlock()
// to incrementally populate individual blocks of data.
//
bool Init(bool populate_hash_table);
// In the context of the open-vcdiff encoder, BlockHash is used for two
// purposes: to hash the source (dictionary) data, and to hash
// the previously encoded target data. The main differences between
// a dictionary BlockHash and a target BlockHash are as follows:
//
// 1. The best_match->source_offset() returned from FindBestMatch()
// for a target BlockHash is computed in the following manner:
// the starting offset of the first byte in the target data
// is equal to the dictionary size. FindBestMatch() will add
// starting_offset_ to any best_match->source_offset() value it returns,
// in order to produce the correct offset value for a target BlockHash.
// 2. For a dictionary BlockHash, the entire data set is hashed at once
// when Init() is called with the parameter populate_hash_table = true.
// For a target BlockHash, because the previously encoded target data
// includes only the data seen up to the current encoding position,
// the data blocks are hashed incrementally as the encoding position
// advances, using AddOneIndexHash() and AddAllBlocksThroughIndex().
//
// The following two factory functions can be used to create BlockHash
// objects for each of these two purposes. Each factory function calls
// the object constructor and also calls Init(). If an error occurs,
// NULL is returned; otherwise a valid BlockHash object is returned.
// Since a dictionary BlockHash is not expected to be modified after
// initialization, a const object is returned.
// The caller is responsible for deleting the returned object
// (using the C++ delete operator) once it is no longer needed.
static const BlockHash* CreateDictionaryHash(const char* dictionary_data,
size_t dictionary_size);
static BlockHash* CreateTargetHash(const char* target_data,
size_t target_size,
size_t dictionary_size);
// This function will be called to add blocks incrementally to the target hash
// as the encoding position advances through the target data. It will be
// called for every kBlockSize-byte block in the target data, regardless
// of whether the block is aligned evenly on a block boundary. The
// BlockHash will only store hash entries for the evenly-aligned blocks.
//
void AddOneIndexHash(int index, uint32_t hash_value) {
if (index == NextIndexToAdd()) {
AddBlock(hash_value);
}
}
// Calls AddBlock() for each kBlockSize-byte block in the range
// (last_block_added_ * kBlockSize, end_index), exclusive of the endpoints.
// If end_index <= the last index added (last_block_added_ * kBlockSize),
// this function does nothing.
//
// A partial block beginning anywhere up to (end_index - 1) is also added,
// unless it extends outside the end of the source data. Like AddAllBlocks(),
// this function computes the hash value for each of the blocks in question
// from scratch, so it is not a good option if the hash values have already
// been computed for some other purpose.
//
// Example: assume kBlockSize = 4, last_block_added_ = 1, and there are
// 14 bytes of source data.
// If AddAllBlocksThroughIndex(9) is invoked, then it will call AddBlock()
// only for block number 2 (at index 8).
// If, after that, AddAllBlocksThroughIndex(14) is invoked, it will not call
// AddBlock() at all, because block 3 (beginning at index 12) would
// fall outside the range of source data.
//
// VCDiffEngine::Encode (in vcdiffengine.cc) uses this function to
// add a whole range of data to a target hash when a COPY instruction
// is generated.
void AddAllBlocksThroughIndex(int end_index);
// FindBestMatch takes a position within the unencoded target data
// (target_candidate_start) and the hash value of the kBlockSize bytes
// beginning at that position (hash_value). It attempts to find a matching
// set of bytes within the source (== dictionary) data, expanding
// the match both below and above the target block. It cannot expand
// the match outside the bounds of the source data, or below
// target_start within the target data, or past
// the end limit of (target_start + target_length).
//
// target_candidate_start is the start of the candidate block within the
// target data for which a match will be sought, while
// target_start (which is <= target_candidate_start)
// is the start of the target data that has yet to be encoded.
//
// If a match is found whose size is greater than the size
// of best_match, this function populates *best_match with the
// size, source_offset, and target_offset of the match found.
// best_match->source_offset() will contain the index of the start of the
// matching source data, plus starting_offset_
// (see description of starting_offset_ for details);
// best_match->target_offset() will contain the offset of the match
// beginning with target_start = offset 0, such that
// 0 <= best_match->target_offset()
// <= (target_candidate_start - target_start);
// and best_match->size() will contain the size of the match.
// If no such match is found, this function leaves *best_match unmodified.
//
// On calling FindBestMatch(), best_match must
// point to a valid Match object, and cannot be NULL.
// The same Match object can be passed
// when calling FindBestMatch() on a different BlockHash object
// for the same candidate data block, in order to find
// the best match possible across both objects. For example:
//
// open_vcdiff::BlockHash::Match best_match;
// uint32_t hash_value =
// RollingHash<BlockHash::kBlockSize>::Hash(target_candidate_start);
// bh1.FindBestMatch(hash_value,
// target_candidate_start,
// target_start,
// target_length,
// &best_match);
// bh2.FindBestMatch(hash_value,
// target_candidate_start,
// target_start,
// target_length,
// &best_match);
// if (best_size >= 0) {
// // a match was found; its size, source offset, and target offset
// // can be found in best_match
// }
//
// hash_value is passed as a separate parameter from target_candidate_start,
// (rather than calculated within FindBestMatch) in order to take
// advantage of the rolling hash, which quickly calculates the hash value
// of the block starting at target_candidate_start based on
// the known hash value of the block starting at (target_candidate_start - 1).
// See vcdiffengine.cc for more details.
//
// Example:
// kBlockSize: 4
// target text: "ANDREW LLOYD WEBBER"
// 1^ 5^2^ 3^
// dictionary: "INSURANCE : LLOYDS OF LONDON"
// 4^
// hashed dictionary blocks:
// "INSU", "RANC", "E : ", "LLOY", "DS O", "F LON"
//
// 1: target_start (beginning of unencoded data)
// 2: target_candidate_start (for the block "LLOY")
// 3: target_length (points one byte beyond the last byte of data.)
// 4: best_match->source_offset() (after calling FindBestMatch)
// 5: best_match->target_offset() (after calling FindBestMatch)
//
// Under these conditions, FindBestMatch will find a matching
// hashed dictionary block for "LLOY", and will extend the beginning of
// this match backwards by one byte, and the end of the match forwards
// by one byte, finding that the best match is " LLOYD"
// with best_match->source_offset() = 10
// (offset of " LLOYD" in the source string),
// best_match->target_offset() = 6
// (offset of " LLOYD" in the target string),
// and best_match->size() = 6.
//
void FindBestMatch(uint32_t hash_value,
const char* target_candidate_start,
const char* target_start,
size_t target_size,
Match* best_match) const;
protected:
// FindBestMatch() will not process more than this number
// of matching hash entries.
//
// It is necessary to have a limit on the maximum number of matches
// that will be checked in order to avoid the worst-case performance
// possible if, for example, all the blocks in the dictionary have
// the same hash value. See the unit test SearchStringFindsTooManyMatches
// for an example of such a case. The encoder uses a loop in
// VCDiffEngine::Encode over each target byte, containing a loop in
// BlockHash::FindBestMatch over the number of matches (up to a maximum
// of the number of source blocks), containing two loops that extend
// the match forwards and backwards up to the number of source bytes.
// Total complexity in the worst case is
// O([target size] * source_size_ * source_size_)
// Placing a limit on the possible number of matches checked changes this to
// O([target size] * source_size_ * kMaxMatchesToCheck)
//
// In empirical testing on real HTML text, using a block size of 4,
// the number of true matches per call to FindBestMatch() did not exceed 78;
// with a block size of 32, the number of matches did not exceed 3.
//
// The expected number of true matches scales super-linearly
// with the inverse of kBlockSize, but here a linear scale is used
// for block sizes smaller than 32.
static const int kMaxMatchesToCheck = (kBlockSize >= 32) ? 32 :
(32 * (32 / kBlockSize));
// Do not skip more than this number of non-matching hash collisions
// to find the next matching entry in the hash chain.
static const int kMaxProbes = 16;
// Internal routine which calculates a hash table size based on kBlockSize and
// the dictionary_size. Will return a power of two if successful, or 0 if an
// internal error occurs. Some calculations (such as GetHashTableIndex())
// depend on the table size being a power of two.
static size_t CalcTableSize(const size_t dictionary_size);
size_t GetNumberOfBlocks() const {
return source_size_ / kBlockSize;
}
// Use the lowest-order bits of the hash value
// as the index into the hash table.
uint32_t GetHashTableIndex(uint32_t hash_value) const {
return hash_value & hash_table_mask_;
}
// The index within source_data_ of the next block
// for which AddBlock() should be called.
int NextIndexToAdd() const {
return (last_block_added_ + 1) * kBlockSize;
}
static inline bool TooManyMatches(int* match_counter);
const char* source_data() { return source_data_; }
size_t source_size() { return source_size_; }
// Adds an entry to the hash table for one block of source data of length
// kBlockSize, starting at source_data_[block_number * kBlockSize],
// where block_number is always (last_block_added_ + 1). That is,
// AddBlock() must be called once for each block in source_data_
// in increasing order.
void AddBlock(uint32_t hash_value);
// Calls AddBlock() for each complete kBlockSize-byte block between
// source_data_ and (source_data_ + source_size_). It is equivalent
// to calling AddAllBlocksThroughIndex(source_data + source_size).
// This function is called when Init(true) is invoked.
void AddAllBlocks();
// Returns true if the contents of the kBlockSize-byte block
// beginning at block1 are identical to the contents of
// the block beginning at block2; false otherwise.
static bool BlockContentsMatch(const char* block1, const char* block2);
// Compares each machine word of the two (possibly unaligned) blocks, rather
// than each byte, thus reducing the number of test-and-branch instructions
// executed. Returns a boolean (do the blocks match?) rather than
// the signed byte difference returned by memcmp.
//
// BlockContentsMatch will use either this function or memcmp to do its work,
// depending on which is faster for a particular architecture.
//
// For gcc on x86-based architectures, this function has been shown to run
// about twice as fast as the library function memcmp(), and between five and
// nine times faster than the assembly instructions (repz and cmpsb) that gcc
// uses by default for builtin memcmp. On other architectures, or using
// other compilers, this function has not shown to be faster than memcmp.
static bool BlockCompareWords(const char* block1, const char* block2);
// Finds the first block number within the hashed data
// that represents a match for the given hash value.
// Returns -1 if no match was found.
//
// 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.
//
// The hash table is initially populated with -1 (not found) values,
// so if this function is called before the hash table has been populated
// using AddAllBlocks() or AddBlock(), it will simply return -1
// for any value of hash_value.
int FirstMatchingBlock(uint32_t hash_value, const char* block_ptr) const;
// Given a block number returned by FirstMatchingBlock()
// or by a previous call to NextMatchingBlock(), returns
// the next block number that matches the same hash value.
// Returns -1 if no match was found.
int NextMatchingBlock(int block_number, const char* block_ptr) const;
// Inline version of FirstMatchingBlock. This saves the cost of a function
// call when this routine is called from within the module. The external
// (non-inlined) version is called only by unit tests.
inline int FirstMatchingBlockInline(uint32_t hash_value,
const char* block_ptr) const;
// Walk through the hash entry chain, skipping over any false matches
// (for which the lowest bits of the fingerprints match,
// but the actual block data does not.) Returns the block number of
// the first true match found, or -1 if no true match was found.
// If block_number is a matching block, the function will return block_number
// without skipping to the next block.
int SkipNonMatchingBlocks(int block_number, const char* block_ptr) const;
// 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.
static int MatchingBytesToLeft(const char* source_match_start,
const char* target_match_start,
int max_bytes);
// 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.
static int MatchingBytesToRight(const char* source_match_end,
const char* target_match_end,
int max_bytes);
// The protected functions BlockContentsMatch, FirstMatchingBlock,
// NextMatchingBlock, MatchingBytesToLeft, and MatchingBytesToRight
// should be made accessible to unit tests.
friend class BlockHashTest;
private:
const char* const source_data_;
const size_t source_size_;
// The size of this array is determined using CalcTableSize(). It has at
// least one element for each kBlockSize-byte block in the source data.
// GetHashTableIndex() returns an index into this table for a given hash
// value. The value of each element of hash_table_ is the lowest block
// number in the source data whose hash value would return the same value from
// GetHashTableIndex(), or -1 if there is no matching block. This value can
// then be used as an index into next_block_table_ to retrieve the entire set
// of matching block numbers.
std::vector<int> hash_table_;
// An array containing one element for each source block. Each element is
// either -1 (== not found) or the index of the next block whose hash value
// would produce a matching result from GetHashTableIndex().
std::vector<int> next_block_table_;
// This vector has the same size as next_block_table_. For every block number
// B that is referenced in hash_table_, last_block_table_[B] will contain
// the maximum block number that has the same GetHashTableIndex() value
// as block B. This number may be B itself. For a block number B' that
// is not referenced in hash_table_, the value of last_block_table_[B'] is -1.
// This table is used only while populating the hash table, not while looking
// up hash values in the table. Keeping track of the last block number in the
// chain allows us to construct the block chains as FIFO rather than LIFO
// lists, so that the match with the lowest index is returned first. This
// should result in a more compact encoding because the VCDIFF format favors
// smaller index values and repeated index values.
std::vector<int> last_block_table_;
// Performing a bitwise AND with hash_table_mask_ will produce a value ranging
// from 0 to the number of elements in hash_table_.
uint32_t hash_table_mask_;
// The offset of the first byte of source data (the data at source_data_[0]).
// For the purpose of computing offsets, the source data and target data
// are considered to be concatenated -- not literally in a single memory
// buffer, but conceptually as described in the RFC.
// The first byte of the previously encoded target data
// has an offset that is equal to dictionary_size, i.e., just after
// the last byte of source data.
// For a hash of source (dictionary) data, starting_offset_ will be zero;
// for a hash of previously encoded target data, starting_offset_ will be
// equal to the dictionary size.
const int starting_offset_;
// The last index added by AddBlock(). This determines the block number
// for successive calls to AddBlock(), and is also
// used to determine the starting block for AddAllBlocksThroughIndex().
int last_block_added_;
// Making these private avoids implicit copy constructor & assignment operator
BlockHash(const BlockHash&); // NOLINT
void operator=(const BlockHash&);
};
} // namespace open_vcdiff
#endif // OPEN_VCDIFF_BLOCKHASH_H_