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