Lua 5.3 VM byte codeファイル構造

## この記事は...
### この記事で伝えたいこと
- Lua 5.3のコンパイルされたバイトコードの**構造を具体例を通じて**示すものです
- 「バイトコードがあるけど、読み方がわからない」、「検索するとLuaの命令（opcodes）セットの情報は出てくるけど、ファイルのどこにopcodesがあるの？」という方に向けて書いています。
    - ちなみに、通常のLuaでデバッグ情報を削らずコンパイルされていれば、[luadec](https://github.com/viruscamp/luadec)でほとんどソースが復元できます。

### この記事で伝えられないこと
- 命令（opcodes）の内容については触れていません。
    - opcodesについては、[このサイト](https://the-ravi-programming-language.readthedocs.io/en/stable/lua_bytecode_reference.html)などに情報が集まっています。
- 別実装（SLua, NLua, LuaJIT等）やv5.3以外のバージョン（v5.2やv5.4）には触れません。
    - Luaは異なる実装はもちろん、マイナーバージョンが違うだけでもコンパイルされたコードが大きく変わります。（ビルドバージョン(5.3.x)は互換性あり）
- 具体例を重視するため、詳細を省略します。この点についてはリファレンスが補足になると考えています。

### 前提知識（対象読者が持っていると想定している知識）
- luaに関する基本的な構文
- バイナリエディタの画面の見方、つまりバイナリ配列の一般的な表記方法

## 扱うサンプル
今回はstring.dump関数を用いて関数をダンプすることでコンパイルを行います。
以下のコードをlua53.exeに引数として渡して実行すると、作業ディレクトリにsample1.luacというコンパイル後のファイルが出力されます。
```lua:sample1.lua
local function to_dump() -- コンパイルする関数
    local a = -1
    local b = 3.14
    local c = "string_example"
    return a * b
end
-- 以下、to_dump関数をコンパイル&ファイル書き込み。
local f = io.open('sample1.luac', 'wb')
f:write(string.dump(to_dump))
f:close()
```
実行して得られたバイトコード（sample1.luac）をバイナリエディタで開くと以下のようになります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/581287/69fddf54-eac3-1b3e-328e-3ea6d3ed64f9.png)
Lua5.3では先頭5バイト（赤枠部分）が``1B 4C 75 61 53``になります。

>Note:
>luaでは、string.dump関数の他にソースコードの書かれたファイルを入力とするluac.exeを利用することでもコンパイルすることができますが、構造は同じです。luacを利用する場合は、指定したファイル全体が一つの関数として扱われます。
>入出力関係は以下の通り：
>> 関数 → string.dump → 関数をコンパイルした文字列
>> ファイル → luac.exe → ファイル全体を引数のない大きな関数としてコンパイルしたファイル

## バイトコードの構造
### 大きなフィールド：header, upvalue_num, function
バイトコードはheader, upvalue_num, functionに分かれます。
- header：**Luaバージョンや実装、型のサイズ情報**
- upvalue_num：upvalueテーブルの大きさ（←ｷﾆｼﾅｸﾃﾖｲ；詳細は参考文献）
- function：**命令群や変数情報**

headerは固定長で先頭33（0x21）バイト、upvalue_numは固定長で1バイト、その後可変長のfunctionが終わりまで続きます。

具体例を見てみましょう。
sample1.luacのheaderが青字、upvalue_numは赤枠、functionがその後の黒字部分です。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/581287/55b959c3-c676-a3eb-b863-842e4f537672.png)

