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
27namespace open_vcdiff {
28namespace {
29
30class DecodeTableTest : public testing::Test {
31 protected:
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
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
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
88  static void TearDownTestCase() {
89    delete g_exercise_code_table_;
90  }
91
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
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
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
164VCDiffCodeTableData* DecodeTableTest::g_exercise_code_table_ = NULL;
165
166const int DecodeTableTest::instruction_buffer_size =
167    VCDiffCodeTableData::kCodeTableSize *
168        (1 + (VarintBE<VCDAddress>::kMaxBytes));
169
170TEST_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
180TEST_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
190TEST_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
200TEST_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
214TEST_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
229TEST_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
246TEST_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
264TEST_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
285TEST_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
307TEST_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
318TEST_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
337TEST_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
390TEST_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