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