Difference between revisions of "Z80 Routines:Math:Multiplication"

From WikiTI
Jump to: navigation, search
(→‎16*16 multiplication)
m (`sbc hl,bc` ==> `sbc hl,de`)
 
(5 intermediate revisions by 3 users not shown)
Line 15: Line 15:
 
  <nowiki>
 
  <nowiki>
 
mult_h_e
 
mult_h_e
−
   ld l, 0
+
   ld d, 0 ; Combining the overhead and
−
  ld d, l
+
   sla h ; optimised first iteration
−
 
+
   sbc a, a
−
   sla h ; optimised 1st iteration
+
  and e
−
   jr nc, $+3
+
   ld l, a
−
   ld l, e
+
 
    
 
    
−
   ld b, 7
+
   ld b, 7
 
_loop:
 
_loop:
 
   add hl, hl           
 
   add hl, hl           
Line 98: Line 97:
  
 
=== 16*8 multiplication ===
 
=== 16*8 multiplication ===
 +
 +
=== 16*16 multiplication ===
 +
 +
The following routine multiplies bc by de and places the signed result in dehl.
 +
<nowiki>
 +
 +
;
 +
;16 bit signed multiply
 +
;31 bytes
 +
;min: 928cc
 +
;max: 1257cc
 +
;avg: 1088.5cc
 +
 +
 +
; call with bc, de = 16 bit signed numbers to multiply
 +
; returns  de:hl = 32 bit signed product
 +
; corrupts  a
 +
 +
; de:hl = bc*de
 +
 +
multiply:
 +
  xor a
 +
  ld h,a
 +
  ld l,a
 +
 +
  bit 7,d
 +
  jr z,muldpos
 +
  sbc hl,bc
 +
muldpos:
 +
 +
  or b
 +
  jp p,mulbpos
 +
  sbc hl,de
 +
mulbpos:
 +
 +
  ld a,16
 +
mulloop:
 +
  add hl,hl
 +
  rl e
 +
  rl d
 +
  jr nc,mul0bit
 +
  add hl,bc
 +
  jr nc,mul0bit
 +
  inc de
 +
mul0bit:
 +
  dec a
 +
  jr nz,mulloop
 +
</nowiki>
 +
 +
 +
'''Note:''' The code was originally John Metcalf's
 +
([https://github.com/impomatic/z80snippets/blob/master/mulsigned.asm here]),
 +
so this looks similar, but Sue Doenim found a bug with negative BC, so we fixed that.
 +
The fix is based on Goplat's pseudocode
 +
([https://www.omnimaga.org/asm-language/(z80)-16-bit-*-16-bit-32-bit-signed-multiplication/msg154690/#msg154690 here]):
 +
 +
<nowiki>
 +
Here's a possibillity: Since a negative signed number is 65536 less than its
 +
interpreted as unsigned, you can just do an unsigned multiplication and if any
 +
side is negative, subtract the other side from the high word of the result:
 +
 +
a b product
 +
pos pos ab                = ab
 +
pos neg a(b-65536)        = ab - 65536a
 +
neg pos (a-65536)b        = ab - 65536b
 +
neg neg (a-65536)(b-65536) = ab - 65536(a+b)
 +
</nowiki>

Latest revision as of 18:31, 28 April 2022


Introduction

All these routines use the restoring multiplication algorithm, adapted to the z80 architecture to maximize speed. They can easily be unrolled to gain some speed.

Unsigned versions

8*8 multiplication

The following routine multiplies h by e and places the result in hl 

mult_h_e
   ld	d, 0	; Combining the overhead and
   sla	h	; optimised first iteration
   sbc	a, a
   and	e
   ld	l, a
   
   ld	b, 7
_loop:
   add	hl, hl          
   jr	nc, $+3
   add	hl, de
   
   djnz	_loop
   
   ret

16*8 multiplication

The following routine multiplies de by a and places the result in ahl (which means a is the most significant byte of the product, l the least significant and h the intermediate one...) 

mult_a_de
   ld	c, 0
   ld	h, c
   ld	l, h

   add	a, a		; optimised 1st iteration
   jr	nc, $+4
   ld	h,d
   ld	l,e

   ld b, 7
_loop:
   add	hl, hl
   rla
   jr	nc, $+4
   add	hl, de
   adc	a, c            ; yes this is actually adc a, 0 but since c is free we set it to zero and so we can save 1 byte and up to 3 T-states per iteration
   
   djnz	_loop
   
   ret

16*16 multiplication

The following routine multiplies bc by de and places the result in dehl. 

mult_de_bc
   ld	hl, 0

   sla	e		; optimised 1st iteration
   rl	d
   jr	nc, $+4
   ld	h, b
   ld	l, c

   ld	a, 15
_loop:
   add	hl, hl
   rl	e
   rl	d
   jr	nc, $+6
   add	hl, bc
   jr	nc, $+3
   inc	de
   
   dec	a
   jr	nz, _loop
   
   ret

Signed versions

8*8 multiplication

16*8 multiplication

16*16 multiplication

The following routine multiplies bc by de and places the signed result in dehl. 


;
;16 bit signed multiply
;31 bytes
;min: 928cc
;max: 1257cc
;avg: 1088.5cc


; call with bc, de = 16 bit signed numbers to multiply
; returns   de:hl = 32 bit signed product
; corrupts  a

; de:hl = bc*de

multiply:
  xor a
  ld h,a
  ld l,a

  bit 7,d
  jr z,muldpos
  sbc hl,bc
muldpos:

  or b
  jp p,mulbpos
  sbc hl,de
mulbpos:

  ld a,16
mulloop:
  add hl,hl
  rl e
  rl d
  jr nc,mul0bit
  add hl,bc
  jr nc,mul0bit
  inc de
mul0bit:
  dec a
  jr nz,mulloop


Note: The code was originally John Metcalf's (here), so this looks similar, but Sue Doenim found a bug with negative BC, so we fixed that. The fix is based on Goplat's pseudocode (here): 

Here's a possibillity: Since a negative signed number is 65536 less than its
interpreted as unsigned, you can just do an unsigned multiplication and if any
side is negative, subtract the other side from the high word of the result:

	a	b	product
	pos	pos	ab                 = ab
	pos	neg	a(b-65536)         = ab - 65536a
	neg	pos	(a-65536)b         = ab - 65536b
	neg	neg	(a-65536)(b-65536) = ab - 65536(a+b)
Retrieved from "https://wikiti.brandonw.net/index.php?title=Z80_Routines:Math:Multiplication&oldid=11861"