号外　4ビットマイコンでアセンブラプログラミング

これまで 32ビット Intel x86 アーキテクチャのサンプルを元に、アセンブラプログラミングについて説明してきた本連載ですが、今回は少々趣向を変えて、4ビットマイコンという制約の中で、プログラミングに工夫を凝らしてみようと思います。

FXマイコンとは？

学研から発売されていた電子ブロックという製品をご存知でしょうか？

この電子ブロックのラインナップの中に、4ビットマイコンユニットがパッケージされているFXシリーズと呼ばれるものがあり、80ワード（1ワード＝4ビット ※1）分のプログラムを組むことができます（http://www.wizforest.com/OldGood/MiCom/にも詳しく書かれています⁠）⁠。

今回はこのFXシリーズの4ビットマイコン（以下「FXマイコン⁠」⁠）を稼動環境として使ってみようと思うのですが、当時のものを完動品で入手するのは勿論困難ですし、「⁠4ビットマイコンのプログラミングとはどんなものだろう？」ぐらいの軽い気持ちであれば、復刻版であったとしても現物を入手するのは少々大げさすぎます。

しかし、ありがたいことに、FXマイコンのシミュレータソフトを公開されている方がいらっしゃいました。

また、学研の『大人の科学マガジン』から、FXマイコンと同等機能のワンボードマイコンが付録として付属する4ビットマイコン特集号（Vol.24）が2009年6月30日付けで刊行されていますので、こちらを入手されても良いでしょう。

シミュレータソフトを使用した場合:

持ち運びの手間がない
プログラム保存／呼び出しが可能
実行中のレジスタ／メモリ内容を確認可能

といった利便性が得られますが、『⁠大人の科学マガジン』の付録マイコンも、TK-80に通じる剥き身のフォルムにノスタルジックな魅力があって、なかなか捨て難いものがあります。

FX マイコン向けアセンブラ

4ビットという非常に制約の厳しいアーキテクチャですので、FXマイコンの命令体系は非常に独特です。

文献やウェブ上の紹介記事等では、この独特な体系の命令をそのまま使用していますが、個人的な印象としては、あまりにも命令体系／名前が独特すぎて、ロジックを考えるよりも、命令表をいちいち調べる方に労力が割かれるように思われます。

そこで、本連載で採用している AT&T ニーモニックっぽい記述のソースから、FXマイコン用のマシン語コードを生成するアセンブラ[2]を用意しました。

http://bitbucket.org/foozy/gmc4-tools/wiki/Home

以下の方法で、ツール一式をダウンロードしてください。

上記URLのページを表示
ページ中から“⁠Download⁠”タブを選択
“Tags & snapshots⁠”の“⁠tip⁠”[3]から、アーカイブファイルの形式（zip/gz/bz2）を選択してクリック
ブラウザの指示に従い、ファイルに保存
ダウンロードしたアーカイブを展開

なお、上記のFXマイコン用アセンブラはPythonで実装されているため、実行にはPython処理系が必要ですからご注意ください。

アーカイブ展開先に格納されているgmc4as.pyがアセンブラを実装しているPythonソースです。アセンブルしたいプログラムがsource.sに記述されている場合、以下の要領で実行してください。

図1　FXマイコン用アセンブラの実行

$ python gmc4as.py source.s
00 A | TIY    |  1|    movw    $0x0E, %y
01 E | E      |   |
02 5 | MA     |  2|    movw    (%y), %a
03 3 | CY     |  3|    swap
 | |     |      |   |
 | |     |      |   +---- オリジナルソースの内容
 | |     |      +-------- オリジナルソースでの行番号
 | |     +--------------- 固有ニーモニックでの表記
 | +--------------------- 16進プログラムデータ
 +----------------------- 16進アドレス

ソースコード中に文法上の問題がなければ、上記のような形式でアセンブル結果が表示されますので、「⁠16進アドレス」に対応する「16進プログラムデータ」を FXマイコンに入力してください。

gmc4as.pyが解釈可能なニーモニック等に関しては、アーカイブ中に含まれるドキュメントを参照してください。以下の記述では文法やニーモニックに関しては特に触れません。

