release/src/router/dropbear/libtommath/bn_mp_mul.c

   1 #include <tommath.h>
   2 #ifdef BN_MP_MUL_C
   3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
   4  *
   5  * LibTomMath is a library that provides multiple-precision
   6  * integer arithmetic as well as number theoretic functionality.
   7  *
   8  * The library was designed directly after the MPI library by
   9  * Michael Fromberger but has been written from scratch with
  10  * additional optimizations in place.
  11  *
  12  * The library is free for all purposes without any express
  13  * guarantee it works.
  14  *
  15  * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com
  16  */
  17
  18 /* high level multiplication (handles sign) */
  19 int mp_mul (mp_int * a, mp_int * b, mp_int * c)
  20 {
  21   int     res, neg;
  22   neg = (a->sign == b->sign) ? MP_ZPOS : MP_NEG;
  23
  24   /* use Toom-Cook? */
  25 #ifdef BN_MP_TOOM_MUL_C
  26   if (MIN (a->used, b->used) >= TOOM_MUL_CUTOFF) {
  27     res = mp_toom_mul(a, b, c);
  28   } else
  29 #endif
  30 #ifdef BN_MP_KARATSUBA_MUL_C
  31   /* use Karatsuba? */
  32   if (MIN (a->used, b->used) >= KARATSUBA_MUL_CUTOFF) {
  33     res = mp_karatsuba_mul (a, b, c);
  34   } else
  35 #endif
  36   {
  37     /* can we use the fast multiplier?
  38      *
  39      * The fast multiplier can be used if the output will
  40      * have less than MP_WARRAY digits and the number of
  41      * digits won't affect carry propagation
  42      */
  43     int     digs = a->used + b->used + 1;
  44
  45 #ifdef BN_FAST_S_MP_MUL_DIGS_C
  46     if ((digs < MP_WARRAY) &&
  47         MIN(a->used, b->used) <=
  48         (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
  49       res = fast_s_mp_mul_digs (a, b, c, digs);
  50     } else
  51 #endif
  52 #ifdef BN_S_MP_MUL_DIGS_C
  53       res = s_mp_mul (a, b, c); /* uses s_mp_mul_digs */
  54 #else
  55       res = MP_VAL;
  56 #endif
  57
  58   }
  59   c->sign = (c->used > 0) ? neg : MP_ZPOS;
  60   return res;
  61 }
  62 #endif
  63
  64 /* $Source: /cvs/libtom/libtommath/bn_mp_mul.c,v $ */
  65 /* $Revision: 1.3 $ */
  66 /* $Date: 2006/03/31 14:18:44 $ */