libzahl

big integer library
git clone git://git.suckless.org/libzahl
Log | Files | Refs | README | LICENSE

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 }