zgcd.c - libzahl - big integer library
 (HTM) git clone git://git.suckless.org/libzahl
 (DIR) Log
 (DIR) Files
 (DIR) Refs
 (DIR) README
 (DIR) 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 }