pd.if.org Git - zpackage/blob - tomsfastmath/src/mul/fp_mul.c

   1 /* TomsFastMath, a fast ISO C bignum library.
   2  *
   3  * This project is meant to fill in where LibTomMath
   4  * falls short.  That is speed ;-)
   5  *
   6  * This project is public domain and free for all purposes.
   7  *
   8  * Tom St Denis, tomstdenis@gmail.com
   9  */
  10 #include <tfm_private.h>
  11
  12 /* c = a * b */
  13 void fp_mul(fp_int *A, fp_int *B, fp_int *C)
  14 {
  15     int   y, old_used;
  16 #if FP_SIZE >= 48
  17     int   yy;
  18 #endif
  19
  20     old_used = C->used;
  21
  22     /* call generic if we're out of range */
  23     if (A->used + B->used > FP_SIZE) {
  24        fp_mul_comba(A, B, C);
  25        goto clean;
  26     }
  27
  28      y  = MAX(A->used, B->used);
  29 #if FP_SIZE >= 48
  30      yy = MIN(A->used, B->used);
  31 #endif
  32     /* pick a comba (unrolled 4/8/16/32 x or rolled) based on the size
  33        of the largest input.  We also want to avoid doing excess mults if the
  34        inputs are not close to the next power of two.  That is, for example,
  35        if say y=17 then we would do (32-17)^2 = 225 unneeded multiplications
  36     */
  37
  38 #if defined(TFM_MUL3) && FP_SIZE >= 6
  39         if (y <= 3) {
  40            fp_mul_comba3(A,B,C);
  41            goto clean;
  42         }
  43 #endif
  44 #if defined(TFM_MUL4) && FP_SIZE >= 8
  45         if (y == 4) {
  46            fp_mul_comba4(A,B,C);
  47            goto clean;
  48         }
  49 #endif
  50 #if defined(TFM_MUL6) && FP_SIZE >= 12
  51         if (y <= 6) {
  52            fp_mul_comba6(A,B,C);
  53            goto clean;
  54         }
  55 #endif
  56 #if defined(TFM_MUL7) && FP_SIZE >= 14
  57         if (y == 7) {
  58            fp_mul_comba7(A,B,C);
  59            goto clean;
  60         }
  61 #endif
  62 #if defined(TFM_MUL8) && FP_SIZE >= 16
  63         if (y == 8) {
  64            fp_mul_comba8(A,B,C);
  65            goto clean;
  66         }
  67 #endif
  68 #if defined(TFM_MUL9) && FP_SIZE >= 18
  69         if (y == 9) {
  70            fp_mul_comba9(A,B,C);
  71            goto clean;
  72         }
  73 #endif
  74 #if defined(TFM_MUL12) && FP_SIZE >= 24
  75         if (y <= 12) {
  76            fp_mul_comba12(A,B,C);
  77            goto clean;
  78         }
  79 #endif
  80 #if defined(TFM_MUL17) && FP_SIZE >= 34
  81         if (y <= 17) {
  82            fp_mul_comba17(A,B,C);
  83            goto clean;
  84         }
  85 #endif
  86
  87 #if defined(TFM_SMALL_SET) && FP_SIZE >= 32
  88         if (y <= 16) {
  89            fp_mul_comba_small(A,B,C);
  90            goto clean;
  91         }
  92 #endif
  93 #if defined(TFM_MUL20) && FP_SIZE >= 40
  94         if (y <= 20) {
  95            fp_mul_comba20(A,B,C);
  96            goto clean;
  97         }
  98 #endif
  99 #if defined(TFM_MUL24) && FP_SIZE >= 48
 100         if (yy >= 16 && y <= 24) {
 101            fp_mul_comba24(A,B,C);
 102            goto clean;
 103         }
 104 #endif
 105 #if defined(TFM_MUL28) && FP_SIZE >= 56
 106         if (yy >= 20 && y <= 28) {
 107            fp_mul_comba28(A,B,C);
 108            goto clean;
 109         }
 110 #endif
 111 #if defined(TFM_MUL32) && FP_SIZE >= 64
 112         if (yy >= 24 && y <= 32) {
 113            fp_mul_comba32(A,B,C);
 114            goto clean;
 115         }
 116 #endif
 117 #if defined(TFM_MUL48) && FP_SIZE >= 96
 118         if (yy >= 40 && y <= 48) {
 119            fp_mul_comba48(A,B,C);
 120            goto clean;
 121         }
 122 #endif
 123 #if defined(TFM_MUL64) && FP_SIZE >= 128
 124         if (yy >= 56 && y <= 64) {
 125            fp_mul_comba64(A,B,C);
 126            goto clean;
 127         }
 128 #endif
 129         fp_mul_comba(A,B,C);
 130 clean:
 131     for (y = C->used; y < old_used; y++) {
 132        C->dp[y] = 0;
 133     }
 134 }
 135
 136
 137 /* $Source: /cvs/libtom/tomsfastmath/src/mul/fp_mul.c,v $ */
 138 /* $Revision: 1.1 $ */
 139 /* $Date: 2006/12/31 21:25:53 $ */