IchigoJam では、キャラクターパターンやマシン語のプログラムなど、バイナリデータをプログラムに埋め込みたいことがある。
そんなとき、データを十進数や十六進数で記述すると、1バイトを表すのに2～4バイト程度使うことになり、効率が悪い。
そこで、本記事では、Base64 を応用し、より効率よくバイナリデータを埋め込む方法を提案する。
※IchigoJamはjig.jpの登録商標です。
サンプルデータ
今回は、美咲フォント (美咲ゴシック) で「大石泉すき」を表現した以下のデータを埋め込む。
00000000 10 10 fe 10 10 28 c6 00 fe 20 20 7c a4 24 3c 00 |.....(... |.$<.|
00000010 10 7c 44 7c da 54 b2 00 08 fe 18 28 18 08 10 00 |.|D|.T.....(....|
00000020 10 7c 08 7e 24 40 3c 00 |.|.~$@<.|
このデータをキャラクターパターン領域 (#700) の先頭から書き込んで「大石泉すき」を出力するプログラムで、容量を比較する。
プログラムの容量の測定方法
今回は、プログラムを「データ」「デコーダ」「文字列の出力」の3パートに分け、それぞれのバイト数を測定する。
測定は、それぞれの部分だけをプログラム領域に格納し、
?1024-FREE()
を実行することで行う。
すなわち、行番号などを含む内部表現でのバイト数を用いる。
この測定方法を用いる都合上、今回は「データ」「デコーダ」「文字列の出力」はそれぞれ別の行に書く。
実際のプログラムでは、1行にこれらを混ぜて書くことで、容量を削減できる可能性がある。
既存手法
POKE を用いて埋め込む
POKE 命令の引数として、埋め込むデータをそのまま書く。
このとき、データは1バイトずつ書くことになる。
十六進数を使うと # をつける分1バイトプログラムが長くなる上、0～255の範囲では高々1桁しか短くならないので、十六進数を用いるメリットは無い。
そのため、データは十進数で書く。
データの埋め込みの効率は悪いが、任意の場所にデータを書き込むことができ、デコーダが不要というメリットがある。
データの区切りの , を含め、1バイトを2～4バイトで表すことになる。
10 POKE#700,16,16,254,16,16,40,198,0,254,32,32,124,164,36,60,0,16,124,68,124,218,84,178,0,8,254,24,40,24,8,16,0,16,124,8,126,36,64,60,0
20 ?CHR$(#E0,#E1,#E2,#E3,#E4)
このプログラムの容量は、以下のようになった。
| 部分 | 容量 (バイト) |
|---|---|
| データ | 136 |
| デコーダ | 0 |
| 文字列の出力 | 30 |
| 合計 | 166 |
配列を用いて埋め込む
データを並べ、LET 命令で配列に代入する。
2バイトずつデータを記述できるので、1バイトずつ記述するより短くなることが期待できる。
-10000 以下の場合は、#D8F0 などの十六進数で表したほうが短くなるが、それ以外の場合は十進数で表したほうが十六進数で表す以下の文字数で表現できる。
その性質上、直接書き込めるのは配列領域のみであり、それ以外の領域に書き込む場合は COPY 命令などでコピーする必要がある。
データの区切りの , を含め、2バイトを2～6バイト (1バイトあたり1～3バイト) で表すことになる。
10 LET[0],4112,4350,10256,198,8446,31776,9380,60,31760,31812,21722,178,-504,10264,2072,16,31760,32264,16420,60
20 COPY#700,#800,40
30 ?CHR$(#E0,#E1,#E2,#E3,#E4)
このプログラムの容量は、以下のようになった。
| 部分 | 容量 (バイト) |
|---|---|
| データ | 112 |
| デコーダ | 20 |
| 文字列の出力 | 30 |
| 合計 | 162 |
提案手法：Base64の応用
Base64 では、バイト列を6ビットずつに分割し、6ビットの数値をそれぞれに対応する文字で表す。
そのため、3バイトを4バイト (1バイトあたり1.33バイト) で表すことができ、十六進数で表すより効率よくデータを埋め込むことができる。
ただし、Base64 をそのまま用いてしまうと、文字から対応する6ビットの数値を求める処理が複雑になり、デコーダのプログラムが長くなってしまう。
そこで、本来のBase64の文字のかわりに、文字コードの下位6ビットがそのまま埋め込むデータの6ビットになっている文字を用いる。
具体的には、文字コード #40～#6F および #30～#3F の文字を用いることで、IchogoJam の文字列としてそのまま簡単に埋め込める。
CyberChef の To Base64 では、エンコードに用いる文字のセットを自由に指定できるため、このエンコードも行うことができる。
From Hexdump, To Base64 - CyberChef
デコードは、以下のように行う。
- 文字を読み込む。それが文字列の終端
"であれば終了する - 読み込んだ文字に対応する6ビットを、バッファの下位に入れる
- 有効なデータが8ビット貯まったら、それを出力先に書き込む
たとえば以下のように実装できる。
データを読み込んだ部分しか参照しないので、B の初期化は不要である。
10 D="DAC>DA@h1`C>HBA<iBP<@AA<QG3ZUKH@BO8XJA`HD@@P_@a>ID@<@@"
20 P=#700:S=0
30 C=PEEK(D):IFC=34GOTO60
40 B=B<<6|C&63:S=S+6:IFS>7S=S-8:POKEP,B>>S:P=P+1
50 D=D+1:GOTO30
60 ?CHR$(#E0,#E1,#E2,#E3,#E4)
このプログラムの容量は、以下のようになった。
| 部分 | 容量 (バイト) |
|---|---|
| データ | 62 |
| デコーダ | 106 |
| 文字列の出力 | 30 |
| 合計 | 198 |
また、「P がとる値は 6・4・2・0 のみで、このうち 6 のときのみ8ビット揃っていない」という性質を利用すると、以下のように実装できる。
10 D="DAC>DA@h1`C>HBA<iBP<@AA<QG3ZUKH@BO8XJA`HD@@P_@a>ID@<@@"
20 P=#700:S=0
30 C=PEEK(D):IFC-34B=B<<6|C&63:S=(S+6)%8:POKEP,B>>S:P=P+1-S/6:D=D+1:CONT
40 ?CHR$(#E0,#E1,#E2,#E3,#E4)
このプログラムの容量は、以下のようになった。
| 部分 | 容量 (バイト) |
|---|---|
| データ | 62 |
| デコーダ | 88 |
| 文字列の出力 | 30 |
| 合計 | 180 |
データは既存手法の約半分と劇的に短くなったが、デコーダの容量がかさみ、合計の容量は既存手法より長くなってしまった。
考察
短いデータであれば、デコーダを使わない方式で埋め込んだことが全体のプログラムが短くなることが期待できる。
一方、長いデータであれば、多少長いデコーダを使っても効率良い方法で埋め込んだほうが全体のプログラムが短くなることが期待できる。
そこで、簡易的な計算式を用いて、どのくらいのデータで有利不利が逆転するかを予測してみた。
今回埋め込んだデータは 40 バイトであり、各方式で埋め込んだ際のデータ1バイトあたりのプログラムの容量は以下のようになる。
| 方式 | プログラムの容量 (バイト) | データ1バイトあたりの容量 (バイト) |
|---|---|---|
| POKE | 136 | 3.40 |
| 配列 | 112 | 2.80 |
| Base64の応用 | 62 | 1.55 |
したがって、デコーダの容量も合わせると、各方式で $x$ バイトのデータを埋め込む際のプログラムの容量は、だいたい以下の式で表せそうである。
ついでに、$x$ の最大値として、データ部分のプログラム容量が 200 バイトになる $x$ (小数点以下切り捨て) も示す。
| 方式 | 埋め込みに用いる容量 | $x$ の最大値 |
|---|---|---|
| POKE | $3.40 x$ | 58 |
| 配列 | $2.80 x + 20$ | 71 |
| Base64の応用 | $1.55 x + 88$ | 129 |
これらを図示すると、以下のようになる。
この見積もりにおいて、各方式が他の方式を追い越すのは、$x$ が以下の値のときである。(小数点以下切り上げ)
| 追い越す方式 | 追い越される方式 | データ容量 $x$ |
|---|---|---|
| 配列 | POKE | 34 |
| Base64の応用 | POKE | 48 |
| Base64の応用 | 配列 | 55 |
なお、今回行った見積もりは簡易的なものであり、あまり正確ではない。
たとえば、行番号・変数・命令の部分の容量は埋め込むデータの容量によらないはずであるが、今回の見積もりではデータ本体と同様に埋め込むデータの容量に比例するとして見積もっている。
さらに、今回は「データ部分のプログラム容量 200 バイト」という上限を設けたが、実際に考慮するべき上限は「行番号も文字列で表した1行の長さ 200 文字 (バイト)」である。
行の文字列表現とプログラム領域での表現は行番号などの表現が異なるため、実際の上限は異なる可能性が高い。
1行で収まらない長いデータを埋め込む場合は複数行で表現することになり、デコーダとの連携方法も変わってくることが考えられる。
さらに、Base64の応用におけるエンコード結果の長さはデータの中身によらないが、POKE や配列を用いた表現ではエンコード結果の長さがデータの中身に依存し、たとえば値 0 のバイトが多いと短くなる。
また、配列領域の偶数番地に書き込む場合は、配列方式で配列領域からコピーする操作を省略できる。
少しでもプログラムの容量を削りたい場合は、エンコードするデータの長さ・中身・書き込み先などにより、実験を行うなどして、適切なエンコード方式を選択するのがよいだろう。
まとめ
IchigoJam BASIC 向けに、Base64 を応用し、ASCII 文字の下位6ビットでデータの6ビットを表現することでプログラムにバイナリデータを埋め込む方式を提案した。
この方式を POKE 命令や配列を用いて埋め込む方法と比較し、おおむね 55 バイト以上のデータを埋め込むのであればこの方式のほうが短いプログラムで埋め込めそうだという見積もりを得た。
ただし、実際のプログラムの長さは埋め込むデータによって変わる可能性があり、見積もりもあまり正確ではないため、境界付近のデータ量であれば実際に実験を行って埋め込みに用いる方式を決めるのがよいだろう。