crypto/bn/bn_lib.c

   1 /* crypto/bn/bn_lib.c */
   2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   3  * All rights reserved.
   4  *
   5  * This package is an SSL implementation written
   6  * by Eric Young (eay@cryptsoft.com).
   7  * The implementation was written so as to conform with Netscapes SSL.
   8  *
   9  * This library is free for commercial and non-commercial use as long as
  10  * the following conditions are aheared to.  The following conditions
  11  * apply to all code found in this distribution, be it the RC4, RSA,
  12  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  13  * included with this distribution is covered by the same copyright terms
  14  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  15  *
  16  * Copyright remains Eric Young's, and as such any Copyright notices in
  17  * the code are not to be removed.
  18  * If this package is used in a product, Eric Young should be given attribution
  19  * as the author of the parts of the library used.
  20  * This can be in the form of a textual message at program startup or
  21  * in documentation (online or textual) provided with the package.
  22  *
  23  * Redistribution and use in source and binary forms, with or without
  24  * modification, are permitted provided that the following conditions
  25  * are met:
  26  * 1. Redistributions of source code must retain the copyright
  27  *    notice, this list of conditions and the following disclaimer.
  28  * 2. Redistributions in binary form must reproduce the above copyright
  29  *    notice, this list of conditions and the following disclaimer in the
  30  *    documentation and/or other materials provided with the distribution.
  31  * 3. All advertising materials mentioning features or use of this software
  32  *    must display the following acknowledgement:
  33  *    "This product includes cryptographic software written by
  34  *     Eric Young (eay@cryptsoft.com)"
  35  *    The word 'cryptographic' can be left out if the rouines from the library
  36  *    being used are not cryptographic related :-).
  37  * 4. If you include any Windows specific code (or a derivative thereof) from
  38  *    the apps directory (application code) you must include an acknowledgement:
  39  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  40  *
  41  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  42  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  43  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  44  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  45  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  46  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  47  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  49  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  50  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  51  * SUCH DAMAGE.
  52  *
  53  * The licence and distribution terms for any publically available version or
  54  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  55  * copied and put under another distribution licence
  56  * [including the GNU Public Licence.]
  57  */
  58
  59 #include <stdio.h>
  60 #include "cryptlib.h"
  61 #include "bn_lcl.h"
  62
  63 const char *BN_version="Big Number" OPENSSL_VERSION_PTEXT;
  64
  65 /* For a 32 bit machine
  66  * 2 -   4 ==  128
  67  * 3 -   8 ==  256
  68  * 4 -  16 ==  512
  69  * 5 -  32 == 1024
  70  * 6 -  64 == 2048
  71  * 7 - 128 == 4096
  72  * 8 - 256 == 8192
  73  */
  74 int bn_limit_bits=0;
  75 int bn_limit_num=8;        /* (1<<bn_limit_bits) */
  76 int bn_limit_bits_low=0;
  77 int bn_limit_num_low=8;    /* (1<<bn_limit_bits_low) */
  78 int bn_limit_bits_high=0;
  79 int bn_limit_num_high=8;   /* (1<<bn_limit_bits_high) */
  80 int bn_limit_bits_mont=0;
  81 int bn_limit_num_mont=8;   /* (1<<bn_limit_bits_mont) */
  82
  83 void BN_set_params(mult,high,low,mont)
  84 int mult,high,low,mont;
  85         {
  86         if (mult >= 0)
  87                 {
  88                 if (mult > (sizeof(int)*8)-1)
  89                         mult=sizeof(int)*8-1;
  90                 bn_limit_bits=mult;
  91                 bn_limit_num=1<<mult;
  92                 }
  93         if (high >= 0)
  94                 {
  95                 if (high > (sizeof(int)*8)-1)
  96                         high=sizeof(int)*8-1;
  97                 bn_limit_bits_high=high;
  98                 bn_limit_num_high=1<<high;
  99                 }
 100         if (low >= 0)
 101                 {
 102                 if (low > (sizeof(int)*8)-1)
 103                         low=sizeof(int)*8-1;
 104                 bn_limit_bits_low=low;
 105                 bn_limit_num_low=1<<low;
 106                 }
 107         if (mont >= 0)
 108                 {
 109                 if (mont > (sizeof(int)*8)-1)
 110                         mont=sizeof(int)*8-1;
 111                 bn_limit_bits_mont=mont;
 112                 bn_limit_num_mont=1<<mont;
 113                 }
 114         }
 115
 116 int BN_get_params(which)
 117 int which;
 118         {
 119         if      (which == 0) return(bn_limit_bits);
 120         else if (which == 1) return(bn_limit_bits_high);
 121         else if (which == 2) return(bn_limit_bits_low);
 122         else if (which == 3) return(bn_limit_bits_mont);
 123         else return(0);
 124         }
 125
 126 BIGNUM *BN_value_one()
 127         {
 128         static BN_ULONG data_one=1L;
 129         static BIGNUM const_one={&data_one,1,1,0};
 130
 131         return(&const_one);
 132         }
 133
 134 char *BN_options()
 135         {
 136         static int init=0;
 137         static char data[16];
 138
 139         if (!init)
 140                 {
 141                 init++;
 142 #ifdef BN_LLONG
 143                 sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULLONG)*8,
 144                         (int)sizeof(BN_ULONG)*8);
 145 #else
 146                 sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULONG)*8,
 147                         (int)sizeof(BN_ULONG)*8);
 148 #endif
 149                 }
 150         return(data);
 151         }
 152
 153 int BN_num_bits_word(l)
 154 BN_ULONG l;
 155         {
 156         static char bits[256]={
 157                 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,
 158                 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
 159                 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
 160                 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
 161                 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 162                 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 163                 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 164                 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 165                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 166                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 167                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 168                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 169                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 170                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 171                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 172                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 173                 };
 174
 175 #if defined(SIXTY_FOUR_BIT_LONG)
 176         if (l & 0xffffffff00000000L)
 177                 {
 178                 if (l & 0xffff000000000000L)
 179                         {
 180                         if (l & 0xff00000000000000L)
 181                                 {
 182                                 return(bits[(int)(l>>56)]+56);
 183                                 }
 184                         else    return(bits[(int)(l>>48)]+48);
 185                         }
 186                 else
 187                         {
 188                         if (l & 0x0000ff0000000000L)
 189                                 {
 190                                 return(bits[(int)(l>>40)]+40);
 191                                 }
 192                         else    return(bits[(int)(l>>32)]+32);
 193                         }
 194                 }
 195         else
 196 #else
 197 #ifdef SIXTY_FOUR_BIT
 198         if (l & 0xffffffff00000000LL)
 199                 {
 200                 if (l & 0xffff000000000000LL)
 201                         {
 202                         if (l & 0xff00000000000000LL)
 203                                 {
 204                                 return(bits[(int)(l>>56)]+56);
 205                                 }
 206                         else    return(bits[(int)(l>>48)]+48);
 207                         }
 208                 else
 209                         {
 210                         if (l & 0x0000ff0000000000LL)
 211                                 {
 212                                 return(bits[(int)(l>>40)]+40);
 213                                 }
 214                         else    return(bits[(int)(l>>32)]+32);
 215                         }
 216                 }
 217         else
 218 #endif
 219 #endif
 220                 {
 221 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 222                 if (l & 0xffff0000L)
 223                         {
 224                         if (l & 0xff000000L)
 225                                 return(bits[(int)(l>>24L)]+24);
 226                         else    return(bits[(int)(l>>16L)]+16);
 227                         }
 228                 else
 229 #endif
 230                         {
 231 #if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 232                         if (l & 0xff00L)
 233                                 return(bits[(int)(l>>8)]+8);
 234                         else
 235 #endif
 236                                 return(bits[(int)(l   )]  );
 237                         }
 238                 }
 239         }
 240
 241 int BN_num_bits(a)
 242 BIGNUM *a;
 243         {
 244         BN_ULONG l;
 245         int i;
 246
 247         bn_check_top(a);
 248
 249         if (a->top == 0) return(0);
 250         l=a->d[a->top-1];
 251         i=(a->top-1)*BN_BITS2;
 252         if (l == 0)
 253                 {
 254 #if !defined(NO_STDIO) && !defined(WIN16)
 255                 fprintf(stderr,"BAD TOP VALUE\n");
 256 #endif
 257                 abort();
 258                 }
 259         return(i+BN_num_bits_word(l));
 260         }
 261
 262 void BN_clear_free(a)
 263 BIGNUM *a;
 264         {
 265         int i;
 266
 267         if (a == NULL) return;
 268         if (a->d != NULL)
 269                 {
 270                 memset(a->d,0,a->max*sizeof(a->d[0]));
 271                 if (!(BN_get_flags(a,BN_FLG_STATIC_DATA)))
 272                         Free(a->d);
 273                 }
 274         i=BN_get_flags(a,BN_FLG_MALLOCED);
 275         memset(a,0,sizeof(BIGNUM));
 276         if (i)
 277                 Free(a);
 278         }
 279
 280 void BN_free(a)
 281 BIGNUM *a;
 282         {
 283         if (a == NULL) return;
 284         if ((a->d != NULL) && !(BN_get_flags(a,BN_FLG_STATIC_DATA)))
 285                 Free(a->d);
 286         a->flags|=BN_FLG_FREE; /* REMOVE? */
 287         if (a->flags & BN_FLG_MALLOCED)
 288                 Free(a);
 289         }
 290
 291 void BN_init(a)
 292 BIGNUM *a;
 293         {
 294         memset(a,0,sizeof(BIGNUM));
 295         }
 296
 297 BIGNUM *BN_new()
 298         {
 299         BIGNUM *ret;
 300
 301         if ((ret=(BIGNUM *)Malloc(sizeof(BIGNUM))) == NULL)
 302                 {
 303                 BNerr(BN_F_BN_NEW,ERR_R_MALLOC_FAILURE);
 304                 return(NULL);
 305                 }
 306         ret->flags=BN_FLG_MALLOCED;
 307         ret->top=0;
 308         ret->neg=0;
 309         ret->max=0;
 310         ret->d=NULL;
 311         return(ret);
 312         }
 313
 314
 315 BN_CTX *BN_CTX_new()
 316         {
 317         BN_CTX *ret;
 318
 319         ret=(BN_CTX *)Malloc(sizeof(BN_CTX));
 320         if (ret == NULL)
 321                 {
 322                 BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE);
 323                 return(NULL);
 324                 }
 325
 326         BN_CTX_init(ret);
 327         ret->flags=BN_FLG_MALLOCED;
 328         return(ret);
 329         }
 330
 331 void BN_CTX_init(ctx)
 332 BN_CTX *ctx;
 333         {
 334         memset(ctx,0,sizeof(BN_CTX));
 335         ctx->tos=0;
 336         ctx->flags=0;
 337         }
 338
 339 void BN_CTX_free(c)
 340 BN_CTX *c;
 341         {
 342         int i;
 343
 344         if(c == NULL)
 345             return;
 346
 347         for (i=0; i<BN_CTX_NUM; i++)
 348                 BN_clear_free(&(c->bn[i]));
 349         if (c->flags & BN_FLG_MALLOCED)
 350                 Free(c);
 351         }
 352
 353 BIGNUM *bn_expand2(b, words)
 354 BIGNUM *b;
 355 int words;
 356         {
 357         BN_ULONG *A,*B,*a;
 358         int i,j;
 359
 360         bn_check_top(b);
 361
 362         if (words > b->max)
 363                 {
 364                 bn_check_top(b);
 365                 if (BN_get_flags(b,BN_FLG_STATIC_DATA))
 366                         {
 367                         BNerr(BN_F_BN_EXPAND2,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
 368                         return(NULL);
 369                         }
 370                 a=A=(BN_ULONG *)Malloc(sizeof(BN_ULONG)*(words+1));
 371                 if (A == NULL)
 372                         {
 373                         BNerr(BN_F_BN_EXPAND2,ERR_R_MALLOC_FAILURE);
 374                         return(NULL);
 375                         }
 376 memset(A,0x5c,sizeof(BN_ULONG)*(words+1));
 377 #if 1
 378                 B=b->d;
 379                 /* Check if the previous number needs to be copied */
 380                 if (B != NULL)
 381                         {
 382                         /* This lot is an unrolled loop to copy b->top
 383                          * BN_ULONGs from B to A
 384                          */
 385                         for (i=b->top&(~7); i>0; i-=8)
 386                                 {
 387                                 A[0]=B[0]; A[1]=B[1]; A[2]=B[2]; A[3]=B[3];
 388                                 A[4]=B[4]; A[5]=B[5]; A[6]=B[6]; A[7]=B[7];
 389                                 A+=8;
 390                                 B+=8;
 391                                 }
 392                         switch (b->top&7)
 393                                 {
 394                         case 7:
 395                                 A[6]=B[6];
 396                         case 6:
 397                                 A[5]=B[5];
 398                         case 5:
 399                                 A[4]=B[4];
 400                         case 4:
 401                                 A[3]=B[3];
 402                         case 3:
 403                                 A[2]=B[2];
 404                         case 2:
 405                                 A[1]=B[1];
 406                         case 1:
 407                                 A[0]=B[0];
 408                         case 0:
 409                                 /* I need the 'case 0' entry for utrix cc.
 410                                  * If the optimiser is turned on, it does the
 411                                  * switch table by doing
 412                                  * a=top&7
 413                                  * a--;
 414                                  * goto jump_table[a];
 415                                  * If top is 0, this makes us jump to 0xffffffc
 416                                  * which is rather bad :-(.
 417                                  * eric 23-Apr-1998
 418                                  */
 419                                 ;
 420                                 }
 421                         Free(b->d);
 422                         }
 423
 424                 b->d=a;
 425                 b->max=words;
 426
 427                 /* Now need to zero any data between b->top and b->max */
 428
 429                 B= &(b->d[b->top]);
 430                 j=(b->max - b->top) & ~7;
 431                 for (i=0; i<j; i+=8)
 432                         {
 433                         B[0]=0; B[1]=0; B[2]=0; B[3]=0;
 434                         B[4]=0; B[5]=0; B[6]=0; B[7]=0;
 435                         B+=8;
 436                         }
 437                 j=(b->max - b->top) & 7;
 438                 for (i=0; i<j; i++)
 439                         {
 440                         B[0]=0;
 441                         B++;
 442                         }
 443 #else
 444                         memcpy(a->d,b->d,sizeof(b->d[0])*b->top);
 445 #endif
 446
 447 /*              memset(&(p[b->max]),0,((words+1)-b->max)*sizeof(BN_ULONG)); */
 448 /*      { int i; for (i=b->max; i<words+1; i++) p[i]=i;} */
 449
 450                 }
 451         return(b);
 452         }
 453
 454 BIGNUM *BN_dup(a)
 455 BIGNUM *a;
 456         {
 457         BIGNUM *r;
 458
 459         bn_check_top(a);
 460
 461         r=BN_new();
 462         if (r == NULL) return(NULL);
 463         return((BIGNUM *)BN_copy(r,a));
 464         }
 465
 466 BIGNUM *BN_copy(a, b)
 467 BIGNUM *a;
 468 BIGNUM *b;
 469         {
 470         int i;
 471         BN_ULONG *A,*B;
 472
 473         bn_check_top(b);
 474
 475         if (a == b) return(a);
 476         if (bn_wexpand(a,b->top) == NULL) return(NULL);
 477
 478 #if 1
 479         A=a->d;
 480         B=b->d;
 481         for (i=b->top&(~7); i>0; i-=8)
 482                 {
 483                 A[0]=B[0];
 484                 A[1]=B[1];
 485                 A[2]=B[2];
 486                 A[3]=B[3];
 487                 A[4]=B[4];
 488                 A[5]=B[5];
 489                 A[6]=B[6];
 490                 A[7]=B[7];
 491                 A+=8;
 492                 B+=8;
 493                 }
 494         switch (b->top&7)
 495                 {
 496         case 7:
 497                 A[6]=B[6];
 498         case 6:
 499                 A[5]=B[5];
 500         case 5:
 501                 A[4]=B[4];
 502         case 4:
 503                 A[3]=B[3];
 504         case 3:
 505                 A[2]=B[2];
 506         case 2:
 507                 A[1]=B[1];
 508         case 1:
 509                 A[0]=B[0];
 510         case 0:
 511                 /* I need the 'case 0' entry for utrix cc.
 512                  * If the optimiser is turned on, it does the
 513                  * switch table by doing
 514                  * a=top&7
 515                  * a--;
 516                  * goto jump_table[a];
 517                  * If top is 0, this makes us jump to 0xffffffc which is
 518                  * rather bad :-(.
 519                  * eric 23-Apr-1998
 520                  */
 521                 ;
 522                 }
 523 #else
 524         memcpy(a->d,b->d,sizeof(b->d[0])*b->top);
 525 #endif
 526
 527 /*      memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));*/
 528         a->top=b->top;
 529         if ((a->top == 0) && (a->d != NULL))
 530                 a->d[0]=0;
 531         a->neg=b->neg;
 532         return(a);
 533         }
 534
 535 void BN_clear(a)
 536 BIGNUM *a;
 537         {
 538         if (a->d != NULL)
 539                 memset(a->d,0,a->max*sizeof(a->d[0]));
 540         a->top=0;
 541         a->neg=0;
 542         }
 543
 544 BN_ULONG BN_get_word(a)
 545 BIGNUM *a;
 546         {
 547         int i,n;
 548         BN_ULONG ret=0;
 549
 550         n=BN_num_bytes(a);
 551         if (n > sizeof(BN_ULONG))
 552                 return(BN_MASK2);
 553         for (i=a->top-1; i>=0; i--)
 554                 {
 555 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
 556                 ret<<=BN_BITS4; /* stops the compiler complaining */
 557                 ret<<=BN_BITS4;
 558 #endif
 559                 ret|=a->d[i];
 560                 }
 561         return(ret);
 562         }
 563
 564 int BN_set_word(a,w)
 565 BIGNUM *a;
 566 BN_ULONG w;
 567         {
 568         int i,n;
 569         if (bn_expand(a,sizeof(BN_ULONG)*8) == NULL) return(0);
 570
 571         n=sizeof(BN_ULONG)/BN_BYTES;
 572         a->neg=0;
 573         a->top=0;
 574         a->d[0]=(BN_ULONG)w&BN_MASK2;
 575         if (a->d[0] != 0) a->top=1;
 576         for (i=1; i<n; i++)
 577                 {
 578                 /* the following is done instead of
 579                  * w>>=BN_BITS2 so compilers don't complain
 580                  * on builds where sizeof(long) == BN_TYPES */
 581 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
 582                 w>>=BN_BITS4;
 583                 w>>=BN_BITS4;
 584 #endif
 585                 a->d[i]=(BN_ULONG)w&BN_MASK2;
 586                 if (a->d[i] != 0) a->top=i+1;
 587                 }
 588         return(1);
 589         }
 590
 591 /* ignore negative */
 592 BIGNUM *BN_bin2bn(s, len, ret)
 593 unsigned char *s;
 594 int len;
 595 BIGNUM *ret;
 596         {
 597         unsigned int i,m;
 598         unsigned int n;
 599         BN_ULONG l;
 600
 601         if (ret == NULL) ret=BN_new();
 602         if (ret == NULL) return(NULL);
 603         l=0;
 604         n=len;
 605         if (n == 0)
 606                 {
 607                 ret->top=0;
 608                 return(ret);
 609                 }
 610         if (bn_expand(ret,(int)(n+2)*8) == NULL)
 611                 return(NULL);
 612         i=((n-1)/BN_BYTES)+1;
 613         m=((n-1)%(BN_BYTES));
 614         ret->top=i;
 615         while (n-- > 0)
 616                 {
 617                 l=(l<<8L)| *(s++);
 618                 if (m-- == 0)
 619                         {
 620                         ret->d[--i]=l;
 621                         l=0;
 622                         m=BN_BYTES-1;
 623                         }
 624                 }
 625         /* need to call this due to clear byte at top if avoiding
 626          * having the top bit set (-ve number) */
 627         bn_fix_top(ret);
 628         return(ret);
 629         }
 630
 631 /* ignore negative */
 632 int BN_bn2bin(a, to)
 633 BIGNUM *a;
 634 unsigned char *to;
 635         {
 636         int n,i;
 637         BN_ULONG l;
 638
 639         n=i=BN_num_bytes(a);
 640         while (i-- > 0)
 641                 {
 642                 l=a->d[i/BN_BYTES];
 643                 *(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff;
 644                 }
 645         return(n);
 646         }
 647
 648 int BN_ucmp(a, b)
 649 BIGNUM *a;
 650 BIGNUM *b;
 651         {
 652         int i;
 653         BN_ULONG t1,t2,*ap,*bp;
 654
 655         bn_check_top(a);
 656         bn_check_top(b);
 657
 658         i=a->top-b->top;
 659         if (i != 0) return(i);
 660         ap=a->d;
 661         bp=b->d;
 662         for (i=a->top-1; i>=0; i--)
 663                 {
 664                 t1= ap[i];
 665                 t2= bp[i];
 666                 if (t1 != t2)
 667                         return(t1 > t2?1:-1);
 668                 }
 669         return(0);
 670         }
 671
 672 int BN_cmp(a, b)
 673 BIGNUM *a;
 674 BIGNUM *b;
 675         {
 676         int i;
 677         int gt,lt;
 678         BN_ULONG t1,t2;
 679
 680         if ((a == NULL) || (b == NULL))
 681                 {
 682                 if (a != NULL)
 683                         return(-1);
 684                 else if (b != NULL)
 685                         return(1);
 686                 else
 687                         return(0);
 688                 }
 689
 690         bn_check_top(a);
 691         bn_check_top(b);
 692
 693         if (a->neg != b->neg)
 694                 {
 695                 if (a->neg)
 696                         return(-1);
 697                 else    return(1);
 698                 }
 699         if (a->neg == 0)
 700                 { gt=1; lt= -1; }
 701         else    { gt= -1; lt=1; }
 702
 703         if (a->top > b->top) return(gt);
 704         if (a->top < b->top) return(lt);
 705         for (i=a->top-1; i>=0; i--)
 706                 {
 707                 t1=a->d[i];
 708                 t2=b->d[i];
 709                 if (t1 > t2) return(gt);
 710                 if (t1 < t2) return(lt);
 711                 }
 712         return(0);
 713         }
 714
 715 int BN_set_bit(a, n)
 716 BIGNUM *a;
 717 int n;
 718         {
 719         int i,j,k;
 720
 721         i=n/BN_BITS2;
 722         j=n%BN_BITS2;
 723         if (a->top <= i)
 724                 {
 725                 if (bn_wexpand(a,i+1) == NULL) return(0);
 726                 for(k=a->top; k<i+1; k++)
 727                         a->d[k]=0;
 728                 a->top=i+1;
 729                 }
 730
 731         a->d[i]|=(1L<<j);
 732         return(1);
 733         }
 734
 735 int BN_clear_bit(a, n)
 736 BIGNUM *a;
 737 int n;
 738         {
 739         int i,j;
 740
 741         i=n/BN_BITS2;
 742         j=n%BN_BITS2;
 743         if (a->top <= i) return(0);
 744
 745         a->d[i]&=(~(1L<<j));
 746         bn_fix_top(a);
 747         return(1);
 748         }
 749
 750 int BN_is_bit_set(a, n)
 751 BIGNUM *a;
 752 int n;
 753         {
 754         int i,j;
 755
 756         if (n < 0) return(0);
 757         i=n/BN_BITS2;
 758         j=n%BN_BITS2;
 759         if (a->top <= i) return(0);
 760         return((a->d[i]&(((BN_ULONG)1)<<j))?1:0);
 761         }
 762
 763 int BN_mask_bits(a,n)
 764 BIGNUM *a;
 765 int n;
 766         {
 767         int b,w;
 768
 769         w=n/BN_BITS2;
 770         b=n%BN_BITS2;
 771         if (w >= a->top) return(0);
 772         if (b == 0)
 773                 a->top=w;
 774         else
 775                 {
 776                 a->top=w+1;
 777                 a->d[w]&= ~(BN_MASK2<<b);
 778                 }
 779         bn_fix_top(a);
 780         return(1);
 781         }
 782
 783 int bn_cmp_words(a,b,n)
 784 BN_ULONG *a,*b;
 785 int n;
 786         {
 787         int i;
 788         BN_ULONG aa,bb;
 789
 790         aa=a[n-1];
 791         bb=b[n-1];
 792         if (aa != bb) return((aa > bb)?1:-1);
 793         for (i=n-2; i>=0; i--)
 794                 {
 795                 aa=a[i];
 796                 bb=b[i];
 797                 if (aa != bb) return((aa > bb)?1:-1);
 798                 }
 799         return(0);
 800         }
 801