//===- NaClBitCodes.h - Enum values for the bitcode format ------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This header Bitcode enum values.
//
// The enum values defined in this file should be considered permanent.  If
// new features are added, they should have values added at the end of the
// respective lists.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_BITCODE_NACL_NACLBITCODES_H
#define LLVM_BITCODE_NACL_NACLBITCODES_H

#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/DataTypes.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include <cassert>

namespace llvm {
class raw_ostream;

namespace naclbitc {
  enum StandardWidths {
    BlockIDWidth   = 8,  // We use VBR-8 for block IDs.
    CodeLenWidth   = 4,  // Codelen are VBR-4.
    BlockSizeWidth = 32, // BlockSize up to 2^32 32-bit words = 16GB per block.
    MaxAbbrevWidth = 32  // Maximum value allowed for Fixed and VBR.
  };

  // The standard abbrev namespace always has a way to exit a block, enter a
  // nested block, define abbrevs, and define an unabbreviated record.
  enum FixedAbbrevIDs {
    END_BLOCK = 0,  // Must be zero to guarantee termination for broken bitcode.
    ENTER_SUBBLOCK = 1,

    /// DEFINE_ABBREV - Defines an abbrev for the current block.  It consists
    /// of a vbr5 for # operand infos.  Each operand info is emitted with a
    /// single bit to indicate if it is a literal encoding.  If so, the value is
    /// emitted with a vbr8.  If not, the encoding is emitted as 3 bits followed
    /// by the info value as a vbr5 if needed.
    DEFINE_ABBREV = 2,

    // UNABBREV_RECORDs are emitted with a vbr6 for the record code, followed by
    // a vbr6 for the # operands, followed by vbr6's for each operand.
    UNABBREV_RECORD = 3,

    // This is not a code, this is a marker for the first abbrev assignment.
    // In addition, we assume up to two additional enumerated constants are
    // added for each extension. These constants are:
    //
    //   PREFIX_MAX_FIXED_ABBREV
    //   PREFIX_MAX_ABBREV
    //
    // PREFIX_MAX_ABBREV defines the maximal enumeration value used for
    // the code selector of a block. If Both PREFIX_MAX_FIXED_ABBREV
    // and PREFIX_MAX_ABBREV is defined, then PREFIX_MAX_FIXED_ABBREV
    // defines the last code selector of the block that must be read using
    // a single read (i.e. a FIXED read, or the first chunk of a VBR read.
    FIRST_APPLICATION_ABBREV = 4,
    // Defines default values for code length, if no additional selectors
    // are added.
    DEFAULT_MAX_ABBREV = FIRST_APPLICATION_ABBREV-1
  };

  /// StandardBlockIDs - All bitcode files can optionally include a BLOCKINFO
  /// block, which contains metadata about other blocks in the file.
  enum StandardBlockIDs {
    /// BLOCKINFO_BLOCK is used to define metadata about blocks, for example,
    /// standard abbrevs that should be available to all blocks of a specified
    /// ID.
    BLOCKINFO_BLOCK_ID = 0,

    // Block IDs 1-7 are reserved for future expansion.
    FIRST_APPLICATION_BLOCKID = 8
  };

  /// BlockInfoCodes - The blockinfo block contains metadata about user-defined
  /// blocks.
  enum BlockInfoCodes {
    // DEFINE_ABBREV has magic semantics here, applying to the current SETBID'd
    // block, instead of the BlockInfo block.

    BLOCKINFO_CODE_SETBID        = 1, // SETBID: [blockid#]
                                      // The following two codes were removed
                                      // because the PNaCl reader could read
                                      // them, but couldn't be generated by
                                      // the writer.
    BLOCKINFO_CODE_BLOCKNAME     = 2, // Not used in PNaCl.
    BLOCKINFO_CODE_SETRECORDNAME = 3  // Not used in PNaCl.
  };

} // End naclbitc namespace

/// NaClBitCodeAbbrevOp - This describes one or more operands in an abbreviation.
/// This is actually a union of two different things:
///   1. It could be a literal integer value ("the operand is always 17").
///   2. It could be an encoding specification ("this operand encoded like so").
///
class NaClBitCodeAbbrevOp {
public:
  enum Encoding {
    Literal = 0, // Value is literal value.
    Fixed = 1,   // A fixed width field, Val specifies number of bits.
    VBR   = 2,   // A VBR field where Val specifies the width of each chunk.
    Array = 3,   // A sequence of fields, next field species elt encoding.
    Char6 = 4,   // A 6-bit fixed field which maps to [a-zA-Z0-9._].
    Encoding_MAX = Char6
  };

  explicit NaClBitCodeAbbrevOp(uint64_t V) :  Enc(Literal), Val(V) {}
  explicit NaClBitCodeAbbrevOp(Encoding E, uint64_t Data = 0);

  Encoding getEncoding() const { return Enc; }

  static bool isValidEncoding(uint64_t Enc) { return Enc <= Encoding_MAX; }

  uint64_t getValue() const { return Val; }

