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