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

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

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

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

まずは,多倍長加算処理に必要な,⁠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レジスタ内容が共に破壊されるため,⁠演算結果の一時保存」「データ位置の復旧」が必要

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

※4)
16進ダンプ片手にゲームプログラムを入力していた頃を思い出してしまいました…。

代替レジスタの使用

先述したような長い実装になってしまうのは,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

著者プロフィール

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

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