防衛省サイバーコンテスト2024 writeup

防衛省サイバーコンテスト2024に参加してみました。

prtimes.jp

防衛省とサイバーコンテストという組み合わせに興味を惹かれ、CTF自体初めてでしたが、勢いで参加してしまいました。

CTFにおいてはWriteupを公開することがあるらしく、参加要領でも「開催時間中の解法の公開は禁止（コンテスト終了後の Writeup 公開は歓迎）」とされていたので、アウトプットと備忘も兼ねて、解けたものについて解法を書いていきます。

あまり多くは解けませんでしたし、解いたものにも力技がいくつかありますが、ご笑覧ください。

Crypto

Information of Certificate(10)

Easy.crt ファイルは自己署名証明書です。証明書の発行者 (Issuer) のコモンネーム (CN) 全体を flag{} で囲んだものがフラグです。

opensslを使うといいらしい。

$ openssl x509 -in Easy.crt -text -noout
Certificate:
    Data:
        Version: 1 (0x0)
        Serial Number: 2024 (0x7e8)
        Signature Algorithm: sha256WithRSAEncryption
        Issuer: C = XX, ST = Some-State, L = Nowhere, O = Invalid, OU = Invalid, CN = QRK7rNJ3hShV.vlc-cybercontest.invalid, emailAddress = user@QRK7rNJ3hShV.vlc-cybercontest.invalid
...

Missing IV(20)

NoIV.bin ファイルは、128bit AES の CBC モードで暗号化した機密ファイルですが、困ったことに IV (初期化ベクトル) を紛失してしまいました。このファイルからできる限りのデータを復元し、隠されているフラグを抽出してください。暗号鍵は 16 進数表記で 4285a7a182c286b5aa39609176d99c13 です。

暗号化鍵がわかっているため、暗号文を素の(ECBモードの) AESで復号できる。ブロックごとに復号したものとその一個前のブロックとをXORしてやれば、IVが必要な最初以外は復元できる。

encs = [] # 後から考えれば、わざわざencsに格納しなくても、最初から読み込んだ順に処理すればよかった

with open(f'NoIV.bin','rb') as fr:    
    cnt = 1
    read_data=fr.read(16)
    while(read_data and cnt < 10000):
        cnt += 1
        encs.append(read_data)
        read_data=fr.read(16)

c = AES.new(
    bytes.fromhex("4285a7a182c286b5aa39609176d99c13"),
    AES.MODE_ECB,
)


decs = []
for i in range(1, len(encs)):
    enc_block = encs[-i]
    enc_block_before = encs[- i - 1]
    
    x = c.decrypt(enc_block)
    decs.append(strxor(x, enc_block_before))

with open("result2.odt", "wb") as fw:
    for d in decs[::-1]:
        fw.write(d)

出てきたヘッダをバイナリで開くと mimetypeapplication/vnd.oasis.opendocument.textなるものが出てきたので、ググるとOpenDocument Text であることがわかる。

あとは適当なodtファイルからヘッダの欠けている部分を補完してやればwordで開けるようになる。……といいつつこのファイルを開いたら「修復しますか？」と出てきて、補完ステップいらない疑惑が。（後で試したら実際いらなかった）

フラグ獲得。

参考資料

この二つの記事が非常にわかりやすかった。

zenn.dev

yocchin.hatenablog.com

平文1ブロック目 ^ IV --(AES暗号)--> 暗号1ブロック目

平文2ブロック目 ^ 暗号1ブロック目 --(AES暗号)--> 暗号2ブロック目

Forensics

NTFS Data Hide(10)

NTFSDataHide フォルダに保存されている Sample.pptx を利用して、攻撃者が実行予定のスクリプトを隠しているようです。 仮想ディスクファイル NTFS.vhd を解析して、攻撃者が実行しようとしているスクリプトの内容を明らかにしてください。

ファイルイメージを解析するツールとして autopsy なるものがあるらしい。これでNTFS.vhdを解析してみたら、なんかSample.pptx:script とかいうファイルが出てきた。base64を見つけたのでこれをデコードしてフラグ獲得。

ただ原理はわかっていない。:scriptってなんなんだろう。

NTFS Data Delete(10)

NTFSFileDelete フォルダにフラグを記載した txt ファイルを保存したのですが、どうやら何者かによって消されてしまったようです。

問題「NTFS Data Hide」に引き続き、仮想ディスクファイル NTFS.vhd を解析して、削除された flag.txt に書かれていた内容を見つけ出してください。

「削除されたファイル」にflag.txtがあったので、ここからフラグを回収。

flag{resident_in_mft}

My Secret(30)

問題「HiddEN Variable」に引き続き、メモリダンプファイル memdump.raw を解析して、秘密(Secret)を明らかにしてください。

問題の順序はこれが最後だけど、メモリダンプを解析するツール Volatility3 をポチポチ触ってたらクリティカルなコマンドを打ってしまったのでこっちがさきに解けてしまった。

最初Volatile2 を使うも、profileの特定のためのimageinfoがうまくいかなかったし、stringsの出力を見てもWindowsであること以上はわからなかったので断念。Volatile 3のほうがよいという情報を見たこともありVolatile3に移行。

適当にコマンドを試す中で ./vol.py -f ../memdump.raw windows.cmdline とか打ったら

5516 7z.exe 7z x -pY0uCanF1ndTh1sPa$$w0rd C:\Users\vauser\Documents\Secrets.7z -od:\

とかいう死ぬほど怪しいログを見つけてしまった。どうやらこれは起動中のコマンドの引数を表示してくれるらしいので、次の目標がSecrets.7zを見つけることになる。

file系ということでfilescanとfiledumpを試す。まずはfilescanから。そのままだと大量に出てくるので grep で絞り込みをかける。

$ ./vol.py -f ../memdump.raw windows.filescan | grep Secret
0xe206bba6b1d0.0\Users\vauser\Documents\Secrets.7z      216
0xe206bbc4a2f0  \Users\vauser\Documents\Secrets.7z      216

filedumpの--virt_addrに与えるのはこれか。--physaddrと迷ったけどこっちで決め打ち。

$ ./vol.py -f ../memdump.raw windows.dumpfiles --virtaddr 0xe206bbc4a2f0

lsすると

file.0xe206bbc4a2f0.0xe206bbabada0.SharedCacheMap.Secrets.7z.dat
file.0xe206bbc4a2f0.0xe206bbabada0.SharedCacheMap.Secrets.7z.vacb

なる物々しいファイル名が出てくるが、datのほうを普通にSecrets.7zにリネームしてOK。あとは最初に出てきた7z.exeの引数にあったパスワードを使って解凍するとSecrets.rtfが出てきてフラグ回収。

このときはcatで中を見たから気が付かなかったが、後でwordで開いてみたらflagは丁寧に白文字になって隠されていた。

参考資料

qiita.com

blog.hamayanhamayan.com

jpn.nec.com

HiddEN Variable(20)

NTFSFileDelete フォルダにフラグを記載した txt ファイルを保存したのですが、どうやら何者かによって消されてしまったようです。 このメモリダンプが取得された環境にはフラグが隠されています。 memdump.raw を解析して、フラグを見つけ出してください。

メモリダンプファイルのダウンロードはこちら: メモリダンプは展開すると 4.5GB 程度になるので注意してください。

「取得された 環境 には」だし、ENvironment Variable か。環境変数を取得するコマンドがヘルプになくてわからなかった（ので飛ばしていた）が、ググるとwindows.envarsなるコマンドがあることが分かった。

すごい量のログが出てくるが、

FLAG   BDkPUNzMM3VHthkj2cVEjdRBqTJcfLMJaxT9si67RgJZ45PS

なるものを発見。

flag{BDkPUNzMM3VHthkj2cVEjdRBqTJcfLMJaxT9si67RgJZ45PS} は通らなかったのでもうひとひねり必要だった。base64でもなかったので、ほかにこの文字列が現れる場所があるのか、そもそもこのFLAGSは本当にフラグなのか、と思っていろいろコマンドを打ってはみたが、結局CyberChefでMagicしてみたらflagが出てきてしまった。

NTFS File Rename(20)

NTFSFileRename フォルダに保存されている Renamed.docx は、以前は別のファイル名で保存されていました。

