1 /* $NetBSD: bn_s_mp_mul_high_digs.c,v 1.1.1.1 2011/04/13 18:14:55 elric Exp $ */ 2 3 #include <tommath.h> 4 #ifdef BN_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 /* multiplies |a| * |b| and does not compute the lower digs digits 21 * [meant to get the higher part of the product] 22 */ 23 int 24 s_mp_mul_high_digs (mp_int * a, mp_int * b, mp_int * c, int digs) 25 { 26 mp_int t; 27 int res, pa, pb, ix, iy; 28 mp_digit u; 29 mp_word r; 30 mp_digit tmpx, *tmpt, *tmpy; 31 32 /* can we use the fast multiplier? */ 33 #ifdef BN_FAST_S_MP_MUL_HIGH_DIGS_C 34 if (((a->used + b->used + 1) < MP_WARRAY) 35 && MIN (a->used, b->used) < (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) { 36 return fast_s_mp_mul_high_digs (a, b, c, digs); 37 } 38 #endif 39 40 if ((res = mp_init_size (&t, a->used + b->used + 1)) != MP_OKAY) { 41 return res; 42 } 43 t.used = a->used + b->used + 1; 44 45 pa = a->used; 46 pb = b->used; 47 for (ix = 0; ix < pa; ix++) { 48 /* clear the carry */ 49 u = 0; 50 51 /* left hand side of A[ix] * B[iy] */ 52 tmpx = a->dp[ix]; 53 54 /* alias to the address of where the digits will be stored */ 55 tmpt = &(t.dp[digs]); 56 57 /* alias for where to read the right hand side from */ 58 tmpy = b->dp + (digs - ix); 59 60 for (iy = digs - ix; iy < pb; iy++) { 61 /* calculate the double precision result */ 62 r = ((mp_word)*tmpt) + 63 ((mp_word)tmpx) * ((mp_word)*tmpy++) + 64 ((mp_word) u); 65 66 /* get the lower part */ 67 *tmpt++ = (mp_digit) (r & ((mp_word) MP_MASK)); 68 69 /* carry the carry */ 70 u = (mp_digit) (r >> ((mp_word) DIGIT_BIT)); 71 } 72 *tmpt = u; 73 } 74 mp_clamp (&t); 75 mp_exch (&t, c); 76 mp_clear (&t); 77 return MP_OKAY; 78 } 79 #endif 80 81 /* Source: /cvs/libtom/libtommath/bn_s_mp_mul_high_digs.c,v */ 82 /* Revision: 1.4 */ 83 /* Date: 2006/12/28 01:25:13 */ 84