  bool hasValue() const {
    return hasValue(Enc);
  }
  static bool hasValue(Encoding E) {
    return E <= Encoding_MAX && HasValueArray[E];
  }

  bool isValid() const { return isValid(Enc, Val); }
  static bool isValid(Encoding E, uint64_t Val);
  static bool isValid(Encoding E) { return isValid(E, 0); }

  bool isLiteral() const { return Enc == Literal; }

  bool isArrayOp() const { return Enc == Array; }

  /// Returns the number of arguments expected by this abbrevation operator.
  unsigned NumArguments() const {
    if (isArrayOp())
      return 1;
    else
      return 0;
  }

  // Returns the name of the encoding
  static const char *getEncodingName(Encoding E) {
    if (E > Encoding_MAX)
      return "???";
    return EncodingNameArray[E];
  }

  /// Prints out the abbreviation operator to the given stream.
  void Print(raw_ostream &Stream) const;

  /// isChar6 - Return true if this character is legal in the Char6 encoding.
  static bool isChar6(char C) {
    if (C >= 'a' && C <= 'z') return true;
    if (C >= 'A' && C <= 'Z') return true;
    if (C >= '0' && C <= '9') return true;
    if (C == '.' || C == '_') return true;
    return false;
  }
  static unsigned EncodeChar6(char C) {
    if (C >= 'a' && C <= 'z') return C-'a';
    if (C >= 'A' && C <= 'Z') return C-'A'+26;
    if (C >= '0' && C <= '9') return C-'0'+26+26;
    if (C == '.')             return 62;
    if (C == '_')             return 63;
    llvm_unreachable("Not a value Char6 character!");
  }

  static char DecodeChar6(unsigned V) {
    assert((V & ~63) == 0 && "Not a Char6 encoded character!");
    if (V < 26)       return V+'a';
    if (V < 26+26)    return V-26+'A';
    if (V < 26+26+10) return V-26-26+'0';
    if (V == 62)      return '.';
    if (V == 63)      return '_';
    llvm_unreachable("Not a value Char6 character!");
  }

  /// \brief Compares this to Op. Returns <0 if this is less than Op,
  /// Returns 0 if they are equal, and >0 if this is greater than Op.
  int Compare(const NaClBitCodeAbbrevOp &Op) const {
    // Compare encoding values.
    int EncodingDiff = static_cast<int>(Enc) - static_cast<int>(Op.Enc);
    if (EncodingDiff != 0) return EncodingDiff;

    // Encodings don't differ, so now base on data associated with the
    // encoding.
    return ValCompare(Op);
  }

private:
  Encoding Enc;           // The encoding to use.
  uint64_t Val;           // Data associated with encoding (if any).

  int ValCompare(const NaClBitCodeAbbrevOp &Op) const {
    if (Val < Op.Val)
      return -1;
    else if (Val > Op.Val)
      return 1;
    else
      return 0;
  }
  static const bool HasValueArray[];
  static const char *EncodingNameArray[];
};

template <> struct isPodLike<NaClBitCodeAbbrevOp> {
  static const bool value=true;
};

static inline bool operator<(const NaClBitCodeAbbrevOp &Op1,
                             const NaClBitCodeAbbrevOp &Op2) {
  return Op1.Compare(Op2) < 0;
}

static inline bool operator<=(const NaClBitCodeAbbrevOp &Op1,
                              const NaClBitCodeAbbrevOp &Op2) {
  return Op1.Compare(Op2) <= 0;
}

static inline bool operator==(const NaClBitCodeAbbrevOp &Op1,
                              const NaClBitCodeAbbrevOp &Op2) {
  return Op1.Compare(Op2) == 0;
}

static inline bool operator!=(const NaClBitCodeAbbrevOp &Op1,
                              const NaClBitCodeAbbrevOp &Op2) {
  return Op1.Compare(Op2) != 0;
}

static inline bool operator>=(const NaClBitCodeAbbrevOp &Op1,
                              const NaClBitCodeAbbrevOp &Op2) {
  return Op1.Compare(Op2) >= 0;
}

static inline bool operator>(const NaClBitCodeAbbrevOp &Op1,
                             const NaClBitCodeAbbrevOp &Op2) {
  return Op1.Compare(Op2) > 0;
}

/// NaClBitCodeAbbrev - This class represents an abbreviation record.  An
/// abbreviation allows a complex record that has redundancy to be stored in a
/// specialized format instead of the fully-general, fully-vbr, format.
class NaClBitCodeAbbrev {
  SmallVector<NaClBitCodeAbbrevOp, 8> OperandList;
  unsigned char RefCount; // Number of things using this.
  ~NaClBitCodeAbbrev() {}
public:
  NaClBitCodeAbbrev() : RefCount(1) {}

  void addRef() { ++RefCount; }
  void dropRef() { if (--RefCount == 0) delete this; }

  unsigned getNumOperandInfos() const {
    return static_cast<unsigned>(OperandList.size());
  }
  const NaClBitCodeAbbrevOp &getOperandInfo(unsigned N) const {
    return OperandList[N];
  }

  void Add(const NaClBitCodeAbbrevOp &OpInfo) {
    OperandList.push_back(OpInfo);
  }

