🎉

アセンブラをゼロから作って自作コンパイラをアセンブルするまで(日記)

2021/09/28に公開

assembler

tech

GNU Assembler互換(サブセット)のアセンブラをGo言語でフルスクラッチで作ってみました。

https://github.com/DQNEO/goas

開発22日目で自作Goコンパイラ(をセルフホストしたときに出力される20万行のアセンブリ)をアセンブルすることに成功しました。

どうやって作ったかというと、小さいコードを GNU Assembler (以下 as) に食わせて出力されたバイナリを観察する、を繰り返して中のロジックを推定し再現しました。as の実装は見ていません。(一瞬見たけど巨大すぎて何もわからなかった)

アセンブラ自作は、やってみるとコンパイラ自作よりだいぶ簡単でハマりポイントも少ないので、学習テーマとしてはおすすめです。2箇所ほど難所(命令エンコーディングのルールを理解するのと、ジャンプ命令の最適化)がありましたがそれ以外はさくさく楽しく作れました。

作ってみた結果、アセンブリ言語の理解が深まったのはもちろんのこと、ELFバイナリの構造が肉眼でわかるようになったりマシン語が読めるようになったり、readelf/objdump等のバイナリツールを使いこなせるようになったりと、得るものも大きかったです。

コードの規模

今のところターゲットは x86-64 Linux のみで、命令セットのごく一部だけをサポートしています。

$  wc -l *.go                                                               
  242 elf_writer.go
  843 encoder.go
  766 main.go
  549 parser.go
 2400 total

現時点で4ファイル、合計2,400行です。
コンパイラを作ったときは1万行書いても「おもちゃコンパイラ」でしかなかったですが、アセンブラの場合はこんな少ない行数で本格的なものが作れるのでびっくりです。それだけアセンブラに必要な機能が少ないということですね。(アセンブラの本質的な難しさはターゲットマシンの種類と命令の多さにあるのかもしれません)

コードはなるべくシンプルにわかりやすく書いたので、アセンブラの実装に興味ある方はぜひ中を見てみてください。Go言語特有の機能(goroutineとか)もあまり使わないようにしています。

以下、開発日記です。(ツイッターとgit logからの書き起こし)

1日目とにかくバイナリを吐いてみる

アセンブラ作るのってどんな感じだろうという好奇心からはじめて見た。

まずは 42でexitするだけの小さなアセンブリコードを用意して、

min.s

.text
.global main
main:
  mov $42, %rax
  ret

GNU Assembler (as) にアセンブルさせてみる。

 $ as -o min.o min.s

するとELFオブジェクトファイル min.o が生成される。

ここで、これと同じバイナリを吐くプログラムを作れば、それはアセンブラと言えそうだ。(強引)

というわけで min.o のバイナリをそのままGoのプログラムに埋め込んで標準出力に吐いてみる。

package main

import "os"

// binary data of min.o
var data []byte = []byte{
        0x7f,0x45,0x4c,0x46,0x02,0x01,0x01,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x01,0x00,0x3e,0x00,0x01,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
        0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0xf8,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x40,0x00,0x00,0x00,0x00,0x00,0x40,0x00,0x07,0x00,0x06,0x00,
        0x48,0xc7,0xc0,0x2a,0x00,0x00,0x00,0xc3,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
        0x00,0x00,0x00,0x00,0x03,0x00,0x01,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x03,0x00,0x02,0x00,
        0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x03,0x00,0x03,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
        0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x01,0x00,0x00,0x00,0x10,0x00,0x01,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
        0x00,0x6d,0x61,0x69,0x6e,0x00,0x00,0x2e,0x73,0x79,0x6d,0x74,0x61,0x62,0x00,0x2e,0x73,0x74,0x72,0x74,0x61,0x62,0x00,0x2e,0x73,0x68,0x73,0x74,0x72,0x74,0x61,0x62,
        0x00,0x2e,0x74,0x65,0x78,0x74,0x00,0x2e,0x64,0x61,0x74,0x61,0x00,0x2e,0x62,0x73,0x73,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
        0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
        0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x1b,0x00,0x00,0x00,0x01,0x00,0x00,0x00,
        0x06,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x40,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x08,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
        0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x01,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x21,0x00,0x00,0x00,0x01,0x00,0x00,0x00,
        0x03,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x48,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
        0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x01,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x27,0x00,0x00,0x00,0x08,0x00,0x00,0x00,
        0x03,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x48,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
        0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x01,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x01,0x00,0x00,0x00,0x02,0x00,0x00,0x00,
        0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x48,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x78,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
        0x05,0x00,0x00,0x00,0x04,0x00,0x00,0x00,0x08,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x18,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x09,0x00,0x00,0x00,0x03,0x00,0x00,0x00,
        0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0xc0,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x06,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
        0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x01,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x11,0x00,0x00,0x00,0x03,0x00,0x00,0x00,
        0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0xc6,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x2c,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
        0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x01,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
}

