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