6809_MPDDIV.s

	.macro	CLC
		ANDCC	#$FE
	.endm
	.macro	SEC
		ORCC	#1
	.endm

;	Title:			Multiple-precision Decimal Division
;	Name:			MPDDIV
;
;	Purpose:		Divide 2 arrays of BCD bytes
;				Quotient := Dividend / divisor
;
;	Entry:
;				TOP OF STACK 
;				High byte of return address
;				Low  byte of return address
;				Length of operands in bytes 
;				High byte of divisor address 
;				Low  byte of divisor address
;				High byte of dividend address 
;				Low  byte of dividend address
;
;				The arrays are unsigned BCD numbers
;				with a maximum length of 255 bytes,
;				ARRAY[0] is the least significant byte, and
;				ARRAY[LENGTH-1] is the most significant byte.
;
;	Exit:
;				Dividend := dividend / divisor
;
;				If no errors then
;					Carry 0
;					Dividend unchanged
;					remainder 0
;
;	Registers Used:
;				All
;
;	Time:
;				Assuming the average digit value in the
;				quotient is 5, then the time is approximately 
;				(410 * length^2) + (750 * Length) + 150 cycles
;
;	Size:
;				Program	169 bytes
;				Data	510 bytes plus 3 stack bytes
;
;	CHECK LENGTH OF OPERANDS
;	EXIT WITH CARRY CLEARED IF LENGTH IS ZERO
;
MPDDIV:
	CLC			; CLEAR CARRY IN CASE OF ZERO LENGTH
	LDB	2,S		; GET LENGTH OF OPERANDS
	LBEQ	EXITDV		; BRANCH (EXIT) IF LENGTH IS ZERO
;
;	SET UP HIGH DIVIDEND AND DIFFERENCE POINTERS
;	CLEAR HIGH DIVIDEND AND DIFFERENCE ARRAYS
;
;	ARRAYS 1 AND 2 ARE USED INTERCHANGEABLY FOR THESE TWO PURPOSES.
;	THE POINTERS ARE SWITCHED WHENEVER A TRIAL SUBTRACTION SUCCEEDS
;
;	THE POINTERS ARE SWITCHED WHENEVER A
;	TRIAL SUBTRACTION SUCCEEDS
;
	LDX	#HIDE1		; GET BASE ADDRESS OF ARRAY 1
	STX	HDEPTR		; DIVIDEND POINTER = ARRAY 1
	LDU	#HIDE2		; GET BASE ADDRESS OF ARRAY 2
	STU	DIFPTR		; DIVIDEND POINTER = ARRAY 2
	CLRA			; GET ZERO FOR CLEARING ARRAYS
CLRHI:
	STA	,X+		; CLEAR BYTE OF ARRAY 1
	STA	,U+		; CLEAR BYTE OF ARRAY 2
	DECB
	BNE	CLRHI		; CONTINUE THROUGH ALL BYTES
;
; CHECK WHETHER DIVISOR IS ZERO
; EXIT WITH CARRY SET IF IT IS
;
	LDB	2,S		; GET LENGTH OF OPERANDS
	LDX	3,S		; GET BASE ADDRESS OF DIVISOR
CHKZRO:
	LDA	,X+		; EXAMINE BYTE OF DIVISOR
	BNE	NINESC		; BRANCH IF BYTE IS NOT ZERO
	DECB			; CONTINUE THROUGH ALL BYTES
	BNE	CHKZRO
	SEC			; ALL BYTES ARE ZERO INDICATE
				; DIVIDE-BY-ZERO ERROR
	BRA	EXITDV		; EXIT
;
; TAKE NINES COMPLEMENT OF DIVISOR TO SIMPLIFY SUBTRACTION
;
NINESC:
	LDB	2,S		; GET LENGTH OF OPERANDS
	LDX	3,S		; POINT TO DIVISOR
NINESB:
	LDA	#$99		; TAKE NINES COMPLEMENT OF EACH BYTE
	SUBA	,X		; 
	STA	,X+		; 
	DECB			; CONTINUE THROUGH ALL BYTES
	BNE	NINESB		; 
;
;	SET COUNT TO NUMBER OF DIGITS PLUS 1
;	COUNT := LENGTH * 2 + 1
;
	LDB	2,S		; GET LENGTH OF OPERANDS
	CLRA			; EXTEND LENGTH TO 16 BITS
	ASLB			; MULTIPLY LENGTH TIMES 2
	ROLA
	ADDD	#1		; 2 * LENGTH + 1
	PSHS	D		; SAVE DIGIT COUNT ON STACK
	CLR	,-S		; SAVE TENS COUNT ON STACK
;
;	SET UP FOR DIGIT SHIFT
;
DIGSET:
	LDY	1,S		; GET DIGIT COUNT
	LEAY	-1,Y		; DECREMENT DIGIT COUNT
	STY	1,S		; SAVE DECREMENTED DIGIT COUNT

	BEQ	CHKTNS		; BRANCH IF ALL DIGITS DONE
	LDA	#4		; FOUR BITS PER DIGIT
;
; DIGIT SHIFT
;
DIGSHF:
	LDX	8,S		; POINT TO DIVIDEND
	LSL	,S		; SHIFT HIGH BIT INTO CARRY
	LDB	5,S		; GET LENGTH OF OPERANDS
;
; SHIFT QUOTIENT AND LOWER DIVIDEND LEFT ONE BIT
;
SHFTQU:
	ROL	,X+		; SHIFT BYTE OF QUOTIENT/DIVIDEND LEFT 
	DECB			; CONTINUE THROUGH ALL BYTES
	BNE	SHFTQU		
