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
|
/* See LICENSE file for copyright and license details. */
#include "internals.h"
#define u libzahl_tmp_gcd_u
#define v libzahl_tmp_gcd_v
void
zgcd(z_t a, z_t b, z_t c)
{
/*
* Binary GCD algorithm.
*/
size_t shifts;
zahl_char_t *u_orig, *v_orig;
size_t u_lsb, v_lsb;
int neg, cmpmag;
if (unlikely(zzero(b))) {
SET(a, c);
return;
}
if (unlikely(zzero(c))) {
SET(a, b);
return;
}
neg = znegative2(b, c);
u_lsb = zlsb(b);
v_lsb = zlsb(c);
shifts = MIN(u_lsb, v_lsb);
zrsh(u, b, u_lsb);
zrsh(v, c, v_lsb);
u_orig = u->chars;
v_orig = v->chars;
for (;;) {
if (likely((cmpmag = zcmpmag(u, v)) >= 0)) {
if (unlikely(cmpmag == 0))
break;
zswap_tainted_unsigned(u, v);
}
zsub_positive_assign(v, u);
zrsh_taint(v, zlsb(v));
}
zlsh(a, u, shifts);
SET_SIGNUM(a, neg ? -1 : 1);
u->chars = u_orig;
v->chars = v_orig;
}
|
