1f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#include <tommath.h> 2f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#ifdef BN_MP_DIV_C 3f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* LibTomMath, multiple-precision integer library -- Tom St Denis 4f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 5f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * LibTomMath is a library that provides multiple-precision 6f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * integer arithmetic as well as number theoretic functionality. 7f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 8f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * The library was designed directly after the MPI library by 9f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Michael Fromberger but has been written from scratch with 10f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * additional optimizations in place. 11f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 12f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * The library is free for all purposes without any express 13f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * guarantee it works. 14f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 15f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com 16f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 17f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 18f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#ifdef BN_MP_DIV_SMALL 19f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 20f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* slower bit-bang division... also smaller */ 21f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_div(mp_int * a, mp_int * b, mp_int * c, mp_int * d) 22f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project{ 23f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int ta, tb, tq, q; 24f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int res, n, n2; 25f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 26f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* is divisor zero ? */ 27f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_iszero (b) == 1) { 28f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return MP_VAL; 29f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 30f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 31f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* if a < b then q=0, r = a */ 32f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_cmp_mag (a, b) == MP_LT) { 33f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (d != NULL) { 34f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project res = mp_copy (a, d); 35f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } else { 36f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project res = MP_OKAY; 37f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 38f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (c != NULL) { 39f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_zero (c); 40f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 41f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return res; 42f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 43f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 44f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* init our temps */ 45f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_init_multi(&ta, &tb, &tq, &q, NULL) != MP_OKAY)) { 46f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return res; 47f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 48f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 49f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 50f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_set(&tq, 1); 51f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project n = mp_count_bits(a) - mp_count_bits(b); 52f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (((res = mp_abs(a, &ta)) != MP_OKAY) || 53f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project ((res = mp_abs(b, &tb)) != MP_OKAY) || 54f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project ((res = mp_mul_2d(&tb, n, &tb)) != MP_OKAY) || 55f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project ((res = mp_mul_2d(&tq, n, &tq)) != MP_OKAY)) { 56f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_ERR; 57f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 58f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 59f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project while (n-- >= 0) { 60f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_cmp(&tb, &ta) != MP_GT) { 61f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (((res = mp_sub(&ta, &tb, &ta)) != MP_OKAY) || 62f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project ((res = mp_add(&q, &tq, &q)) != MP_OKAY)) { 63f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_ERR; 64f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 65f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 66f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (((res = mp_div_2d(&tb, 1, &tb, NULL)) != MP_OKAY) || 67f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project ((res = mp_div_2d(&tq, 1, &tq, NULL)) != MP_OKAY)) { 68f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_ERR; 69f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 70f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 71f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 72f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now q == quotient and ta == remainder */ 73f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project n = a->sign; 74f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project n2 = (a->sign == b->sign ? MP_ZPOS : MP_NEG); 75f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (c != NULL) { 76f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_exch(c, &q); 77f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project c->sign = (mp_iszero(c) == MP_YES) ? MP_ZPOS : n2; 78f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 79f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (d != NULL) { 80f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_exch(d, &ta); 81f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project d->sign = (mp_iszero(d) == MP_YES) ? MP_ZPOS : n; 82f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 83f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_ERR: 84f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear_multi(&ta, &tb, &tq, &q, NULL); 85f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return res; 86f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project} 87f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 88f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#else 89f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 90f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* integer signed division. 91f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * c*b + d == a [e.g. a/b, c=quotient, d=remainder] 92f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * HAC pp.598 Algorithm 14.20 93f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 94f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Note that the description in HAC is horribly 95f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * incomplete. For example, it doesn't consider 96f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * the case where digits are removed from 'x' in 97f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * the inner loop. It also doesn't consider the 98f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * case that y has fewer than three digits, etc.. 99f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 100f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * The overall algorithm is as described as 101f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 14.20 from HAC but fixed to treat these cases. 102f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project*/ 103f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d) 104f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project{ 105f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int q, x, y, t1, t2; 106f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int res, n, t, i, norm, neg; 107f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 108f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* is divisor zero ? */ 109f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_iszero (b) == 1) { 110f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return MP_VAL; 111f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 112f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 113f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* if a < b then q=0, r = a */ 114f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_cmp_mag (a, b) == MP_LT) { 115f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (d != NULL) { 116f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project res = mp_copy (a, d); 117f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } else { 118f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project res = MP_OKAY; 119f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 120f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (c != NULL) { 121f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_zero (c); 122f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 123f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return res; 124f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 125f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 126f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_init_size (&q, a->used + 2)) != MP_OKAY) { 127f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return res; 128f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 129f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project q.used = a->used + 2; 130f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 131f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_init (&t1)) != MP_OKAY) { 132f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Q; 133f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 134f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 135f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_init (&t2)) != MP_OKAY) { 136f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_T1; 137f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 138f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 139f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_init_copy (&x, a)) != MP_OKAY) { 140f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_T2; 141f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 142f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 143f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_init_copy (&y, b)) != MP_OKAY) { 144f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_X; 145f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 146f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 147f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* fix the sign */ 148f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project neg = (a->sign == b->sign) ? MP_ZPOS : MP_NEG; 149f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x.sign = y.sign = MP_ZPOS; 150f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 151f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* normalize both x and y, ensure that y >= b/2, [b == 2**DIGIT_BIT] */ 152f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project norm = mp_count_bits(&y) % DIGIT_BIT; 153f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (norm < (int)(DIGIT_BIT-1)) { 154f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project norm = (DIGIT_BIT-1) - norm; 155f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul_2d (&x, norm, &x)) != MP_OKAY) { 156f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Y; 157f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 158f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul_2d (&y, norm, &y)) != MP_OKAY) { 159f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Y; 160f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 161f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } else { 162f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project norm = 0; 163f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 164f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 165f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* note hac does 0 based, so if used==5 then its 0,1,2,3,4, e.g. use 4 */ 166f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project n = x.used - 1; 167f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project t = y.used - 1; 168f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 169f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* while (x >= y*b**n-t) do { q[n-t] += 1; x -= y*b**{n-t} } */ 170f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_lshd (&y, n - t)) != MP_OKAY) { /* y = y*b**{n-t} */ 171f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Y; 172f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 173f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 174f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project while (mp_cmp (&x, &y) != MP_LT) { 175f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project ++(q.dp[n - t]); 176f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_sub (&x, &y, &x)) != MP_OKAY) { 177f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Y; 178f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 179f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 180f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 181f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* reset y by shifting it back down */ 182f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_rshd (&y, n - t); 183f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 184f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* step 3. for i from n down to (t + 1) */ 185f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (i = n; i >= (t + 1); i--) { 186f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (i > x.used) { 187f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 188f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 189f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 190f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* step 3.1 if xi == yt then set q{i-t-1} to b-1, 191f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * otherwise set q{i-t-1} to (xi*b + x{i-1})/yt */ 192f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (x.dp[i] == y.dp[t]) { 193f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project q.dp[i - t - 1] = ((((mp_digit)1) << DIGIT_BIT) - 1); 194f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } else { 195f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_word tmp; 196f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project tmp = ((mp_word) x.dp[i]) << ((mp_word) DIGIT_BIT); 197f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project tmp |= ((mp_word) x.dp[i - 1]); 198f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project tmp /= ((mp_word) y.dp[t]); 199f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (tmp > (mp_word) MP_MASK) 200f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project tmp = MP_MASK; 201f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project q.dp[i - t - 1] = (mp_digit) (tmp & (mp_word) (MP_MASK)); 202f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 203f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 204f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* while (q{i-t-1} * (yt * b + y{t-1})) > 205f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project xi * b**2 + xi-1 * b + xi-2 206f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 207f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project do q{i-t-1} -= 1; 208f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 209f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project q.dp[i - t - 1] = (q.dp[i - t - 1] + 1) & MP_MASK; 210f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project do { 211f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project q.dp[i - t - 1] = (q.dp[i - t - 1] - 1) & MP_MASK; 212f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 213f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* find left hand */ 214f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_zero (&t1); 215f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project t1.dp[0] = (t - 1 < 0) ? 0 : y.dp[t - 1]; 216f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project t1.dp[1] = y.dp[t]; 217f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project t1.used = 2; 218f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul_d (&t1, q.dp[i - t - 1], &t1)) != MP_OKAY) { 219f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Y; 220f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 221f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 222f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* find right hand */ 223f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project t2.dp[0] = (i - 2 < 0) ? 0 : x.dp[i - 2]; 224f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project t2.dp[1] = (i - 1 < 0) ? 0 : x.dp[i - 1]; 225f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project t2.dp[2] = x.dp[i]; 226f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project t2.used = 3; 227f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } while (mp_cmp_mag(&t1, &t2) == MP_GT); 228f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 229f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* step 3.3 x = x - q{i-t-1} * y * b**{i-t-1} */ 230f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul_d (&y, q.dp[i - t - 1], &t1)) != MP_OKAY) { 231f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Y; 232f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 233f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 234f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_lshd (&t1, i - t - 1)) != MP_OKAY) { 235f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Y; 236f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 237f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 238f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_sub (&x, &t1, &x)) != MP_OKAY) { 239f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Y; 240f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 241f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 242f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* if x < 0 then { x = x + y*b**{i-t-1}; q{i-t-1} -= 1; } */ 243f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (x.sign == MP_NEG) { 244f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_copy (&y, &t1)) != MP_OKAY) { 245f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Y; 246f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 247f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_lshd (&t1, i - t - 1)) != MP_OKAY) { 248f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Y; 249f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 250f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_add (&x, &t1, &x)) != MP_OKAY) { 251f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Y; 252f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 253f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 254f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project q.dp[i - t - 1] = (q.dp[i - t - 1] - 1UL) & MP_MASK; 255f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 256f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 257f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 258f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now q is the quotient and x is the remainder 259f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * [which we have to normalize] 260f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 261f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 262f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* get sign before writing to c */ 263f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x.sign = x.used == 0 ? MP_ZPOS : a->sign; 264f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 265f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (c != NULL) { 266f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clamp (&q); 267f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_exch (&q, c); 268f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project c->sign = neg; 269f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 270f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 271f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (d != NULL) { 272f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_div_2d (&x, norm, &x, NULL)) != MP_OKAY) { 273f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Y; 274f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 275f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_exch (&x, d); 276f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 277f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 278f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project res = MP_OKAY; 279f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 280f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_Y:mp_clear (&y); 281f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_X:mp_clear (&x); 282f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_T2:mp_clear (&t2); 283f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_T1:mp_clear (&t1); 284f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_Q:mp_clear (&q); 285f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return res; 286f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project} 287f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 288f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#endif 289f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 290f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#endif 291f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 292f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Source: /cvs/libtom/libtommath/bn_mp_div.c,v $ */ 293f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Revision: 1.3 $ */ 294f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Date: 2006/03/31 14:18:44 $ */ 295