問題「NTFS File Delete」に引き続き、仮想ディスクファイル NTFS.vhdを解析して、 Renamed.docx の元のファイル名を明らかにしてください。

Autopsyを探し回っても出てこなかったので、resident_in_mftって言ってたし出てこないかなーくらいのつもりでNTFS.vhdをstringsにかける。有意な情報は出てこない。バイナリエディタで見る。有意っぽい文字列が、間にゼロをはさみつつ登場していることがわかる。だからstringsに出てこなかったのか。

ただそれ以外のところで0のバイトが大量に出てきすぎて、スクロールしてもスクロールしても終わらず、諦める。

いっそpythonでゼロになってるバイトを取り除くとスクロールしやすくならないかな？って思って実装。これをバイナリエディタで見るとフラグが出てきた。……たぶん想定解じゃないよなあ。

Miscellaneous

Une Maison (10)

画像 maison.jpg の中にフラグが隠されています。探してみてください。

Forensics入門（CTF） #CTF - Qiita

この記事の手法をひととおり試してみたものの当たらなかった。しかし「意外と一番重要かもしれない」というこの記事の導きに従い、画像検索で元ファイルを探して、gimpで重ねて見比べると画像の一部がバーコードになっていることがわかった。これを読み込むとフラグ獲得。

String Obfuscation (10)

難読化された Python コード string_obfuscation.py ファイルからフラグを抽出してください。

import sys

if len(sys.argv) < 2:
    exit()

KEY = "gobbledygook".replace("b", "").replace("e", "").replace("oo", "").replace("gk", "").replace("y", "en")
FLAG = chr(51)+chr(70)+chr(120)+chr(89)+chr(70)+chr(109)+chr(52)+chr(117)+chr(84)+chr(89)+chr(68)+chr(70)+chr(70)+chr(122)+chr(109)+chr(98)+chr(51)

if sys.argv[1] == KEY:
    print("flag{%s}" % FLAG)

if文消したら普通に動いた。

Where Is the Legit Flag?(20)

fakeflag.py を実行しても偽のフラグが出力されてしまいます。難読化されたコードを解読し、本物のフラグを見つけ出してください。

exec(chr(105)+chr(109)+chr(112)+chr(111)+chr(114)+chr(116)+chr(32)+chr(122)+chr(108)+chr(105)+chr(98)+chr(44)+chr(32)+chr(98)+chr(97)+chr(115)+chr(101)+chr(54)+chr(52))
TANAKA = "eJyNVG1320QT/Z5z8h+GhNYvcR35JZZdaCGhT6D0gQTiFKjjlpU0ljZe7272xYpoy2/vrJRA+MA56IOPrJ29e+feO7sP84JJ2CohsEqYELBlktsCWM64tA6E3+gKEjSm6u/uXBzPz+AZtBY/vRx91Unffv908vOrw9PXz7/E23h/nf2mtp9/Gz05fn9zbv8sB18f/P7DWa9o/5/1f/Hf6KMlhzfJ9YvZ/x4NKzk185PNF6vud3uf/Xjx0eV/PLsUvz4ev/tw1bq6au3u7MNxorYIK5Yi4K0WRAhWyoAuKstTJiDDlFuuZB9C9WvOwEq2RpBsg2CUlxk4Is5XPIXEMGubwlNqVpVc5mB9nqN1BAG2LjeYM5OFpRVumCAUTPF+31yVtAhb+oB0OLcsN4ikjUTmCih8jqCVoSODUpdvLl+9JK0W8fhJdBD1dnfg7pnG3UGPS9ceT7vdQYdW9uFstQLtjVYWQTBiwiwYb6hJ65jDDUpHoPcIYfP03ahTo4yG/Sg8zb/WaNwKkPel8QQeQ3R7etqLh/CB3qKoF8/gbfO2mBwtF9GypvDCm9D4WipHbYsKLCP1S4MuLTADmzISw6gyiHGP3h52euMY+ArmxpNLguhHNY/B8JBaG0TwCAaDnjJZOy1MezjpPCQ3ig6O7pQ4HHYJa9adLQMXOBfeglMIFp0jH0pOCm8ZBZJSialrHIGLQJECnFmwBQqSvqk0zLkKtFGZT5GEo9Iz7yzPSF3MLUhynYw0NpximLzxXISmWchCU39soWRiDZqRHE04eF64lRfAsi0n2JrCCdaomlXBowBGKU0qMtFQHNYYpmYfzgPzBAu25SHAiv65Jk1esoT6K9TmDhCON4psoLhT7FO1aXKfKhnOqR3ykjwq6Zs3pslFG8K+hqXVzKzJLWVSmuJ6gqxWQY7cMF0fEqRvtWjLpSTIJr3XWFKo00Jp6oXoZaiRVqklmh8RNAy7+uHnWhGhf33ai7/9DQ5xWfeRlJiA4wiKkl544yjYoZu7S2XBl38h/Ldd4SbglAZoJu3hoRRHDs9hHA+nT/9Bhp7EIFs//OhoRoej8WQSQxemo3h69HBV02mu7Q5H46M4no46tUPzgqTOC7jxiBIytiF6YAXXGk1Ve8YMt3WQls2OkyqEKQyzUXRBhYwqT83QQKGjJVtQbVN6pike3CFUoVIijV7SZMx6wk/CjUzXcfCxIbe3Eip/P91e46z0MtGz6fjjHmHt7nwCLpe/Qg=="
TAKAHASHI = [0x7a,0x7a,0x7a,0x12,0x18,0x12,0x1d,0x12,0x07,0x7b,0x36,0x37,0x3c,0x30,0x36,0x37,0x67,0x65,0x31,0x7d,0x67,0x65,0x36,0x20,0x32,0x31,0x7b,0x20,0x20,0x36,0x21,0x23,0x3e,0x3c,0x30,0x36,0x37,0x7d,0x31,0x3a,0x3f,0x29,0x7b,0x30,0x36,0x2b,0x36]
exec(bytes([WATANABE ^ 0b01010011 for WATANABE in reversed(TAKAHASHI)]))

実行すると出てくるのはflog{8vje9wunbp984} だが、これは当然通らない。

とりあえずexecの中身を確認。 １個目は import zlib, base64 。２個目はexec(zlib.decompress(base64.b64decode(TANAKA)))'。もう一回execの中身を確認。すると、大量のコメントの中に

SATO = ... 
SUZUKI = ...
(''.join([SATO[i] for i in SUZUKI]))
print("flog{8vje9wunbp984}")

というコードが埋もれているのを発見。3行目をprintすればflagが出てくる。

Utter Darkness(20)

画像ファイル darkness.bmp に隠されているフラグを見つけてください。

真っ黒。実は真っ黒に見えて画素値1/255で書いてたりしない？と思ってpythonで読み込んで画素値を調べてみるも、全部ゼロ。 ただバイナリを見ると全部同じ値というわけではない。？？？と思ってbmpのヘッダを解読すると、どうやら画素を表現する値(0/1)は、直接色を指定しているわけではなく、ヘッダにあるパレットの番号を表しており、これによって色を指定しているらしい。そのパレットの色が0も1も真っ黒（0x000000）になっていたことが原因だった。片方を白（0xFFFFFF）に書き換えたらフラグが出てきた。

参考資料

www.setsuki.com

Serial Port Signal(30)

Tx.csv は、とあるシリアル通信の内容を傍受し、電気信号の Hi, Low をそれぞれ数字の 1 と 0 に変換したものです。通信内容を解析してフラグを抽出してください。

中身はmicroseconds（20μs刻み）とlogic（0/1）の対応表。どっかで見たことあるなと思いつつ「シリアル通信　Tx」などと検索するとUARTが出てくる。学部の実験でやったところだ！！！！！

0/1の切り替わりが最短でも100μsほど空いていたことから、baud rate は9600だろうとあたりをつけてuartのシミュレータをpythonで書く。いろいろネットで検索したけど実装の詳細がよくわからず、授業で配布された資料を引っ張ってきて書いた。やっぱりわかりやすかった。送信が7bitであることとparity bit があることが最初わかっておらず、結果がちょっとずれて原因の特定に時間を食った。

def get_logic(df, t):
    ret_df = df[(df["microseconds"] <= t)]["logic"]
    if(len(ret_df) == 0):
        return 1
      
    return int(ret_df.iloc[-1])

