1/* $NetBSD: bn_s_mp_mul_digs.c,v 1.2 2017/01/28 21:31:47 christos Exp $ */ 2 3#include <tommath.h> 4#ifdef BN_S_MP_MUL_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 only computes upto digs digits of result 21 * HAC pp. 595, Algorithm 14.12 Modified so you can control how 22 * many digits of output are created. 23 */ 24int s_mp_mul_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 if (((digs) < MP_WARRAY) && 34 MIN (a->used, b->used) < 35 (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) { 36 return fast_s_mp_mul_digs (a, b, c, digs); 37 } 38 39 if ((res = mp_init_size (&t, digs)) != MP_OKAY) { 40 return res; 41 } 42 t.used = digs; 43 44 /* compute the digits of the product directly */ 45 pa = a->used; 46 for (ix = 0; ix < pa; ix++) { 47 /* set the carry to zero */ 48 u = 0; 49 50 /* limit ourselves to making digs digits of output */ 51 pb = MIN (b->used, digs - ix); 52 53 /* setup some aliases */ 54 /* copy of the digit from a used within the nested loop */ 55 tmpx = a->dp[ix]; 56 57 /* an alias for the destination shifted ix places */ 58 tmpt = t.dp + ix; 59 60 /* an alias for the digits of b */ 61 tmpy = b->dp; 62 63 /* compute the columns of the output and propagate the carry */ 64 for (iy = 0; iy < pb; iy++) { 65 /* compute the column as a mp_word */ 66 r = ((mp_word)*tmpt) + 67 ((mp_word)tmpx) * ((mp_word)*tmpy++) + 68 ((mp_word) u); 69 70 /* the new column is the lower part of the result */ 71 *tmpt++ = (mp_digit) (r & ((mp_word) MP_MASK)); 72 73 /* get the carry word from the result */ 74 u = (mp_digit) (r >> ((mp_word) DIGIT_BIT)); 75 } 76 /* set carry if it is placed below digs */ 77 if (ix + iy < digs) { 78 *tmpt = u; 79 } 80 } 81 82 mp_clamp (&t); 83 mp_exch (&t, c); 84 85 mp_clear (&t); 86 return MP_OKAY; 87} 88#endif 89 90/* Source: /cvs/libtom/libtommath/bn_s_mp_mul_digs.c,v */ 91/* Revision: 1.4 */ 92/* Date: 2006/12/28 01:25:13 */ 93