// SPDX-License-Identifier: MIT OR MPL-2.0 OR LGPL-2.1-or-later OR GPL-2.0-or-later
// Copyright 2010, SIL International, All rights reserved.

// This class represents loaded graphite stack machine code.  It performs
// basic sanity checks, on the incoming code to prevent more obvious problems
// from crashing graphite.
// Author: Tim Eves

#include <cassert>
#include <cstddef>
#include <cstdlib>
#include <cstring>
#include "graphite2/Segment.h"
#include "inc/Code.h"
#include "inc/Face.h"
#include "inc/GlyphFace.h"
#include "inc/GlyphCache.h"
#include "inc/Machine.h"
#include "inc/Rule.h"
#include "inc/Silf.h"

#include <cstdio>

#ifdef NDEBUG
#ifdef __GNUC__
#pragma GCC diagnostic ignored "-Wunused-parameter"
#endif
#endif


using namespace graphite2;
using namespace vm;

namespace {

inline bool is_return(const instr i) {
    const opcode_t * opmap = Machine::getOpcodeTable();
    const instr pop_ret  = *opmap[POP_RET].impl,
                ret_zero = *opmap[RET_ZERO].impl,
                ret_true = *opmap[RET_TRUE].impl;
    return i == pop_ret || i == ret_zero || i == ret_true;
}

struct context
{
    context(uint8 ref=0) : codeRef(ref) {flags.changed=false; flags.referenced=false;}
    struct {
        uint8   changed:1,
                referenced:1;
    } flags;
    uint8       codeRef;
};

} // end namespace


class Machine::Code::decoder
{
public:
    struct limits;
    static const int NUMCONTEXTS = 256;

    decoder(limits & lims, Code &code, enum passtype pt) throw();

    bool        load(const byte * bc_begin, const byte * bc_end);
    void        apply_analysis(instr * const code, instr * code_end);
    byte        max_ref() { return _max_ref; }
    int         out_index() const { return _out_index; }

private:
    void        set_ref(int index) throw();
    void        set_noref(int index) throw();
    void        set_changed(int index) throw();
    opcode      fetch_opcode(const byte * bc);
    void        analyse_opcode(const opcode, const int8 * const dp) throw();
    bool        emit_opcode(opcode opc, const byte * & bc);
    bool        validate_opcode(const byte opc, const byte * const bc);
    bool        valid_upto(const uint16 limit, const uint16 x) const throw();
    bool        test_context() const throw();
    bool        test_ref(int8 index) const throw();
    bool        test_attr(attrCode attr) const throw();
    void        failure(const status_t s) const throw() { _code.failure(s); }

    Code              & _code;
    int                 _out_index;
    uint16              _out_length;
    instr             * _instr;
    byte              * _data;
    limits            & _max;
    enum passtype       _passtype;
    int                 _stack_depth;
    bool                _in_ctxt_item;
    int16               _slotref;
    context             _contexts[NUMCONTEXTS];
    byte                _max_ref;
};


struct Machine::Code::decoder::limits
{
  const byte       * bytecode;
  const uint8        pre_context;
  const uint16       rule_length,
                     classes,
                     glyf_attrs,
                     features;
  const byte         attrid[gr_slatMax];
};

inline Machine::Code::decoder::decoder(limits & lims, Code &code, enum passtype pt) throw()
: _code(code),
  _out_index(code._constraint ? 0 : lims.pre_context),
  _out_length(code._constraint ? 1 : lims.rule_length),
  _instr(code._code), _data(code._data), _max(lims), _passtype(pt),
  _stack_depth(0),
  _in_ctxt_item(false),
  _slotref(0),
  _max_ref(0)
{ }



