blob: 20d8c976cdc3e8ce1bf21c5b601e38adc3005b34 (
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
57
58
|
#ifdef __K1_TINYK1__
unsigned long long
udivmoddi4(unsigned long long num, unsigned long long den, int modwanted)
{
unsigned long long bit = 1;
unsigned long long res = 0;
while (den < num && bit && !(den & (1L<<31)))
{
den <<=1;
bit <<=1;
}
while (bit)
{
if (num >= den)
{
num -= den;
res |= bit;
}
bit >>=1;
den >>=1;
}
if (modwanted) return num;
return res;
}
#else
/* THIS IS THE PREVIOUS VERSION, USED ON BOSTAN AND ANDEY */
unsigned long long
udivmoddi4(unsigned long long num, unsigned long long den, int modwanted)
{
unsigned long long r = num, q = 0;
if(den <= r) {
unsigned k = __builtin_clzll (den) - __builtin_clzll (r);
den = den << k;
if(r >= den) {
r = r - den;
q = 1LL << k;
}
if(k != 0) {
unsigned i = k;
den = den >> 1;
do {
r = __builtin_k1_stsud (den, r);
i--;
} while (i!= 0);
q = q + r;
r = r >> k;
q = q - (r << k);
}
}
return modwanted ? r : q;
}
#endif /* __K1_TINYK1__ */
|
