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