Difference between revisions of "Z80 Routines:Math:Multiplication"
From WikiTI
(creation) |
m (`sbc hl,bc` ==> `sbc hl,de`) |
||
| (9 intermediate revisions by 6 users not shown) | |||
| Line 1: | Line 1: | ||
| + | [[Category:Z80 Routines:Math|Multiplication]] | ||
| + | [[Category:Z80 Routines|Multiplication]] | ||
| + | |||
== Introduction == | == Introduction == | ||
| Line 4: | Line 7: | ||
They can easily be unrolled to gain some speed. | They can easily be unrolled to gain some speed. | ||
| − | == 8*8 multiplication == | + | == Unsigned versions == |
| + | |||
| + | === 8*8 multiplication === | ||
The following routine multiplies h by e and places the result in hl | The following routine multiplies h by e and places the result in hl | ||
| Line 10: | Line 15: | ||
<nowiki> | <nowiki> | ||
mult_h_e | mult_h_e | ||
| − | ld | + | ld d, 0 ; Combining the overhead and |
| − | + | sla h ; optimised first iteration | |
| − | + | sbc a, a | |
| − | sla h | + | and e |
| − | + | ld l, a | |
| − | ld l, | + | |
| − | ld b, 7 | + | ld b, 7 |
_loop: | _loop: | ||
add hl, hl | add hl, hl | ||
| Line 28: | Line 32: | ||
</nowiki> | </nowiki> | ||
| − | == 16*8 multiplication == | + | === 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...) | 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...) | ||
| Line 56: | Line 60: | ||
</nowiki> | </nowiki> | ||
| − | == 16*16 multiplication == | + | === 16*16 multiplication === |
The following routine multiplies bc by de and places the result in dehl. | The following routine multiplies bc by de and places the result in dehl. | ||
| Line 62: | Line 66: | ||
<nowiki> | <nowiki> | ||
mult_de_bc | mult_de_bc | ||
| − | ld | + | ld hl, 0 |
| − | + | ||
sla e ; optimised 1st iteration | sla e ; optimised 1st iteration | ||
| Line 85: | Line 88: | ||
ret | ret | ||
| + | </nowiki> | ||
| + | |||
| + | == 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. --> | ||
| + | |||
| + | === 8*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> | </nowiki> | ||
Latest revision as of 19:31, 28 April 2022
Contents
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)
