;
; divide.s
;
; Various routines of a division-related nature (MDW/TMA)
;
;  1994-1998 Straylight
;

;----- Licensing note -------------------------------------------------------
;
; This file is part of Straylight's Sapphire library.
;
; Sapphire is free software; you can redistribute it and/or modify
; it under the terms of the GNU General Public License as published by
; the Free Software Foundation; either version 2, or (at your option)
; any later version.
;
; Sapphire is distributed in the hope that it will be useful,
; but WITHOUT ANY WARRANTY; without even the implied warranty of
; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
; GNU General Public License for more details.
;
; You should have received a copy of the GNU General Public License
; along with Sapphire.  If not, write to the Free Software Foundation,
; 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

;----- Standard header ------------------------------------------------------

		GET	libs:header
		GET	libs:swis

;----- Simple mathematics ---------------------------------------------------

		AREA	|Sapphire$$Code|,CODE,READONLY

; --- divide ---
;
; On entry:	R0 == dividend
; 		R1 == divisor
;
; On exit:	R0 == quotient
;		R1 == remainder
;
; Use:		A standard divide routine.  Fairly speedy, hopefully.
;		The results are always such that
;
;			|quotient| <= |(divisor/dividend)|,
;
;			|remainder| < |divisor|
;
;		and
;
;			quotient * divisor + remainder == dividend

		EXPORT	divide
divide		ROUT

		STMFD	R13!,{R2,R14}		;Save some registers

		; --- First, mess about with the signs ---

		ANDS	R2,R0,#&80000000	;Get the dividend's sign bit
		ORR	R2,R2,R2,LSR #1		;Copy -- this is sign of mod
		RSBNE	R0,R0,#0		;Take absolute value of R0
		ANDS	R14,R1,#&80000000	;Get the divisor's sign too
		RSBNE	R1,R1,#0		;Take absolute value of R1
		EOR	R2,R2,R14		;Calculate sign of quotient

		; --- Now do the division ---

		BL	div_unsigned		;That's done for us elsewhere

		; --- Now tidy everything up ---

		TST	R2,#&40000000		;Is remainder to be negative?
		RSBNE	R1,R1,#0		;Yes -- negate it
		TST	R2,#&80000000		;Is quotient to be negative?
		RSBNE	R0,R0,#0		;Yes -- negate it

		LDMFD	R13!,{R2,PC}^		;Return to caller

		LTORG

; --- div_unsigned ---
;
; On entry:	R0 == dividend
; 		R1 == divisor
;
; On exit:	R0 == quotient
;		R1 == remainder
;
; Use:		As for divide, except that it considers its operands to be
;		unsigned.

		EXPORT	div_unsigned
		EXPORT	div_byZero
div_unsigned	ROUT

		CMP	R1,#0			;Check for divide by zero
		BEQ	div_byZero		;Yes -- make the error
		STMFD	R13!,{R2,R3,R14}	;Save some registers

		; --- A note about the method ---
		;
		; We use traditional long division, but unroll the loop a
		; lot to keep the thing ticking over at a good rate.

		MOV	R14,R1			;Look after the divisor
		ANDS	R3,R0,#&80000000	;Is the top dividend bit set?
		MOVEQ	R3,R0			;No -- use the real thing

		; --- Shift divisor up for long division ---
		;
		; We keep shifting the divisor up until it's greater than
		; the dividend, and then we skip ahead to the divide section

		MOV	R2,#0			;Quotient starts off at 0
00div_unsigned	CMP	R3,R14,LSL #0
		BLS	%10div_unsigned
		CMP	R3,R14,LSL #1
		BLS	%11div_unsigned
		CMP	R3,R14,LSL #2
		BLS	%12div_unsigned
		CMP	R3,R14,LSL #3
		BLS	%13div_unsigned
		CMP	R3,R14,LSL #4
		BLS	%14div_unsigned
		CMP	R3,R14,LSL #5
		BLS	%15div_unsigned
		CMP	R3,R14,LSL #6
		BLS	%16div_unsigned
		CMP	R3,R14,LSL #7
		MOVHI	R14,R14,LSL #8
		BHI	%00div_unsigned

		; --- Now we have the shift-down loop ---
		;
		; This is where the actual job of dividing is performed.
		; We shift the divisor back down until it's back where we
		; started again.

17div_unsigned	CMP	R0,R14,LSL #7
		ADC	R2,R2,R2
		SUBCS	R0,R0,R14,LSL #7
16div_unsigned	CMP	R0,R14,LSL #6
		ADC	R2,R2,R2
		SUBCS	R0,R0,R14,LSL #6
15div_unsigned	CMP	R0,R14,LSL #5
		ADC	R2,R2,R2
		SUBCS	R0,R0,R14,LSL #5
14div_unsigned	CMP	R0,R14,LSL #4
		ADC	R2,R2,R2
		SUBCS	R0,R0,R14,LSL #4
