int aws_mp_gcd()

in AWSCognitoIdentityProvider/Internal/JKBigInteger/LibTomMath/tommath.c [5996:6079]

• 60 lines of code
• 17 McCabe index (conditional complexity)

int aws_mp_gcd(aws_mp_int *a, aws_mp_int *b, aws_mp_int *c)
{
  aws_mp_int u, v;
  int     k, u_lsb, v_lsb, res;

  /* either zero than gcd is the largest */
  if (aws_mp_iszero (a) == AWS_MP_YES) {
    return aws_mp_abs(b, c);
  }
  if (aws_mp_iszero (b) == AWS_MP_YES) {
    return aws_mp_abs(a, c);
  }

  /* get copies of a and b we can modify */
  if ((res = aws_mp_init_copy(&u, a)) != AWS_MP_OKAY) {
    return res;
  }

  if ((res = aws_mp_init_copy(&v, b)) != AWS_MP_OKAY) {
    goto LBL_U;
  }

  /* must be positive for the remainder of the algorithm */
  u.sign = v.sign = AWS_MP_ZPOS;

  /* B1.  Find the common power of two for u and v */
  u_lsb = aws_mp_cnt_lsb(&u);
  v_lsb = aws_mp_cnt_lsb(&v);
  k     = AWS_MIN(u_lsb, v_lsb);

  if (k > 0) {
     /* divide the power of two out */
     if ((res = aws_mp_div_2d(&u, k, &u, NULL)) != AWS_MP_OKAY) {
        goto LBL_V;
     }

     if ((res = aws_mp_div_2d(&v, k, &v, NULL)) != AWS_MP_OKAY) {
        goto LBL_V;
     }
  }

  /* divide any remaining factors of two out */
  if (u_lsb != k) {
     if ((res = aws_mp_div_2d(&u, u_lsb - k, &u, NULL)) != AWS_MP_OKAY) {
        goto LBL_V;
     }
  }

  if (v_lsb != k) {
     if ((res = aws_mp_div_2d(&v, v_lsb - k, &v, NULL)) != AWS_MP_OKAY) {
        goto LBL_V;
     }
  }

  while (aws_mp_iszero(&v) == 0) {
     /* make sure v is the largest */
     if (aws_mp_cmp_mag(&u, &v) == AWS_MP_GT) {
        /* swap u and v to make sure v is >= u */
         aws_mp_exch(&u, &v);
     }
     
     /* subtract smallest from largest */
     if ((res = aws_s_mp_sub(&v, &u, &v)) != AWS_MP_OKAY) {
        goto LBL_V;
     }
     
     /* Divide out all factors of two */
     if ((res = aws_mp_div_2d(&v, aws_mp_cnt_lsb(&v), &v, NULL)) != AWS_MP_OKAY) {
        goto LBL_V;
     } 
  } 

  /* multiply by 2**k which we divided out at the beginning */
  if ((res = aws_mp_mul_2d(&u, k, c)) != AWS_MP_OKAY) {
     goto LBL_V;
  }
  c->sign = AWS_MP_ZPOS;
  res = AWS_MP_OKAY;
LBL_V:
aws_mp_clear(&u);
LBL_U:
aws_mp_clear(&v);
  return res;
}