summaryrefslogtreecommitdiff
path: root/src/libbiguint/bu_gcd.c
blob: 919c8685965e1030bdeb61fb8c38e4660adc54d1 (plain)
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
/* ISC license. */

#include <stdint.h>
#include <skalibs/biguint.h>

int bu_gcd (uint32_t *r, unsigned int rn, uint32_t const *a, unsigned int an, uint32_t const *b, unsigned int bn)
{
  if (bu_cmp(a, an, b, bn) < 0)
  {
    register uint32_t const *t = a ;
    register unsigned int tn = an ;
    a = b ; an = bn ;
    b = t ; bn = tn ;
  }
  {
    uint32_t trash[an] ;
    uint32_t aa[an] ;
    uint32_t bb[an] ;
    uint32_t *aaa = aa, *bbb = bb ;
    bu_copy_internal(aa, a, an) ;
    bu_copy_internal(bb, b, bn) ;
    bu_zero(bb+bn, an-bn) ;

    while (bu_len(bbb, an))
    {
      register uint32_t *ttt = aaa ;
      bu_div_internal(aaa, an, bbb, an, trash, an) ;
      aaa = bbb ;
      bbb = ttt ;
    }
    return bu_copy(r, rn, aaa, an) ;
  }
}