baudrate = 9600
dt = 1000 * 1000 / baudrate 
t = 5460 # 最初のlow bit の開始時刻
t += dt / 4


while(t < 40940):
    while(get_logic(df, t) == 1):
        t += dt
    s = ""
    for i in range(7):
        t += dt
        s = str(get_logic(df, t)) + s
    t += dt # parity
    t += dt
    if (get_logic(df, t) != 1):
        print(f"ERROR on t = {t}")
    print(chr(int(s, 2)))

Hello UART: synt{IjUZC5TD} Hell

やっぱUARTか。rot13かな？とあたりをつけたらやっぱりrot13だった。

flag{VwHMP5GQ}

参考資料

www.rohde-schwarz.com

パリティビットの存在と、データが8bitでない場合があることは知らなかった。

Network

FileExtract(10)

添付の FileExtract.pcapng ファイルからフラグを見つけ出し、解答してください。

Network解けたのはこれだけだった。

pcapngを解析するためにはWiresharkがよいらしい。眺めると、FTPでs3cr3t.zipを送っているログを発見。ファイルを書き出す方法を発見したのでs3cr3t.zipを落として展開。

……パスワードに阻まれる。ログのFTPをもう一回探すと

FTP Request: Pass br2fWWJjjab3

なるものを見つける。これを打ち込むと解凍に成功。パスを取得。

その時は何も考えなかったけど、FTPのログインパスワードとzipのパス同じってことだろうか。実質PPAP？

参考資料

unit42.paloaltonetworks.jp

Programming

Logistic Map(10)

下記のロジスティック写像について、x_0 = 0.3 を与えた時の x_9999 の値を求め、小数第7位までの値を答えてください(例:flag{0.1234567})。なお、値の保持と計算には倍精度浮動小数点数を使用してください。 x_{n+1} = 3.99 x_n (1 - x_n)

double x = 0.3;
for(int i = 0; i < 9999; i++){
    x = (double) 3.99 * x * ((double) 1 - x);
}
cout << std::setprecision(7) << x;

Randomness Extraction(20)

ファイル random.dat は一様でない乱数生成器の出力ですが、一部にフラグが埋め込まれています。フォン・ノイマンランダムネスエクストラクターを適用してフラグを抽出してください。

フォン・ノイマンランダムネスエクストラクター、初耳だった。カタカナで検索しても出てこないが、英語で検索をかけると出てくる。

2bitずつ読み込んで

src[2*i]	src[2*i+1]	操作
0	0	skip
0	1	dst[j]=0; j++;
1	0	dst[j]=1; j++;
1	1	skip

みたいな処理をするらしい。

最初、これを６～７回くらい繰り返し適用したらflagになるのかな～とか思ってたけど何も出てこず、一旦飛ばしていた。最後３０分くらいで見直したら１回目の適用結果（のバイナリ）にflagが普通に紛れ込んでいた。

参考資料

prefetch.eu

XML Confectioner(20)

添付の sweets.xml には、多数の sweets:batch 要素が含まれています。これらの中から、下記の条件すべてを満たすものを探してください。

少なくとも二つの子要素 sweets:icecream が含まれる 子要素 sweets:icecream には icecream:amount 属性の値が 105g を下回るものがない 子要素 sweets:candy の candy:weight 属性の値の合計が 28.0g 以上である 子要素 sweets:candy の candy:shape 属性が 5 種類以上含まれる cookie:kind 属性が icing でありかつ cookie:radius 属性が 3.0cm 以上の子要素 sweets:cookie を少なくとも一つ含む フラグは、条件を満たす sweets:batch 要素内において、最も cookie:radius 属性が大きな sweets:cookie 要素の内容に書かれています。

xml.etree.ElementTree でひたすら処理する。

tree = et.parse("sweets.xml")
root = tree.getroot()

ans = []
for child in root:
    icecream = []
    candy = []
    cookie = []
    for c2 in child:
        if ("icecream" in c2.tag) :
            icecream.append(c2)
        if ("candy" in c2.tag) :
            candy.append(c2)
        if ("cookie" in c2.tag) :
            cookie.append(c2)
    
    if len(icecream) < 2:
        continue
    
    prefix_icecream = "{http://xml.vlc-cybercontest.com/icecream}"
    prefix_candy = "{http://xml.vlc-cybercontest.com/candy}"
    prefix_cookie = "{http://xml.vlc-cybercontest.com/cookie}"
    
    
    skipFlg = False
    for i in icecream:
        if float(i.attrib[prefix_icecream + "amount"][:-1]) < 105:
            skipFlg = True
            break
    if skipFlg: continue
    
    s = 0
    shapes = set()
    for c in candy:
        s += float(c.attrib[prefix_candy + "weight"][:-1])
        shapes.add(c.attrib[prefix_candy + "shape"])
    if s < 28.0:
        continue
    if(len(shapes) < 4):
        continue
    
    for c in cookie:
        if (c.attrib[prefix_cookie + "kind"] == "icing" and
            c.attrib[prefix_cookie + "radius"][:-2] >= "3.0"):
            ans.append(child)
            break

for a in ans:
    max_rad = -1
    max_rad_c = None
    for c in a:
        if "cookie" in c.tag:
            if max_rad < float(c.attrib[prefix_cookie+"radius"][:-2]):
                max_rad =  float(c.attrib[prefix_cookie+"radius"][:-2])
                max_rad_c = c

print(max_rad_c.tag)
print(max_rad_c.attrib)

Trivia（各10点）

Q. Advanced Encryption Standard (AES) は、公募によって策定された標準暗号です。 現在採用されているアルゴリズムの候補名は何だったでしょうか?

A. Rijndael

Q. 最も番号が若い CVE レコードのソフトウェアパッケージにおいて、脆弱性が指摘された行を含むソースファイル名は何でしょう?

CVEレコードの一覧がだいぶ見つけづらかったが、 https://www.cve.org/Downloads を発見すれば最も若い番号がCVE-1999-0001であることがわかる。画面上部の検索窓に打ち込めば答えが見つかる。

A. ip_input.c

Q. 多要素認証に使われる本人確認のための3種類の情報の名前は何でしょう?それぞれ漢字2文字で、50音の辞書順で並べて「・」で区切ってお答えください。

A. 所持・生体・知識

Web

Browsers Have Local Storage(10)

http://10.10.10.30 にアクセスしてフラグを見つけ出し、解答してください。

右クリックメニューからInspectを選び、Storage > Local Storage を見るとフラグが見つかる。

結果・感想

Webやネットワークがほとんど解けなかったのが少し悔しいです。

一日丸々費やしてかなり疲れましたが、Google検索と地道な調査と閃きで進んでいくのが楽しかったです。

解けなかった問題や、解けても力技になった問題は、他の方のwriteupを見るなどして学習してみたいと思いました。

ソフトウェアシンセサイザーを実装するときにピッチを揺らす方法

結論

周波数 が時刻変化するとき、sin関数等に与えるべき位相は「 ×周波数」の積算値（積分）であって、 ではない。

実装例（C#）

• 時刻における周波数は、
• 時刻における位相は、
• よって、

const int SAMPLE_PER_SEC = 48000;
float length = 2;
float sample_size = SAMPLE_PER_SEC * length;
float[] waveform = new float[sample_size] ;
float phase = 0;
float base_freq = 440; // A4(hiA) 「栄光の架橋」の最高音らしい
float base_amp = 1;
float LFO_freq = 1;
float LFO_amp = 2 / 12; // 上下に全音一個分ずつ揺らす
for (int sample = 0; sample < sample_size; sample++)
{
    float t = sample / SAMPLE_PER_SEC;
   
    float LFO_value = LFO_amp * MathF.Sin(2 * MathF.PI * LFO_freq * t);
    float frequency = base_freq * MathF.Pow(2, LFO_value);
    float dt = 1.0F / SAMPLE_PER_SEC;


    phase += 2 * MathF.PI * frequency * dt;
    // 周波数を 2 * PI に収める処理
    if (phase > 2 * MathF.PI){
        phase -= 2 * MathF.PI;
    }

    float val = base_amp * MathF.Sin(phase) ;

    waveform[sample] = val;

}

備考

• 「周波数を に収める処理」について
  これをしないと、２～３秒経ってから数値計算をミスっていそうな音が鳴るようになります。たぶん丸め誤差です。

