1f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#include <tommath.h> 2f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#ifdef BN_FAST_S_MP_SQR_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/* the jist of squaring... 19f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * you do like mult except the offset of the tmpx [one that 20f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * starts closer to zero] can't equal the offset of tmpy. 21f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * So basically you set up iy like before then you min it with 22f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * (ty-tx) so that it never happens. You double all those 23f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * you add in the inner loop 24f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 25f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectAfter that loop you do the squares and add them in. 26f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project*/ 27f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 28f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint fast_s_mp_sqr (mp_int * a, mp_int * b) 29f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project{ 30f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int olduse, res, pa, ix, iz; 31f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_digit W[MP_WARRAY], *tmpx; 32f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_word W1; 33f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 34f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* grow the destination as required */ 35f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project pa = a->used + a->used; 36f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (b->alloc < pa) { 37f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_grow (b, pa)) != MP_OKAY) { 38f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return res; 39f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 40f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 41f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 42f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* number of output digits to produce */ 43f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project W1 = 0; 44f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (ix = 0; ix < pa; ix++) { 45f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int tx, ty, iy; 46f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_word _W; 47f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_digit *tmpy; 48f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 49f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* clear counter */ 50f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project _W = 0; 51f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 52f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* get offsets into the two bignums */ 53f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project ty = MIN(a->used-1, ix); 54f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project tx = ix - ty; 55f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 56f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* setup temp aliases */ 57f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project tmpx = a->dp + tx; 58f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project tmpy = a->dp + ty; 59f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 60f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* this is the number of times the loop will iterrate, essentially 61f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project while (tx++ < a->used && ty-- >= 0) { ... } 62f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 63f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project iy = MIN(a->used-tx, ty+1); 64f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 65f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now for squaring tx can never equal ty 66f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * we halve the distance since they approach at a rate of 2x 67f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * and we have to round because odd cases need to be executed 68f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 69f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project iy = MIN(iy, (ty-tx+1)>>1); 70f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 71f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* execute loop */ 72f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (iz = 0; iz < iy; iz++) { 73f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--); 74f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 75f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 76f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* double the inner product and add carry */ 77f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project _W = _W + _W + W1; 78f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 79f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* even columns have the square term in them */ 80f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((ix&1) == 0) { 81f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project _W += ((mp_word)a->dp[ix>>1])*((mp_word)a->dp[ix>>1]); 82f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 83f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 84f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* store it */ 85f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project W[ix] = (mp_digit)(_W & MP_MASK); 86f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 87f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* make next carry */ 88f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project W1 = _W >> ((mp_word)DIGIT_BIT); 89f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 90f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 91f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* setup dest */ 92f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project olduse = b->used; 93f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project b->used = a->used+a->used; 94f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 95f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project { 96f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_digit *tmpb; 97f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project tmpb = b->dp; 98f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (ix = 0; ix < pa; ix++) { 99f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project *tmpb++ = W[ix] & MP_MASK; 100f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 101f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 102f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* clear unused digits [that existed in the old copy of c] */ 103f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (; ix < olduse; ix++) { 104f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project *tmpb++ = 0; 105f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 106f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 107f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clamp (b); 108f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return MP_OKAY; 109f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project} 110f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#endif 111f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 112f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Source: /cvs/libtom/libtommath/bn_fast_s_mp_sqr.c,v $ */ 113f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Revision: 1.3 $ */ 114f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Date: 2006/03/31 14:18:44 $ */ 115