moritz/libtommath forked from libtom/libtommath

Subversion checkout URL

You can clone with
or
.
Fetching contributors…

Cannot retrieve contributors at this time

99 lines (86 sloc) 2.812 kB
 /* 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, tomstdenis@iahu.ca, http://math.libtomcrypt.org */ #include /* this is a modified version of fast_s_mp_mul_digs that only produces * output digits *above* digs. See the comments for fast_s_mp_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 oldused, newused, res, pa, pb, ix; mp_word W[MP_WARRAY]; /* calculate size of product and allocate more space if required */ newused = a->used + b->used + 1; if (c->alloc < newused) { if ((res = mp_grow (c, newused)) != MP_OKAY) { return res; } } /* like the other comba method we compute the columns first */ pa = a->used; pb = b->used; memset (W + digs, 0, (pa + pb + 1 - digs) * sizeof (mp_word)); for (ix = 0; ix < pa; ix++) { { register mp_digit tmpx, *tmpy; register int iy; register mp_word *_W; /* work todo, that is we only calculate digits that are at "digs" or above */ iy = digs - ix; /* copy of word on the left of A[ix] * B[iy] */ tmpx = a->dp[ix]; /* alias for right side */ tmpy = b->dp + iy; /* alias for the columns of output. Offset to be equal to or above the * smallest digit place requested */ _W = W + digs; /* skip cases below zero where ix > digs */ if (iy < 0) { iy = abs(iy); tmpy += iy; _W += iy; iy = 0; } /* compute column products for digits above the minimum */ for (; iy < pb; iy++) { *_W++ += ((mp_word) tmpx) * ((mp_word)*tmpy++); } } } /* setup dest */ oldused = c->used; c->used = newused; /* now convert the array W downto what we need * * See comments in bn_fast_s_mp_mul_digs.c */ for (ix = digs + 1; ix < newused; ix++) { W[ix] += (W[ix - 1] >> ((mp_word) DIGIT_BIT)); c->dp[ix - 1] = (mp_digit) (W[ix - 1] & ((mp_word) MP_MASK)); } c->dp[newused - 1] = (mp_digit) (W[newused - 1] & ((mp_word) MP_MASK)); for (; ix < oldused; ix++) { c->dp[ix] = 0; } mp_clamp (c); return MP_OKAY; }
Something went wrong with that request. Please try again.