1c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Copyright 2008 Google Inc. 2c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Author: Lincoln Smith 3c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 4c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Licensed under the Apache License, Version 2.0 (the "License"); 5c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// you may not use this file except in compliance with the License. 6c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// You may obtain a copy of the License at 7c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 8c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// http://www.apache.org/licenses/LICENSE-2.0 9c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 10c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Unless required by applicable law or agreed to in writing, software 11c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// distributed under the License is distributed on an "AS IS" BASIS, 12c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// See the License for the specific language governing permissions and 14c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// limitations under the License. 15c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 16c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include <config.h> 17c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "instruction_map.h" 18c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include <string.h> // memset 19c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "addrcache.h" 20c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "vcdiff_defs.h" 21c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 22c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottnamespace open_vcdiff { 23c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 24c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// VCDiffInstructionMap members and methods 25c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 26c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottVCDiffInstructionMap* VCDiffInstructionMap::default_instruction_map = NULL; 27c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 28c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottVCDiffInstructionMap* VCDiffInstructionMap::GetDefaultInstructionMap() { 29c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!default_instruction_map) { 30c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott default_instruction_map = new VCDiffInstructionMap( 31c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott VCDiffCodeTableData::kDefaultCodeTableData, 32c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott VCDiffAddressCache::DefaultLastMode()); 33c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 34c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return default_instruction_map; 35c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 36c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 37c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottstatic unsigned char FindMaxSize( 38c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const unsigned char size_array[VCDiffCodeTableData::kCodeTableSize]) { 39c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char max_size = size_array[0]; 40c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 1; i < VCDiffCodeTableData::kCodeTableSize; ++i) { 41c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (size_array[i] > max_size) { 42c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott max_size = size_array[i]; 43c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 44c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 45c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return max_size; 46c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 47c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 48c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottstatic void ClearSizeOpcodeArray(int length, OpcodeOrNone* array) { 49c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < length; ++i) { 50c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott array[i] = kNoOpcode; 51c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 52c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 53c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 54c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottstatic OpcodeOrNone* NewSizeOpcodeArray(int length) { 55c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott OpcodeOrNone* array = new OpcodeOrNone[length]; 56c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ClearSizeOpcodeArray(length, array); 57c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return array; 58c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 59c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 60c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottVCDiffInstructionMap::FirstInstructionMap::FirstInstructionMap( 61c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int num_insts_and_modes, 62c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int max_size_1) 63c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott : num_instruction_type_modes_(num_insts_and_modes), 64c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott max_size_1_(max_size_1) { 65c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott first_opcodes_ = new OpcodeOrNone*[num_instruction_type_modes_]; 66c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < num_instruction_type_modes_; ++i) { 67c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // There must be at least (max_size_1_ + 1) elements in first_opcodes_ 68c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // because the element first_opcodes[max_size_1_] will be referenced. 69c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott first_opcodes_[i] = NewSizeOpcodeArray(max_size_1_ + 1); 70c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 71c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 72c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 73c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottVCDiffInstructionMap::FirstInstructionMap::~FirstInstructionMap() { 74c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < num_instruction_type_modes_; ++i) { 75c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott delete[] first_opcodes_[i]; 76c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 77c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott delete[] first_opcodes_; 78c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 79c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 80c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottVCDiffInstructionMap::SecondInstructionMap::SecondInstructionMap( 81c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int num_insts_and_modes, 82c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int max_size_2) 83c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott : num_instruction_type_modes_(num_insts_and_modes), 84c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott max_size_2_(max_size_2) { 85c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott memset(second_opcodes_, 0, sizeof(second_opcodes_)); 86c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 87c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 88c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 89c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottVCDiffInstructionMap::SecondInstructionMap::~SecondInstructionMap() { 90c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int opcode = 0; opcode < VCDiffCodeTableData::kCodeTableSize; ++opcode) { 91c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (second_opcodes_[opcode] != NULL) { 92c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int inst_mode = 0; 93c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott inst_mode < num_instruction_type_modes_; 94c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ++inst_mode) { 95c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // No need to check for NULL 96c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott delete[] second_opcodes_[opcode][inst_mode]; 97c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 98c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott delete[] second_opcodes_[opcode]; 99c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 100c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 101c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 102c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 103c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid VCDiffInstructionMap::SecondInstructionMap::Add( 104c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char first_opcode, 105c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char inst, 106c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char size, 107c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char mode, 108c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char second_opcode) { 109c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott OpcodeOrNone**& inst_mode_array = second_opcodes_[first_opcode]; 110c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!inst_mode_array) { 111c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott inst_mode_array = new OpcodeOrNone*[num_instruction_type_modes_]; 112c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott memset(inst_mode_array, 113c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 0, 114c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott num_instruction_type_modes_ * sizeof(inst_mode_array[0])); 115c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 116c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott OpcodeOrNone*& size_array = inst_mode_array[inst + mode]; 117c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!size_array) { 118c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // There must be at least (max_size_2_ + 1) elements in size_array 119c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // because the element size_array[max_size_2_] will be referenced. 120c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott size_array = NewSizeOpcodeArray(max_size_2_ + 1); 121c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 122c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (size_array[size] == kNoOpcode) { 123c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott size_array[size] = second_opcode; 124c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 125c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 126c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 127c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottOpcodeOrNone VCDiffInstructionMap::SecondInstructionMap::Lookup( 128c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char first_opcode, 129c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char inst, 130c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char size, 131c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char mode) const { 132c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (size > max_size_2_) { 133c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return kNoOpcode; 134c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 135c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const OpcodeOrNone* const * const inst_mode_array = 136c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott second_opcodes_[first_opcode]; 137c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!inst_mode_array) { 138c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return kNoOpcode; 139c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 140c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int inst_mode = (inst == VCD_COPY) ? (inst + mode) : inst; 141c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const OpcodeOrNone* const size_array = inst_mode_array[inst_mode]; 142c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!size_array) { 143c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return kNoOpcode; 144c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 145c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return size_array[size]; 146c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 147c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 148c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Because a constructor should never fail, the caller must already 149c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// have run ValidateCodeTable() against the code table data. 150c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 151c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottVCDiffInstructionMap::VCDiffInstructionMap( 152c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const VCDiffCodeTableData& code_table_data, 153c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char max_mode) 154c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott : first_instruction_map_(VCD_LAST_INSTRUCTION_TYPE + max_mode + 1, 155c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott FindMaxSize(code_table_data.size1)), 156c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott second_instruction_map_(VCD_LAST_INSTRUCTION_TYPE + max_mode + 1, 157c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott FindMaxSize(code_table_data.size2)) { 158c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // First pass to fill up first_instruction_map_ 159c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int opcode = 0; opcode < VCDiffCodeTableData::kCodeTableSize; ++opcode) { 160c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (code_table_data.inst2[opcode] == VCD_NOOP) { 161c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Single instruction. If there is more than one opcode for the same 162c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // inst, mode, and size, then the lowest-numbered opcode will always 163c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // be used by the encoder, because of the descending loop. 164c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott first_instruction_map_.Add(code_table_data.inst1[opcode], 165c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott code_table_data.size1[opcode], 166c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott code_table_data.mode1[opcode], 167c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott opcode); 168c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else if (code_table_data.inst1[opcode] == VCD_NOOP) { 169c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // An unusual case where inst1 == NOOP and inst2 == ADD, RUN, or COPY. 170c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // This is valid under the standard, but unlikely to be used. 171c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Add it to the first instruction map as if inst1 and inst2 were swapped. 172c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott first_instruction_map_.Add(code_table_data.inst2[opcode], 173c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott code_table_data.size2[opcode], 174c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott code_table_data.mode2[opcode], 175c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott opcode); 176c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 177c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 178c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Second pass to fill up second_instruction_map_ (depends on first pass) 179c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int opcode = 0; opcode < VCDiffCodeTableData::kCodeTableSize; ++opcode) { 180c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if ((code_table_data.inst1[opcode] != VCD_NOOP) && 181c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott (code_table_data.inst2[opcode] != VCD_NOOP)) { 182c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Double instruction. Find the corresponding single instruction opcode 183c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const OpcodeOrNone single_opcode = 184c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott LookupFirstOpcode(code_table_data.inst1[opcode], 185c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott code_table_data.size1[opcode], 186c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott code_table_data.mode1[opcode]); 187c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (single_opcode == kNoOpcode) continue; // No single opcode found 188c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott second_instruction_map_.Add(static_cast<unsigned char>(single_opcode), 189c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott code_table_data.inst2[opcode], 190c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott code_table_data.size2[opcode], 191c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott code_table_data.mode2[opcode], 192c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott opcode); 193c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 194c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 195c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 196c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 197c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott}; // namespace open_vcdiff 198