### フィールド詳細：header
ここではfunctionを読み解く上で必要な型のサイズ情報の読み方に絞って説明します。
その他細かい点は[headerに関する記事](https://qiita.com/sakurausagi/items/430b4a296a9898ff2372)を参照してください。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/581287/563bf222-808b-5625-635d-ad7b57d6e64e.png)
headerのうちサイズ情報に関する場所は``0x0C`` ~ ``0x10``（上図緑背景）の5bytesになります。
この部分はそれぞれ1byteごとに順にint, size_t, instruction, LuaInterger, LuaNumberの大きさを表します。
上の例では、以下の表のように大きさが記載されていることになります。
|      型     |  長さ  |
|------------:|:------:|
|         int | 4bytes |
|      size_t | 4bytes |
| instruction | 4bytes |
| LuaInterger | 8bytes |
|   LuaNumber | 8bytes |

これらの値は次のfunctionを読み解く上で重要な役割を果たします。

### フィールド詳細：function
続いて本題のfunctionについて見ていきます。
functionは下の表に示す11の要素に分解できます。
表中の「関数の命令(opcodes)」までがその関数の動作を表し、それ以降が関数の中にある変数などを表す部分になっています。
| 型 | 要素名（仮） |
| ---- | ---- |
| String | ソースの名前 |
| int | 関数定義の先頭行 |
| int | 関数定義の末尾行 |
| Byte | 引数の数 |
| Byte | 可変長引数を取る関数か？ |
| Byte | 最大スタックサイズ |
| Code | 関数の命令（opcodes） |
| Constants | 定数のリスト |
| Upvalues | [上位値(非ローカル変数)](https://en.wikipedia.org/wiki/Non-local_variable)のリスト |
| Protos | 内部で定義されている関数のリスト |
| Debug | デバッグ情報 |

型として意味がわからないものが多くあると思いますがこれは以降で実際に例を見ながら解説します。
では早速先程のコードでどの場所がそれぞれの要素を表しているか見てみましょう。

#### function前半部（ソースの名前～関数の命令）
前半部(ソースの名前～関数の命令)は以下の図のようになります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/581287/ae356176-d6d1-cc37-1ff5-5330d3a13c4e.png)
先頭の背景色のない``40 00``はheader末尾とupvalue_numです。その後続く黄色い``40 40 43 ...``から、最後までがfunctionの中身ですが、ここでは関数の命令（水色）までを色分けしてあります。

先頭から見ていきましょう。初めは**ソースの名前**（黄色）ですが、これは今回ファイルの絶対パスになります。これは``String``型なのですが、この型は可変長のため、先頭に文字列の長さ（配列長）を示す1byteがあり、その後それ自身も含めてその長さの分だけASCII文字を表すバイト列が連なる形になります。ここでは赤矢印でしめした``0x40=64``が確保された長さを表し、続く``40 43 3A ... 75 61``の64-1=63バイトが「ソースの名前」の実体になります。この実体を[デコード](https://www.rapidtables.org/ja/convert/number/ascii-hex-bin-dec-converter.html)すると``@C:\Users\aaaaa\Desktop\xxx\yyyy\zzzzzzzzzzzzzzzzzz\sample1.lua``という文字列を得ることができました。

続いてint型で**関数定義の先頭行**（橙色）、**関数定義の末尾行**（紺色）ですがheaderでint型が4bytesと指定されていたことを思い出すと、2つとも4bytesで読むことが推定できます。また、lua 5.3は基本的に[リトルエンディアン](https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%B3%E3%83%87%E3%82%A3%E3%82%A2%E3%83%B3)（位が高いバイトが後ろに来る）なので``01 00 00 00``は0x00000001=1を、``06 00 00 00``は0x00000006=6を意味することがわかります。
この先頭行や末尾行というのは何を表しているかというと、コンパイル前のソースコードでその関数がどの位置にあったのかを表します。例でコンパイルしたto_dump関数は元のソースコードで1行目から6行目までで定義されていることがこの部分に反映されています。

続いてbyte型で**引数の数**（黒色）、**可変長引数を取る関数か？**（紫色）、**最大スタックサイズ**（緑色）が示されます。引数の数は関数の引数の個数を表す数値ですが、to_dump関数は引数を取らないので0、可変長引数（luaでは``...``で表される）も指定していないのでfalseを表す0（trueの場合は1）です。
最後のスタックサイズは、Lua Virtual Machine上で関数を実行する際に必要なスタックサイズと思われますがここでは紹介しません。参考文献の3番を御覧ください。

いよいよ前半部最後の**関数の命令**です。この部分はinstructionと呼ばれたりopcodesと呼ばれたり、サイトにより表記ゆれのあるところですが、中身としては関数をLua Virtual Machineが理解できる機械語の命令として書き下しているものになります。命令系列の長さは当たり前ですが関数の複雑さによって変わるので、はじめにint型で命令の長さをかき、その後その長さの個数だけ命令を表すバイト列が続きます。
例では、長さが6（赤矢印部分）であることがわかり、その後header記載の命令（instruction）の長さである4bytesの塊が6つつながる（青矢印部分）という構造になっています。

>Note:
また、命令で注意しなければならない点は、それぞれの命令はint型と同様リトルエンディアンで書かれており、例えば2つめの命令``41 40 00 00``は実際には0x00004041として解釈する必要があります。

#### function後半部（定数のリスト～デバッグ情報）
ちょっと長くなって来てヤルキが低下してきましたが、後半戦サクッと終わらせてしまいましょう！
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/581287/90ad5521-3a4c-634a-040c-b8120d2949e9.png)

後半戦の最初は**定数のリスト**（黄色）です。こちらは関数内で定義されている定数（`a=-1; b=3.14, c="string_example"`の`-1`, `3.14`, `"string_example"`）を格納しています。まずはint型で定数の個数（赤矢印、例では3）を表現します。続いてそれぞれの定数の値が続くのですが、定数の型がそれぞれ異なるため、最初の1byteは型を表現するのに利用されます。これをタイプタグ（type tag; tt）と言います。

|      型     |   tt   |
|------------:|:------:|
|     浮動小数(LuaNumber) | 0x03 |
|     整数(LuaInterger)| 0x13 |
| (short) string | 0x04 |

上の表はタイプタグの一部を示したものになっています（全ての列挙は参考文献1番を参照）。
これを見ながら例のバイトコードの定数1番目を見ると`13 FF FF ...`となっているため0x13 → LuaInterger型です。この型はheaderで8bytesだと定義があったため8バイトを読むと`FF FF FF FF FF FF FF FF`つまり符号付き8バイト整数型と解釈すると、これは`-1`を表現しています（今回の例ではわかりにくいですが、これもリトルエンディアンです）。
続いて定数2つ目に移ると、`03 1F 85 ...`となっており、先頭が0x03であることから浮動小数(LuaNumber)であることがわかります。こちらもheaderで8bytesとわかっているためdoubleとして解釈すると、`3.14`を示すことがわかります（浮動小数はこれまでと違いビッグエンディアンです）。
最後に定数3つ目の型を見ると0x04、つまり型はstringであることがわかります。string型は先程も出てきましたが、先頭に文字配列の長さが来て、その後に文字が並ぶ形でした。これを解釈すると0x0F - 1 = 0x0E = 14文字からなる文字列だということがわかり、"string_example"を復元できます。

続いて**上位値のリスト**（橙色）です。上位値はpythonで言うところのnonlocalな値で、関数外で定義されているが最も外側のグローバルからはアクセスできない場所にある値（例えば関数が2重になっていて最も深い関数からみた1重目の関数のローカル変数）を表します。
これも定数と同様、int型の上位値の個数、[タイプタグ1, 値1, タイプタグ2, 値2, ...]となるのですが、今回は上位値がないため個数を示す`00 00 00 00`のみです。

同様に**内部で定義されている関数のリスト**（青色）もint型の関数の個数から始まりますが、今回は関数内関数がないため個数を示す`00 00 00 00`=0で終わっています。
今回はありませんでしたが**関数があった場合、フィールド詳細：function**で書いた関数の構造が個数分繰り返されます。、、、つまりとても読むのが大変になりますです。これはもう解消しようがないため自身で逆アセンブラを作るか既成のもの（luadecや[ここ](https://qiita.com/tacigar/items/28531572836ed614396d)）を使ったほうが早いです。。

最後に**デバッグ情報**（黒色）ですが、これは全部説明すると記事の長さが2倍になるので端折って説明します（参考文献1番で全て説明されています）。
まず初めのint型の0x00000006（初めの赤矢印）は「関数の命令」の長さです。続いて関数の命令のそれぞれに対してそれがソースコード上の何行目に対応しているかがint型のリスト（6要素；青矢印）で続きます。続いて、関数内の変数の個数がint型で示されます（赤矢印2番目；例では0x00000003）。続いてその個数分だけ変数の表示名（例では`a`, `b`, `c`等（紫枠））、変数が最初に現れた行(int)と有効範囲の最後の行(int)（黄色矢印）が続きます。ラストの赤は上位値の変数名の個数と文字列のリストが続きますが、今回は上位値がないため個数（0x00000000=0）で終わっています。



以上、ざっとどう読むのかを説明してきました。


色々細かすぎる点、よくわからなかった点等あると思います。


ぜひ下のコメント欄で指摘してくださるとありがたいです。（編集リクエストくれると更に捗ります）


ではでは、良いlua53ライフを！


（lua54がメジャーになったらまたluaのソースコード読み直しってマジ....?）

## 補足とtips
本文では触れられなかったが、知っておかないと困るかもしれないな情報のまとめです。
- long string型：
    - 本文中ではstringは長さを表す1byte + （その長さ－１）のASCIIバイト文字列と書きましたが実際には1バイトで長さを表現できなくなる255文字以上からなる文字列を表現するためにlong stringという型が存在します（タイプタグは0x14です）。詳細については省きますが（参考文献4と1参照）、長さを表す1byteが0xFFになり、その後int型で文字列の長さが示され、その文字列の長さ分ASCII文字列が続きます。長さがintの限界（4,294,967,295文字）を超えた場合どうなるかは不明ですが、まあ超えないと思うので大丈夫....調べた方いらっしゃれば教えてください！

## 参考文献
1. https://github.com/JaciBrunning/quokka-lua/blob/master/bytecode_structure.md
    - Lua5.3のバイトコード実装に関するまとめです。
    - 本記事を読んで感覚を掴んだ後、この記事を参照するとバイトコードがより理解できると思います。
2. https://www.programmersought.com/article/55296061925/
    - Lua実装を暗号化/復号化する手法について書かれています。
    - Luaのバイトコードが難読化されたり、そもそも実装が明らかでなかったりする場合に参考にしてください。
3. https://the-ravi-programming-language.readthedocs.io/en/stable/lua_bytecode_reference.html
    - Luaのopcodesやアセンブリ実行の仕組みを解説してくれています。
4. https://nymphium.github.io/2016/06/17/luaexpression.html
    - 数少ない日本人Luaユーザの貴重なブログの更にレアな現在も更新が行われているものの、Lua5.3に関する資料ページです。主にlong string や LuaInterger型に関する説明が書いてあります。
        - long stringについては若干誤りが含まれています。詳細は省きますが、type tag = 0x14の時、次のバイトが0xffなら書いてある通りですが、それ以下（例えば0x32等）の場合はshort string（type tag=0x04）と同様に読みます。（0x32自体を含めて0x32=50バイト確保されている）
    - 全然知り合いじゃないですが、この方のLua資料全般とてもわかりやすいので一度目を通すと世界が広がったりするかもしれませんです。


## 補遺
- 世の中にはバイトコードを読むための言語もあるみたいです。バイナリエディタの時代は終わったのかもしれませんね....ex.) [Kaitai Struct](https://kaitai.io/)