MC6800のプログラミングテクニック(20) 除算の再検討 8bit版
1978年に発表された Intel 8086 には乗除算命令が搭載されていた。それ以前の8bitマイクロプロセッサでは、MC6801やMC6809に8bit乗算命令があるぐらい。
初期のRISCであるSPARCでも パイプラインを乱さないように乗除算命令すらなく びっくりしたものだ。
さて、ソフトウェアで除算を行う場合、代表的な方法は回復法と非回復法（引きっ放し法）である。SRT法などハードウェア実装を主にした方法はソフトウェア実装には不向きなので使わない。
回復法で8bit除算
わかりやすい回復法で8bit除算を書いてみよう。Aに剰余、Bに被除数と商、メモリ上に除数を置く。
テストのため、chibiccの関数として使えるように 引数はAccBとスタックで与えているが、通常のサブルーチンとして使うなら両方ともレジスタ渡しが良い。
ループ本体の処理時間は 22-25cyc, 14bytes である。商に1が立つときが25cyc, 0のときは22cycである。
.setcpu 6800 .export _div8x8 .code ; ; AccB = AccB / TOS ; ; AccB: divient ; Stack: ; 0-1: return address ; 2: divisor ; _div8x8: tsx tba ldab 2,x clrb stab @tmp1 ; divisor ldx #8 loop: asla ; 2 1 rolb ; 2 1 subb @tmp1 ; 3 2 divient - divisor bcs skip ; 4 2 can't subtract inca ; 2 1 bra next ; 4 2 skip: addb @tmp1 ; 3 2 next: dex ; 4 1 bne loop ; 4 2 tab clra rts
キャリーを利用した改良
引き算の直後のキャリーフラグは、引けた場合はC=0, 引けなかった場合はC=1になっている。本来必要な情報の逆になっているのだが、これが使える。
キャリーを次回のシフト時にAccAの末尾に入れるようにする（asl→rolに変更）。ループ終了時点で1bit未処理なので rol命令を追加する。終了時点でビット反転（com）することで 辻褄を合わせる。
ループ内の処理時間は商が1になるときに19cyc, 0のときに22cycになる。1のときはに6cyc縮んでいる。0のときは変わらない。バイト数も1つ少ない。
ただし、ループ最後の辻褄合わせで4cyc必要になる。商が0になるときは損だが 1bitでも1になっていれば少し速くなる。
_div8x8: tsx tba ldab 2,x stab @tmp1 ; divisor ldx #8 clrb loop: rola ; 2 1 rolb ; 2 1 subb @tmp1 ; 3 2 bcc next ; 4 2 addb @tmp1 ; 3 2 next: dex ; 4 1 bne loop ; 4 2 rola ; 2 1 coma ; 2 1 tab clra rts
回復法で引かない方法（比較法）
一般的なアルゴリズムの説明では比較と減算は同コストなので、引いてみてだめなら足す方法が良いと書かれている。
しかしながら、MC6800の場合、8bit除算であれば、比較して 引けるなら引くという方法でも良いのである。MC6809なら16bitでも同様。
（MC6800で16bitの場合は引いてみるしかない。cmp命令のキャリー付きがあれば比較法でも良いが、そんな便利な命令はないので）
ループ内の処理時間は商が1になるときに22cyc, 0のときに19cycになる。先ほどと必要時間が逆になっていて、0の時が速い。
実は整数除算では、商のビット数は圧倒的に0が多くなるので（これは別項で書く）、こちらの方が平均的に速い。
_div8x8: tsx tba ldab 2,x stab @tmp1 ; divisor ldx #8 clrb loop: rola ; 2 1 rolb ; 2 1 cmpb @tmp1 ; 3 2 bcs next ; 4 2 subb @tmp1 ; 3 2 next: dex ; 4 1 bne loop ; 4 2 rola ; 2 1 coma ; 2 1 tab clra rts
非回復法除算
回復法では引けなかったときは足すのだが、これが無駄なので足さなくても良いようにしたのが非回復法。
足し戻すコストが大きい場合（longなど）では効果絶大だが、8bit除算ではオーバーヘッドの方が大きい。
非回復法の除算は符号ビットを使用するので、8bit全体を使った除算には そのままでは適用できない。
そこで、このプログラムはCarry bitを符号ビットに見立てて処理している。
キャリーが1のときのadd/subの結果が期待の反対になってしまうので、そこを分岐で判断 （pcarry,mcarry付近）。
この分岐の判断に4cyc必要なので、8bit除算では却って遅くなる（回復のaddは3cycで済むので）。
高速化のためには incをsec/clcで代用したり、ループ末のdex/bneを展開する必要があるが、わかりにくくなるので、このプログラムは素直に書いてある。
剰余を正しく得るためには、最後のステップで AQ<0 のときに、剰余に除数を加える必要がある。
.setcpu 6800 .export _div8x8 .code _div8x8: tsx ldaa 2,x staa @tmp1 ; divisor ldx #8 clra ; clear remainder ; ; main loop when AQ>=0 ; ploop: aslb rola bcs pcarry suba @tmp1 bcs mnext bra pnext pcarry: suba @tmp1 bcc mnext pnext: incb dex bne ploop clra rts ; ; main loop when AQ<0 ; mloop: aslb rola bcs mcarry adda @tmp1 bcc pnext bra mnext mcarry: adda @tmp1 bcs pnext mnext: dex bne mloop clra rts
剰余が欲しい場合は、ループ終了時点でAccAに入っている値を使う。最後にキャリーが立っている場合（結果が負の時）は、剰余の補正が必要。
mnext: dex bne mloop tab ; 剰余を戻り値にする beq mrem ; 剰余が0でなければ addb @tmp1 ; 補正する mrem: clra rts
以前、GAME-CCコンパイラ用の非回復法の除算ルーチンを紹介しましたが、GAME言語は符号付き整数しか扱わないので問題にならなかったのでした。
（以前のルーチンは現在の視点で見ると遅いので、書き直したいものだ）。