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