| // Copyright 2008 Google Inc. |
| // Author: Lincoln Smith |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| // |
| // codetable.cc: |
| // Classes to implement the Code Table |
| // described in sections 5.5, 5.6 and 7 of |
| // RFC 3284 - The VCDIFF Generic Differencing and Compression Data Format. |
| // The RFC text can be found at http://www.faqs.org/rfcs/rfc3284.html |
| |
| #include <config.h> |
| #include "addrcache.h" |
| #include "codetable.h" |
| #include "logging.h" |
| #include "vcdiff_defs.h" // VCD_MAX_MODES |
| |
| namespace open_vcdiff { |
| |
| const char* VCDiffInstructionName(VCDiffInstructionType inst) { |
| switch (inst) { |
| case VCD_NOOP: |
| return "NOOP"; |
| case VCD_ADD: |
| return "ADD"; |
| case VCD_RUN: |
| return "RUN"; |
| case VCD_COPY: |
| return "COPY"; |
| default: |
| LOG(ERROR) << "Unexpected instruction type " << inst << LOG_ENDL; |
| return ""; |
| } |
| } |
| |
| // This is the default code table defined in the RFC, section 5.6. |
| // Using a static struct means that the compiler will do the work of |
| // laying out the values in memory rather than having to use loops to do so |
| // at runtime. The letters "N", "A", "R", and "C" are defined as VCD_NOOP, |
| // VCD_ADD, VCD_RUN, and VCD_COPY respectively (see the definition of |
| // struct VCDiffCodeTableData), which allows for a compact |
| // representation of the code table data. |
| // |
| const VCDiffCodeTableData VCDiffCodeTableData::kDefaultCodeTableData = |
| // inst1 |
| { { R, // opcode 0 |
| A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, // opcodes 1-18 |
| C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, // opcodes 19-34 |
| C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, // opcodes 35-50 |
| C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, // opcodes 51-66 |
| C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, // opcodes 67-82 |
| C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, // opcodes 83-98 |
| C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, // opcodes 99-114 |
| C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, // opcodes 115-130 |
| C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, // opcodes 131-146 |
| C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, // opcodes 147-162 |
| A, A, A, A, A, A, A, A, A, A, A, A, // opcodes 163-174 |
| A, A, A, A, A, A, A, A, A, A, A, A, // opcodes 175-186 |
| A, A, A, A, A, A, A, A, A, A, A, A, // opcodes 187-198 |
| A, A, A, A, A, A, A, A, A, A, A, A, // opcodes 199-210 |
| A, A, A, A, A, A, A, A, A, A, A, A, // opcodes 211-222 |
| A, A, A, A, A, A, A, A, A, A, A, A, // opcodes 223-234 |
| A, A, A, A, // opcodes 235-238 |
| A, A, A, A, // opcodes 239-242 |
| A, A, A, A, // opcodes 243-246 |
| C, C, C, C, C, C, C, C, C }, // opcodes 247-255 |
| // inst2 |
| { N, // opcode 0 |
| N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, // opcodes 1-18 |
| N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, // opcodes 19-34 |
| N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, // opcodes 35-50 |
| N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, // opcodes 51-66 |
| N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, // opcodes 67-82 |
| N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, // opcodes 83-98 |
| N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, // opcodes 99-114 |
| N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, // opcodes 115-130 |
| N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, // opcodes 131-146 |
| N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, // opcodes 147-162 |
| C, C, C, C, C, C, C, C, C, C, C, C, // opcodes 163-174 |
| C, C, C, C, C, C, C, C, C, C, C, C, // opcodes 175-186 |
| C, C, C, C, C, C, C, C, C, C, C, C, // opcodes 187-198 |
| C, C, C, C, C, C, C, C, C, C, C, C, // opcodes 199-210 |
| C, C, C, C, C, C, C, C, C, C, C, C, // opcodes 211-222 |
| C, C, C, C, C, C, C, C, C, C, C, C, // opcodes 223-234 |
| C, C, C, C, // opcodes 235-238 |
| C, C, C, C, // opcodes 239-242 |
| C, C, C, C, // opcodes 243-246 |
| A, A, A, A, A, A, A, A, A }, // opcodes 247-255 |
| // size1 |
| { 0, // opcode 0 |
| 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, // 1-18 |
| 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, // 19-34 |
| 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, // 35-50 |
| 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, // 51-66 |
| 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, // 67-82 |
| 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, // 83-98 |
| 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, // 99-114 |
| 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, // 115-130 |
| 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, // 131-146 |
| 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, // 147-162 |
| 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, // opcodes 163-174 |
| 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, // opcodes 175-186 |
| 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, // opcodes 187-198 |
| 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, // opcodes 199-210 |
| 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, // opcodes 211-222 |
| 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, // opcodes 223-234 |
| 1, 2, 3, 4, // opcodes 235-238 |
| 1, 2, 3, 4, // opcodes 239-242 |
| 1, 2, 3, 4, // opcodes 243-246 |
| 4, 4, 4, 4, 4, 4, 4, 4, 4 }, // opcodes 247-255 |
| // size2 |
| { 0, // opcode 0 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 1-18 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 19-34 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 35-50 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 51-66 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 67-82 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 83-98 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 99-114 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 115-130 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 131-146 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 147-162 |
| 4, 5, 6, 4, 5, 6, 4, 5, 6, 4, 5, 6, // opcodes 163-174 |
| 4, 5, 6, 4, 5, 6, 4, 5, 6, 4, 5, 6, // opcodes 175-186 |
| 4, 5, 6, 4, 5, 6, 4, 5, 6, 4, 5, 6, // opcodes 187-198 |
| 4, 5, 6, 4, 5, 6, 4, 5, 6, 4, 5, 6, // opcodes 199-210 |
| 4, 5, 6, 4, 5, 6, 4, 5, 6, 4, 5, 6, // opcodes 211-222 |
| 4, 5, 6, 4, 5, 6, 4, 5, 6, 4, 5, 6, // opcodes 223-234 |
| 4, 4, 4, 4, // opcodes 235-238 |
| 4, 4, 4, 4, // opcodes 239-242 |
| 4, 4, 4, 4, // opcodes 243-246 |
| 1, 1, 1, 1, 1, 1, 1, 1, 1 }, // opcodes 247-255 |
| // mode1 |
| { 0, // opcode 0 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 1-18 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 19-34 |
| 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // opcodes 35-50 |
| 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, // opcodes 51-66 |
| 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, // opcodes 67-82 |
| 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, // opcodes 83-98 |
| 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, // opcodes 99-114 |
| 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, // opcodes 115-130 |
| 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // opcodes 131-146 |
| 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // opcodes 147-162 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 163-174 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 175-186 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 187-198 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 199-210 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 211-222 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 223-234 |
| 0, 0, 0, 0, // opcodes 235-238 |
| 0, 0, 0, 0, // opcodes 239-242 |
| 0, 0, 0, 0, // opcodes 243-246 |
| 0, 1, 2, 3, 4, 5, 6, 7, 8 }, // opcodes 247-255 |
| // mode2 |
| { 0, // opcode 0 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 1-18 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 19-34 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 35-50 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 51-66 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 67-82 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 83-98 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 99-114 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 115-130 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 131-146 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 147-162 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // opcodes 163-174 |
| 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // opcodes 175-186 |
| 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, // opcodes 187-198 |
| 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, // opcodes 199-210 |
| 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, // opcodes 211-222 |
| 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, // opcodes 223-234 |
| 6, 6, 6, 6, // opcodes 235-238 |
| 7, 7, 7, 7, // opcodes 239-242 |
| 8, 8, 8, 8, // opcodes 243-246 |
| 0, 0, 0, 0, 0, 0, 0, 0, 0 } }; // opcodes 247-255 |
| |
| bool VCDiffCodeTableData::ValidateOpcode(int opcode, |
| unsigned char inst, |
| unsigned char size, |
| unsigned char mode, |
| unsigned char max_mode, |
| const char* first_or_second) { |
| bool no_errors_found = true; |
| // Check upper limits of inst and mode. inst, size, and mode are |
| // unsigned, so there is no lower limit on them. |
| if (inst > VCD_LAST_INSTRUCTION_TYPE) { |
| LOG(ERROR) << "VCDiff: Bad code table; opcode " << opcode << " has invalid " |
| << first_or_second << " instruction type " |
| << static_cast<int>(inst) << LOG_ENDL; |
| no_errors_found = false; |
| } |
| if (mode > max_mode) { |
| LOG(ERROR) << "VCDiff: Bad code table; opcode " << opcode << " has invalid " |
| << first_or_second << " mode " |
| << static_cast<int>(mode) << LOG_ENDL; |
| no_errors_found = false; |
| } |
| // A NOOP instruction must have size 0 |
| // (and mode 0, which is included in the next rule) |
| if ((inst == VCD_NOOP) && (size != 0)) { |
| LOG(ERROR) << "VCDiff: Bad code table; opcode " << opcode << " has " |
| << first_or_second << " instruction NOOP with nonzero size " |
| << static_cast<int>(size) << LOG_ENDL; |
| no_errors_found = false; |
| } |
| // A nonzero mode can only be used with a COPY instruction |
| if ((inst != VCD_COPY) && (mode != 0)) { |
| LOG(ERROR) << "VCDiff: Bad code table; opcode " << opcode |
| << " has non-COPY " |
| << first_or_second << " instruction with nonzero mode " |
| << static_cast<int>(mode) << LOG_ENDL; |
| no_errors_found = false; |
| } |
| return no_errors_found; |
| } |
| |
| // If an error is found while validating, continue to validate the rest |
| // of the code table so that all validation errors will appear in |
| // the error log. Otherwise the user would have to fix a single error |
| // and then rerun validation to find the next error. |
| // |
| bool VCDiffCodeTableData::Validate(unsigned char max_mode) const { |
| const int kNumberOfTypesAndModes = VCD_LAST_INSTRUCTION_TYPE + max_mode + 1; |
| bool hasOpcodeForTypeAndMode[VCD_LAST_INSTRUCTION_TYPE + VCD_MAX_MODES]; |
| bool no_errors_found = true; |
| for (int i = 0; i < kNumberOfTypesAndModes; ++i) { |
| hasOpcodeForTypeAndMode[i] = false; |
| } |
| for (int i = 0; i < kCodeTableSize; ++i) { |
| no_errors_found = |
| ValidateOpcode(i, inst1[i], size1[i], mode1[i], max_mode, "first") |
| && no_errors_found; // use as 2nd operand to avoid short-circuit |
| no_errors_found = |
| ValidateOpcode(i, inst2[i], size2[i], mode2[i], max_mode, "second") |
| && no_errors_found; |
| // A valid code table must have an opcode to encode every possible |
| // combination of inst and mode with size=0 as its first instruction, |
| // and NOOP as its second instruction. If this condition fails, |
| // then there exists a set of input instructions that cannot be encoded. |
| if ((size1[i] == 0) && |
| (inst2[i] == VCD_NOOP) && |
| ((static_cast<int>(inst1[i]) + static_cast<int>(mode1[i])) |
| < kNumberOfTypesAndModes)) { |
| hasOpcodeForTypeAndMode[inst1[i] + mode1[i]] = true; |
| } |
| } |
| for (int i = 0; i < kNumberOfTypesAndModes; ++i) { |
| if (i == VCD_NOOP) continue; |
| if (!hasOpcodeForTypeAndMode[i]) { |
| if (i >= VCD_COPY) { |
| LOG(ERROR) << "VCDiff: Bad code table; there is no opcode for inst " |
| "COPY, size 0, mode " << (i - VCD_COPY) << LOG_ENDL; |
| } else { |
| LOG(ERROR) << "VCDiff: Bad code table; there is no opcode for inst " |
| << VCDiffInstructionName(static_cast<VCDiffInstructionType>(i)) |
| << ", size 0, mode 0" << LOG_ENDL; |
| } |
| no_errors_found = false; |
| } |
| } |
| return no_errors_found; |
| } |
| |
| bool VCDiffCodeTableData::Validate() const { |
| return Validate(VCDiffAddressCache::DefaultLastMode()); |
| } |
| |
| } // namespace open_vcdiff |
