sdch/open-vcdiff/src/encodetable_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.
//
// Unit tests for the class VCDiffCodeTableWriter, found in encodetable.h.

#include <config.h>
#include "encodetable.h"
#include <string.h>  // strlen
#include <algorithm>
#include <string>
#include <vector>
#include "addrcache.h"  // VCDiffAddressCache::kDefaultNearCacheSize
#include "checksum.h"
#include "codetable.h"
#include "google/output_string.h"
#include "testing.h"
#include "vcdiff_defs.h"

namespace open_vcdiff {
namespace {

class CodeTableWriterTest : public testing::Test {
 protected:
  typedef std::string string;

  CodeTableWriterTest()
      : standard_writer(false),
        interleaved_writer(true),
        exercise_writer(true,
                        VCDiffAddressCache::kDefaultNearCacheSize,
                        VCDiffAddressCache::kDefaultSameCacheSize,
                        *g_exercise_code_table_, kLastExerciseMode),
        output_string(&out),
        out_index(0) { }

  virtual ~CodeTableWriterTest() { }

  static void AddExerciseOpcode(unsigned char inst1,
                                unsigned char mode1,
                                unsigned char size1,
                                unsigned char inst2,
                                unsigned char mode2,
                                unsigned char size2,
                                int opcode) {
    g_exercise_code_table_->inst1[opcode] = inst1;
    g_exercise_code_table_->mode1[opcode] = mode1;
    g_exercise_code_table_->size1[opcode] = (inst1 == VCD_NOOP) ? 0 : size1;
    g_exercise_code_table_->inst2[opcode] = inst2;
    g_exercise_code_table_->mode2[opcode] = mode2;
    g_exercise_code_table_->size2[opcode] = (inst2 == VCD_NOOP) ? 0 : size2;
  }

  static void SetUpTestCase() {
    g_exercise_code_table_ = new VCDiffCodeTableData;
    int opcode = 0;
    for (unsigned char inst_mode1 = 0;
         inst_mode1 <= VCD_LAST_INSTRUCTION_TYPE + kLastExerciseMode;
         ++inst_mode1) {
      unsigned char inst1 = inst_mode1;
      unsigned char mode1 = 0;
      if (inst_mode1 > VCD_COPY) {
        inst1 = VCD_COPY;
        mode1 = inst_mode1 - VCD_COPY;
      }
      for (unsigned char inst_mode2 = 0;
           inst_mode2 <= VCD_LAST_INSTRUCTION_TYPE + kLastExerciseMode;
           ++inst_mode2) {
        unsigned char inst2 = inst_mode2;
        unsigned char mode2 = 0;
        if (inst_mode2 > VCD_COPY) {
          inst2 = VCD_COPY;
          mode2 = inst_mode2 - VCD_COPY;
        }
        AddExerciseOpcode(inst1, mode1, 0, inst2, mode2, 0, opcode++);
        AddExerciseOpcode(inst1, mode1, 0, inst2, mode2, 255, opcode++);
        AddExerciseOpcode(inst1, mode1, 255, inst2, mode2, 0, opcode++);
        AddExerciseOpcode(inst1, mode1, 255, inst2, mode2, 255, opcode++);
      }
    }
    // This is a CHECK rather than an EXPECT because it validates only
    // the logic of the test, not of the code being tested.
    CHECK_EQ(VCDiffCodeTableData::kCodeTableSize, opcode);

    EXPECT_TRUE(g_exercise_code_table_->Validate(kLastExerciseMode));
  }

  static void TearDownTestCase() {
    delete g_exercise_code_table_;
  }

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

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

  void ExpectNoMoreBytes() {
    EXPECT_EQ(out_index, out.size());
  }

  static bool AnyMatch(int match_count) { return match_count != 0; }

  static void ExpectNoMatchesForWriter(const VCDiffCodeTableWriter& writer) {
    const std::vector<int>& match_counts = writer.match_counts();
    EXPECT_TRUE(find_if(match_counts.begin(), match_counts.end(), AnyMatch)
                    == match_counts.end());
  }