Machine::Code::Code(bool is_constraint, const byte * bytecode_begin, const byte * const bytecode_end,
           uint8 pre_context, uint16 rule_length, const Silf & silf, const Face & face,
           enum passtype pt, byte * * const _out)
 :  _code(0), _data(0), _data_size(0), _instr_count(0), _max_ref(0), _status(loaded),
    _constraint(is_constraint), _modify(false), _delete(false), _own(_out==0)
{
#ifdef GRAPHITE2_TELEMETRY
    telemetry::category _code_cat(face.tele.code);
#endif
    assert(bytecode_begin != 0);
    if (bytecode_begin == bytecode_end)
    {
      // ::new (this) Code();
      return;
    }
    assert(bytecode_end > bytecode_begin);
    const opcode_t *    op_to_fn = Machine::getOpcodeTable();

    // Allocate code and data target buffers, these sizes are a worst case
    // estimate.  Once we know their real sizes the we'll shrink them.
    if (_out)   _code = reinterpret_cast<instr *>(*_out);
    else        _code = static_cast<instr *>(malloc(estimateCodeDataOut(bytecode_end-bytecode_begin, 1, is_constraint ? 0 : rule_length)));
    _data = reinterpret_cast<byte *>(_code + (bytecode_end - bytecode_begin));

    if (!_code || !_data) {
        failure(alloc_failed);
        return;
    }

    decoder::limits lims = {
        bytecode_end,
        pre_context,
        rule_length,
        silf.numClasses(),
        face.glyphs().numAttrs(),
        face.numFeatures(),
        {1,1,1,1,1,1,1,1,
         1,1,1,1,1,1,1,255,
         1,1,1,1,1,1,1,1,
         1,1,1,1,1,1,0,0,
         0,0,0,0,0,0,0,0,
         0,0,0,0,0,0,0,0,
         0,0,0,0,0,0,0, silf.numUser()}
    };

    decoder dec(lims, *this, pt);
    if(!dec.load(bytecode_begin, bytecode_end))
       return;

    // Is this an empty program?
    if (_instr_count == 0)
    {
      release_buffers();
      ::new (this) Code();
      return;
    }

    // When we reach the end check we've terminated it correctly
    if (!is_return(_code[_instr_count-1])) {
        failure(missing_return);
        return;
    }

    assert((_constraint && immutable()) || !_constraint);
    dec.apply_analysis(_code, _code + _instr_count);
    _max_ref = dec.max_ref();

    // Now we know exactly how much code and data the program really needs
    // realloc the buffers to exactly the right size so we don't waste any
    // memory.
    assert((bytecode_end - bytecode_begin) >= ptrdiff_t(_instr_count));
    assert((bytecode_end - bytecode_begin) >= ptrdiff_t(_data_size));
    memmove(_code + (_instr_count+1), _data, _data_size*sizeof(byte));
    size_t const total_sz = ((_instr_count+1) + (_data_size + sizeof(instr)-1)/sizeof(instr))*sizeof(instr);
    if (_out)
        *_out += total_sz;
    else
    {
      instr * const old_code = _code;
      _code = static_cast<instr *>(realloc(_code, total_sz));
      if (!_code) free(old_code);
    }
   _data = reinterpret_cast<byte *>(_code + (_instr_count+1));

    if (!_code)
    {
        failure(alloc_failed);
        return;
    }

    // Make this RET_ZERO, we should never reach this but just in case ...
    _code[_instr_count] = op_to_fn[RET_ZERO].impl[_constraint];

#ifdef GRAPHITE2_TELEMETRY
    telemetry::count_bytes(_data_size + (_instr_count+1)*sizeof(instr));
#endif
}

Machine::Code::~Code() throw ()
{
    if (_own)
        release_buffers();
}


bool Machine::Code::decoder::load(const byte * bc, const byte * bc_end)
{
    _max.bytecode = bc_end;
    while (bc < bc_end)
    {
        const opcode opc = fetch_opcode(bc++);
        if (opc == vm::MAX_OPCODE)
            return false;

        analyse_opcode(opc, reinterpret_cast<const int8 *>(bc));

        if (!emit_opcode(opc, bc))
            return false;
    }

    return bool(_code);
}