func main() {
        os.Stdout.Write(data)
}

as と同じ出力を吐くプログラムができた。

なにか物作りをするときは、最初のハードルをおもいきり下げるのが重要だ。「はじめること」が一番大変だから。
これが動いた時点で、このプロジェクトはいけるのではという予感がした。

さてWikipediaのELFフォーマットの解説を見ると、先頭のいくつかは決まった値を出力すればいいみたいだ。そこで先頭部分はこういう風に定義して、

var magickNumber = []byte{
        // 0x7F followed by ELF(45 4c 46) in ASCII;
        0x7f,0x45,0x4c,0x46,
}

var EI_CLASS = []byte{0x02} //  1 or 2 to signify 32- or 64-bit format, respectively.

そのまま書き出す。

os.Stdout.Write(magickNumber)
os.Stdout.Write(EI_CLASS)

オブジェクトファイルを吐く"プログラム" っぽくなってきた。

バイナリ列をベタ書きするのはダサいのでヘッダー構造体を定義してみた。

type Elf64_Ehdr struct {
       e_ident [16]uint8
       e_type uint16
...
}

Goはunsafeを使うと構造体をそのままバイナリとして書き出すことができるので便利。
Goの変数とELFはどちらもリトルエンディアンなのでこういうことができる。

var buf []byte = ((*[unsafe.Sizeof(elfHeader)]byte(unsafe.Pointer(&elfHeader)))[:]
os.Stdout.Write(buf)

ELFの解説を読むと、Header値のいくつかは、これから吐くべきデータの中身をもとに動的に計算できるようなので、プログラム側で計算してみた。

各セクションヘッダーについても同様に構造体を定義してoffsetを動的にセット。

2日目謎のゼロ埋め

e_shoff (Section header table file offset) を動的に計算するようにしてみた。

as の出力を観察していたら、あるSectionの隙間と、Section Header Tableの直前に謎のゼロパディングがあるのを発見して、これはなんだろうと半日格闘したら謎が解けた

Sectionの隙間にあるゼロ埋めは、ELFの仕様で決まっている。sectionの offset開始地点が2の乗数になるようにゼロ埋めしなきゃいけないケースがある。sh_addralign によって挙動が決まる。
Section Header Tableの直前のゼロ埋めは、ELF仕様では決まっておらず、おそらく)GNU独自のもの。なくても動くっぽい。(手元では動いた)

てなことをツイートしていたらruiさんからアドバイスをいただけた。ありがとうございます。

テストして使っている短いアセンブリコードを少し変えてみると、自分のoffset計算のバグが簡単に見つかるので面白い。この体験は何かに似ている。TDDのイエローグリーンレッドのサイクルだ。

今のところ "GNU Assemblerと同じバイナリを吐くこと" を期待値としているので、出力バイナリをdiffで比較するだけで簡単にe2eテストができる。
出力バイナリを実行しなくてもよいというのは快適だ。バイナリの実行時バグをgdbで追うというのはかなり大変で、1作目のGoコンパイラ minigo を開発したときにさんざん体験したけど生産性が悪いのでなるべく避けたい。

関数呼び出しするアセンブリを as に食わせてみたら、 .strtab やら .symtab やらのコンテンツが増えた。自作アセンブラでもこれらを動的に生成できるようにしてみた。「シンボルテーブル」というのも名前はよく聞くけど何のことかわかってなかったが、自分で作ってみるとはっきりわかる。

3日目 ELFバイナリに慣れてくる

.symtabとか.strtabってなんで "tab" なんだろう？とずっと疑問だったんだけど、"table"の略っぽいと気づいて目からウロコ。"タブ"かと思ってた。略すなら tbl とかにしてくれ〜

ubuntu 21.04 → 21.10 にアップグレードしたら、as が吐くオブジェクトファイルの内容が少し変わった。こんなに古いツールでも微妙に進化が続いてるのね。

生のELFバイナリを見て、どのエリアにどんな情報が埋まってるかが肌感覚でわかるようになってきた。これは思わぬ副効果...!

