これまで 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進プログラムデータ」を 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
addw $9, %y
addw (%y), %a
jsf carry
movw %a, (%y)
movw $0x0F, %y
movw (%y), %a
neqw $1, %a
jsf loop_check
movw $0x0E, %y
movw (%y), %a
swap
addw $9, %y
movw (%y), %a
addw $1, %a
jsf store_carry
movw %a, (%y)
jmp loop_check
carry:
movw %a, (%y)
movw $0x0F, %y
movw (%y), %a
neqw $1, %a
jsf set_carry
movw $0x0E, %y
movw (%y), %a
swap
addw $9, %y
movw (%y), %a
addw $1, %a
store_carry:
movw %a, (%y)
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
addw $9, %y
addw (%y), %a
jsf carry1
flip
check_lower:
neqw $0, %b
jsf lower_carry
finishX:
flip
finish:
movw %a, (%y)
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
movw $0, %z
flip
計算量を無視した実装
代替レジスタを退避領域に使用することで、最初に示した実装と比較すれば、ずいぶんコード量を低減させることができました。
しかし:
下位桁での繰り上がりの有無を保持しておく
という、通常の多倍長演算の実装で用いられる発想では、これ以上のコード量低減は望めそうにありません。そこで:
現行桁の演算で繰り上がりが発生したならば、繰り上がりが発生しなくなるまで、上位桁への反映を済ませてしまう
という風に発想を転換してみましょう。
リスト5 先に上位桁に繰り上がりを反映
movw (%y), %a
addw $9, %y
addw (%y), %a
jsf carry
finish:
movw %a, (%y)
jmp loop_check
carry:
movw %a, (%y)
addw $0x0F, %y
movw $1, %a
addw (%y), %a
jsf carry
jmp finish
loop_check:
圧倒的にコード量を低減できました!
但し、このアルゴリズムでは、N桁の処理を実施する際の計算量 がO(N)ではなくO(N2 )になってしまいます。
特別な制約条件のない通常の開発において、このような実装をした場合、ソースコードレビューの席は針のムシロ になること確実です。
あくまで、実行性能よりもプログラム領域の最小化が優先、といった制約条件を前提とした実装の一例と考えてください。
ちなみに、筆者が最初にFXマイコンに触れた際に、10進補正付きの多倍長加減算命令("CAL DEM+" や "CAL DEM-")の:
繰り上がりが続く限り、メモリ上のデータに対する繰り上がり分の更新処理を繰り返す
という仕様が、際立って高機能に思えたのですが、実際に多倍長演算処理の最適化を考えてみると、このような実装にしておいた方が有用性が高い、という判断が働いたのだということがわかります。
多倍長加算処理の実装
「1桁分の繰り上がり配慮付き加算処理」ができましたので、いよいよ多倍長加算処理を組み上げてみましょう。
リスト6 多倍長加算処理
movw $0x0D, %a
movw $0x0E, %y
do_add:
movw %a, (%y)
swap
add_x:
movw (%y), %a
addw $9, %y
addw (%y), %a
jsf carry
finish:
movw %a, (%y)
jmp loop_check
carry:
movw %a, (%y)
addw $0x0F, %y
movw $1, %a
addw (%y), %a
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で順次表示する、といった処理を付け加えてみてもおもしろいのではないでしょうか。