1// Copyright 2008 Google Inc.
2// Author: Lincoln Smith
3//
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at
7//
8//      http://www.apache.org/licenses/LICENSE-2.0
9//
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15//
16// Unit tests for the class VCDiffCodeTableWriter, found in encodetable.h.
17
18#include <config.h>
19#include "encodetable.h"
20#include <string.h>  // strlen
21#include <algorithm>
22#include <string>
23#include "addrcache.h"  // VCDiffAddressCache::kDefaultNearCacheSize
24#include "checksum.h"
25#include "codetable.h"
26#include "google/output_string.h"
27#include "testing.h"
28#include "vcdiff_defs.h"
29
30namespace open_vcdiff {
31namespace {
32
33class CodeTableWriterTest : public testing::Test {
34 protected:
35  typedef std::string string;
36
37  CodeTableWriterTest()
38      : standard_writer(false),
39        interleaved_writer(true),
40        exercise_writer(true,
41                        VCDiffAddressCache::kDefaultNearCacheSize,
42                        VCDiffAddressCache::kDefaultSameCacheSize,
43                        *g_exercise_code_table_, kLastExerciseMode),
44        output_string(&out),
45        out_index(0) { }
46
47  virtual ~CodeTableWriterTest() { }
48
49  static void AddExerciseOpcode(unsigned char inst1,
50                                unsigned char mode1,
51                                unsigned char size1,
52                                unsigned char inst2,
53                                unsigned char mode2,
54                                unsigned char size2,
55                                int opcode) {
56    g_exercise_code_table_->inst1[opcode] = inst1;
57    g_exercise_code_table_->mode1[opcode] = mode1;
58    g_exercise_code_table_->size1[opcode] = (inst1 == VCD_NOOP) ? 0 : size1;
59    g_exercise_code_table_->inst2[opcode] = inst2;
60    g_exercise_code_table_->mode2[opcode] = mode2;
61    g_exercise_code_table_->size2[opcode] = (inst2 == VCD_NOOP) ? 0 : size2;
62  }
63
64  static void SetUpTestCase() {
65    g_exercise_code_table_ = new VCDiffCodeTableData;
66    int opcode = 0;
67    for (unsigned char inst_mode1 = 0;
68         inst_mode1 <= VCD_LAST_INSTRUCTION_TYPE + kLastExerciseMode;
69         ++inst_mode1) {
70      unsigned char inst1 = inst_mode1;
71      unsigned char mode1 = 0;
72      if (inst_mode1 > VCD_COPY) {
73        inst1 = VCD_COPY;
74        mode1 = inst_mode1 - VCD_COPY;
75      }
76      for (unsigned char inst_mode2 = 0;
77           inst_mode2 <= VCD_LAST_INSTRUCTION_TYPE + kLastExerciseMode;
78           ++inst_mode2) {
79        unsigned char inst2 = inst_mode2;
80        unsigned char mode2 = 0;
81        if (inst_mode2 > VCD_COPY) {
82          inst2 = VCD_COPY;
83          mode2 = inst_mode2 - VCD_COPY;
84        }
85        AddExerciseOpcode(inst1, mode1, 0, inst2, mode2, 0, opcode++);
86        AddExerciseOpcode(inst1, mode1, 0, inst2, mode2, 255, opcode++);
87        AddExerciseOpcode(inst1, mode1, 255, inst2, mode2, 0, opcode++);
88        AddExerciseOpcode(inst1, mode1, 255, inst2, mode2, 255, opcode++);
89      }
90    }
91    // This is a CHECK rather than an EXPECT because it validates only
92    // the logic of the test, not of the code being tested.
93    CHECK_EQ(VCDiffCodeTableData::kCodeTableSize, opcode);
94
95    EXPECT_TRUE(g_exercise_code_table_->Validate(kLastExerciseMode));
96  }
97
98  static void TearDownTestCase() {
99    delete g_exercise_code_table_;
100  }
101
102  void ExpectByte(unsigned char b) {
103    EXPECT_EQ(b, static_cast<unsigned char>(out[out_index]));
104    ++out_index;
105  }
106
107  void ExpectString(const char* s) {
108    const size_t size = strlen(s);  // don't include terminating NULL char
109    EXPECT_EQ(s, string(out.data() + out_index, size));
110    out_index += size;
111  }
112
113  void ExpectNoMoreBytes() {
114    EXPECT_EQ(out_index, out.size());
115  }
116
117  // This value is designed so that the total number of inst values and modes
118  // will equal 8 (VCD_NOOP, VCD_ADD, VCD_RUN, VCD_COPY modes 0 - 4).
119  // Eight combinations of inst and mode, times two possible size values,
120  // squared (because there are two instructions per opcode), makes
121  // exactly 256 possible instruction combinations, which fits kCodeTableSize
122  // (the number of opcodes in the table.)
123  static const int kLastExerciseMode = 4;
124
125  // A code table that exercises as many combinations as possible:
126  // 2 instructions, each is a NOOP, ADD, RUN, or one of 5 copy modes
127  // (== 8 total combinations of inst and mode), and each has
128  // size == 0 or 255 (2 possibilities.)
129  static VCDiffCodeTableData* g_exercise_code_table_;
130
131  // The code table writer for standard encoding, default code table.
132  VCDiffCodeTableWriter standard_writer;
133
134  // The code table writer for interleaved encoding, default code table.
135  VCDiffCodeTableWriter interleaved_writer;
136
137  // The code table writer corresponding to g_exercise_code_table_
138  // (interleaved encoding).
139  VCDiffCodeTableWriter exercise_writer;
140
141  // Destination for VCDiffCodeTableWriter::Output()
142  string out;
143  OutputString<string> output_string;
144  size_t out_index;
145};
146
147VCDiffCodeTableData* CodeTableWriterTest::g_exercise_code_table_;
148
149#ifdef GTEST_HAS_DEATH_TEST
150typedef CodeTableWriterTest CodeTableWriterDeathTest;
151#endif  // GTEST_HAS_DEATH_TEST
152
153#ifdef GTEST_HAS_DEATH_TEST
154TEST_F(CodeTableWriterDeathTest, WriterAddWithoutInit) {
155#ifndef NDEBUG
156  // This condition is only checked in the debug build.
157  EXPECT_DEBUG_DEATH(standard_writer.Add("Hello", 5),
158                     "Init");
159#endif  // !NDEBUG
160}
161
162TEST_F(CodeTableWriterDeathTest, WriterRunWithoutInit) {
163#ifndef NDEBUG
164  // This condition is only checked in the debug build.
165  EXPECT_DEBUG_DEATH(standard_writer.Run(3, 'a'),
166                     "Init");
167#endif  // !NDEBUG
168}
169
170TEST_F(CodeTableWriterDeathTest, WriterCopyWithoutInit) {
171#ifndef NDEBUG
172  // This condition is only checked in the debug build.
173  EXPECT_DEBUG_DEATH(standard_writer.Copy(6, 5),
174                     "Init");
175#endif  // !NDEBUG
176}
177#endif  // GTEST_HAS_DEATH_TEST
178
179// Output() without Init() is harmless, but will produce no output.
180TEST_F(CodeTableWriterTest, WriterOutputWithoutInit) {
181  standard_writer.Output(&output_string);
182  EXPECT_TRUE(out.empty());
183}
184
185TEST_F(CodeTableWriterTest, WriterEncodeNothing) {
186  EXPECT_TRUE(standard_writer.Init(0));
187  standard_writer.Output(&output_string);
188  // The writer should know not to append a delta file window
189  // if nothing was encoded.
190  EXPECT_TRUE(out.empty());
191
192  out.clear();
193  EXPECT_TRUE(interleaved_writer.Init(0x10));
194  interleaved_writer.Output(&output_string);
195  EXPECT_TRUE(out.empty());
196
197  out.clear();
198  EXPECT_TRUE(exercise_writer.Init(0x20));
199  exercise_writer.Output(&output_string);
200  EXPECT_TRUE(out.empty());
201}
202
203TEST_F(CodeTableWriterTest, StandardWriterEncodeAdd) {
204  EXPECT_TRUE(standard_writer.Init(0x11));
205  standard_writer.Add("foo", 3);
206  standard_writer.Output(&output_string);
207  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
208  ExpectByte(0x11);  // Source segment size: dictionary length
209  ExpectByte(0x00);  // Source segment position: start of dictionary
210  ExpectByte(0x09);  // Length of the delta encoding
211  ExpectByte(0x03);  // Size of the target window
212  ExpectByte(0x00);  // Delta_indicator (no compression)
213  ExpectByte(0x03);  // length of data for ADDs and RUNs
214  ExpectByte(0x01);  // length of instructions section
215  ExpectByte(0x00);  // length of addresses for COPYs
216  ExpectString("foo");
217  ExpectByte(0x04);  // ADD(3) opcode
218  ExpectNoMoreBytes();
219}
220
221TEST_F(CodeTableWriterTest, ExerciseWriterEncodeAdd) {
222  EXPECT_TRUE(exercise_writer.Init(0x11));
223  exercise_writer.Add("foo", 3);
224  exercise_writer.Output(&output_string);
225  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
226  ExpectByte(0x11);  // Source segment size: dictionary length
227  ExpectByte(0x00);  // Source segment position: start of dictionary
228  ExpectByte(0x0A);  // Length of the delta encoding
229  ExpectByte(0x03);  // Size of the target window
230  ExpectByte(0x00);  // Delta_indicator (no compression)
231  ExpectByte(0x00);  // length of data for ADDs and RUNs
232  ExpectByte(0x05);  // length of instructions section
233  ExpectByte(0x00);  // length of addresses for COPYs
234  ExpectByte(0x04);  // Opcode: NOOP + ADD(0)
235  ExpectByte(0x03);  // Size of ADD (3)
236  ExpectString("foo");
237}
238
239TEST_F(CodeTableWriterTest, StandardWriterEncodeRun) {
240  EXPECT_TRUE(standard_writer.Init(0x11));
241  standard_writer.Run(3, 'a');
242  standard_writer.Output(&output_string);
243  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
244  ExpectByte(0x11);  // Source segment size: dictionary length
245  ExpectByte(0x00);  // Source segment position: start of dictionary
246  ExpectByte(0x08);  // Length of the delta encoding
247  ExpectByte(0x03);  // Size of the target window
248  ExpectByte(0x00);  // Delta_indicator (no compression)
249  ExpectByte(0x01);  // length of data for ADDs and RUNs
250  ExpectByte(0x02);  // length of instructions section
251  ExpectByte(0x00);  // length of addresses for COPYs
252  ExpectByte('a');
253  ExpectByte(0x00);  // RUN(0) opcode
254  ExpectByte(0x03);  // Size of RUN (3)
255  ExpectNoMoreBytes();
256}
257
258TEST_F(CodeTableWriterTest, ExerciseWriterEncodeRun) {
259  EXPECT_TRUE(exercise_writer.Init(0x11));
260  exercise_writer.Run(3, 'a');
261  exercise_writer.Output(&output_string);
262  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
263  ExpectByte(0x11);  // Source segment size: dictionary length
264  ExpectByte(0x00);  // Source segment position: start of dictionary
265  ExpectByte(0x08);  // Length of the delta encoding
266  ExpectByte(0x03);  // Size of the target window
267  ExpectByte(0x00);  // Delta_indicator (no compression)
268  ExpectByte(0x00);  // length of data for ADDs and RUNs
269  ExpectByte(0x03);  // length of instructions section
270  ExpectByte(0x00);  // length of addresses for COPYs
271  ExpectByte(0x08);  // Opcode: NOOP + RUN(0)
272  ExpectByte(0x03);  // Size of RUN (3)
273  ExpectByte('a');
274  ExpectNoMoreBytes();
275}
276
277TEST_F(CodeTableWriterTest, StandardWriterEncodeCopy) {
278  EXPECT_TRUE(standard_writer.Init(0x11));
279  standard_writer.Copy(2, 8);
280  standard_writer.Copy(2, 8);
281  standard_writer.Output(&output_string);
282  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
283  ExpectByte(0x11);  // Source segment size: dictionary length
284  ExpectByte(0x00);  // Source segment position: start of dictionary
285  ExpectByte(0x09);  // Length of the delta encoding
286  ExpectByte(0x10);  // Size of the target window
287  ExpectByte(0x00);  // Delta_indicator (no compression)
288  ExpectByte(0x00);  // length of data for ADDs and RUNs
289  ExpectByte(0x02);  // length of instructions section
290  ExpectByte(0x02);  // length of addresses for COPYs
291  ExpectByte(0x18);  // COPY mode SELF, size 8
292  ExpectByte(0x78);  // COPY mode SAME(0), size 8
293  ExpectByte(0x02);  // COPY address (2)
294  ExpectByte(0x02);  // COPY address (2)
295  ExpectNoMoreBytes();
296}
297
298// The exercise code table can't be used to test how the code table
299// writer encodes COPY instructions because the code table writer
300// always uses the default cache sizes, which exceed the maximum mode
301// used in the exercise table.
302TEST_F(CodeTableWriterTest, InterleavedWriterEncodeCopy) {
303  EXPECT_TRUE(interleaved_writer.Init(0x11));
304  interleaved_writer.Copy(2, 8);
305  interleaved_writer.Copy(2, 8);
306  interleaved_writer.Output(&output_string);
307  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
308  ExpectByte(0x11);  // Source segment size: dictionary length
309  ExpectByte(0x00);  // Source segment position: start of dictionary
310  ExpectByte(0x09);  // Length of the delta encoding
311  ExpectByte(0x10);  // Size of the target window
312  ExpectByte(0x00);  // Delta_indicator (no compression)
313  ExpectByte(0x00);  // length of data for ADDs and RUNs
314  ExpectByte(0x04);  // length of instructions section
315  ExpectByte(0x00);  // length of addresses for COPYs
316  ExpectByte(0x18);  // COPY mode SELF, size 8
317  ExpectByte(0x02);  // COPY address (2)
318  ExpectByte(0x78);  // COPY mode SAME(0), size 8
319  ExpectByte(0x02);  // COPY address (2)
320  ExpectNoMoreBytes();
321}
322
323TEST_F(CodeTableWriterTest, StandardWriterEncodeCombo) {
324  EXPECT_TRUE(standard_writer.Init(0x11));
325  standard_writer.Add("rayo", 4);
326  standard_writer.Copy(2, 5);
327  standard_writer.Copy(0, 4);
328  standard_writer.Add("X", 1);
329  standard_writer.Output(&output_string);
330  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
331  ExpectByte(0x11);  // Source segment size: dictionary length
332  ExpectByte(0x00);  // Source segment position: start of dictionary
333  ExpectByte(0x0E);  // Length of the delta encoding
334  ExpectByte(0x0E);  // Size of the target window
335  ExpectByte(0x00);  // Delta_indicator (no compression)
336  ExpectByte(0x05);  // length of data for ADDs and RUNs
337  ExpectByte(0x02);  // length of instructions section
338  ExpectByte(0x02);  // length of addresses for COPYs
339  ExpectString("rayoX");
340  ExpectByte(0xAD);  // Combo: Add size 4 + COPY mode SELF, size 5
341  ExpectByte(0xFD);  // Combo: COPY mode SAME(0), size 4 + Add size 1
342  ExpectByte(0x02);  // COPY address (2)
343  ExpectByte(0x00);  // COPY address (0)
344  ExpectNoMoreBytes();
345}
346
347TEST_F(CodeTableWriterTest, InterleavedWriterEncodeCombo) {
348  EXPECT_TRUE(interleaved_writer.Init(0x11));
349  interleaved_writer.Add("rayo", 4);
350  interleaved_writer.Copy(2, 5);
351  interleaved_writer.Copy(0, 4);
352  interleaved_writer.Add("X", 1);
353  interleaved_writer.Output(&output_string);
354  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
355  ExpectByte(0x11);  // Source segment size: dictionary length
356  ExpectByte(0x00);  // Source segment position: start of dictionary
357  ExpectByte(0x0E);  // Length of the delta encoding
358  ExpectByte(0x0E);  // Size of the target window
359  ExpectByte(0x00);  // Delta_indicator (no compression)
360  ExpectByte(0x00);  // length of data for ADDs and RUNs
361  ExpectByte(0x09);  // length of instructions section
362  ExpectByte(0x00);  // length of addresses for COPYs
363  ExpectByte(0xAD);  // Combo: Add size 4 + COPY mode SELF, size 5
364  ExpectString("rayo");
365  ExpectByte(0x02);  // COPY address (2)
366  ExpectByte(0xFD);  // Combo: COPY mode SAME(0), size 4 + Add size 1
367  ExpectByte(0x00);  // COPY address (0)
368  ExpectByte('X');
369  ExpectNoMoreBytes();
370}
371
372TEST_F(CodeTableWriterTest, InterleavedWriterEncodeComboWithChecksum) {
373  EXPECT_TRUE(interleaved_writer.Init(0x11));
374  const VCDChecksum checksum = 0xFFFFFFFF;  // would be negative if signed
375  interleaved_writer.AddChecksum(checksum);
376  interleaved_writer.Add("rayo", 4);
377  interleaved_writer.Copy(2, 5);
378  interleaved_writer.Copy(0, 4);
379  interleaved_writer.Add("X", 1);
380  interleaved_writer.Output(&output_string);
381  ExpectByte(VCD_SOURCE | VCD_CHECKSUM);  // Win_Indicator
382  ExpectByte(0x11);  // Source segment size: dictionary length
383  ExpectByte(0x00);  // Source segment position: start of dictionary
384  ExpectByte(0x13);  // Length of the delta encoding
385  ExpectByte(0x0E);  // Size of the target window
386  ExpectByte(0x00);  // Delta_indicator (no compression)
387  ExpectByte(0x00);  // length of data for ADDs and RUNs
388  ExpectByte(0x09);  // length of instructions section
389  ExpectByte(0x00);  // length of addresses for COPYs
390  ExpectByte(0x8F);  // checksum byte 1
391  ExpectByte(0xFF);  // checksum byte 2
392  ExpectByte(0xFF);  // checksum byte 3
393  ExpectByte(0xFF);  // checksum byte 4
394  ExpectByte(0x7F);  // checksum byte 5
395  ExpectByte(0xAD);  // Combo: Add size 4 + COPY mode SELF, size 5
396  ExpectString("rayo");
397  ExpectByte(0x02);  // COPY address (2)
398  ExpectByte(0xFD);  // Combo: COPY mode SAME(0), size 4 + Add size 1
399  ExpectByte(0x00);  // COPY address (0)
400  ExpectByte('X');
401  ExpectNoMoreBytes();
402}
403
404TEST_F(CodeTableWriterTest, ReallyBigDictionary) {
405  EXPECT_TRUE(interleaved_writer.Init(0x3FFFFFFF));
406  interleaved_writer.Copy(2, 8);
407  interleaved_writer.Copy(0x3FFFFFFE, 8);
408  interleaved_writer.Output(&output_string);
409  ExpectByte(VCD_SOURCE);  // Win_Indicator: VCD_SOURCE (dictionary)
410  ExpectByte(0x83);  // Source segment size: dictionary length (1)
411  ExpectByte(0xFF);  // Source segment size: dictionary length (2)
412  ExpectByte(0xFF);  // Source segment size: dictionary length (3)
413  ExpectByte(0xFF);  // Source segment size: dictionary length (4)
414  ExpectByte(0x7F);  // Source segment size: dictionary length (5)
415  ExpectByte(0x00);  // Source segment position: start of dictionary
416  ExpectByte(0x09);  // Length of the delta encoding
417  ExpectByte(0x10);  // Size of the target window
418  ExpectByte(0x00);  // Delta_indicator (no compression)
419  ExpectByte(0x00);  // length of data for ADDs and RUNs
420  ExpectByte(0x04);  // length of instructions section
421  ExpectByte(0x00);  // length of addresses for COPYs
422  ExpectByte(0x18);  // COPY mode SELF, size 8
423  ExpectByte(0x02);  // COPY address (2)
424  ExpectByte(0x28);  // COPY mode HERE, size 8
425  ExpectByte(0x09);  // COPY address (9)
426  ExpectNoMoreBytes();
427}
428
429#ifdef GTEST_HAS_DEATH_TEST
430TEST_F(CodeTableWriterDeathTest, DictionaryTooBig) {
431  EXPECT_TRUE(interleaved_writer.Init(0x7FFFFFFF));
432  interleaved_writer.Copy(2, 8);
433  EXPECT_DEBUG_DEATH(interleaved_writer.Copy(0x7FFFFFFE, 8),
434                     "address.*<.*here_address");
435}
436#endif  // GTEST_HAS_DEATH_TEST
437
438}  // unnamed namespace
439}  // namespace open_vcdiff
440