乗算ルーチンの検討（ベーシックマスター開発 その23）

2024/08/24BASICMASTER, 昔のパソコン

BASICMASTERは日立製のCPU HD6800を使っている。これはモトローラのMC6800の互換品。昔のCPUなので乗算・除算命令は無く、シフト命令と加減算を組み合わせる必要がある。

コンパイラを作成・改良するにあたり、各種言語で、16bit = 16bit*16bitの乗算を行うサブルーチンがどのように実装されているか調べたので、結果をメモしておく。

GAME言語の乗算

GAMEでは下記のような AccAB*(IX,IX+1) → AccAB を実行する乗算ルーチンが使われていた。右端は実行サイクル数と、命令のバイト数である。

被乗数を右シフトしたキャリーを見て乗数をAccABに加算する。乗数はループのたびに2倍（左シフト）していく。

Electronic DIY with Arduinoの図がわかりやすい。

ループ部分は ML1〜BNE ML1 までで、これを16bit分（１６回）繰り返す。1ループあたりのサイクル数は、50cycle（分岐不成立時）、40cycle（分岐成立時）である。

（プログラムで実際に使われる数は小さな数が多いだろうから、平均すると45cycle未満だろう）

プログラムサイズの節約もあって　インデックスアドレッシングを使っている部分があり、そこをダイレクトモードにすれば 各1サイクル節約できる （46cycle/36cycle）。その代わり4バイトも！増えてしまうので、メモリが極めて少ない当時の環境では悩ましい問題だ。

乗数（W68）が256以下のときはループ回数は8回で済むので、その処理を入れると平均すると速くなる。これは他のルーチンも同様。

MLTPLY  STAA	W68		; 4 2
        STAB	W68+1		; 4 2
        LDAB	#16		; 2 2
        STAB	W66		; 4 2
        CLRA			; 2 1
        CLRB			; 2 1
ML1     LSR	W68		; 6 3
        ROR	W68+1		; 6 3
        BCC	ML2		; 4 2
	ADDB	1,X		; 5 2
	ADCA	0,X		; 5 2
ML2     ASL	1,X		; 7 2
        ROL	0,X		; 7 2
        DEC	W66		; 6 3
        BNE	ML1		; 4 2
        RTS			; 5 1

GAMEの該当部分のソースはASCII誌連載二回目（1978年7月号）に掲載されている。

GAME68コンパイラの演算ルーチンも上記と同じ。

• GAME68コンパイラ : 電子工作やってみたよ

NAKAMOZU Tiny BASICの乗算

NAKAMOZU Tiny BASICでは (IX,IX+1)*(IX+2,IX+3) → AccAB という処理を行なっている。

こちらは被乗数の左側のbitから処理していき、計算結果AccABを左シフトしている。乗数は変わらない。被乗数と計算結果を連結してシフトしているのが肝。

file.php (688×781)の一番上の図がわかりやすい。

ループ部分は MLT1〜BNE までで、1ループあたり 42cycle（分岐不成立時）、32cycle（分岐成立時）である。

GAMEよりも実行時間が短いのは、シフト対象が乗数（ダイレクトページ）ではなく結果（AccAB）になっているため。

２バイトシフトに14cycleもかかるのか、4サイクルで済むのかは大きな差である。

こちらもインデックスアドレッシングをダイレクトモードに変えれば、38,28サイクルまで減らせる。しかし、プログラムサイズとの兼ね合いでインデックスアドレッシングが使われたのだと思う（4バイト変わる）。

電大版 Tiny BASIC　（Bit誌1978年8月号 共立出版）のものも同様

MLTPLY  LDAA	#16		; 2 2	
        STAA	LPCT		; 4 2
        CLRA  			; 2 1
        CLRB   			; 2 1
MLT1    ASLA			; 2 1 
        ROLB			; 2 1
        ROL	1,X             ; 7 2
        ROL	0,X             ; 7 2
        BCC	*+6             ; 4 2
        ADDA	3,X             ; 5 2
        ADCB	2,X             ; 5 2
        DEC     LPCT            ; 6 3
        BNE     MLT1            ; 4 2
	RTS			; 5 1

