diff options
Diffstat (limited to 'src/codetable.cc')
| -rw-r--r-- | src/codetable.cc | 279 |
1 files changed, 279 insertions, 0 deletions
diff --git a/src/codetable.cc b/src/codetable.cc new file mode 100644 index 0000000..45b3c78 --- /dev/null +++ b/src/codetable.cc @@ -0,0 +1,279 @@ +// 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: + VCD_ERROR << "Unexpected instruction type " << inst << VCD_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) { + VCD_ERROR << "VCDiff: Bad code table; opcode " << opcode << " has invalid " + << first_or_second << " instruction type " + << static_cast<int>(inst) << VCD_ENDL; + no_errors_found = false; + } + if (mode > max_mode) { + VCD_ERROR << "VCDiff: Bad code table; opcode " << opcode << " has invalid " + << first_or_second << " mode " + << static_cast<int>(mode) << VCD_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)) { + VCD_ERROR << "VCDiff: Bad code table; opcode " << opcode << " has " + << first_or_second << " instruction NOOP with nonzero size " + << static_cast<int>(size) << VCD_ENDL; + no_errors_found = false; + } + // A nonzero mode can only be used with a COPY instruction + if ((inst != VCD_COPY) && (mode != 0)) { + VCD_ERROR << "VCDiff: Bad code table; opcode " << opcode + << " has non-COPY " + << first_or_second << " instruction with nonzero mode " + << static_cast<int>(mode) << VCD_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) { + VCD_ERROR << "VCDiff: Bad code table; there is no opcode for inst " + "COPY, size 0, mode " << (i - VCD_COPY) << VCD_ENDL; + } else { + VCD_ERROR << "VCDiff: Bad code table; there is no opcode for inst " + << VCDiffInstructionName(static_cast<VCDiffInstructionType>(i)) + << ", size 0, mode 0" << VCD_ENDL; + } + no_errors_found = false; + } + } + return no_errors_found; +} + +bool VCDiffCodeTableData::Validate() const { + return Validate(VCDiffAddressCache::DefaultLastMode()); +} + +} // namespace open_vcdiff |