divrem.m4 revision 1.4
1 /* $NetBSD: divrem.m4,v 1.4 2003/08/07 16:32:22 agc Exp $ */ 2 3 /* 4 * Copyright (c) 1992, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * This software was developed by the Computer Systems Engineering group 8 * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and 9 * contributed to Berkeley. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 2. Redistributions in binary form must reproduce the above copyright 17 * notice, this list of conditions and the following disclaimer in the 18 * documentation and/or other materials provided with the distribution. 19 * 3. Neither the name of the University nor the names of its contributors 20 * may be used to endorse or promote products derived from this software 21 * without specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33 * SUCH DAMAGE. 34 * 35 * from: Header: divrem.m4,v 1.4 92/06/25 13:23:57 torek Exp 36 */ 37 38 #include <machine/asm.h> 39 #include <machine/trap.h> 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) 47 RCSID("$NetBSD: divrem.m4,v 1.4 2003/08/07 16:32:22 agc Exp $") 48 #endif 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 82 define(N, `4') 83 define(TWOSUPN, `16') 84 define(WORDSIZE, `32') 85 define(TOPBITS, eval(WORDSIZE - N*((WORDSIZE-1)/N))) 86 87 define(dividend, `%o0') 88 define(divisor, `%o1') 89 define(Q, `%o2') 90 define(R, `%o3') 91 define(ITER, `%o4') 92 define(V, `%o5') 93 94 /* m4 reminder: ifelse(a,b,c,d) => if a is b, then c, else d */ 95 define(T, `%g1') 96 define(SC, `%g5') 97 ifelse(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 */ 112 define(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)')') 122 L.$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 FUNC(NAME) 132 ifelse(S, `true', 133 ` ! compute sign of result; if neither is negative, no problem 134 orcc divisor, dividend, %g0 ! either negative? 135 bge 2f ! no, go do the divide 136 ifelse(OP, `div', 137 `xor divisor, dividend, SIGN', 138 `mov dividend, SIGN') ! compute sign in any case 139 tst divisor 140 bge 1f 141 tst dividend 142 ! divisor is definitely negative; dividend might also be negative 143 bge 2f ! if dividend not negative... 144 neg divisor ! in any case, make divisor nonneg 145 1: ! dividend is negative, divisor is nonnegative 146 neg dividend ! make dividend nonnegative 147 2: 148 ') 149 ! Ready to divide. Compute size of quotient; scale comparand. 150 orcc divisor, %g0, V 151 bnz 1f 152 mov dividend, R 153 154 ! Divide by zero trap. If it returns, return 0 (about as 155 ! wrong as possible, but that is what SunOS does...). 156 t ST_DIV0 157 retl 158 clr %o0 159 160 1: 161 cmp R, V ! if divisor exceeds dividend, done 162 blu Lgot_result ! (and algorithm fails otherwise) 163 clr Q 164 sethi %hi(1 << (WORDSIZE - TOPBITS - 1)), T 165 cmp R, T 166 blu Lnot_really_big 167 clr ITER 168 169 ! `Here the dividend is >= 2^(31-N) or so. We must be careful here, 170 ! as our usual N-at-a-shot divide step will cause overflow and havoc. 171 ! The number of bits in the result here is N*ITER+SC, where SC <= N. 172 ! Compute ITER in an unorthodox manner: know we need to shift V into 173 ! the top decade: so do not even bother to compare to R.' 174 1: 175 cmp V, T 176 bgeu 3f 177 mov 1, SC 178 sll V, N, V 179 b 1b 180 inc ITER 181 182 ! Now compute SC. 183 2: addcc V, V, V 184 bcc Lnot_too_big 185 inc SC 186 187 ! We get here if the divisor overflowed while shifting. 188 ! This means that R has the high-order bit set. 189 ! Restore V and subtract from R. 190 sll T, TOPBITS, T ! high order bit 191 srl V, 1, V ! rest of V 192 add V, T, V 193 b Ldo_single_div 194 dec SC 195 196 Lnot_too_big: 197 3: cmp V, R 198 blu 2b 199 nop 200 be Ldo_single_div 201 nop 202 /* NB: these are commented out in the V8-Sparc manual as well */ 203 /* (I do not understand this) */ 204 ! V > R: went too far: back up 1 step 205 ! srl V, 1, V 206 ! dec SC 207 ! do single-bit divide steps 208 ! 209 ! We have to be careful here. We know that R >= V, so we can do the 210 ! first divide step without thinking. BUT, the others are conditional, 211 ! and are only done if R >= 0. Because both R and V may have the high- 212 ! order bit set in the first step, just falling into the regular 213 ! division loop will mess up the first time around. 214 ! So we unroll slightly... 215 Ldo_single_div: 216 deccc SC 217 bl Lend_regular_divide 218 nop 219 sub R, V, R 220 mov 1, Q 221 b Lend_single_divloop 222 nop 223 Lsingle_divloop: 224 sll Q, 1, Q 225 bl 1f 226 srl V, 1, V 227 ! R >= 0 228 sub R, V, R 229 b 2f 230 inc Q 231 1: ! R < 0 232 add R, V, R 233 dec Q 234 2: 235 Lend_single_divloop: 236 deccc SC 237 bge Lsingle_divloop 238 tst R 239 b,a Lend_regular_divide 240 241 Lnot_really_big: 242 1: 243 sll V, N, V 244 cmp V, R 245 bleu 1b 246 inccc ITER 247 be Lgot_result 248 dec ITER 249 250 tst R ! set up for initial iteration 251 Ldivloop: 252 sll Q, N, Q 253 DEVELOP_QUOTIENT_BITS(1, 0) 254 Lend_regular_divide: 255 deccc ITER 256 bge Ldivloop 257 tst R 258 bl,a Lgot_result 259 ! non-restoring fixup here (one instruction only!) 260 ifelse(OP, `div', 261 ` dec Q 262 ', ` add R, divisor, R 263 ') 264 265 Lgot_result: 266 ifelse(S, `true', 267 ` ! check to see if answer should be < 0 268 tst SIGN 269 bl,a 1f 270 ifelse(OP, `div', `neg Q', `neg R') 271 1:') 272 retl 273 ifelse(OP, `div', `mov Q, %o0', `mov R, %o0') 274
Indexes created Thu Sep 25 16:09:42 GMT 2025