NTBのソースは下記のサイトに掲載されている。

• Nakamozu Tiny Basic /ASCII

Fuzix-Compiler-Kit/support6800の乗算

EtchedPixels氏(aka. Alax cox)による6800コンパイラのサポートルーチンに含まれているサブルーチンである。英小文字を使っているのが現代風である。

スタックマシンなので 被乗数はスタックトップにある。それをインデックスレジスタ経由でアクセスしている。乗数も先頭でスタックに積んでいる。

処理はGAMEと同様。ループ部分は nextbit 〜 bne まで。 52,42cycle。GAMEより2cycle多いのは、乗数も被乗数もインデックスアクセスしているため。

__mul:
	pshb			; 4 1
	psha			; 4 1
	tsx			; 4 1
	ldab #16		; 2 2
	stab @tmp		; 4 2
	clra			; 2 1
	clrb			; 2 1
nextbit:
	lsr ,x			; 7 2
	ror 1,x			; 7 2
	bcc noadd		; 4 2
	addb 5,x		; 5 2
	adca 4,x		; 5 2
noadd:	lsl  5,x		; 7 2
	rol  4,x		; 7 2
	dec @tmp		; 6 3
	bne nextbit		; 4 2
	ins			; 4 1
	ins			; 4 1
	jmp __pop2		; 3 3

• Fuzix-Compiler-Kit/support6800/__mul.s at main · EtchedPixels/Fuzix-Compiler-Kit

拙作のGAMEクロスコンパイラの乗算ルーチン(1)

NAKAMOZU Tiny BASICを参考に、なるべくダイレクトページを使うようにしてみたルーチン。

ループ部分は ML01〜BNEまで 34,28 cycle。インデックスアクセスが無くなったので、ループカウンタに IXレジスタを使うことで さらに2cycle縮めている。

１サイクルでも減るとループ回数分（16回）減るので、効果は意外に大きい。ベーシックマスターのクロックは755KHz弱で、１サイクルあたり1.325μsもかかるので なおさらだ。

初期化部分で256未満の場合は16*8bitのルーチンを呼ぶようにして、姑息に速度を稼いでいる。

また、FCB $8C はASLB/ROLAをスキップするため。ABともに0なので実行しても問題はないのだが、1バイトと1サイクルを交換している。無くても大差はない。

MULTIPLY    STX     TDXWK           ;   5   2
            LDX     0,X             ;   6   2
            STX     W66             ;   4   2
            STAB    W68+1           ;   4   2
            STAA    W68             ;   4   2
            BEQ     MULTI02         ;   4   2
MULTI       LDX     #16             ;   3   3
            CLRA                    ;   2   1
            CLRB                    ;   2   1
            FCB     $8C             ;   3   1       SKIP2. It costs one byte but saves one cycle.
ML01        ASLB                    ;   2   1
            ROLA                    ;   2   1
            ROL     W68+1           ;   6   3
            ROL     W68             ;   6   3
            BCC     ML02            ;   4   2
            ADDB    W66+1           ;   3   2
            ADCA    W66             ;   3   2
ML02        DEX                     ;   4   1       
            BNE     ML01            ;   4　　　　　　2	    34cycle/loop => *16=>544cycle
            LDX     TDXWK
            RTS

• BASICMASTER/GAME-CC1 at main · zu2/BASICMASTER

拙作のGAMEクロスコンパイラの乗算ルーチン(2)

現在使っているもの。 Dr Jefyll’s method を使っている。

いままでの手法では掛け算を行うときに、通常はループごとに4byteのシフトが必要だが、これを3byteに抑えることで速度を稼ぐ方法。

file.php (688×781)の一番下の図がわかりやすい。

MC6800は、ダイレクトページであってもシフトに6cycleもかかるので、ループ内からシフトが無くなるのは大きい。

