Z80 Routines:Math:Multiplication: Difference between revisions

From WikiTI
Jump to navigationJump to search
No edit summary
Zeda (talk | contribs)
m `sbc hl,bc` ==> `sbc hl,de`
 
(4 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 91: Line 90:
  </nowiki>
  </nowiki>


=== 24*24 multiplication ===
== Signed versions ==
 
<!-- do the routines later, basically try to use cpu instruction that preserve bit 7 (sign) or if this is not possible, just take the sign out, do the multiplication and give the sign afterwards and accordingly. -->


The following routine multiplies bcd by ehl and places the result in bcdehl. It uses 2 bytes of ram, but those can be substituted for IX half registers. (By thepenguin77)
=== 8*8 multiplication ===


=== 16*8 multiplication ===
=== 16*16 multiplication ===
The following routine multiplies bc by de and places the signed result in dehl.
  <nowiki>
  <nowiki>
multDBCbyEHL:
push de
push hl
ld ix, $8000
ld (ix), l
xor a
ld h, a
ld l, a


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


ld (ix+1), a
pop af
ld (ix), a
push de
ld a, (ix+1)


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


ld (ix+1), a
; de:hl = bc*de
pop af ;least sig number
ex de, hl
ex (sp), hl ;D and 2nd least sig in for new number
ld (ix), l
pop hl ;D and 2nd least sig
push af ;least sig number
push hl ;2nd least sig number
ex de, hl
ld a, (ix+1)


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


ld b, a
  bit 7,d
ld c, h
  jr z,muldpos
ld d, l
  sbc hl,bc
pop hl
muldpos:
ld a, l
pop hl
ld h, a
ret


;####
  or b
;input: DBC = 1 number
  jp p,mulbpos
; AHL = running number
  sbc hl,de
; (ix) = to multiply by
mulbpos:
;output: AHLE = output
; E is done
; DBC = 1 number


do8Bits:
  ld a,16
ld (ix+1), 8
mulloop:
loop:
  add hl,hl
srl (ix)
  rl e
jr nc, skip
  rl d
  jr nc,mul0bit
  add hl,bc
  jr nc,mul0bit
  inc de
mul0bit:
  dec a
  jr nz,mulloop
</nowiki>


add hl, bc
adc a, d
skip:
rra
rr h
rr l
rr e
dec (ix+1)
jr nz, loop
ret
</nowiki>


== Signed versions ==
'''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]):


<!-- do the routines later, basically try to use cpu instruction that preserve bit 7 (sign) or if this is not possible, just take the sign out, do the multiplication and give the sign afterwards and accordingly. -->
<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:


=== 8*8 multiplication ===
a b product
 
pos pos ab                = ab
=== 16*8 multiplication ===
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 02:31, 29 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)