/* This file is generated from divrem.m4; DO NOT EDIT! */ /* * Division and remainder, from Appendix E of the Sparc Version 8 * Architecture Manual, with fixes from Gordon Irlam. */ /* * Input: dividend and divisor in %o0 and %o1 respectively. * * m4 parameters: * .urem name of function to generate * rem rem=div => %o0 / %o1; rem=rem => %o0 % %o1 * false false=true => signed; false=false => unsigned * * Algorithm parameters: * N how many bits per iteration we try to get (4) * WORDSIZE total number of bits (32) * * Derived constants: * TOPBITS number of bits in the top decade of a number * * Important variables: * Q the partial quotient under development (initially 0) * R the remainder so far, initially the dividend * ITER number of main division loop iterations required; * equal to ceil(log2(quotient) / N). Note that this * is the log base (2^N) of the quotient. * V the current comparand, initially divisor*2^(ITER*N-1) * * Cost: * Current estimate for non-large dividend is * ceil(log2(quotient) / N) * (10 + 7N/2) + C * A large dividend is one greater than 2^(31-TOPBITS) and takes a * different path, as the upper bits of the quotient must be developed * one bit at a time. */ #include <sysdep.h> .global .urem; .align 4; .type .urem ,@function; .urem: ! Ready to divide. Compute size of quotient; scale comparand. orcc %o1, %g0, %o5 bne 1f mov %o0, %o3 ! Divide by zero trap. If it returns, return 0 (about as ! wrong as possible, but that is what SunOS does...). ta 0x02 retl clr %o0 1: cmp %o3, %o5 ! if %o1 exceeds %o0, done blu .Lgot_result ! (and algorithm fails otherwise) clr %o2 sethi %hi(1 << (32 - 4 - 1)), %g1 cmp %o3, %g1 blu .Lnot_really_big clr %o4 ! Here the dividend is >= 2**(31-N) or so. We must be careful here, ! as our usual N-at-a-shot divide step will cause overflow and havoc. ! The number of bits in the result here is N*ITER+SC, where SC <= N. ! Compute ITER in an unorthodox manner: know we need to shift V into ! the top decade: so do not even bother to compare to R. 1: cmp %o5, %g1 bgeu 3f mov 1, %g2 sll %o5, 4, %o5 b 1b add %o4, 1, %o4 ! Now compute %g2. 2: addcc %o5, %o5, %o5 bcc .Lnot_too_big add %g2, 1, %g2 ! We get here if the %o1 overflowed while shifting. ! This means that %o3 has the high-order bit set. ! Restore %o5 and subtract from %o3. sll %g1, 4, %g1 ! high order bit srl %o5, 1, %o5 ! rest of %o5 add %o5, %g1, %o5 b .Ldo_single_div sub %g2, 1, %g2 .Lnot_too_big: 3: cmp %o5, %o3 blu 2b nop be .Ldo_single_div nop /* NB: these are commented out in the V8-Sparc manual as well */ /* (I do not understand this) */ ! %o5 > %o3: went too far: back up 1 step ! srl %o5, 1, %o5 ! dec %g2 ! do single-bit divide steps ! ! We have to be careful here. We know that %o3 >= %o5, so we can do the ! first divide step without thinking. BUT, the others are conditional, ! and are only done if %o3 >= 0. Because both %o3 and %o5 may have the high- ! order bit set in the first step, just falling into the regular ! division loop will mess up the first time around. ! So we unroll slightly... .Ldo_single_div: subcc %g2, 1, %g2 bl .Lend_regular_divide nop sub %o3, %o5, %o3 mov 1, %o2 b .Lend_single_divloop nop .Lsingle_divloop: sll %o2, 1, %o2 bl 1f srl %o5, 1, %o5 ! %o3 >= 0 sub %o3, %o5, %o3 b 2f add %o2, 1, %o2 1: ! %o3 < 0 add %o3, %o5, %o3 sub %o2, 1, %o2 2: .Lend_single_divloop: subcc %g2, 1, %g2 bge .Lsingle_divloop tst %o3 b,a .Lend_regular_divide .Lnot_really_big: 1: sll %o5, 4, %o5 cmp %o5, %o3 bleu 1b addcc %o4, 1, %o4 be .Lgot_result sub %o4, 1, %o4 tst %o3 ! set up for initial iteration .Ldivloop: sll %o2, 4, %o2 ! depth 1, accumulated bits 0 bl .L1.16 srl %o5,1,%o5 ! remainder is positive subcc %o3,%o5,%o3 ! depth 2, accumulated bits 1 bl .L2.17 srl %o5,1,%o5 ! remainder is positive subcc %o3,%o5,%o3 ! depth 3, accumulated bits 3 bl .L3.19 srl %o5,1,%o5 ! remainder is positive subcc %o3,%o5,%o3 ! depth 4, accumulated bits 7 bl .L4.23 srl %o5,1,%o5 ! remainder is positive subcc %o3,%o5,%o3 b 9f add %o2, (7*2+1), %o2 .L4.23: ! remainder is negative addcc %o3,%o5,%o3 b 9f add %o2, (7*2-1), %o2 .L3.19: ! remainder is negative addcc %o3,%o5,%o3 ! depth 4, accumulated bits 5 bl .L4.21 srl %o5,1,%o5 ! remainder is positive subcc %o3,%o5,%o3 b 9f add %o2, (5*2+1), %o2 .L4.21: ! remainder is negative addcc %o3,%o5,%o3 b 9f add %o2, (5*2-1), %o2 .L2.17: ! remainder is negative addcc %o3,%o5,%o3 ! depth 3, accumulated bits 1 bl .L3.17 srl %o5,1,%o5 ! remainder is positive subcc %o3,%o5,%o3 ! depth 4, accumulated bits 3 bl .L4.19 srl %o5,1,%o5 ! remainder is positive subcc %o3,%o5,%o3 b 9f add %o2, (3*2+1), %o2 .L4.19: ! remainder is negative addcc %o3,%o5,%o3 b 9f add %o2, (3*2-1), %o2 .L3.17: ! remainder is negative addcc %o3,%o5,%o3 ! depth 4, accumulated bits 1 bl .L4.17 srl %o5,1,%o5 ! remainder is positive subcc %o3,%o5,%o3 b 9f add %o2, (1*2+1), %o2 .L4.17: ! remainder is negative addcc %o3,%o5,%o3 b 9f add %o2, (1*2-1), %o2 .L1.16: ! remainder is negative addcc %o3,%o5,%o3 ! depth 2, accumulated bits -1 bl .L2.15 srl %o5,1,%o5 ! remainder is positive subcc %o3,%o5,%o3 ! depth 3, accumulated bits -1 bl .L3.15 srl %o5,1,%o5 ! remainder is positive subcc %o3,%o5,%o3 ! depth 4, accumulated bits -1 bl .L4.15 srl %o5,1,%o5 ! remainder is positive subcc %o3,%o5,%o3 b 9f add %o2, (-1*2+1), %o2 .L4.15: ! remainder is negative addcc %o3,%o5,%o3 b 9f add %o2, (-1*2-1), %o2 .L3.15: ! remainder is negative addcc %o3,%o5,%o3 ! depth 4, accumulated bits -3 bl .L4.13 srl %o5,1,%o5 ! remainder is positive subcc %o3,%o5,%o3 b 9f add %o2, (-3*2+1), %o2 .L4.13: ! remainder is negative addcc %o3,%o5,%o3 b 9f add %o2, (-3*2-1), %o2 .L2.15: ! remainder is negative addcc %o3,%o5,%o3 ! depth 3, accumulated bits -3 bl .L3.13 srl %o5,1,%o5 ! remainder is positive subcc %o3,%o5,%o3 ! depth 4, accumulated bits -5 bl .L4.11 srl %o5,1,%o5 ! remainder is positive subcc %o3,%o5,%o3 b 9f add %o2, (-5*2+1), %o2 .L4.11: ! remainder is negative addcc %o3,%o5,%o3 b 9f add %o2, (-5*2-1), %o2 .L3.13: ! remainder is negative addcc %o3,%o5,%o3 ! depth 4, accumulated bits -7 bl .L4.9 srl %o5,1,%o5 ! remainder is positive subcc %o3,%o5,%o3 b 9f add %o2, (-7*2+1), %o2 .L4.9: ! remainder is negative addcc %o3,%o5,%o3 b 9f add %o2, (-7*2-1), %o2 9: .Lend_regular_divide: subcc %o4, 1, %o4 bge .Ldivloop tst %o3 bl,a .Lgot_result ! non-restoring fixup here (one instruction only!) add %o3, %o1, %o3 .Lgot_result: retl mov %o3, %o0 END(.urem)