その代わり、前半ループ8回と後半ループ8回で処理を分けないといけないので、プログラムサイズは大きくなる。

*
*   MULTIPLY Dr Jefyll's method
*   MULTIPLY    AB = (IX,IX+1)*AB
*
MULTIPLY    STX     TDXWK           ;   5 2
            LDX     0,X             ;   6 2
            STX     W66             ;   4 2
            STAA    W68             ;   4 2
            CLRA                    ;   2 1
            STAB    W68+1           ;   4 2
            CLRB                    ;   2 1
            LDX     #8              ;   3 3
ML01        ROR     W68+1           ;   6 3
            BCC     ML02            ;   4 2
            ADDB    W66+1           ;   3 2
            ADCA    W66             ;   3 2
ML02        LSRA                    ;   2 1
            RORB                    ;   2 1
            DEX                     ;   4 1
            BNE     ML01            ;   4 2         28cycle/loop => *8=>224cycle
            ROR     W68+1           ;   6 3
ML03        TST     W68             ;   6 3
            BNE     ML031           ;   4 2         Is W68,W68+1 <= 255?
            TBA                     ;   2 1
            BRA     ML07            ;   4 2
ML031       LDX     #8              ;   3 3
ML04        ROR     W68             ;   6 3
            BCC     ML05            ;   4 2
            ADDB    W66+1           ;   3 2
            ADCA    W66             ;   3 2
ML05        LSRA                    ;   2 1
            RORB                    ;   2 1
            DEX                     ;   4 1
            BNE     ML04            ;   4 2         ↑28cycle/loop => *8=>224cycle
            ROR     W68             ;   6 3
ML06        LDAA    W68             ;   3 2
ML07        LDAB    W68+1           ;   3 2
            LDX     TDXWK           ;   4 2
            RTS                     ;   5 1

• BASICMASTER/GAME-CC1 at main · zu2/BASICMASTER

他のCPUの例

掛け算は、Z80と6502で8bit*8bitの掛け算を行うルーチンを比較したもの。

他のCPUと比べると6800遅いなーと思います。実は6809も遅いんだけど、LEAXが強力で、七難隠してたんだよな。

TobyLobster/multiply_test: Comparing 6502 multiply routinesは6502で各種乗算ルーチンを比較したもの。すごい。一読の価値あり。 Dr Jefyll’s method は、このページで知りました。

表引きをすると高速化できるというのは、誰でも思いつくが、素直に8bit*8bitの表を作ると128KBになるのでメモリに入らない （ROMに焼いて6820PIO経由でアクセスすれば……ロマンだ）。

16bit乗算を8bit乗算3回で実現するとして、各乗算を2乗の和or差で計算する場合、2乗を表引きしても表は512byteで足りる。

表引きした乗算については マイナス二乗法：ＰＩＣマイコンは面白い：So-netブログ が詳しい。ただ、6800は表引きが遅いので、どれぐらい速くなるかなあ。

• 掛け算
• TobyLobster/multiply_test: Comparing 6502 multiply routines
• マイナス二乗法：ＰＩＣマイコンは面白い：So-netブログ
• Programming:Integer Multiplication – CPCWiki

リンク

• GAME68コンパイラ : 電子工作やってみたよ
• Nakamozu Tiny Basic /ASCII
• Fuzix-Compiler-Kit/support6800/__mul.s at main · EtchedPixels/Fuzix-Compiler-Kit
• BASICMASTER/GAME-CC1 at main · zu2/BASICMASTER
• 6502.org • View topic – UM* (multiplication) bug in common 6502 Forths
• 掛け算
• TobyLobster/multiply_test: Comparing 6502 multiply routines
• Z80 乗算アルゴリズム : プログラミング指南 – Code Knowledge
• HRA’s room
• the fast multiplication
• Programming:Integer Multiplication – CPCWiki
• Reverse-engineering the multiplication algorithm in the Intel 8086 processor