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. 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. 24 * 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 35 * SUCH DAMAGE. 36 * 37 * from: Header: divrem.m4,v 1.4 92/06/25 13:23:57 torek Exp 38 * $NetBSD: divrem.m4,v 1.6 1999/03/05 09:18:32 pk Exp $ 39 */ 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#if defined(LIBC_SCCS) && !defined(lint) 47 .asciz "@(#)divrem.m4 8.1 (Berkeley) 6/4/93" 48#endif /* LIBC_SCCS and not lint */ 49 50/* 51 * Input: dividend and divisor in %o0 and %o1 respectively. 52 * 53 * m4 parameters: 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 57 * 58 * Algorithm parameters: 59 * N how many bits per iteration we try to get (4) 60 * WORDSIZE total number of bits (32) 61 * 62 * Derived constants: 63 * TWOSUPN 2^N, for label generation (m4 exponentiation currently broken) 64 * TOPBITS number of bits in the top `decade' of a number 65 * 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) 73 * 74 * Cost: 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 79 * one bit at a time. 80 */ 81 82define(N, `4') 83define(TWOSUPN, `16') 84define(WORDSIZE, `32') 85define(TOPBITS, eval(WORDSIZE - N*((WORDSIZE-1)/N))) 86 87define(dividend, `%o0') 88define(divisor, `%o1') 89define(Q, `%o2') 90define(R, `%o3') 91define(ITER, `%o4') 92define(V, `%o5') 93 94/* m4 reminder: ifelse(a,b,c,d) => if a is b, then c, else d */ 95define(T, `%g1') 96define(SC, `%g7') 97ifelse(S, `true', `define(SIGN, `%g6')') 98 99/* 100 * This is the recursive definition for developing quotient digits. 101 * 102 * Parameters: 103 * $1 the current depth, 1 <= $1 <= N 104 * $2 the current accumulation of quotient bits 105 * N max depth 106 * 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. 111 */ 112define(DEVELOP_QUOTIENT_BITS, 113` ! depth $1, accumulated bits $2 114 bl L.$1.eval(TWOSUPN+$2) 115 srl V,1,V 116 ! remainder is positive 117 subcc R,V,R 118 ifelse($1, N, 119 ` b 9f 120 add Q, ($2*2+1), Q 121 ', ` DEVELOP_QUOTIENT_BITS(incr($1), `eval(2*$2+1)')') 122L.$1.eval(TWOSUPN+$2): 123 ! remainder is negative 124 addcc R,V,R 125 ifelse($1, N, 126 ` b 9f 127 add Q, ($2*2-1), Q 128 ', ` DEVELOP_QUOTIENT_BITS(incr($1), `eval(2*$2-1)')') 129 ifelse($1, 1, `9:')') 130 131#include <machine/asm.h> 132#include <machine/trap.h> 133 134FUNC(NAME) 135ifelse(S, `true', 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 139 ifelse(OP, `div', 140 `xor divisor, dividend, SIGN', 141 `mov dividend, SIGN') ! compute sign in any case 142 tst divisor 143 bge 1f 144 tst dividend 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 1481: ! dividend is negative, divisor is nonnegative 149 neg dividend ! make dividend nonnegative 1502: 151') 152 ! Ready to divide. Compute size of quotient; scale comparand. 153 orcc divisor, %g0, V 154 bnz 1f 155 mov dividend, R 156 157 ! Divide by zero trap. If it returns, return 0 (about as 158 ! wrong as possible, but that is what SunOS does...). 159 t ST_DIV0 160 retl 161 clr %o0 162 1631: 164 cmp R, V ! if divisor exceeds dividend, done 165 blu Lgot_result ! (and algorithm fails otherwise) 166 clr Q 167 sethi %hi(1 << (WORDSIZE - TOPBITS - 1)), T 168 cmp R, T 169 blu Lnot_really_big 170 clr ITER 171 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.' 177 1: 178 cmp V, T 179 bgeu 3f 180 mov 1, SC 181 sll V, N, V 182 b 1b 183 inc ITER 184 185 ! Now compute SC. 186 2: addcc V, V, V 187 bcc Lnot_too_big 188 inc SC 189 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 195 add V, T, V 196 b Ldo_single_div 197 dec SC 198 199 Lnot_too_big: 200 3: cmp V, R 201 blu 2b 202 nop 203 be Ldo_single_div 204 nop 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 208 ! srl V, 1, V 209 ! dec SC 210 ! do single-bit divide steps 211 ! 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... 218 Ldo_single_div: 219 deccc SC 220 bl Lend_regular_divide 221 nop 222 sub R, V, R 223 mov 1, Q 224 b Lend_single_divloop 225 nop 226 Lsingle_divloop: 227 sll Q, 1, Q 228 bl 1f 229 srl V, 1, V 230 ! R >= 0 231 sub R, V, R 232 b 2f 233 inc Q 234 1: ! R < 0 235 add R, V, R 236 dec Q 237 2: 238 Lend_single_divloop: 239 deccc SC 240 bge Lsingle_divloop 241 tst R 242 b,a Lend_regular_divide 243 244Lnot_really_big: 2451: 246 sll V, N, V 247 cmp V, R 248 bleu 1b 249 inccc ITER 250 be Lgot_result 251 dec ITER 252 253 tst R ! set up for initial iteration 254Ldivloop: 255 sll Q, N, Q 256 DEVELOP_QUOTIENT_BITS(1, 0) 257Lend_regular_divide: 258 deccc ITER 259 bge Ldivloop 260 tst R 261 bl,a Lgot_result 262 ! non-restoring fixup here (one instruction only!) 263ifelse(OP, `div', 264` dec Q 265', ` add R, divisor, R 266') 267 268Lgot_result: 269ifelse(S, `true', 270` ! check to see if answer should be < 0 271 tst SIGN 272 bl,a 1f 273 ifelse(OP, `div', `neg Q', `neg R') 2741:') 275 retl 276 ifelse(OP, `div', `mov Q, %o0', `mov R, %o0') 277