open-vcdiff/src/vcencoder_test.cc

// 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 "google/vcencoder.h"
#include <stdlib.h>  // free, posix_memalign
#include <string.h>  // memcpy
#include <algorithm>
#include <string>
#include <vector>
#include "blockhash.h"
#include "checksum.h"
#include "testing.h"
#include "varint_bigendian.h"
#include "google/vcdecoder.h"
#include "vcdiff_defs.h"

#ifdef HAVE_EXT_ROPE
#include <ext/rope>
#include "output_string_crope.h"
using __gnu_cxx::crope;
#endif  // HAVE_EXT_ROPE

#ifdef HAVE_MALLOC_H
#include <malloc.h>
#endif  // HAVE_MALLOC_H

#ifdef HAVE_SYS_MMAN_H
#define _XOPEN_SOURCE 600  // posix_memalign
#include <sys/mman.h>  // mprotect
#endif  // HAVE_SYS_MMAN_H

#ifdef HAVE_UNISTD_H
#include <unistd.h>  // getpagesize
#endif  // HAVE_UNISTD_H

namespace open_vcdiff {
namespace {

static const size_t kFileHeaderSize = sizeof(DeltaFileHeader);

// This is to check the maximum possible encoding size
// if using a single ADD instruction, so assume that the
// dictionary size, the length of the ADD data, the size
// of the target window, and the length of the delta window
// are all two-byte Varints, that is, 128 <= length < 4096.
// This figure includes three extra bytes for a zero-sized
// ADD instruction with a two-byte Varint explicit size.
// Any additional COPY & ADD instructions must reduce
// the length of the encoding from this maximum.
static const size_t kWindowHeaderSize = 21;

class VerifyEncodedBytesTest : public testing::Test {
 public:
  typedef std::string string;

  VerifyEncodedBytesTest() : delta_index_(0) { }
  virtual ~VerifyEncodedBytesTest() { }

  void ExpectByte(unsigned char b) {
    EXPECT_EQ(b, static_cast<unsigned char>(delta_[delta_index_]));
    ++delta_index_;
  }

  void ExpectString(const char* s) {
    const size_t size = strlen(s);  // don't include terminating NULL char
    EXPECT_EQ(string(s, size),
              string(delta_data() + delta_index_, size));
    delta_index_ += size;
  }

  void ExpectNoMoreBytes() {
    EXPECT_EQ(delta_index_, delta_size());
  }

  void ExpectSize(size_t size) {
    const char* delta_size_pos = &delta_[delta_index_];
    EXPECT_EQ(size,
              static_cast<size_t>(
                  VarintBE<int32_t>::Parse(delta_data() + delta_size(),
                                           &delta_size_pos)));
    delta_index_ = delta_size_pos - delta_data();
  }

  void ExpectChecksum(VCDChecksum checksum) {
    const char* delta_checksum_pos = &delta_[delta_index_];
    EXPECT_EQ(checksum,
              static_cast<VCDChecksum>(
                  VarintBE<int64_t>::Parse(delta_data() + delta_size(),
                                           &delta_checksum_pos)));
    delta_index_ = delta_checksum_pos - delta_data();
  }

  const string& delta_as_const() const { return delta_; }
  string* delta() { return &delta_; }

  const char* delta_data() const { return delta_as_const().data(); }
  size_t delta_size() const { return delta_as_const().size(); }

 private:
  string delta_;
  size_t delta_index_;
};

class VCDiffEncoderTest : public VerifyEncodedBytesTest {
 protected:
  static const char kDictionary[];
  static const char kTarget[];

  VCDiffEncoderTest();
  virtual ~VCDiffEncoderTest() { }

  void TestWithFixedChunkSize(size_t chunk_size);
  void TestWithEncodedChunkVector(size_t chunk_size);

  HashedDictionary hashed_dictionary_;
  VCDiffStreamingEncoder encoder_;
  VCDiffStreamingDecoder decoder_;
  VCDiffEncoder simple_encoder_;
  VCDiffDecoder simple_decoder_;

