1c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Copyright 2006, 2008 Google Inc. 2c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Authors: Chandra Chereddi, Lincoln Smith 3c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 4c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Licensed under the Apache License, Version 2.0 (the "License"); 5c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// you may not use this file except in compliance with the License. 6c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// You may obtain a copy of the License at 7c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 8c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// http://www.apache.org/licenses/LICENSE-2.0 9c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 10c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Unless required by applicable law or agreed to in writing, software 11c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// distributed under the License is distributed on an "AS IS" BASIS, 12c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// See the License for the specific language governing permissions and 14c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// limitations under the License. 15c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 16c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include <config.h> 17c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "vcdiffengine.h" 18c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include <stdint.h> // uint32_t 19c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include <string.h> // memcpy 20c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "blockhash.h" 21c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "codetablewriter_interface.h" 22c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "logging.h" 23c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "rolling_hash.h" 24c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 25c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottnamespace open_vcdiff { 26c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 27c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottVCDiffEngine::VCDiffEngine(const char* dictionary, size_t dictionary_size) 28c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // If dictionary_size == 0, then dictionary could be NULL. Guard against 29c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // using a NULL value. 30c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott : dictionary_((dictionary_size > 0) ? new char[dictionary_size] : ""), 31c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott dictionary_size_(dictionary_size), 32c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott hashed_dictionary_(NULL) { 33c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (dictionary_size > 0) { 34c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott memcpy(const_cast<char*>(dictionary_), dictionary, dictionary_size); 35c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 36c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 37c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 38c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottVCDiffEngine::~VCDiffEngine() { 39c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott delete hashed_dictionary_; 40c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (dictionary_size_ > 0) { 41c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott delete[] dictionary_; 42c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 43c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 44c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 45c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottbool VCDiffEngine::Init() { 46c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (hashed_dictionary_) { 47c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott LOG(DFATAL) << "Init() called twice for same VCDiffEngine object" 48c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott << LOG_ENDL; 49c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 50c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 51c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott hashed_dictionary_ = BlockHash::CreateDictionaryHash(dictionary_, 52c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott dictionary_size()); 53c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!hashed_dictionary_) { 54c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott LOG(DFATAL) << "Creation of dictionary hash failed" << LOG_ENDL; 55c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 56c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 57c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!RollingHash<BlockHash::kBlockSize>::Init()) { 58c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott LOG(DFATAL) << "RollingHash initialization failed" << LOG_ENDL; 59c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 60c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 61c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 62c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 63c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 64c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// This helper function tries to find an appropriate match within 65c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// hashed_dictionary_ for the block starting at the current target position. 66c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// If target_hash is not NULL, this function will also look for a match 67c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// within the previously encoded target data. 68c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 69c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// If a match is found, this function will generate an ADD instruction 70c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// for all unencoded data that precedes the match, 71c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// and a COPY instruction for the match itself; then it returns 72c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// the number of bytes processed by both instructions, 73c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// which is guaranteed to be > 0. 74c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// If no appropriate match is found, the function returns 0. 75c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 76c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// The first four parameters are input parameters which are passed 77c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// directly to BlockHash::FindBestMatch; please see that function 78c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// for a description of their allowable values. 79c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scotttemplate<bool look_for_target_matches> 80c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottinline size_t VCDiffEngine::EncodeCopyForBestMatch( 81c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint32_t hash_value, 82c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const char* target_candidate_start, 83c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const char* unencoded_target_start, 84c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott size_t unencoded_target_size, 85c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const BlockHash* target_hash, 86c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CodeTableWriterInterface* coder) const { 87c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // When FindBestMatch() comes up with a match for a candidate block, 88c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // it will populate best_match with the size, source offset, 89c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // and target offset of the match. 90c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott BlockHash::Match best_match; 91c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 92c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // First look for a match in the dictionary. 93c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott hashed_dictionary_->FindBestMatch(hash_value, 94c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott target_candidate_start, 95c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unencoded_target_start, 96c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unencoded_target_size, 97c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott &best_match); 98c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // If target matching is enabled, then see if there is a better match 99c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // within the target data that has been encoded so far. 100c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (look_for_target_matches) { 101c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott target_hash->FindBestMatch(hash_value, 102c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott target_candidate_start, 103c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unencoded_target_start, 104c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unencoded_target_size, 105c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott &best_match); 106c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 107c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!ShouldGenerateCopyInstructionForMatchOfSize(best_match.size())) { 108c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return 0; 109c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 110c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (best_match.target_offset() > 0) { 111c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Create an ADD instruction to encode all target bytes 112c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // from the end of the last COPY match, if any, up to 113c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // the beginning of this COPY match. 114c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott coder->Add(unencoded_target_start, best_match.target_offset()); 115c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 116c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott coder->Copy(best_match.source_offset(), best_match.size()); 117c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return best_match.target_offset() // ADD size 118c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott + best_match.size(); // + COPY size 119c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 120c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 121c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Once the encoder loop has finished checking for matches in the target data, 122c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// this function creates an ADD instruction to encode all target bytes 123c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// from the end of the last COPY match, if any, through the end of 124c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// the target data. In the worst case, if no matches were found at all, 125c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// this function will create one big ADD instruction 126c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// for the entire buffer of target data. 127c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottinline void VCDiffEngine::AddUnmatchedRemainder( 128c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const char* unencoded_target_start, 129c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott size_t unencoded_target_size, 130c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CodeTableWriterInterface* coder) const { 131c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (unencoded_target_size > 0) { 132c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott coder->Add(unencoded_target_start, unencoded_target_size); 133c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 134c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 135c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 136c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// This helper function tells the coder to finish the encoding and write 137c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// the results into the output string "diff". 138c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottinline void VCDiffEngine::FinishEncoding( 139c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott size_t target_size, 140c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott OutputStringInterface* diff, 141c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CodeTableWriterInterface* coder) const { 142c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (target_size != static_cast<size_t>(coder->target_length())) { 143c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott LOG(DFATAL) << "Internal error in VCDiffEngine::Encode: " 144c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott "original target size (" << target_size 145c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott << ") does not match number of bytes processed (" 146c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott << coder->target_length() << ")" << LOG_ENDL; 147c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 148c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott coder->Output(diff); 149c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 150c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 151c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scotttemplate<bool look_for_target_matches> 152c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid VCDiffEngine::EncodeInternal(const char* target_data, 153c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott size_t target_size, 154c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott OutputStringInterface* diff, 155c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CodeTableWriterInterface* coder) const { 156c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!hashed_dictionary_) { 157c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott LOG(DFATAL) << "Internal error: VCDiffEngine::Encode() " 158c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott "called before VCDiffEngine::Init()" << LOG_ENDL; 159c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 160c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 161c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (target_size == 0) { 162c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; // Do nothing for empty target 163c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 164c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Special case for really small input 165c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (target_size < static_cast<size_t>(BlockHash::kBlockSize)) { 166c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott AddUnmatchedRemainder(target_data, target_size, coder); 167c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott FinishEncoding(target_size, diff, coder); 168c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 169c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 170c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott RollingHash<BlockHash::kBlockSize> hasher; 171c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott BlockHash* target_hash = NULL; 172c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (look_for_target_matches) { 173c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Check matches against previously encoded target data 174c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // in this same target window, as well as against the dictionary 175c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott target_hash = BlockHash::CreateTargetHash(target_data, 176c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott target_size, 177c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott dictionary_size()); 178c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!target_hash) { 179c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott LOG(DFATAL) << "Instantiation of target hash failed" << LOG_ENDL; 180c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 181c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 182c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 183c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const char* const target_end = target_data + target_size; 184c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const char* const start_of_last_block = target_end - BlockHash::kBlockSize; 185c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Offset of next bytes in string to ADD if NOT copied (i.e., not found in 186c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // dictionary) 187c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const char* next_encode = target_data; 188c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // candidate_pos points to the start of the kBlockSize-byte block that may 189c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // begin a match with the dictionary or previously encoded target data. 190c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const char* candidate_pos = target_data; 191c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint32_t hash_value = hasher.Hash(candidate_pos); 192c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott while (1) { 193c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const size_t bytes_encoded = 194c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EncodeCopyForBestMatch<look_for_target_matches>( 195c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott hash_value, 196c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott candidate_pos, 197c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next_encode, 198c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott (target_end - next_encode), 199c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott target_hash, 200c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott coder); 201c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (bytes_encoded > 0) { 202c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next_encode += bytes_encoded; // Advance past COPYed data 203c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott candidate_pos = next_encode; 204c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (candidate_pos > start_of_last_block) { 205c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; // Reached end of target data 206c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 207c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // candidate_pos has jumped ahead by bytes_encoded bytes, so UpdateHash 208c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // can't be used to calculate the hash value at its new position. 209c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott hash_value = hasher.Hash(candidate_pos); 210c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (look_for_target_matches) { 211c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Update the target hash for the ADDed and COPYed data 212c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott target_hash->AddAllBlocksThroughIndex( 213c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott static_cast<int>(next_encode - target_data)); 214c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 215c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else { 216c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // No match, or match is too small to be worth a COPY instruction. 217c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Move to the next position in the target data. 218c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if ((candidate_pos + 1) > start_of_last_block) { 219c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; // Reached end of target data 220c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 221c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (look_for_target_matches) { 222c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott target_hash->AddOneIndexHash( 223c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott static_cast<int>(candidate_pos - target_data), 224c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott hash_value); 225c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 226c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott hash_value = hasher.UpdateHash(hash_value, 227c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott candidate_pos[0], 228c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott candidate_pos[BlockHash::kBlockSize]); 229c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ++candidate_pos; 230c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 231c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 232c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott AddUnmatchedRemainder(next_encode, target_end - next_encode, coder); 233c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott FinishEncoding(target_size, diff, coder); 234c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott delete target_hash; 235c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 236c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 237c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid VCDiffEngine::Encode(const char* target_data, 238c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott size_t target_size, 239c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott bool look_for_target_matches, 240c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott OutputStringInterface* diff, 241c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CodeTableWriterInterface* coder) const { 242c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (look_for_target_matches) { 243c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EncodeInternal<true>(target_data, target_size, diff, coder); 244c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else { 245c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EncodeInternal<false>(target_data, target_size, diff, coder); 246c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 247c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 248c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 249c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} // namespace open_vcdiff 250