テストコードにもっといろいろな要素を詰め込んでみて、.data セクションやら　.rela セクションやらも吐けるようにしてみた。吐くといっても現段階では固定値を吐いてるだけだけど。

当面必要な ELFのセクションはすべて形式的に出力できるようになった。あとはいよいよアセンブリ→機械語変換と、シンボル・アドレス周りの解析・構築に入っていく

4日目パーサを作り始める

パーサーを自作してて、言語マニュアルを読んでるんだけど、こんなゆるい言語仕様で35年間も動き続けてることにびっくり。
一番重要なsymbolの文法定義が2箇所に重複して定義されてたり(表現も微妙に違う)するし、Go言語に慣れた身からするとカルチャーショックだ。
まあ gcc のツールチェイン内部で使われる想定の言語だし、仕様化はそこまで重要じゃないのかも。

Goのパーサを書いたときと同じ設計でやり始めたけど、GNU Assemblerは言語仕様的に token と ast がきっちりレイヤ分けされてないことに気づいたので、全部捨ててやり直した。今度はうまく行きそう。

「言語仕様」と言ったけどそもそもあれは単なるマニュアルであって「言語仕様」ではないか。

5日目パーサが完走

パーサが対象のソースファイルを全行パースできるようになった。気合いれたら2-3日でできるもんなのね。
GASの文法は「1行が1 statement 」「directiveも命令の一種」みたいな極端な設計思想になっていて面白い。

パーサの自作、機能を足していくとパースできる文の量が指数関数的に増大していって、最後一気にファイル末尾まで完走する瞬間はかなり感動する。

こんな入力が

こうなる

6日目

入力ファイルをパースした結果を使って文字列テーブル、シンボルテーブル、dataセクションを動的に組み立てられるようになった。これは感動。
今まで固定バイナリを吐いていたインチキアセンブラだったものが、こうやって本物っぽくなっていく過程がたのしい。

次はいよいよアセンブリ命令を機械語に変換するロジックにとりかかる。

7日目

アセンブリ→機械語への変換ルールがめちゃくちゃ難しい。特殊な専門用語のオンパレードで初心者を寄せ付けない感じある。

中途半端に内容のあるアセンブリファイルを処理しようとしたら行き詰まったので、空のアセンブリファイルから再スタートすることにした。

as は空のアセンブリファイルを渡すとちゃんと validなELFファイルを吐いてくれる。アセンブリ開発は、hello worldとかじゃなくて、命令が一個もない空のファイルからスタートすればよいことに今気づいた。
「validなELFバイナリを吐く」ということと「吐いたバイナリがちゃんと動く」は全く別の話であって、後者を意識する必要はない(as と同じバイナリを吐くのなら)。そう考えたら頭がスッキリした。
(この発見は、後から見ればかなり大きなマイルストーンであった)

ちまちまリファクタリングをしたりELFに関する未実装部分を直した結果、空入力に対して as と同じバイナリを生成できるようになった。

8日目

再度命令エンコーディングに挑戦。
この解説記事を見ながら命令を一個ずつ丁寧に分析してみたら、少しわかってきた。

コツは、32bit命令から始めること。64bit命令は激ムズ。

movl $1, %eax # (32bit)
movq $1, %rax # (64bit)

アセンブリ上の見た目はほぼ同じなのに、機械語にすると全然違う。32bit → 64bitに拡張するときに互換性を維持しながらうまいこと設計した結果、こうなったらしい。

64bit命令も、がちゃがちゃやってたら動くコードが少し吐けるようになった。
2日ほど格闘した甲斐あって簡単な機械語命令は読めるようになってきた。

ローカル関数定義に対応したりグローバル変数に対応したり。

call命令は相対アドレスを指定してジャンプするのだとはじめて知った。コンパイラを作ってるときは全く気にしたことがなかった。

.dataセクションでグローバル変数の値のところで別のグローバル変数を参照しようとすると、.relaセクションなるものが必要になったので生成してみる。意味はわかっていない。

readelf と objdump と xxd と hexdump、どれも役割がかぶっててどれ使えばいいのか混乱する...w
とりあえず各コマンドのオプションをいろいろ試してみた。

readelfのオプションを全部調べて、自分用にカスタマイズしたラッパー( readelf.sh ) を書いたら一気に QOLが向上した。こういう環境整備は非常に重要。もっと早い段階でやっといてもよかった。

9日目 ModR/Mわからん

.rela.data, .rela.text を動的に正しく生成できるようになってきた。

ModR/M というやつに少しずつ慣れてきた。