  string result_target_;
};

const char VCDiffEncoderTest::kDictionary[] =
    "\"Just the place for a Snark!\" the Bellman cried,\n"
    "As he landed his crew with care;\n"
    "Supporting each man on the top of the tide\n"
    "By a finger entwined in his hair.\n";

const char VCDiffEncoderTest::kTarget[] =
    "\"Just the place for a Snark! I have said it twice:\n"
    "That alone should encourage the crew.\n"
    "Just the place for a Snark! I have said it thrice:\n"
    "What I tell you three times is true.\"\n";

VCDiffEncoderTest::VCDiffEncoderTest()
    : hashed_dictionary_(kDictionary, sizeof(kDictionary)),
      encoder_(&hashed_dictionary_,
               VCD_FORMAT_INTERLEAVED | VCD_FORMAT_CHECKSUM,
               /* look_for_target_matches = */ true),
      simple_encoder_(kDictionary, sizeof(kDictionary)) {
  EXPECT_TRUE(hashed_dictionary_.Init());
}

TEST_F(VCDiffEncoderTest, EncodeBeforeStartEncoding) {
  EXPECT_FALSE(encoder_.EncodeChunk(kTarget, strlen(kTarget), delta()));
}

TEST_F(VCDiffEncoderTest, FinishBeforeStartEncoding) {
  EXPECT_FALSE(encoder_.FinishEncoding(delta()));
}

TEST_F(VCDiffEncoderTest, EncodeDecodeNothing) {
  HashedDictionary nothing_dictionary("", 0);
  EXPECT_TRUE(nothing_dictionary.Init());
  VCDiffStreamingEncoder nothing_encoder(&nothing_dictionary,
                                         VCD_STANDARD_FORMAT,
                                         false);
  EXPECT_TRUE(nothing_encoder.StartEncoding(delta()));
  EXPECT_TRUE(nothing_encoder.FinishEncoding(delta()));
  decoder_.StartDecoding("", 0);
  EXPECT_TRUE(decoder_.DecodeChunk(delta_data(),
                                   delta_size(),
                                   &result_target_));
  EXPECT_TRUE(decoder_.FinishDecoding());
  EXPECT_TRUE(result_target_.empty());
}

// A NULL dictionary pointer is legal as long as the dictionary size is 0.
TEST_F(VCDiffEncoderTest, EncodeDecodeNullDictionaryPtr) {
  HashedDictionary null_dictionary(NULL, 0);
  EXPECT_TRUE(null_dictionary.Init());
  VCDiffStreamingEncoder null_encoder(&null_dictionary,
                                      VCD_STANDARD_FORMAT,
                                      false);
  EXPECT_TRUE(null_encoder.StartEncoding(delta()));
  EXPECT_TRUE(null_encoder.EncodeChunk(kTarget, strlen(kTarget), delta()));
  EXPECT_TRUE(null_encoder.FinishEncoding(delta()));
  EXPECT_GE(strlen(kTarget) + kFileHeaderSize + kWindowHeaderSize,
            delta_size());
  decoder_.StartDecoding(NULL, 0);
  EXPECT_TRUE(decoder_.DecodeChunk(delta_data(),
                                   delta_size(),
                                   &result_target_));
  EXPECT_TRUE(decoder_.FinishDecoding());
  EXPECT_EQ(kTarget, result_target_);
}

TEST_F(VCDiffEncoderTest, EncodeDecodeSimple) {
  EXPECT_TRUE(simple_encoder_.Encode(kTarget, strlen(kTarget), delta()));
  EXPECT_GE(strlen(kTarget) + kFileHeaderSize + kWindowHeaderSize,
            delta_size());
  EXPECT_TRUE(simple_decoder_.Decode(kDictionary,
                                     sizeof(kDictionary),
                                     delta_as_const(),
                                     &result_target_));
  EXPECT_EQ(kTarget, result_target_);
}

TEST_F(VCDiffEncoderTest, EncodeDecodeInterleaved) {
  simple_encoder_.SetFormatFlags(VCD_FORMAT_INTERLEAVED);
  EXPECT_TRUE(simple_encoder_.Encode(kTarget, strlen(kTarget), delta()));
  EXPECT_GE(strlen(kTarget) + kFileHeaderSize + kWindowHeaderSize,
            delta_size());
  EXPECT_TRUE(simple_decoder_.Decode(kDictionary,
                                     sizeof(kDictionary),
                                     delta_as_const(),
                                     &result_target_));
  EXPECT_EQ(kTarget, result_target_);
}

TEST_F(VCDiffEncoderTest, EncodeDecodeInterleavedChecksum) {
  simple_encoder_.SetFormatFlags(VCD_FORMAT_INTERLEAVED | VCD_FORMAT_CHECKSUM);
  EXPECT_TRUE(simple_encoder_.Encode(kTarget,
                                     strlen(kTarget),
                                     delta()));
  EXPECT_GE(strlen(kTarget) + kFileHeaderSize + kWindowHeaderSize,
            delta_size());
  EXPECT_TRUE(simple_decoder_.Decode(kDictionary,
                                     sizeof(kDictionary),
                                     delta_as_const(),
                                     &result_target_));
  EXPECT_EQ(kTarget, result_target_);
}

TEST_F(VCDiffEncoderTest, EncodeDecodeSingleChunk) {
  EXPECT_TRUE(encoder_.StartEncoding(delta()));
  EXPECT_TRUE(encoder_.EncodeChunk(kTarget, strlen(kTarget), delta()));
  EXPECT_TRUE(encoder_.FinishEncoding(delta()));
  EXPECT_GE(strlen(kTarget) + kFileHeaderSize + kWindowHeaderSize,
            delta_size());
  decoder_.StartDecoding(kDictionary, sizeof(kDictionary));
  EXPECT_TRUE(decoder_.DecodeChunk(delta_data(),
                                   delta_size(),
                                   &result_target_));
  EXPECT_TRUE(decoder_.FinishDecoding());
  EXPECT_EQ(kTarget, result_target_);
}

TEST_F(VCDiffEncoderTest, EncodeDecodeSeparate) {
  string delta_start, delta_encode, delta_finish;
  EXPECT_TRUE(encoder_.StartEncoding(&delta_start));
  EXPECT_TRUE(encoder_.EncodeChunk(kTarget, strlen(kTarget), &delta_encode));
  EXPECT_TRUE(encoder_.FinishEncoding(&delta_finish));
  EXPECT_GE(strlen(kTarget) + kFileHeaderSize + kWindowHeaderSize,
            delta_start.size() + delta_encode.size() + delta_finish.size());
  decoder_.StartDecoding(kDictionary, sizeof(kDictionary));
  EXPECT_TRUE(decoder_.DecodeChunk(delta_start.data(),
                                   delta_start.size(),
                                   &result_target_));
  EXPECT_TRUE(decoder_.DecodeChunk(delta_encode.data(),
                                   delta_encode.size(),
                                   &result_target_));
  EXPECT_TRUE(decoder_.DecodeChunk(delta_finish.data(),
                                   delta_finish.size(),
                                   &result_target_));
  EXPECT_TRUE(decoder_.FinishDecoding());
  EXPECT_EQ(kTarget, result_target_);
}

#ifdef HAVE_EXT_ROPE
// Test that the crope class can be used in place of a string for encoding
// and decoding.
TEST_F(VCDiffEncoderTest, EncodeDecodeCrope) {
  crope delta_crope, result_crope;
  EXPECT_TRUE(encoder_.StartEncoding(&delta_crope));
  EXPECT_TRUE(encoder_.EncodeChunk(kTarget, strlen(kTarget), &delta_crope));
  EXPECT_TRUE(encoder_.FinishEncoding(&delta_crope));
  EXPECT_GE(strlen(kTarget) + kFileHeaderSize + kWindowHeaderSize,
            delta_crope.size());
  decoder_.StartDecoding(kDictionary, sizeof(kDictionary));
  // crope can't guarantee that its characters are contiguous, so the decoding
  // has to be done byte-by-byte.
  for (crope::const_iterator it = delta_crope.begin();
       it != delta_crope.end(); it++) {
    const char this_char = *it;
    EXPECT_TRUE(decoder_.DecodeChunk(&this_char, 1, &result_crope));
  }
  EXPECT_TRUE(decoder_.FinishDecoding());
  crope expected_target(kTarget);
  EXPECT_EQ(expected_target, result_crope);
}
#endif  // HAVE_EXT_ROPE

void VCDiffEncoderTest::TestWithFixedChunkSize(size_t chunk_size) {
  delta()->clear();
  EXPECT_TRUE(encoder_.StartEncoding(delta()));
  for (size_t chunk_start_index = 0;
       chunk_start_index < strlen(kTarget);
       chunk_start_index += chunk_size) {
    size_t this_chunk_size = chunk_size;
    const size_t bytes_available = strlen(kTarget) - chunk_start_index;
    if (this_chunk_size > bytes_available) {
      this_chunk_size = bytes_available;
    }
    EXPECT_TRUE(encoder_.EncodeChunk(&kTarget[chunk_start_index],
                                     this_chunk_size,
                                     delta()));
  }
  EXPECT_TRUE(encoder_.FinishEncoding(delta()));
  const size_t num_windows = (strlen(kTarget) / chunk_size) + 1;
  const size_t size_of_windows =
      strlen(kTarget) + (kWindowHeaderSize * num_windows);
  EXPECT_GE(kFileHeaderSize + size_of_windows, delta_size());
  result_target_.clear();
  decoder_.StartDecoding(kDictionary, sizeof(kDictionary));
  for (size_t chunk_start_index = 0;
       chunk_start_index < delta_size();
       chunk_start_index += chunk_size) {
    size_t this_chunk_size = chunk_size;
    const size_t bytes_available = delta_size() - chunk_start_index;
    if (this_chunk_size > bytes_available) {
      this_chunk_size = bytes_available;
    }
    EXPECT_TRUE(decoder_.DecodeChunk(delta_data() + chunk_start_index,
                                     this_chunk_size,
                                     &result_target_));
  }
  EXPECT_TRUE(decoder_.FinishDecoding());
  EXPECT_EQ(kTarget, result_target_);
}

TEST_F(VCDiffEncoderTest, EncodeDecodeFixedChunkSizes) {
  // These specific chunk sizes have failed in the past
  TestWithFixedChunkSize(6);
  TestWithFixedChunkSize(45);
  TestWithFixedChunkSize(60);

  // Now loop through all possible chunk sizes
  for (size_t chunk_size = 1; chunk_size < strlen(kTarget); ++chunk_size) {
    TestWithFixedChunkSize(chunk_size);
  }
}

// If --allow_vcd_target=false is specified, the decoder will throw away some of
// the internally-stored decoded target beyond the current window.  Try
// different numbers of encoded window sizes to make sure that this behavior
// does not affect the results.
TEST_F(VCDiffEncoderTest, EncodeDecodeFixedChunkSizesNoVcdTarget) {
  decoder_.SetAllowVcdTarget(false);
  // Loop through all possible chunk sizes
  for (size_t chunk_size = 1; chunk_size < strlen(kTarget); ++chunk_size) {
    TestWithFixedChunkSize(chunk_size);
  }
}

// Splits the text to be encoded into fixed-size chunks.  Encodes each
// chunk and puts it into a vector of strings.  Then decodes each string
// in the vector and appends the result into result_target_.
void VCDiffEncoderTest::TestWithEncodedChunkVector(size_t chunk_size) {
  std::vector<string> encoded_chunks;
  string this_encoded_chunk;
  size_t total_chunk_size = 0;
  EXPECT_TRUE(encoder_.StartEncoding(&this_encoded_chunk));
  encoded_chunks.push_back(this_encoded_chunk);
  total_chunk_size += this_encoded_chunk.size();
  for (size_t chunk_start_index = 0;
       chunk_start_index < strlen(kTarget);
       chunk_start_index += chunk_size) {
    size_t this_chunk_size = chunk_size;
    const size_t bytes_available = strlen(kTarget) - chunk_start_index;
    if (this_chunk_size > bytes_available) {
      this_chunk_size = bytes_available;
    }
    this_encoded_chunk.clear();
    EXPECT_TRUE(encoder_.EncodeChunk(&kTarget[chunk_start_index],
                                     this_chunk_size,
                                     &this_encoded_chunk));
    encoded_chunks.push_back(this_encoded_chunk);
    total_chunk_size += this_encoded_chunk.size();
  }
  this_encoded_chunk.clear();
  EXPECT_TRUE(encoder_.FinishEncoding(&this_encoded_chunk));
  encoded_chunks.push_back(this_encoded_chunk);
  total_chunk_size += this_encoded_chunk.size();
  const size_t num_windows = (strlen(kTarget) / chunk_size) + 1;
  const size_t size_of_windows =
      strlen(kTarget) + (kWindowHeaderSize * num_windows);
  EXPECT_GE(kFileHeaderSize + size_of_windows, total_chunk_size);
  result_target_.clear();
  decoder_.StartDecoding(kDictionary, sizeof(kDictionary));
  for (std::vector<string>::iterator it = encoded_chunks.begin();
       it != encoded_chunks.end(); ++it) {
    EXPECT_TRUE(decoder_.DecodeChunk(it->data(), it->size(), &result_target_));
  }
  EXPECT_TRUE(decoder_.FinishDecoding());
  EXPECT_EQ(kTarget, result_target_);
}

TEST_F(VCDiffEncoderTest, EncodeDecodeStreamOfChunks) {
  // Loop through all possible chunk sizes
  for (size_t chunk_size = 1; chunk_size < strlen(kTarget); ++chunk_size) {
    TestWithEncodedChunkVector(chunk_size);
  }
}

// Verify that HashedDictionary stores a copy of the dictionary text,
// rather than just storing a pointer to it.  If the dictionary buffer
// is overwritten after creating a HashedDictionary from it, it shouldn't
// affect an encoder that uses that HashedDictionary.
TEST_F(VCDiffEncoderTest, DictionaryBufferOverwritten) {
  string dictionary_copy(kDictionary, sizeof(kDictionary));
  HashedDictionary hd_copy(dictionary_copy.data(), dictionary_copy.size());
  EXPECT_TRUE(hd_copy.Init());
  VCDiffStreamingEncoder copy_encoder(&hd_copy,
                                      VCD_FORMAT_INTERLEAVED
                                          | VCD_FORMAT_CHECKSUM,
                                      /* look_for_target_matches = */ true);
  // Produce a reference version of the encoded text.
  string delta_before;
  EXPECT_TRUE(copy_encoder.StartEncoding(&delta_before));
  EXPECT_TRUE(copy_encoder.EncodeChunk(kTarget,
                                       strlen(kTarget),
                                       &delta_before));
  EXPECT_TRUE(copy_encoder.FinishEncoding(&delta_before));
  EXPECT_GE(strlen(kTarget) + kFileHeaderSize + kWindowHeaderSize,
            delta_before.size());

  // Overwrite the dictionary text with all 'Q' characters.
  dictionary_copy.replace(0,
                          dictionary_copy.size(),
                          dictionary_copy.size(),
                          'Q');
  // When the encoder is used on the same target text after overwriting
  // the dictionary, it should produce the same encoded output.
  string delta_after;
  EXPECT_TRUE(copy_encoder.StartEncoding(&delta_after));
  EXPECT_TRUE(copy_encoder.EncodeChunk(kTarget, strlen(kTarget), &delta_after));
  EXPECT_TRUE(copy_encoder.FinishEncoding(&delta_after));
  EXPECT_EQ(delta_before, delta_after);
}

// Binary data test part 1: The dictionary and target data should not
// be treated as NULL-terminated.  An embedded NULL should be handled like
// any other byte of data.
TEST_F(VCDiffEncoderTest, DictionaryHasEmbeddedNULLs) {
  const char embedded_null_dictionary_text[] =
      { 0x00, 0xFF, 0xFE, 0xFD, 0x00, 0xFD, 0xFE, 0xFF, 0x00, 0x03 };
  const char embedded_null_target[] =
      { 0xFD, 0x00, 0xFD, 0xFE, 0x03, 0x00, 0x01, 0x00 };
  CHECK_EQ(10, sizeof(embedded_null_dictionary_text));
  CHECK_EQ(8, sizeof(embedded_null_target));
  HashedDictionary embedded_null_dictionary(embedded_null_dictionary_text,
      sizeof(embedded_null_dictionary_text));
  EXPECT_TRUE(embedded_null_dictionary.Init());
  VCDiffStreamingEncoder embedded_null_encoder(&embedded_null_dictionary,
      VCD_FORMAT_INTERLEAVED | VCD_FORMAT_CHECKSUM,
      /* look_for_target_matches = */ true);
  EXPECT_TRUE(embedded_null_encoder.StartEncoding(delta()));
  EXPECT_TRUE(embedded_null_encoder.EncodeChunk(embedded_null_target,
                                                sizeof(embedded_null_target),
                                                delta()));
  EXPECT_TRUE(embedded_null_encoder.FinishEncoding(delta()));
  decoder_.StartDecoding(embedded_null_dictionary_text,
                         sizeof(embedded_null_dictionary_text));
  EXPECT_TRUE(decoder_.DecodeChunk(delta_data(),
                                   delta_size(),
                                   &result_target_));
  EXPECT_TRUE(decoder_.FinishDecoding());
  EXPECT_EQ(sizeof(embedded_null_target), result_target_.size());
  EXPECT_EQ(string(embedded_null_target,
                   sizeof(embedded_null_target)),
            result_target_);
}

// Binary data test part 2: An embedded CR or LF should be handled like
// any other byte of data.  No text-processing of the data should occur.
TEST_F(VCDiffEncoderTest, DictionaryHasEmbeddedNewlines) {
  const char embedded_null_dictionary_text[] =
      { 0x0C, 0xFF, 0xFE, 0x0C, 0x00, 0x0A, 0xFE, 0xFF, 0x00, 0x0A };
  const char embedded_null_target[] =
      { 0x0C, 0x00, 0x0A, 0xFE, 0x03, 0x00, 0x0A, 0x00 };
  CHECK_EQ(10, sizeof(embedded_null_dictionary_text));
  CHECK_EQ(8, sizeof(embedded_null_target));
  HashedDictionary embedded_null_dictionary(embedded_null_dictionary_text,
      sizeof(embedded_null_dictionary_text));
  EXPECT_TRUE(embedded_null_dictionary.Init());
  VCDiffStreamingEncoder embedded_null_encoder(&embedded_null_dictionary,
      VCD_FORMAT_INTERLEAVED | VCD_FORMAT_CHECKSUM,
      /* look_for_target_matches = */ true);
  EXPECT_TRUE(embedded_null_encoder.StartEncoding(delta()));
  EXPECT_TRUE(embedded_null_encoder.EncodeChunk(embedded_null_target,
                                                sizeof(embedded_null_target),
                                                delta()));
  EXPECT_TRUE(embedded_null_encoder.FinishEncoding(delta()));
  decoder_.StartDecoding(embedded_null_dictionary_text,
                         sizeof(embedded_null_dictionary_text));
  EXPECT_TRUE(decoder_.DecodeChunk(delta_data(),
                                   delta_size(),
                                   &result_target_));
  EXPECT_TRUE(decoder_.FinishDecoding());
  EXPECT_EQ(sizeof(embedded_null_target), result_target_.size());
  EXPECT_EQ(string(embedded_null_target,
                   sizeof(embedded_null_target)),
            result_target_);
}

TEST_F(VCDiffEncoderTest, UsingWideCharacters) {
  const wchar_t wchar_dictionary_text[] =
      L"\"Just the place for a Snark!\" the Bellman cried,\n"
      L"As he landed his crew with care;\n"
      L"Supporting each man on the top of the tide\n"
      L"By a finger entwined in his hair.\n";

  const wchar_t wchar_target[] =
      L"\"Just the place for a Snark! I have said it twice:\n"
      L"That alone should encourage the crew.\n"
      L"Just the place for a Snark! I have said it thrice:\n"
      L"What I tell you three times is true.\"\n";

  HashedDictionary wchar_dictionary((const char*) wchar_dictionary_text,
                                    sizeof(wchar_dictionary_text));
  EXPECT_TRUE(wchar_dictionary.Init());
  VCDiffStreamingEncoder wchar_encoder(&wchar_dictionary,
                                       VCD_FORMAT_INTERLEAVED
                                           | VCD_FORMAT_CHECKSUM,
                                       /* look_for_target_matches = */ false);
  EXPECT_TRUE(wchar_encoder.StartEncoding(delta()));
  EXPECT_TRUE(wchar_encoder.EncodeChunk((const char*) wchar_target,
                                        sizeof(wchar_target),
                                        delta()));
  EXPECT_TRUE(wchar_encoder.FinishEncoding(delta()));
  decoder_.StartDecoding((const char*) wchar_dictionary_text,
                         sizeof(wchar_dictionary_text));
  EXPECT_TRUE(decoder_.DecodeChunk(delta_data(),
                                   delta_size(),
                                   &result_target_));
  EXPECT_TRUE(decoder_.FinishDecoding());
  const wchar_t* result_as_wchar = (const wchar_t*) result_target_.data();
  EXPECT_EQ(wcslen(wchar_target), wcslen(result_as_wchar));
  EXPECT_EQ(0, wcscmp(wchar_target, result_as_wchar));
}

#if defined(HAVE_MPROTECT) && \
   (defined(HAVE_MEMALIGN) || defined(HAVE_POSIX_MEMALIGN))
// Bug 1220602: Make sure the encoder doesn't read past the end of the input
// buffer.
TEST_F(VCDiffEncoderTest, ShouldNotReadPastEndOfBuffer) {
  const size_t target_size = strlen(kTarget);

  // Allocate two memory pages.
  const int page_size = getpagesize();
  void* two_pages = NULL;
#ifdef HAVE_POSIX_MEMALIGN
  posix_memalign(&two_pages, page_size, 2 * page_size);
#else  // !HAVE_POSIX_MEMALIGN
  two_pages = memalign(page_size, 2 * page_size);
#endif  // HAVE_POSIX_MEMALIGN
  char* const first_page = reinterpret_cast<char*>(two_pages);
  char* const second_page = first_page + page_size;

  // Place the target string at the end of the first page.
  char* const target_with_guard = second_page - target_size;
  memcpy(target_with_guard, kTarget, target_size);

  // Make the second page unreadable.
  mprotect(second_page, page_size, PROT_NONE);

  // Now perform the encode operation, which will cause a segmentation fault
  // if it reads past the end of the buffer.
  EXPECT_TRUE(encoder_.StartEncoding(delta()));
  EXPECT_TRUE(encoder_.EncodeChunk(target_with_guard, target_size, delta()));
  EXPECT_TRUE(encoder_.FinishEncoding(delta()));

  // Undo the mprotect.
  mprotect(second_page, page_size, PROT_READ|PROT_WRITE);
  free(two_pages);
}

TEST_F(VCDiffEncoderTest, ShouldNotReadPastBeginningOfBuffer) {
  const size_t target_size = strlen(kTarget);

  // Allocate two memory pages.
  const int page_size = getpagesize();
  void* two_pages = NULL;
#ifdef HAVE_POSIX_MEMALIGN
  posix_memalign(&two_pages, page_size, 2 * page_size);
#else  // !HAVE_POSIX_MEMALIGN
  two_pages = memalign(page_size, 2 * page_size);
#endif  // HAVE_POSIX_MEMALIGN
  char* const first_page = reinterpret_cast<char*>(two_pages);
  char* const second_page = first_page + page_size;

  // Make the first page unreadable.
  mprotect(first_page, page_size, PROT_NONE);

  // Place the target string at the beginning of the second page.
  char* const target_with_guard = second_page;
  memcpy(target_with_guard, kTarget, target_size);

  // Now perform the encode operation, which will cause a segmentation fault
  // if it reads past the beginning of the buffer.
  EXPECT_TRUE(encoder_.StartEncoding(delta()));
  EXPECT_TRUE(encoder_.EncodeChunk(target_with_guard, target_size, delta()));
  EXPECT_TRUE(encoder_.FinishEncoding(delta()));

  // Undo the mprotect.
  mprotect(first_page, page_size, PROT_READ|PROT_WRITE);
  free(two_pages);
}
#endif  // HAVE_MPROTECT && (HAVE_MEMALIGN || HAVE_POSIX_MEMALIGN)

class VCDiffMatchCountTest : public VerifyEncodedBytesTest {
 protected:
  virtual ~VCDiffMatchCountTest() { }

