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 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 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 // 233 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 275 bool VCDiffCodeTableData::Validate() const { 276 return Validate(VCDiffAddressCache::DefaultLastMode()); 277 } 278 279 } // namespace open_vcdiff 280
