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// codetable.cc:
17//     Classes to implement the Code Table
18//     described in sections 5.5, 5.6 and 7 of
19//     RFC 3284 - The VCDIFF Generic Differencing and Compression Data Format.
20//     The RFC text can be found at http://www.faqs.org/rfcs/rfc3284.html
21
22#include <config.h>
23#include "addrcache.h"
24#include "codetable.h"
25#include "logging.h"
26#include "vcdiff_defs.h"  // VCD_MAX_MODES
27
28namespace open_vcdiff {
29
30const char* VCDiffInstructionName(VCDiffInstructionType inst) {
31  switch (inst) {
32    case VCD_NOOP:
33      return "NOOP";
34    case VCD_ADD:
35      return "ADD";
36    case VCD_RUN:
37      return "RUN";
38    case VCD_COPY:
39      return "COPY";
40    default:
41      LOG(ERROR) << "Unexpected instruction type " << inst << LOG_ENDL;
42      return "";
43  }
44}
45
46// This is the default code table defined in the RFC, section 5.6.
47// Using a static struct means that the compiler will do the work of
48// laying out the values in memory rather than having to use loops to do so
49// at runtime.  The letters "N", "A", "R", and "C" are defined as VCD_NOOP,
50// VCD_ADD, VCD_RUN, and VCD_COPY respectively (see the definition of
51// struct VCDiffCodeTableData), which allows for a compact
52// representation of the code table data.
53//
54const VCDiffCodeTableData VCDiffCodeTableData::kDefaultCodeTableData =
55    // inst1
56    { { R,  // opcode 0
57        A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,  // opcodes 1-18
58        C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C,  // opcodes 19-34
59        C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C,  // opcodes 35-50
60        C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C,  // opcodes 51-66
61        C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C,  // opcodes 67-82
62        C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C,  // opcodes 83-98
63        C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C,  // opcodes 99-114
64        C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C,  // opcodes 115-130
65        C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C,  // opcodes 131-146
66        C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C,  // opcodes 147-162
67        A, A, A, A, A, A, A, A, A, A, A, A,  // opcodes 163-174
68        A, A, A, A, A, A, A, A, A, A, A, A,  // opcodes 175-186
69        A, A, A, A, A, A, A, A, A, A, A, A,  // opcodes 187-198
70        A, A, A, A, A, A, A, A, A, A, A, A,  // opcodes 199-210
71        A, A, A, A, A, A, A, A, A, A, A, A,  // opcodes 211-222
72        A, A, A, A, A, A, A, A, A, A, A, A,  // opcodes 223-234
73        A, A, A, A,  // opcodes 235-238
74        A, A, A, A,  // opcodes 239-242
75        A, A, A, A,  // opcodes 243-246
76        C, C, C, C, C, C, C, C, C },  // opcodes 247-255
77    // inst2
78      { N,  // opcode 0
79        N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,  // opcodes 1-18
80        N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,  // opcodes 19-34
81        N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,  // opcodes 35-50
82        N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,  // opcodes 51-66
83        N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,  // opcodes 67-82
84        N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,  // opcodes 83-98
85        N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,  // opcodes 99-114
86        N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,  // opcodes 115-130
87        N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,  // opcodes 131-146
88        N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,  // opcodes 147-162
89        C, C, C, C, C, C, C, C, C, C, C, C,  // opcodes 163-174
90        C, C, C, C, C, C, C, C, C, C, C, C,  // opcodes 175-186
91        C, C, C, C, C, C, C, C, C, C, C, C,  // opcodes 187-198
92        C, C, C, C, C, C, C, C, C, C, C, C,  // opcodes 199-210
93        C, C, C, C, C, C, C, C, C, C, C, C,  // opcodes 211-222
94        C, C, C, C, C, C, C, C, C, C, C, C,  // opcodes 223-234
95        C, C, C, C,  // opcodes 235-238
96        C, C, C, C,  // opcodes 239-242
97        C, C, C, C,  // opcodes 243-246
98        A, A, A, A, A, A, A, A, A },  // opcodes 247-255
99    // size1
100      { 0,  // opcode 0
101        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,  // 1-18
102        0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,  // 19-34
103        0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,  // 35-50
104        0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,  // 51-66
105        0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,  // 67-82
106        0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,  // 83-98
107        0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,  // 99-114
108        0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,  // 115-130
109        0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,  // 131-146
110        0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,  // 147-162
111        1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4,  // opcodes 163-174
112        1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4,  // opcodes 175-186
113        1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4,  // opcodes 187-198
114        1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4,  // opcodes 199-210
115        1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4,  // opcodes 211-222
116        1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4,  // opcodes 223-234
117        1, 2, 3, 4,  // opcodes 235-238
118        1, 2, 3, 4,  // opcodes 239-242
119        1, 2, 3, 4,  // opcodes 243-246
120        4, 4, 4, 4, 4, 4, 4, 4, 4 },  // opcodes 247-255
121    // size2
122      { 0,  // opcode 0
123        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 1-18
124        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 19-34
125        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 35-50
126        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 51-66
127        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 67-82
128        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 83-98
129        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 99-114
130        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 115-130
131        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 131-146
132        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 147-162
133        4, 5, 6, 4, 5, 6, 4, 5, 6, 4, 5, 6,  // opcodes 163-174
134        4, 5, 6, 4, 5, 6, 4, 5, 6, 4, 5, 6,  // opcodes 175-186
135        4, 5, 6, 4, 5, 6, 4, 5, 6, 4, 5, 6,  // opcodes 187-198
136        4, 5, 6, 4, 5, 6, 4, 5, 6, 4, 5, 6,  // opcodes 199-210
137        4, 5, 6, 4, 5, 6, 4, 5, 6, 4, 5, 6,  // opcodes 211-222
138        4, 5, 6, 4, 5, 6, 4, 5, 6, 4, 5, 6,  // opcodes 223-234
139        4, 4, 4, 4,  // opcodes 235-238
140        4, 4, 4, 4,  // opcodes 239-242
141        4, 4, 4, 4,  // opcodes 243-246
142        1, 1, 1, 1, 1, 1, 1, 1, 1 },  // opcodes 247-255
143    // mode1
144      { 0,  // opcode 0
145        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 1-18
146        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 19-34
147        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  // opcodes 35-50
148        2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,  // opcodes 51-66
149        3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,  // opcodes 67-82
150        4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,  // opcodes 83-98
151        5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,  // opcodes 99-114
152        6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,  // opcodes 115-130
153        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,  // opcodes 131-146
154        8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,  // opcodes 147-162
155        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 163-174
156        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 175-186
157        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 187-198
158        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 199-210
159        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 211-222
160        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 223-234
161        0, 0, 0, 0,  // opcodes 235-238
162        0, 0, 0, 0,  // opcodes 239-242
163        0, 0, 0, 0,  // opcodes 243-246
164        0, 1, 2, 3, 4, 5, 6, 7, 8 },  // opcodes 247-255
165    // mode2
166      { 0,  // opcode 0
167        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 1-18
168        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 19-34
169        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 35-50
170        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 51-66
171        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 67-82
172        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 83-98
173        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 99-114
174        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 115-130
175        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 131-146
176        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 147-162
177        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // opcodes 163-174
178        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  // opcodes 175-186
179        2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,  // opcodes 187-198
180        3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,  // opcodes 199-210
181        4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,  // opcodes 211-222
182        5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,  // opcodes 223-234
183        6, 6, 6, 6,  // opcodes 235-238
184        7, 7, 7, 7,  // opcodes 239-242
185        8, 8, 8, 8,  // opcodes 243-246
186        0, 0, 0, 0, 0, 0, 0, 0, 0 } };  // opcodes 247-255
187
188bool VCDiffCodeTableData::ValidateOpcode(int opcode,
189                                         unsigned char inst,
190                                         unsigned char size,
191                                         unsigned char mode,
192                                         unsigned char max_mode,
193                                         const char* first_or_second) {
194  bool no_errors_found = true;
195  // Check upper limits of inst and mode.  inst, size, and mode are
196  // unsigned, so there is no lower limit on them.
197  if (inst > VCD_LAST_INSTRUCTION_TYPE) {
198    LOG(ERROR) << "VCDiff: Bad code table; opcode " << opcode << " has invalid "
199               << first_or_second << " instruction type "
200               << static_cast<int>(inst) << LOG_ENDL;
201    no_errors_found = false;
202  }
203  if (mode > max_mode) {
204    LOG(ERROR) << "VCDiff: Bad code table; opcode " << opcode << " has invalid "
205               << first_or_second << " mode "
206               << static_cast<int>(mode) << LOG_ENDL;
207    no_errors_found = false;
208  }
209  // A NOOP instruction must have size 0
210  // (and mode 0, which is included in the next rule)
211  if ((inst == VCD_NOOP) && (size != 0)) {
212    LOG(ERROR) << "VCDiff: Bad code table; opcode " << opcode << " has "
213               << first_or_second << " instruction NOOP with nonzero size "
214               << static_cast<int>(size) << LOG_ENDL;
215    no_errors_found = false;
216  }
217  // A nonzero mode can only be used with a COPY instruction
218  if ((inst != VCD_COPY) && (mode != 0)) {
219    LOG(ERROR) << "VCDiff: Bad code table; opcode " << opcode
220               << " has non-COPY "
221               << first_or_second << " instruction with nonzero mode "
222               << static_cast<int>(mode) << LOG_ENDL;
223    no_errors_found = false;
224  }
225  return no_errors_found;
226}
227
228// If an error is found while validating, continue to validate the rest
229// of the code table so that all validation errors will appear in
230// the error log.  Otherwise the user would have to fix a single error
231// and then rerun validation to find the next error.
232//
233bool VCDiffCodeTableData::Validate(unsigned char max_mode) const {
234  const int kNumberOfTypesAndModes = VCD_LAST_INSTRUCTION_TYPE + max_mode + 1;
235  bool hasOpcodeForTypeAndMode[VCD_LAST_INSTRUCTION_TYPE + VCD_MAX_MODES];
236  bool no_errors_found = true;
237  for (int i = 0; i < kNumberOfTypesAndModes; ++i) {
238    hasOpcodeForTypeAndMode[i] = false;
239  }
240  for (int i = 0; i < kCodeTableSize; ++i) {
241    no_errors_found =
242        ValidateOpcode(i, inst1[i], size1[i], mode1[i], max_mode, "first")
243        && no_errors_found;  // use as 2nd operand to avoid short-circuit
244    no_errors_found =
245        ValidateOpcode(i, inst2[i], size2[i], mode2[i], max_mode, "second")
246        && no_errors_found;
247    // A valid code table must have an opcode to encode every possible
248    // combination of inst and mode with size=0 as its first instruction,
249    // and NOOP as its second instruction.  If this condition fails,
250    // then there exists a set of input instructions that cannot be encoded.
251    if ((size1[i] == 0) &&
252        (inst2[i] == VCD_NOOP) &&
253        ((static_cast<int>(inst1[i]) + static_cast<int>(mode1[i]))
254            < kNumberOfTypesAndModes)) {
255      hasOpcodeForTypeAndMode[inst1[i] + mode1[i]] = true;
256    }
257  }
258  for (int i = 0; i < kNumberOfTypesAndModes; ++i) {
259    if (i == VCD_NOOP) continue;
260    if (!hasOpcodeForTypeAndMode[i])  {
261      if (i >= VCD_COPY) {
262        LOG(ERROR) << "VCDiff: Bad code table; there is no opcode for inst "
263                      "COPY, size 0, mode " << (i - VCD_COPY) << LOG_ENDL;
264      } else {
265        LOG(ERROR) << "VCDiff: Bad code table; there is no opcode for inst "
266            << VCDiffInstructionName(static_cast<VCDiffInstructionType>(i))
267            << ", size 0,  mode 0" << LOG_ENDL;
268      }
269      no_errors_found = false;
270    }
271  }
272  return no_errors_found;
273}
274
275bool VCDiffCodeTableData::Validate() const {
276  return Validate(VCDiffAddressCache::DefaultLastMode());
277}
278
279}  // namespace open_vcdiff
280