  void ExpectMatch(size_t match_size) {
    if (match_size >= expected_match_counts_.size()) {
      // Be generous to avoid resizing again
      expected_match_counts_.resize(match_size * 2, 0);
    }
    ++expected_match_counts_[match_size];
  }

  void VerifyMatchCounts() {
    EXPECT_TRUE(std::equal(expected_match_counts_.begin(),
                           expected_match_counts_.end(),
                           actual_match_counts_.begin()));
  }

  std::vector<int> expected_match_counts_;
  std::vector<int> actual_match_counts_;
};

class VCDiffHTML1Test : public VCDiffMatchCountTest {
 protected:
  static const char kDictionary[];
  static const char kTarget[];
  static const char kRedundantTarget[];

  VCDiffHTML1Test();
  virtual ~VCDiffHTML1Test() { }

  void SimpleEncode();
  void StreamingEncode();

  HashedDictionary hashed_dictionary_;
  VCDiffStreamingEncoder encoder_;
  VCDiffStreamingDecoder decoder_;
  VCDiffEncoder simple_encoder_;
  VCDiffDecoder simple_decoder_;

  string result_target_;
};

const char VCDiffHTML1Test::kDictionary[] =
    "<html><font color=red>This part from the dict</font><br>";

const char VCDiffHTML1Test::kTarget[] =
    "<html><font color=red>This part from the dict</font><br>\n"
    "And this part is not...</html>";

const char VCDiffHTML1Test::kRedundantTarget[] =
    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";  // 256

VCDiffHTML1Test::VCDiffHTML1Test()
    : hashed_dictionary_(kDictionary, sizeof(kDictionary)),
      encoder_(&hashed_dictionary_,
               VCD_FORMAT_INTERLEAVED | VCD_FORMAT_CHECKSUM,
               /* look_for_target_matches = */ true),
      simple_encoder_(kDictionary, sizeof(kDictionary)) {
  EXPECT_TRUE(hashed_dictionary_.Init());
}

void VCDiffHTML1Test::SimpleEncode() {
  EXPECT_TRUE(simple_encoder_.Encode(kTarget, strlen(kTarget), delta()));
  EXPECT_GE(strlen(kTarget) + kFileHeaderSize + kWindowHeaderSize,
            delta_size());
  EXPECT_TRUE(simple_decoder_.Decode(kDictionary,
                                     sizeof(kDictionary),
                                     delta_as_const(),
                                     &result_target_));
  EXPECT_EQ(kTarget, result_target_);
}

void VCDiffHTML1Test::StreamingEncode() {
  EXPECT_TRUE(encoder_.StartEncoding(delta()));
  EXPECT_TRUE(encoder_.EncodeChunk(kTarget, strlen(kTarget), delta()));
  EXPECT_TRUE(encoder_.FinishEncoding(delta()));
}

TEST_F(VCDiffHTML1Test, CheckOutputOfSimpleEncoder) {
  SimpleEncode();
  // These values do not depend on the block size used for encoding
  ExpectByte(0xD6);  // 'V' | 0x80
  ExpectByte(0xC3);  // 'C' | 0x80
  ExpectByte(0xC4);  // 'D' | 0x80
  ExpectByte(0x00);  // Simple encoder never uses interleaved format
  ExpectByte(0x00);  // Hdr_Indicator
  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
  ExpectByte(sizeof(kDictionary));  // Dictionary length
  ExpectByte(0x00);  // Source segment position: start of dictionary
  if (BlockHash::kBlockSize < 16) {
    // A medium block size will catch the "his part " match.
    ExpectByte(0x22);  // Length of the delta encoding
    ExpectSize(strlen(kTarget));  // Size of the target window
    ExpectByte(0x00);  // Delta_indicator (no compression)
    ExpectByte(0x16);  // Length of the data section
    ExpectByte(0x05);  // Length of the instructions section
    ExpectByte(0x02);  // Length of the address section
    // Data section
    ExpectString("\nAnd t");      // Data for 1st ADD
    ExpectString("is not...</html>");  // Data for 2nd ADD
    // Instructions section
    ExpectByte(0x73);  // COPY size 0 mode VCD_SAME(0)
    ExpectByte(0x38);  // COPY size (56)
    ExpectByte(0x07);  // ADD size 6
    ExpectByte(0x19);  // COPY size 9 mode VCD_SELF
    ExpectByte(0x11);  // ADD size 16
    // Address section
    ExpectByte(0x00);  // COPY address (0) mode VCD_SAME(0)
    ExpectByte(0x17);  // COPY address (23) mode VCD_SELF
  } else if (BlockHash::kBlockSize <= 56) {
    // Any block size up to 56 will catch the matching prefix string.
    ExpectByte(0x29);  // Length of the delta encoding
    ExpectSize(strlen(kTarget));  // Size of the target window
    ExpectByte(0x00);  // Delta_indicator (no compression)
    ExpectByte(0x1F);  // Length of the data section
    ExpectByte(0x04);  // Length of the instructions section
    ExpectByte(0x01);  // Length of the address section
    ExpectString("\nAnd this part is not...</html>");  // Data for ADD
    // Instructions section
    ExpectByte(0x73);  // COPY size 0 mode VCD_SAME(0)
    ExpectByte(0x38);  // COPY size (56)
    ExpectByte(0x01);  // ADD size 0
    ExpectByte(0x1F);  // Size of ADD (31)
    // Address section
    ExpectByte(0x00);  // COPY address (0) mode VCD_SAME(0)
  } else {
    // The matching string is 56 characters long, and the block size is
    // 64 or greater, so no match should be found.
    ExpectSize(strlen(kTarget) + 7);  // Delta encoding len
    ExpectSize(strlen(kTarget));  // Size of the target window
    ExpectByte(0x00);  // Delta_indicator (no compression)
    ExpectSize(strlen(kTarget));  // Length of the data section
    ExpectByte(0x02);  // Length of the instructions section
    ExpectByte(0x00);  // Length of the address section
    // Data section
    ExpectString(kTarget);
    ExpectByte(0x01);  // ADD size 0
    ExpectSize(strlen(kTarget));
  }
  ExpectNoMoreBytes();
}

TEST_F(VCDiffHTML1Test, MatchCounts) {
  StreamingEncode();
  encoder_.GetMatchCounts(&actual_match_counts_);
  if (BlockHash::kBlockSize < 16) {
    // A medium block size will catch the "his part " match.
    ExpectMatch(56);
    ExpectMatch(9);
  } else if (BlockHash::kBlockSize <= 56) {
    // Any block size up to 56 will catch the matching prefix string.
    ExpectMatch(56);
  }
  VerifyMatchCounts();
}

TEST_F(VCDiffHTML1Test, SimpleEncoderPerformsTargetMatching) {
  EXPECT_TRUE(simple_encoder_.Encode(kRedundantTarget,
                                     strlen(kRedundantTarget),
                                     delta()));
  EXPECT_GE(strlen(kRedundantTarget) + kFileHeaderSize + kWindowHeaderSize,
            delta_size());
  EXPECT_TRUE(simple_decoder_.Decode(kDictionary,
                                     sizeof(kDictionary),
                                     delta_as_const(),
                                     &result_target_));
  EXPECT_EQ(kRedundantTarget, result_target_);
  // These values do not depend on the block size used for encoding
  ExpectByte(0xD6);  // 'V' | 0x80
  ExpectByte(0xC3);  // 'C' | 0x80
  ExpectByte(0xC4);  // 'D' | 0x80
  ExpectByte(0x00);  // Simple encoder never uses interleaved format
  ExpectByte(0x00);  // Hdr_Indicator
  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
  ExpectByte(sizeof(kDictionary));  // Dictionary length
  ExpectByte(0x00);  // Source segment position: start of dictionary
  ExpectByte(0x0C);  // Length of the delta encoding
  ExpectSize(strlen(kRedundantTarget));  // Size of the target window
  ExpectByte(0x00);  // Delta_indicator (no compression)
  ExpectByte(0x01);  // Length of the data section
  ExpectByte(0x04);  // Length of the instructions section
  ExpectByte(0x01);  // Length of the address section
  // Data section
  ExpectString("A");      // Data for ADD
  // Instructions section
  ExpectByte(0x02);  // ADD size 1
  ExpectByte(0x23);  // COPY size 0 mode VCD_HERE
  ExpectSize(strlen(kRedundantTarget) - 1);  // COPY size 255
  // Address section
  ExpectByte(0x01);  // COPY address (1) mode VCD_HERE
  ExpectNoMoreBytes();
}

TEST_F(VCDiffHTML1Test, SimpleEncoderWithoutTargetMatching) {
  simple_encoder_.SetTargetMatching(false);
  EXPECT_TRUE(simple_encoder_.Encode(kRedundantTarget,
                                     strlen(kRedundantTarget),
                                     delta()));
  EXPECT_GE(strlen(kRedundantTarget) + kFileHeaderSize + kWindowHeaderSize,
            delta_size());
  EXPECT_TRUE(simple_decoder_.Decode(kDictionary,
                                     sizeof(kDictionary),
                                     delta_as_const(),
                                     &result_target_));
  EXPECT_EQ(kRedundantTarget, result_target_);
  // These values do not depend on the block size used for encoding
  ExpectByte(0xD6);  // 'V' | 0x80
  ExpectByte(0xC3);  // 'C' | 0x80
  ExpectByte(0xC4);  // 'D' | 0x80
  ExpectByte(0x00);  // Simple encoder never uses interleaved format
  ExpectByte(0x00);  // Hdr_Indicator
  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
  ExpectByte(sizeof(kDictionary));  // Dictionary length
  ExpectByte(0x00);  // Source segment position: start of dictionary
  ExpectSize(strlen(kRedundantTarget) + 0x0A);  // Length of the delta encoding
  ExpectSize(strlen(kRedundantTarget));  // Size of the target window
  ExpectByte(0x00);  // Delta_indicator (no compression)
  ExpectSize(strlen(kRedundantTarget));  // Length of the data section
  ExpectByte(0x03);  // Length of the instructions section
  ExpectByte(0x00);  // Length of the address section
  // Data section
  ExpectString(kRedundantTarget);      // Data for ADD
  // Instructions section
  ExpectByte(0x01);  // ADD size 0
  ExpectSize(strlen(kRedundantTarget));  // ADD size
  // Address section empty
  ExpectNoMoreBytes();
}

#ifdef GTEST_HAS_DEATH_TEST
typedef VCDiffHTML1Test VCDiffHTML1DeathTest;

TEST_F(VCDiffHTML1DeathTest, NullMatchCounts) {
  EXPECT_DEBUG_DEATH(encoder_.GetMatchCounts(NULL), "GetMatchCounts");
}
#endif  // GTEST_HAS_DEATH_TEST

class VCDiffHTML2Test : public VCDiffMatchCountTest {
 protected:
  static const char kDictionary[];
  static const char kTarget[];