// Validation check and fixups.
//

opcode Machine::Code::decoder::fetch_opcode(const byte * bc)
{
    const byte opc = *bc++;

    // Do some basic sanity checks based on what we know about the opcode
    if (!validate_opcode(opc, bc))  return MAX_OPCODE;

    // And check its arguments as far as possible
    switch (opcode(opc))
    {
        case NOP :
            break;
        case PUSH_BYTE :
        case PUSH_BYTEU :
        case PUSH_SHORT :
        case PUSH_SHORTU :
        case PUSH_LONG :
            ++_stack_depth;
            break;
        case ADD :
        case SUB :
        case MUL :
        case DIV :
        case MIN_ :
        case MAX_ :
        case AND :
        case OR :
        case EQUAL :
        case NOT_EQ :
        case LESS :
        case GTR :
        case LESS_EQ :
        case GTR_EQ :
        case BITOR :
        case BITAND :
            if (--_stack_depth <= 0)
                failure(underfull_stack);
            break;
        case NEG :
        case TRUNC8 :
        case TRUNC16 :
        case NOT :
        case BITNOT :
        case BITSET :
            if (_stack_depth <= 0)
                failure(underfull_stack);
            break;
        case COND :
            _stack_depth -= 2;
            if (_stack_depth <= 0)
                failure(underfull_stack);
            break;
        case NEXT_N :           // runtime checked
            break;
        case NEXT :
        case COPY_NEXT :
            ++_out_index;
            if (_out_index < -1 || _out_index > _out_length || _slotref > _max.rule_length)
                failure(out_of_range_data);
            break;
        case PUT_GLYPH_8BIT_OBS :
            valid_upto(_max.classes, bc[0]);
            test_context();
            break;
        case PUT_SUBS_8BIT_OBS :
            test_ref(int8(bc[0]));
            valid_upto(_max.classes, bc[1]);
            valid_upto(_max.classes, bc[2]);
            test_context();
            break;
        case PUT_COPY :
            test_ref(int8(bc[0]));
            test_context();
            break;
        case INSERT :
            if (_passtype >= PASS_TYPE_POSITIONING)
                failure(invalid_opcode);
            ++_out_length;
            if (_out_index < 0) ++_out_index;
            if (_out_index < -1 || _out_index >= _out_length)
                failure(out_of_range_data);
            break;
        case DELETE :
            if (_passtype >= PASS_TYPE_POSITIONING)
                failure(invalid_opcode);
            if (_out_index < _max.pre_context)
                failure(out_of_range_data);
            --_out_index;
            --_out_length;
            if (_out_index < -1 || _out_index > _out_length)
                failure(out_of_range_data);
            break;
        case ASSOC :
            if (bc[0] == 0)
                failure(out_of_range_data);
            for (uint8 num = bc[0]; num; --num)
                test_ref(int8(bc[num]));
            test_context();
            break;
        case CNTXT_ITEM :
            valid_upto(_max.rule_length, _max.pre_context + int8(bc[0]));
            if (bc + 2 + bc[1] >= _max.bytecode)    failure(jump_past_end);
            if (_in_ctxt_item)                      failure(nested_context_item);
            break;
        case ATTR_SET :
        case ATTR_ADD :
        case ATTR_SUB :
        case ATTR_SET_SLOT :
            if (--_stack_depth < 0)
                failure(underfull_stack);
            valid_upto(gr_slatMax, bc[0]);
            if (attrCode(bc[0]) == gr_slatUserDefn)     // use IATTR for user attributes
                failure(out_of_range_data);
            test_attr(attrCode(bc[0]));
            test_context();
            break;
        case IATTR_SET_SLOT :
            if (--_stack_depth < 0)
                failure(underfull_stack);
            if (valid_upto(gr_slatMax, bc[0]))
                valid_upto(_max.attrid[bc[0]], bc[1]);
            test_attr(attrCode(bc[0]));
            test_context();
            break;
        case PUSH_SLOT_ATTR :
            ++_stack_depth;
            valid_upto(gr_slatMax, bc[0]);
            test_ref(int8(bc[1]));
            if (attrCode(bc[0]) == gr_slatUserDefn)     // use IATTR for user attributes
                failure(out_of_range_data);
            test_attr(attrCode(bc[0]));
            break;
        case PUSH_GLYPH_ATTR_OBS :
        case PUSH_ATT_TO_GATTR_OBS :
            ++_stack_depth;
            valid_upto(_max.glyf_attrs, bc[0]);
            test_ref(int8(bc[1]));
            break;
        case PUSH_ATT_TO_GLYPH_METRIC :
        case PUSH_GLYPH_METRIC :
            ++_stack_depth;
            valid_upto(kgmetDescent, bc[0]);
            test_ref(int8(bc[1]));
            // level: dp[2] no check necessary
            break;
        case PUSH_FEAT :
            ++_stack_depth;
            valid_upto(_max.features, bc[0]);
            test_ref(int8(bc[1]));
            break;
        case PUSH_ISLOT_ATTR :
            ++_stack_depth;
            if (valid_upto(gr_slatMax, bc[0]))
            {
                test_ref(int8(bc[1]));
                valid_upto(_max.attrid[bc[0]], bc[2]);
            }
            test_attr(attrCode(bc[0]));
            break;
        case PUSH_IGLYPH_ATTR :// not implemented
            ++_stack_depth;
            break;
        case POP_RET :
            if (--_stack_depth < 0)
                failure(underfull_stack);
            GR_FALLTHROUGH;
            // no break
        case RET_ZERO :
        case RET_TRUE :
            break;
        case IATTR_SET :
        case IATTR_ADD :
        case IATTR_SUB :
            if (--_stack_depth < 0)
                failure(underfull_stack);
            if (valid_upto(gr_slatMax, bc[0]))
                valid_upto(_max.attrid[bc[0]], bc[1]);
            test_attr(attrCode(bc[0]));
            test_context();
            break;
        case PUSH_PROC_STATE :  // dummy: dp[0] no check necessary
        case PUSH_VERSION :
            ++_stack_depth;
            break;
        case PUT_SUBS :
            test_ref(int8(bc[0]));
            valid_upto(_max.classes, uint16(bc[1]<< 8) | bc[2]);
            valid_upto(_max.classes, uint16(bc[3]<< 8) | bc[4]);
            test_context();
            break;
        case PUT_SUBS2 :        // not implemented
        case PUT_SUBS3 :        // not implemented
            break;
        case PUT_GLYPH :
            valid_upto(_max.classes, uint16(bc[0]<< 8) | bc[1]);
            test_context();
            break;
        case PUSH_GLYPH_ATTR :
        case PUSH_ATT_TO_GLYPH_ATTR :
            ++_stack_depth;
            valid_upto(_max.glyf_attrs, uint16(bc[0]<< 8) | bc[1]);
            test_ref(int8(bc[2]));
            break;
        case SET_FEAT :
            valid_upto(_max.features, bc[0]);
            test_ref(int8(bc[1]));
            break;
        default:
            failure(invalid_opcode);
            break;
    }

    return bool(_code) ? opcode(opc) : MAX_OPCODE;
}


