Mercurial > dropbear
annotate bn_fast_s_mp_sqr.c @ 200:c5c969ed76f3 libtommath
propagate from branch 'au.asn.ucc.matt.ltm-orig' (head 7fa10cba9535de3461cedb14b877c24858826204)
to branch 'au.asn.ucc.matt.dropbear.ltm' (head fc26f60de0370ab0a281fa41a2d13fb17c9d90a8)
| author | Matt Johnston <matt@ucc.asn.au> |
|---|---|
| date | Wed, 11 May 2005 16:15:27 +0000 |
| parents | d8254fc979e9 |
| children |
| rev | line source |
|---|---|
| 142 | 1 #include <tommath.h> |
| 2 #ifdef BN_FAST_S_MP_SQR_C | |
| 2 | 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
| 4 * | |
| 5 * LibTomMath is a library that provides multiple-precision | |
| 6 * integer arithmetic as well as number theoretic functionality. | |
| 7 * | |
| 8 * The library was designed directly after the MPI library by | |
| 9 * Michael Fromberger but has been written from scratch with | |
| 10 * additional optimizations in place. | |
| 11 * | |
| 12 * The library is free for all purposes without any express | |
| 13 * guarantee it works. | |
| 14 * | |
| 15 * Tom St Denis, [email protected], http://math.libtomcrypt.org | |
| 16 */ | |
| 17 | |
| 142 | 18 /* the jist of squaring... |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
19 * you do like mult except the offset of the tmpx [one that |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
20 * starts closer to zero] can't equal the offset of tmpy. |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
21 * So basically you set up iy like before then you min it with |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
22 * (ty-tx) so that it never happens. You double all those |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
23 * you add in the inner loop |
| 142 | 24 |
| 25 After that loop you do the squares and add them in. | |
| 26 */ | |
| 27 | |
| 2 | 28 int fast_s_mp_sqr (mp_int * a, mp_int * b) |
| 29 { | |
| 142 | 30 int olduse, res, pa, ix, iz; |
| 31 mp_digit W[MP_WARRAY], *tmpx; | |
| 32 mp_word W1; | |
| 2 | 33 |
| 142 | 34 /* grow the destination as required */ |
| 35 pa = a->used + a->used; | |
| 36 if (b->alloc < pa) { | |
| 37 if ((res = mp_grow (b, pa)) != MP_OKAY) { | |
| 2 | 38 return res; |
| 39 } | |
| 40 } | |
| 41 | |
| 142 | 42 /* number of output digits to produce */ |
| 43 W1 = 0; | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
44 for (ix = 0; ix < pa; ix++) { |
| 142 | 45 int tx, ty, iy; |
| 46 mp_word _W; | |
| 47 mp_digit *tmpy; | |
| 48 | |
| 49 /* clear counter */ | |
| 50 _W = 0; | |
| 51 | |
| 52 /* get offsets into the two bignums */ | |
| 53 ty = MIN(a->used-1, ix); | |
| 54 tx = ix - ty; | |
| 55 | |
| 56 /* setup temp aliases */ | |
| 57 tmpx = a->dp + tx; | |
| 58 tmpy = a->dp + ty; | |
| 59 | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
60 /* this is the number of times the loop will iterrate, essentially |
| 142 | 61 while (tx++ < a->used && ty-- >= 0) { ... } |
| 62 */ | |
| 63 iy = MIN(a->used-tx, ty+1); | |
| 2 | 64 |
| 142 | 65 /* now for squaring tx can never equal ty |
| 66 * we halve the distance since they approach at a rate of 2x | |
| 67 * and we have to round because odd cases need to be executed | |
| 68 */ | |
| 69 iy = MIN(iy, (ty-tx+1)>>1); | |
| 70 | |
| 71 /* execute loop */ | |
| 72 for (iz = 0; iz < iy; iz++) { | |
| 73 _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--); | |
| 74 } | |
| 2 | 75 |
| 142 | 76 /* double the inner product and add carry */ |
| 77 _W = _W + _W + W1; | |
| 2 | 78 |
| 142 | 79 /* even columns have the square term in them */ |
| 80 if ((ix&1) == 0) { | |
| 81 _W += ((mp_word)a->dp[ix>>1])*((mp_word)a->dp[ix>>1]); | |
| 82 } | |
| 2 | 83 |
| 142 | 84 /* store it */ |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
85 W[ix] = (mp_digit)(_W & MP_MASK); |
| 142 | 86 |
| 87 /* make next carry */ | |
| 88 W1 = _W >> ((mp_word)DIGIT_BIT); | |
| 2 | 89 } |
| 90 | |
| 91 /* setup dest */ | |
| 92 olduse = b->used; | |
| 142 | 93 b->used = a->used+a->used; |
| 2 | 94 |
| 95 { | |
| 142 | 96 mp_digit *tmpb; |
| 2 | 97 tmpb = b->dp; |
| 142 | 98 for (ix = 0; ix < pa; ix++) { |
| 99 *tmpb++ = W[ix] & MP_MASK; | |
| 100 } | |
| 2 | 101 |
| 142 | 102 /* clear unused digits [that existed in the old copy of c] */ |
| 2 | 103 for (; ix < olduse; ix++) { |
| 104 *tmpb++ = 0; | |
| 105 } | |
| 106 } | |
| 107 mp_clamp (b); | |
| 108 return MP_OKAY; | |
| 109 } | |
| 142 | 110 #endif |