diff options
Diffstat (limited to 'src/encodetable_test.cc')
-rw-r--r-- | src/encodetable_test.cc | 508 |
1 files changed, 508 insertions, 0 deletions
diff --git a/src/encodetable_test.cc b/src/encodetable_test.cc new file mode 100644 index 0000000..50a74ca --- /dev/null +++ b/src/encodetable_test.cc @@ -0,0 +1,508 @@ +// 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 <algorithm> +#include <cstring> // strlen +#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 { + +using std::string; + +class CodeTableWriterTest : public testing::Test { + protected: + // Remove all of the functions below that are not useful for this + // test fixture. + + 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 |