アンティーク・アセンブラ~Antique Assembler

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

この記事を読むのに必要な時間:およそ 5.5 分

計算量を無視した実装

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

しかし:

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

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

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

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

リスト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(N2になってしまいます。

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

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

ちなみに,筆者が最初に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で順次表示する,といった処理を付け加えてみてもおもしろいのではないでしょうか。

著者プロフィール

藤原克則(ふじわらかつのり)

Mercurial三昧の日々が嵩じて, いつの間にやら『入門Mercurial Linux/Windows対応』を上梓。凝り性なのが災いして,年がら年中アップアップな一介の実装屋。最近は仕事の縁が元で,OpenSolarisに入れ込む毎日。