ModR/M、 mod=0b00 で、r/m=0b101 の場合は特別扱いで、 RIP-Relative Addressingになるらしい。スーパーややこしい。

命令をいくつかサポートして ELF対応もちゃんとやったら、
42で exit するコードがアセンブルできるようになった。

さらに命令エンコーディングをちまちま実装。
movq 0(%rsp), %rdi みたいな命令を機械語に変換するのに1時間かかる (調査時間が)

10日目２進数の重要性に気づく

命令エンコーディングのバグをちまちま修正。
相変わらず命令エンコーディングが難しいのだが、方眼紙にビット列を書くという画期的な方法を思いついた。

今まで16進数と2進数は相互変換可能だし実質同じものだと思ってたんだけど、全然そうではなかった。x86-64は ModR/Mみたいな7bitの情報が16進数の2桁分にまたがっているので、16進数が役に立たない。常に2進数で考えないとダメ。

50行くらいのアセンブリを完璧にアセンブルできるようになった。
Makefile を全部書き直してすっきり。

11日目ツールへの投資

やたらとググるのをやめて、正攻法でIntelのマニュアルの英語をちゃんと読んでみたら、あの暗号みたいな命令表の読み方が少しずつわかってきた。

自作Goコンパイラのruntime内の小さい関数を1個アセンブルできるようになった。

ワンライナーで機械語変換できるようにしたり、ModRMをbit表現で視覚化するツールを作ったら生産性が瀑上がりした。やはり開発環境への投資は大事。

結果、方眼紙がいらなくなったw

パーサの未実装箇所を実装したり命令エンコーディングをちまちま実装したり。

12日目

gas の文法上の symbol と ELFの symbol は指してる内容に大きな差があることに気づいた。(前者は後者を包含していて、前者の集合の方がはるかに大きい)
ややこしい...

シンボルテーブルの生成ロジックを改善。だいぶ意味がわかってきた。
開発支援ツールを整備。

13日目 runtime.s のアセンブルに成功

.rela.text 生成ロジックを修正。このへんは正直意味があまりわかっていない。
ちまちま直していたら、自作Goコンパイラの runtime.s を完璧にアセンブルできるようになった！ as の出力とバイト単位で完全一致。これは気持ちがよい

アセンブラはコンパイラと違って、出力が小さいし「正解はひとつ」的な感じなので、意思決定で悩むポイントが少ないのがよい。パズルを解いてる感じ。

ELFの仕様書の存在を発見した。 https://refspecs.linuxfoundation.org/elf/elf.pdf

びっくりしたんだけど、ELFの仕様って1995年から変わってないのねw なんという息の長い技術や...

14日目

ひたすらリファクタリング。リファクタリングをすると、やってることの意味がわかってくる。

ビットパターンを作るのにGoのshift演算を使えることに気づいた。こういうときに使うのね。

15日目

stringリテラルやbyteリテラルに対応。
機械語エンコーディングをちまちま実装。

16日目コマンドラインの仕様をあわせる

コマンドライン引数の仕様を as と同じにした。Goのflagパッケージ初めてつかったけど便利。
deferとrecoverを駆使してエンコード失敗時の該当アセンブリコードを表示できるようにした。便利。
デバグ用のロガーやエラーメッセージを改善。
こうやって足回りを整備していくと、生産性が目に見えて向上する。

ModR/M の/1 とか/7 の意味がやっとわかった。Intelマニュアルの3.1.1.1に書いてあった。
機械語エンコーディングをバーっと実装。だいぶ速く書けるようになってきた。
.string や .byte をサポート。
定数計算をサポート。

マシン語命令に慣れてきたので hikalium さん作の opv86 を愛用してるんだけど、めちゃ便利！このツールが登場する前は人類はどうやって機械語を生成してたんだ....
https://hikalium.github.io/opv86/?q=add

17日目ジャンプ命令の最適化の難しさ

ジャンプ系命令は rel8 か rel32 で命令長が変わるんだけど、もしかしてジャンプ先との相対距離を計算した上で opcodeを決めないといけない？

as ここでちゃんと計算をして最適化を行っているっぽい。wikipediaを見たら確かにそのようなことが書かれている。この挙動を再現するのはかなり面倒そうだ...

いままで小さいプログラムしかアセンブルしてなかったから気づかなかった。そうなると as 完全互換は結構難しいかもしれない？
とりあえず最適化は後回しで、まず動くコードを目指すことにした。

18日目ジャンプ命令の最適化に苦戦(1)

