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