/* * Division and remainder, from Appendix E of the Sparc Version 8 * Architecture Manual, with fixes from Gordon Irlam. *//* * Input: dividend and divisor in %o0 and %o1 respectively. * * m4 parameters: *  NAME	name of function to generate *  OP		OP=div => %o0 / %o1; OP=rem => %o0 % %o1 *  S		S=true => signed; S=false => unsigned * * Algorithm parameters: *  N		how many bits per iteration we try to get (4) *  WORDSIZE	total number of bits (32) * * Derived constants: *  TOPBITS	number of bits in the top `decade' of a number * * Important variables: *  Q		the partial quotient under development (initially 0) *  R		the remainder so far, initially the dividend *  ITER	number of main division loop iterations required; *		equal to ceil(log2(quotient) / N).  Note that this *		is the log base (2^N) of the quotient. *  V		the current comparand, initially divisor*2^(ITER*N-1) * * Cost: *  Current estimate for non-large dividend is *	ceil(log2(quotient) / N) * (10 + 7N/2) + C *  A large dividend is one greater than 2^(31-TOPBITS) and takes a *  different path, as the upper bits of the quotient must be developed *  one bit at a time. */define(N, `4')dnldefine(WORDSIZE, `32')dnldefine(TOPBITS, eval(WORDSIZE - N*((WORDSIZE-1)/N)))dnldnldefine(dividend, `%o0')dnldefine(divisor, `%o1')dnldefine(Q, `%o2')dnldefine(R, `%o3')dnldefine(ITER, `%o4')dnldefine(V, `%o5')dnldnldnl m4 reminder: ifelse(a,b,c,d) => if a is b, then c, else ddefine(T, `%g1')dnldefine(SC, `%g2')dnlifelse(S, `true', `define(SIGN, `%g3')')dnldnldnl This is the recursive definition for developing quotient digits.dnldnl Parameters:dnl  $1	the current depth, 1 <= $1 <= Ndnl  $2	the current accumulation of quotient bitsdnl  N	max depthdnldnl We add a new bit to $2 and either recurse or insert the bits indnl the quotient.  R, Q, and V are inputs and outputs as defined above;dnl the condition codes are expected to reflect the input R, and arednl modified to reflect the output R.dnldefine(DEVELOP_QUOTIENT_BITS,`	! depth $1, accumulated bits $2	bl	LOC($1.eval(2**N+$2))	srl	V,1,V	! remainder is positive	subcc	R,V,R	ifelse($1, N,	`	b	9f		add	Q, ($2*2+1), Q	', `	DEVELOP_QUOTIENT_BITS(incr($1), `eval(2*$2+1)')')LOC($1.eval(2**N+$2)):	! remainder is negative	addcc	R,V,R	ifelse($1, N,	`	b	9f		add	Q, ($2*2-1), Q	', `	DEVELOP_QUOTIENT_BITS(incr($1), `eval(2*$2-1)')')	ifelse($1, 1, `9:')')dnl#include <sysdep.h>#include <sys/trap.h>ENTRY(NAME)ifelse(S, `true',`	! compute sign of result; if neither is negative, no problem	orcc	divisor, dividend, %g0	! either negative?	bge	2f			! no, go do the divideifelse(OP, `div',`	xor	divisor, dividend, SIGN	! compute sign in any case',`	mov	dividend, SIGN		! sign of remainder matches dividend')	tst	divisor	bge	1f	tst	dividend	! divisor is definitely negative; dividend might also be negative	bge	2f			! if dividend not negative...	sub	%g0, divisor, divisor	! in any case, make divisor nonneg1:	! dividend is negative, divisor is nonnegative	sub	%g0, dividend, dividend	! make dividend nonnegative2:')	! Ready to divide.  Compute size of quotient; scale comparand.	orcc	divisor, %g0, V	bne	1f	mov	dividend, R		! Divide by zero trap.  If it returns, return 0 (about as		! wrong as possible, but that is what SunOS does...).		ta	ST_DIV0		retl		clr	%o01:	cmp	R, V			! if divisor exceeds dividend, done	blu	LOC(got_result)		! (and algorithm fails otherwise)	clr	Q	sethi	%hi(1 << (WORDSIZE - TOPBITS - 1)), T	cmp	R, T	blu	LOC(not_really_big)	clr	ITER	! `Here the dividend is >= 2**(31-N) or so.  We must be careful here,	! as our usual N-at-a-shot divide step will cause overflow and havoc.	! The number of bits in the result here is N*ITER+SC, where SC <= N.	! Compute ITER in an unorthodox manner: know we need to shift V into	! the top decade: so do not even bother to compare to R.'	1:		cmp	V, T		bgeu	3f		mov	1, SC		sll	V, N, V		b	1b		add	ITER, 1, ITER	! Now compute SC.	2:	addcc	V, V, V		bcc	LOC(not_too_big)		add	SC, 1, SC		! We get here if the divisor overflowed while shifting.		! This means that R has the high-order bit set.		! Restore V and subtract from R.		sll	T, TOPBITS, T	! high order bit		srl	V, 1, V		! rest of V		add	V, T, V		b	LOC(do_single_div)		sub	SC, 1, SC	LOC(not_too_big):	3:	cmp	V, R		blu	2b		nop		be	LOC(do_single_div)		nop	/* NB: these are commented out in the V8-Sparc manual as well */	/* (I do not understand this) */	! V > R: went too far: back up 1 step	!	srl	V, 1, V	!	dec	SC	! do single-bit divide steps	!	! We have to be careful here.  We know that R >= V, so we can do the	! first divide step without thinking.  BUT, the others are conditional,	! and are only done if R >= 0.  Because both R and V may have the high-	! order bit set in the first step, just falling into the regular	! division loop will mess up the first time around.	! So we unroll slightly...	LOC(do_single_div):		subcc	SC, 1, SC		bl	LOC(end_regular_divide)		nop		sub	R, V, R		mov	1, Q		b	LOC(end_single_divloop)		nop	LOC(single_divloop):		sll	Q, 1, Q		bl	1f		srl	V, 1, V		! R >= 0		sub	R, V, R		b	2f		add	Q, 1, Q	1:	! R < 0		add	R, V, R		sub	Q, 1, Q	2:	LOC(end_single_divloop):		subcc	SC, 1, SC		bge	LOC(single_divloop)		tst	R		b,a	LOC(end_regular_divide)LOC(not_really_big):1:	sll	V, N, V	cmp	V, R	bleu	1b	addcc	ITER, 1, ITER	be	LOC(got_result)	sub	ITER, 1, ITER	tst	R	! set up for initial iterationLOC(divloop):	sll	Q, N, Q	DEVELOP_QUOTIENT_BITS(1, 0)LOC(end_regular_divide):	subcc	ITER, 1, ITER	bge	LOC(divloop)	tst	R	bl,a	LOC(got_result)	! non-restoring fixup here (one instruction only!)ifelse(OP, `div',`	sub	Q, 1, Q', `	add	R, divisor, R')LOC(got_result):ifelse(S, `true',`	! check to see if answer should be < 0	tst	SIGN	bl,a	1f	ifelse(OP, `div', `sub %g0, Q, Q', `sub %g0, R, R')1:')	retl	ifelse(OP, `div', `mov Q, %o0', `mov R, %o0')END(NAME)