void Machine::Code::decoder::analyse_opcode(const opcode opc, const int8  * arg) throw()
{
  switch (opc)
  {
    case DELETE :
      _code._delete = true;
      break;
    case ASSOC :
      set_changed(0);
//      for (uint8 num = arg[0]; num; --num)
//        _analysis.set_noref(num);
      break;
    case PUT_GLYPH_8BIT_OBS :
    case PUT_GLYPH :
      _code._modify = true;
      set_changed(0);
      break;
    case ATTR_SET :
    case ATTR_ADD :
    case ATTR_SUB :
    case ATTR_SET_SLOT :
    case IATTR_SET_SLOT :
    case IATTR_SET :
    case IATTR_ADD :
    case IATTR_SUB :
      set_noref(0);
      break;
    case NEXT :
    case COPY_NEXT :
      ++_slotref;
      _contexts[_slotref] = context(uint8(_code._instr_count+1));
      // if (_analysis.slotref > _analysis.max_ref) _analysis.max_ref = _analysis.slotref;
      break;
    case INSERT :
      if (_slotref >= 0) --_slotref;
      _code._modify = true;
      break;
    case PUT_SUBS_8BIT_OBS :    // slotref on 1st parameter
    case PUT_SUBS :
      _code._modify = true;
      set_changed(0);
      GR_FALLTHROUGH;
      // no break
    case PUT_COPY :
      if (arg[0] != 0) { set_changed(0); _code._modify = true; }
      set_ref(arg[0]);
      break;
    case PUSH_GLYPH_ATTR_OBS :
    case PUSH_SLOT_ATTR :
    case PUSH_GLYPH_METRIC :
    case PUSH_ATT_TO_GATTR_OBS :
    case PUSH_ATT_TO_GLYPH_METRIC :
    case PUSH_ISLOT_ATTR :
    case PUSH_FEAT :
    case SET_FEAT :
      set_ref(arg[1]);
      break;
    case PUSH_ATT_TO_GLYPH_ATTR :
    case PUSH_GLYPH_ATTR :
      set_ref(arg[2]);
      break;
    default:
        break;
  }
}