アセンブラってのはアセンブリ言語をマシン語に変換するものだと思ってたけど、ジャンプ命令を変換してる最中にはジャンプ距離が決まらないのでマシン語に変換できないという謎のジレンマがある。未決定状態をうまく扱う必要がある。

エンコーディングしてる最中に各命令のアドレスを決められないことに気づいたので、あちこち修正が発生。何をどうすればよいのかわからなくなってきた。実装も迷走してきた。

19日目ジャンプ命令の最適化に苦戦(2)

ジャンプ先の距離を計測するために自分の命令長を決定するためにジャンプ先の距離を計測する、みたいな再帰的なコードを書いたら案の定無限ループした...w これはかなりむずい

ジャンプ先の途中に可変長のジャンプ命令が挟まっていると、お互いがお互いに距離計算を依存してしまうので永久に解決できないような？

プロジェクトの雲行きが怪しくなってきた。

Wikiipediaいわく、

This means that if the size of an operation referring to an operand defined later depends on the type or distance of the operand, the assembler will make a pessimistic estimate when first encountering the operation,

ふむ。

たしかに保守的な計算をして長い方の命令を選択すればよいけど、そうすると as と同じバイナリを吐くという路線が崩れてしまう... どうしたもんか。

20日目わからん

気分転換にコマンドラインオプションを改善したり、ビルド周りを整えたり。
距離計算についていろいろ試行錯誤してみる。やはり可変長命令は「可変長」状態としてあいまいなまま扱わなければいけない気がする。
まだ決定打は見えてこない。

21日目ひらめいた

気分転換に別の未実装箇所を直したり、軽めの作業をする。

夜、ついにひらめいた。

ジャンプ距離が不明といっても、とりうる最大距離と最小距離は計算できるのだ。それで最大距離が128未満なら短ジャンプだし、最小距離が128以上なら長ジャンプに決まる。これで可変長命令のいくつかを固定長にできる。
しかし残った可変長命令はどうすればいいのか？
がちゃがちゃ苦し紛れで雑なコードを書いて試してみたら、嘘のようにうまく動いた…
まじで何がうまくいったかわからんけど、めちゃくちゃうまく動いてる...!

22日目可変長命令を攻略

なんか標準ライブラリの関数の挙動がおかしいと思って調べてみたら、間違って自作標準ライブラリをimportしてたのが原因だった。 #自作勢あるある

ついにテストファイルの可変長命令の長さが as と完全一致した...!!

23日目あと数命令

as との差分があと 5命令というところまで来た!

16万バイトのバイナリのうち 6バイトだけ間違ってるんだけど、よくこんな微妙なバグはいったなw

ジャンプ距離の計算を3バイト間違えてるっぽい

あと3命令 ....!

キターー ELFバイナリの差分ゼロ！
これは勝てる

考案したアルゴリズム↓

ジャンプ先未定の可変長命令を、未決定リストに登録
未決定リストのメンバーについて、相対距離を特定できるものは卒業扱いにする
相対距離が未定でもレンジ(min,max)がわかれば命令長は決定可能
「命令長が決まった」と「ジャンプ先が決まった」を別の状態として扱う

完成

参考

他にアセンブラ自作をされていた事例を紹介します。
偉大な先人たちに拍手を贈りたいと思います。

あと、そもそもの GNU Assemblerを作られた方々にも敬意を表します。

seccamp2018でセルフホストCコンパイラをつくった

艮鮟鱇さんの全部入りCコンパイラです。
僕はこの記事に勇気づけられてアセンブラ開発をはじめました。素晴らしい発表をありがとうございます。

TCFM 13. 自作アセンブラ、リンカの最適化、トリッキーなビット操作の楽しさ、外資系IT企業のコーディング面接対策」

https://turingcomplete.fm/13

hikaliumさんのアセンブラ自作のエピソード。「実際のプロダクトの出力を観察する」という着想はここから学びました。

実行プログラム作成基盤をスクラッチで書いた

Drumatoさんの記事です。ELFリーダやローダまで自作されていてすごい。

言語処理系Slack

言語処理系Slackで質問や雑談の相手をしてくださった方々もありがとうございました。
強いひとたちが優しく教えてくださるので素晴らしいです。

まとめ

アセンブラの作り方: やるだけ

コードの規模

1日目 とにかくバイナリを吐いてみる

2日目 謎のゼロ埋め

3日目 ELFバイナリに慣れてくる

4日目 パーサを作り始める

5日目 パーサが完走

6日目

7日目

8日目

9日目 ModR/Mわからん

10日目 ２進数の重要性に気づく

11日目 ツールへの投資