失敗例

• 時刻における周波数は、 （定義）
• 波の方程式、（が一定値なら正しい）
• よって、 （間違い）

const int SAMPLE_PER_SEC = 48000;
float length = 2;
float sample_size = SAMPLE_PER_SEC * length;
float[] waveform = new float[sample_size] ;
float phase = 0;
float base_freq = 440;  
float base_amp = 1;
float LFO_freq = 1;
float LFO_amp = 2 / 12; 
for (int sample = 0; sample < sample_size; sample++)
{
    float t = sample / SAMPLE_PER_SEC;
   
    float LFO_value = LFO_amp * MathF.Sin(2 * MathF.PI * LFO_freq * t);
    float frequency = base_freq * MathF.Pow(2, LFO_value);

    phase = 2 * MathF.PI * frequency * t; // y = A sin(2 * pi * f * t) <-- 間違い

    float val = base_amp * MathF.Sin(phase) ;

    waveform[sample] = val;

}

これをやると、ピッチが宇宙の彼方へと飛んでいきます。それもそのはず、位相が のとき、周波数はこれを微分した値 で、tが大きくなるとどんどん大きくなっていきます。

最初LFOを で実装してしまい、これが下手に解析的に積分できてしまうせいで、正しく（解析的に積分できないらしい）で実装したりADSRエンベロープを実装したりしようとしたときに、数値積分という発想に至らず、しばらく泥沼にはまってしまったので、書き残してみます。

参考資料

• 「瞬時位相・瞬時周波数」（英語版Wikipedia）

CPU実験の記録（byコンパイラ係）

はじめに

この記事は、僕のコンパイラ係としての活動をまとめたものです。

CPU実験の紹介

東京大学理学部情報科学科の３年後期（Aセメスター）には、「プロセッサ・コンパイラ実験」（通称「CPU実験」）という名物授業があります。この実験はざっくりというと「CPUを自作しよう！」というものです。学科の30人が各３～４人の班に分かれて、それぞれが「コア係」「FPU係」「シミュレータ係」「コンパイラ係」を担当することになります。

それぞれの係の詳細な説明は他の記事に譲りますが、大まかにはコア係がいわゆる中央演算装置（命令を読み込んで、演算して、結果をレジスタやメモリに書き戻す回路）を作ります。FPU係はこれに組み込むFPU（浮動小数点演算装置）を作ります。シミュレータ係はこのコアにおける命令列（プログラム）の実行結果をC++等（に限らず好きな言語）でシミュレートするソフトウェアを書きます。*1

そしてコンパイラ係の仕事は、大まかには次のようなものです。

• MinCamlという言語*2で書かれたソースコードを読み込んで、自分たちのISA（CPUが読み込む命令列のフォーマット）に則ったアセンブリを生成する
• 動作を変えない範囲でできる限り効率の良いコードを作成するよう最適化する
• コンパイラ実験の課題をやる*3

コンパイラを書くのに使う言語はなんでもよいですが、 OCamlで書かれたMinCamlコンパイラが公開されているので、これをベースに、自班ISAへの変更、種々の最適化、等の改造を加えていく人が多いです。僕もその方針をとりました。また、RustとかPythonとかを使って一から全部自分で書く（フルスクラッチ）していた人もいました。

なお、対象とするプログラムはレイトレーシング*4を実行するプログラム（minrt）です。完全に正しく動く（いわゆる完動）と次のような画像が出ます。

アセンブラについて

なお、これら４つの係のほかにも、どの係にも属さない（よって誰がやってもいい）仕事として、アセンブリを吐いた後に、それをCPUが読める形式である機械語に直すという仕事（アセンブラの作成）があります。うちの班では、これは神たるシミュレータ係にお任せすることになりました。

この判断は次の理由から大成功だったと思っています。

第一に、コンパイラ係としては、アセンブリさえ吐けば、その後の機械語への変換は気にしなくてよくなりました。もしコンパイラ係がアセンブラも書いていたら、「シミュレータ上でうまく動かない」理由がコンパイラのせいなのかアセンブラのせいなのかがわからず、デバッグ作業が大変になっていたでしょう。（コンパイラ係はアセンブラのバグを踏まなかったので、実際にバグったらどうなったかについては何とも言えないですが……）

第二に、機械語に「もとのアセンブリの何行目か」という情報を埋め込むことで、シミュレータの実行時「現在実行している場所やブレークポイントは、もとのアセンブリの何行目か」という情報が得られるようになりました。この作業も死ぬほど面倒だったようなので、シミュレータ係以外がアセンブラを書いていたらなおさら面倒だったでしょう。

やったこと（時系列順）

日記のようなものです。

シミュレータ上完動まで（～11月上旬）

第１週の班の顔合わせの時、コア係がいきなりISAを持ってきました。びっくりしたのですが、今思えばこれが相当のアドバンテージで、第１週からもう自班ISA向けの改造を始めることができました。また、前述のとおりアセンブラをシミュレータ係にお願いしていました。そのおかげでコンパイラに集中できたのも大きいです。

種々の最適化（コンパイラ実験の課題）と並行して改造を進め、第１週終了時にはデバッグ段階に至り、第２週終了時にはレイトレのコードをエラー落ちせずにコンパイルできるようになりました（結果はもちろんまだ正しくない）。そこからアセンブラが文法エラーを出さないようなコードを生成できるようになるまでが長く*5、結局第５週までかかりました。

アセンブラに通ってからは、運のいいことにデバッグが素直に終わり（クロージャ回りが相当の闇でしたが…）11/7にシミュレータ上で完動させることができました。

中間コードの出力と、中間コードや出力コードと元のプログラムの対応関係の明示

第１週に、コンパイラ実験第１回課題として実装しました。MinCamlコンパイラのプログラムを初めて読んだ段階で全体をいじらなきゃいけないため、死ぬほど大変な作業でした。が、以降のデバッグにものすごく役に立ちました。

ついでに、コンパイルオプション-kindとして指定することで、（ほぼ）任意の最適化の直後の中間コードを出力することができるようにもしています。これは第３週くらいに実装しました。

コンパイルオプション

ここでついでにコンパイルオプションについて述べます。もともとmin-camlにも、インライン展開する関数のサイズ-inline、最適化適用の繰り返しの回数-iterを指定するオプションがあったのですが、コンパイラを使いやすくするため、上述の中間コード出力を含め、他にもいろいろコンパイルオプションを実装しました。

たとえば、-id XX と指定することで、出力ファイルの末尾にXXという文字列を追加できます。適用する最適化の種類や条件を変えて出力結果を比較するときに便利でした。また、-on XX -off YYとすることで、最適化XXを適用し、最適化YYを適用しないことができるようになります。「特定の最適化の組み合わせによりバグが生まれることもあるので、原因を切り分けるため最適化をオンオフすることができるとよい」と先輩のブログにあったので、実装してみたところ、非常に助けられました。

これらのオプションを駆使して、

./min-caml minrt -kind Logic -iter 3 -off Tuple -id 3
./min-caml minrt -kind Logic -iter 2 -off Tuple -id 2 

などと指定し、吐き出されたminrt_Logic_3, minrt_Logic_2を眺めて、３回目の最適化でバグった最適化Logicを修正していました。

共通部分式削除

初出はコンパイラ実験第２回課題でした。

特筆すべきこととしては、副作用の扱いです。副作用のある共通部分式を削除してしまうとプログラムの意味が変わってしまいます。たとえば、極端な話

let _ = print_int 1 in
let _ = print_int 1 in
...

のprint_int 1は共通部分式ですが、当然これを削除するとまずいです。しかし、副作用の有無は判定不能なので、ある程度保守的な判断をせざるを得ません。

同様の判定はElim.f（MinCaml組み込みの不要定義削除）でも必要となりますが、これを流用すると「関数呼び出しや配列への書き込みはすべて削除しない」ことになってしまいます。例えば、

let rec fib x = if x <= 2 then 1 else (fib (x-1)) + (fib (x-2)) in
let a = fib 10 in 
let b = fib 10 in ...
let _ = arr.(0) <- a in
let _ = arr.(0) <- a in
...

のような場合は共通部分式削除が実際にはできるのに、「できない」と判断されてしまうことになります。

