Z80:Math Routines - Revision history

Xeda112358: /* gcdHL_DE */ copied wrong code first time, added 8-bit version

2016-05-31T22:30:03Z

gcdHL_DE: copied wrong code first time, added 8-bit version

← Older revision		Revision as of 22:30, 31 May 2016
Line 1,138:		Line 1,138:
	ld a,h \ or l \ ret z		ld a,h \ or l \ ret z
	sbc hl,de		sbc hl,de
	~~jr z,step4~~
	add hl,de		add hl,de
			ret z
	ld b,1		ld b,1
	ld a,e \ or l \ rra \ jr c,~~step2~~		ld a,e \ or l \ rra \ jr c,+_
	inc b		inc b
	rr h \ rr l		rr h \ rr l
	rr d \ rr e		rr d \ rr e
	ld a,e \ or l \ rra \ jr nc,$-12		ld a,e \ or l \ rra \ jr nc,$-12
	~~ld a,e~~		_:
	~~and l~~		srl h \ rr l \ jr nc,$-4 \ adc hl,hl
	~~rra~~		ex de,hl
	~~jr c,step3~~		_:
	~~step2~~:		srl h \ rr l \ jr nc,$-4 \ adc hl,hl
	~~bit 0,~~l \ jr z,$+3 \ ex de,hl
	~~xor a~~ \ ~~sbc hl,de~~ \ jr nc,$+7 \ ~~sub l \ ld l~~,~~a \ sbc a,a \ sub h \ ld h,a~~
	~~step3:~~
	xor a \ sbc hl,de		xor a \ sbc hl,de
	jr z,~~step4~~		jr z,+_
	jr nc,~~$+7~~ \ sub l \ ld l,a \ sbc a,a \ sub h \ ld h,a		jr nc,-_ \ sub l \ ld l,a \ sbc a,a \ sub h \ ld h,a
	~~srl h \ rr l \ jr nc,$~~-4		jp -_-1
	~~adc hl,hl~~		_:
	~~jp step2~~
	~~step4~~:
	ex de,hl		ex de,hl
	dec b		dec b

Xeda112358: /* GCDHL_BC */ is now gcdHL_DE, much more efficient algorithm.

2016-05-31T20:57:23Z

GCDHL_BC: is now gcdHL_DE, much more efficient algorithm.

← Older revision		Revision as of 20:57, 31 May 2016
Line 1,128:		Line 1,128:


	= ~~GCDHL_BC~~ =		= gcdHL_DE =
	This computes the Greatest Common Divisor of HL and ~~BC:~~		This computes the Greatest Common Divisor of HL and DE, using the binary gcd algorithm.

	~~GCDHL_BC~~:		gcdHL_DE:
	;~~Inputs:~~		;gcd(HL,DE)->HL
	; HL,BC		;binary GCD algorithm
	;~~Outputs:~~		ld a,h \ or l \ ret z
	~~; A is 0~~		ex de,hl
	~~; BC~~,~~DE are both the GCD~~		ld a,h \ or l \ ret z
	~~; HL is 0~~		sbc hl,de
	ld a,16		jr z,step4
	ld de,0		add hl,de
	add hl,hl		ld b,1
	~~ex de~~,hl		ld a,e \ or l \ rra \ jr c,step2
	~~adc hl~~,hl		inc b
	or a		rr h \ rr l
	~~sbc hl~~,bc		rr d \ rr e
	jr c,$+3		ld a,e \ or l \ rra \ jr nc,$-12
	~~add hl,bc~~		ld a,e
	ex de,hl		and l
	~~dec~~ a		rra
	jr nz,~~GCDHL_BC~~+5		jr c,step3
	ld h,b		step2:
	~~ld l~~,c		bit 0,l \ jr z,$+3 \ ex de,hl
	~~ld b~~,d		xor a \ sbc hl,de \ jr nc,$+7 \ sub l \ ld l,a \ sbc a,a \ sub h \ ld h,a
	ld c,e		step3:
	ld a,d \ ~~or e~~		xor a \ sbc hl,de
	jr nz,~~GCDHL_BC~~		jr z,step4
	ret		jr nc,$+7 \ sub l \ ld l,a \ sbc a,a \ sub h \ ld h,a
			srl h \ rr l \ jr nc,$-4
			adc hl,hl
			jp step2
			step4:
			ex de,hl
			dec b
			ret z
			add hl,hl
			djnz $-1
			ret

	= Modulus =		= Modulus =

Xeda112358: /* Modulus */

2016-05-31T20:17:37Z

