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