X-Git-Url: http://git.rot13.org/?p=bcm963xx.git;a=blobdiff_plain;f=userapps%2Fopensource%2Fsshd%2Flibtommath%2Fbn_mp_div.c;h=6b2b8f0d5f2af24f0be208cb8b67d9b0c4369c36;hp=4e0f353302b269b3305afbfe3d13b258f78cb6f6;hb=57a096f051259ceaefd5977f30d269884e1dd248;hpb=a69849c98808437716b821267cd97529c56f45b0 diff --git a/userapps/opensource/sshd/libtommath/bn_mp_div.c b/userapps/opensource/sshd/libtommath/bn_mp_div.c index 4e0f3533..6b2b8f0d 100755 --- a/userapps/opensource/sshd/libtommath/bn_mp_div.c +++ b/userapps/opensource/sshd/libtommath/bn_mp_div.c @@ -1,9 +1,11 @@ +#include +#ifdef BN_MP_DIV_C /* LibTomMath, multiple-precision integer library -- Tom St Denis * - * LibTomMath is library that provides for multiple-precision + * LibTomMath is a library that provides multiple-precision * integer arithmetic as well as number theoretic functionality. * - * The library is designed directly after the MPI library by + * The library was designed directly after the MPI library by * Michael Fromberger but has been written from scratch with * additional optimizations in place. * @@ -12,7 +14,78 @@ * * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org */ -#include + +#ifdef BN_MP_DIV_SMALL + +/* slower bit-bang division... also smaller */ +int mp_div(mp_int * a, mp_int * b, mp_int * c, mp_int * d) +{ + mp_int ta, tb, tq, q; + int res, n, n2; + + /* is divisor zero ? */ + if (mp_iszero (b) == 1) { + return MP_VAL; + } + + /* if a < b then q=0, r = a */ + if (mp_cmp_mag (a, b) == MP_LT) { + if (d != NULL) { + res = mp_copy (a, d); + } else { + res = MP_OKAY; + } + if (c != NULL) { + mp_zero (c); + } + return res; + } + + /* init our temps */ + if ((res = mp_init_multi(&ta, &tb, &tq, &q, NULL) != MP_OKAY)) { + return res; + } + + + mp_set(&tq, 1); + n = mp_count_bits(a) - mp_count_bits(b); + if (((res = mp_abs(a, &ta)) != MP_OKAY) || + ((res = mp_abs(b, &tb)) != MP_OKAY) || + ((res = mp_mul_2d(&tb, n, &tb)) != MP_OKAY) || + ((res = mp_mul_2d(&tq, n, &tq)) != MP_OKAY)) { + goto LBL_ERR; + } + + while (n-- >= 0) { + if (mp_cmp(&tb, &ta) != MP_GT) { + if (((res = mp_sub(&ta, &tb, &ta)) != MP_OKAY) || + ((res = mp_add(&q, &tq, &q)) != MP_OKAY)) { + goto LBL_ERR; + } + } + if (((res = mp_div_2d(&tb, 1, &tb, NULL)) != MP_OKAY) || + ((res = mp_div_2d(&tq, 1, &tq, NULL)) != MP_OKAY)) { + goto LBL_ERR; + } + } + + /* now q == quotient and ta == remainder */ + n = a->sign; + n2 = (a->sign == b->sign ? MP_ZPOS : MP_NEG); + if (c != NULL) { + mp_exch(c, &q); + c->sign = (mp_iszero(c) == MP_YES) ? MP_ZPOS : n2; + } + if (d != NULL) { + mp_exch(d, &ta); + d->sign = (mp_iszero(d) == MP_YES) ? MP_ZPOS : n; + } +LBL_ERR: + mp_clear_multi(&ta, &tb, &tq, &q, NULL); + return res; +} + +#else /* integer signed division. * c*b + d == a [e.g. a/b, c=quotient, d=remainder] @@ -27,8 +100,7 @@ * The overall algorithm is as described as * 14.20 from HAC but fixed to treat these cases. */ -int -mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d) +int mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d) { mp_int q, x, y, t1, t2; int res, n, t, i, norm, neg; @@ -57,19 +129,19 @@ mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d) q.used = a->used + 2; if ((res = mp_init (&t1)) != MP_OKAY) { - goto __Q; + goto LBL_Q; } if ((res = mp_init (&t2)) != MP_OKAY) { - goto __T1; + goto LBL_T1; } if ((res = mp_init_copy (&x, a)) != MP_OKAY) { - goto __T2; + goto LBL_T2; } if ((res = mp_init_copy (&y, b)) != MP_OKAY) { - goto __X; + goto LBL_X; } /* fix the sign */ @@ -81,10 +153,10 @@ mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d) if (norm < (int)(DIGIT_BIT-1)) { norm = (DIGIT_BIT-1) - norm; if ((res = mp_mul_2d (&x, norm, &x)) != MP_OKAY) { - goto __Y; + goto LBL_Y; } if ((res = mp_mul_2d (&y, norm, &y)) != MP_OKAY) { - goto __Y; + goto LBL_Y; } } else { norm = 0; @@ -96,13 +168,13 @@ mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d) /* while (x >= y*b**n-t) do { q[n-t] += 1; x -= y*b**{n-t} } */ if ((res = mp_lshd (&y, n - t)) != MP_OKAY) { /* y = y*b**{n-t} */ - goto __Y; + goto LBL_Y; } while (mp_cmp (&x, &y) != MP_LT) { ++(q.dp[n - t]); if ((res = mp_sub (&x, &y, &x)) != MP_OKAY) { - goto __Y; + goto LBL_Y; } } @@ -111,8 +183,9 @@ mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d) /* step 3. for i from n down to (t + 1) */ for (i = n; i >= (t + 1); i--) { - if (i > x.used) + 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 */ @@ -143,7 +216,7 @@ mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d) t1.dp[1] = y.dp[t]; t1.used = 2; if ((res = mp_mul_d (&t1, q.dp[i - t - 1], &t1)) != MP_OKAY) { - goto __Y; + goto LBL_Y; } /* find right hand */ @@ -155,27 +228,27 @@ mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d) /* step 3.3 x = x - q{i-t-1} * y * b**{i-t-1} */ if ((res = mp_mul_d (&y, q.dp[i - t - 1], &t1)) != MP_OKAY) { - goto __Y; + goto LBL_Y; } if ((res = mp_lshd (&t1, i - t - 1)) != MP_OKAY) { - goto __Y; + goto LBL_Y; } if ((res = mp_sub (&x, &t1, &x)) != MP_OKAY) { - goto __Y; + goto LBL_Y; } /* if x < 0 then { x = x + y*b**{i-t-1}; q{i-t-1} -= 1; } */ if (x.sign == MP_NEG) { if ((res = mp_copy (&y, &t1)) != MP_OKAY) { - goto __Y; + goto LBL_Y; } if ((res = mp_lshd (&t1, i - t - 1)) != MP_OKAY) { - goto __Y; + goto LBL_Y; } if ((res = mp_add (&x, &t1, &x)) != MP_OKAY) { - goto __Y; + goto LBL_Y; } q.dp[i - t - 1] = (q.dp[i - t - 1] - 1UL) & MP_MASK; @@ -187,7 +260,7 @@ mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d) */ /* get sign before writing to c */ - x.sign = a->sign; + x.sign = x.used == 0 ? MP_ZPOS : a->sign; if (c != NULL) { mp_clamp (&q); @@ -202,10 +275,14 @@ mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d) res = MP_OKAY; -__Y:mp_clear (&y); -__X:mp_clear (&x); -__T2:mp_clear (&t2); -__T1:mp_clear (&t1); -__Q:mp_clear (&q); +LBL_Y:mp_clear (&y); +LBL_X:mp_clear (&x); +LBL_T2:mp_clear (&t2); +LBL_T1:mp_clear (&t1); +LBL_Q:mp_clear (&q); return res; } + +#endif + +#endif