  // Returns a simplified version of the abbreviation. Used
  // to recognize equivalent abbrevations.
  NaClBitCodeAbbrev *Simplify() const;

  // Returns true if the abbreviation is valid wrt to the bitcode reader.
  bool isValid() const;

  int Compare(const NaClBitCodeAbbrev &Abbrev) const {
    // First order based on number of operands.
    size_t OperandListSize = OperandList.size();
    size_t AbbrevOperandListSize = Abbrev.OperandList.size();
    if (OperandListSize < AbbrevOperandListSize)
      return -1;
    else if (OperandListSize > AbbrevOperandListSize)
      return 1;

    // Same number of operands, so compare element by element.
    for (size_t I = 0; I < OperandListSize; ++I) {
      if (int Diff = OperandList[I].Compare(Abbrev.OperandList[I]))
        return Diff;
    }
    return 0;
  }

  // Returns true if all records matching the abbreviation must be
  // of fixed length.
  bool IsFixedSize() const {
    unsigned Size = getNumOperandInfos();
    if (Size < 2) return true;
    return !OperandList[Size-2].isArrayOp();
  }

  // Returns the smallest record size that will match this
  // abbreviation.
  size_t GetMinRecordSize() const {
    size_t Min = getNumOperandInfos();
    if (!IsFixedSize()) Min -= 2;
    return Min;
  }

  void Print(raw_ostream &Stream, bool AddNewline=true) const;

  NaClBitCodeAbbrev *Copy() const {
    NaClBitCodeAbbrev *AbbrevCopy = new NaClBitCodeAbbrev();
    for (unsigned I = 0, IEnd = getNumOperandInfos();
         I != IEnd; ++I) {
      AbbrevCopy->Add(NaClBitCodeAbbrevOp(getOperandInfo(I)));
    }
    return AbbrevCopy;
  }
};

static inline bool operator<(const NaClBitCodeAbbrev &A1,
                             const NaClBitCodeAbbrev &A2) {
  return A1.Compare(A2) < 0;
}

static inline bool operator<=(const NaClBitCodeAbbrev &A1,
                              const NaClBitCodeAbbrev &A2) {
  return A1.Compare(A2) <= 0;
}
static inline bool operator==(const NaClBitCodeAbbrev &A1,
                              const NaClBitCodeAbbrev &A2) {
  return A1.Compare(A2) == 0;
}

static inline bool operator!=(const NaClBitCodeAbbrev &A1,
                              const NaClBitCodeAbbrev &A2) {
  return A1.Compare(A2) != 0;
}
static inline bool operator>=(const NaClBitCodeAbbrev &A1,
                              const NaClBitCodeAbbrev &A2) {
  return A1.Compare(A2) >= 0;
}

static inline bool operator>(const NaClBitCodeAbbrev &A1,
                             const NaClBitCodeAbbrev &A2) {
  return A1.Compare(A2) > 0;
}

/// \brief Returns number of bits needed to encode
/// value for dense FIXED encoding.
inline unsigned NaClBitsNeededForValue(unsigned Value) {
  // Note: Need to handle case where Value=0xFFFFFFFF as special case,
  // since we can't add 1 to it.
  if (Value >= 0x80000000) return 32;
  return Log2_32_Ceil(Value+1);
}

/// \brief Encode a signed value by moving the sign to the LSB for dense
/// VBR encoding.
inline uint64_t NaClEncodeSignRotatedValue(int64_t V) {
  return (V >= 0) ? (V << 1) : ((-V << 1) | 1);
}

/// \brief Decode a signed value stored with the sign bit in
/// the LSB for dense VBR encoding.
inline uint64_t NaClDecodeSignRotatedValue(uint64_t V) {
  if ((V & 1) == 0)
    return V >> 1;
  if (V != 1)
    return -(V >> 1);
  // There is no such thing as -0 with integers.  "-0" really means MININT.
  return 1ULL << 63;
}

/// \brief This class determines whether a FIXED or VBR
/// abbreviation should be used for the selector, and the number of bits
/// needed to capture such selectors.
class NaClBitcodeSelectorAbbrev {

public:
  // If true, use a FIXED abbreviation. Otherwise, use a VBR abbreviation.
  bool IsFixed;
  // Number of bits needed for selector.
  unsigned NumBits;

  // Creates a selector range for the given values.
  NaClBitcodeSelectorAbbrev(bool IF, unsigned NB)
      : IsFixed(IF), NumBits(NB) {}

  // Creates a selector range when no abbreviations are defined.
  NaClBitcodeSelectorAbbrev()
      : IsFixed(true),
        NumBits(NaClBitsNeededForValue(naclbitc::DEFAULT_MAX_ABBREV)) {}

  // Creates a selector range to handle fixed abbrevations up to
  // the specified value.
  explicit NaClBitcodeSelectorAbbrev(unsigned MaxAbbrev)
      : IsFixed(true),
        NumBits(NaClBitsNeededForValue(MaxAbbrev)) {}
};
} // End llvm namespace

#endif
