zgcd.c (870B)
1 /* See LICENSE file for copyright and license details. */ 2 #include "internals.h" 3 4 #define u libzahl_tmp_gcd_u 5 #define v libzahl_tmp_gcd_v 6 7 8 void 9 zgcd(z_t a, z_t b, z_t c) 10 { 11 /* 12 * Binary GCD algorithm. 13 */ 14 15 size_t shifts; 16 zahl_char_t *u_orig, *v_orig; 17 size_t u_lsb, v_lsb; 18 int neg, cmpmag; 19 20 if (unlikely(zzero(b))) { 21 SET(a, c); 22 return; 23 } 24 if (unlikely(zzero(c))) { 25 SET(a, b); 26 return; 27 } 28 29 neg = znegative2(b, c); 30 31 u_lsb = zlsb(b); 32 v_lsb = zlsb(c); 33 shifts = MIN(u_lsb, v_lsb); 34 zrsh(u, b, u_lsb); 35 zrsh(v, c, v_lsb); 36 37 u_orig = u->chars; 38 v_orig = v->chars; 39 40 for (;;) { 41 if (likely((cmpmag = zcmpmag(u, v)) >= 0)) { 42 if (unlikely(cmpmag == 0)) 43 break; 44 zswap_tainted_unsigned(u, v); 45 } 46 zsub_positive_assign(v, u); 47 zrsh_taint(v, zlsb(v)); 48 } 49 50 zlsh(a, u, shifts); 51 SET_SIGNUM(a, neg ? -1 : 1); 52 53 u->chars = u_orig; 54 v->chars = v_orig; 55 }