13div_unsigned	CMP	R0,R14,LSL #3
		ADC	R2,R2,R2
		SUBCS	R0,R0,R14,LSL #3
12div_unsigned	CMP	R0,R14,LSL #2
		ADC	R2,R2,R2
		SUBCS	R0,R0,R14,LSL #2
11div_unsigned	CMP	R0,R14,LSL #1
		ADC	R2,R2,R2
		SUBCS	R0,R0,R14,LSL #1
10div_unsigned	CMP	R0,R14,LSL #0
		ADC	R2,R2,R2
		SUBCS	R0,R0,R14,LSL #0

		CMP	R14,R1			;Have we finished dividing?
		MOVHI	R14,R14,LSR #8		;No -- shift down a byte
		BHI	%17div_unsigned		;And loop round again

		; --- Now tidy everything up ---

		MOV	R1,R0			;Copy results into registers
		MOV	R0,R2

		LDMFD	R13!,{R2,R3,PC}^	;Return to caller

div_byZero	ADR	R0,divByZero
		SWI	OS_GenerateError

divByZero	DCD	1
		DCB	"Division by zero",0

		LTORG

; --- div10 ---
;
; On entry:	R0 == integer to divide
;
; On exit:	R0 == quotient after division by 10
;		R1 == remainder after division by 10
;
; Use:		Divides an integer very quickly by 10.
;
; [Generated by Straylight divc]

		EXPORT	div10
div10		ROUT

		STMFD	R13!,{R2,R14}
		MOVS	R2,R0
		RSBMI	R0,R0,#0
		MOV	R1,R0

		ADD	R0,R0,R0,LSR #1
		ADD	R0,R0,R0,LSR #4
		ADD	R0,R0,R0,LSR #8
		ADD	R0,R0,R0,LSR #16

		MOV	R0,R0,LSR #4

		ADD	R14,R0,R0,LSL #2
		SUB	R1,R1,R14,LSL #1
		SUBS	R1,R1,#10
		ADDGE	R0,R0,#1
		ADDLT	R1,R1,#10

		CMP	R2,#0
		RSBMI	R0,R0,#0
		RSBMI	R1,R1,#0
		LDMFD	R13!,{R2,PC}^

		LTORG

; --- div_round ---
;
; On entry:	R0 == dividend
;		R1 == divisor
;
; On exit:	R0 == quotient, rounded to nearest integer
;		R1 == remainder
;
; Use:		Calculates a rounded-to-nearest quotient, rather than one
;		rounded towards zero, which is what divide returns you.
;
;		The remainder is fiddled during this process, so that the
;		properties
;
;			quotient * divisor + remainder == dividend
;
;		and
;
;			|remainder| < |divisor|
;
;		still hold (so the remainder's sign may well change).

		EXPORT	div_round
div_round	ROUT

		STMFD	R13!,{R2,R14}		;Save some registers
		MOV	R2,R0			;Keep a copy of the dividend
		CMP	R1,#0			;Is the divisor positive?
		MOVGE	R14,R1			;Yes -- just copy it
		RSBLT	R14,R1,#0		;No -- negate it on the way
		CMP	R0,#0			;Is the dividend positive?
		ADDGE	R0,R0,R14,ASR #1	;Yes -- add half the divisor
		SUBLT	R0,R0,R14,ASR #1	;No -- subtract it
		SUB	R2,R2,R0		;Remember this difference
		BL	divide			;Do the division
		ADD	R1,R1,R2		;Modify remainder suitably
		LDMFD	R13!,{R2,PC}^		;Return to caller

		LTORG

; --- div_u64x32 ---
;
; On entry:	R0,R1 == dividend (high word in R1)
;		R2 == divisor
;
; On exit:	R0 == quotient
;		R1 == remainder
;
; Use:		Divides a 64-bit unsigned value by a 32-bit unsigned value
;		yielding 32-bit unsigned quotient and remainder.  If there
;		are more than 32 bits of quotient, the return values are
;		undefined.

		EXPORT	div_u64x32
div_u64x32	ROUT

		STMFD	R13!,{R14}		;Save the link register

		MOV	R14,#8			;Initialise the loop counter

00div_u64x32

		GBLA	count
count		SETA	4

		WHILE	count>0

		CMP	R1,R2			;Can we subtract here?
		SUBCS	R1,R1,R2		;Yes -- do that then
		ADCS	R0,R0,R0		;Shift up quotient/dividend
		ADC	R1,R1,R1		;Put next dividend bit in R1

count		SETA	count-1
		WEND

		SUBS	R14,R14,#1		;Decrement loop counter
		BGT	%00div_u64x32		;If more to do, loop round

		CMP	R1,R2			;Can we subtract here?
		SUBCS	R1,R1,R2		;Yes -- do that then
		ADCS	R0,R0,R0		;Shift up quotient

		LDMFD	R13!,{PC}^		;And return to caller

		LTORG

;----- That's all, folks ----------------------------------------------------

		END