ちなみに「FXマイコン独特の命令体系の方が良い」という方は、FXマイコン固有ニーモニックを用いるアセンブラを公開されている方がいますので、こちらを使用するのが良いでしょう（ただし、ネットワーク経由での使用が前提です⁠）⁠。

実装対象の仕様決め

今回は FX マイコンを使用して、第3回でも取り上げた多倍長演算処理を実装してみようと思います。

FXマイコン添付のサンプルプログラムや、『大人の科学マガジン』のマイコン特集号に掲載されているサンプルに比べると、なんだか地味な感じがするかもしれませんが、限られた資源／機能を如何に遣り繰りするか、というアセンブラの醍醐味に溢れる題材と言えます。

とりあえず、演算は「加算」限定で、ソース（source）データをデスティネーション（destination）データに加算した結果を、デスティネーション領域に上書きする処理を、7ワード分の多倍長データに対して行う仕様とします。多倍長データはそれぞれ:

デスティネーションデータ領域: 0x50 ～ 0x56
ソースデータ領域: 0x57 ～ 0x5D

上記の各7ワードの領域に、MSB First（上位桁をアドレス低位に配置）で行うものとします。

なお、デスティネーション領域は加算結果によって上書きされますので、処理そのものは不可逆なものとなります。

繰り上がりに配慮した加算処理

まずは、多倍長加算処理に必要な、「⁠1桁分の繰り上がり配慮付き加算処理」を実装します。

変数領域の定義

N桁の多倍長加算処理の骨子をC言語風に記述するならば、以下のようになります。

リスト1　加算処理の基本

    carry = 0;
    for(i = N - 1 ; 0 <= i ; i -= 1){
        dst[i] += src[i] + carry;
        carry = 上記演算での繰り上がりの有無;
    }

C言語では演算でのキャリー発生を検出できないため、carry変数の更新に関しては日本語での記述です。また、加算対象データの格納は、前述したようにMSB First仕様です。

先のメモリ配置で srcおよびdst 領域は確定していますので、他に必要な一時変数領域としては、ループ制御のためのi、および下位桁での繰り上がりの有無を保持するcarryがあります。

これらに相当する値として:

領域src参照用アドレス:: src + iに相当する値を0x5E番地に格納します。初期値は、srcの最下位桁を指す0x0Dです。また、1桁分の処理の開始時点では、yレジスタにも同じ値が格納されているものとします。
繰り上がりの有無:: 1桁分の処理の開始時点では下位桁での繰り上がりの有無、処理完了時点では現行桁での繰り上がりの有無を、0x5F番地に格納します。初期値は 0 です。

愚直な実装

まずは、愚直に「1桁分の繰り上がり配慮付き加算処理」を実装してみます。

リスト2　愚直な実装

    movw    (%y), %a    # src データの読み込み
    addw    $9, %y      # dst の同桁位置に移動
                        # 9 = 16 - 7 なので、y -= 7 と等価
    addw    (%y), %a    # src と dst の同桁を加算
    jsf     carry

    # 現行桁同士の演算による繰り上がり無し
    movw    %a, (%y)    # dst 位置に現時点の演算結果の保存

    movw    $0x0F, %y
    movw    (%y), %a
    neqw    $1, %a      # 下位桁での繰り上がり判定
    jsf     loop_check  # 下位桁からの繰り上がり無しなら
                        # ループ終了の判定処理へ

    movw    $0x0E, %y
    movw    (%y), %a    # a に src 位置を取り出し
    swap                # y に src 位置を復旧
    addw    $9, %y      # dst の同桁位置に移動

    movw    (%y), %a    # dst 位置から演算結果の復旧
    addw    $1, %a      # 下位桁の繰り上がり分を加算
    jsf     store_carry # 加算による繰り上がり有り

    # 繰り上がり無し
    movw    %a, (%y)    # dst 位置に演算結果の保存
    jmp     loop_check

    # 現行桁同士の演算による繰り上がり有り
carry:
    movw    %a, (%y)    # dst 位置に現時点の演算結果の保存

    movw    $0x0F, %y
    movw    (%y), %a
    neqw    $1, %a      # 下位桁での繰り上がり判定
    jsf     set_carry   # 下位桁からの繰り上がり無し

    movw    $0x0E, %y
    movw    (%y), %a    # a に src 位置を取り出し
    swap                # y に src 位置を復旧
    addw    $9, %y      # dst の同桁位置に移動

    movw    (%y), %a    # dst 位置から演算結果の復旧
    addw    $1, %a      # 下位桁の繰り上がり分を加算
                        # ここでは絶対に繰り上がりが発生しない!

    # 演算結果の保存と、繰り上がり「有り」の設定
