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 VCDiffCodeTableReader, found in decodetable.h.
17
18 #include <config.h>
19 #include "decodetable.h"
20 #include <stdint.h> // int32_t
21 #include <vector>
22 #include "addrcache.h"
23 #include "codetable.h"
24 #include "testing.h"
25 #include "varint_bigendian.h"
26
27 namespace open_vcdiff {
28 namespace {
29
30 class DecodeTableTest : public testing::Test {
31 protected:
DecodeTableTest()32 DecodeTableTest()
33 : instructions_and_sizes_(instruction_buffer_size),
34 found_size_(0),
35 found_mode_(0) {
36 instructions_and_sizes_ptr_ = &instructions_and_sizes_[0];
37 reader_.Init(&instructions_and_sizes_ptr_,
38 instructions_and_sizes_ptr_ + instruction_buffer_size);
39 }
40
AddExerciseOpcode(unsigned char inst1,unsigned char mode1,unsigned char size1,unsigned char inst2,unsigned char mode2,unsigned char size2,int opcode)41 static void AddExerciseOpcode(unsigned char inst1,
42 unsigned char mode1,
43 unsigned char size1,
44 unsigned char inst2,
45 unsigned char mode2,
46 unsigned char size2,
47 int opcode) {
48 g_exercise_code_table_->inst1[opcode] = inst1;
49 g_exercise_code_table_->mode1[opcode] = mode1;
50 g_exercise_code_table_->size1[opcode] = (inst1 == VCD_NOOP) ? 0 : size1;
51 g_exercise_code_table_->inst2[opcode] = inst2;
52 g_exercise_code_table_->mode2[opcode] = mode2;
53 g_exercise_code_table_->size2[opcode] = (inst2 == VCD_NOOP) ? 0 : size2;
54 }
55
SetUpTestCase()56 static void SetUpTestCase() {
57 g_exercise_code_table_ = new VCDiffCodeTableData;
58 int opcode = 0;
59 for (unsigned char inst_mode1 = 0;
60 inst_mode1 <= VCD_LAST_INSTRUCTION_TYPE + kLastExerciseMode;
61 ++inst_mode1) {
62 unsigned char inst1 = inst_mode1;
63 unsigned char mode1 = 0;
64 if (inst_mode1 > VCD_COPY) {
65 inst1 = VCD_COPY;
66 mode1 = inst_mode1 - VCD_COPY;
67 }
68 for (unsigned char inst_mode2 = 0;
69 inst_mode2 <= VCD_LAST_INSTRUCTION_TYPE + kLastExerciseMode;
70 ++inst_mode2) {
71 unsigned char inst2 = inst_mode2;
72 unsigned char mode2 = 0;
73 if (inst_mode2 > VCD_COPY) {
74 inst2 = VCD_COPY;
75 mode2 = inst_mode2 - VCD_COPY;
76 }
77 AddExerciseOpcode(inst1, mode1, 0, inst2, mode2, 0, opcode++);
78 AddExerciseOpcode(inst1, mode1, 0, inst2, mode2, 255, opcode++);
79 AddExerciseOpcode(inst1, mode1, 255, inst2, mode2, 0, opcode++);
80 AddExerciseOpcode(inst1, mode1, 255, inst2, mode2, 255, opcode++);
81 }
82 }
83 CHECK_EQ(VCDiffCodeTableData::kCodeTableSize, opcode);
84 EXPECT_TRUE(VCDiffCodeTableData::kDefaultCodeTableData.Validate());
85 EXPECT_TRUE(g_exercise_code_table_->Validate(kLastExerciseMode));
86 }
87
TearDownTestCase()88 static void TearDownTestCase() {
89 delete g_exercise_code_table_;
90 }
91
VerifyInstModeSize(unsigned char inst,unsigned char mode,unsigned char size,unsigned char opcode)92 void VerifyInstModeSize(unsigned char inst,
93 unsigned char mode,
94 unsigned char size,
95 unsigned char opcode) {
96 if (inst == VCD_NOOP) return; // GetNextInstruction skips NOOPs
97 int32_t found_size = 0;
98 unsigned char found_mode = 0;
99 unsigned char found_inst = reader_.GetNextInstruction(&found_size,
100 &found_mode);
101 EXPECT_EQ(inst, found_inst);
102 EXPECT_EQ(mode, found_mode);
103 if (size == 0) {
104 EXPECT_EQ(1000 + opcode, found_size);
105 } else {
106 EXPECT_EQ(size, found_size);
107 }
108 }
109
VerifyInstModeSize1(unsigned char inst,unsigned char mode,unsigned char size,unsigned char opcode)110 void VerifyInstModeSize1(unsigned char inst,
111 unsigned char mode,
112 unsigned char size,
113 unsigned char opcode) {
114 if (inst == VCD_NOOP) size = 0;
115 EXPECT_EQ(g_exercise_code_table_->inst1[opcode], inst);
116 EXPECT_EQ(g_exercise_code_table_->mode1[opcode], mode);
117 EXPECT_EQ(g_exercise_code_table_->size1[opcode], size);
118 VerifyInstModeSize(inst, mode, size, opcode);
119 }
120
VerifyInstModeSize2(unsigned char inst,unsigned char mode,unsigned char size,unsigned char opcode)121 void VerifyInstModeSize2(unsigned char inst,
122 unsigned char mode,
123 unsigned char size,
124 unsigned char opcode) {
125 if (inst == VCD_NOOP) size = 0;
126 EXPECT_EQ(g_exercise_code_table_->inst2[opcode], inst);
127 EXPECT_EQ(g_exercise_code_table_->mode2[opcode], mode);
128 EXPECT_EQ(g_exercise_code_table_->size2[opcode], size);
129 VerifyInstModeSize(inst, mode, size, opcode);
130 }
131
132 // This value is designed so that the total number of inst values and modes
133 // will equal 8 (VCD_NOOP, VCD_ADD, VCD_RUN, VCD_COPY modes 0 - 4).
134 // Eight combinations of inst and mode, times two possible size values,
135 // squared (because there are two instructions per opcode), makes
136 // exactly 256 possible instruction combinations, which fits kCodeTableSize
137 // (the number of opcodes in the table.)
138 static const int kLastExerciseMode = 4;
139
140 // The buffer size (in bytes) needed to store kCodeTableSize opcodes plus
141 // up to kCodeTableSize VarintBE-encoded size values.
142 static const int instruction_buffer_size;
143
144 // A code table that exercises as many combinations as possible:
145 // 2 instructions, each is a NOOP, ADD, RUN, or one of 5 copy modes
146 // (== 8 total combinations of inst and mode), and each has
147 // size == 0 or 255 (2 possibilities.)
148 static VCDiffCodeTableData* g_exercise_code_table_;
149
150 VCDiffCodeTableReader reader_;
151
152 // A buffer to which instructions and sizes will be added manually
153 // in order to exercise VCDiffCodeTableReader.
154 std::vector<char> instructions_and_sizes_;
155
156 // The buffer pointer used by the VCDiffCodeTableReader.
157 const char* instructions_and_sizes_ptr_;
158
159 // The size and mode returned by GetNextInstruction().
160 int32_t found_size_;
161 unsigned char found_mode_;
162 };
163
164 VCDiffCodeTableData* DecodeTableTest::g_exercise_code_table_ = NULL;
165
166 const int DecodeTableTest::instruction_buffer_size =
167 VCDiffCodeTableData::kCodeTableSize *
168 (1 + (VarintBE<VCDAddress>::kMaxBytes));
169
TEST_F(DecodeTableTest,ReadAdd)170 TEST_F(DecodeTableTest, ReadAdd) {
171 instructions_and_sizes_[0] = 1;
172 VarintBE<VCDAddress>::Encode(257, &instructions_and_sizes_[1]);
173 unsigned char found_inst = reader_.GetNextInstruction(&found_size_,
174 &found_mode_);
175 EXPECT_EQ(VCD_ADD, found_inst);
176 EXPECT_EQ(257, found_size_);
177 EXPECT_EQ(0, found_mode_);
178 }
179
TEST_F(DecodeTableTest,ReadRun)180 TEST_F(DecodeTableTest, ReadRun) {
181 instructions_and_sizes_[0] = 0;
182 VarintBE<VCDAddress>::Encode(111, &instructions_and_sizes_[1]);
183 unsigned char found_inst = reader_.GetNextInstruction(&found_size_,
184 &found_mode_);
185 EXPECT_EQ(VCD_RUN, found_inst);
186 EXPECT_EQ(111, found_size_);
187 EXPECT_EQ(0, found_mode_);
188 }
189
TEST_F(DecodeTableTest,ReadCopy)190 TEST_F(DecodeTableTest, ReadCopy) {
191 instructions_and_sizes_[0] = 58;
192 instructions_and_sizes_[1] = 0;
193 unsigned char found_inst = reader_.GetNextInstruction(&found_size_,
194 &found_mode_);
195 EXPECT_EQ(VCD_COPY, found_inst);
196 EXPECT_EQ(10, found_size_);
197 EXPECT_EQ(2, found_mode_);
198 }
199
TEST_F(DecodeTableTest,ReadAddCopy)200 TEST_F(DecodeTableTest, ReadAddCopy) {
201 instructions_and_sizes_[0] = 175;
202 instructions_and_sizes_[1] = 0;
203 unsigned char found_inst = reader_.GetNextInstruction(&found_size_,
204 &found_mode_);
205 EXPECT_EQ(VCD_ADD, found_inst);
206 EXPECT_EQ(1, found_size_);
207 EXPECT_EQ(0, found_mode_);
208 found_inst = reader_.GetNextInstruction(&found_size_, &found_mode_);
209 EXPECT_EQ(VCD_COPY, found_inst);
210 EXPECT_EQ(4, found_size_);
211 EXPECT_EQ(1, found_mode_);
212 }
213
TEST_F(DecodeTableTest,ReadCopyAdd)214 TEST_F(DecodeTableTest, ReadCopyAdd) {
215 instructions_and_sizes_[0] = 255;
216 instructions_and_sizes_[1] = 0;
217 unsigned char found_inst = reader_.GetNextInstruction(&found_size_,
218 &found_mode_);
219 EXPECT_EQ(VCD_COPY, found_inst);
220 EXPECT_EQ(4, found_size_);
221 EXPECT_EQ(8, found_mode_);
222 found_mode_ = 0;
223 found_inst = reader_.GetNextInstruction(&found_size_, &found_mode_);
224 EXPECT_EQ(VCD_ADD, found_inst);
225 EXPECT_EQ(1, found_size_);
226 EXPECT_EQ(0, found_mode_);
227 }
228
TEST_F(DecodeTableTest,UnGetAdd)229 TEST_F(DecodeTableTest, UnGetAdd) {
230 instructions_and_sizes_[0] = 1;
231 instructions_and_sizes_[1] = 255;
232 VarintBE<VCDAddress>::Encode(257, &instructions_and_sizes_[1]);
233 unsigned char found_inst = reader_.GetNextInstruction(&found_size_,
234 &found_mode_);
235 EXPECT_EQ(VCD_ADD, found_inst);
236 EXPECT_EQ(257, found_size_);
237 EXPECT_EQ(0, found_mode_);
238 reader_.UnGetInstruction();
239 found_size_ = 0;
240 found_inst = reader_.GetNextInstruction(&found_size_, &found_mode_);
241 EXPECT_EQ(VCD_ADD, found_inst);
242 EXPECT_EQ(257, found_size_);
243 EXPECT_EQ(0, found_mode_);
244 }
245
TEST_F(DecodeTableTest,UnGetCopy)246 TEST_F(DecodeTableTest, UnGetCopy) {
247 instructions_and_sizes_[0] = 58;
248 instructions_and_sizes_[1] = 0;
249 instructions_and_sizes_[2] = 255;
250 unsigned char found_inst = reader_.GetNextInstruction(&found_size_,
251 &found_mode_);
252 EXPECT_EQ(VCD_COPY, found_inst);
253 EXPECT_EQ(10, found_size_);
254 EXPECT_EQ(2, found_mode_);
255 reader_.UnGetInstruction();
256 found_size_ = 0;
257 found_mode_ = 0;
258 found_inst = reader_.GetNextInstruction(&found_size_, &found_mode_);
259 EXPECT_EQ(VCD_COPY, found_inst);
260 EXPECT_EQ(10, found_size_);
261 EXPECT_EQ(2, found_mode_);
262 }
263
TEST_F(DecodeTableTest,UnGetCopyAdd)264 TEST_F(DecodeTableTest, UnGetCopyAdd) {
265 instructions_and_sizes_[0] = 255;
266 instructions_and_sizes_[1] = 0;
267 unsigned char found_inst = reader_.GetNextInstruction(&found_size_,
268 &found_mode_);
269 EXPECT_EQ(VCD_COPY, found_inst);
270 EXPECT_EQ(4, found_size_);
271 EXPECT_EQ(8, found_mode_);
272 reader_.UnGetInstruction();
273 found_mode_ = 0;
274 found_inst = reader_.GetNextInstruction(&found_size_, &found_mode_);
275 EXPECT_EQ(VCD_COPY, found_inst);
276 EXPECT_EQ(4, found_size_);
277 EXPECT_EQ(8, found_mode_);
278 found_mode_ = 0;
279 found_inst = reader_.GetNextInstruction(&found_size_, &found_mode_);
280 EXPECT_EQ(VCD_ADD, found_inst);
281 EXPECT_EQ(1, found_size_);
282 EXPECT_EQ(0, found_mode_);
283 }
284
TEST_F(DecodeTableTest,UnGetTwice)285 TEST_F(DecodeTableTest, UnGetTwice) {
286 instructions_and_sizes_[0] = 255;
287 instructions_and_sizes_[1] = 0;
288 unsigned char found_inst = reader_.GetNextInstruction(&found_size_,
289 &found_mode_);
290 EXPECT_EQ(VCD_COPY, found_inst);
291 EXPECT_EQ(4, found_size_);
292 EXPECT_EQ(8, found_mode_);
293 reader_.UnGetInstruction();
294 reader_.UnGetInstruction();
295 found_mode_ = 0;
296 found_inst = reader_.GetNextInstruction(&found_size_, &found_mode_);
297 EXPECT_EQ(VCD_COPY, found_inst);
298 EXPECT_EQ(4, found_size_);
299 EXPECT_EQ(8, found_mode_);
300 found_mode_ = 0;
301 found_inst = reader_.GetNextInstruction(&found_size_, &found_mode_);
302 EXPECT_EQ(VCD_ADD, found_inst);
303 EXPECT_EQ(1, found_size_);
304 EXPECT_EQ(0, found_mode_);
305 }
306
TEST_F(DecodeTableTest,UnGetBeforeGet)307 TEST_F(DecodeTableTest, UnGetBeforeGet) {
308 instructions_and_sizes_[0] = 255;
309 instructions_and_sizes_[1] = 0;
310 reader_.UnGetInstruction();
311 unsigned char found_inst = reader_.GetNextInstruction(&found_size_,
312 &found_mode_);
313 EXPECT_EQ(VCD_COPY, found_inst);
314 EXPECT_EQ(4, found_size_);
315 EXPECT_EQ(8, found_mode_);
316 }
317
TEST_F(DecodeTableTest,UnGetAddCopy)318 TEST_F(DecodeTableTest, UnGetAddCopy) {
319 instructions_and_sizes_[0] = 175;
320 instructions_and_sizes_[1] = 0;
321 unsigned char found_inst = reader_.GetNextInstruction(&found_size_,
322 &found_mode_);
323 EXPECT_EQ(VCD_ADD, found_inst);
324 EXPECT_EQ(1, found_size_);
325 EXPECT_EQ(0, found_mode_);
326 reader_.UnGetInstruction();
327 found_inst = reader_.GetNextInstruction(&found_size_, &found_mode_);
328 EXPECT_EQ(VCD_ADD, found_inst);
329 EXPECT_EQ(1, found_size_);
330 EXPECT_EQ(0, found_mode_);
331 found_inst = reader_.GetNextInstruction(&found_size_, &found_mode_);
332 EXPECT_EQ(VCD_COPY, found_inst);
333 EXPECT_EQ(4, found_size_);
334 EXPECT_EQ(1, found_mode_);
335 }
336
TEST_F(DecodeTableTest,ReReadIncomplete)337 TEST_F(DecodeTableTest, ReReadIncomplete) {
338 instructions_and_sizes_[0] = 175; // Add(1) + Copy1(4)
339 instructions_and_sizes_[1] = 1; // Add(0)
340 instructions_and_sizes_[2] = 111; // with size 111
341 instructions_and_sizes_[3] = 255; // Copy8(4) + Add(1)
342
343 reader_.Init(&instructions_and_sizes_ptr_,
344 instructions_and_sizes_ptr_ + 0); // 0 bytes available
345 EXPECT_EQ(VCD_INSTRUCTION_END_OF_DATA,
346 reader_.GetNextInstruction(&found_size_, &found_mode_));
347 EXPECT_EQ(&instructions_and_sizes_[0], instructions_and_sizes_ptr_);
348
349 reader_.Init(&instructions_and_sizes_ptr_,
350 instructions_and_sizes_ptr_ + 1); // 1 more byte available
351 EXPECT_EQ(VCD_ADD, reader_.GetNextInstruction(&found_size_, &found_mode_));
352 EXPECT_EQ(1, found_size_);
353 EXPECT_EQ(0, found_mode_);
354 EXPECT_EQ(VCD_COPY, reader_.GetNextInstruction(&found_size_, &found_mode_));
355 EXPECT_EQ(4, found_size_);
356 EXPECT_EQ(1, found_mode_);
357 EXPECT_EQ(VCD_INSTRUCTION_END_OF_DATA,
358 reader_.GetNextInstruction(&found_size_, &found_mode_));
359 EXPECT_EQ(&instructions_and_sizes_[1], instructions_and_sizes_ptr_);
360
361 reader_.Init(&instructions_and_sizes_ptr_,
362 instructions_and_sizes_ptr_ + 1); // 1 more byte available
363 // The opcode is available, but the separately encoded size is not
364 EXPECT_EQ(VCD_INSTRUCTION_END_OF_DATA,
365 reader_.GetNextInstruction(&found_size_, &found_mode_));
366 EXPECT_EQ(&instructions_and_sizes_[1], instructions_and_sizes_ptr_);
367
368 reader_.Init(&instructions_and_sizes_ptr_,
369 instructions_and_sizes_ptr_ + 2); // 2 more bytes available
370 EXPECT_EQ(VCD_ADD, reader_.GetNextInstruction(&found_size_, &found_mode_));
371 EXPECT_EQ(111, found_size_);
372 EXPECT_EQ(0, found_mode_);
373 EXPECT_EQ(VCD_INSTRUCTION_END_OF_DATA,
374 reader_.GetNextInstruction(&found_size_, &found_mode_));
375 EXPECT_EQ(&instructions_and_sizes_[3], instructions_and_sizes_ptr_);
376
377 reader_.Init(&instructions_and_sizes_ptr_,
378 instructions_and_sizes_ptr_ + 1); // 1 more byte available
379 EXPECT_EQ(VCD_COPY, reader_.GetNextInstruction(&found_size_, &found_mode_));
380 EXPECT_EQ(4, found_size_);
381 EXPECT_EQ(8, found_mode_);
382 EXPECT_EQ(VCD_ADD, reader_.GetNextInstruction(&found_size_, &found_mode_));
383 EXPECT_EQ(1, found_size_);
384 EXPECT_EQ(0, found_mode_);
385 EXPECT_EQ(VCD_INSTRUCTION_END_OF_DATA,
386 reader_.GetNextInstruction(&found_size_, &found_mode_));
387 EXPECT_EQ(&instructions_and_sizes_[4], instructions_and_sizes_ptr_);
388 }
389
TEST_F(DecodeTableTest,ExerciseCodeTableReader)390 TEST_F(DecodeTableTest, ExerciseCodeTableReader) {
391 char* instruction_ptr = &instructions_and_sizes_[0];
392 for (int opcode = 0; opcode < VCDiffCodeTableData::kCodeTableSize; ++opcode) {
393 *instruction_ptr = opcode;
394 ++instruction_ptr;
395 if ((g_exercise_code_table_->inst1[opcode] != VCD_NOOP) &&
396 (g_exercise_code_table_->size1[opcode] == 0)) {
397 // A separately-encoded size value
398 int encoded_size = VarintBE<VCDAddress>::Encode(1000 + opcode,
399 instruction_ptr);
400 EXPECT_LT(0, encoded_size);
401 instruction_ptr += encoded_size;
402 }
403 if ((g_exercise_code_table_->inst2[opcode] != VCD_NOOP) &&
404 (g_exercise_code_table_->size2[opcode] == 0)) {
405 int encoded_size = VarintBE<VCDAddress>::Encode(1000 + opcode,
406 instruction_ptr);
407 EXPECT_LT(0, encoded_size);
408 instruction_ptr += encoded_size;
409 }
410 }
411 EXPECT_TRUE(reader_.UseCodeTable(*g_exercise_code_table_, kLastExerciseMode));
412 int opcode = 0;
413 // This loop has the same bounds as the one in SetUpTestCase.
414 // Iterate over the instruction types and make sure that the opcodes,
415 // interpreted in order, return exactly those instruction types.
416 for (unsigned char inst_mode1 = 0;
417 inst_mode1 <= VCD_LAST_INSTRUCTION_TYPE + kLastExerciseMode;
418 ++inst_mode1) {
419 unsigned char inst1 = inst_mode1;
420 unsigned char mode1 = 0;
421 if (inst_mode1 > VCD_COPY) {
422 inst1 = VCD_COPY;
423 mode1 = inst_mode1 - VCD_COPY;
424 }
425 for (unsigned char inst_mode2 = 0;
426 inst_mode2 <= VCD_LAST_INSTRUCTION_TYPE + kLastExerciseMode;
427 ++inst_mode2) {
428 unsigned char inst2 = inst_mode2;
429 unsigned char mode2 = 0;
430 if (inst_mode2 > VCD_COPY) {
431 inst2 = VCD_COPY;
432 mode2 = inst_mode2 - VCD_COPY;
433 }
434 VerifyInstModeSize1(inst1, mode1, 0, opcode);
435 VerifyInstModeSize2(inst2, mode2, 0, opcode);
436 ++opcode;
437 VerifyInstModeSize1(inst1, mode1, 0, opcode);
438 VerifyInstModeSize2(inst2, mode2, 255, opcode);
439 ++opcode;
440 VerifyInstModeSize1(inst1, mode1, 255, opcode);
441 VerifyInstModeSize2(inst2, mode2, 0, opcode);
442 ++opcode;
443 VerifyInstModeSize1(inst1, mode1, 255, opcode);
444 VerifyInstModeSize2(inst2, mode2, 255, opcode);
445 ++opcode;
446 }
447 }
448 CHECK_EQ(VCDiffCodeTableData::kCodeTableSize, opcode);
449 }
450
451 } // unnamed namespace
452 } // namespace open_vcdiff
453