;
; SHIFT UPPER DIVIDEND LEFT WITH CARRY FROM LOWER DIVIDEND
;
SHFTUP:
	LDX	HDEPTR		; POINT TO BASE ADDRESS OF UPPER DIVIDEND
	LDB	5,S		; GET LENGTH OF OPERANDS

	ROL	,X+		; SHIFT BYTE OF UPPER DIVIDEND LEFT 
	DECB			; CONTINUE THROUGH ALL BYTES
	BNE	SHFTUP
	DECA			; DECREMENT DIGIT BIT COUNT 
	BNE	DIGSHF		; LOOP UNTIL DONE
;
;	PERFORM DIVISION BY TRIAL SUBTRACTIONS
;	KEEP REMAINDER IN CASE IT IS NEEDED LATER
;	FINAL CARRY IS AN INVERTED BORROW
;
	CLR	,S			; TENS COUNTER 0	
SETSUB:
	LDU	DIFPTR			; POINT TO DIFFERENCE
	LDX	HDEPTR			; POINT TO UPPER DIVIDEND
	LDY	6,S 			; POINT TO DIVISOR
	LDB	5,S			; GET LENGTH OF OPERANDS IN BYTES
	SEC				; SET INVERTED BORROW INITIALLY
					; TO FORM 10'S COMPLEMENT
SUBDVS:
	LDA	,X+			; GET BYTE OF HIGH DIVIDEND
	ADCA	,Y+			; SUBTRACT BYTE OF DIVISOR BY ADDING
					; BYTE OF NINE'S COMPLEMENT
	DAA				; MAKE DIFFERENCE DECIMAL
	STA	,U+			; SAVE DIFFERENCE			
	DECB				; CONTINUE THROUGH ALL BYTES
	BNE	SUBDVS
;
;	IF DIFFERENCE IS POSITIVE (CARRY SET),
;	REPLACE HIGH DIVIDEND WITH
;	DIFFERENCE AND ADD 10 TO 10'S COUNT
;
	BCC	DIGSET			; BRANCH IF DIFFERENCE IS NEGATIVE
	LDX	HDEPTR			; GET HIGH DIVIDEND POINTER
	LDU	DIFPTR			; GET DIFFERENCE POINTER
	STU	HDEPTR			; NEW HIGH DIVIDEND = DIFFERENCE
	STX	DIFPTR		; USE OLD HIGH DIVIDEND FOR NEXT DIFFERENCE
	LDA	#$10		; ADD 10
	ADDA	,S
	STA	,S		; SAVE SUM ON STACK
	BRA	SETSUB		; CONTINUE WITH TRIAL SUBTRACTIONS
;
;	DO LAST SHIFT IF TENS COUNT IS NOT ZERO
;
CHKTNS:
	LDA	,S		; GET TENS COUNT
	LEAS	3,S		; REMOVE TEMPORARIES FROM STACK
	BEQ	GOODRT		; BRANCH IF TENS COUNT IS ZERO
	PSHS	A		; SAVE TENS COUNT
	LDA	#4		; 4 BIT SHIFT TO MOVE DIGIT
CSHIFT:
	LDX	6,S		; POINT TO QUOTIENT
	LDB	3,S		; GET LENGTH OF OPERANDS
	LSL	,S		; SHIFT TENS COUNT INTO CARRY
LSTSHF:
	ROL	,X+		; SHIFT QUOTIENT LEFT 1 BIT
	DECB			; CONTINUE THROUGH ALL BYTES
	BNE	LSTSHF
	DECA			; CONTINUE THROUGH 4 BIT SHIFT
	BNE	CSHIFT
	LEAS	1,S		; REMOVE TEMPORARY STORAGE FROM STACK
GOODRT:
	CLC			; CLEAR CARRY FOR GOOD RETURN
;
; REMOVE PARAMETERS FROM STACK AND EXIT
;
EXITDV:
	LDX	HDEPTR		; GET BASE ADDRESS OF REMAINDER
	LDY	,S		; SAVE RETURN ADDRESS
	LDA	7,S		; REMOVE PARAMETERS FROM STACK
	JMP	,U		; EXIT TO RETURN ADDRESS
DVEXIT:
;
; DATA
;
HDEPTR:	RMB	2		; POINTER TO HIGH DIVIDEND
DIFPTR:	RMB	2		; POINTER TO DIFFERENCE BETWEEN HIGH
				; DIVIDEND AND DIVISOR
HIDE1:	RMB	255		; HIGH DIVIDEND BUFFER 1
HIDE2:	RMB	255		; HIGH DIVIDEND BUFFER 2
;
;
; SAMPLE EXECUTION
;
;
SC3K:	
	LDX	AY1ADR		; GET DIVIDEND	
	LDY	AY2ADR		; GET DIVISOR	
	LDA	#SZAYS		; LENGTH OF ARRAYS IN BYTES	
	PSHS	A,X,Y		; SAVE PARAMETERS IN STACK 	
	JSR	MPDDIV		; MULTIPLE-PRECISION BINARY DIVISION
				; RESULT OF 3822756 / 1234 = 3097
				; IN MEMORY
				;	AY1	= 97H
				;	AY1+1	= 30H
				;	AY1+2	= 00H
				;	AY1+3	= 00H
				;	AY1+4	= 00H
				;	AY1+5	= 00H
				;	AY1+6	= 00H
	BRA	SC3K		; REPEAT TEST

SZAYS	EQU	7		; LENGTH OF ARRAYS IN BYTES
AY1ADR	FDB	AY1		; BASE ADDRESS OF ARRAY 1 (DIVIDEND)
AY2ADR	FDB	AY2		; BASE ADDRESS OF ARRAY 2 (DIVISOR)
AY1:	FCB	$56,$27,$82,$03,0,0,0,0
AY2:	FCB	$34,$12,0,0,0,0,0,0
	END