そこでより厳しい判定条件として、「関数間解析とエイリアス解析により副作用のありなしをより厳格に判断する」という方針の実装をしました。

• 関数は、その本体とその関数が呼び出す関数の中で両方副作用がないならば、副作用がない。

• 配列への書き込みは、値の同一性が保証されている限りは副作用がない。

ということです。

この工夫によっては、実装時点ではコンパイル結果に影響を与えませんでした。しかしその後第１２週に、shadow_check_one_or_matrixの中のshadow_check_one_or_groupの呼び出しが一部無駄であることに気づきました。shadow_check_one_or_groupは実質的には副作用がないのに、下手に配列の書き込みをやっているせいで「副作用がある」と判定されてしまっていました。単純化すれば

let rec f x = arr.(0) <- x; fib x in ...

みたいな構造です*6。

これをうまく「共通部分式削除できる」と判定することで共通部分式削除ができるようになり、１億命令ほど削減できました。

ただし、結局エイリアス解析は完全に嘘実装で実質的には機能していませんでした。これによりバグを踏んでしまったので、配列書き込みそのものの共通部分式削除は無効化してしまいました。

あとは、あんまり離れた共通部分式を削除してしまうと、レジスタ負荷が高まって逆によくないという話があり、その制御も実装しています。

ラムダリフティング

第３週に、コンパイラ実験第３回課題として実装しました。が、グローバル変数のメモリ番地固定化を導入すると、関数から自由変数が全部消えるため、結局実装の必要はそんなになかったです。

タプル平坦化

第４週～第５週に、コンパイラ実験第４回課題として実装しました。これが相当の曲者でした。

まず、実装方針が非常に面倒です。本当は必要なタプルだけを展開するのが望ましいのですが、よくよく考えるとこのタプルを展開するとこれも展開しなきゃいけなくなり、これも展開して……となってしまい、結局「すべてのタプルを展開する」のが一番楽になってしまいます。

しかし、すべてのタプルを展開すると、今度は異常にレジスタ負荷が大きくなってしまいます。さらに関数引数のタプルを展開した場合、引数がレジスタの個数（32個）に収まらなくなったりしてしまいます。そこで、「要素数n以下のタプルのみを展開する」という方針に移行しました。これもまた面倒で、たとえばn=2のとき(((1, 2, 3), (4, 5, 6)), 7)をどこまで展開するか？とか、いろいろ大量のコーナーケースが生じるので、これらを矛盾することなく処理する必要がありました。

また、タプルの配列の扱いについて、コンパイラ実験では

let arr = create_array 5 (1, 2) in ...

を

for(int i=0; i++; i<5){
  arr[2*i] = 1;
  arr[2*i+1] = 2;
}

に書き換える方針が示されていましたが、これでは配列アクセスのたびにindexに2を掛ける必要があって非効率なことに気づきました。なので、

let arr1 = create_array 5 1 in 
let arr2 = create_array 5 2 in ...

に書き換えるという効率化も行いました。

ここまでやっても、実行命令数自体はタプル平坦化を導入するほうが多くなってしまいました。その原因は、実装時点ではレジスタ負荷の問題だろうか、とか考えていました。これはある意味正解で、実行命令数は後述のグローバルレジスタ割り当てを実装してやっと減りました。関数呼び出し時生きている変数をstoreしなければいけないのが相当悪影響を与えていたようです。

完動からA1ターム終了まで（11月）

このあたりの無限最適化編が一番楽しかったです。まず共通部分式削除とインライン展開のパラメータをいじって50億命令くらいになりました。論理に関する最適化や、(float_of_int x) *. (float_of_int 2^n) をshift_left x nに置き換えたりするようなこまごました最適化を実装したりして40億命令にまで減らしました。さらに即値の利用（addiとかlw 4, 4(x4)とか）により、40億命令→30億命令くらいにまで減りました。この瞬間は本当に気持ちよかったです。

その後なんやかんやで25億命令まで減り、グローバル変数の導入で21億命令まで減りました。

論理に関する最適化

let b = if x = y then 1 else 0 in
let x = if b = 0 then e3 else e4 in ...

は

let x = if x = y  then e4 else e3 in ...

に置き換えたほうがお得です。より一般に、「then 1 else 0」ではなく「then e1 else e2」とかでも

let x = 
    if x = y then 
        if e1 = 0 then e4 else e3
    else
        if e2 = 0 then e4 else e3

とかにしたほうがお得です。then 1 else 0の場合より単純化できるという話も、MinCamlデフォルトの定数畳み込みがよしなにやってくれます。

なお、あんまりやりすぎるとコードサイズ爆発を招く最適化ですが、minrtの場合は動くのでヨシ！

即値の利用

特筆すべきことはそんなにないのですが、

addi tmp, x0, 8   # tmp = 8;  
add  b, a, tmp    # b = a + tmp;

を

addi tmp, x0, 8    
addi  b, a, 8  

に置き換えた結果不要になるtmp, どこに行ったんだろうなーとか思っていたのですが、MinCamlデフォルトのSimm18で消えていました。すごいなと思いました。

グローバル変数の導入

これも先述の先輩のブログが詳しいですが、minrtではプログラムの最初（というかglobals.ml）でグローバル配列を確保しており、レイトレ本体の中ではこれに対してload/storeを行っています。これを「変数に格納されたアドレスへのload/store」とみなすと関数内に自由変数が大量発生し大変なことになります。しかし、変数を確保するタイミングがプログラムの先頭であることを利用すればこれらのグローバル配列のメモリ上の位置は確定するので、グローバル変数をすべて定数に置き換えてやれば、「定数アドレスへのload/store」とみなすことができます。すると、自由変数はなくなるわ、アドレス計算等の定数畳み込みは促進されるわで幸せになれます。

年末まで（11月下旬～12月）

グラフ彩色によるレジスタ割り当て

このあたりでできる最適化が少なくなってきて、グラフ彩色によるレジスタ割り当てを実装しようと試みます。しかし、これが相当の地獄でした。

そもそもMinCamlにデフォルトで入っている貪欲なレジスタ割り当ては、単純な割にそんなに効率が悪いものではないです。一方グラフ彩色レジスタ割り当ての実装として参照するのはタイガーブックのアルゴリズムですが、これはかなり複雑です。まず生存解析の実装に２週間かかってしまいました*7。そのうえで彩色問題を解いたりSpillやCoalescingを考えつつうまいレジスタ割り当てを考えたり、callee save register*8を導入したり…などと考えると、効率の良いレジスタ割り当てにはかなりの時間的コストがかかります。

結局、「最適化だけを考えるならほかの部分に注力したほうがよい」という判断を下してしまい、グラフ彩色をあきらめてしまいました。

命令スケジューリング

グラフ彩色を凍結した後、コンパイラ実験第８週の課題として実装しました。lwの結果が返ってくるまでにaddiなどの別の命令を実行しておこう！というやつです。

単純なコアにおける命令スケジューリングについてはコンパイラ実験のスライドが割と詳しいのですが、うちの班ではコア係がスーパースカラプロセッサを作ってくれたので、資源制約の部分が少し特殊で、スーパースカラプロセッサをシミュレートするようなスケジューラを作成しました。すなわち、「現在発行できる命令」や「今実行しているこの命令は結果が返ってきているか」等を管理しておき、できる限り２命令を同時発行できるようにスケジューリングしています。

このときに同時発行できる命令の条件についてコア係さんに聞いてみたのですが、かなり複雑でびっくりしたのを覚えています。OCamlでもけっこうきついのに、よくVerilogで書けるなあ、と……

スケジューラは（よっぽど変なことをしない限り）命令の優先順位がおかしくても動きはしてしまうため、バグの存在が見えにくいです。実際、実装した時点では40秒のうちの2秒くらいしか変わりませんでした。しかし、コア係に指摘してもらったバグの修正や実装の改善点を取り入れてみたり*9などを2月上旬まで続けていった結果、最終的に20%も実行時間が減っていました。

試験終わりまで（1月）

このあたりで、計算量理論演習や知能システム論の課題がだいぶきつくなってきました。それが終わると試験のための準備が必要になり、CPU実験に回せるリソースが多くなくなってしまいました。

命令スケジューリングの実装も終わり、いよいよやることが見つけにくくなっていた時期でもありました。この時期実装した新しい最適化は連鎖するジャンプの除去くらいでした。それ以外ではもっぱら既存の最適化（論理最適化、共通部分式削除、タプル平坦化）の強化を進めていました。