  VCDiffHTML2Test();
  virtual ~VCDiffHTML2Test() { }

  void SimpleEncode();
  void StreamingEncode();

  HashedDictionary hashed_dictionary_;
  VCDiffStreamingEncoder encoder_;
  VCDiffStreamingDecoder decoder_;
  VCDiffEncoder simple_encoder_;
  VCDiffDecoder simple_decoder_;

  string result_target_;
};

const char VCDiffHTML2Test::kDictionary[] = "10\nThis is a test";

const char VCDiffHTML2Test::kTarget[] = "This is a test!!!\n";

VCDiffHTML2Test::VCDiffHTML2Test()
    : hashed_dictionary_(kDictionary, sizeof(kDictionary)),
      encoder_(&hashed_dictionary_,
               VCD_FORMAT_INTERLEAVED | VCD_FORMAT_CHECKSUM,
               /* look_for_target_matches = */ true),
      simple_encoder_(kDictionary, sizeof(kDictionary)) {
  EXPECT_TRUE(hashed_dictionary_.Init());
}

void VCDiffHTML2Test::SimpleEncode() {
  EXPECT_TRUE(simple_encoder_.Encode(kTarget, strlen(kTarget), delta()));
  EXPECT_GE(strlen(kTarget) + kFileHeaderSize + kWindowHeaderSize,
            delta_size());
  EXPECT_TRUE(simple_decoder_.Decode(kDictionary,
                                     sizeof(kDictionary),
                                     delta_as_const(),
                                     &result_target_));
  EXPECT_EQ(kTarget, result_target_);
}

void VCDiffHTML2Test::StreamingEncode() {
  EXPECT_TRUE(encoder_.StartEncoding(delta()));
  EXPECT_TRUE(encoder_.EncodeChunk(kTarget, strlen(kTarget), delta()));
  EXPECT_GE(strlen(kTarget) + kFileHeaderSize + kWindowHeaderSize,
            delta_size());
  EXPECT_TRUE(simple_decoder_.Decode(kDictionary,
                                     sizeof(kDictionary),
                                     delta_as_const(),
                                     &result_target_));
  EXPECT_EQ(kTarget, result_target_);
}

TEST_F(VCDiffHTML2Test, VerifyOutputOfSimpleEncoder) {
  SimpleEncode();
  // These values do not depend on the block size used for encoding
  ExpectByte(0xD6);  // 'V' | 0x80
  ExpectByte(0xC3);  // 'C' | 0x80
  ExpectByte(0xC4);  // 'D' | 0x80
  ExpectByte(0x00);  // Simple encoder never uses interleaved format
  ExpectByte(0x00);  // Hdr_Indicator
  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
  ExpectByte(sizeof(kDictionary));  // Dictionary length
  ExpectByte(0x00);  // Source segment position: start of dictionary
  if (BlockHash::kBlockSize <= 8) {
    ExpectByte(12);  // Length of the delta encoding
    ExpectSize(strlen(kTarget));  // Size of the target window
    ExpectByte(0x00);  // Delta_indicator (no compression)
    ExpectByte(0x04);  // Length of the data section
    ExpectByte(0x02);  // Length of the instructions section
    ExpectByte(0x01);  // Length of the address section
    ExpectByte('!');
    ExpectByte('!');
    ExpectByte('!');
    ExpectByte('\n');
    ExpectByte(0x1E);  // COPY size 14 mode VCD_SELF
    ExpectByte(0x05);  // ADD size 4
    ExpectByte(0x03);  // COPY address (3) mode VCD_SELF
  } else {
    // Larger block sizes will not catch any matches.
    ExpectSize(strlen(kTarget) + 7);  // Delta encoding len
    ExpectSize(strlen(kTarget));  // Size of the target window
    ExpectByte(0x00);  // Delta_indicator (no compression)
    ExpectSize(strlen(kTarget));  // Length of the data section
    ExpectByte(0x02);  // Length of the instructions section
    ExpectByte(0x00);  // Length of the address section
    // Data section
    ExpectString(kTarget);
    ExpectByte(0x01);  // ADD size 0
    ExpectSize(strlen(kTarget));
  }
  ExpectNoMoreBytes();
}

TEST_F(VCDiffHTML2Test, VerifyOutputWithChecksum) {
  StreamingEncode();
  const VCDChecksum html2_checksum = ComputeAdler32(kTarget, strlen(kTarget));
  CHECK_EQ(5, VarintBE<int64_t>::Length(html2_checksum));
  // These values do not depend on the block size used for encoding
  ExpectByte(0xD6);  // 'V' | 0x80
  ExpectByte(0xC3);  // 'C' | 0x80
  ExpectByte(0xC4);  // 'D' | 0x80
  ExpectByte('S');  // Format extensions
  ExpectByte(0x00);  // Hdr_Indicator
  ExpectByte(VCD_SOURCE | VCD_CHECKSUM);  // Win_Indicator
  ExpectByte(sizeof(kDictionary));  // Dictionary length
  ExpectByte(0x00);  // Source segment position: start of dictionary
  if (BlockHash::kBlockSize <= 8) {
    ExpectByte(17);  // Length of the delta encoding
    ExpectSize(strlen(kTarget));  // Size of the target window
    ExpectByte(0x00);  // Delta_indicator (no compression)
    ExpectByte(0x00);  // Length of the data section
    ExpectByte(0x07);  // Length of the instructions section
    ExpectByte(0x00);  // Length of the address section
    ExpectChecksum(html2_checksum);
    ExpectByte(0x1E);  // COPY size 14 mode VCD_SELF
    ExpectByte(0x03);  // COPY address (3) mode VCD_SELF
    ExpectByte(0x05);  // ADD size 4
    ExpectByte('!');
    ExpectByte('!');
    ExpectByte('!');
    ExpectByte('\n');
  } else {
    // Larger block sizes will not catch any matches.
    ExpectSize(strlen(kTarget) + 12);  // Delta encoding len
    ExpectSize(strlen(kTarget));  // Size of the target window
    ExpectByte(0x00);  // Delta_indicator (no compression)
    ExpectByte(0x00);  // Length of the data section
    ExpectSize(0x02 + strlen(kTarget));  // Interleaved
    ExpectByte(0x00);  // Length of the address section
    ExpectChecksum(html2_checksum);
    // Data section
    ExpectByte(0x01);  // ADD size 0
    ExpectSize(strlen(kTarget));
    ExpectString(kTarget);
  }
  ExpectNoMoreBytes();
}

TEST_F(VCDiffHTML2Test, MatchCounts) {
  StreamingEncode();
  encoder_.GetMatchCounts(&actual_match_counts_);
  if (BlockHash::kBlockSize <= 8) {
    ExpectMatch(14);
  }
  VerifyMatchCounts();
}

}  // anonymous namespace
}  // namespace open_vcdiff