Mercurial > dropbear
annotate bn_fast_s_mp_mul_high_digs.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_MUL_HIGH_DIGS_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 /* this is a modified version of fast_s_mul_digs that only produces |
| 19 * output digits *above* digs. See the comments for fast_s_mul_digs | |
| 2 | 20 * to see how it works. |
| 21 * | |
| 22 * This is used in the Barrett reduction since for one of the multiplications | |
| 23 * only the higher digits were needed. This essentially halves the work. | |
| 24 * | |
| 25 * Based on Algorithm 14.12 on pp.595 of HAC. | |
| 26 */ | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
27 int fast_s_mp_mul_high_digs (mp_int * a, mp_int * b, mp_int * c, int digs) |
| 2 | 28 { |
| 142 | 29 int olduse, res, pa, ix, iz; |
| 30 mp_digit W[MP_WARRAY]; | |
| 31 mp_word _W; | |
| 2 | 32 |
| 142 | 33 /* grow the destination as required */ |
| 34 pa = a->used + b->used; | |
| 35 if (c->alloc < pa) { | |
| 36 if ((res = mp_grow (c, pa)) != MP_OKAY) { | |
| 2 | 37 return res; |
| 38 } | |
| 39 } | |
| 40 | |
| 142 | 41 /* number of output digits to produce */ |
| 42 pa = a->used + b->used; | |
| 43 _W = 0; | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
44 for (ix = digs; ix < pa; ix++) { |
| 142 | 45 int tx, ty, iy; |
| 46 mp_digit *tmpx, *tmpy; | |
| 2 | 47 |
| 142 | 48 /* get offsets into the two bignums */ |
| 49 ty = MIN(b->used-1, ix); | |
| 50 tx = ix - ty; | |
| 2 | 51 |
| 142 | 52 /* setup temp aliases */ |
| 53 tmpx = a->dp + tx; | |
| 54 tmpy = b->dp + ty; | |
| 2 | 55 |
| 142 | 56 /* this is the number of times the loop will iterrate, essentially its |
| 57 while (tx++ < a->used && ty-- >= 0) { ... } | |
| 2 | 58 */ |
| 142 | 59 iy = MIN(a->used-tx, ty+1); |
| 60 | |
| 61 /* execute loop */ | |
| 62 for (iz = 0; iz < iy; iz++) { | |
| 63 _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--); | |
| 2 | 64 } |
| 65 | |
| 142 | 66 /* store term */ |
| 67 W[ix] = ((mp_digit)_W) & MP_MASK; | |
| 68 | |
| 69 /* make next carry */ | |
| 70 _W = _W >> ((mp_word)DIGIT_BIT); | |
| 2 | 71 } |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
72 |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
73 /* store final carry */ |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
74 W[ix] = (mp_digit)(_W & MP_MASK); |
| 2 | 75 |
| 76 /* setup dest */ | |
| 142 | 77 olduse = c->used; |
| 78 c->used = pa; | |
| 79 | |
| 80 { | |
| 81 register mp_digit *tmpc; | |
| 2 | 82 |
| 142 | 83 tmpc = c->dp + digs; |
| 84 for (ix = digs; ix <= pa; ix++) { | |
| 85 /* now extract the previous digit [below the carry] */ | |
| 86 *tmpc++ = W[ix]; | |
| 87 } | |
| 2 | 88 |
| 142 | 89 /* clear unused digits [that existed in the old copy of c] */ |
| 90 for (; ix < olduse; ix++) { | |
| 91 *tmpc++ = 0; | |
| 92 } | |
| 2 | 93 } |
| 94 mp_clamp (c); | |
| 95 return MP_OKAY; | |
| 96 } | |
| 142 | 97 #endif |