• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
30 namespace open_vcdiff {
31 namespace {
32 
33 class CodeTableWriterTest : public testing::Test {
34  protected:
35   typedef std::string string;
36 
CodeTableWriterTest()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 
~CodeTableWriterTest()47   virtual ~CodeTableWriterTest() { }
48 
AddExerciseOpcode(unsigned char inst1,unsigned char mode1,unsigned char size1,unsigned char inst2,unsigned char mode2,unsigned char size2,int opcode)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 
SetUpTestCase()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 
TearDownTestCase()98   static void TearDownTestCase() {
99     delete g_exercise_code_table_;
100   }
101 
ExpectByte(unsigned char b)102   void ExpectByte(unsigned char b) {
103     EXPECT_EQ(b, static_cast<unsigned char>(out[out_index]));
104     ++out_index;
105   }
106 
ExpectString(const char * s)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 
ExpectNoMoreBytes()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 
147 VCDiffCodeTableData* CodeTableWriterTest::g_exercise_code_table_;
148 
149 #ifdef GTEST_HAS_DEATH_TEST
150 typedef CodeTableWriterTest CodeTableWriterDeathTest;
151 #endif  // GTEST_HAS_DEATH_TEST
152 
153 #ifdef GTEST_HAS_DEATH_TEST
TEST_F(CodeTableWriterDeathTest,WriterAddWithoutInit)154 TEST_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 
TEST_F(CodeTableWriterDeathTest,WriterRunWithoutInit)162 TEST_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 
TEST_F(CodeTableWriterDeathTest,WriterCopyWithoutInit)170 TEST_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.
TEST_F(CodeTableWriterTest,WriterOutputWithoutInit)180 TEST_F(CodeTableWriterTest, WriterOutputWithoutInit) {
181   standard_writer.Output(&output_string);
182   EXPECT_TRUE(out.empty());
183 }
184 
TEST_F(CodeTableWriterTest,WriterEncodeNothing)185 TEST_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 
TEST_F(CodeTableWriterTest,StandardWriterEncodeAdd)203 TEST_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 
TEST_F(CodeTableWriterTest,ExerciseWriterEncodeAdd)221 TEST_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 
TEST_F(CodeTableWriterTest,StandardWriterEncodeRun)239 TEST_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 
TEST_F(CodeTableWriterTest,ExerciseWriterEncodeRun)258 TEST_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 
TEST_F(CodeTableWriterTest,StandardWriterEncodeCopy)277 TEST_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.
TEST_F(CodeTableWriterTest,InterleavedWriterEncodeCopy)302 TEST_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 
TEST_F(CodeTableWriterTest,StandardWriterEncodeCombo)323 TEST_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 
TEST_F(CodeTableWriterTest,InterleavedWriterEncodeCombo)347 TEST_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 
TEST_F(CodeTableWriterTest,InterleavedWriterEncodeComboWithChecksum)372 TEST_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 
TEST_F(CodeTableWriterTest,ReallyBigDictionary)404 TEST_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
TEST_F(CodeTableWriterDeathTest,DictionaryTooBig)430 TEST_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