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
33namespace 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//
40class 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_
209