はじめに

LOCAL学生部アドベントカレンダー11日目

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

Kaitai Struct って何？

概要

公式: kaitai.io

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

独自の言語で書いたデータ構造をもとに、バイナリデータのパーサのソースコードを自動生成できます。

対応言語(2019年12月2日現在)

C++ / STL
C#
Go (entry-level support)
Java
JavaScript
Lua
Perl
PHP
Python
Ruby

license

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

インストール

Kaitai Struct Compiler (KSC)

インストールに関する詳しい情報はこちら
Macはbrew install kaitai-struct-compilerで一発です。
Windowsは、上記のリンクに飛んでインストーラをダウンロードしてください。

Debian/Ubuntuベースのディストリビューションなら公式の.debリポジトリからパッケージをインストールできます。

# 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

その他のOSを用いている場合は、ここからCloneしてビルドしましょう。

Kaitai Struct Visualizer (KSV)

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

gem install kaitai-struct-visualizer

(Gitリポジトリ)

使ってみる

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

例) matrix

ファイルへの保存(np.array)

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))

上記のコードで生成された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
で構成されます。
すべてを持つ必要はありません。
詳しい情報は公式リファレンスをご覧ください。

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にデータの型を記述します（詳しくはこちら)。
後述するtypesに記述した型を利用することもできます。ここではheader型を利用しています。
repeatには expr, eos, untilのいずれかを入れることができます(詳しくはこちら)
exprを入れた場合、repeat-exprに繰り返す回数を入れます。

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のように順番に存在するもの以外のデータを読み込むために使用することができます。

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

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

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

$ 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

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

ファイル解凍

本題です。
こちらの記事で圧縮ファイルを作りました。
今回はこの圧縮ファイルをKSを使用して解凍します。
ファイルの構造などは記事をご覧ください。

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の詳しい情報はこちら

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

$ ksc -t python mcp.ksy

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が生成されたコードです。
これを使って解凍用のスクリプトを書きましょう。

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をつかって「解体」してみませんか？

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