1/*
2 * Copyright (c) 1992, 1993
3 *	The Regents of the University of California.  All rights reserved.
4 *
5 * This software was developed by the Computer Systems Engineering group
6 * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and
7 * contributed to Berkeley.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 *    notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 *    notice, this list of conditions and the following disclaimer in the
16 *    documentation and/or other materials provided with the distribution.
17 * 3. Neither the name of the University nor the names of its contributors
18 *    may be used to endorse or promote products derived from this software
19 *    without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33
34#include <machine/asm.h>
35
36RCSID("$MirOS: src/kern/c/sparc/divrem.m4,v 1.2 2008/10/18 17:45:50 tg Exp $")
37RCSID("@(#)divrem.m4	8.1 (Berkeley) 6/4/93")
38
39	.text
40
41/*
42 * Division and remainder, from Appendix E of the Sparc Version 8
43 * Architecture Manual, with fixes from Gordon Irlam.
44 */
45
46/*
47 * Input: dividend and divisor in %o0 and %o1 respectively.
48 *
49 * m4 parameters:
50 *  NAME	name of function to generate
51 *  NAME2	secondary name of function to generate
52 *  OP		OP=div => %o0 / %o1; OP=rem => %o0 % %o1
53 *  S		S=true => signed; S=false => unsigned
54 *
55 * Algorithm parameters:
56 *  N		how many bits per iteration we try to get (4)
57 *  WORDSIZE	total number of bits (32)
58 *
59 * Derived constants:
60 *  TWOSUPN	2^N, for label generation (m4 exponentiation currently broken)
61 *  TOPBITS	number of bits in the top `decade' of a number
62 *
63 * Important variables:
64 *  Q		the partial quotient under development (initially 0)
65 *  R		the remainder so far, initially the dividend
66 *  ITER	number of main division loop iterations required;
67 *		equal to ceil(log2(quotient) / N).  Note that this
68 *		is the log base (2^N) of the quotient.
69 *  V		the current comparand, initially divisor*2^(ITER*N-1)
70 *
71 * Cost:
72 *  Current estimate for non-large dividend is
73 *	ceil(log2(quotient) / N) * (10 + 7N/2) + C
74 *  A large dividend is one greater than 2^(31-TOPBITS) and takes a
75 *  different path, as the upper bits of the quotient must be developed
76 *  one bit at a time.
77 */
78
79define(N, `4')
80define(TWOSUPN, `16')
81define(WORDSIZE, `32')
82define(TOPBITS, eval(WORDSIZE - N*((WORDSIZE-1)/N)))
83
84define(dividend, `%o0')
85define(divisor, `%o1')
86define(Q, `%o2')
87define(R, `%o3')
88define(ITER, `%o4')
89define(V, `%o5')
90
91/* m4 reminder: ifelse(a,b,c,d) => if a is b, then c, else d */
92define(T, `%g1')
93define(SC, `%g7')
94ifelse(S, `true', `define(SIGN, `%g6')')
95
96/*
97 * This is the recursive definition for developing quotient digits.
98 *
99 * Parameters:
100 *  $1	the current depth, 1 <= $1 <= N
101 *  $2	the current accumulation of quotient bits
102 *  N	max depth
103 *
104 * We add a new bit to $2 and either recurse or insert the bits in
105 * the quotient.  R, Q, and V are inputs and outputs as defined above;
106 * the condition codes are expected to reflect the input R, and are
107 * modified to reflect the output R.
108 */
109define(DEVELOP_QUOTIENT_BITS,
110`	! depth $1, accumulated bits $2
111	bl	L.$1.eval(TWOSUPN+$2)
112	srl	V,1,V
113	! remainder is positive
114	subcc	R,V,R
115	ifelse($1, N,
116	`	b	9f
117		 add	Q, ($2*2+1), Q
118	', `	DEVELOP_QUOTIENT_BITS(incr($1), `eval(2*$2+1)')')
119L.$1.eval(TWOSUPN+$2):
120	! remainder is negative
121	addcc	R,V,R
122	ifelse($1, N,
123	`	b	9f
124		 add	Q, ($2*2-1), Q
125	', `	DEVELOP_QUOTIENT_BITS(incr($1), `eval(2*$2-1)')')
126	ifelse($1, 1, `9:')')
127
128#include <machine/asm.h>
129#include <machine/trap.h>
130
131#ifdef _KERNEL
132	.globl NAME2
133NAME2:
134#endif
135#ifndef STRONG_SPARC
136.weak NAME
137#else
138FUNC(patsubst(NAME,\.,__))
139#endif
140FUNC(NAME)
141ifelse(S, `true',
142`	! compute sign of result; if neither is negative, no problem
143	orcc	divisor, dividend, %g0	! either negative?
144	bge	2f			! no, go do the divide
145	ifelse(OP, `div',
146		`xor	divisor, dividend, SIGN',
147		`mov	dividend, SIGN')	! compute sign in any case
148	tst	divisor
149	bge	1f
150	tst	dividend
151	! divisor is definitely negative; dividend might also be negative
152	bge	2f			! if dividend not negative...
153	neg	divisor			! in any case, make divisor nonneg
1541:	! dividend is negative, divisor is nonnegative
155	neg	dividend		! make dividend nonnegative
1562:
157')
158	! Ready to divide.  Compute size of quotient; scale comparand.
159	orcc	divisor, %g0, V
160	bnz	1f
161	mov	dividend, R
162
163		! Divide by zero trap.  If it returns, return 0 (about as
164		! wrong as possible, but that is what SunOS does...).
165		t	ST_DIV0
166		retl
167		 clr	%o0
168
1691:
170	cmp	R, V			! if divisor exceeds dividend, done
171	blu	Lgot_result		! (and algorithm fails otherwise)
172	clr	Q
173	sethi	%hi(1 << (WORDSIZE - TOPBITS - 1)), T
174	cmp	R, T
175	blu	Lnot_really_big
176	 clr	ITER
177
178	! `Here the dividend is >= 2^(31-N) or so.  We must be careful here,
179	! as our usual N-at-a-shot divide step will cause overflow and havoc.
180	! The number of bits in the result here is N*ITER+SC, where SC <= N.
181	! Compute ITER in an unorthodox manner: know we need to shift V into
182	! the top decade: so do not even bother to compare to R.'
183	1:
184		cmp	V, T
185		bgeu	3f
186		 mov	1, SC
187		sll	V, N, V
188		b	1b
189		 inc	ITER
190
191	! Now compute SC.
192	2:	addcc	V, V, V
193		bcc	Lnot_too_big
194		 inc	SC
195
196		! We get here if the divisor overflowed while shifting.
197		! This means that R has the high-order bit set.
198		! Restore V and subtract from R.
199		sll	T, TOPBITS, T	! high order bit
200		srl	V, 1, V		! rest of V
201		add	V, T, V
202		b	Ldo_single_div
203		 dec	SC
204
205	Lnot_too_big:
206	3:	cmp	V, R
207		blu	2b
208		 nop
209		be	Ldo_single_div
210		 nop
211	/* NB: these are commented out in the V8-Sparc manual as well */
212	/* (I do not understand this) */
213	! V > R: went too far: back up 1 step
214	!	srl	V, 1, V
215	!	dec	SC
216	! do single-bit divide steps
217	!
218	! We have to be careful here.  We know that R >= V, so we can do the
219	! first divide step without thinking.  BUT, the others are conditional,
220	! and are only done if R >= 0.  Because both R and V may have the high-
221	! order bit set in the first step, just falling into the regular
222	! division loop will mess up the first time around.
223	! So we unroll slightly...
224	Ldo_single_div:
225		deccc	SC
226		bl	Lend_regular_divide
227		 nop
228		sub	R, V, R
229		mov	1, Q
230		b	Lend_single_divloop
231		 nop
232	Lsingle_divloop:
233		sll	Q, 1, Q
234		bl	1f
235		 srl	V, 1, V
236		! R >= 0
237		sub	R, V, R
238		b	2f
239		 inc	Q
240	1:	! R < 0
241		add	R, V, R
242		dec	Q
243	2:
244	Lend_single_divloop:
245		deccc	SC
246		bge	Lsingle_divloop
247		tst	R
248		b,a	Lend_regular_divide
249
250Lnot_really_big:
2511:
252	sll	V, N, V
253	cmp	V, R
254	bleu	1b
255	 inccc	ITER
256	be	Lgot_result
257	 dec	ITER
258
259	tst	R	! set up for initial iteration
260Ldivloop:
261	sll	Q, N, Q
262	DEVELOP_QUOTIENT_BITS(1, 0)
263Lend_regular_divide:
264	deccc	ITER
265	bge	Ldivloop
266	 tst	R
267	bl,a	Lgot_result
268	! non-restoring fixup here (one instruction only!)
269ifelse(OP, `div',
270`	 dec	Q
271', `	 add	R, divisor, R
272')
273
274Lgot_result:
275ifelse(S, `true',
276`	! check to see if answer should be < 0
277	tst	SIGN
278	bl,a	1f
279	 ifelse(OP, `div', `neg Q', `neg R')
2801:')
281	retl
282	 ifelse(OP, `div', `mov Q, %o0', `mov R, %o0')
283