GLuLuJit VM (not complete)

------------------------------------------------------------------------------
-- LuLu - Lua VM on Lua  version 0.05, June 8th, 2008
--
--  Copyright (C) 2008 hzkr <[email protected]>
--
--  This software is provided 'as-is', without any express or implied
--  warranty.  In no event will the authors be held liable for any damages
--  arising from the use of this software.
--
--  Permission is granted to anyone to use this software for any purpose,
--  including commercial applications, and to alter it and redistribute it
--  freely, subject to the following restrictions:
--
--  1. The origin of this software must not be misrepresented; you must not
--     claim that you wrote the original software. If you use this software
--     in a product, an acknowledgment in the product documentation would be
--     appreciated but is not required.
--  2. Altered source versions must be plainly marked as such, and must not be
--     misrepresented as being the original software.
--  3. This notice may not be removed or altered from any source distribution.
------------------------------------------------------------------------------

lulu = {}

if(MENU_DLL) then
    for k,v in pairs(hook.GetTable()) do
        hook.Remove(k, "LuLu VM");
    end
end

-------------------------------------------------------------------------
-- <<Utilities>>
-------------------------------------------------------------------------

local function bits(n, lsb, numbits)
  return math.floor(n / 2^lsb) % 2^numbits
end

local function dup(obj)
    return setmetatable(table.Copy(obj), {});
end

local function tlen(t)
    return table.maxn(t);
end

-------------------------------------------------------------------------
-- <<Representation of Values>>
--   LuLu VM での値は、基本的には、LuLuを実行しているホストLuaでの
--   値でそのまま表現されます。ただし、関数とスレッドは、特別なタグを
--   つけたテーブルで表現します。
--
--   On LuLu VM, each value except a function and a thread in programs is
--   represented by the corresponding value on host Lua (the Lua environ-
--   ment running LuLu itself). Functions and threads are represented by
--   tables with a special tag-field.
--
-- Example:
--   "true"           --> true
--   "1.23"           --> 1.23
--   "{a=100,b=200}"  --> {a=100,b=200}
--   "function() end" --> {type=type_function, ...} (by a table w/tag)
--   "print"          --> function print()...end (native funcs by funcs)
-------------------------------------------------------------------------

local function type_function(x)
  return type(x)=="table" and x.type==type_function
end

local function type_thread(x)
  return type(x)=="table" and x.type==type_thread
end

local function type_table(x)
  return type(x)=="table" and x.type~=type_function and x.type~=type_thread
end

-------------------------------------------------------------------------
-- Prototype
--   関数オブジェクトの"原型"。UpValue(周囲スコープのローカル変数)と
--   環境(グローバル変数の参照先)が決まっていない状態の関数オブジェクト。
--   luac コマンドや string.dump の出力を lulu.loadproto(binstr) で
--   ロードすることでオブジェクトを作成できます。
--
--   Fields:
--      type   = type_function (tag)
--      numup  = Number of UpValues
--      numpr  = Number of Parameters
--      varflg = Flag for variadic parameters
--      maxstk = Maximum stack consumption
--      code   = Instructions
--      kv     = Constant-Table
--      kp     = Prototype-Table
-------------------------------------------------------------------------

local function inst_decode(self) -- Instruction Decoder
    local ret = {
        OP = self:byte();
        A = self:byte();
        B = self:byte();
        C = self:byte();
    };
    return ret;
end