びっくりしたのが、このあたりでインライン展開を、再帰関数以外はすべて展開するようにしたところ、もともと17億命令だったのが15億命令にまで減りました。２億命令も減ってびっくりしました。

最後の追い込み（～2/15）

ワードアドレッシング

２月に入ったくらいで班全体としてワードアドレッシングへの移行が完了しました。これにより、0.8億命令くらい削減できました。

グローバルレジスタ割り当て

この直後くらいにグローバルレジスタ割り当てが完成し、命令数が13億まで減りました。

関数呼び出しの依存グラフがDAG（つまり相互再帰がない）で、かつminrtの場合クロージャがない（どこに飛ぶかがわかっている）ため、末端の関数から順に「その関数が使うレジスタ」を確定させることができます。すると、レジスタ割り当ての時、関数呼び出し先で使わないレジスタに対して優先的にallocateすることが可能となります。このようなレジスタは関数呼び出し時に破壊されないため退避する必要がなく、結果として関数呼び出しに伴うload/store（スタックアクセス）を60%減らすことに成功しました。残りの40%はおそらくレジスタが足りなかったことによるもので、スタックアクセスは6500万回ほど残ってしまいました。

fabsとfneg

この後しばらくは命令スケジューリングのバグ取りに奔走することになりました。さらに、絶対値を取るとき

    fblt f0, f1, LABEL
    fsub f1, f0, f1
    jal CONT
LABEL:
CONT:
...

みたいな超無駄なことをしていたので、fabs（とついでにfneg）の実装を依頼しました。さらに、直後に飛ぶジャンプ命令の除去を実装しました。これにより12.6億命令まで減らすことができました。このとき2/11でした。

トレーススケジューリング

とうとうやることが見つからなくなり、コンパイラの本を眺めていると、「トレーススケジューリング」なる手法があることがわかりました。ちょうど、スーパースカラなのにIPCが0.7しか出ず、なんじゃこりゃと思っていたので、最後の大仕事としてトレーススケジューリングの実装をすることに決めました。

しかし、この時点で残り３日だったのと、そもそもあまり文献がなくて実装に相当苦労しました。この文献がわかりやすかったので、これを読みつつ実装を進めていました。スケジューリングの宿命として、しょうもないけど非自明なバグに苦しめられました。発表会当日の朝に投機的スケジューラという形でかろうじて部分的に完成したものの、実行時間は0.2s減、IPCは0.75にしかならず、力不足を感じました。

結果

最終結果は、命令数12.6億、実行時間14.5秒でいずれも２位となりました。１位の班はアーキテクチャをかなり工夫していたようです。結果として出てしまうとどうしても悔しいですね。

この半年間相当の労力を注ぎ込んできたので、終わったときはなんともいえない虚脱感でした。部活の引退試合ってこんな感じなのかな、などと思いました。

謝辞

最後になりましたが、プロセッサ・コンパイラ実験担当の先生方、TAの方々、そして何より４班の班員に感謝を申し上げたいと思います。ありがとうございました。

*1:なお今年は担当の先生により「FPU係の単位要件にキャッシュメモリの作成が追加」「シミュレータ係の単位要件に実行時間予測が追加」というコンテンツが追加されました

*2:MLのサブセット

*3:今年は各回「個人課題」に加え「グループ課題の提出」が単位要件でした。グループ課題は先生の意図としては分担してやってほしかったようですが、うちの班ではコンパイラ係が全てやってしまいました……。その分他の係は自分のすべきことに集中するということで…

*4:ざっくりいうとオブジェクトと光源とカメラの位置から３D画像を生成すること

*5:たとえば add f1, f1, f2 みたいなコードが生成されていると、「レジスタの指定が間違っています！」というエラーを出してくれていました。この機能も本当にありがたかった…

*6:まあ配列への書き込みという副作用は実際あるんですが、共通部分式削除に関しては、一度fを呼んだあとは、違う値をarrに書き込むまではfは副作用がないとみなせます

*7:この時期に睡眠習慣が崩壊してしまい進捗を生めなかったのもあるのですが…

*8:MinCamlデフォルトではすべてcaller saveなので、うまいことやれば改善できる余地はあります。ちなみにグローバルレジスタ割り当てを導入するとこの問題が消えます。

*9:命令が逆順にスケジューリングされていたのを修正したり、依存グラフにおいてRAW依存以外のときはレイテンシ（≒優先度）を加算しないようにしたり。本当によくあのスパゲティコードを読んでくれたなということで感謝しかないです

再帰関数をwhileループに変換する

動機

GLSLで

vec3 shade(...){
  if(material == glass){
    R * shade(reflection) + (1-R) * shade(refraction);
   }
}

みたいなシェーダを書こうとして、「あれ、GLSLで再帰関数って書けないの……？」となり、whileで書く方法を調べていたところ、上のような関数呼び出しの後でいろいろ処理して値を返すような一般の関数に直接応用できる手法をなかなか見つけられず、さらにいろいろ調べたところ、コールスタックっぽいことをするとうまくいくようなので、書いてみようと思いました。

コールスタック及び呼び出し規約周りの知識があるとより分かりやすいかもしれません。

この投稿（英語）がかなりわかりやすいですが、本稿では複数の再帰を持つ、より一般的な例を扱っています。

前処理

①変換元

似たようなプログラムをpythonで書きました。

def f(x):
    if x == 0:
        return 1
    elif x == 1:
        return 2 * f(x-1) + f(-(x-1))
    else:
        return 2 * f(x+1) * f(-(x-1))

②まずreturn hoge を ans = hoge; return ans にします。

def f(x):
    if x == 0:
        ans = 1
        return ans
    elif x == 1:
        ans = 2 * f(x-1) + f(-(x-1))
        return ans
    else:
        ans = 2 * f(x+1) * f(-(x-1))
        return ans

③次に関数呼び出し部を独立させます。 （コンパイラの中間表現を知っている方は ret = Call(f, x) をイメージするとわかりやすいかもしれません）

def f(x):
    if x == 0:
        ans = 1
        return ans
    elif x > 0:
        ret1 = f(x-1)
        ans = 2 * ret1
        ret2 = f(-(x-1))
        ans += ret2
        return ans
    else:
        ret1 =  f(x+1)
        ans = 2 * ret1
        ret2 = f(-(x+1))
        ans += ret2
        return ans

④エントリーポイントにラベルL0を、それ以降の関数呼び出し地点の直後に順にL1, L2, ...をつけます：

def f(x):
    #L0
    if x == 0:
        ans = 1
        return ans
    elif x > 0:
        ret1 = f(x-1)
        #L1
        ans = 2 * ret1
        ret2 = f(-(x-1))
        #L2
        ans += ret2
        return ans
    else:
        ret1 =  f(x+1)
        #L3
        ans = 2 * ret1
        ret2 = f(-(x+1))
        #L4
        ans += ret2
        return ans

⑤これをgoto文に書き換えて、基本ブロックを独立させます：

def f(x):
#L0
    if x == 0:
        ans = 1
        return ans
    elif x > 0:
        ret1 = f(x-1)
        goto L1
    else:
        ret1 =  f(x+1)
        goto L2
#L1
        ans = 2 * ret1
        ret2 = f(-(x-1))
        goto L2
#L2
        ans += ret2
        return ans
#L3
        ans = 2 * ret1
        ret2 = f(-(x+1))
#L4
        ans += ret2
        return ans

⑥gotoをwhileに書き換えます。returnはまだそのままにします。 pc という、「現在プログラム中のどの部分を処理しているか」の状態を表す変数で管理しています。

def f(x):
    pc = 0    # program counter
    while(True):
        if(pc == 0):
        #L0
            if x == 0:
                ans = 1
                return ans
            elif x > 0:
                ret1 = f(x-1)
                pc = 1
            else:
                ret1 =  f(x+1)
                pc = 1
        elif (pc == 1):
        #L1
                ans = 2 * ret1
                ret2 = f(-(x-1))
                pc = 2
        elif (pc == 2):
        #L2
                ans += ret2
                return ans
        elif (pc == 3):
        #L3
                ans = 2 * ret1
                ret2 = f(-(x+1))
                pc = 4
        else:
        #L4
                ans += ret2
                return ans

