crypto/bn/old/bn_wmul.c

   1 #include <stdio.h>
   2 #include "bn_lcl.h"
   3
   4 #if 1
   5
   6 int bn_mull(BIGNUM *r,BIGNUM *a,BIGNUM *b, BN_CTX *ctx);
   7
   8 int bn_mull(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
   9         {
  10         int top,i,j,k,al,bl;
  11         BIGNUM *t;
  12
  13 #ifdef BN_COUNT
  14 printf("bn_mull %d * %d\n",a->top,b->top);
  15 #endif
  16
  17         bn_check_top(a);
  18         bn_check_top(b);
  19         bn_check_top(r);
  20
  21         al=a->top;
  22         bl=b->top;
  23         r->neg=a->neg^b->neg;
  24
  25         top=al+bl;
  26         if ((al < 4) || (bl < 4))
  27                 {
  28                 if (bn_wexpand(r,top) == NULL) return(0);
  29                 r->top=top;
  30                 bn_mul_normal(r->d,a->d,al,b->d,bl);
  31                 goto end;
  32                 }
  33         else if (al == bl) /* A good start, they are the same size */
  34                 goto symetric;
  35         else
  36                 {
  37                 i=(al-bl);
  38                 if ((i ==  1) && !BN_get_flags(b,BN_FLG_STATIC_DATA))
  39                         {
  40                         bn_wexpand(b,al);
  41                         b->d[bl]=0;
  42                         bl++;
  43                         goto symetric;
  44                         }
  45                 else if ((i ==  -1) && !BN_get_flags(a,BN_FLG_STATIC_DATA))
  46                         {
  47                         bn_wexpand(a,bl);
  48                         a->d[al]=0;
  49                         al++;
  50                         goto symetric;
  51                         }
  52                 }
  53
  54         /* asymetric and >= 4 */
  55         if (bn_wexpand(r,top) == NULL) return(0);
  56         r->top=top;
  57         bn_mul_normal(r->d,a->d,al,b->d,bl);
  58
  59         if (0)
  60                 {
  61                 /* symetric and > 4 */
  62 symetric:
  63                 if (al == 4)
  64                         {
  65                         if (bn_wexpand(r,al*2) == NULL) return(0);
  66                         r->top=top;
  67                         bn_mul_comba4(r->d,a->d,b->d);
  68                         goto end;
  69                         }
  70                 if (al == 8)
  71                         {
  72                         if (bn_wexpand(r,al*2) == NULL) return(0);
  73                         r->top=top;
  74                         bn_mul_comba8(r->d,a->d,b->d);
  75                         goto end;
  76                         }
  77                 if (al <= BN_MULL_NORMAL_SIZE)
  78                         {
  79                         if (bn_wexpand(r,al*2) == NULL) return(0);
  80                         r->top=top;
  81                         bn_mul_normal(r->d,a->d,al,b->d,bl);
  82                         goto end;
  83                         }
  84                 /* 16 or larger */
  85                 j=BN_num_bits_word((BN_ULONG)al);
  86                 j=1<<(j-1);
  87                 k=j+j;
  88                 t= &(ctx->bn[ctx->tos]);
  89                 if (al == j) /* exact multiple */
  90                         {
  91                         bn_wexpand(t,k*2);
  92                         bn_wexpand(r,k*2);
  93                         bn_mul_recursive(r->d,a->d,b->d,al,t->d);
  94                         }
  95                 else
  96                         {
  97                         bn_wexpand(a,k);
  98                         bn_wexpand(b,k);
  99                         bn_wexpand(t,k*4);
 100                         bn_wexpand(r,k*4);
 101                         for (i=a->top; i<k; i++)
 102                                 a->d[i]=0;
 103                         for (i=b->top; i<k; i++)
 104                                 b->d[i]=0;
 105                         bn_mul_part_recursive(r->d,a->d,b->d,al-j,j,t->d);
 106                         }
 107                 r->top=top;
 108                 }
 109 end:
 110         bn_fix_top(r);
 111         return(1);
 112         }
 113 #endif
 114
 115 void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
 116         {
 117         BN_ULONG *rr;
 118
 119 #ifdef BN_COUNT
 120 printf(" bn_mul_normal %d * %d\n",na,nb);
 121 #endif
 122
 123         if (na < nb)
 124                 {
 125                 int itmp;
 126                 BN_ULONG *ltmp;
 127
 128                 itmp=na; na=nb; nb=itmp;
 129                 ltmp=a;   a=b;   b=ltmp;
 130
 131                 }
 132         rr= &(r[na]);
 133         rr[0]=bn_mul_words(r,a,na,b[0]);
 134
 135         for (;;)
 136                 {
 137                 if (--nb <= 0) return;
 138                 rr[1]=bn_mul_add_words(&(r[1]),a,na,b[1]);
 139                 if (--nb <= 0) return;
 140                 rr[2]=bn_mul_add_words(&(r[2]),a,na,b[2]);
 141                 if (--nb <= 0) return;
 142                 rr[3]=bn_mul_add_words(&(r[3]),a,na,b[3]);
 143                 if (--nb <= 0) return;
 144                 rr[4]=bn_mul_add_words(&(r[4]),a,na,b[4]);
 145                 rr+=4;
 146                 r+=4;
 147                 b+=4;
 148                 }
 149         }
 150
 151 #if 1
 152 void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
 153         {
 154 #ifdef BN_COUNT
 155 printf(" bn_mul_low_normal %d * %d\n",n,n);
 156 #endif
 157         bn_mul_words(r,a,n,b[0]);
 158
 159         for (;;)
 160                 {
 161                 if (--n <= 0) return;
 162                 bn_mul_add_words(&(r[1]),a,n,b[1]);
 163                 if (--n <= 0) return;
 164                 bn_mul_add_words(&(r[2]),a,n,b[2]);
 165                 if (--n <= 0) return;
 166                 bn_mul_add_words(&(r[3]),a,n,b[3]);
 167                 if (--n <= 0) return;
 168                 bn_mul_add_words(&(r[4]),a,n,b[4]);
 169                 r+=4;
 170                 b+=4;
 171                 }
 172         }
 173 #endif