1f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#include <tommath.h> 2f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#ifdef BN_MP_TOOM_MUL_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/* multiplication using the Toom-Cook 3-way algorithm 19f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 20f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Much more complicated than Karatsuba but has a lower 21f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * asymptotic running time of O(N**1.464). This algorithm is 22f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * only particularly useful on VERY large inputs 23f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * (we're talking 1000s of digits here...). 24f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project*/ 25f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_toom_mul(mp_int *a, mp_int *b, mp_int *c) 26f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project{ 27f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int w0, w1, w2, w3, w4, tmp1, tmp2, a0, a1, a2, b0, b1, b2; 28f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int res, B; 29f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 30f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* init temps */ 31f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_init_multi(&w0, &w1, &w2, &w3, &w4, 32f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project &a0, &a1, &a2, &b0, &b1, 33f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project &b2, &tmp1, &tmp2, NULL)) != MP_OKAY) { 34f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return res; 35f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 36f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 37f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* B */ 38f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project B = MIN(a->used, b->used) / 3; 39f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 40f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* a = a2 * B**2 + a1 * B + a0 */ 41f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mod_2d(a, DIGIT_BIT * B, &a0)) != MP_OKAY) { 42f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 43f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 44f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 45f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_copy(a, &a1)) != MP_OKAY) { 46f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 47f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 48f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_rshd(&a1, B); 49f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_mod_2d(&a1, DIGIT_BIT * B, &a1); 50f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 51f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_copy(a, &a2)) != MP_OKAY) { 52f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 53f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 54f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_rshd(&a2, B*2); 55f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 56f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* b = b2 * B**2 + b1 * B + b0 */ 57f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mod_2d(b, DIGIT_BIT * B, &b0)) != MP_OKAY) { 58f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 59f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 60f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 61f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_copy(b, &b1)) != MP_OKAY) { 62f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 63f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 64f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_rshd(&b1, B); 65f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_mod_2d(&b1, DIGIT_BIT * B, &b1); 66f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 67f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_copy(b, &b2)) != MP_OKAY) { 68f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 69f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 70f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_rshd(&b2, B*2); 71f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 72f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* w0 = a0*b0 */ 73f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul(&a0, &b0, &w0)) != MP_OKAY) { 74f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 75f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 76f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 77f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* w4 = a2 * b2 */ 78f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul(&a2, &b2, &w4)) != MP_OKAY) { 79f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 80f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 81f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 82f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* w1 = (a2 + 2(a1 + 2a0))(b2 + 2(b1 + 2b0)) */ 83f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul_2(&a0, &tmp1)) != MP_OKAY) { 84f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 85f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 86f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_add(&tmp1, &a1, &tmp1)) != MP_OKAY) { 87f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 88f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 89f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul_2(&tmp1, &tmp1)) != MP_OKAY) { 90f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 91f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 92f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_add(&tmp1, &a2, &tmp1)) != MP_OKAY) { 93f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 94f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 95f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 96f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul_2(&b0, &tmp2)) != MP_OKAY) { 97f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 98f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 99f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_add(&tmp2, &b1, &tmp2)) != MP_OKAY) { 100f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 101f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 102f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul_2(&tmp2, &tmp2)) != MP_OKAY) { 103f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 104f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 105f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_add(&tmp2, &b2, &tmp2)) != MP_OKAY) { 106f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 107f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 108f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 109f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul(&tmp1, &tmp2, &w1)) != MP_OKAY) { 110f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 111f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 112f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 113f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* w3 = (a0 + 2(a1 + 2a2))(b0 + 2(b1 + 2b2)) */ 114f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul_2(&a2, &tmp1)) != MP_OKAY) { 115f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 116f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 117f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_add(&tmp1, &a1, &tmp1)) != MP_OKAY) { 118f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 119f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 120f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul_2(&tmp1, &tmp1)) != MP_OKAY) { 121f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 122f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 123f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_add(&tmp1, &a0, &tmp1)) != MP_OKAY) { 124f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 125f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 126f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 127f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul_2(&b2, &tmp2)) != MP_OKAY) { 128f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 129f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 130f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_add(&tmp2, &b1, &tmp2)) != MP_OKAY) { 131f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 132f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 133f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul_2(&tmp2, &tmp2)) != MP_OKAY) { 134f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 135f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 136f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_add(&tmp2, &b0, &tmp2)) != MP_OKAY) { 137f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 138f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 139f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 140f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul(&tmp1, &tmp2, &w3)) != MP_OKAY) { 141f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 142f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 143f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 144f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 145f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* w2 = (a2 + a1 + a0)(b2 + b1 + b0) */ 146f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_add(&a2, &a1, &tmp1)) != MP_OKAY) { 147f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 148f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 149f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_add(&tmp1, &a0, &tmp1)) != MP_OKAY) { 150f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 151f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 152f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_add(&b2, &b1, &tmp2)) != MP_OKAY) { 153f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 154f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 155f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_add(&tmp2, &b0, &tmp2)) != MP_OKAY) { 156f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 157f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 158f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul(&tmp1, &tmp2, &w2)) != MP_OKAY) { 159f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 160f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 161f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 162f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now solve the matrix 163f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 164f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 0 0 0 0 1 165f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1 2 4 8 16 166f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1 1 1 1 1 167f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 16 8 4 2 1 168f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 1 0 0 0 0 169f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 170f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project using 12 subtractions, 4 shifts, 171f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 2 small divisions and 1 small multiplication 172f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 173f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 174f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* r1 - r4 */ 175f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_sub(&w1, &w4, &w1)) != MP_OKAY) { 176f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 177f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 178f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* r3 - r0 */ 179f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_sub(&w3, &w0, &w3)) != MP_OKAY) { 180f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 181f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 182f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* r1/2 */ 183f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_div_2(&w1, &w1)) != MP_OKAY) { 184f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 185f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 186f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* r3/2 */ 187f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_div_2(&w3, &w3)) != MP_OKAY) { 188f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 189f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 190f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* r2 - r0 - r4 */ 191f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_sub(&w2, &w0, &w2)) != MP_OKAY) { 192f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 193f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 194f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_sub(&w2, &w4, &w2)) != MP_OKAY) { 195f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 196f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 197f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* r1 - r2 */ 198f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_sub(&w1, &w2, &w1)) != MP_OKAY) { 199f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 200f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 201f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* r3 - r2 */ 202f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_sub(&w3, &w2, &w3)) != MP_OKAY) { 203f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 204f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 205f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* r1 - 8r0 */ 206f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul_2d(&w0, 3, &tmp1)) != MP_OKAY) { 207f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 208f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 209f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_sub(&w1, &tmp1, &w1)) != MP_OKAY) { 210f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 211f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 212f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* r3 - 8r4 */ 213f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul_2d(&w4, 3, &tmp1)) != MP_OKAY) { 214f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 215f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 216f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_sub(&w3, &tmp1, &w3)) != MP_OKAY) { 217f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 218f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 219f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* 3r2 - r1 - r3 */ 220f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul_d(&w2, 3, &w2)) != MP_OKAY) { 221f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 222f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 223f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_sub(&w2, &w1, &w2)) != MP_OKAY) { 224f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 225f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 226f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_sub(&w2, &w3, &w2)) != MP_OKAY) { 227f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 228f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 229f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* r1 - r2 */ 230f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_sub(&w1, &w2, &w1)) != MP_OKAY) { 231f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 232f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 233f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* r3 - r2 */ 234f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_sub(&w3, &w2, &w3)) != MP_OKAY) { 235f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 236f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 237f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* r1/3 */ 238f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_div_3(&w1, &w1, NULL)) != MP_OKAY) { 239f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 240f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 241f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* r3/3 */ 242f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_div_3(&w3, &w3, NULL)) != MP_OKAY) { 243f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 244f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 245f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 246f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* at this point shift W[n] by B*n */ 247f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_lshd(&w1, 1*B)) != MP_OKAY) { 248f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 249f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 250f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_lshd(&w2, 2*B)) != MP_OKAY) { 251f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 252f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 253f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_lshd(&w3, 3*B)) != MP_OKAY) { 254f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 255f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 256f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_lshd(&w4, 4*B)) != MP_OKAY) { 257f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 258f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 259f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 260f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_add(&w0, &w1, c)) != MP_OKAY) { 261f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 262f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 263f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_add(&w2, &w3, &tmp1)) != MP_OKAY) { 264f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 265f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 266f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_add(&w4, &tmp1, &tmp1)) != MP_OKAY) { 267f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 268f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 269f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_add(&tmp1, c, c)) != MP_OKAY) { 270f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 271f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 272f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 273f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectERR: 274f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear_multi(&w0, &w1, &w2, &w3, &w4, 275f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project &a0, &a1, &a2, &b0, &b1, 276f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project &b2, &tmp1, &tmp2, NULL); 277f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return res; 278f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project} 279f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 280f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#endif 281f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 282f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Source: /cvs/libtom/libtommath/bn_mp_toom_mul.c,v $ */ 283f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Revision: 1.3 $ */ 284f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Date: 2006/03/31 14:18:44 $ */ 285