src/instruction_map.h

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