【Malbolge完全攻略 第3回】Malbolgeの命令セットを読む。位置で変わる命令、crazy演算、実行のたびの暗号化

Malbolgeの命令の仕組み。三進法の表と、実行のたびに入れ替わる文字の輪 Web Development
この記事は約8分で読めます。

シリーズ:地獄のプログラミング言語Malbolge完全攻略(第3回/全4回)

前回は、Malbolge の生い立ちと、三進法の仮想マシンの作りを見ました。今回は、その上で動く 8つの命令を、一緒に1つずつ開けていきます。
命令が場所で変わる仕組み、crazy 演算、実行のたびに起きる暗号化。この3つが分かると、最終回の Hello World のプログラムが、ただの文字の羅列ではなくなります。

命令は、置かれた場所で決まる

Malbolgeの命令デコードの流れ。[C]にCを足して94で割った余りで命令が決まる

ふつうの言語では、同じ記号はいつも同じ命令です。Brainfuck の + は、どこに書いても「1増やす」です。Malbolge では、そうなりません。

Malbolge は、実行する命令をこう決めます。コードポインタ C が指すメモリの値 [C] を取り出して、そこに C の値(アドレスそのもの)を足し、94で割った余りを見ます。式で書くと (C + [C]) % 94 です。
同じ文字でも、置かれたアドレスが違えば、別の命令になります。足すのはアドレスなので、94アドレスごとに同じ並びがくり返されます。書く側は、「この文字をこのアドレスに置いたら、何の命令になるか」を毎回計算しなければなりません。

8つの命令

余りが次の8つのどれかなら、その命令が実行されます。それ以外の値は、何もしない命令(NOP)として扱われます。

(C+[C])%94 記号 名前 動き
4 i SetCodePtr C に [D] の値を入れる。C = [D]
5 < PrintChar A を256で割った余りを、文字として出力する
23 / ReadChar 1文字読み込んで、その文字コードを A に入れる
39 * RotateRight [D] を三進法で1トリット右に回し、結果を [D] と A に入れる
40 j SetDataPtr D に [D] の値を入れる。D = [D]
62 p CrazyOp A と [D] に crazy 演算をかけ、結果を [D] と A に入れる
68 o Nop 何もしない
81 v Halt 止まる

この表を見ながら、気づくことが3つあります。

  • 命令は8つだけ。Brainfuck と同じ数ですが、こちらには位置と暗号化が加わります
  • LOAD や STORE がない。メモリに値を置く方法は、回転(*)と crazy 演算(p)の2つしかない
  • 条件分岐がない。制御を動かせるのは、C と D を入れ替える i と j だけ

1つずつ中身を見ておきます。

j(40)は、D が指している場所の値を、新しい D にします。間接参照です。扱うデータの場所を変えられますが、行き先の値そのものを狙って作るのが難しいので、思った場所に D を向けるのは大変です。
i(4)は、D が指している場所の値を、新しい C にします。Malbolge で唯一のジャンプで、条件はありません。飛び先を決めたければ、その値を先にメモリに作っておく必要があります。

*(39)は、[D] の値を三進法で右に1トリット回します。10トリットの t9 t8 … t1 t0 は、t0 t9 t8 … t1 になります。いちばん下の桁が、いちばん上に移る形です。結果は [D] に書き戻され、A にも入ります。
p(62)は、A と [D] に、このあと見る crazy 演算をかけます。結果は [D] と A の両方に入ります。

/(23)は1文字読み込み、その文字コードを A に入れます。入力が終わっていたら、A には59,048が入ります。
<(5)は、A を256で割った余りを文字として出力する命令です。Malbolge で画面に文字を出す方法は、これだけです。

o(68)は何もしません。ですが、このあと見る暗号化の循環をやりくりするうえで、何もしない命令がどこに置けるかは大きな意味を持ちます。
v(81)で、プログラムは止まります。もう1つ、C の指す値が33〜126の外に出たときも、プログラムは止まります(リファレンスのインタプリタでは、止まらずに固まる場合もあります)。

crazy 演算

Malbolgeのcrazy演算の表。2つの入力トリットから出力トリットが決まる

crazy 演算は、2つの10トリットの値に対して、1トリットずつ別々にかける演算です。各トリットの答えは、この表で決まります。

A のトリット
[D] のトリット 0 1 2
0 1 0 0
1 1 0 2
2 2 2 1

