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 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 47 virtual ~CodeTableWriterTest() { } 48 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 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 98 static void TearDownTestCase() { 99 delete g_exercise_code_table_; 100 } 101 102 void ExpectByte(unsigned char b) { 103 EXPECT_EQ(b, static_cast<unsigned char>(out[out_index])); 104 ++out_index; 105 } 106 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 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 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 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 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. 180 TEST_F(CodeTableWriterTest, WriterOutputWithoutInit) { 181 standard_writer.Output(&output_string); 182 EXPECT_TRUE(out.empty()); 183 } 184 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 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 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 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 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 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. 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 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 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 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 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 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