bool Machine::Code::decoder::emit_opcode(opcode opc, const byte * & bc)
{
    const opcode_t * op_to_fn = Machine::getOpcodeTable();
    const opcode_t & op       = op_to_fn[opc];
    if (op.impl[_code._constraint] == 0)
    {
        failure(unimplemented_opcode_used);
        return false;
    }

    const size_t     param_sz = op.param_sz == VARARGS ? bc[0] + 1 : op.param_sz;

    // Add this instruction
    *_instr++ = op.impl[_code._constraint];
    ++_code._instr_count;

    // Grab the parameters
    if (param_sz) {
        memcpy(_data, bc, param_sz * sizeof(byte));
        bc               += param_sz;
        _data            += param_sz;
        _code._data_size += param_sz;
    }

    // recursively decode a context item so we can split the skip into
    // instruction and data portions.
    if (opc == CNTXT_ITEM)
    {
        assert(_out_index == 0);
        _in_ctxt_item = true;
        _out_index = _max.pre_context + int8(_data[-2]);
        _slotref = int8(_data[-2]);
        _out_length = _max.rule_length;

        const size_t ctxt_start = _code._instr_count;
        byte & instr_skip = _data[-1];
        byte & data_skip  = *_data++;
        ++_code._data_size;
        const byte *curr_end = _max.bytecode;

        if (load(bc, bc + instr_skip))
        {
            bc += instr_skip;
            data_skip  = instr_skip - byte(_code._instr_count - ctxt_start);
            instr_skip =  byte(_code._instr_count - ctxt_start);
            _max.bytecode = curr_end;

            _out_length = 1;
            _out_index = 0;
            _slotref = 0;
            _in_ctxt_item = false;
        }
        else
        {
            _out_index = 0;
            _slotref = 0;
            return false;
        }
    }

    return bool(_code);
}


void Machine::Code::decoder::apply_analysis(instr * const code, instr * code_end)
{
    // insert TEMP_COPY commands for slots that need them (that change and are referenced later)
    int tempcount = 0;
    if (_code._constraint) return;

    const instr temp_copy = Machine::getOpcodeTable()[TEMP_COPY].impl[0];
    for (const context * c = _contexts, * const ce = c + _slotref; c < ce; ++c)
    {
        if (!c->flags.referenced || !c->flags.changed) continue;

        instr * const tip = code + c->codeRef + tempcount;
        memmove(tip+1, tip, (code_end - tip) * sizeof(instr));
        *tip = temp_copy;
        ++code_end;
        ++tempcount;
        _code._delete = true;
    }

    _code._instr_count = code_end - code;
}


