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 * $Id: divrem.m4,v 1.1 1994/06/30 06:53:01 deraadt 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 "DEFS.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 xor divisor, dividend, SIGN ! compute sign in any case 140 tst divisor 141 bge 1f 142 tst dividend 143 ! divisor is definitely negative; dividend might also be negative 144 bge 2f ! if dividend not negative... 145 neg divisor ! in any case, make divisor nonneg 1461: ! dividend is negative, divisor is nonnegative 147 neg dividend ! make dividend nonnegative 1482: 149') 150 ! Ready to divide. Compute size of quotient; scale comparand. 151 orcc divisor, %g0, V 152 bnz 1f 153 mov dividend, R 154 155 ! Divide by zero trap. If it returns, return 0 (about as 156 ! wrong as possible, but that is what SunOS does...). 157 t ST_DIV0 158 retl 159 clr %o0 160 1611: 162 cmp R, V ! if divisor exceeds dividend, done 163 blu Lgot_result ! (and algorithm fails otherwise) 164 clr Q 165 sethi %hi(1 << (WORDSIZE - TOPBITS - 1)), T 166 cmp R, T 167 blu Lnot_really_big 168 clr ITER 169 170 ! `Here the dividend is >= 2^(31-N) or so. We must be careful here, 171 ! as our usual N-at-a-shot divide step will cause overflow and havoc. 172 ! The number of bits in the result here is N*ITER+SC, where SC <= N. 173 ! Compute ITER in an unorthodox manner: know we need to shift V into 174 ! the top decade: so do not even bother to compare to R.' 175 1: 176 cmp V, T 177 bgeu 3f 178 mov 1, SC 179 sll V, N, V 180 b 1b 181 inc ITER 182 183 ! Now compute SC. 184 2: addcc V, V, V 185 bcc Lnot_too_big 186 inc SC 187 188 ! We get here if the divisor overflowed while shifting. 189 ! This means that R has the high-order bit set. 190 ! Restore V and subtract from R. 191 sll T, TOPBITS, T ! high order bit 192 srl V, 1, V ! rest of V 193 add V, T, V 194 b Ldo_single_div 195 dec SC 196 197 Lnot_too_big: 198 3: cmp V, R 199 blu 2b 200 nop 201 be Ldo_single_div 202 nop 203 /* NB: these are commented out in the V8-Sparc manual as well */ 204 /* (I do not understand this) */ 205 ! V > R: went too far: back up 1 step 206 ! srl V, 1, V 207 ! dec SC 208 ! do single-bit divide steps 209 ! 210 ! We have to be careful here. We know that R >= V, so we can do the 211 ! first divide step without thinking. BUT, the others are conditional, 212 ! and are only done if R >= 0. Because both R and V may have the high- 213 ! order bit set in the first step, just falling into the regular 214 ! division loop will mess up the first time around. 215 ! So we unroll slightly... 216 Ldo_single_div: 217 deccc SC 218 bl Lend_regular_divide 219 nop 220 sub R, V, R 221 mov 1, Q 222 b Lend_single_divloop 223 nop 224 Lsingle_divloop: 225 sll Q, 1, Q 226 bl 1f 227 srl V, 1, V 228 ! R >= 0 229 sub R, V, R 230 b 2f 231 inc Q 232 1: ! R < 0 233 add R, V, R 234 dec Q 235 2: 236 Lend_single_divloop: 237 deccc SC 238 bge Lsingle_divloop 239 tst R 240 b,a Lend_regular_divide 241 242Lnot_really_big: 2431: 244 sll V, N, V 245 cmp V, R 246 bleu 1b 247 inccc ITER 248 be Lgot_result 249 dec ITER 250 251 tst R ! set up for initial iteration 252Ldivloop: 253 sll Q, N, Q 254 DEVELOP_QUOTIENT_BITS(1, 0) 255Lend_regular_divide: 256 deccc ITER 257 bge Ldivloop 258 tst R 259 bl,a Lgot_result 260 ! non-restoring fixup here (one instruction only!) 261ifelse(OP, `div', 262` dec Q 263', ` add R, divisor, R 264') 265 266Lgot_result: 267ifelse(S, `true', 268` ! check to see if answer should be < 0 269 tst SIGN 270 bl,a 1f 271 ifelse(OP, `div', `neg Q', `neg R') 2721:') 273 retl 274 ifelse(OP, `div', `mov Q, %o0', `mov R, %o0') 275