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