  void ExpectNoMatches() const {
    ExpectNoMatchesForWriter(standard_writer);
    ExpectNoMatchesForWriter(interleaved_writer);
    ExpectNoMatchesForWriter(exercise_writer);
  }

  // This value is designed so that the total number of inst values and modes
  // will equal 8 (VCD_NOOP, VCD_ADD, VCD_RUN, VCD_COPY modes 0 - 4).
  // Eight combinations of inst and mode, times two possible size values,
  // squared (because there are two instructions per opcode), makes
  // exactly 256 possible instruction combinations, which fits kCodeTableSize
  // (the number of opcodes in the table.)
  static const int kLastExerciseMode = 4;

  // A code table that exercises as many combinations as possible:
  // 2 instructions, each is a NOOP, ADD, RUN, or one of 5 copy modes
  // (== 8 total combinations of inst and mode), and each has
  // size == 0 or 255 (2 possibilities.)
  static VCDiffCodeTableData* g_exercise_code_table_;

  // The code table writer for standard encoding, default code table.
  VCDiffCodeTableWriter standard_writer;

  // The code table writer for interleaved encoding, default code table.
  VCDiffCodeTableWriter interleaved_writer;

  // The code table writer corresponding to g_exercise_code_table_
  // (interleaved encoding).
  VCDiffCodeTableWriter exercise_writer;

