Kaitai Struct を使って、バイナリデータのパーサを作ってみる

# はじめに
LOCAL学生部アドベントカレンダー11日目

つよつよな人ばかりで「自分弱すぎないか…？」と心配になったので、僕は変化球を投げることにしました。
僕が探した限りでは日本語の文献が存在しないため、今後これについて調べた人はほぼ自動的にこの記事を目にするのではないでしょうか。
そんな皆さんにお願いです。
「コイツ何言ってんだ？間違った情報だらけじゃないか」と思ったら、是非コメントください。
全力で修正します。

# Kaitai Struct って何？
## 概要
公式: [kaitai.io](https://kaitai.io/)

> Kaitai Struct は、バイナリデータ構造を記述するために使用される宣言型言語です。


独自の言語で書いたデータ構造をもとに、バイナリデータのパーサのソースコードを自動生成できます。
<details><summary>対応言語(2019年12月2日現在)</summary><div>

- C++ / STL
- C\#
- Go (entry-level support)
- Java
- JavaScript
- Lua
- Perl
- PHP
- Python
- Ruby
</div>
</details>

## license
のちに記述するCompilerとVisualizerはGPLv3+であり、各言語のライブラリはMIT(JSはApache v2)
これって、Compilerを用いて生成したソースコードはGPLに感染するのだろうか…？
詳しい人教えてください。

# インストール
## Kaitai Struct Compiler (KSC)
インストールに関する詳しい情報は[こちら](http://kaitai.io/#download)
Macは`brew install kaitai-struct-compiler`で一発です。
Windowsは、上記のリンクに飛んでインストーラをダウンロードしてください。
<details><summary>Debian/Ubuntuベースのディストリビューションなら公式の.debリポジトリからパッケージをインストールできます。</summary><div>

```shell
# Import GPG key, if you never used any BinTray repos before
sudo apt-key adv --keyserver hkp://pool.sks-keyservers.net --recv 379CE192D401AB61

# Add stable repository
echo "deb https://dl.bintray.com/kaitai-io/debian jessie main" | sudo tee /etc/apt/sources.list.d/kaitai.list
# ... or unstable repository
echo "deb https://dl.bintray.com/kaitai-io/debian_unstable jessie main" | sudo tee /etc/apt/sources.list.d/kaitai.list

sudo apt-get update
sudo apt-get install kaitai-struct-compiler
```
</div></details>
その他のOSを用いている場合は、[ここ](https://github.com/kaitai-io/kaitai_struct_compiler)からCloneしてビルドしましょう。

## Kaitai Struct Visualizer (KSV)
これは`.ksy`ファイルのためのシンプルなビジュアライザです。
`Ruby`で書かれており、`gem`パッケージとして入手できます。

```shell
gem install kaitai-struct-visualizer
```
([Gitリポジトリ](https://github.com/kaitai-io/kaitai_struct_visualizer))

# 使ってみる
有名なファイルについては、[公式のgithubリポジトリ](https://github.com/kaitai-io/kaitai_struct_formats)に`.ksy`ファイルが存在します。
(ここに存在する`.ksy`ファイルを利用する場合、ファイル内の`meta/license`に記述されたライセンスを確認してください。)
もしあなたが新しい`.ksy`を書いたなら、プルリクエストを送りましょう。
([kaitai_struct_formats/CONTRIBUTING.md](https://github.com/kaitai-io/kaitai_struct_formats/blob/master/CONTRIBUTING.md))

## 例) matrix
<details><summary>ファイルへの保存(np.array)</summary><div>

```python:matrix.py
import numpy as np
import struct


def create_header(*mats: [np.ndarray], magic: bytes = None) -> bytes:
    header = magic
    header += struct.pack('<H', len(mats))
    length = len(header) + 8 * len(mats)
    for mat in mats:
        header += struct.pack('<HH', mat.shape[0], mat.shape[1])
        header += struct.pack('<I', length)
        length += 4 * mat.shape[0] * mat.shape[1]
    return header


mat1 = np.random.randint(-1024, 1024, [3, 3], dtype=np.int32)
mat2 = np.random.randint(-1024, 1024, [5, 9], dtype=np.int32)
mat3 = np.random.randint(-1024, 1024, [2, 2], dtype=np.int32)

with open('test.matrix', 'wb') as o:
    magic = b'THIS IS MAT FILE.\x01\x02'
    o.write(create_header(mat1, mat2, mat3, magic=magic))
    for mat in [mat1, mat2, mat3]:
        for y in mat:
            for x in y:
                o.write(struct.pack('<i', x))

```
</div></details>
上記のコードで生成された`test.matrix`を、KSを使用して読み込んでみようと思います。

```:test.matrix
  Offset: 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 	
00000000: 4D 41 54 01 02 2F 03 00 03 00 03 00 20 00 00 00    MAT../..........
00000010: 05 00 09 00 44 00 00 00 02 00 02 00 F8 00 00 00    ....D.......x...
00000020: DC FE FF FF 49 01 00 00 A7 FF FF FF 17 02 00 00    \~..I...'.......
00000030: 25 FC FF FF 35 FF FF FF B5 00 00 00 CF FE FF FF    %|..5...5...O~..
00000040: E2 FF FF FF 5D 00 00 00 15 FE FF FF 30 FC FF FF    b...]....~..0|..
00000050: 4C 03 00 00 C1 FF FF FF B0 FD FF FF 31 02 00 00    L...A...0}..1...
00000060: 54 03 00 00 C4 FF FF FF 65 FF FF FF D0 FE FF FF    T...D...e...P~..
00000070: 75 01 00 00 DE FE FF FF ED 00 00 00 ED FC FF FF    u...^~..m...m|..
00000080: BE FD FF FF E5 02 00 00 EC FE FF FF 22 FE FF FF    >}..e...l~.."~..
00000090: C3 02 00 00 11 00 00 00 29 03 00 00 00 01 00 00    C.......).......
000000a0: 78 00 00 00 C4 FC FF FF 4C 02 00 00 88 00 00 00    x...D|..L.......
000000b0: 43 FF FF FF 35 FF FF FF A4 00 00 00 CF 02 00 00    C...5...$...O...
000000c0: 3A FF FF FF 33 FF FF FF BD FE FF FF F9 01 00 00    :...3...=~..y...
000000d0: 22 FF FF FF 3A 02 00 00 7C 00 00 00 15 FF FF FF    "...:...|.......
000000e0: D8 FE FF FF 42 00 00 00 82 02 00 00 24 02 00 00    X~..B.......$...
000000f0: 8A FE FF FF AF FF FF FF EF 02 00 00 96 01 00 00    .~../...o.......
00000100: 83 01 00 00 2F 02 00 00  
```

ファイルの構造は、頭から
1. `b'MAT\x01\x02/'`
2. 存在する行列の数(2bytes)
3. 各行列ごとのshapeとoffset((8 * 行列の数)bytes)
4. 行列本体
となっています。

これを`matrix.ksy`に記述してみます。

KSY(Kaitai Struct YAML)では、単一のユーザー定義型（公式から直訳）を宣言します。
ユーザー定義型は
- `meta`
- `doc`
- `seq`
- `types`
- `instances`
- `enums`
で構成されます。
すべてを持つ必要はありません。
詳しい情報は公式リファレンスをご覧ください。

### meta 

```yaml:meta
meta:
  id: matrix
  endian: le
```

記述するユーザー定義型の名前を`meta/id`に記述します。これは`.ksy`ファイルに必ず存在する必要があります。
`meta/endian`は構造体で使用するデフォルトのエンディアンを記述します(`le`/`be`)

### seq

```yaml:seq
seq:
  - id: magic
    contents: ['MAT', 1, 0x2, '/']
  - id: header_num
    type: u2
  - id: headers
    repeat: expr
    repeat-expr: header_num
    type: header
```
`seq`に、データの構造を記述していきます。
`id`は変数名になります。
データが定数である場合は`contents`に定数を記述します。
値を取得したい場合、`type`にデータの型を記述します（詳しくは[こちら](https://doc.kaitai.io/ksy_reference.html#primitive-data-types))。
後述する`types`に記述した型を利用することもできます。ここでは`header`型を利用しています。
`repeat`には `expr`, `eos`, `until`のいずれかを入れることができます(詳しくは[こちら](https://doc.kaitai.io/ksy_reference.html#attribute-repeat))
`expr`を入れた場合、`repeat-expr`に繰り返す回数を入れます。

### types

```yaml:types
types:
  header:
    seq:
      - id: shape0
        type: u2
      - id: shape1
        type: u2
      - id: offset
        type: u4
    instances: 
      mat_body:
        pos: offset
        io: _root._io
        type: matrix

  matrix:
    seq:
      - id: dim0
        repeat: expr
        repeat-expr: _parent.shape0
        type: dim1
    types:
      dim1:
        seq:
          - id: dim1
            repeat: expr
            repeat-expr: _parent._parent.shape0
            type: s4
```

`types`には、ユーザー定義型をネストして記述することができます。
`header`型で`instances`を使用していますが、これは`seq`のように順番に存在するもの以外のデータを読み込むために使用することができます。

```yaml:header.instances
instances: 
  mat_body:
    pos: offset
    io: _root._io
    type: matrix
```
使い方は`seq`によく似ています。
`id`はここでいう`mat_body`です。
`io`は使用するIOストリームです。
`pos`には`io`の頭からのバイト数が入ります。
`type`は`seq`の時と同じです。

### 変数について
一部のフィールド（今回は`repeat-expr`, `pos`, `io`）では、定数値だけではなく変数を参照できます。
まだ読み込まれていないデータを参照することはできません。
データはツリー構造になっており（ksvを利用するとわかりやすい）、親の要素を`_parent`で指定できます。
また、一番上の要素を`_root`で指定できます。

### Visualize

ここまでで、以下のコードを書くことができました。

```yaml:matrix.ksy
meta:
  id: matrix
  endian: le

seq:
  - id: magic
    contents: ['MAT', 1, 0x2, '/']
  - id: header_num
    type: u2
  - id: headers
    repeat: expr
    repeat-expr: header_num
    type: header

types:
  header:
    seq:
      - id: shape0
        type: u2
      - id: shape1
        type: u2
      - id: offset
        type: u4
    instances: 
      mat_body:
        pos: offset
        io: _root._io
        type: matrix

  matrix:
    seq:
      - id: dim0
        repeat: expr
        repeat-expr: _parent.shape0
        type: dim1
    types:
      dim1:
        seq:
          - id: dim1
            repeat: expr
            repeat-expr: _parent._parent.shape0
            type: s4
```

これをksv(Kaitai Struct Visualizer)を使用して可視化してみましょう。
使い方は`ksv <file_to_parse.bin> <format.ksy>`です。

```shell:shell
$ ksv test.matrix matrix.ksy
```

```:ksv
[-] [root]                              00000000: 4d 41 54 01 02 2f 03 00 03 00 03 00 20 00 00 00 | MAT../...... ...
  [.] magic = 4d 41 54 01 02 2f         00000010: 05 00 09 00 44 00 00 00 02 00 02 00 f8 00 00 00 | ....D...........
  [.] header_num = 3                    00000020: dc fe ff ff 49 01 00 00 a7 ff ff ff 17 02 00 00 | ....I...........
  [-] headers (3 = 0x3 entries)         00000030: 25 fc ff ff 35 ff ff ff b5 00 00 00 cf fe ff ff | %...5...........
    [-] 0                               00000040: e2 ff ff ff 5d 00 00 00 15 fe ff ff 30 fc ff ff | ....].......0...
      [.] shape0 = 3                    00000050: 4c 03 00 00 c1 ff ff ff b0 fd ff ff 31 02 00 00 | L...........1...
      [.] shape1 = 3                    00000060: 54 03 00 00 c4 ff ff ff 65 ff ff ff d0 fe ff ff | T.......e.......
      [.] offset = 32                   00000070: 75 01 00 00 de fe ff ff ed 00 00 00 ed fc ff ff | u...............
      [-] mat_body                      00000080: be fd ff ff e5 02 00 00 ec fe ff ff 22 fe ff ff | ............"...
        [-] dim0 (3 = 0x3 entries)      00000090: c3 02 00 00 11 00 00 00 29 03 00 00 00 01 00 00 | ........).......
          [-] 0                         000000a0: 78 00 00 00 c4 fc ff ff 4c 02 00 00 88 00 00 00 | x.......L.......
            [-] dim1 (3 = 0x3 entries)  000000b0: 43 ff ff ff 35 ff ff ff a4 00 00 00 cf 02 00 00 | C...5...........
              [.] 0 = -292              000000c0: 3a ff ff ff 33 ff ff ff bd fe ff ff f9 01 00 00 | :...3...........
              [.] 1 = 329               000000d0: 22 ff ff ff 3a 02 00 00 7c 00 00 00 15 ff ff ff | "...:...|.......
              [.] 2 = -89               000000e0: d8 fe ff ff 42 00 00 00 82 02 00 00 24 02 00 00 | ....B.......$...
          [-] 1                         000000f0: 8a fe ff ff af ff ff ff ef 02 00 00 96 01 00 00 | ................
            [-] dim1 (3 = 0x3 entries)  00000100: 83 01 00 00 2f 02 00 00                         | ..../...        
              [.] 0 = 535
              [.] 1 = -987
              [.] 2 = -203
          [-] 2
            [+] dim1
    [-] 1
      [.] shape0 = 5
      [.] shape1 = 9
      [.] offset = 68
      [-] mat_body
        [+] dim0
    [+] 2
```

うまく読み込めているようです。

## ファイル解凍
本題です。
[こちら](https://qiita.com/mueru/items/2e99832304cf8b89d3ec)の記事で圧縮ファイルを作りました。
今回はこの圧縮ファイルをKSを使用して解凍します。
ファイルの構造などは記事をご覧ください。

```yaml:mcp.ksy
meta:
    id: mcp
    encoding: UTF-8
    endian: le

seq:
  - id: file
    type: file
    repeat: eos
types:
    file:
        seq:
          - id: filename_len
            type: u4
          - id: filebody_len
            type: u4
          - id: filename
            type: str
            size: filename_len
          - id: filebody
            size: filebody_len
            process: zlib
```

`meta/encoding`は、`type: str`で使用するデフォルトのエンコーディングを指定します。
`repeat: eos`はストリームの最後まで繰り返します。
`process: zlib`は、読み込んだデータをzlibで解答します。（すごく便利）
※ `process`の詳しい情報は[こちら](https://doc.kaitai.io/ksy_reference.html#spec-process)

ksc(Kaitai Struct Compiler)を使用して`mcp.ksy`からコードを生成します。

```:usage
Usage: kaitai-struct-compiler [options] <file>...

  <file>...                source files (.ksy)
  -t, --target <language>  target languages (graphviz, csharp, all, perl, java, go, cpp_stl, php, lua, python, ruby, javascript)
  -d, --outdir <directory>
                           output directory (filenames will be auto-generated)
  -I, --import-path <directory>:<directory>:...
                           .ksy library search path(s) for imports (see also KSPATH env variable)
  --go-package <package>   Go package (Go only, default: none)
  --java-package <package>
                           Java package (Java only, default: root package)
  --java-from-file-class <class>
                           Java class to be invoked in fromFile() helper (default: io.kaitai.struct.ByteBufferKaitaiStream)
  --dotnet-namespace <namespace>
                           .NET Namespace (.NET only, default: Kaitai)
  --php-namespace <namespace>
                           PHP Namespace (PHP only, default: root package)
  --python-package <package>
                           Python package (Python only, default: root package)
  --opaque-types <value>   opaque types allowed, default: false
  --ksc-exceptions         ksc throws exceptions instead of human-readable error messages
  --ksc-json-output        output compilation results as JSON to stdout
  --verbose <value>        verbose output
  --debug                  enable debugging helpers (mostly used by visualization tools)
  --help                   display this help and exit
  --version                output version information and exit
```

```shell:shell
$ ksc -t python mcp.ksy
```

```python:mcp.py
# This is a generated file! Please edit source .ksy file and use kaitai-struct-compiler to rebuild

from pkg_resources import parse_version
from kaitaistruct import __version__ as ks_version, KaitaiStruct, KaitaiStream, BytesIO
import zlib


if parse_version(ks_version) < parse_version('0.7'):
    raise Exception("Incompatible Kaitai Struct Python API: 0.7 or later is required, but you have %s" % (ks_version))

class Mcp(KaitaiStruct):
    def __init__(self, _io, _parent=None, _root=None):
        self._io = _io
        self._parent = _parent
        self._root = _root if _root else self
        self._read()

    def _read(self):
        self.file = []
        i = 0
        while not self._io.is_eof():
            self.file.append(self._root.File(self._io, self, self._root))
            i += 1


    class File(KaitaiStruct):
        def __init__(self, _io, _parent=None, _root=None):
            self._io = _io
            self._parent = _parent
            self._root = _root if _root else self
            self._read()

        def _read(self):
            self.filename_len = self._io.read_u4le()
            self.filebody_len = self._io.read_u4le()
            self.filename = (self._io.read_bytes(self.filename_len)).decode(u"UTF-8")
            self._raw_filebody = self._io.read_bytes(self.filebody_len)
            self.filebody = zlib.decompress(self._raw_filebody)
```

`mcp.py`が生成されたコードです。
これを使って解凍用のスクリプトを書きましょう。

```python:extract.py
from mcp import Mcp
import os
import sys

mcps = Mcp.from_file(sys.argv[1])
out = 'output/'
if len(sys.argv) >= 3:
    out = sys.argv[2]

for f in mcps.file:
    if os.path.dirname(f.filename):
        os.makedirs(os.path.join(out, os.path.dirname(f.filename)), exist_ok=True)
    with open(os.path.join(out, f.filename), 'wb') as o:
        o.write(f.filebody)
```

`python extract.py <target.mcp> [output_folder]`で解答することができます

ファイルの読み込みは、`KaitaiStruct.from_file(file_path)`で。
バイト列をそのまま読み込みたい場合、`KaitaiStruct.from_bytes(bytes)`で。
IOストリームの場合は`KaitaiStruct.from_io(io)`で。

# さいごに
KSはかなり便利だと僕は思います。
簡単に記述出来る上好きな言語で利用できるので、新しく覚えるコストがとても少なく済みます。
公式リファレンスは正直読みにくいですが、今後僕のようにKSについて記事を書いてくれる人が増えていくでしょう（多分）。

あなたもKSをつかって「解体」してみませんか？