Modulus

@@ Line 1,159: / Line 1,159: @@
 = Modulus =
 == A_mod_3 ==
 Computes A mod 3 (essentially, the remainder of A after division by 3):
      ;Inputs:
      ;  A  unsigned integer
@@ Line 1,168: / Line 1,201: @@
      ;Destroys:
      ;  C
-     ; 19 bytes,  ~75cc (65 or 80)
+     ; 19 bytes,  65cc or 80cc, avg=76.25cc
          ld c,a                     ;add nibbles
          rrca / rrca / rrca / rrca
@@ Line 1,183: / Line 1,215: @@
          ret
 source: [https://www.cemetech.net/forum/viewtopic.php?p=249602#249602 Cemetech/Fast 8-bit mod 3]
@@ Line 1,281: / Line 1,228: @@
           djnz Loop
           ret
 = Random Numbers =

Xeda112358: /* B_Times_DE, 16-bit output */

2016-05-31T20:01:06Z

B_Times_DE, 16-bit output

← Older revision		Revision as of 20:01, 31 May 2016
Line 75:		Line 75:

	== B_Times_DE, 16-bit output ==		== B_Times_DE, 16-bit output ==
	This routine removes leading zeroes before finishing the multiplication, which take a little more code, but		This routine removes leading zeroes before finishing the multiplication, which take a little more code, but results in a faster average speed.
	~~This routine uses another clever way of optimizing for speed without unrolling. The result is slightly larger and~~ a ~~bit~~ faster. ~~The idea here is to remove leading zeros before multiplying.~~


	B_Times_DE:		B_Times_DE:

Xeda112358: /* BCDE_Times_A */

2016-05-31T19:49:26Z

BCDE_Times_A

← Older revision		Revision as of 19:49, 31 May 2016
Line 345:		Line 345:
	add ix,de \ adc hl,bc \ adc a,0		add ix,de \ adc hl,bc \ adc a,0
	ret		ret
	source: [http://pastebin.com/~~CsKUpZCm~~ Zeda's Pastebin/BCDE_Times_A]		source: [http://pastebin.com/yzFsHMqn Zeda's Pastebin/BCDE_Times_A]

	== H_Times_E ==		== H_Times_E ==

Xeda112358: /* DE_Div_BC */ changed to BC_Div_DE, faster, smaller.

2016-05-31T18:59:48Z

DE_Div_BC: changed to BC_Div_DE, faster, smaller.

@@ Line 530: / Line 530: @@
           ret
-== DE_Div_BC ==
+== BC_Div_DE ==
-This divides DE by BC, storing the result in DE, remainder in HL
+This divides BC by DE, storing the result in AC, remainder in HL
 == DEHL_Div_C ==

Xeda112358: /* DEHL_Mul_IXBC */ replaced with a better 32-bit multiplication routine

2016-05-31T18:41:31Z

DEHL_Mul_IXBC: replaced with a better 32-bit multiplication routine

← Older revision		Revision as of 18:41, 31 May 2016
Line 260:		Line 260:


	== ~~DEHL_Mul_IXBC~~ ==		== mul32, 64-bit output ==
	~~32-bit multiplication~~		With these sizes, we need to use RAM to hold intermediate values.
			'''mul16 needs to perform DE*BC => DEHL'''
	;***********		mul32:
	; RAM		;;uses karatsuba multiplication
	;***********		;;var_x * var_y
	~~;This uses Self Modifying Code~~ to ~~get a speed boost~~. ~~This must be~~		;;z0 holds the 64-bit result
	~~;used from RAM.~~		;;708cc+6a+13b+42c +3mul
	~~DEHL_Mul_IXBC~~:		;;Avg: 2464.110153
	;~~Inputs:~~		;;Max:2839cc, 92cc faster
	; ~~DEHL~~		;;Min:2178cc (early can make it faster, though), 167cc faster
	; ~~IXBC~~		ld de,(var_x) ;\
	;~~Outputs:~~		ld bc,(var_y) ; \|compute z0,z2
	; ~~AF is the return address~~		push bc ; \| var_y
	; ~~IXHLDEBC is~~ the result		call mul16 ; \|
	; ~~4 bytes at TempWord1 contain the upper 32-bits of the result~~		ld (var_z0),hl ; \|
	; ~~4 bytes at TempWord3 contain the value of the input stack values~~		ld bc,(var_y+2) ; \|
	;~~Comparison/Perspective~~:		ld (var_z0+2),de; \|
	; ~~At 6MHz~~, ~~this can be executed at the slowest more than 726~~		ld de,(var_x+2) ; \|
	; ~~times per second.~~		push bc ; \| var_y+2
	; ~~At 15MHz~~, ~~this can be executed at the slowest more than~~		call mul16 ; \|
	; ~~1815 times per second.~~		ld (var_z2),hl ; \|
	;~~===============================================================~~		ld (var_z2+2),de;/ 208cc
	ld (~~TempWord1~~),hl		xor a ;\
	ld (~~TempWord2~~),de		ld hl,(var_x) ; \|
	ld (~~TempWord3~~),bc		ld de,(var_x+2) ; \|
	ld (~~TempWord4~~),ix		add hl,de ; \|
	ld a~~,32~~		rra ; \|
	ld bc,0		pop de ; \|
	ld d,~~b \ ld e~~,b		ex (sp),hl ; \|
	~~Mult32StackLoop:~~		add hl,de ; \|
	~~sla c \ rl b \ rl e \ rl d~~		pop bc ; \|
	~~.db 21h~~ ;ld hl,**		ex de,hl ; \| 109cc
	~~TempWord1:~~		push de ; \|if bit0=1, add DE<<16 to result
	~~.dw 0~~		push bc ; \|
	~~adc hl~~,hl		push af ; \|c flag means add BC<<16 to result
	~~.db 21h~~ ;~~ld hl~~,**		call mul16 ; \|
	~~TempWord2:~~		ex de,hl ; \|
	~~.dw 0~~		pop af ; \|
	~~adc hl~~,hl		pop bc ; \|
	jr nc,~~OverFlowDone~~		jr nc,$+3 ; \| 86+6a
	~~.db 21h~~		add hl,bc ; \|
	~~TempWord3:~~		pop bc ; \|
	~~.dw 0~~		rla ; \|
	add hl,bc		jr nc,$+4 ; \| 26+13b
	~~ld b,h \ ld c,l~~		add hl,bc ; \|
	~~.db 21h~~		adc a,0 ; \|z1 = AHLDE-z2-z1
	~~TempWord4:~~		ex de,hl \ ld bc,(var_z0) \ sbc hl,bc
	~~.dw 0~~		ex de,hl \ ld bc,(var_z0+2) \ sbc hl,bc
	adc hl,de		sbc a,0
	ex de,hl		ex de,hl \ ld bc,(var_z2) \ sbc hl,bc
	~~jr nc~~,~~OverFlowDone~~		ex de,hl \ ld bc,(var_z2+2) \ sbc hl,bc
	ld hl,~~TempWord1~~		sbc a,0 ; \|z1 = AHLDE
	~~inc~~ (hl) \ ~~jr nz~~,~~OverFlowDone~~		ld b,h \ ld c,l ;/ z1 = ABCDE
	~~inc~~ hl \ ~~inc~~ (hl) \ ~~jr nz~~,~~OverFlowDone~~		ld hl,(var_z0+2);\
	~~inc~~ hl \ ~~inc~~ (hl) \ ~~jr nz~~,~~OverFlowDone~~		add hl,de ; \|Add:
	~~inc~~ hl ~~\ inc~~ (hl)		ld (var_z0+2),hl; \|z2z0
	~~OverFlowDone~~:		ld hl,(var_z2) ; \| z1
	~~dec a~~		adc hl,bc ; \|----
	~~jr nz~~,~~Mult32StackLoop~~		ld (var_z2),hl ; \|
	ld ~~ix,~~(~~TempWord2~~)		ret nc ; \| 279+42c
	ld hl,(~~TempWord1~~)		ld hl,(var_z2+2); \|
	ret		inc hl ; \|
			ld (var_z2+2),hl; \|
			ret ;/
			source [http://pastebin.com/PT3qqGFu Zeda's Pastebin/mul32]

	== BCDE_Times_A ==		== BCDE_Times_A ==

Xeda112358: /* BC_Times_DE, fully unrolled */

2016-05-31T18:40:42Z

BC_Times_DE, fully unrolled

← Older revision		Revision as of 18:40, 31 May 2016
Line 197:		Line 197:
	;Overall average: 78209011/131072=596.68740081787109375		;Overall average: 78209011/131072=596.68740081787109375
	;123 bytes		;123 bytes




	ld a,b		ld a,b
	ld hl,0		ld hl,0

Xeda112358: /* DEHL_Times_A */ changed to BCDE_Times_A, faster and smaller, clobbers fewer regs, doesn't mess with interrupts.

2016-05-31T18:34:51Z

DEHL_Times_A: changed to BCDE_Times_A, faster and smaller, clobbers fewer regs, doesn't mess with interrupts.

← Older revision		Revision as of 18:34, 31 May 2016
Line 329:		Line 329:


	== ~~DEHL_Times_A~~ ==		== BCDE_Times_A ==
			BCDE_Times_A:
	~~;===============================================================~~		;Inputs: BC:DE,A
	~~DEHL_Times_A~~:		;Outputs: A:HL:IX is the 40-bit product, BC,DE unaffected
	~~;===============================================================~~		;503cc~831cc
	;Inputs:		;667cc average
	~~; DEHL is a 32 bit factor~~		;29 bytes
	; A ~~is an 8 bit factor~~		ld ix,0
	;Outputs:		ld hl,0
	~~; interrupts disabled~~		call +_
	~~; BC is not changed~~		_:
	~~; AHLDE~~ is the 40-bit ~~result~~		call +_
	; ~~D'E' is the lower 16 bits of the input~~		_:
	; ~~H'L' is the lower 16 bits of the output~~		call +_
	; ~~B' is~~ 0		_:
	~~; C' is not changed~~		add ix,ix \ adc hl,hl \ rla \ ret nc
	~~; A' is not changed~~		add ix,de \ adc hl,bc \ adc a,0
	~~;===============================================================~~		ret
	di		source: [http://pastebin.com/CsKUpZCm Zeda's Pastebin/BCDE_Times_A]
	~~push hl~~
	~~or a~~
	~~sbc hl,hl~~
	~~exx~~
	~~pop de~~
	~~sbc hl,hl~~
	~~ld b,8~~
	~~mul32Loop~~:
	add hl,hl
	~~rl e~~ \ ~~rl d~~
	~~add a,a~~
	jr nc~~,$+8~~
	add hl,de
	~~exx~~
	adc hl,de
	~~inc~~ a
	~~exx~~
	~~djnz mul32Loop~~
	~~push hl~~
	~~exx~~
	~~pop de~~
	~~ret~~

	== H_Times_E ==		== H_Times_E ==

Xeda112358: /* D_Times_C */ removed redundant, poorly coded routine.

2016-05-31T18:16:57Z

D_Times_C: removed redundant, poorly coded routine.

← Older revision		Revision as of 18:16, 31 May 2016
Line 262:		Line 262:
	;308 is average speed.		;308 is average speed.
	;12 bytes		;12 bytes


	~~== D_Times_C ==~~
	~~This routine returns a 16-bit value with C as the overflow.~~


	~~;Returns a 16-bit result~~
	;
	~~;===============================================================~~
	~~D_Times_C:~~
	~~;===============================================================~~
	~~;Inputs:~~
	~~; D and C are factors~~
	~~;Outputs:~~
	~~; A is the product (lower 8 bits)~~
	~~; B is 0~~
	~~; C is the overflow (upper 8 bits)~~
	~~; DE, HL are not changed~~
	~~;Size: 15 bytes~~
	~~;Speed: 312+12z-y~~
	~~; See Speed Summary below~~
	~~;===============================================================~~
	~~xor a ;This is an optimised way to set A to zero. 4 cycles, 1 byte.~~
	~~ld b,8 ;Number of bits in E, so number of times we will cycle through~~
	~~Loop:~~
	~~add a,a ;We double A, so we shift it left. Overflow goes into the c flag.~~
	~~rl c ;Rotate overflow in and get the next bit of C in the c flag~~
	~~jr nc,$+6 ;If it is 0, we don't need to add anything to A~~
	~~add a,d ;Since it was 1, we do A+1*D~~
	~~jr nc,$+3 ;Check if there was overflow~~
	~~inc c ;If there was overflow, we need to increment E~~
	~~djnz Loop ;Decrements B, if it isn't zero yet, jump back to Loop:~~
	~~ret~~



	~~;Speed Summary~~
	~~; xor a ; 4~~
	~~; ld b,8 ; 7~~
	~~;Loop: ;~~
	~~; add a,a ; 32~~
	~~; rl c ; 64~~
	~~; jr nc,$+6 ; 96+12z-y z=number of bits in C, y is overflow, so at most one less than z~~
	~~; add a,d ; --~~
	~~; jr nc,$+3 ; --~~
	~~; inc c ; --~~
	~~; djnz Loop ; 99~~
	~~; ret ; 10~~
	;
	~~;312+12z-y~~
	~~; z is the number of bits in C~~
	~~; y is the number of overflows in the branch. This is at most z-1.~~
	~~;Max: 415 cycles~~