2 * Copyright (c) 1992, 1993
3 * The Regents of the University of California. All rights reserved.
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.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
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. All advertising materials mentioning features or use of this software
18 * must display the following acknowledgement:
19 * This product includes software developed by the University of
20 * California, Berkeley and its contributors.
21 * 4. Neither the name of the University nor the names of its contributors
22 * may be used to endorse or promote products derived from this software
23 * without specific prior written permission.
25 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37 * from: Header: divrem.m4,v 1.4 92/06/25 13:23:57 torek Exp
38 * $NetBSD: divrem.m4,v 1.4 1997/10/09 10:07:54 lukem Exp $
42 * Division and remainder, from Appendix E of the Sparc Version 8
43 * Architecture Manual, with fixes from Gordon Irlam.
46 #if defined(LIBC_SCCS) && !defined(lint)
47 .asciz "@(#)divrem.m4 8.1 (Berkeley) 6/4/93"
48 #endif /* LIBC_SCCS and not lint */
51 * Input: dividend and divisor in %o0 and %o1 respectively.
54 * NAME name of function to generate
55 * OP OP=div => %o0 / %o1; OP=rem => %o0 % %o1
56 * S S=true => signed; S=false => unsigned
58 * Algorithm parameters:
59 * N how many bits per iteration we try to get (4)
60 * WORDSIZE total number of bits (32)
63 * TWOSUPN 2^N, for label generation (m4 exponentiation currently broken)
64 * TOPBITS number of bits in the top `decade' of a number
66 * Important variables:
67 * Q the partial quotient under development (initially 0)
68 * R the remainder so far, initially the dividend
69 * ITER number of main division loop iterations required;
70 * equal to ceil(log2(quotient) / N). Note that this
71 * is the log base (2^N) of the quotient.
72 * V the current comparand, initially divisor*2^(ITER*N-1)
75 * Current estimate for non-large dividend is
76 * ceil(log2(quotient) / N) * (10 + 7N/2) + C
77 * A large dividend is one greater than 2^(31-TOPBITS) and takes a
78 * different path, as the upper bits of the quotient must be developed
84 define(WORDSIZE, `32')
85 define(TOPBITS, eval(WORDSIZE - N*((WORDSIZE-1)/N)))
87 define(dividend, `%o0')
88 define(divisor, `%o1')
94 /* m4 reminder: ifelse(a,b,c,d) => if a is b, then c, else d */
97 ifelse(S, `true', `define(SIGN, `%g6')')
100 * This is the recursive definition for developing quotient digits.
103 * $1 the current depth, 1 <= $1 <= N
104 * $2 the current accumulation of quotient bits
107 * We add a new bit to $2 and either recurse or insert the bits in
108 * the quotient. R, Q, and V are inputs and outputs as defined above;
109 * the condition codes are expected to reflect the input R, and are
110 * modified to reflect the output R.
112 define(DEVELOP_QUOTIENT_BITS,
113 ` ! depth $1, accumulated bits $2
114 bl L.$1.eval(TWOSUPN+$2)
116 ! remainder is positive
121 ', ` DEVELOP_QUOTIENT_BITS(incr($1), `eval(2*$2+1)')')
122 L.$1.eval(TWOSUPN+$2):
123 ! remainder is negative
128 ', ` DEVELOP_QUOTIENT_BITS(incr($1), `eval(2*$2-1)')')
129 ifelse($1, 1, `9:')')
131 #include <machine/asm.h>
132 #include <machine/trap.h>
136 ` ! compute sign of result; if neither is negative, no problem
137 orcc divisor, dividend, %g0 ! either negative?
138 bge 2f ! no, go do the divide
140 `xor divisor, dividend, SIGN',
141 `mov dividend, SIGN') ! compute sign in any case
145 ! divisor is definitely negative; dividend might also be negative
146 bge 2f ! if dividend not negative...
147 neg divisor ! in any case, make divisor nonneg
148 1: ! dividend is negative, divisor is nonnegative
149 neg dividend ! make dividend nonnegative
152 ! Ready to divide. Compute size of quotient; scale comparand.
157 ! Divide by zero trap. If it returns, return 0 (about as
158 ! wrong as possible, but that is what SunOS does...).
164 cmp R, V ! if divisor exceeds dividend, done
165 blu Lgot_result ! (and algorithm fails otherwise)
167 sethi %hi(1 << (WORDSIZE - TOPBITS - 1)), T
172 ! `Here the dividend is >= 2^(31-N) or so. We must be careful here,
173 ! as our usual N-at-a-shot divide step will cause overflow and havoc.
174 ! The number of bits in the result here is N*ITER+SC, where SC <= N.
175 ! Compute ITER in an unorthodox manner: know we need to shift V into
176 ! the top decade: so do not even bother to compare to R.'
190 ! We get here if the divisor overflowed while shifting.
191 ! This means that R has the high-order bit set.
192 ! Restore V and subtract from R.
193 sll T, TOPBITS, T ! high order bit
194 srl V, 1, V ! rest of V
205 /* NB: these are commented out in the V8-Sparc manual as well */
206 /* (I do not understand this) */
207 ! V > R: went too far: back up 1 step
210 ! do single-bit divide steps
212 ! We have to be careful here. We know that R >= V, so we can do the
213 ! first divide step without thinking. BUT, the others are conditional,
214 ! and are only done if R >= 0. Because both R and V may have the high-
215 ! order bit set in the first step, just falling into the regular
216 ! division loop will mess up the first time around.
217 ! So we unroll slightly...
220 bl Lend_regular_divide
224 b Lend_single_divloop
242 b,a Lend_regular_divide
253 tst R ! set up for initial iteration
256 DEVELOP_QUOTIENT_BITS(1, 0)
262 ! non-restoring fixup here (one instruction only!)
265 ', ` add R, divisor, R
270 ` ! check to see if answer should be < 0
273 ifelse(OP, `div', `neg Q', `neg R')
276 ifelse(OP, `div', `mov Q, %o0', `mov R, %o0')