crypto/bn/old/bn_ka.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <strings.h>
   4 #include "bn_lcl.h"
   5
   6 /* r is 2*n2 words in size,
   7  * a and b are both n2 words in size.
   8  * n2 must be a power of 2.
   9  * We multiply and return the result.
  10  * t must be 2*n2 words in size
  11  * We calulate
  12  * a[0]*b[0]
  13  * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
  14  * a[1]*b[1]
  15  */
  16 void bn_mul_recursive(r,a,b,n2,t)
  17 BN_ULONG *r,*a,*b;
  18 int n2;
  19 BN_ULONG *t;
  20         {
  21         int n=n2/2;
  22         int neg,zero,c1,c2;
  23         BN_ULONG ln,lo,*p;
  24
  25 #ifdef BN_COUNT
  26 printf(" bn_mul_recursive %d * %d\n",n2,n2);
  27 #endif
  28         if (n2 <= 8)
  29                 {
  30                 if (n2 == 8)
  31                         bn_mul_comba8(r,a,b);
  32                 else
  33                         bn_mul_normal(r,a,n2,b,n2);
  34                 return;
  35                 }
  36
  37         if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL)
  38                 {
  39                 /* This should not happen */
  40                 /*abort(); */
  41                 bn_mul_normal(r,a,n2,b,n2);
  42                 return;
  43                 }
  44         /* r=(a[0]-a[1])*(b[1]-b[0]) */
  45         c1=bn_cmp_words(a,&(a[n]),n);
  46         c2=bn_cmp_words(&(b[n]),b,n);
  47         zero=neg=0;
  48         switch (c1*3+c2)
  49                 {
  50         case -4:
  51                 bn_sub_words(t,      &(a[n]),a,      n); /* - */
  52                 bn_sub_words(&(t[n]),b,      &(b[n]),n); /* - */
  53                 break;
  54         case -3:
  55                 zero=1;
  56                 break;
  57         case -2:
  58                 bn_sub_words(t,      &(a[n]),a,      n); /* - */
  59                 bn_sub_words(&(t[n]),&(b[n]),b,      n); /* + */
  60                 neg=1;
  61                 break;
  62         case -1:
  63         case 0:
  64         case 1:
  65                 zero=1;
  66                 break;
  67         case 2:
  68                 bn_sub_words(t,      a,      &(a[n]),n); /* + */
  69                 bn_sub_words(&(t[n]),b,      &(b[n]),n); /* - */
  70                 neg=1;
  71                 break;
  72         case 3:
  73                 zero=1;
  74                 break;
  75         case 4:
  76                 bn_sub_words(t,      a,      &(a[n]),n);
  77                 bn_sub_words(&(t[n]),&(b[n]),b,      n);
  78                 break;
  79                 }
  80
  81         if (n == 8)
  82                 {
  83                 if (!zero)
  84                         bn_mul_comba8(&(t[n2]),t,&(t[n]));
  85                 else
  86                         memset(&(t[n2]),0,8*sizeof(BN_ULONG));
  87
  88                 bn_mul_comba8(r,a,b);
  89                 bn_mul_comba8(&(r[n2]),&(a[n]),&(b[n]));
  90                 }
  91         else
  92                 {
  93                 p= &(t[n2*2]);
  94                 if (!zero)
  95                         bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p);
  96                 else
  97                         memset(&(t[n2]),0,n*sizeof(BN_ULONG));
  98                 bn_mul_recursive(r,a,b,n,p);
  99                 bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),n,p);
 100                 }
 101
 102         /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
 103          * r[10] holds (a[0]*b[0])
 104          * r[32] holds (b[1]*b[1])
 105          */
 106
 107         c1=bn_add_words(t,r,&(r[n2]),n2);
 108
 109         if (neg) /* if t[32] is negative */
 110                 {
 111                 c1-=bn_sub_words(&(t[n2]),t,&(t[n2]),n2);
 112                 }
 113         else
 114                 {
 115                 /* Might have a carry */
 116                 c1+=bn_add_words(&(t[n2]),&(t[n2]),t,n2);
 117                 }
 118
 119         /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
 120          * r[10] holds (a[0]*b[0])
 121          * r[32] holds (b[1]*b[1])
 122          * c1 holds the carry bits
 123          */
 124         c1+=bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2);
 125         if (c1)
 126                 {
 127                 p= &(r[n+n2]);
 128                 lo= *p;
 129                 ln=(lo+c1)&BN_MASK2;
 130                 *p=ln;
 131
 132                 /* The overflow will stop before we over write
 133                  * words we should not overwrite */
 134                 if (ln < c1)
 135                         {
 136                         do      {
 137                                 p++;
 138                                 lo= *p;
 139                                 ln=(lo+1)&BN_MASK2;
 140                                 *p=ln;
 141                                 } while (ln == 0);
 142                         }
 143                 }
 144         }
 145
 146 /* n+tn is the word length
 147  * t needs to be n*4 is size, as does r */
 148 void bn_mul_part_recursive(r,a,b,tn,n,t)
 149 BN_ULONG *r,*a,*b;
 150 int tn,n;
 151 BN_ULONG *t;
 152         {
 153         int n2=n*2,i,j;
 154         int c1;
 155         BN_ULONG ln,lo,*p;
 156
 157 #ifdef BN_COUNT
 158 printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n);
 159 #endif
 160         if (n < 8)
 161                 {
 162                 i=tn+n;
 163                 bn_mul_normal(r,a,i,b,i);
 164                 return;
 165                 }
 166
 167         /* r=(a[0]-a[1])*(b[1]-b[0]) */
 168         bn_sub_words(t,      a,      &(a[n]),n); /* + */
 169         bn_sub_words(&(t[n]),b,      &(b[n]),n); /* - */
 170
 171         if (n == 8)
 172                 {
 173                 bn_mul_comba8(&(t[n2]),t,&(t[n]));
 174                 bn_mul_comba8(r,a,b);
 175                 bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn);
 176                 memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2));
 177                 }
 178         else
 179                 {
 180                 p= &(t[n2*2]);
 181                 bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p);
 182                 bn_mul_recursive(r,a,b,n,p);
 183                 i=n/2;
 184                 /* If there is only a bottom half to the number,
 185                  * just do it */
 186                 j=tn-i;
 187                 if (j == 0)
 188                         {
 189                         bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),i,p);
 190                         memset(&(r[n2+i*2]),0,sizeof(BN_ULONG)*(n2-i*2));
 191                         }
 192                 else if (j > 0) /* eg, n == 16, i == 8 and tn == 11 */
 193                                 {
 194                                 bn_mul_part_recursive(&(r[n2]),&(a[n]),&(b[n]),
 195                                         j,i,p);
 196                                 memset(&(r[n2+tn*2]),0,
 197                                         sizeof(BN_ULONG)*(n2-tn*2));
 198                                 }
 199                 else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
 200                         {
 201                         memset(&(r[n2]),0,sizeof(BN_ULONG)*(tn*2));
 202                         for (;;)
 203                                 {
 204                                 i/=2;
 205                                 if (i < tn)
 206                                         {
 207                                         bn_mul_part_recursive(&(r[n2]),
 208                                                 &(a[n]),&(b[n]),
 209                                                 tn-i,i,p);
 210                                         break;
 211                                         }
 212                                 else if (i == tn)
 213                                         {
 214                                         bn_mul_recursive(&(r[n2]),
 215                                                 &(a[n]),&(b[n]),
 216                                                 i,p);
 217                                         break;
 218                                         }
 219                                 }
 220                         }
 221                 }
 222
 223         /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
 224          * r[10] holds (a[0]*b[0])
 225          * r[32] holds (b[1]*b[1])
 226          */
 227
 228         c1=bn_add_words(t,r,&(r[n2]),n2);
 229         c1-=bn_sub_words(&(t[n2]),t,&(t[n2]),n2);
 230
 231         /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
 232          * r[10] holds (a[0]*b[0])
 233          * r[32] holds (b[1]*b[1])
 234          * c1 holds the carry bits
 235          */
 236         c1+=bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2);
 237         if (c1)
 238                 {
 239                 p= &(r[n+n2]);
 240                 lo= *p;
 241                 ln=(lo+c1)&BN_MASK2;
 242                 *p=ln;
 243
 244                 /* The overflow will stop before we over write
 245                  * words we should not overwrite */
 246                 if (ln < c1)
 247                         {
 248                         do      {
 249                                 p++;
 250                                 lo= *p;
 251                                 ln=(lo+1)&BN_MASK2;
 252                                 *p=ln;
 253                                 } while (ln == 0);
 254                         }
 255                 }
 256         }
 257
 258 /* r is 2*n words in size,
 259  * a and b are both n words in size.
 260  * n must be a power of 2.
 261  * We multiply and return the result.
 262  * t must be 2*n words in size
 263  * We calulate
 264  * a[0]*b[0]
 265  * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
 266  * a[1]*b[1]
 267  */
 268 void bn_sqr_recursive(r,a,n2,t)
 269 BN_ULONG *r,*a;
 270 int n2;
 271 BN_ULONG *t;
 272         {
 273         int n=n2/2;
 274         int zero,c1;
 275         BN_ULONG ln,lo,*p;
 276
 277 #ifdef BN_COUNT
 278 printf(" bn_sqr_recursive %d * %d\n",n2,n2);
 279 #endif
 280         if (n2 == 4)
 281                 {
 282                 bn_sqr_comba4(r,a);
 283                 return;
 284                 }
 285         else if (n2 == 8)
 286                 {
 287                 bn_sqr_comba8(r,a);
 288                 return;
 289                 }
 290         if (n2 < BN_SQR_RECURSIVE_SIZE_NORMAL)
 291                 {
 292                 bn_sqr_normal(r,a,n2,t);
 293                 return;
 294                 abort();
 295                 }
 296         /* r=(a[0]-a[1])*(a[1]-a[0]) */
 297         c1=bn_cmp_words(a,&(a[n]),n);
 298         zero=0;
 299         if (c1 > 0)
 300                 bn_sub_words(t,a,&(a[n]),n);
 301         else if (c1 < 0)
 302                 bn_sub_words(t,&(a[n]),a,n);
 303         else
 304                 zero=1;
 305
 306         /* The result will always be negative unless it is zero */
 307
 308         if (n == 8)
 309                 {
 310                 if (!zero)
 311                         bn_sqr_comba8(&(t[n2]),t);
 312                 else
 313                         memset(&(t[n2]),0,8*sizeof(BN_ULONG));
 314
 315                 bn_sqr_comba8(r,a);
 316                 bn_sqr_comba8(&(r[n2]),&(a[n]));
 317                 }
 318         else
 319                 {
 320                 p= &(t[n2*2]);
 321                 if (!zero)
 322                         bn_sqr_recursive(&(t[n2]),t,n,p);
 323                 else
 324                         memset(&(t[n2]),0,n*sizeof(BN_ULONG));
 325                 bn_sqr_recursive(r,a,n,p);
 326                 bn_sqr_recursive(&(r[n2]),&(a[n]),n,p);
 327                 }
 328
 329         /* t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero
 330          * r[10] holds (a[0]*b[0])
 331          * r[32] holds (b[1]*b[1])
 332          */
 333
 334         c1=bn_add_words(t,r,&(r[n2]),n2);
 335
 336         /* t[32] is negative */
 337         c1-=bn_sub_words(&(t[n2]),t,&(t[n2]),n2);
 338
 339         /* t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1])
 340          * r[10] holds (a[0]*a[0])
 341          * r[32] holds (a[1]*a[1])
 342          * c1 holds the carry bits
 343          */
 344         c1+=bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2);
 345         if (c1)
 346                 {
 347                 p= &(r[n+n2]);
 348                 lo= *p;
 349                 ln=(lo+c1)&BN_MASK2;
 350                 *p=ln;
 351
 352                 /* The overflow will stop before we over write
 353                  * words we should not overwrite */
 354                 if (ln < c1)
 355                         {
 356                         do      {
 357                                 p++;
 358                                 lo= *p;
 359                                 ln=(lo+1)&BN_MASK2;
 360                                 *p=ln;
 361                                 } while (ln == 0);
 362                         }
 363                 }
 364         }
 365
 366 #if 1
 367 /* a and b must be the same size, which is n2.
 368  * r needs to be n2 words and t needs to be n2*2
 369  */
 370 void bn_mul_low_recursive(r,a,b,n2,t)
 371 BN_ULONG *r,*a,*b;
 372 int n2;
 373 BN_ULONG *t;
 374         {
 375         int n=n2/2;
 376
 377 #ifdef BN_COUNT
 378 printf(" bn_mul_low_recursive %d * %d\n",n2,n2);
 379 #endif
 380
 381         bn_mul_recursive(r,a,b,n,&(t[0]));
 382         if (n > BN_MUL_LOW_RECURSIVE_SIZE_NORMAL)
 383                 {
 384                 bn_mul_low_recursive(&(t[0]),&(a[0]),&(b[n]),n,&(t[n2]));
 385                 bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
 386                 bn_mul_low_recursive(&(t[0]),&(a[n]),&(b[0]),n,&(t[n2]));
 387                 bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
 388                 }
 389         else
 390                 {
 391                 bn_mul_low_normal(&(t[0]),&(a[0]),&(b[n]),n);
 392                 bn_mul_low_normal(&(t[n]),&(a[n]),&(b[0]),n);
 393                 bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
 394                 bn_add_words(&(r[n]),&(r[n]),&(t[n]),n);
 395                 }
 396         }
 397
 398 /* a and b must be the same size, which is n2.
 399  * r needs to be n2 words and t needs to be n2*2
 400  * l is the low words of the output.
 401  * t needs to be n2*3
 402  */
 403 void bn_mul_high(r,a,b,l,n2,t)
 404 BN_ULONG *r,*a,*b,*l;
 405 int n2;
 406 BN_ULONG *t;
 407         {
 408         int j,i,n,c1,c2;
 409         int neg,oneg,zero;
 410         BN_ULONG ll,lc,*lp,*mp;
 411
 412 #ifdef BN_COUNT
 413 printf(" bn_mul_high %d * %d\n",n2,n2);
 414 #endif
 415         n=(n2+1)/2;
 416
 417         /* Calculate (al-ah)*(bh-bl) */
 418         neg=zero=0;
 419         c1=bn_cmp_words(&(a[0]),&(a[n]),n);
 420         c2=bn_cmp_words(&(b[n]),&(b[0]),n);
 421         switch (c1*3+c2)
 422                 {
 423         case -4:
 424                 bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n);
 425                 bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n);
 426                 break;
 427         case -3:
 428                 zero=1;
 429                 break;
 430         case -2:
 431                 bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n);
 432                 bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n);
 433                 neg=1;
 434                 break;
 435         case -1:
 436         case 0:
 437         case 1:
 438                 zero=1;
 439                 break;
 440         case 2:
 441                 bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n);
 442                 bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n);
 443                 neg=1;
 444                 break;
 445         case 3:
 446                 zero=1;
 447                 break;
 448         case 4:
 449                 bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n);
 450                 bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n);
 451                 break;
 452                 }
 453
 454         oneg=neg;
 455         /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */
 456         bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,&(t[n2]));
 457         /* r[10] = (a[1]*b[1]) */
 458         bn_mul_recursive(r,&(a[n]),&(b[n]),n,&(t[n2]));
 459
 460         /* s0 == low(al*bl)
 461          * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
 462          * We know s0 and s1 so the only unknown is high(al*bl)
 463          * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl))
 464          * high(al*bl) == s1 - (r[0]+l[0]+t[0])
 465          */
 466         if (l != NULL)
 467                 {
 468                 lp= &(t[n2+n]);
 469                 c1=bn_add_words(lp,&(r[0]),&(l[0]),n);
 470                 }
 471         else
 472                 {
 473                 c1=0;
 474                 lp= &(r[0]);
 475                 }
 476
 477         if (neg)
 478                 neg=bn_sub_words(&(t[n2]),lp,&(t[0]),n);
 479         else
 480                 {
 481                 bn_add_words(&(t[n2]),lp,&(t[0]),n);
 482                 neg=0;
 483                 }
 484
 485         if (l != NULL)
 486                 {
 487                 bn_sub_words(&(t[n2+n]),&(l[n]),&(t[n2]),n);
 488                 }
 489         else
 490                 {
 491                 lp= &(t[n2+n]);
 492                 mp= &(t[n2]);
 493                 for (i=0; i<n; i++)
 494                         lp[i]=((~mp[i])+1)&BN_MASK2;
 495                 }
 496
 497         /* s[0] = low(al*bl)
 498          * t[3] = high(al*bl)
 499          * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign
 500          * r[10] = (a[1]*b[1])
 501          */
 502         /* R[10] = al*bl
 503          * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0])
 504          * R[32] = ah*bh
 505          */
 506         /* R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow)
 507          * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow)
 508          * R[3]=r[1]+(carry/borrow)
 509          */
 510         if (l != NULL)
 511                 {
 512                 lp= &(t[n2]);
 513                 c1= bn_add_words(lp,&(t[n2+n]),&(l[0]),n);
 514                 }
 515         else
 516                 {
 517                 lp= &(t[n2+n]);
 518                 c1=0;
 519                 }
 520         c1+=bn_add_words(&(t[n2]),lp,  &(r[0]),n);
 521         if (oneg)
 522                 c1-=bn_sub_words(&(t[n2]),&(t[n2]),&(t[0]),n);
 523         else
 524                 c1+=bn_add_words(&(t[n2]),&(t[n2]),&(t[0]),n);
 525
 526         c2 =bn_add_words(&(r[0]),&(r[0]),&(t[n2+n]),n);
 527         c2+=bn_add_words(&(r[0]),&(r[0]),&(r[n]),n);
 528         if (oneg)
 529                 c2-=bn_sub_words(&(r[0]),&(r[0]),&(t[n]),n);
 530         else
 531                 c2+=bn_add_words(&(r[0]),&(r[0]),&(t[n]),n);
 532
 533         if (c1 != 0) /* Add starting at r[0], could be +ve or -ve */
 534                 {
 535                 i=0;
 536                 if (c1 > 0)
 537                         {
 538                         lc=c1;
 539                         do      {
 540                                 ll=(r[i]+lc)&BN_MASK2;
 541                                 r[i++]=ll;
 542                                 lc=(lc > ll);
 543                                 } while (lc);
 544                         }
 545                 else
 546                         {
 547                         lc= -c1;
 548                         do      {
 549                                 ll=r[i];
 550                                 r[i++]=(ll-lc)&BN_MASK2;
 551                                 lc=(lc > ll);
 552                                 } while (lc);
 553                         }
 554                 }
 555         if (c2 != 0) /* Add starting at r[1] */
 556                 {
 557                 i=n;
 558                 if (c2 > 0)
 559                         {
 560                         lc=c2;
 561                         do      {
 562                                 ll=(r[i]+lc)&BN_MASK2;
 563                                 r[i++]=ll;
 564                                 lc=(lc > ll);
 565                                 } while (lc);
 566                         }
 567                 else
 568                         {
 569                         lc= -c2;
 570                         do      {
 571                                 ll=r[i];
 572                                 r[i++]=(ll-lc)&BN_MASK2;
 573                                 lc=(lc > ll);
 574                                 } while (lc);
 575                         }
 576                 }
 577         }
 578 #endif