store_carry:
    movw    %a, (%y)    # dst 位置に演算結果の保存
set_carry:
    movw    $1, %a
    movw    $0x0F, %y
    movw    %a, (%y)    # 現行桁での繰り上がりを「有り」に設定

    # ループ終了の判定処理
loop_check:

うんざりするほど長くなってしまいました。

これだけ長いプログラムになると、アセンブル結果を入力するのも面倒なら、入力結果の確認も面倒です[4]⁠。上手く動かなかった時に原因特定するぐらいなら、いっそゼロから書き直したい気分になりかねません。

単に長いだけでなく、似たようなコードが複数箇所で記述されていますので、明らかに無駄なのですが:

繰り上がり有無の保持領域（メモリ上の0x5E）が、一時的に「現行桁」と「下位桁」で共有されている
繰り上がり判定の際にa/yレジスタ内容が共に破壊されるため、「⁠演算結果の一時保存」と「データ位置の復旧」が必要

という事情から、愚直に実装するとどうしても長くなってしまいます。

代替レジスタの使用

先述したような長い実装になってしまうのは、FXマイコンのアーキテクチャに、一時情報保持に使用できる余分なレジスタが無いことに原因があります。

しかし、幸いなことに FX マイコンのアーキテクチャには、a/yレジスタの値を破壊せずに使用することができる、代替レジスタとでも言うべきレジスタが備わっており、FXマイコンのニーモニックで言えばCH、本稿で使用しているアセンブラのニーモニックで言えばflip命令を使用することで、a/yレジスタと代替レジスタ b/z を入れ替えることができます。

flip命令は、実行のつどa/yレジスタと代替レジスタb/zを入れ替えますので、偶数回の命令実施により、入れ替え状態は元に戻ることになります。

それでは、「⁠下位桁」および「現行桁」での繰り上がりをそれぞれbおよびzレジスタで保持するものとした場合の実装を見てみましょう。

リスト3　代替レジスタの使用

    movw    (%y), %a    # src データの読み込み
    addw    $9, %y      # dst の同桁位置に移動
    addw    (%y), %a    # src と dst の同桁を加算
    jsf     carry1

    # 現行桁同士の演算による繰り上がり無し
    flip
check_lower:
    neqw    $0, %b      # 下位桁での繰り上がり判定
    jsf     lower_carry

    # 「下位桁での繰り上がり無し」ないし「結果保存」
finishX:
    flip
finish:
    movw    %a, (%y)    # dst 位置に演算結果の保存
    jmp     loop_check  # ループ終了の判定処理へ

    # 下位桁での繰り上がり有り
lower_carry:
    flip
    addw    $1, %a      # 下位桁の繰り上がり分を加算
    jsf     carry2

    # 現行桁での繰り上がり無し
    jmp     finish

    # 下位桁での繰り上がりによる、現行桁での繰り上がり
carry2:
    flip
    movw    $1, %z      # 現行桁での繰り上がりを「有り」に設定
    jmp     finishX     # 演算結果の保存へ

    # 現行桁同士の加算による繰り上がり
carry1:
    flip
    movw    $1, %z      # 現行桁での繰り上がりを「有り」に設定
    jmp     check_lower # 下位桁での繰り上がり判定を実施

    # ループ終了の判定処理
loop_check:

「下位桁」と「現行桁」での繰り上がりの有無が分離された（それぞれb/zレジスタが保持）ことと、繰り上がりに関する処理のつど実施していたa/yレジスタの退避／復旧がflip 命令で簡略化できたことから、随分コード量が減りました。

後は、「⁠1桁分の繰り上がり配慮付き加算処理」実施のつど下記の処理を実施することで、次の桁での演算でも、適切に下位桁＝直前の「現行桁」での繰り上がりを考慮することができます。

リスト4　繰り上がりの初期化処理

    flip
    swap                # b/z の入れ替え
    movw    $0, %z      # 現行桁での繰り上がりを「無し」に初期化
    flip

