Z80での固定値の乗算処理の最適化

１．はじめに
　Z80 で固定値の乗算処理はシフト（２のべき乗）と加算を使って最適化できますが、複数のやり方があるので少し整理し、アセンブラのソースを自動生成してみようと思います。


２．乗算処理の複数の展開方法
　例えば A-reg の値を１０倍する処理であれば下記のように書けます。

; A <- val ; A -> val * 10 Mul10: LD L,A ADD A,A ; x2 ADD A,A ; x4 ADD A,L ; x5 ADD A,A ; x10

　しかし同様な手法で次のように処理することも可能ですが、上記の処理と実行時間及び処理サイズが同様になります。

; A <- val ; A -> val * 10 Mul10: ADD A,A ; x2 LD L,A ADD A,A ; x4 ADD A,A ; x8 ADD A,L ; x10

　両者を比較してみると１０(0b1010)倍の筆算による処理を展開したものと同様で、両者は２進数表現で上位から２個目の１を加算するタイミングが異なるだけであることが判ります。
　そこで前者のように１倍の値を加算する方式によりＣ言語で Z80 のアセンブラソースを自動生成するプログラムを作成してみました。
　実行例が下記になります。

; Z80 source of 5 * const 10 ; A <- val ; A -> val * 10 LD A,5 ; can set any value Mul10: LD L,A ADD A,A ; x2 ADD A,A ADD A,L ; x5 ADD A,A ; x10

３．減算を使用した乗算処理の最適化
　減算処理も織り込むことで更に最適化が可能なので、例として１６倍から減算を一回使用する場合に最適化可能なパターンについて列挙すると下表のようになります。

No.	multiplier	binary value	Subtraction value
1	x15	1111	x16 - x1
2	x14	1110	x16 - x2
3	x12	1100	x16 - x4

　この表を眺めてみるとソースを自動生成する処理が浮かんできますね。と言うことで先程のＣ言語で作成したアセンブラソース自動生成プログラムに組み込み、１６倍～１１倍までの Z80 アセンブラソースを自動生成した結果を以下に示します。

; Z80 source of 5 * const 16 ; A <- val ; A -> val * 16 LD A,5 ; can set any value Mul16: ADD A,A ADD A,A ADD A,A ADD A,A

; Z80 source of 5 * const 15 ; A <- val ; A -> val * 15 LD A,5 ; can set any value Mul15: LD L,A ADD A,A ADD A,A ADD A,A ADD A,A SUB L

; Z80 source of 5 * const 14 ; A <- val ; A -> val * 14 LD A,5 ; can set any value Mul14: LD L,A ADD A,A ADD A,A ADD A,A SUB L ADD A,A

; Z80 source of 5 * const 13 ; A <- val ; A -> val * 13 LD A,5 ; can set any value Mul13: LD L,A ADD A,A ADD A,L ; x3 ADD A,A ; x6 ADD A,A ADD A,L ; x13

; Z80 source of 5 * const 12 ; A <- val ; A -> val * 12 LD A,5 ; can set any value Mul12: LD L,A ADD A,A ADD A,L ; x3 ADD A,A ; x6 ADD A,A ; x12

; Z80 source of 5 * const 11 ; A <- val ; A -> val * 11 LD A,5 ; can set any value Mul11: LD L,A ADD A,A ; x2 ADD A,A ADD A,L ; x5 ADD A,A ADD A,L ; x11

★追記　2026/02/13　{
　例えば、ｘ28の場合は自動生成されたアセンブラソース出力が次のようになります。

; Z80 source of 5 * const 28 ; A -> val * 28 LD A,5 ; can set any value Mul28: LD L,A ADD A,A ADD A,A ADD A,A SUB L ADD A,A ADD A,A

}

　今回作成したアセンブラソース生成処理のソースは下記でオーバーフロー処理は割愛しています。また、HLとDEレジスタペアを使用するようにすれば２バイト処理に拡張することが容易にできると思います。
　尚、今回はｗｅｂ上でgcc環境（gdb環境含む）を提供している OnlineGDB の環境で動かしてみました。

Ｚ８０固定値乗算アセンブラソース生成処理（Ｃ言語）

/**************************************** Simple Multiplication compiler Ver 0.02 2026/02/07 reduce shift when Subtraction Method Ver 0.01a 2026/02/05 more simple logic by skyriver ****************************************/ #include <stdio.h> #include <stdlib.h> void MulEx( int mul ) { if ( mul <= 1 ) { return; } MulEx( mul / 2 ); printf( "\tADD\tA,A" ); if ( mul & 1 ) { printf( "\n\tADD\tA,L" ); } printf( "\t; x%d\n", mul ); } void CompMul( int x, int y ) { int onbit, subval, subflg, mask; onbit = 0; printf( "; Z80 source of %d * const %d\n", x, y ); printf( "; A <- val\n" "; A -> val * %d\n" , y ); subval = subflg = 1; for ( mask = 1; mask <= y; mask <<= 1 ) { if ( y & mask ) { onbit++; subflg = 0; } else { if ( subflg ) { subval <<= 1; } else { subval = 0; } } } printf( "\tLD\tA,%d\t; can set any value\n", x ); printf( "Mul%d:", y ); if ( y == 0 ) { printf( "\tXOR\tA,A\n" ); } else { if ( onbit == 1 ) { for ( y--; y; y >>= 1 ) { printf( "\tADD\tA,A\n" ); } } else if ( (subval != 0) && (onbit > 2) ) { printf( "\tLD\tL,A\n" ); for ( int bit = mask >> 1; bit; bit >>= 1 ) { printf( "\tADD\tA,A\n" ); if ( bit == subval ) { printf( "\tSUB\tL\n" ); } } } else { if ( onbit > 1 ) { printf( "\tLD\tL,A\n" ); } MulEx( y ); } } } int main( int argc, char *argv[] ) { int x, y; if ( argc != 3 ) { printf( "input X and Y, then answer x*y Z80 assembler source" ); } else { x = atoi( argv[ 1 ] ); y = atoi( argv[ 2 ] ); CompMul( x, y ); } return 0; }

・2026/02/07　減算手法でaddの回数を削減 ・2026/02/05　ロジックを若干簡略化

４．まとめ
　固定値の乗算処理の最適化について検討し、シフトと加算を使って最適化するやり方は複数の実現方法がありますが、処理内容はシフト途中で適宜１倍値を加算する処理と同等であることが判り、これらの情報を元に Z80 のアセンブラソースを生成するプログラムを作ってみました。
　更に被乗数の２のべき乗から減算する手法での最適化についても整理し自動生成プログラムに追加できました。
　実は上記の自動生成プログラムでは最適解を選出するロジックを端折っていますが、加算と減算の両者を使用する場合も含めた真の最適解を求める問題はなかなか面白そうです。
　このような自動生成処理はコンパイラへの実装やインタープリタでの処理内で固定値の乗算を複数回実行する際の高速化としてのJIT（Just-In-Time）コンパイル等で利用できるかもしれませんね。