• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
28 namespace open_vcdiff {
29 
VCDiffInstructionName(VCDiffInstructionType inst)30 const 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       VCD_ERROR << "Unexpected instruction type " << inst << VCD_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 //
54 const 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 
ValidateOpcode(int opcode,unsigned char inst,unsigned char size,unsigned char mode,unsigned char max_mode,const char * first_or_second)188 bool 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     VCD_ERROR << "VCDiff: Bad code table; opcode " << opcode << " has invalid "
199               << first_or_second << " instruction type "
200               << static_cast<int>(inst) << VCD_ENDL;
201     no_errors_found = false;
202   }
203   if (mode > max_mode) {
204     VCD_ERROR << "VCDiff: Bad code table; opcode " << opcode << " has invalid "
205               << first_or_second << " mode "
206               << static_cast<int>(mode) << VCD_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     VCD_ERROR << "VCDiff: Bad code table; opcode " << opcode << " has "
213               << first_or_second << " instruction NOOP with nonzero size "
214               << static_cast<int>(size) << VCD_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     VCD_ERROR << "VCDiff: Bad code table; opcode " << opcode
220               << " has non-COPY "
221               << first_or_second << " instruction with nonzero mode "
222               << static_cast<int>(mode) << VCD_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 //
Validate(unsigned char max_mode) const233 bool 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         VCD_ERROR << "VCDiff: Bad code table; there is no opcode for inst "
263                      "COPY, size 0, mode " << (i - VCD_COPY) << VCD_ENDL;
264       } else {
265         VCD_ERROR << "VCDiff: Bad code table; there is no opcode for inst "
266             << VCDiffInstructionName(static_cast<VCDiffInstructionType>(i))
267             << ", size 0,  mode 0" << VCD_ENDL;
268       }
269       no_errors_found = false;
270     }
271   }
272   return no_errors_found;
273 }
274 
Validate() const275 bool VCDiffCodeTableData::Validate() const {
276   return Validate(VCDiffAddressCache::DefaultLastMode());
277 }
278 
279 }  // namespace open_vcdiff
280