## Mercurial > dropbear

### view libtommath/bn_fast_s_mp_mul_high_digs.c @ 350:01e4180895ba

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

merge of '9a4e042fd565f46141e81e0c1ab90260303348fe'
and 'bea3887a5875cf3ab8a1331e15e698b37b61fe37'

author | Matt Johnston <matt@ucc.asn.au> |
---|---|

date | Mon, 07 Aug 2006 13:41:23 +0000 |

parents | eed26cff980b |

children | 5ff8218bcee9 |

line wrap: on

line source

#include <tommath.h> #ifdef BN_FAST_S_MP_MUL_HIGH_DIGS_C /* LibTomMath, multiple-precision integer library -- Tom St Denis * * LibTomMath is a library that provides multiple-precision * integer arithmetic as well as number theoretic functionality. * * The library was designed directly after the MPI library by * Michael Fromberger but has been written from scratch with * additional optimizations in place. * * The library is free for all purposes without any express * guarantee it works. * * Tom St Denis, [email protected], http://math.libtomcrypt.org */ /* this is a modified version of fast_s_mul_digs that only produces * output digits *above* digs. See the comments for fast_s_mul_digs * to see how it works. * * This is used in the Barrett reduction since for one of the multiplications * only the higher digits were needed. This essentially halves the work. * * Based on Algorithm 14.12 on pp.595 of HAC. */ int fast_s_mp_mul_high_digs (mp_int * a, mp_int * b, mp_int * c, int digs) { int olduse, res, pa, ix, iz; mp_digit W[MP_WARRAY]; mp_word _W; /* grow the destination as required */ pa = a->used + b->used; if (c->alloc < pa) { if ((res = mp_grow (c, pa)) != MP_OKAY) { return res; } } /* number of output digits to produce */ pa = a->used + b->used; _W = 0; for (ix = digs; ix < pa; ix++) { int tx, ty, iy; mp_digit *tmpx, *tmpy; /* get offsets into the two bignums */ ty = MIN(b->used-1, ix); tx = ix - ty; /* setup temp aliases */ tmpx = a->dp + tx; tmpy = b->dp + ty; /* this is the number of times the loop will iterrate, essentially its while (tx++ < a->used && ty-- >= 0) { ... } */ iy = MIN(a->used-tx, ty+1); /* execute loop */ for (iz = 0; iz < iy; iz++) { _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--); } /* store term */ W[ix] = ((mp_digit)_W) & MP_MASK; /* make next carry */ _W = _W >> ((mp_word)DIGIT_BIT); } /* store final carry */ W[ix] = (mp_digit)(_W & MP_MASK); /* setup dest */ olduse = c->used; c->used = pa; { register mp_digit *tmpc; tmpc = c->dp + digs; for (ix = digs; ix <= pa; ix++) { /* now extract the previous digit [below the carry] */ *tmpc++ = W[ix]; } /* clear unused digits [that existed in the old copy of c] */ for (; ix < olduse; ix++) { *tmpc++ = 0; } } mp_clamp (c); return MP_OKAY; } #endif