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: 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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
