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