1 b3f61791 2004-03-21 devnull #include "os.h"
 2 b3f61791 2004-03-21 devnull #include <mp.h>
 3 b3f61791 2004-03-21 devnull #include "dat.h"
 4 b3f61791 2004-03-21 devnull 
 5 cbeb0b26 2006-04-01 devnull /* */
 6 cbeb0b26 2006-04-01 devnull /*	divide two digits by one and return quotient */
 7 cbeb0b26 2006-04-01 devnull /* */
 8 b3f61791 2004-03-21 devnull void
 9 b3f61791 2004-03-21 devnull mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient)
10 b3f61791 2004-03-21 devnull {
11 b3f61791 2004-03-21 devnull 	mpdigit hi, lo, q, x, y;
12 b3f61791 2004-03-21 devnull 	int i;
13 b3f61791 2004-03-21 devnull 
14 b3f61791 2004-03-21 devnull 	hi = dividend[1];
15 b3f61791 2004-03-21 devnull 	lo = dividend[0];
16 b3f61791 2004-03-21 devnull 
17 cbeb0b26 2006-04-01 devnull 	/* return highest digit value if the result >= 2**32 */
18 b3f61791 2004-03-21 devnull 	if(hi >= divisor || divisor == 0){
19 b3f61791 2004-03-21 devnull 		divisor = 0;
20 b3f61791 2004-03-21 devnull 		*quotient = ~divisor;
21 b3f61791 2004-03-21 devnull 		return;
22 b3f61791 2004-03-21 devnull 	}
23 b3f61791 2004-03-21 devnull 
24 cbeb0b26 2006-04-01 devnull 	/* at this point we know that hi < divisor */
25 cbeb0b26 2006-04-01 devnull 	/* just shift and subtract till we're done */
26 b3f61791 2004-03-21 devnull 	q = 0;
27 b3f61791 2004-03-21 devnull 	x = divisor;
28 b3f61791 2004-03-21 devnull 	for(i = Dbits-1; hi > 0 && i >= 0; i--){
29 b3f61791 2004-03-21 devnull 		x >>= 1;
30 b3f61791 2004-03-21 devnull 		if(x > hi)
31 b3f61791 2004-03-21 devnull 			continue;
32 b3f61791 2004-03-21 devnull 		y = divisor<<i;
33 b3f61791 2004-03-21 devnull 		if(x == hi && y > lo)
34 b3f61791 2004-03-21 devnull 			continue;
35 b3f61791 2004-03-21 devnull 		if(y > lo)
36 b3f61791 2004-03-21 devnull 			hi--;
37 b3f61791 2004-03-21 devnull 		lo -= y;
38 b3f61791 2004-03-21 devnull 		hi -= x;
39 b3f61791 2004-03-21 devnull 		q |= 1<<i;
40 b3f61791 2004-03-21 devnull 	}
41 b3f61791 2004-03-21 devnull 	q += lo/divisor;
42 b3f61791 2004-03-21 devnull 	*quotient = q;
43 b3f61791 2004-03-21 devnull }