ASCII 印字可能文字縛りで IchigoJam のマシン語プログラムを書く

# IchigoJam におけるマシン語

[IchigoJam](https://ichigojam.net/)[^regtr] では、`USR` 関数を用いてマシン語のプログラムを呼び出すことができる。
ここでは、以下の命令セットを用いることができる。

[^regtr]: IchigoJamはjig.jpの登録商標です。

[Cortex-M0 Armマシン語表 （asm15表記、抜粋）](https://mikecat.github.io/asm15/armasm.html)

:::note info
IchigoJam **R** では命令セットが異なる。
この記事では、R がつかない IchigoJam を扱う。
:::

この `USR` 関数を使う際は、キャラクターパターンRAMなどに命令列を書き込み、書き込んだ命令列の先頭アドレスを `USR` 関数に渡して実行するのが基本となっている。

[はじめてのマシン語 - IchigoJamではじめるArmマシン語その1](https://fukuno.jig.jp/1184)

たとえば、`USR` 関数の第2引数がレジスタ `R0` に渡されるので、以下のコード (asm15)

```
R0 += 1
RET
```

を[アセンブル](https://mikecat.github.io/asm15/)し、書き込んで実行する。

```
10 POKE #700,#01,#30,#70,#47
20 PRINT USR(#700,42)
```

すると、`USR` 関数の第2引数として渡した値 `42` に1を足した

```
43
```

が出力される。

# ASCII 印字可能文字

[ASCII 印字可能文字](https://ja.wikipedia.org/wiki/ASCII#ASCII%E5%8D%B0%E5%AD%97%E5%8F%AF%E8%83%BD%E6%96%87%E5%AD%97) とは、文字コード 0x20 以上 0x7E 以下の文字である。
**文字コード 0x7F (DEL) は含まない。**

これらの文字は、多くの環境でキーボードから入力しやすく、文字列に埋め込みやすい。

# IchigoJam における文字列とマシン語

IchigoJam ([1.2系以降](https://fukuno.jig.jp/1266)) では、文字列はその文字列の先頭のアドレスとして評価される。
そのため、文字列を直接、もしくは変数に代入して `USR` 関数に渡すことで、文字列の内容をマシン語として実行できる。
実行するマシン語を ASCII 印字可能文字のみで表せるものにすることで、この方法を使いやすくすることができる。

:::note info
0x22 (`"`) は ASCII 印字可能文字に含まれるが、IchigoJam では文字列の終端を表すため文字列中には使用できない。
また、カナ文字 (0xA1 ～ 0xDF) も、ASCII 印字可能文字と同様に入力や文字列への埋め込みが容易である。
しかし、簡単のため、この記事ではこれらの条件は無視し、「ASCII 印字可能文字縛り」とする。
:::

たとえば、マシン語の `RET` 命令は `0x70 0x47` の 2 バイトで表され、これらの値は ASCII 印字可能文字の範囲に入っている。
`0x70 0x47` を文字列に変換すると `"pG"` なので、これを「何もせず第1引数の値をそのまま返すマシン語のプログラム」として実行できる。

```
10 PRINT USR("pG",42)
```

このプログラムを実行すると、`USR` 関数の第 2 引数に渡した値

```
42
```

が出力されるはずである。

:::note warn
マシン語のプログラムは、**偶数のアドレスから配置**しなければならない。
行番号なし (直接実行) の

```
PRINT USR("pG",42)
```

は、Segmentation Fault になってしまった。
以下のように空白を追加して文字列の位置を調整することで、実行できた。

```
PRINT  USR("pG",42)
```

:::

マシン語のプログラムを ASCII 印字可能文字のみで表して文字列として埋め込むことで、普段 (`POKE` コマンド) は 1 バイトを表すのに最大 4 バイト (区切りのカンマを含む) 使うのに対し、1 バイトを 1 バイトで表すことができるため、プログラム容量を削減できる可能性がある。

一方、ASCII 印字可能文字しか使わないとなると使うことができない命令やオペランドが出てくるため、プログラムを書くのが難しくなったり、プログラムが長くなったりする可能性がある。

# ASCII 印字可能文字で使える命令・使えない命令

具体的に、「ASCII 印字可能文字縛り」でどのような命令が使えるかをみていく。

## 使えるかどうかの判定方法

ある命令が使える (ASCII 印字可能文字で表現できる) かは、以下のようにして判定できる。
この判定法では、命令中の各バイトそれぞれの上位ニブル (15～12 ビット目、7～4 ビット目) を参照する。
ある命令中のすべてのバイトが「使える」と判定されれば、その命令は使える。
一方、「使えない」と判定されたバイトがあれば、その命令は使えない。

![命令が使えるかの判定チャート](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/516f955a-5b33-df3b-f42c-0f3540c15740.png)

1. 15 (7) ビット目が 1 の場合、使えない (0x80 ～ 0xff)
2. そうでなく、14 (6) ビット目が 1 の場合、0x7f 以外は使える (0x40 ～ 0x7f)
3. そうでなく、13 (5) ビット目が 1 の場合、使える (0x20 ～ 0x3f)
4. そうでない場合、使えない (0x00 ～ 0x1f)

## 使える命令の例

以下の命令は ASCII 印字可能文字で表現できる。

* 即値の代入 `Rd = u8`、加算 `Rd += u8`、減算 `Rd -= u8`、比較 `Rn - u8`
  * `u8` は ASCII 印字可能文字の範囲 (0x20 ～ 0x7e)
* 代入 `Rd = Rm`、加算 `Rd += Rm`、比較 `Rn - Rm`
  * `Rd` / `Rn` は R0 ～ R7
  * `Rm` は R4 ～ R15 (比較 `Rn - Rm` では、命令の制約で R8 ～ R15)
  * (Rd, Rm) = (R7, R15) は除く (0x7f になるため)
* 符号反転 `Rd = -Rm`、乗算 `Rd *= Rm`、XOR `Rd ^= Rm`、キャリー加算 `Rd += Rm + C`
  * (Rd, Rm) = (R7, R7) は除く (0x7f になるため)
* AND `Rd &= Rm`、OR `Rd |= Rm`、算術右シフト `ASR Rd, Rs`、ビットテスト `Rn & Rm`
  * `Rm` / `Rs` は R4 ～ R7
* メモリアクセス `Rd = [Rn + u5]` など
  * オペランドの組み合わせの制約あり
  * `Rd = [Rn + u5]W` および `[Rn + u5]W = Rd` は除く (15 ビット目が 1 であるため)
* 絶対ジャンプ `GOTO Rm`
  * `Rm` は R4 ～ R12 または R14 (R13・R15 は命令の制約で使えない)

## 使えない命令の例

以下の命令は、15 ビット目または 7 ビット目が 1であるため、ASCII 印字可能文字で表現できない。

* 実行位置取得 `Rd = PC + u8`
* 可変論理シフト `Rd <<= Rs`、`Rd >>= Rs`
* ビットNOT `Rd = ~Rm`
* 比較 `Rn - Rm`、`Rn + Rm`
  * `Rn` および `Rm` は R0 ～ R7
* 条件分岐 `IF 0 GOTO n8`、`IF !0 GOTO n8`、`IF cond GOTO n8`
* 相対ジャンプ `GOTO n11`
* 絶対コール `GOSUB Rm`
* 相対コール `GOSUB n22`
* スタック操作 `PUSH {regs}`、`POP {regs}` など
* バイト反転 `Rd = REV(Rm)`、`Rd = REV16(Rm)`、`Rd = REVSH(Rm)`
* ビットクリア `BIC Rd, Rm`
* 右ローテート `ROR Rd, Rs`
* ボロー減算 `Rd -= Rd + !C`
* マルチメモリアクセス `LDM Rn, {regs}`、`STM Rn, {regs}`
* 符号拡張 `Rd = SXTH(Rm)`、`Rd = SXTB(Rm)`
* ゼロ拡張 `Rd = UXTH(Rm)`、`Rd = UXTB(Rm)`
* システム `CPSID`、`CPSIE` など

:::note info
これらの命令の中には、カナ文字の使用も許可すれば使えるようになるものもある。
:::

以下の命令は、0x1f 以下のバイトがあるため、ASCII 印字可能文字で表現できない。

* 非破壊加減算 `Rd = Rn + u3`、`Rd = Rn - u3`、`Rd = Rn + Rm`、`Rd = Rn - Rm`
* 固定シフト `Rd = Rm << u5`、`Rd = Rm >> u5`、`Rd = ASR(Rm, u5)`
* フラグを破壊するだけ `NOP`

:::note info
これらの命令は、カナ文字の使用も許可しても使えない。
:::

# IchigoJam におけるマシン語の規約

プログラムを書く参考になるよう、IchigoJam におけるマシン語の規約をおさらいする。

## 引数と返り値

`USR` 関数によりマシン語の実行が開始される際、レジスタ `R0` ～ `R3` に以下の値が設定される。

|レジスタ|値|
|:-:|---|
|R0|`USR` 関数の引数 (32ビットに符号拡張される)|
|R1|RAMの基準アドレス ([1.1～](https://fukuno.jig.jp/1188))|
|R2|キャラクターROMの基準アドレス ([1.1～](https://fukuno.jig.jp/1188))|
|R3|割り算ルーチンのアドレス ([1.2.2～](https://fukuno.jig.jp/1771))|

また、`LR` (`R14`) に処理復帰用アドレスが設定される。
`RET` 命令などでこのアドレスに処理を移すことで、BASIC の処理に戻ることができる。
このとき `R0` レジスタに格納されている値が、`USR` 関数の戻り値となる。

## レジスタの使用方法

各レジスタの用途および保存の要否を以下に示す。
「保存」が「要」であるレジスタの値は、処理を終了して復帰する際、処理を開始した際の値と同じでなければならない。(すなわち、これらのレジスタを用いる場合は、事前に値を別の場所に保存しておき、処理が終了したら復帰する前に保存しておいた値を書き戻さなければならない)

|レジスタ|用途|保存|
|:-:|---|:-:|
|R0 ～ R3|汎用 / 引数と戻り値|不要|
|R4 ～ R7|汎用|**要**|
|R8 ～ R11|汎用 (一部の命令のみアクセス可能)|**要**|
|R12|汎用 (一部の命令のみアクセス可能)|不要|
|R13|スタックポインタ (SP)|**要**|
|R14|処理復帰先 (LR)|不要|
|R15|プログラムカウンタ (PC)|(不要)|

参考：

* [楽しさ広がるマルチバイトメモリアクセスとスタック - IchigoJamではじめるArmマシン語その5](https://fukuno.jig.jp/1479)
* [32ビットへの誘い](http://elm-chan.org/junk/32bit/report.html)

# ASCII 印字可能文字縛りでの基本的なパターン

ASCII 印字可能文字のみを使う場合、使える命令やオペランドが限られるため、基本的なパターンでも素直には実現できなくなることがある。
ここでは、いくつかのパターンの実現方法をみていく。

## 定数の加減算

足す値が ASCII 印字可能文字の範囲 (0x20 ～ 0x7e) の場合は、そのまま加算できる。

```
R0 += #40
```

足す値が ASCII 印字可能文字の範囲を下回る場合は、一旦大きい値を加算し、その後余計に加算した分を減算することで実現できる。

```
' R0 += 1
R0 += #41
R0 -= #40
```

足す値が ASCII 印字可能文字の範囲を上回る場合は、複数回に分けて加算することで実現できる。

```
' R0 += #C0
R0 += #50
R0 += #70
```

減算についても、上記の加算と減算を入れ替えればよい。

:::note warn
加減算を分割すると、結果のフラグは分割前から変わる可能性がある。
行いたい判定に応じて、「加算してから減算」のかわりに「減算してから加算」を行うなど、適切に実装を行うのがよいだろう。
:::

## レジスタの代入

レジスタ間の代入を行う `Rd = Rm` 命令は、ASCII 印字可能文字縛りでは `Rm` として `R4` 以降しか使用できない。
そのため、`R0` ～ `R3` から代入をしたい場合は別の方法をとることが求められる。

たとえば、符号反転を行い、もう一度符号反転を行うことで、もとの値が得られる。

```
' R0 = R1
R0 = -R1
R0 = -R0
```

XOR を用いて代入先のレジスタの値をゼロにし、そこに XOR を用いることでも代入ができる。

```
' R0 = R1
R0 ^= R0
R0 ^= R1
```

:::note warn
`Rd = Rm` 命令とは違って、これらの演算操作はフラグを変更する。
:::

## レジスタの加算

ASCII 印字可能文字縛りでレジスタ同士の加算を行える命令は、`Rd += Rm` および `Rd += Rm + C` である。
前者は、`Rm` として `R4` 以降しか使えない。
後者はキャリーフラグが加算されるので、単純な加算として用いるなら事前にキャリーフラグを 0 にしておく必要がある。

```
' R0 += R1
' R4 の値を保存する
R3 = -R4
' 加算する値を R4 に格納し、加算を行う
R4 = -R1
R4 = -R4
R0 += R4
' R4 の値を復元する
R4 = -R3
```

:::note warn
`R0 += R4` 命令はフラグを変更しないが、値の退避に用いた `R3 = -R4` などの命令はフラグを変更する。
:::

```
' R0 = R0 + R1
' キャリーフラグを 0 にする
R2 ^= R2
R2 += R2 + C
' 加算を行う
R0 += R1 + C
```

:::note info
`R0 = R0 + R1` も `R0 += R1 + C` も計算結果に応じてフラグを設定する。
したがって、このコードの実行結果は `R2` の値を破壊する点以外 `R0 = R0 + R1` と同様になる。
:::

## メモリアクセス

オペランドの制約はあるものの、汎用レジスタを基準とするメモリアクセスはそのまま表現できるパターンが多い。

```
' RAM の仮想アドレス R0 から値を読み出す
R0 = [R0 + R1]
```

しかし、スタックを使用するのは難しそうである。
スタック操作系の命令は 15 ビット目が 1 なので使えず、R8 ～ R15 に値を書き込む命令も 7 ビット目が 1 になってしまうので使えない。
そのため、スタックポインタを動かす方法が見つかっていない。
スタックポインタを動かさずに、スタックポインタより下位の部分に値を書き込んでも、割り込み処理により上書きされる可能性があり、危険である。

メモリを用いたい場合は、渡される RAM の基準アドレス `R1` の情報などを用い、スタックではなく固定の位置を作業用に用いるのがよいだろう。

:::note info
「ASCII 印字可能文字縛り」を緩めてカナ文字の使用を認めれば、`PUSH` や `POP` などのスタックを操作する命令も用いることができるようになる。
:::

## キャリーフラグの取得

ASCII 印字可能文字縛りでは条件分岐命令も PSR (Program Status Register) を読み出す命令も使えないため、フラグの取得には工夫が必要である。

キャリーフラグは、`Rd += Rm + C` 命令により取得できる。
これは加算命令なので、値を 0 か 1 で取得したい場合は、事前に取得先のレジスタの値をゼロに設定しておくとよいだろう。
レジスタの値をゼロに設定するには、XOR 演算 `Rd ^= Rm` が使える。
この XOR 演算はキャリーフラグを変更しないので、取得したいキャリーフラグを設定する命令の後で実行してもよい。

```
' この演算により設定されたキャリーフラグを取得したい
R0 += #40
' キャリーフラグの取得先 R1 をゼロに設定する
R1 ^= R1
' R1 にキャリーフラグの値を 0 か 1 で取得する
R1 += R1 + C
```

:::note info
キャリーフラグの値を 0 か 1 で取得することで、この値を掛け算することにより値を「0 にする」か「そのままにする」かを行うことができる。
これを用いると、ある値を足すかどうかの条件分岐として利用できる。
:::

## レジスタの値がゼロかどうかの判定

ASCII 印字可能文字縛りではゼロフラグを取得できなそうなので、他の方法を考える。

符号反転命令 `Rd = -Rm` を用いると、入力の値がゼロならばキャリーフラグが 1、非ゼロならばキャリーフラグが 0 になる。
このキャリーフラグを前述の方法で取得することで、レジスタの値がゼロかどうかを判定できる。

```
' R0 の値がゼロかを判定する
R1 = -R0
' キャリーフラグの取得先 R1 をゼロに設定する
R1 ^= R1
' R0 がゼロなら R1 は 1、R0 が非ゼロなら R1 は 0 になる
R1 += R1 + C
```

:::note info
符号反転 `Rd = -Rm` は、ゼロからの減算 `Rd = 0 - Rm` として処理される。
入力 `Rm` がゼロのときは、定数 `0` は(符号なしの)入力 `Rm` **以上**なので、キャリーフラグが 1 となる。
入力 `Rm` が非ゼロのときは、定数 `0` は(符号なしの)入力 `Rm` **未満**なので、キャリーフラグが 0 となる。
:::

## ジャンプ (分岐)

ASCII 印字可能文字縛りで使える分岐命令は、`GOTO Rm` のみである。(`RET` はこの命令の特殊なケースである)
これは、レジスタ `Rm` で指定したアドレスに実行を移す命令である。
ただし、レジスタ `Rm` の最下位ビット (LSB) は `1` にしておかなければならない。

:::note info
「ASCII 印字可能文字縛り」の制約を満たすためには、`Rm` は `R4` 以降でなければならない。
`R8` 以降の利用 (値の設定) は難しく、`R4` ～ `R7` は**値の保存が必要**なので、注意して利用すること。
:::

`Rd = Rm` 命令において、`Rm` として `R15` を指定することで、この命令のアドレス**に 4 を足した値** (この命令の 2 個次の命令のアドレス) を取得できる。
このアドレスの最下位ビットは `0` なので、`GOTO Rm` に渡す前に奇数を加減算するなどして最下位ビットを `1` にしなければならない。

```
' R4 のもとの値を保存する
R3 = -R4
' R4 にこの命令のアドレス + 4 を格納する
R4 = R15
' R4 に 7 を加え、合計で R4 = R15 の 5 命令先を指すようにする
R4 += #37
R4 -= #30
' ジャンプを実行する
GOTO R4
' この命令は実行されない
R0 = #20
' ジャンプ先：R4 の値を復元する
R4 = -R3
' 呼び出し元に復帰する
RET
```

:::note info
この処理は、ASCII 印字可能文字縛りが無ければ

```
GOTO @SKIP
R0 = #20
@SKIP
RET
```

と表せる。このプログラムを IchigoJam BASIC に埋め込むと、たとえば

```
10 POKE#700,0,224,32,32,112,71
```

や

```
10 LET[0],#E000,8224,#4770
```

となる。一方、先ほどのサンプルプログラムは

```
10 A="cB|F740< G  \BpG"
```

となり、命令数は多いにもかかわらず短く表せている。
:::

# ASCII 印字可能文字縛りのマシン語プログラム例

実際に、ASCII 印字可能文字縛りでいくつかのマシン語プログラムを書き、IchigoJam BASIC に埋め込んで実行してみた。

## 引数で与えられた値に 1 を足して返す

### アセンブリプログラム

```
R0 += #31
R0 -= #30
RET
```

### BASIC プログラム

```
10 P="1008pG"
20 PRINT USR(P, 42)
30 PRINT USR(P, -73)
```

### 実行結果

```
43
-72
```

## 1 から 引数で与えられた値までの整数の和を求める

### アセンブリプログラム

```
' ----- ループ初期化 -----
' R5 の値を保存する
R3 = -R5
' R1 に引数の -1 倍を格納する
R1 = -R0
' R0 の値を 0 に設定する
R0 ^= R0

' ----- ループ -----
' R5 に足す値を設定する
R5 = -R1
' 合計を更新する
R0 += R5
' R1 に 1 を足す
R1 += #31
R1 -= #30
' R1 が 0 になったかを判定する
R2 = -R1
R2 ^= R2
R2 += R2 + C
' キャリーフラグによって分岐する準備をする (1 → ループ終了)
R5 = #20
R5 *= R2
' ジャンプ先のアドレスを計算する
R2 = R15
R2 -= #46
R2 += #31
R2 += R5
' ジャンプを実行する
R5 = -R2
R5 = -R5
GOTO R5

' ----- ループ終了 -----
' R5 の値を復元する
R5 = -R3
' 復帰する
RET
```

:::note info
`R2 += R4` を表すマシン語は `#4422` であり、IchigoJam BASIC の文字列では使えない `"` が含まれてしまう。
レジスタ `R4` のかわりに `R5` を用いることで、これを回避した。
:::

### BASIC プログラム

```
10 P="kBAB@@MB(D1109JBR@RA %UCzFF:12*DUBmB(G]BpG"
20 PRINT USR(P, 5)
30 PRINT USR(P, 10)
40 PRINT USR(P, 100)
```

### 実行結果

```
15
55
5050
```

## 引数の 1 になっているビットを数える (popcnt)

### アセンブリプログラム

```
' ----- ループ初期化 -----
' R5 の値を保存する
R3 = -R5
' R1 に引数の値を格納する
R1 = -R0
R1 = -R1
' R0 の値を 0 に設定する
R0 ^= R0

' ----- ループ -----
' R1 の値をコピーし、右に31ビット算術シフトする
' これにより、最上位ビットが 1 であれば値は -1 に、0 であれば値は 0 になる
R5 = #4F
R5 -= #30
R2 = -R1
R2 = -R2
ASR R2, R5
' 求めた値を -1 倍し、R0 に加える
R5 = -R2
R0 += R5
' R1 を 2 倍 (1 ビット左シフト) する
R5 = -R1
R5 = -R5
R1 += R5
' R1 が 0 になったかを判定する
R2 = -R1
R2 ^= R2
R2 += R2 + C
' キャリーフラグによって分岐する準備をする (1 → ループ終了)
R5 = #2A
R5 *= R2
' ジャンプ先のアドレスを計算する
R2 = R15
R2 -= #21
R2 += R5
' ジャンプを実行する
R5 = -R2
R5 = -R5
GOTO R5

' ----- ループ終了 -----
' R5 の値を復元する
R5 = -R3
' 復帰する
RET
```

### BASIC プログラム

```
10 P="kBABIB@@O%0=JBRB*AUB(DMBmB)DJBR@RA*%UCzF!:*DUBmB(G]BpG"
20 FOR I=1 TO 10
30 Q=RND(32767)
40 PRINT BIN$(Q,15),USR(P,Q)
50 NEXT
```

### 実行結果例

```
111111110010011 11
010101101001110 8
000111000011010 6
010100001000011 5
010110111101010 9
101001011000101 7
011011010000011 7
110010010010111 8
001001100100101 6
010100010010010 5
```

# 結論

ASCII 印字可能文字のみで表現できるマシン語を用いることで、いくつかの処理を行うマシン語プログラムを文字列で表現し、実行することができた。
しかし、この制約では、値の保存が不要かつ多くの命令で使用できる 4 個のレジスタが

* 計算結果
* 計算の状態
* 作業用
* 値の保存が必要なレジスタの値の保存

で埋まってしまい、あまり複雑な処理を行うのは難しいだろう。
実用的なプログラムを書くためには、ASCII 印字可能文字だけでなくカナ文字も活用し、スタックを操作する命令なども使用していくのがよいだろう。