Home | History | Annotate | Download | only in src
      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