MC6800のプログラミングテクニック(22) 除算の再検討 16bit版

2025/11/20BASICMASTER, 昔のパソコン

こんどは16bit版の除算を考える。考え方は8bit版と一緒だが、16bitだとレジスタが足りないので工夫が必要になる。

ワーク領域（剰余）は加減算が必要なので、レジスタに置く。16bit除算なので加減算も16bit幅だ。これでAccABを使ってしまう。

除数は固定なのでメモリ上にあれば良い。問題は被除数。幸い1bitずつシフトすれば済むので、メモリを直接シフトすれば済む。

メモリロケーションを直接操作できるのは便利であるが、これらの命令は遅い。1バイトのシフトに6cycも必要だ。MC6800の乗除算では、メモリシフトを減らすことが重要である。

回復法バージョン

ループカウンタにIXを使って素直に書いたバージョン。16bit比較は減算するしかないので、比較法よりも回復法が速い。

キャリービットを使って、6cycもかかるinc命令を使わないようにしているが、ループ後処理でrol/comが必要になり8cycかかる。

商に1のbitが2つ立てば元は取れるが、0〜1個だと損になる。


       	.setcpu 6800
        .export _div16x16
        .code
_div16x16:
        tsx
        ldx 2,x
        stx @tmp1     ; divisor
        stab @tmp2+1  ; divient
        staa @tmp2
        ldx #16
        clrb
        clra            ; clear remainder
loop:
        rol @tmp2+1	; 6 2
        rol @tmp2	; 6 2
        rolb		; 2 1
        rola		; 2 1
        subb @tmp1+1	; 3 2
        sbca @tmp1	; 3 2
        bcc next	; 4 2
        addb @tmp1+1	; 3 2
        adca @tmp1	; 3 2
next:
        dex		; 4 1
        bne loop	; 4 2
        ldab @tmp2+1
        ldaa @tmp2
        rolb
        rola
        comb
        coma
        rts

回復法その2 / Dr Jefyll method

先のプログラムは被除数を2バイト（16bit）単位でシフトする。メモリシフトは6cycかかる遅い命令なので、これを減らしたい。

乗算のDr Jefyll methodを応用して、除算でも1バイトだけシフトするプログラムが組める。

IXでシフトする1バイトを示す。カウンタをその2バイト後ろ（@tmp3）に置き、 2,x でアクセスする（tmp3-tmp2,x と書きたかったが、エラーになった）。

これによりloop末端でのカウンタ更新を避けて高速化を図っている。

6cycかかるシフト命令が1つ減ったが、rolがインデックスアドレッシングになったので +1cyc。ループカウンタも dexから dec 2,xになったので +3cyc。差し引き -2cyc。

バイト境界を超えるときに +11cyc。事前準備に+8cyc。

差し引きするとループ内が -2cycを16bit分で -32cyc。ループ前後に増えた分が19cycあっても 13cycの得になっている。

ループ展開すれば IXレジスタをカウンタとして使えるし、rolもエクステンドのままにできるので、さらに高速にできる。

多バイト除算であれば節約できるシフト命令も多いので、もっと差は開く。


       	.setcpu 6800
        .export _div16x16
        .code
_div16x16:
        tsx
        ldx 2,x
        stx @tmp1     ; divisor
        stab @tmp2+1  ; divient
        staa @tmp2
        ldx #$0808
        stx @tmp3
        ldx #tmp2
        clrb
        clra            ; clear remainder
;
loop:
        rol 0,x
        rolb
        rola
        subb @tmp1+1
        sbca @tmp1
        bcc next
        addb @tmp1+1
        adca @tmp1
next:
        dec 2,x
        bne loop
        inx
        cpx #tmp2+2
        bne loop
end:
        ldab @tmp2+1
        ldaa @tmp2
        rolb
        rola
        comb
        coma
        rts

非回復法 16bit除算

符号なし16bit同士の除算。剰余が必要な場合は mnext の終わりで補正が必要。

加算・減算の判断と最上位ビットの処理があるので、回復法よりもかなり長くなるのが難点。Z80のCCFのようなキャリー反転命令があれば短くできるが、MC6800には無い。

回復法と比べるとループ内に分岐が2-3個増え、代わりに回復のためのaddb/adcaが減る。前者が 8-12cyc, 後者が6cycなので損している。

回復法と同様にシフトするバイトを1つ減らして高速化できるが、それでも回復法の方が速いので損である。

除数が0x8000以下ならキャリーを使わずに素直に符号ビットを見ればよく、その場合は回復法よりも速い (8bit除算の記事を参照のこと）。


       	.setcpu 6800
        .export _div16x16
        .code
_div16x16:
        tsx
        ldx 2,x
        stx @tmp1     ; divisor
        stab @tmp2+1  ; divient
        staa @tmp2
        ldx #16
        clrb
        clra            ; clear remainder
;
; main loop when AQ>=0
;
ploop:
        asl @tmp2+1
        rol @tmp2
        rolb
        rola
        bcs pcarry
        subb @tmp1+1
        sbca @tmp1
        bcs mnext
        bra pnext
pcarry:
        subb @tmp1+1
        sbca @tmp1
        bcc mnext
pnext:
        inc @tmp2+1
        dex
        bne ploop
        ldab @tmp2+1
        ldaa @tmp2
        rts
;
; main loop when AQ<0
;
mloop:
        asl @tmp2+1
        rol @tmp2
        rolb
        rola
        bcs mcarry
        addb @tmp1+1
        adca @tmp1
        bcc pnext
        bra mnext
mcarry:
        addb @tmp1+1
        adca @tmp1
        bcs pnext
mnext:
        dex
        bne mloop
        ldab @tmp2+1
        ldaa @tmp2
        rts