openvcdiff | 311c714 | 2008-08-26 19:29:25 +0000 | [diff] [blame] | 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 | // |
| 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 | // |
| 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 | |
| 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 | // |
| 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_ |