in AWSCognitoIdentityProvider/Internal/JKBigInteger/LibTomMath/tommath.c [3773:3959]
int aws_mp_div(aws_mp_int *a, aws_mp_int *b, aws_mp_int *c, aws_mp_int *d)
{
aws_mp_int q, x, y, t1, t2;
int res, n, t, i, norm, neg;
/* is divisor zero ? */
if (aws_mp_iszero (b) == 1) {
return AWS_MP_VAL;
}
/* if a < b then q=0, r = a */
if (aws_mp_cmp_mag(a, b) == AWS_MP_LT) {
if (d != NULL) {
res = aws_mp_copy(a, d);
} else {
res = AWS_MP_OKAY;
}
if (c != NULL) {
aws_mp_zero(c);
}
return res;
}
if ((res = aws_mp_init_size(&q, a->used + 2)) != AWS_MP_OKAY) {
return res;
}
q.used = a->used + 2;
if ((res = aws_mp_init(&t1)) != AWS_MP_OKAY) {
goto LBL_Q;
}
if ((res = aws_mp_init(&t2)) != AWS_MP_OKAY) {
goto LBL_T1;
}
if ((res = aws_mp_init_copy(&x, a)) != AWS_MP_OKAY) {
goto LBL_T2;
}
if ((res = aws_mp_init_copy(&y, b)) != AWS_MP_OKAY) {
goto LBL_X;
}
/* fix the sign */
neg = (a->sign == b->sign) ? AWS_MP_ZPOS : AWS_MP_NEG;
x.sign = y.sign = AWS_MP_ZPOS;
/* normalize both x and y, ensure that y >= b/2, [b == 2**AWS_DIGIT_BIT] */
norm = aws_mp_count_bits(&y) % AWS_DIGIT_BIT;
if (norm < (int)(AWS_DIGIT_BIT-1)) {
norm = (AWS_DIGIT_BIT-1) - norm;
if ((res = aws_mp_mul_2d(&x, norm, &x)) != AWS_MP_OKAY) {
goto LBL_Y;
}
if ((res = aws_mp_mul_2d(&y, norm, &y)) != AWS_MP_OKAY) {
goto LBL_Y;
}
} else {
norm = 0;
}
/* note hac does 0 based, so if used==5 then its 0,1,2,3,4, e.g. use 4 */
n = x.used - 1;
t = y.used - 1;
/* while (x >= y*b**n-t) do { q[n-t] += 1; x -= y*b**{n-t} } */
if ((res = aws_mp_lshd(&y, n - t)) != AWS_MP_OKAY) { /* y = y*b**{n-t} */
goto LBL_Y;
}
while (aws_mp_cmp(&x, &y) != AWS_MP_LT) {
++(q.dp[n - t]);
if ((res = aws_mp_sub(&x, &y, &x)) != AWS_MP_OKAY) {
goto LBL_Y;
}
}
/* reset y by shifting it back down */
aws_mp_rshd(&y, n - t);
/* step 3. for i from n down to (t + 1) */
for (i = n; i >= (t + 1); i--) {
if (i > x.used) {
continue;
}
/* step 3.1 if xi == yt then set q{i-t-1} to b-1,
* otherwise set q{i-t-1} to (xi*b + x{i-1})/yt */
if (x.dp[i] == y.dp[t]) {
q.dp[i - t - 1] = ((((aws_mp_digit)1) << AWS_DIGIT_BIT) - 1);
} else {
aws_mp_word tmp;
tmp = ((aws_mp_word) x.dp[i]) << ((aws_mp_word) AWS_DIGIT_BIT);
tmp |= ((aws_mp_word) x.dp[i - 1]);
tmp /= ((aws_mp_word) y.dp[t]);
if (tmp > (aws_mp_word) AWS_MP_MASK)
tmp = AWS_MP_MASK;
q.dp[i - t - 1] = (aws_mp_digit) (tmp & (aws_mp_word) (AWS_MP_MASK));
}
/* while (q{i-t-1} * (yt * b + y{t-1})) >
xi * b**2 + xi-1 * b + xi-2
do q{i-t-1} -= 1;
*/
q.dp[i - t - 1] = (q.dp[i - t - 1] + 1) & AWS_MP_MASK;
do {
q.dp[i - t - 1] = (q.dp[i - t - 1] - 1) & AWS_MP_MASK;
/* find left hand */
aws_mp_zero(&t1);
t1.dp[0] = (t - 1 < 0) ? 0 : y.dp[t - 1];
t1.dp[1] = y.dp[t];
t1.used = 2;
if ((res = aws_mp_mul_d(&t1, q.dp[i - t - 1], &t1)) != AWS_MP_OKAY) {
goto LBL_Y;
}
/* find right hand */
t2.dp[0] = (i - 2 < 0) ? 0 : x.dp[i - 2];
t2.dp[1] = (i - 1 < 0) ? 0 : x.dp[i - 1];
t2.dp[2] = x.dp[i];
t2.used = 3;
} while (aws_mp_cmp_mag(&t1, &t2) == AWS_MP_GT);
/* step 3.3 x = x - q{i-t-1} * y * b**{i-t-1} */
if ((res = aws_mp_mul_d(&y, q.dp[i - t - 1], &t1)) != AWS_MP_OKAY) {
goto LBL_Y;
}
if ((res = aws_mp_lshd(&t1, i - t - 1)) != AWS_MP_OKAY) {
goto LBL_Y;
}
if ((res = aws_mp_sub(&x, &t1, &x)) != AWS_MP_OKAY) {
goto LBL_Y;
}
/* if x < 0 then { x = x + y*b**{i-t-1}; q{i-t-1} -= 1; } */
if (x.sign == AWS_MP_NEG) {
if ((res = aws_mp_copy(&y, &t1)) != AWS_MP_OKAY) {
goto LBL_Y;
}
if ((res = aws_mp_lshd(&t1, i - t - 1)) != AWS_MP_OKAY) {
goto LBL_Y;
}
if ((res = aws_mp_add(&x, &t1, &x)) != AWS_MP_OKAY) {
goto LBL_Y;
}
q.dp[i - t - 1] = (q.dp[i - t - 1] - 1UL) & AWS_MP_MASK;
}
}
/* now q is the quotient and x is the remainder
* [which we have to normalize]
*/
/* get sign before writing to c */
x.sign = x.used == 0 ? AWS_MP_ZPOS : a->sign;
if (c != NULL) {
aws_mp_clamp(&q);
aws_mp_exch(&q, c);
c->sign = neg;
}
if (d != NULL) {
aws_mp_div_2d(&x, norm, &x, NULL);
aws_mp_exch(&x, d);
}
res = AWS_MP_OKAY;
LBL_Y:
aws_mp_clear(&y);
LBL_X:
aws_mp_clear(&x);
LBL_T2:
aws_mp_clear(&t2);
LBL_T1:
aws_mp_clear(&t1);
LBL_Q:
aws_mp_clear(&q);
return res;
}