計算量を無視した実装

代替レジスタを退避領域に使用することで、最初に示した実装と比較すれば、ずいぶんコード量を低減させることができました。

しかし:

下位桁での繰り上がりの有無を保持しておく

という、通常の多倍長演算の実装で用いられる発想では、これ以上のコード量低減は望めそうにありません。そこで:

現行桁の演算で繰り上がりが発生したならば、繰り上がりが発生しなくなるまで、上位桁への反映を済ませてしまう

という風に発想を転換してみましょう。

リスト5　先に上位桁に繰り上がりを反映

    movw    (%y), %a    # src データの読み込み
    addw    $9, %y      # dst の同桁位置に移動
    addw    (%y), %a    # src と dst の同桁を加算
    jsf     carry

    # 「繰り上がり無し」ないし「結果保存」
finish:
    movw    %a, (%y)    # 演算結果の保存
    jmp     loop_check  # ループ終了の判定処理へ

    # 繰り上がり発生
carry:
    movw    %a, (%y)    # 演算結果の保存

    addw    $0x0F, %y   # 15 = 16 - 1 なので、y -= 1 と等価
    movw    $1, %a
    addw    (%y), %a    # 上位桁に繰り上がり分の 1 を加算
    jsf     carry

    # 上位桁への繰り上がり無し
    jmp     finish

    # ループ終了の判定処理
loop_check:

圧倒的にコード量を低減できました！

但し、このアルゴリズムでは、N桁の処理を実施する際の計算量がO（N）ではなくO（N²）になってしまいます。

特別な制約条件のない通常の開発において、このような実装をした場合、ソースコードレビューの席は針のムシロになること確実です。

あくまで、実行性能よりもプログラム領域の最小化が優先、といった制約条件を前提とした実装の一例と考えてください。

ちなみに、筆者が最初にFXマイコンに触れた際に、10進補正付きの多倍長加減算命令（"CAL DEM+" や "CAL DEM-"）の:

繰り上がりが続く限り、メモリ上のデータに対する繰り上がり分の更新処理を繰り返す

という仕様が、際立って高機能に思えたのですが、実際に多倍長演算処理の最適化を考えてみると、このような実装にしておいた方が有用性が高い、という判断が働いたのだということがわかります。

多倍長加算処理の実装

「1桁分の繰り上がり配慮付き加算処理」ができましたので、いよいよ多倍長加算処理を組み上げてみましょう。

リスト6　多倍長加算処理

    movw    $0x0D, %a   # データ位置の初期値
    movw    $0x0E, %y

    # ループ初回は終了判定を省略可能
do_add:
    movw    %a, (%y)    # データ位置の退避
    swap                # y に src 位置を復旧

add_x:   # 現行桁に対する加算の開始
    movw    (%y), %a    # src データの読み込み
    addw    $9, %y      # dst の同桁位置に移動
    addw    (%y), %a    # src と dst の同桁を加算
    jsf     carry

    # 「繰り上がり無し」ないし「結果保存」
finish:
    movw    %a, (%y)    # 演算結果の保存
    jmp     loop_check  # ループ終了の判定処理へ

    # 繰り上がり発生
carry:
    movw    %a, (%y)    # 演算結果の保存

    addw    $0x0F, %y   # 15 = 16 - 1 なので、y -= 1 と等価
    movw    $1, %a
    addw    (%y), %a    # 上位桁に繰り上がり分の 1 を加算
    jsf     carry

    # 上位桁への繰り上がり無し
    jmp     finish

    # ループ終了の判定処理
loop_check:
    movw    $0x0E, %y
    movw    (%y), %a      # データ位置の復旧
    addw    $0x0F, %a     # 次のデータ位置(上位桁)の算出
    neqw    $0x06, %a     # データ位置下限との比較
    jsf     do_add        # 処理を継続

    - 終了 -

"add_x"から"loop_check" にかけての処理は、「⁠1桁分の繰り上がり配慮付き加算処理」そのものですし、それ以外の部分は分量も処理内容も単純ですので、特に説明は不要でしょう。

上記のプログラムでおおよそ40ワードほどですから、残りのプログラム領域を使用して、演算結果の各桁を7セグメントLEDで順次表示する、といった処理を付け加えてみてもおもしろいのではないでしょうか。