1/* $NetBSD: bn_fast_s_mp_mul_high_digs.c,v 1.1.1.1 2011/04/13 18:14:54 elric Exp $ */ 2 3#include <tommath.h> 4#ifdef BN_FAST_S_MP_MUL_HIGH_DIGS_C 5/* LibTomMath, multiple-precision integer library -- Tom St Denis 6 * 7 * LibTomMath is a library that provides multiple-precision 8 * integer arithmetic as well as number theoretic functionality. 9 * 10 * The library was designed directly after the MPI library by 11 * Michael Fromberger but has been written from scratch with 12 * additional optimizations in place. 13 * 14 * The library is free for all purposes without any express 15 * guarantee it works. 16 * 17 * Tom St Denis, tomstdenis@gmail.com, http://libtom.org 18 */ 19 20/* this is a modified version of fast_s_mul_digs that only produces 21 * output digits *above* digs. See the comments for fast_s_mul_digs 22 * to see how it works. 23 * 24 * This is used in the Barrett reduction since for one of the multiplications 25 * only the higher digits were needed. This essentially halves the work. 26 * 27 * Based on Algorithm 14.12 on pp.595 of HAC. 28 */ 29int fast_s_mp_mul_high_digs (mp_int * a, mp_int * b, mp_int * c, int digs) 30{ 31 int olduse, res, pa, ix, iz; 32 mp_digit W[MP_WARRAY]; 33 mp_word _W; 34 35 /* grow the destination as required */ 36 pa = a->used + b->used; 37 if (c->alloc < pa) { 38 if ((res = mp_grow (c, pa)) != MP_OKAY) { 39 return res; 40 } 41 } 42 43 /* number of output digits to produce */ 44 pa = a->used + b->used; 45 _W = 0; 46 for (ix = digs; ix < pa; ix++) { 47 int tx, ty, iy; 48 mp_digit *tmpx, *tmpy; 49 50 /* get offsets into the two bignums */ 51 ty = MIN(b->used-1, ix); 52 tx = ix - ty; 53 54 /* setup temp aliases */ 55 tmpx = a->dp + tx; 56 tmpy = b->dp + ty; 57 58 /* this is the number of times the loop will iterrate, essentially its 59 while (tx++ < a->used && ty-- >= 0) { ... } 60 */ 61 iy = MIN(a->used-tx, ty+1); 62 63 /* execute loop */ 64 for (iz = 0; iz < iy; iz++) { 65 _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--); 66 } 67 68 /* store term */ 69 W[ix] = ((mp_digit)_W) & MP_MASK; 70 71 /* make next carry */ 72 _W = _W >> ((mp_word)DIGIT_BIT); 73 } 74 75 /* setup dest */ 76 olduse = c->used; 77 c->used = pa; 78 79 { 80 register mp_digit *tmpc; 81 82 tmpc = c->dp + digs; 83 for (ix = digs; ix < pa; ix++) { 84 /* now extract the previous digit [below the carry] */ 85 *tmpc++ = W[ix]; 86 } 87 88 /* clear unused digits [that existed in the old copy of c] */ 89 for (; ix < olduse; ix++) { 90 *tmpc++ = 0; 91 } 92 } 93 mp_clamp (c); 94 return MP_OKAY; 95} 96#endif 97 98/* Source: /cvs/libtom/libtommath/bn_fast_s_mp_mul_high_digs.c,v */ 99/* Revision: 1.6 */ 100/* Date: 2006/12/28 01:25:13 */ 101