GopherProxy

	zgcd.c - 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 }