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