A が 0001112220、[D] が 0120120120 のときを、上の桁から一緒にたどってみます。
1桁目は A が0、[D] が0なので、表から1。2桁目は A が0、[D] が1で1。3桁目は A が0、[D] が2で2。4桁目は A が1、[D] が0で0。
こうして10桁すべてを引くと、答えは 1120020211 になります。

AND にも OR にも XOR にも似ていない、わざと直感に反するように作られた演算です。それでも、メモリに値を作る数少ない手段なので、Malbolge でプログラムを組むなら、避けて通れません。

実行のたびに暗号化される

Malbolgeの暗号化の置換に含まれる循環の構造。68文字の大きな循環を含む

Malbolge でいちばんたちが悪いのが、命令を実行したあとの 暗号化です。
命令を1つ実行するたびに、C が指している場所の値が、次の置換表で別の文字に置き換えられます。[C] から33を引いた番号で、下の段の文字を引きます。

「!」は「5」に、「”」は「z」に、「#」は「]」に変わります。変わった文字が、もとの場所に書き戻されます。

ジャンプ(i)のときだけ、少し事情が違います。i を実行すると、C は [D] の値になります。暗号化は、その新しい C の場所にかかり、そのあと C が1つ進みます。そのため、飛び先として指定したアドレスの命令が暗号化されて、実際の実行はその次のアドレスから始まります。i そのものは、このとき暗号化されません。

循環

Malbolgeの1命令の実行サイクル。フェッチ、デコード、実行、暗号化、インクリメント

この置換表を何度もくり返しかけると、文字はいつか元に戻ります。Lou Scheffer の暗号解析で、この置換が 6つの循環に分かれていることが分かっています。
手元で数え直すと、長さは68、9、6、5、4、2文字でした。合わせて94文字で、1回で元に戻る文字(固定点)はありません。いちばん長い68文字の循環は、こう回ります。

6文字の循環は 37→103→117→111→120→58→37、2文字の循環は 70→74→70 です。

この循環があるから、Malbolge にも手がかりが生まれます。

  • 循環の長さだけ実行すると、その場所の命令は元に戻る。ループの中で、毎回ちがう命令を順番に実行させることもできる
  • 2文字の循環を使えば、「1回目は命令として働き、2回目は NOP」という切り替えが作れる
  • 何度暗号化されても、そのアドレスでは命令にならない値がある。計算すると、どのアドレスにも少なくとも1つあった。プログラムの「骨組み」に使える

ただし、3つめの値の多くは、ソースに直接書ける文字ではありません。ソースに書ける文字だけで見ると、そういう値がある位置は94のうち14でした。

1命令の流れ

Malbolgeの命令暗号化の置換表。実行後に命令の文字が別の文字に置き換わる

ここまでを、1命令の流れとしてまとめます。

  1. [C] を取り出す。33〜126の外なら止まる
  2. (C + [C]) % 94 で命令を決める
  3. 命令を実行する
  4. [C] を置換表で暗号化して、書き戻す(i のときは、飛び先のアドレスが対象)
  5. C と D を1ずつ進める(59,048の次は0に戻る)

これがくり返されるあいだ、プログラムは走りながら自分を書き換え続けます。

ソースに書ける文字

ソースの空白以外の文字は、すべて、置かれる位置で有効な命令にならなければなりません。
アドレス0(と94の倍数のアドレス)で使える文字は ' ( > D Q b c u の8つです。アドレス1では & ' = C P a b t の8つ。アドレスが1つ進むと、使える文字の文字コードが1つずつ下がり、「!」の下は「~」に回り込みます。
書ける「単語」は、位置ごとに違う8文字だけです。

HeLL:Malbolge のアセンブリ言語

この難しさを少しでも扱いやすくするために、Malbolge のアセンブリ言語も作られています。2013年に lutter.cc で公開された HeLL(Hellish Low-level Language)と、そのアセンブラの LMAO(Low-level Malbolge Assembler, Ooh!)です。
ラベルや命令名で、メモリのアドレスを直接いじる手間は減ります。それでも、位置と暗号化の難しさそのものが消えるわけではありません。

次回は、Hello World

次回は最終回です。ここまでの仕組みを使って、Malbolge の Hello World のプログラムが、どうやって作られ、どう動いているのかを追います。Andrew Cooke のビームサーチ、ジャンプを使わずに組み立てるやり方、そして実際のプログラムの最初の1手を、インタプリタで1ステップずつ見ていきます。

コメント

タイトルとURLをコピーしました