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 // There are two different representations of a Code Table's contents: 17 // VCDiffCodeTableData is the same as the format given in section 7 18 // of the RFC, and is used for transmission and decoding. However, 19 // on the encoding side, it is useful to have a representation that 20 // can map efficiently from delta instructions to opcodes: 21 // VCDiffInstructionMap. A VCDiffInstructionMap is constructed 22 // using a VCDiffCodeTableData. For a custom code table, it is recommended 23 // that the VCDiffCodeTableData be defined as a static struct and that the 24 // VCDiffInstructionMap be a static pointer that gets initialized only once. 25 26 #ifndef OPEN_VCDIFF_INSTRUCTION_MAP_H_ 27 #define OPEN_VCDIFF_INSTRUCTION_MAP_H_ 28 29 #include <config.h> 30 #include "codetable.h" 31 #include "vcdiff_defs.h" 32 33 namespace open_vcdiff { 34 35 // An alternate representation of the data in a VCDiffCodeTableData that 36 // optimizes for fast encoding, that is, for taking a delta instruction 37 // inst (also known as instruction type), size, and mode and arriving at 38 // the corresponding opcode. 39 // 40 class VCDiffInstructionMap { 41 public: 42 // Create a VCDiffInstructionMap from the information in code_table_data. 43 // Does not save a pointer to code_table_data after using its contents 44 // to create the instruction->opcode mappings. The caller *must* have 45 // verified that code_table_data->Validate() returned true before 46 // attempting to use this constructor. 47 // max_mode is the maximum value for the mode of a COPY instruction. 48 // 49 VCDiffInstructionMap(const VCDiffCodeTableData& code_table_data, 50 unsigned char max_mode); 51 52 static VCDiffInstructionMap* GetDefaultInstructionMap(); 53 54 // Finds an opcode that has the given inst, size, and mode for its first 55 // instruction and NOOP for its second instruction (or vice versa.) 56 // Returns kNoOpcode if the code table does not have any matching 57 // opcode. Otherwise, returns an opcode value between 0 and 255. 58 // 59 // If this function returns kNoOpcode for size > 0, the caller will 60 // usually want to try again with size == 0 to find an opcode that 61 // doesn't have a fixed size value. 62 // 63 // If this function returns kNoOpcode for size == 0, it is an error condition, 64 // because any code table that passed the Validate() check should have a way 65 // of expressing all combinations of inst and mode with size=0. 66 // LookupFirstOpcode(unsigned char inst,unsigned char size,unsigned char mode)67 OpcodeOrNone LookupFirstOpcode(unsigned char inst, 68 unsigned char size, 69 unsigned char mode) const { 70 return first_instruction_map_.Lookup(inst, size, mode); 71 } 72 73 // Given a first opcode (presumed to have been returned by a previous call to 74 // lookupFirstOpcode), finds an opcode that has the same first instruction as 75 // the first opcode, and has the given inst, size, and mode for its second 76 // instruction. 77 // 78 // If this function returns kNoOpcode for size > 0, the caller will 79 // usually want to try again with size == 0 to find an opcode that 80 // doesn't have a fixed size value. 81 // LookupSecondOpcode(unsigned char first_opcode,unsigned char inst,unsigned char size,unsigned char mode)82 OpcodeOrNone LookupSecondOpcode(unsigned char first_opcode, 83 unsigned char inst, 84 unsigned char size, 85 unsigned char mode) const { 86 return second_instruction_map_.Lookup(first_opcode, inst, size, mode); 87 } 88 89 private: 90 // Data structure used to implement LookupFirstOpcode efficiently. 91 // 92 class FirstInstructionMap { 93 public: 94 FirstInstructionMap(int num_insts_and_modes, int max_size_1); 95 ~FirstInstructionMap(); 96 Add(unsigned char inst,unsigned char size,unsigned char mode,unsigned char opcode)97 void Add(unsigned char inst, 98 unsigned char size, 99 unsigned char mode, 100 unsigned char opcode) { 101 OpcodeOrNone* opcode_slot = &first_opcodes_[inst + mode][size]; 102 if (*opcode_slot == kNoOpcode) { 103 *opcode_slot = opcode; 104 } 105 } 106 107 // See comments for LookupFirstOpcode, above. 108 // Lookup(unsigned char inst,unsigned char size,unsigned char mode)109 OpcodeOrNone Lookup(unsigned char inst, 110 unsigned char size, 111 unsigned char mode) const { 112 int inst_mode = (inst == VCD_COPY) ? (inst + mode) : inst; 113 if (size > max_size_1_) { 114 return kNoOpcode; 115 } 116 // Lookup specific-sized opcode 117 return first_opcodes_[inst_mode][size]; 118 } 119 120 private: 121 // The number of possible combinations of inst (a VCDiffInstructionType) and 122 // mode. Since the mode is only used for COPY instructions, this number 123 // is not (number of VCDiffInstructionType values) * (number of modes), but 124 // rather (number of VCDiffInstructionType values other than VCD_COPY) 125 // + (number of COPY modes). 126 // 127 // Compressing inst and mode into a single integer relies on 128 // VCD_COPY being the last instruction type. The inst+mode values are: 129 // 0 (NOOP), 1 (ADD), 2 (RUN), 3 (COPY mode 0), 4 (COPY mode 1), ... 130 // 131 const int num_instruction_type_modes_; 132 133 // The maximum value of a size1 element in code_table_data 134 // 135 const int max_size_1_; 136 137 // There are two levels to first_opcodes_: 138 // 1) A dynamically-allocated pointer array of size 139 // num_instruction_type_modes_ (one element for each combination of inst 140 // and mode.) Every element of this array is non-NULL and contains 141 // a pointer to: 142 // 2) A dynamically-allocated array of OpcodeOrNone values, with one element 143 // for each possible first instruction size (size1) in the code table. 144 // (In the default code table, for example, the maximum size used is 18, 145 // so these arrays would have 19 elements representing values 0 146 // through 18.) 147 // 148 OpcodeOrNone** first_opcodes_; 149 150 // Making these private avoids implicit copy constructor 151 // and assignment operator 152 FirstInstructionMap(const FirstInstructionMap&); // NOLINT 153 void operator=(const FirstInstructionMap&); 154 } first_instruction_map_; 155 156 // Data structure used to implement LookupSecondOpcode efficiently. 157 // 158 class SecondInstructionMap { 159 public: 160 SecondInstructionMap(int num_insts_and_modes, int max_size_2); 161 ~SecondInstructionMap(); 162 void Add(unsigned char first_opcode, 163 unsigned char inst, 164 unsigned char size, 165 unsigned char mode, 166 unsigned char second_opcode); 167 168 // See comments for LookupSecondOpcode, above. 169 OpcodeOrNone Lookup(unsigned char first_opcode, 170 unsigned char inst, 171 unsigned char size, 172 unsigned char mode) const; 173 private: 174 // See the member of the same name in FirstInstructionMap. 175 const int num_instruction_type_modes_; 176 177 // The maximum value of a size2 element in code_table_data 178 const int max_size_2_; 179 180 // There are three levels to second_opcodes_: 181 // 1) A statically-allocated pointer array with one element 182 // for each possible opcode. Each element can be NULL, or can point to: 183 // 2) A dynamically-allocated pointer array of size 184 // num_instruction_type_modes_ (one element for each combination of inst 185 // and mode.) Each element can be NULL, or can point to: 186 // 3) A dynamically-allocated array with one element for each possible 187 // second instruction size in the code table. (In the default code 188 // table, for example, the maximum size used is 6, so these arrays would 189 // have 7 elements representing values 0 through 6.) 190 // 191 OpcodeOrNone** second_opcodes_[VCDiffCodeTableData::kCodeTableSize]; 192 193 // Making these private avoids implicit copy constructor 194 // and assignment operator 195 SecondInstructionMap(const SecondInstructionMap&); // NOLINT 196 void operator=(const SecondInstructionMap&); 197 } second_instruction_map_; 198 199 static VCDiffInstructionMap* default_instruction_map; 200 201 // Making these private avoids implicit copy constructor & assignment operator 202 VCDiffInstructionMap(const VCDiffInstructionMap&); // NOLINT 203 void operator=(const VCDiffInstructionMap&); 204 }; 205 206 }; // namespace open_vcdiff 207 208 #endif // OPEN_VCDIFF_INSTRUCTION_MAP_H_ 209