メイン処理

ここからが本番です。return とは「元の関数呼び出し文脈へのreturn」ですが、どうやってreturnするんやという問題を解決しなければなりません。 これを、コールスタック的な概念を導入することで解決します。アセンブリというかCPUの処理を模倣するようなイメージです。

ざっくりいうと、

• 前の関数呼び出しの結果を格納する変数retを用意する。
• 関数呼び出しのときは
  • スタックに、次に飛びたいラベルの番号、及び現在の（生きている）変数の値たちを積む。
    • 設計上は「どこかの関数呼び出し地点の前後で生きていうる変数すべて」としたほうがシンプルなので、その方針にします。
  • そのうえで関数引数をセットして、
  • pcを0にする（＋while文の先頭に戻る）ことで「関数呼び出し」が成立する。
• returnは
  • retに返したい値を代入する。
  • スタックがあるなら、
    • 呼び出し元で飛びたいと思っていたラベルの番号、及び呼び出し元での変数の値をスタックから取り出す。
    • pc及び変数の値をセットすることで、元の「関数呼び出し文脈」に帰れる。
  • スタックがないなら、return retすることで、"大元の関数fの値を返す"ようにする。

初めに「生きていうる変数」の一覧を作ります。④を見ると、xに加えansも生きている変数になりうることがわかります。

まずL0の関数呼び出しret1 = f(x-1); pc = 1を変換します。上の手順に従うと、

stack.append([1, x, ans])
x = x - 1
pc = 0

次にL2のans += ret2; return ansを変換します：

ans += ret
ret = ans
if len(stack) == 0:
    return ans
else:
    pc, x, ans = stack.pop()

同様に変換すれば、次のような⑦最終形が得られます：

def g(x):
    ans = 0        # temporary variable 
    ret = 0         # return value
    pc = 0         # program counter
    
    stack = []
    stack.append([pc, x, ans])
    while(True):
        if(pc == 0):
            if(x == 0):
                ret = 1
                if len(stack) == 0:
                    return ret
                else:
                    pc, x, ans = stack.pop()
            elif(x > 0):
                stack.append([1, x, ans])
                x = x - 1
                pc = 0
            else:
                stack.append([3, x, ans])
                x = x + 1
                pc = 0
        elif pc == 1:
            ans = 2 * ret
            stack.append([2, x, ans])
            x = -(x - 1)
            pc = 0
        elif pc == 2:
            ans += ret
            ret = ans
            if len(stack) == 0:
                return ret
            else:
                pc, x, ans = stack.pop()
        elif pc == 3:
            ans = 2 * ret
            stack.append([4, x, ans])
            x = -(x + 1)
            pc = 0
        elif pc == 4:
            ans += ret
            ret = ans
            if len(stack) == 0:
                return ret
            else:
                pc, x, ans = stack.pop()

ひょっとすると、①→③→④→⑦くらいに飛ばすほうがわかりやすいかもしれません。

これを使うと相互再帰も同様の手順で書けると思われます。

自動変換するプログラムとか書けそう。

余談

なお、もう少し厳密に「呼び出し規約」を書き下すと、次のようになります：

• 「スタック」を用意する。プログラム中ではリストで実装している。
• 「レジスタ」をいくつか用意する。これはプログラム中では変数である。
  • 「プログラムカウンタ」用のレジスタpcに加え、
  • 「返り値」の格納用レジスタ ret（RISC-Vでいうa0）
  • 「引数」の格納用レジスタx（RISC-Vでいう a1, a2, ...。RISC-Vだとa0と共用だが混乱を避けるため別にしておく）
  • 「関数呼び出し時に生きている変数」を保持しておくための汎用レジスタx, ans（t0, t1, ...）
• 「関数呼び出し」（ret1 = f(x-1)等）の手順は次の通り。
  • 「リターンアドレス」と「今生きている変数」x, ans を「スタック」に積んでおく。
    • 「リターンアドレス」は、次に向かうべきラベルになる。
  • 「引数」を引数格納用レジスタxに入れる。
  • 「呼び出し」を行うため「プログラムカウンタ」を関数の先頭にセットする。
• 値を返す（returnのとき）ときは、
  • ret に値を格納する
  • スタックから生きている変数の値x, ansを回収し現状復帰する
    • レジスタ割り当てが面倒なので全部の呼び出し地点での生きている変数を全部保持しておくことにする
    • saveはcallerだがrestoreはcallee
    • スタックがない場合は"もともとの関数fが値を返す"場合に相当するためreturn retする。
  • スタックから回収したプログラムカウンタの値をpcレジスタにセットして呼び出し元文脈に戻る。

なので、本当は関数呼び出しの時点で、引数レジスタにあるxの値をcallee saveな汎用レジスタに移しておかなければならないのだろうけれど、それをすると余計ややこしくなりそう…

Schemeの式をEmacsで簡単に実行する

この記事は、ISer Advent Calendar 2021の21日目の記事です。前日の記事はfushiguさんによる「噂のCPU実験」でした。翌日の記事は81uemanさんによる「ノルムで遊ぼ」です。

この記事では、SchemeやOCamlの式を簡単に実行するためのEmacsの設定を書き残しておきます。なお、SchemeやOCamlを書くことになったのは、学科の実験（プログラミング課題）のためなので、そのことが前提となっています。

なぜEmacsか

VS Codeで書いてもいいんですが、２Aの実験のサイト*1で、Emacsを使うための設定が書かれているため、とりあえずEmacsを使うか～となりました。

使ってみると、いろいろカスタマイズができることがわかりました。こんな感じで、キーボードショートカット一つで、１画面で結果が表示されるようにできました。

Scheme on Scheme*2までたどり着けたのも、これがあったからかもしれません。

特に、Schemeの課題の大部分やOCaml課題*3の前半は「フィボナッチ数列の第n項を求める関数fibを定義せよ。」のような小さな関数一発であることが多いので、毎回コンパイルするよりも、ショートカット一発でできるこちらのほうが楽でした。*4

この手法の限界

ただし、Scheme on Schemeのように、大量の関数を定義するような大きいファイルは、毎回実行のショートカットを連打するよりも、素直にターミナルでコンパイルしたほうが早いかもしれません*5。そのうえ、Emacs上のScheme処理系は重いので、guileだと動くはずのScheme on Scheme on Schemeが動かなくなった気がします。

それに、VS Codeのほうが大量のファイルを管理するのは楽なので*6、それが求められる場面（OCaml課題の後半のOCaml処理系作成、など）ではVS Codeのほうがいいかもしれません。（僕は3SまではEmacs + ターミナル + Makefileで頑張りましたが、3Aのコンパイラ実験でVS Codeを使い始めました。）

環境

Win10に乗っているWSL1です。 このサイトとかが参考になると思います。 GUI（X Server）を動かすのに苦労した記憶があるんですが、なぜだか具体的な手順を覚えていないです。~/.bashrcに

export DISPLAY=:0.0
export PATH=~/anaconda3/bin:$PATH

という文言があることだけは確かです。

前提知識

Emacs教習所にお世話になりました。ここのinit.elの設定は、undo-treeと見た目の変更、multi-term以外はやりました。（undo-treeは入れたかったんですが、なぜか激重になったので諦めました……） また、実験のサイトの設定も追加しました。

本題

ただ、実験のサイトの設定だけだと、ターミナルがEmacsの画面上で開くのみです。

そこからさらに一歩進めて、「今開いている.scmファイルの、カーソルの位置の式 *7 を、キー操作一つで開いたターミナルに打ち込める」ことができれば便利です。発想としては、C-c C-eで使える(eval-last-sexp)に近いですが、もっと便利です。

挙動をもう少し詳しく説明しておくと、

• C-c C-j で、現在のカーソルの位置の式を処理系に打ち込む。
• このとき、現在Scheme処理系が立ち上がっていないならば、自動的に開く。*8
• このとき、現在Scheme処理系が立ち上がっているもののそのウィンドウが開かれていないならば、そのウィンドウを自動的に開く。

みたいな処理をします。

それを実現するために、init.elに次のようなコードを書きました。*9

かなりガバガバなコードな気がします。怒らないでください。

