178d19267Storek/* 2ac4d1c6bSbostic * Copyright (c) 1992, 1993 3ac4d1c6bSbostic * The Regents of the University of California. All rights reserved. 478d19267Storek * 578d19267Storek * This software was developed by the Computer Systems Engineering group 678d19267Storek * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and 778d19267Storek * contributed to Berkeley. 878d19267Storek * 978d19267Storek * %sccs.include.redist.c% 1078d19267Storek * 1178d19267Storek * from: $Header: divrem.m4,v 1.4 92/06/25 13:23:57 torek Exp $ 1278d19267Storek */ 1378d19267Storek 1478d19267Storek/* 1578d19267Storek * Division and remainder, from Appendix E of the Sparc Version 8 1678d19267Storek * Architecture Manual, with fixes from Gordon Irlam. 1778d19267Storek */ 1878d19267Storek 1978d19267Storek#if defined(LIBC_SCCS) && !defined(lint) 20*f00e44ddSbostic .asciz "@(#)divrem.m4 8.1 (Berkeley) 06/04/93" 2178d19267Storek#endif /* LIBC_SCCS and not lint */ 2278d19267Storek 2378d19267Storek/* 2478d19267Storek * Input: dividend and divisor in %o0 and %o1 respectively. 2578d19267Storek * 2678d19267Storek * m4 parameters: 2778d19267Storek * NAME name of function to generate 2878d19267Storek * OP OP=div => %o0 / %o1; OP=rem => %o0 % %o1 2978d19267Storek * S S=true => signed; S=false => unsigned 3078d19267Storek * 3178d19267Storek * Algorithm parameters: 3278d19267Storek * N how many bits per iteration we try to get (4) 3378d19267Storek * WORDSIZE total number of bits (32) 3478d19267Storek * 3578d19267Storek * Derived constants: 3678d19267Storek * TWOSUPN 2^N, for label generation (m4 exponentiation currently broken) 3778d19267Storek * TOPBITS number of bits in the top `decade' of a number 3878d19267Storek * 3978d19267Storek * Important variables: 4078d19267Storek * Q the partial quotient under development (initially 0) 4178d19267Storek * R the remainder so far, initially the dividend 4278d19267Storek * ITER number of main division loop iterations required; 4378d19267Storek * equal to ceil(log2(quotient) / N). Note that this 4478d19267Storek * is the log base (2^N) of the quotient. 4578d19267Storek * V the current comparand, initially divisor*2^(ITER*N-1) 4678d19267Storek * 4778d19267Storek * Cost: 4878d19267Storek * Current estimate for non-large dividend is 4978d19267Storek * ceil(log2(quotient) / N) * (10 + 7N/2) + C 5078d19267Storek * A large dividend is one greater than 2^(31-TOPBITS) and takes a 5178d19267Storek * different path, as the upper bits of the quotient must be developed 5278d19267Storek * one bit at a time. 5378d19267Storek */ 5478d19267Storek 5578d19267Storekdefine(N, `4') 5678d19267Storekdefine(TWOSUPN, `16') 5778d19267Storekdefine(WORDSIZE, `32') 5878d19267Storekdefine(TOPBITS, eval(WORDSIZE - N*((WORDSIZE-1)/N))) 5978d19267Storek 6078d19267Storekdefine(dividend, `%o0') 6178d19267Storekdefine(divisor, `%o1') 6278d19267Storekdefine(Q, `%o2') 6378d19267Storekdefine(R, `%o3') 6478d19267Storekdefine(ITER, `%o4') 6578d19267Storekdefine(V, `%o5') 6678d19267Storek 6778d19267Storek/* m4 reminder: ifelse(a,b,c,d) => if a is b, then c, else d */ 6878d19267Storekdefine(T, `%g1') 6978d19267Storekdefine(SC, `%g7') 7078d19267Storekifelse(S, `true', `define(SIGN, `%g6')') 7178d19267Storek 7278d19267Storek/* 7378d19267Storek * This is the recursive definition for developing quotient digits. 7478d19267Storek * 7578d19267Storek * Parameters: 7678d19267Storek * $1 the current depth, 1 <= $1 <= N 7778d19267Storek * $2 the current accumulation of quotient bits 7878d19267Storek * N max depth 7978d19267Storek * 8078d19267Storek * We add a new bit to $2 and either recurse or insert the bits in 8178d19267Storek * the quotient. R, Q, and V are inputs and outputs as defined above; 8278d19267Storek * the condition codes are expected to reflect the input R, and are 8378d19267Storek * modified to reflect the output R. 8478d19267Storek */ 8578d19267Storekdefine(DEVELOP_QUOTIENT_BITS, 8678d19267Storek` ! depth $1, accumulated bits $2 8778d19267Storek bl L.$1.eval(TWOSUPN+$2) 8878d19267Storek srl V,1,V 8978d19267Storek ! remainder is positive 9078d19267Storek subcc R,V,R 9178d19267Storek ifelse($1, N, 9278d19267Storek ` b 9f 9378d19267Storek add Q, ($2*2+1), Q 9478d19267Storek ', ` DEVELOP_QUOTIENT_BITS(incr($1), `eval(2*$2+1)')') 9578d19267StorekL.$1.eval(TWOSUPN+$2): 9678d19267Storek ! remainder is negative 9778d19267Storek addcc R,V,R 9878d19267Storek ifelse($1, N, 9978d19267Storek ` b 9f 10078d19267Storek add Q, ($2*2-1), Q 10178d19267Storek ', ` DEVELOP_QUOTIENT_BITS(incr($1), `eval(2*$2-1)')') 10278d19267Storek ifelse($1, 1, `9:')') 10378d19267Storek 10478d19267Storek#include "DEFS.h" 10578d19267Storek#include <machine/trap.h> 10678d19267Storek 10778d19267StorekFUNC(NAME) 10878d19267Storekifelse(S, `true', 10978d19267Storek` ! compute sign of result; if neither is negative, no problem 11078d19267Storek orcc divisor, dividend, %g0 ! either negative? 11178d19267Storek bge 2f ! no, go do the divide 11278d19267Storek xor divisor, dividend, SIGN ! compute sign in any case 11378d19267Storek tst divisor 11478d19267Storek bge 1f 11578d19267Storek tst dividend 11678d19267Storek ! divisor is definitely negative; dividend might also be negative 11778d19267Storek bge 2f ! if dividend not negative... 11878d19267Storek neg divisor ! in any case, make divisor nonneg 11978d19267Storek1: ! dividend is negative, divisor is nonnegative 12078d19267Storek neg dividend ! make dividend nonnegative 12178d19267Storek2: 12278d19267Storek') 12378d19267Storek ! Ready to divide. Compute size of quotient; scale comparand. 12478d19267Storek orcc divisor, %g0, V 12578d19267Storek bnz 1f 12678d19267Storek mov dividend, R 12778d19267Storek 12878d19267Storek ! Divide by zero trap. If it returns, return 0 (about as 12978d19267Storek ! wrong as possible, but that is what SunOS does...). 13078d19267Storek t ST_DIV0 13178d19267Storek retl 13278d19267Storek clr %o0 13378d19267Storek 13478d19267Storek1: 13578d19267Storek cmp R, V ! if divisor exceeds dividend, done 13678d19267Storek blu Lgot_result ! (and algorithm fails otherwise) 13778d19267Storek clr Q 13878d19267Storek sethi %hi(1 << (WORDSIZE - TOPBITS - 1)), T 13978d19267Storek cmp R, T 14078d19267Storek blu Lnot_really_big 14178d19267Storek clr ITER 14278d19267Storek 14378d19267Storek ! `Here the dividend is >= 2^(31-N) or so. We must be careful here, 14478d19267Storek ! as our usual N-at-a-shot divide step will cause overflow and havoc. 14578d19267Storek ! The number of bits in the result here is N*ITER+SC, where SC <= N. 14678d19267Storek ! Compute ITER in an unorthodox manner: know we need to shift V into 14778d19267Storek ! the top decade: so do not even bother to compare to R.' 14878d19267Storek 1: 14978d19267Storek cmp V, T 15078d19267Storek bgeu 3f 15178d19267Storek mov 1, SC 15278d19267Storek sll V, N, V 15378d19267Storek b 1b 15478d19267Storek inc ITER 15578d19267Storek 15678d19267Storek ! Now compute SC. 15778d19267Storek 2: addcc V, V, V 15878d19267Storek bcc Lnot_too_big 15978d19267Storek inc SC 16078d19267Storek 16178d19267Storek ! We get here if the divisor overflowed while shifting. 16278d19267Storek ! This means that R has the high-order bit set. 16378d19267Storek ! Restore V and subtract from R. 16478d19267Storek sll T, TOPBITS, T ! high order bit 16578d19267Storek srl V, 1, V ! rest of V 16678d19267Storek add V, T, V 16778d19267Storek b Ldo_single_div 16878d19267Storek dec SC 16978d19267Storek 17078d19267Storek Lnot_too_big: 17178d19267Storek 3: cmp V, R 17278d19267Storek blu 2b 17378d19267Storek nop 17478d19267Storek be Ldo_single_div 17578d19267Storek nop 17678d19267Storek /* NB: these are commented out in the V8-Sparc manual as well */ 17778d19267Storek /* (I do not understand this) */ 17878d19267Storek ! V > R: went too far: back up 1 step 17978d19267Storek ! srl V, 1, V 18078d19267Storek ! dec SC 18178d19267Storek ! do single-bit divide steps 18278d19267Storek ! 18378d19267Storek ! We have to be careful here. We know that R >= V, so we can do the 18478d19267Storek ! first divide step without thinking. BUT, the others are conditional, 18578d19267Storek ! and are only done if R >= 0. Because both R and V may have the high- 18678d19267Storek ! order bit set in the first step, just falling into the regular 18778d19267Storek ! division loop will mess up the first time around. 18878d19267Storek ! So we unroll slightly... 18978d19267Storek Ldo_single_div: 19078d19267Storek deccc SC 19178d19267Storek bl Lend_regular_divide 19278d19267Storek nop 19378d19267Storek sub R, V, R 19478d19267Storek mov 1, Q 19578d19267Storek b Lend_single_divloop 19678d19267Storek nop 19778d19267Storek Lsingle_divloop: 19878d19267Storek sll Q, 1, Q 19978d19267Storek bl 1f 20078d19267Storek srl V, 1, V 20178d19267Storek ! R >= 0 20278d19267Storek sub R, V, R 20378d19267Storek b 2f 20478d19267Storek inc Q 20578d19267Storek 1: ! R < 0 20678d19267Storek add R, V, R 20778d19267Storek dec Q 20878d19267Storek 2: 20978d19267Storek Lend_single_divloop: 21078d19267Storek deccc SC 21178d19267Storek bge Lsingle_divloop 21278d19267Storek tst R 21378d19267Storek b,a Lend_regular_divide 21478d19267Storek 21578d19267StorekLnot_really_big: 21678d19267Storek1: 21778d19267Storek sll V, N, V 21878d19267Storek cmp V, R 21978d19267Storek bleu 1b 22078d19267Storek inccc ITER 22178d19267Storek be Lgot_result 22278d19267Storek dec ITER 22378d19267Storek 22478d19267Storek tst R ! set up for initial iteration 22578d19267StorekLdivloop: 22678d19267Storek sll Q, N, Q 22778d19267Storek DEVELOP_QUOTIENT_BITS(1, 0) 22878d19267StorekLend_regular_divide: 22978d19267Storek deccc ITER 23078d19267Storek bge Ldivloop 23178d19267Storek tst R 23278d19267Storek bl,a Lgot_result 23378d19267Storek ! non-restoring fixup here (one instruction only!) 23478d19267Storekifelse(OP, `div', 23578d19267Storek` dec Q 23678d19267Storek', ` add R, divisor, R 23778d19267Storek') 23878d19267Storek 23978d19267StorekLgot_result: 24078d19267Storekifelse(S, `true', 24178d19267Storek` ! check to see if answer should be < 0 24278d19267Storek tst SIGN 24378d19267Storek bl,a 1f 24478d19267Storek ifelse(OP, `div', `neg Q', `neg R') 24578d19267Storek1:') 24678d19267Storek retl 24778d19267Storek ifelse(OP, `div', `mov Q, %o0', `mov R, %o0') 248