inline
bool Machine::Code::decoder::validate_opcode(const byte opc, const byte * const bc)
{
    if (opc >= MAX_OPCODE)
    {
        failure(invalid_opcode);
        return false;
    }
    const opcode_t & op = Machine::getOpcodeTable()[opc];
    if (op.impl[_code._constraint] == 0)
    {
        failure(unimplemented_opcode_used);
        return false;
    }
    if (op.param_sz == VARARGS && bc >= _max.bytecode)
    {
        failure(arguments_exhausted);
        return false;
    }
    const size_t param_sz = op.param_sz == VARARGS ? bc[0] + 1 : op.param_sz;
    if (bc - 1 + param_sz >= _max.bytecode)
    {
        failure(arguments_exhausted);
        return false;
    }
    return true;
}


bool Machine::Code::decoder::valid_upto(const uint16 limit, const uint16 x) const throw()
{
    const bool t = (limit != 0) && (x < limit);
    if (!t) failure(out_of_range_data);
    return t;
}

inline
bool Machine::Code::decoder::test_ref(int8 index) const throw()
{
    if (_code._constraint && !_in_ctxt_item)
    {
        if (index > 0 || -index > _max.pre_context)
        {
            failure(out_of_range_data);
            return false;
        }
    }
    else
    {
      if (_max.rule_length == 0
          || (_slotref + _max.pre_context + index >= _max.rule_length)
          || (_slotref + _max.pre_context + index < 0))
      {
        failure(out_of_range_data);
        return false;
      }
    }
    return true;
}

bool Machine::Code::decoder::test_context() const throw()
{
    if (_out_index >= _out_length || _out_index < 0 || _slotref >= NUMCONTEXTS - 1)
    {
        failure(out_of_range_data);
        return false;
    }
    return true;
}

bool Machine::Code::decoder::test_attr(attrCode) const throw()
{
#if 0   // This code is coming but causes backward compatibility problems.
    if (_passtype < PASS_TYPE_POSITIONING)
    {
        if (attr != gr_slatBreak && attr != gr_slatDir && attr != gr_slatUserDefn
                                 && attr != gr_slatCompRef)
        {
            failure(out_of_range_data);
            return false;
        }
    }
#endif
    return true;
}

inline
void Machine::Code::failure(const status_t s) throw() {
    release_buffers();
    _status = s;
}


inline
void Machine::Code::decoder::set_ref(int index) throw() {
    if (index + _slotref < 0 || index + _slotref >= NUMCONTEXTS) return;
    _contexts[index + _slotref].flags.referenced = true;
    if (index + _slotref > _max_ref) _max_ref = index + _slotref;
}


inline
void Machine::Code::decoder::set_noref(int index) throw() {
    if (index + _slotref < 0 || index + _slotref >= NUMCONTEXTS) return;
    if (index + _slotref > _max_ref) _max_ref = index + _slotref;
}


inline
void Machine::Code::decoder::set_changed(int index) throw() {
    if (index + _slotref < 0 || index + _slotref >= NUMCONTEXTS) return;
    _contexts[index + _slotref].flags.changed= true;
    if (index + _slotref > _max_ref) _max_ref = index + _slotref;
}


void Machine::Code::release_buffers() throw()
{
    if (_own)
        free(_code);
    _code = 0;
    _data = 0;
    _own  = false;
}


int32 Machine::Code::run(Machine & m, slotref * & map) const
{
//    assert(_own);
    assert(*this);          // Check we are actually runnable

    if (m.slotMap().size() <= size_t(_max_ref + m.slotMap().context())
        || m.slotMap()[_max_ref + m.slotMap().context()] == 0)
    {
        m._status = Machine::slot_offset_out_bounds;
        return 1;
//        return m.run(_code, _data, map);
    }

    return  m.run(_code, _data, map);
}