MC6800のプログラミングテクニック(23) 除算の再検討 32bit版
32bit版の除算を考える。考え方は8/16bit版と一緒だが、32bitだとレジスタが全く足りない。32bit加減算が必要なのに、AccAB合わせても16bit幅しかない。
被除数とワーク領域（剰余）だけで合計8バイトものシフトが発生するので、素直に書くとシフトだけで 2*2 + 6*6 = 40cycも使う （2つはAccABを使う計算）。
40cyc * 32bitループだけで 1280cyc。1MHzの6800だと1.28msもかかる。遅すぎるのだ。
比較法バージョン
chibiccに合わせて、被除数を@long、除数をスタックにあると想定。
下位16bitが比較法、上位は回復法っぽい処理になっている。この方法は商に0が立つ時の処理が最小になっていて、平均すると速いはず。
loop先頭の asl/rol命令は、1バイトのみシフトにした方が良い（3バイト分減らす）。準備とループ判定処理が増えるが、6*3*32 = 576cycも減るので十分に元は取れる。
商を立てるinc long+3 は、clcにして次回ループで@longの下位に押し込む方法も使える。商に1が立つ場合に4cyc減る。
ただし、ループ末で @long全体の左シフトと反転が必要になるので、6*4*2 = 48cycが追加される。
商に1が12bit以上立てば得ではあるが、除算の再検討・データの性質で書いたように、被除数がランダム・除数が冪乗則の場合でも1になるのは14-15bit程度。被除数が小さな数に偏った場合はさらに1になるビットは減るので、元が取れるかどうかは微妙。
.setcpu 6800 .export _div32x32 .code ; ; @long = @long / TOS (2-5,x) ; _div32x32: tsx ldx 2,x stx @tmp1 ; divisor (tmp1:tmp2) tsx ldx 4,x stx @tmp2 ; ldx #0 stx @tmp3 ; remainder (upper 16bits) ldx #32 ; loop count ; clrb ; remainder (lower 16bits) clra ; loop: asl @long+3 ; shift divient 32bits rol @long+2 rol @long+1 rol @long rolb ; shift work 32bits rola rol @tmp3+1 rol @tmp3 ; pshb psha subb @tmp2+1 ; remainder - divisor (lower 16bits) sbca @tmp2 ldab @tmp3+1 ; upper 16bits ldaa @tmp3 sbcb @tmp1+1 sbca @tmp1 bcs skip stab @tmp3+1 ; update remainder staa @tmp3 pula pulb subb @tmp2+1 sbca @tmp2 inc @long+3 bra next skip: pula pulb next: dex bne loop rts
非回復法のプログラム
非回復法の場合、上記の asl @long … pulb までの部分が4つ必要になる。ループ末端の処理も増えるので、所要メモリがかなり増える。
下のプログラムは、左シフト・加減算をサブルーチンにしたもの。MC6800のサブルーチンコールはjsr/rtsで 14cycも喰うのだが、サイズを小さくするために使っている。
速度が気になる用途ならインライン展開すべき。
詳細な所要時間は次の項で述べる。
.setcpu 6800 .export _div32x32 .code ; ; @long = @long / TOS (2-5,x) ; _div32x32: tsx ldx 2,x stx @tmp1 ; divisor (tmp1:tmp2) tsx ldx 4,x stx @tmp2 ; ldx #0 stx @tmp3 ; remainder (upper 16bits) ldx #32 ; loop count ; clrb ; remainder (lower 16bits) clra ; ; main loop when AQ>=0 ; ploop: jsr shift32 bcs pcarry jsr sub32 bcs mnext bra pnext pcarry: jsr sub32 bcc mnext pnext: inc @long+3 dex bne ploop rts ; ; main loop when AQ<0 ; mloop: jsr shift32 bcs mcarry jsr add32 bcc pnext bra mnext mcarry: jsr add32 bcs pnext mnext: dex bne mloop rts ; shift32: asl @long+3 ; shift divient 32bits rol @long+2 rol @long+1 rol @long rolb ; shift work 32bits rola rol @tmp3+1 rol @tmp3 rts add32: addb @tmp2+1 adca @tmp2 psha ldaa @tmp3+1 ; upper 16bits adca @tmp1+1 staa @tmp3+1 ldaa @tmp3 adca @tmp1 staa @tmp3 pula rts sub32: subb @tmp2+1 sbca @tmp2 psha ldaa @tmp3+1 ; upper 16bits sbca @tmp1+1 staa @tmp3+1 ldaa @tmp3 sbca @tmp1 staa @tmp3 pula rts
非回復法プログラムの所要時間
32bit減算部分を比べてみよう。
回復法の場合は、AccAB,@tmp3を元に戻す可能性があるので、ABレジスタをpshしたり、@tmp3の更新タイミングをずらしたりしている。
非回復法では素直に更新すれば良く、保存するレジスタはAccAだけで済んでいる
回復法では 商に1が立つ場合は52cyc+分岐4cyc、商が0のときは38cycを要するが、非回復法ではどちらも 34cyc+分岐4cycで済む（jsr/rtsを除く）。
インライン展開すれば かなり高速になる。ただし、加減算だけで18bytes*4=72bytesも喰う。
pshb psha subb @tmp2+1 ; remainder - divisor (lower 16bits) sbca @tmp2 ldab @tmp3+1 ; upper 16bits ldaa @tmp3 sbcb @tmp1+1 sbca @tmp1 bcs skip stab @tmp3+1 ; update remainder staa @tmp3 pula pulb subb @tmp2+1 sbca @tmp2
sub32: subb @tmp2+1 sbca @tmp2 psha ldaa @tmp3+1 ; upper 16bits sbca @tmp1+1 staa @tmp3+1 ldaa @tmp3 sbca @tmp1 staa @tmp3 pula rts