function lulu.loadproto(binstr, bobj)
  if bobj == nil and binstr:sub(1,4) ~= "\x1BLJ\x01" then
    error("Not a valid Lua chunk file!"..binstr:sub(1,4))
  end
  local loader = {
    header = binstr:sub(1,4),
    d = binstr:sub(5), -- ヘッダはスキップ。x86 で標準的な形式を暗黙に仮定
    bytes =
      function(self, n)
        local dd = self.d
        self.d = self.d:sub(n+1)
        return dd:byte(1,n)
      end,
    -----------------------------
    byte = -- 1バイト整数
      function(self)
        return self:bytes(1)
      end,
    int  = -- 4バイト整数（リトルエンディアン）
      function(self)
        local a,b = self:bytes(2)
        return a*256+b+1
      end,
    int32= -- 4バイト整数（リトルエンディアン）
      function(self)
        local a,b,c,d = self:bytes(4)
        return a*0x1000000+ b*0x10000+ c*0x100+ d
      end,
    uleb128   =
      function(self)
        --[[ ty caken ]]--
        local n = 0
        local factor = 1

        local done = false

        repeat
          local byte = self:byte()
          if(byte >= 0x80) then
            byte = byte - 0x80
          else
            done = true
          end

          n = n + byte * factor
          factor = factor * 128
        until done


        return n
      end,
    inst = -- 命令 (4バイト整数(ここでデコードする))
      function(self)
        return inst_decode(self)
      end,
    string = -- 文字列 = 長さ(size_t) ++ char * 長さ ++ \0
      function(self)
        local n = self:int()
        if n == 0 then
          return ""
        else
          local dd = self.d
          self.d = self.d:sub(n+1)
          return dd:sub(1,n-1)
        end
      end,
    number = -- 数値 = 倍精度(1+11+52)浮動小数点数
      function(self, l, h)
        local l,h,s = l or self:int32(), h or self:int32(), -1
        if h < 2^31 then s = 1 end
        local e = 1 + math.floor(h/2^20)%2^11 - 2^10
        if e == -1023 then
          return 0
        else
          return s*(2^e + math.ldexp(h%2^20,e-20) + math.ldexp(l,e-52))
        end
      end,
    code = -- コード = 命令の列
      function(self, obj)
        local n = obj.instructs
        local code = {}
        for i=1,n do
          code[i] = self:inst()
        end
        return code
      end,
    proto = -- 関数プロトタイプ
      function(self)
        --[[ changed to !cake standards ]]--
        local _begin = self.d
        local obj = {type = type_function}
        if(bobj==nil) then
            self:string() -- 定義されたソースファイル名
            obj.varflg = self:byte();

            obj.numpr = self:byte()
            obj.maxstk = self:byte()
            obj.numup  = self:byte()
        else
            obj.varflg = bobj.varflg;
            obj.numpr = bobj.numpr;
            obj.maxstk = bobj.maxstk;
            obj.numup = bobj.numup
        end

        obj.gccnt = self:uleb128()
        obj.constcnt = self:uleb128()
        obj.instructs = self:uleb128()

        obj.dbgdatlen = self:uleb128()

        obj.lnstart = self:uleb128()
        obj.lncnt = self:uleb128()
        obj.lnend = obj.lnstart + obj.lncnt

        obj.updat = {};

        obj.code   = self:code(obj)
        if(bobj == nil) then
            for i = 1, obj.numup do
                obj.updat[i] = self:int();
            end
        end
        obj.constgc = {};
        for i = obj.gccnt, 1, -1 do
            local type = self:uleb128()
            if(type == 0) then -- function
                obj.constgc[i] = bobj;
            elseif(type >= 5) then -- string
                obj.constgc[i] = self:zstring(type - 5);
            --elseif(type == 0) then -- function
            --  print("not deserializing..")
            --elseif(type == 1) then -- table
            --  print("not deserializing..")
            else
                error("unsupported variable type "..type)
            end
        end
        obj.constnum = {};
        for i = 1, obj.constcnt do
            local l,h,n = self:uleb128();
            if(l % 2 == 1) then
                n = self:number(l, self:uleb128());
                --n = math.floor(n * 1000000) / 1000000
            else
                n = math.floor(l/2);
            end
            obj.constnum[i] = n;
        end
        obj.rawdata = self.header .. _begin:sub(1, #_begin - #self.d)
    --  PrintTable(obj);
        self:bytes(obj.dbgdatlen +1);

        if(#self.d > 0) then
            --print(#self.d);
            local oldobj = obj;
            obj = lulu.loadproto(self.d, oldobj);
            --table.insert(obj.constgc, 1, oldobj);
        end

        return obj
      end,
    zstring =
      function(self, n)
        local dd = self.d
        self.d = self.d:sub(n+1)
        return dd:sub(1,n)
      end,
    dbginfo = -- デバッグ情報。とりあえずスキップ
      function(self)
        local n = self:int()
        for i=1, n do
          self:int()
        end
        n = self:int()
        for i=1, n do
          self:string()
          self:int()
          self:int()
        end
        n = self:int()
        for i=1, n do
          self:string()
        end
      end,
  }
  return loader:proto()
end

-------------------------------------------------------------------------
-- Function
--   関数を表現するオブジェクト。lulu.newfunction(proto, env) で、
--   元となるPrototypeオブジェクトとグローバル変数テーブルを指定して
--   作成する。UpValueは後から適当に埋める。
--
--   Fields (<< Prototype):
--     upval  = Array of Upvalues
--     env    = Table of global values
-------------------------------------------------------------------------

local running_vm = nil
local function_metatable = {__call = function(fn, ...)
  return unpack({running_vm:co_resume(lulu.newthread(fn), ...)}, 2)
end}

function lulu.newfunction(proto, env)
  local fn = dup(proto)
  fn.upval = {}
  fn.env   = env
  setmetatable(fn, function_metatable)
  return fn
end

-------------------------------------------------------------------------
-- VM
--   lulu.newvm() で仮想マシンオブジェクトを作成します。
--   仮想マシンオブジェクトには以下のフィールドがあります。
--      vm.running_thread  (現在実行中のスレッド)
--      vm.main_thread     (メインスレッド)
--      vm:run_as_main(th) (指定されたスレッドをメインスレッドとして実行)
--      vm:run(proto)      (指定されたPrototypeを標準ライブラリ付きで実行)
-------------------------------------------------------------------------

local STARTUP_CODE = lulu.newfunction(lulu.loadproto(string.dump(function() return end)), {}) -- TAILCALL

function lulu.newvm()
  return {
    main_thread    = nil,
    running_thread = nil,
    run_as_main = function(vm, th)
        vm.main_thread = th
        local ret = {vm:co_resume(vm.main_thread)}
        if(table.remove(ret, 1)) then
            return ret;
        end
    end,
    run = function(vm, proto)
      return vm:run_as_main(lulu.newthread(lulu.newfunction(proto, lulu.stdlib(vm))))
    end,
    run_func = function(vm, fn)
        vm:run_as_main(lulu.newthread(fn));
    end,
    ----------------------------------------------------------
    -- コルーチン関係
    ----------------------------------------------------------
    co_resume = function(vm, co, ...)
      local pre_vm = running_vm
      running_vm = vm
      if co.status == "notstarted" then
        co.dstk = {nil, co.main, ...}
        co.dtop = 1 + #co.dstk
        co.cstk = {{func=STARTUP_CODE, pc=1, base=2, retpos=1, wanted=-1, uvcache={}}}
        co.ctop = 2
      elseif co.status == "suspended" then
        local a = {...}
        local narg = (co.yield_wanted==-1 and #a or co.yield_wanted)
        for i=1, narg do
          co.dstk[co.yield_from+i-1] = a[i]
        end
        co.dtop = co.yield_from + narg
      else
        error( "cannot resume ".. co.status .." coroutine" )
      end

      local rt = vm.running_thread
      if rt then rt.status = "normal" end
      vm.running_thread = co
      co.status = "running"
      local ret = co_run(co)
      vm.running_thread = rt
      if rt then rt.status = "running" end

      running_vm = pre_vm
      return true, unpack(ret)
    end,
    co_yield = function(vm, ...)
      vm.running_thread.yield_from    = YF -- てぬき
      vm.running_thread.yield_wanted  = YW -- てぬき
      vm.running_thread.return_values = {...}
      vm.running_thread.status        = "suspended"
    end,
    co_wrap = function(vm,fn)
      local co = lulu.newthread(fn)
      return function(...)
        local a = {vm:co_resume(co, ...)}
        return unpack(a, 2, tlen(a))
      end
    end,
    co_running = function(vm)
      return vm.running_thread~=vm.main_thread and vm.running_thread or nil
    end,
  }
end

-------------------------------------------------------------------------
-- 標準ライブラリ
--
-- Unsupported:
--   dofile/load/loadfile/loadstring (なんとかなる気もする)
--   pcall/xpcall      (なんとかなる気もする)
--   module/require/package (loadがあれば)
--   debug (めんどう)
-------------------------------------------------------------------------

local INTERNAL_HOOKS = {}

function lulu.stdlib(vm)
  local lib = {}; --dup(_G) -- とりあえずホスト環境のライブラリをコピー
  lib._G       = lib;
  lib._VERSION = "LuLuJit 0.4"
  --lib.arg      = {[-1]=arg[-1].." "..arg[0], [0]=arg[1], unpack(arg,2)}
  lib.type     = function(v)
                   local s = type(v)
                   if s == "table" then
                      return v.type==type_function and "function" or
                                (v.type==type_thread and "thread" or s)
                   else
                      return s
                   end
                 end
  lib.coroutine = { create = lulu.newthread,
                    resume = function(...) return vm:co_resume(...) end,
                    yield  = function(...) return vm:co_yield(...) end,
                    wrap   = function(fn) return vm:co_wrap(fn) end,
                    running= function() return vm:co_running() end,
                    status = function(co) return co:status_string() end, }
  local function getfunc(fn)
    if type_function(fn) then
      return fn
    else
      local rt = vm.running_thread
      fn = fn or 1
      if fn == 0 then
        return rt.main
      else
        return rt.cstk[rt.ctop-fn].func
      end
    end
  end
  lib.getfenv = function(fn)
                  return getfunc(fn).env
                end
  lib.setfenv = function(fn, t)
                  local fn = getfunc(fn)
                  fn.env = t
                  return fn
                end
  lib.getmetatable = function(obj)
                        if type_table(obj) then
                           return getmetatable(obj)
                        else
                           return nil
                        end
                     end
  lib.setmetatable = function(obj, mt)
                        if type_table(obj) then
                           setmetatable(obj, mt)
                        else
                           error("bad argument to setmetatable: table expected")
                        end
                        return obj
                     end
  lib.string = dup(_G.string)
  lib.math = dup(_G.math);
    lib.hook = {
        Add = function(event, fn)
            if(MENU_DLL) then
                local func = getfunc(fn);
                if(type(func) == "function") then
                    -- we don't want it to return anything due to evil people
                    -- maybe allow it in the menu though? who knows
                    hook.Add(event, "LuLu VM", function(...)
                        func(...);
                    end);
                elseif(type_function(func)) then
                    hook.Add(event, "LuLu VM", function()
                        vm:run_func(func)
                    end);
                else
                    hook.Remove(event, "LuLu VM");
                end
            end
        end
    };
  lib.string.dump = function(fn)
                       if type_function(fn) then
                           return fn.rawdata
                       elseif type(fn) then
                           return string.dump(fn)
                       end
                    end
  lib.tostring = function(obj) -- 同じことをprintでやるべき？うーむ
                   local s = tostring(obj)
                   if type_function(obj) then
                      s = s:gsub("table", "function")
                   elseif type_thread(obj) then
                      s = s:gsub("table", "thread")
                   end
                   return s
                 end

    lib.print = print
  -- 非対応
  return lib
end

-------------------------------------------------------------------------
-- Thread
--   スレッド。コルーチン。
--
--   Fields:
--     type       = type_thread (tag)
--     dstk, dtop = data stack
--     cstk, ctop = call stack
--     status     = running status
--     main       = main function
-------------------------------------------------------------------------

function lulu.newthread(fn)
  return {
    type   = type_thread,
    status = "notstarted",
    main   = fn,
    status_string = function(co)
      return (co.status=="notstarted" and "suspended" or co.status)
    end,
  }
end

-------------------------------------------------------------------------
-- メタテーブルを考慮したテーブルアクセス
--   ToDo: 同様に__callの実装
-------------------------------------------------------------------------

function gettable(table, key)
  if not type_table(table) then
    error("not a table")
  end

  local v = rawget(table, key)
  if v~=nil then return v end
  local mt = getmetatable(table)
  if mt==nil then return v end
  local ix = rawget(mt, "__index")
  if ix==nil then return v end

  if type_function(ix) or type(ix)=="function" then
    return ix(table, key)
  else
    return gettable(ix, key)
  end
end

function settable(table, key, value)
  if not type_table(table) then
    error("not a table")
  end

  local v = rawget(table, key)
  if v~=nil then rawset(table, key, value) return end
  local mt = getmetatable(table)
  if mt==nil then rawset(table, key, value) return end
  local ix = rawget(mt, "__index")
  if ix==nil then rawset(table, key, value) return end

  if type_function(ix) or type(ix)=="function" then
    ix(table, key, value)
  else
    settable(ix, key, value)
  end
end

-------------------------------------------------------------------------
-- メインの実行ループ
-------------------------------------------------------------------------


lulu.tnil = {};

function co_run(co, limit)
  local limit = limit or 256;
  -- コールスタック
  local ci = co.cstk[co.ctop-1]
  local func,base,retpos,wanted,uvcache = ci.func, ci.base, ci.retpos, ci.wanted, ci.uvcache
  local function cipush(tail, a,b,c,d,e,f)
     ci = {func=a, pc=b, base=c, retpos=d, wanted=e, uvcache=f}
     if not tail then
       co.ctop=co.ctop+1
     end
     co.cstk[co.ctop-1]=ci
     func,base,retpos,wanted,uvcache = ci.func, ci.base, ci.retpos, ci.wanted, ci.uvcache
  end
  local function cipop()
     co.ctop=co.ctop-1
     ci = co.cstk[co.ctop-1]
     func,base,retpos,wanted,uvcache = ci.func, ci.base, ci.retpos, ci.wanted, ci.uvcache
  end

  -- データスタック
  local stk = co.dstk
  local function getreg(n)   return stk[base+n] end
  local function setreg(n,v) stk[base+n] = v    end
  local function getregs(i,n) return unpack(stk, base+i, base+i+n-1) end
  local function setregs(i,n,vals)
    local m = n
    --if m > tlen(vals) then m = tlen(vals) end
    -- why? lulu noob :(
    for j=1,m   do stk[base+i+j-1] = vals[j] end
    for j=m+1,n do stk[base+i+j-1] = nil  end
  end

  -- upvalueをスタックから逃がす処理
  local function closeupvals(from)
    from = from or 0
    for k,u in next, uvcache do
      if from<=k and not rawequal(u.base, u) then
        u[1]   = u.base[u.idx]
        u.base = u
        u.idx  = 1
        uvcache[k] = nil --逃がし終わったらテーブルから消す
      end
    end
  end

  local rets = 0;

  local MULTRES = 0;

  local inner = 1;

  local function do_call(fn, A, narg, nret, tail) -- 関数呼び出しの共通処理
    --PrintTable(stk);
     inner = inner + 1;
     if type_function(fn) then
        cipush(tail, fn, 1, base+A+1, base+A, nret, {})

        -- 実引数が仮引数より少ない場合、残りを nil で埋める
        if narg < fn.numpr then
           for i=narg, fn.numpr-1 do setreg(i, nil) end
           narg = fn.numpr
        end
        -- 可変長引数な時、必須引数を前に持ってきてbaseをずらす
        if func.varflg>0 then
           for i=0,fn.numpr-1 do
             stk[base+narg+i] = stk[base+i]
             stk[base+i]      = nil
           end
           base = base+narg
           co.cstk[co.ctop-1].base = base
        end
        -- ローカル変数領域をnilクリア
        for i=fn.numpr, fn.maxstk-1 do setreg(i,nil) end
     else
        inner = inner - 1;
        YF, YW = A, nret -- てぬき：fnがco_yieldだった場合に使う
        local a = {fn(getregs(A+1, narg))} -- TODO: nil がかえると{nil}は長さゼロになるバグ！
        local ret = nret==-1 and tlen(a) or nret;
        setregs(A, ret, a)
        co.dtop = base+A+ret;
     end
  end

    local function do_return(rbase, rets)
        closeupvals()
        inner = inner - 1;
        --print(inner);
        --print(A,B,C);
        local fn = getreg(rbase)
        --PrintTable(stk);

        if inner == -1 then
            co.status = "dead"
            co.return_values = {getregs(rbase, rets-1)};
            --print"Aaa"
            --PrintTable(co.return_values);
        elseif type_function(fn) then
            --print(fn);
            local narg = rets==0 and co.dtop-(base+rbase+1) or rets-1
            setregs(rbase, narg+1, {getregs(rbase, narg+1)})
            inner = inner - 1;
            do_call(fn, retpos-base, narg, -1, true)
        else
            local a = {fn(getregs(rbase+1, rets==0 and co.dtop-(base+rbase+1) or rets-1))}
            local ret = (wanted==-1 and tlen(a) or wanted);
            for i = rbase, rbase+ret - 1 do
                setreg(i, nil);
            end
            setregs(rbase, ret, a)
            co.dtop = retpos + ret

            cipop()
        end
    end


  -- メインの実行ループ
  local ops_ran = 0;
  co.return_values = nil
  repeat
    ops_ran = ops_ran + 1;
    if(ops_ran > limit) then
        return lua.tnil;
    end
    --PrintTable(func);
    local inst = func.code[ci.pc]
    ci.pc = ci.pc+1

    local OP  = inst.OP
    local A   = inst.A
    local C   = inst.C
    local B   = inst.B
    local D   = inst.B + bit.lshift(inst.C, 8);
    local Bx  = inst.Bx
    local sBx = inst.sBx
    local RKB if B>=2^8 then RKB = func.kv[B-2^8+1] else RKB = getreg(B) end
    local RKC if C>=2^8 then RKC = func.kv[C-2^8+1] else RKC = getreg(C) end

    --print(OP,A,B,C);

    if(OP == 16) then
        setreg(A, getreg(D));
    elseif(OP == 41) then
        if(D == 2) then
            setreg(A, true);
        elseif(D == 1) then
            setreg(A, false);
        elseif(D == 0) then
            setreg(A, nil);
        else
            error("OP = 41, D = "..D);
        end
    elseif(OP == 36) then
       local s = ""
       for i=C,B do s = s .. getreg(i) end
       setreg(A, s)
    elseif(OP == 37) then
        setreg(A, func.constgc[D+1]);
    elseif(OP == 39) then
        setreg(A, D);
    elseif(OP == 40) then
        setreg(A, func.constnum[D+1]);
    elseif(OP == 48) then
        --print("UCLO reached.. unknown!");
    elseif(OP == 49) then
        setreg(A, lulu.newfunction(func.constgc[D+1], func.env));
    elseif(OP == 52) then
        --print("stk_"..A.." = func.env["..tostring(func.constgc[D+1]).."]");
        setreg(A, func.env[func.constgc[D+1]])
    elseif(OP == 53) then
        func.env[func.constgc[A + 1]] = getreg(D);
    elseif(OP == 54) then
        setreg(A, getreg(C)[getreg(B)]);
    elseif(OP == 55) then
        --print("stk_"..A.." = stk_"..C.."["..func.constgc[D+1].."]");
        setreg(A, getreg(C)[func.constgc[B+1]]);
    elseif(OP == 56) then
        setreg(A, getreg(C)[bit.band(B, 0xFF)]);
    elseif(OP == 57) then
        getreg(C)[getreg(B)] = getreg(A);
    elseif(OP == 59) then
        getreg(C)[bit.band(B, 0xFF)] = getreg(A);
    elseif(OP == 61) then
        do_call(getreg(A), A, B + 1, C - 1, false);
    elseif(OP == 62) then
        do_call(getreg(A), A, B - 1, C - 1, false);
    elseif(OP == 63) then
        do_call(getreg(A), A, D +1, -1, false);
        local rets = co.dtop - base - A;
        do_return(A, rets + 1, 0);
    elseif(OP == 64) then
        do_call(getreg(A), A, D - 1, -1, false);
        local rets = co.dtop - base - A;
        do_return(A, rets + 1, 0);
    elseif(OP == 69) then
        do_return(A,D+1);
    elseif(OP == 70) then
        do_return(A,D);
    elseif(OP == 71) then
        do_return(A,D);
    elseif(OP == 72) then
        do_return(A,D);
    --elseif(OP == 73) then

    --elseif(OP == 75) then

    else
        error("OP = "..OP);
    end
    --print("\t "..base);
    --for i = 1, tlen(stk) do print("\t  "..i,stk[i]) end

  until co.return_values
  return co.return_values
end

-------------------------------------------------------------------------
-- Main
-------------------------------------------------------------------------

local vm = lulu.newvm()

concommand.Add("lulu", function(p,c,a,s)
    local rets = vm:run(lulu.loadproto(string.dump(CompileString(s, "luluvm"))));
    if(rets and tlen(rets) > 0) then
        print("lulu:",unpack(rets, 1, tlen(rets)));
    end
end);