(defun my-execute-scheme ()
  (interactive)
  (if (string= mode-name "Scheme")
      (progn (run-scheme scheme-program-name)
             (end-of-buffer)
             (other-window -1)
             (scheme-send-last-sexp))
    )
  )

(add-hook 'scheme-mode-hook
          '(lambda ()
             (define-key scheme-mode-map (kbd "C-c C-j") 'my-execute-scheme)))


(defun my-execute-scheme-all ()
  (interactive)
  (if (string= mode-name "Scheme")
      (progn (run-scheme scheme-program-name)
             (end-of-buffer)
             (other-window -1)
             (scheme-load-file (buffer-file-name (current-buffer))))))
;;(global-set-key (kbd "C-c C-a") 'my-execute-scheme-all)
(add-hook 'scheme-mode-hook
          '(lambda ()
             (define-key scheme-mode-map (kbd "C-c C-a") 'my-execute-scheme-all)))

とりあえず、Emacsで適当に.scmファイルを開き、適当に任意の式を書いて、任意の式の後ろでC-c C-j *10してみると挙動がわかると思います。

解説

(interactive)

コマンドを書くためには、関数の最初にこれを入れることが必要らしいです。

  (if (string= mode-name "Scheme")

「もし現在のモード名が"Scheme"なら」。Scheme以外の言語でSchemeの処理系が開かれると困ります。*11

      (progn (run-scheme scheme-program-name)
             (end-of-buffer)
             (other-window -1)
             (scheme-send-last-sexp))

⓪現時点では、フォーカスは.scmファイルを編集しているウィンドウ（以下「編集ウィンドウ」）にあるはずである。

① (run-scheme)でschemeを起動する。このとき、(defadvice run-scheme ...)の影響で、最終的には「編集ウィンドウとguileが走っているウィンドウの二つがあり、後者にフォーカスがある」状態になる。*12

②よってこのバッファの最下部に飛んでから、

③編集ウィンドウに戻り、

④「カーソルの位置の式」をguileに送る。

すると評価結果が表示されます。

(add-hook 'scheme-mode-hook
          '(lambda ()
             (define-key scheme-mode-map (kbd "C-c C-j") 'my-execute-scheme)))

scheme-modeを起動するときに、"C-c C-j"を上述の関数に割り当てます。

my-execute-scheme-all　も似たようなことをやっています。

ちなみに、OCaml・Prolog ver は以下の通りです。やってることはだいたい同じです。

;; https://y0m0r.hateblo.jp/entry/20130524/1369405033　から4行

(defun my-execute-ocaml ()
  (interactive)
  (if (string= mode-name "Tuareg")
      (progn (tuareg-run-process-if-needed tuareg-interactive-program)
             (if (not (string= mode-name "Tuareg"))
                 (other-window -1))
             (tuareg-eval-phrase)
             )))
(add-hook 'tuareg-mode-hook
          '(lambda ()
             (define-key tuareg-mode-map (kbd "C-c C-j") 'my-execute-ocaml)))


(autoload 'prolog-mode "prolog" "Major mode for editing Prolog programs." t)
(add-to-list 'auto-mode-alist '("\\.pl\\'" . prolog-mode))

(defun my-prolog-consult-file ()
  (interactive)
  (if (string= mode-name "Prolog")
      (progn
        (run-prolog t)
        (prolog-consult-file)
        (other-window -1))))

(defun my-prolog-query-clause ()
  (interactive)
  (if (string= mode-name "Prolog")
      (let* ((send-string
              (progn (prolog-mark-clause)
                     (buffer-substring-no-properties (region-beginning) (region-end)))))

        (progn       
          (if (eq (get-process "prolog") nil)
              (my-prolog-consult-file))
          (run-prolog)
          (end-of-buffer)
          (insert send-string "\n"))
        )
      )
)

(add-hook 'prolog-mode-hook
          '(lambda ()
             (define-key prolog-mode-map (kbd "C-c C-j") 'my-prolog-query-clause)))
(add-hook 'prolog-mode-hook
          '(lambda ()
             (define-key prolog-mode-map (kbd "C-c C-k") 'my-prolog-consult-file)))

おまけ

init.elのその他の設定のうち、自分が書いた部分のみ載せておきます。Emacs教習所にいろいろ載っています（再掲）。

smartparens

これがあるとカッコが自動で補完されて、いい感じになります。

(leaf smartparens
  :require smartparens-config 
  :ensure t
  :custom ((smartparens-global-mode . t))
)

ウィンドウの大きさの初期値を変える

デフォルトだと10行くらいしかなく、縦に狭いので、こうすると広げられます。

(add-to-list 'initial-frame-alist '(height . 35))
(add-to-list 'default-frame-alist '(height . 35))

余談

• 一度init.elを書くと、init.elさえ移せば他の環境でも同じ環境が簡単に再現できるのがEmacsの魅力です。具体的には、私物のPCから学科PCの仮想環境への移行がスムーズでした。ここまでの設定をすればCのコードもそこそこ書きやすくなっているはずです。*13 2021年度以降は、ASMでリモートアクセスすることになるECCSの環境にも適応してくれると思います。*14
• 最終的にはいろいろ書いたので、単にコピペするだけじゃなくて、他の人の書いたinit.elを解読したりelispのドキュメントを読んだりEmacsでdescribe-variableしたりして、自分なりにelispによるinit.elの書き方を勉強することができました。
• elispは、Schemeと同じくLispの方言らしいです。なので、動かねえ～～～って言いながらelispのドキュメントを読んでる間、なんでLispの方言（Scheme）を学ぶためにLispの方言（elisp）を学んでるんだろう、という気持ちになりました。勉強になってよかったです。

*1:2021/12/21現在、「情報科学基礎実験」でググるとこのサイトが出てくるので、これは公開情報のはずです

*2:Schemeで、自分自身を読み込めるScheme処理系を書いてみよう！という、Schemeの課題の最終目標です。

*3:OCamlは3Sでやります

*4:Q. Code Runnerか何か入れればいいんじゃないですか？ A.それでもいいんですが、Windows上にguileを入れるにしてもCode Runnerと連携させるのがよくわからず、WSL上でやるにしてもVS CodeをWSLと連携させる方法が当時よくわかりませんでした…（3Aで学科の人に手伝ってもらいながらやっとできたので、今でもよくわかっていないです）

*5:いちおうC-c C-aで全実行できるようにはしていますが…

*6:VS Codeでは、常に画面上にファイル一覧が表示されていて、GUIでそれを並べ替えたり、クリックで編集するファイルを切り替えられたりするのが非常に便利です。Emacsでもそれを実現する方法はあるかもしれませんが…あと、Emacs、ウィンドウ名が全部emacs@DESKTOP-...なんですよね。これが致命的でした。

*7:関数型言語だと、C言語における int a = 1; のような命令も、すべて「式」と呼ばれます。例えば、Schemeだとこれと等価な式は (define a 1) となります。この式を処理系に打ち込むと、「aが1である」という定義を現在の処理系で行うことができます。

*8:なお、複数ウィンドウ開いていると、現在のウィンドウの次のウィンドウが勝手にScheme処理系に移ってしまうようです。

*9:この記事のコードの著作権は放棄しますが、使うときは自己責任でお使いください。

*10: jikkou のj。あと、C-c C-eだと両方左手で使いにくかったため。

*11: (add-hook 'scheme-mode-hook ...)してるから不要っちゃ不要ですが、一応の保険です。これを書いた当時 ;;(global-set-key (kbd "C-c C-j") 'my-execute-scheme) みたいなマネをしてた名残でもあります。

*12:編集ウィンドウのみでもすでにguileのウィンドウが開いていても、まだguileが走っていなくとももうguileが走っていてもOKです。このへんについては、Scheme-mode で C-h f run-scheme したら出てくるヘルプと (defadvice) を眺めてください。

*13:2Aでは自分のPCでコードを書くことになると思います。3Sからは学科PCが学科から配布されます。このinit.elは、2Aのとき、自分のPCのEmacsのために書いたものでしたが、それをそのまま、3Sにおいて学科PCのHyper-Vで動かすUbuntuに輸入しました。

*14:2020年度ではECCSのEmacsはver22とかだったと思います。そのせいでleafが使えず、whitespaceもautocompleteもsmartparensも読み込めなかったため、泣きながら手元のVS Codeで書いたアセンブリコードをコピペしていました。