  // Destination for VCDiffCodeTableWriter::Output()
  string out;
  OutputString<string> output_string;
  size_t out_index;
};

VCDiffCodeTableData* CodeTableWriterTest::g_exercise_code_table_;

#ifdef GTEST_HAS_DEATH_TEST
typedef CodeTableWriterTest CodeTableWriterDeathTest;
#endif  // GTEST_HAS_DEATH_TEST

#ifdef GTEST_HAS_DEATH_TEST
TEST_F(CodeTableWriterDeathTest, WriterAddWithoutInit) {
#ifndef NDEBUG
  // This condition is only checked in the debug build.
  EXPECT_DEBUG_DEATH(standard_writer.Add("Hello", 5),
                     "Init");
#endif  // !NDEBUG
}

TEST_F(CodeTableWriterDeathTest, WriterRunWithoutInit) {
#ifndef NDEBUG
  // This condition is only checked in the debug build.
  EXPECT_DEBUG_DEATH(standard_writer.Run(3, 'a'),
                     "Init");
#endif  // !NDEBUG
}

TEST_F(CodeTableWriterDeathTest, WriterCopyWithoutInit) {
#ifndef NDEBUG
  // This condition is only checked in the debug build.
  EXPECT_DEBUG_DEATH(standard_writer.Copy(6, 5),
                     "Init");
#endif  // !NDEBUG
}
#endif  // GTEST_HAS_DEATH_TEST

// Output() without Init() is harmless, but will produce no output.
TEST_F(CodeTableWriterTest, WriterOutputWithoutInit) {
  standard_writer.Output(&output_string);
  EXPECT_TRUE(out.empty());
}

TEST_F(CodeTableWriterTest, WriterEncodeNothing) {
  EXPECT_TRUE(standard_writer.Init(0));
  standard_writer.Output(&output_string);
  // The writer should know not to append a delta file window
  // if nothing was encoded.
  EXPECT_TRUE(out.empty());

  out.clear();
  EXPECT_TRUE(interleaved_writer.Init(0x10));
  interleaved_writer.Output(&output_string);
  EXPECT_TRUE(out.empty());

  out.clear();
  EXPECT_TRUE(exercise_writer.Init(0x20));
  exercise_writer.Output(&output_string);
  EXPECT_TRUE(out.empty());

  ExpectNoMatches();
}

TEST_F(CodeTableWriterTest, StandardWriterEncodeAdd) {
  EXPECT_TRUE(standard_writer.Init(0x11));
  standard_writer.Add("foo", 3);
  standard_writer.Output(&output_string);
  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
  ExpectByte(0x11);  // Source segment size: dictionary length
  ExpectByte(0x00);  // Source segment position: start of dictionary
  ExpectByte(0x09);  // Length of the delta encoding
  ExpectByte(0x03);  // Size of the target window
  ExpectByte(0x00);  // Delta_indicator (no compression)
  ExpectByte(0x03);  // length of data for ADDs and RUNs
  ExpectByte(0x01);  // length of instructions section
  ExpectByte(0x00);  // length of addresses for COPYs
  ExpectString("foo");
  ExpectByte(0x04);  // ADD(3) opcode
  ExpectNoMoreBytes();
  ExpectNoMatches();
}

TEST_F(CodeTableWriterTest, ExerciseWriterEncodeAdd) {
  EXPECT_TRUE(exercise_writer.Init(0x11));
  exercise_writer.Add("foo", 3);
  exercise_writer.Output(&output_string);
  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
  ExpectByte(0x11);  // Source segment size: dictionary length
  ExpectByte(0x00);  // Source segment position: start of dictionary
  ExpectByte(0x0A);  // Length of the delta encoding
  ExpectByte(0x03);  // Size of the target window
  ExpectByte(0x00);  // Delta_indicator (no compression)
  ExpectByte(0x00);  // length of data for ADDs and RUNs
  ExpectByte(0x05);  // length of instructions section
  ExpectByte(0x00);  // length of addresses for COPYs
  ExpectByte(0x04);  // Opcode: NOOP + ADD(0)
  ExpectByte(0x03);  // Size of ADD (3)
  ExpectString("foo");
  ExpectNoMatches();
}

TEST_F(CodeTableWriterTest, StandardWriterEncodeRun) {
  EXPECT_TRUE(standard_writer.Init(0x11));
  standard_writer.Run(3, 'a');
  standard_writer.Output(&output_string);
  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
  ExpectByte(0x11);  // Source segment size: dictionary length
  ExpectByte(0x00);  // Source segment position: start of dictionary
  ExpectByte(0x08);  // Length of the delta encoding
  ExpectByte(0x03);  // Size of the target window
  ExpectByte(0x00);  // Delta_indicator (no compression)
  ExpectByte(0x01);  // length of data for ADDs and RUNs
  ExpectByte(0x02);  // length of instructions section
  ExpectByte(0x00);  // length of addresses for COPYs
  ExpectByte('a');
  ExpectByte(0x00);  // RUN(0) opcode
  ExpectByte(0x03);  // Size of RUN (3)
  ExpectNoMoreBytes();
  ExpectNoMatches();
}

TEST_F(CodeTableWriterTest, ExerciseWriterEncodeRun) {
  EXPECT_TRUE(exercise_writer.Init(0x11));
  exercise_writer.Run(3, 'a');
  exercise_writer.Output(&output_string);
  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
  ExpectByte(0x11);  // Source segment size: dictionary length
  ExpectByte(0x00);  // Source segment position: start of dictionary
  ExpectByte(0x08);  // Length of the delta encoding
  ExpectByte(0x03);  // Size of the target window
  ExpectByte(0x00);  // Delta_indicator (no compression)
  ExpectByte(0x00);  // length of data for ADDs and RUNs
  ExpectByte(0x03);  // length of instructions section
  ExpectByte(0x00);  // length of addresses for COPYs
  ExpectByte(0x08);  // Opcode: NOOP + RUN(0)
  ExpectByte(0x03);  // Size of RUN (3)
  ExpectByte('a');
  ExpectNoMoreBytes();
  ExpectNoMatches();
}

TEST_F(CodeTableWriterTest, StandardWriterEncodeCopy) {
  EXPECT_TRUE(standard_writer.Init(0x11));
  standard_writer.Copy(2, 8);
  standard_writer.Copy(2, 8);
  standard_writer.Output(&output_string);
  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
  ExpectByte(0x11);  // Source segment size: dictionary length
  ExpectByte(0x00);  // Source segment position: start of dictionary
  ExpectByte(0x09);  // Length of the delta encoding
  ExpectByte(0x10);  // Size of the target window
  ExpectByte(0x00);  // Delta_indicator (no compression)
  ExpectByte(0x00);  // length of data for ADDs and RUNs
  ExpectByte(0x02);  // length of instructions section
  ExpectByte(0x02);  // length of addresses for COPYs
  ExpectByte(0x18);  // COPY mode SELF, size 8
  ExpectByte(0x78);  // COPY mode SAME(0), size 8
  ExpectByte(0x02);  // COPY address (2)
  ExpectByte(0x02);  // COPY address (2)
  ExpectNoMoreBytes();
  EXPECT_LE(9U, standard_writer.match_counts().size());
  EXPECT_EQ(0, standard_writer.match_counts()[0]);
  EXPECT_EQ(0, standard_writer.match_counts()[1]);
  EXPECT_EQ(0, standard_writer.match_counts()[2]);
  EXPECT_EQ(0, standard_writer.match_counts()[3]);
  EXPECT_EQ(0, standard_writer.match_counts()[4]);
  EXPECT_EQ(0, standard_writer.match_counts()[5]);
  EXPECT_EQ(0, standard_writer.match_counts()[6]);
  EXPECT_EQ(0, standard_writer.match_counts()[7]);
  EXPECT_EQ(2, standard_writer.match_counts()[8]);
}

// The exercise code table can't be used to test how the code table
// writer encodes COPY instructions because the code table writer
// always uses the default cache sizes, which exceed the maximum mode
// used in the exercise table.
TEST_F(CodeTableWriterTest, InterleavedWriterEncodeCopy) {
  EXPECT_TRUE(interleaved_writer.Init(0x11));
  interleaved_writer.Copy(2, 8);
  interleaved_writer.Copy(2, 8);
  interleaved_writer.Output(&output_string);
  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
  ExpectByte(0x11);  // Source segment size: dictionary length
  ExpectByte(0x00);  // Source segment position: start of dictionary
  ExpectByte(0x09);  // Length of the delta encoding
  ExpectByte(0x10);  // Size of the target window
  ExpectByte(0x00);  // Delta_indicator (no compression)
  ExpectByte(0x00);  // length of data for ADDs and RUNs
  ExpectByte(0x04);  // length of instructions section
  ExpectByte(0x00);  // length of addresses for COPYs
  ExpectByte(0x18);  // COPY mode SELF, size 8
  ExpectByte(0x02);  // COPY address (2)
  ExpectByte(0x78);  // COPY mode SAME(0), size 8
  ExpectByte(0x02);  // COPY address (2)
  ExpectNoMoreBytes();
  EXPECT_LE(9U, interleaved_writer.match_counts().size());
  EXPECT_EQ(0, interleaved_writer.match_counts()[0]);
  EXPECT_EQ(0, interleaved_writer.match_counts()[1]);
  EXPECT_EQ(0, interleaved_writer.match_counts()[2]);
  EXPECT_EQ(0, interleaved_writer.match_counts()[3]);
  EXPECT_EQ(0, interleaved_writer.match_counts()[4]);
  EXPECT_EQ(0, interleaved_writer.match_counts()[5]);
  EXPECT_EQ(0, interleaved_writer.match_counts()[6]);
  EXPECT_EQ(0, interleaved_writer.match_counts()[7]);
  EXPECT_EQ(2, interleaved_writer.match_counts()[8]);
}

TEST_F(CodeTableWriterTest, StandardWriterEncodeCombo) {
  EXPECT_TRUE(standard_writer.Init(0x11));
  standard_writer.Add("rayo", 4);
  standard_writer.Copy(2, 5);
  standard_writer.Copy(0, 4);
  standard_writer.Add("X", 1);
  standard_writer.Output(&output_string);
  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
  ExpectByte(0x11);  // Source segment size: dictionary length
  ExpectByte(0x00);  // Source segment position: start of dictionary
  ExpectByte(0x0E);  // Length of the delta encoding
  ExpectByte(0x0E);  // Size of the target window
  ExpectByte(0x00);  // Delta_indicator (no compression)
  ExpectByte(0x05);  // length of data for ADDs and RUNs
  ExpectByte(0x02);  // length of instructions section
  ExpectByte(0x02);  // length of addresses for COPYs
  ExpectString("rayoX");
  ExpectByte(0xAD);  // Combo: Add size 4 + COPY mode SELF, size 5
  ExpectByte(0xFD);  // Combo: COPY mode SAME(0), size 4 + Add size 1
  ExpectByte(0x02);  // COPY address (2)
  ExpectByte(0x00);  // COPY address (0)
  ExpectNoMoreBytes();
  EXPECT_LE(6U, standard_writer.match_counts().size());
  EXPECT_EQ(0, standard_writer.match_counts()[0]);
  EXPECT_EQ(0, standard_writer.match_counts()[1]);
  EXPECT_EQ(0, standard_writer.match_counts()[2]);
  EXPECT_EQ(0, standard_writer.match_counts()[3]);
  EXPECT_EQ(1, standard_writer.match_counts()[4]);
  EXPECT_EQ(1, standard_writer.match_counts()[5]);
}

TEST_F(CodeTableWriterTest, InterleavedWriterEncodeCombo) {
  EXPECT_TRUE(interleaved_writer.Init(0x11));
  interleaved_writer.Add("rayo", 4);
  interleaved_writer.Copy(2, 5);
  interleaved_writer.Copy(0, 4);
  interleaved_writer.Add("X", 1);
  interleaved_writer.Output(&output_string);
  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
  ExpectByte(0x11);  // Source segment size: dictionary length
  ExpectByte(0x00);  // Source segment position: start of dictionary
  ExpectByte(0x0E);  // Length of the delta encoding
  ExpectByte(0x0E);  // Size of the target window
  ExpectByte(0x00);  // Delta_indicator (no compression)
  ExpectByte(0x00);  // length of data for ADDs and RUNs
  ExpectByte(0x09);  // length of instructions section
  ExpectByte(0x00);  // length of addresses for COPYs
  ExpectByte(0xAD);  // Combo: Add size 4 + COPY mode SELF, size 5
  ExpectString("rayo");
  ExpectByte(0x02);  // COPY address (2)
  ExpectByte(0xFD);  // Combo: COPY mode SAME(0), size 4 + Add size 1
  ExpectByte(0x00);  // COPY address (0)
  ExpectByte('X');
  ExpectNoMoreBytes();
  EXPECT_LE(6U, interleaved_writer.match_counts().size());
  EXPECT_EQ(0, interleaved_writer.match_counts()[0]);
  EXPECT_EQ(0, interleaved_writer.match_counts()[1]);
  EXPECT_EQ(0, interleaved_writer.match_counts()[2]);
  EXPECT_EQ(0, interleaved_writer.match_counts()[3]);
  EXPECT_EQ(1, interleaved_writer.match_counts()[4]);
  EXPECT_EQ(1, interleaved_writer.match_counts()[5]);
}

TEST_F(CodeTableWriterTest, InterleavedWriterEncodeComboWithChecksum) {
  EXPECT_TRUE(interleaved_writer.Init(0x11));
  const VCDChecksum checksum = 0xFFFFFFFF;  // would be negative if signed
  interleaved_writer.AddChecksum(checksum);
  interleaved_writer.Add("rayo", 4);
  interleaved_writer.Copy(2, 5);
  interleaved_writer.Copy(0, 4);
  interleaved_writer.Add("X", 1);
  interleaved_writer.Output(&output_string);
  ExpectByte(VCD_SOURCE | VCD_CHECKSUM);  // Win_Indicator
  ExpectByte(0x11);  // Source segment size: dictionary length
  ExpectByte(0x00);  // Source segment position: start of dictionary
  ExpectByte(0x13);  // Length of the delta encoding
  ExpectByte(0x0E);  // Size of the target window
  ExpectByte(0x00);  // Delta_indicator (no compression)
  ExpectByte(0x00);  // length of data for ADDs and RUNs
  ExpectByte(0x09);  // length of instructions section
  ExpectByte(0x00);  // length of addresses for COPYs
  ExpectByte(0x8F);  // checksum byte 1
  ExpectByte(0xFF);  // checksum byte 2
  ExpectByte(0xFF);  // checksum byte 3
  ExpectByte(0xFF);  // checksum byte 4
  ExpectByte(0x7F);  // checksum byte 5
  ExpectByte(0xAD);  // Combo: Add size 4 + COPY mode SELF, size 5
  ExpectString("rayo");
  ExpectByte(0x02);  // COPY address (2)
  ExpectByte(0xFD);  // Combo: COPY mode SAME(0), size 4 + Add size 1
  ExpectByte(0x00);  // COPY address (0)
  ExpectByte('X');
  ExpectNoMoreBytes();
}

TEST_F(CodeTableWriterTest, ReallyBigDictionary) {
  EXPECT_TRUE(interleaved_writer.Init(0x3FFFFFFF));
  interleaved_writer.Copy(2, 8);
  interleaved_writer.Copy(0x3FFFFFFE, 8);
  interleaved_writer.Output(&output_string);
  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
  ExpectByte(0x83);  // Source segment size: dictionary length (1)
  ExpectByte(0xFF);  // Source segment size: dictionary length (2)
  ExpectByte(0xFF);  // Source segment size: dictionary length (3)
  ExpectByte(0xFF);  // Source segment size: dictionary length (4)
  ExpectByte(0x7F);  // Source segment size: dictionary length (5)
  ExpectByte(0x00);  // Source segment position: start of dictionary
  ExpectByte(0x09);  // Length of the delta encoding
  ExpectByte(0x10);  // Size of the target window
  ExpectByte(0x00);  // Delta_indicator (no compression)
  ExpectByte(0x00);  // length of data for ADDs and RUNs
  ExpectByte(0x04);  // length of instructions section
  ExpectByte(0x00);  // length of addresses for COPYs
  ExpectByte(0x18);  // COPY mode SELF, size 8
  ExpectByte(0x02);  // COPY address (2)
  ExpectByte(0x28);  // COPY mode HERE, size 8
  ExpectByte(0x09);  // COPY address (9)
  ExpectNoMoreBytes();
  EXPECT_LE(9U, interleaved_writer.match_counts().size());
  EXPECT_EQ(0, interleaved_writer.match_counts()[0]);
  EXPECT_EQ(0, interleaved_writer.match_counts()[1]);
  EXPECT_EQ(0, interleaved_writer.match_counts()[2]);
  EXPECT_EQ(0, interleaved_writer.match_counts()[3]);
  EXPECT_EQ(0, interleaved_writer.match_counts()[4]);
  EXPECT_EQ(0, interleaved_writer.match_counts()[5]);
  EXPECT_EQ(0, interleaved_writer.match_counts()[6]);
  EXPECT_EQ(0, interleaved_writer.match_counts()[7]);
  EXPECT_EQ(2, interleaved_writer.match_counts()[8]);
}

#ifdef GTEST_HAS_DEATH_TEST
TEST_F(CodeTableWriterDeathTest, DictionaryTooBig) {
  EXPECT_TRUE(interleaved_writer.Init(0x7FFFFFFF));
  interleaved_writer.Copy(2, 8);
  EXPECT_DEBUG_DEATH(interleaved_writer.Copy(0x7FFFFFFE, 8),
                     "address.*<.*here_address");
}
#endif  // GTEST_HAS_DEATH_TEST

}  // unnamed namespace
}  // namespace open_vcdiff