// 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_