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 #ifndef BN_DEBUG
  60 # undef NDEBUG /* avoid conflicting definitions */
  61 # define NDEBUG
  62 #endif
  63
  64 #include <assert.h>
  65 #include <limits.h>
  66 #include <stdio.h>
  67 #include "cryptlib.h"
  68 #include "bn_lcl.h"
  69
  70 const char *BN_version="Big Number" OPENSSL_VERSION_PTEXT;
  71
  72 /* For a 32 bit machine
  73  * 2 -   4 ==  128
  74  * 3 -   8 ==  256
  75  * 4 -  16 ==  512
  76  * 5 -  32 == 1024
  77  * 6 -  64 == 2048
  78  * 7 - 128 == 4096
  79  * 8 - 256 == 8192
  80  */
  81 static int bn_limit_bits=0;
  82 static int bn_limit_num=8;        /* (1<<bn_limit_bits) */
  83 static int bn_limit_bits_low=0;
  84 static int bn_limit_num_low=8;    /* (1<<bn_limit_bits_low) */
  85 static int bn_limit_bits_high=0;
  86 static int bn_limit_num_high=8;   /* (1<<bn_limit_bits_high) */
  87 static int bn_limit_bits_mont=0;
  88 static int bn_limit_num_mont=8;   /* (1<<bn_limit_bits_mont) */
  89
  90 void BN_set_params(int mult, int high, int low, int mont)
  91         {
  92         if (mult >= 0)
  93                 {
  94                 if (mult > (sizeof(int)*8)-1)
  95                         mult=sizeof(int)*8-1;
  96                 bn_limit_bits=mult;
  97                 bn_limit_num=1<<mult;
  98                 }
  99         if (high >= 0)
 100                 {
 101                 if (high > (sizeof(int)*8)-1)
 102                         high=sizeof(int)*8-1;
 103                 bn_limit_bits_high=high;
 104                 bn_limit_num_high=1<<high;
 105                 }
 106         if (low >= 0)
 107                 {
 108                 if (low > (sizeof(int)*8)-1)
 109                         low=sizeof(int)*8-1;
 110                 bn_limit_bits_low=low;
 111                 bn_limit_num_low=1<<low;
 112                 }
 113         if (mont >= 0)
 114                 {
 115                 if (mont > (sizeof(int)*8)-1)
 116                         mont=sizeof(int)*8-1;
 117                 bn_limit_bits_mont=mont;
 118                 bn_limit_num_mont=1<<mont;
 119                 }
 120         }
 121
 122 int BN_get_params(int which)
 123         {
 124         if      (which == 0) return(bn_limit_bits);
 125         else if (which == 1) return(bn_limit_bits_high);
 126         else if (which == 2) return(bn_limit_bits_low);
 127         else if (which == 3) return(bn_limit_bits_mont);
 128         else return(0);
 129         }
 130
 131 BIGNUM *BN_value_one(void)
 132         {
 133         static BN_ULONG data_one=1L;
 134         static BIGNUM const_one={&data_one,1,1,0};
 135
 136         return(&const_one);
 137         }
 138
 139 char *BN_options(void)
 140         {
 141         static int init=0;
 142         static char data[16];
 143
 144         if (!init)
 145                 {
 146                 init++;
 147 #ifdef BN_LLONG
 148                 sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULLONG)*8,
 149                         (int)sizeof(BN_ULONG)*8);
 150 #else
 151                 sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULONG)*8,
 152                         (int)sizeof(BN_ULONG)*8);
 153 #endif
 154                 }
 155         return(data);
 156         }
 157
 158 int BN_num_bits_word(BN_ULONG l)
 159         {
 160         static const char bits[256]={
 161                 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,
 162                 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
 163                 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
 164                 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
 165                 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 166                 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 167                 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 168                 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 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                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 174                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 175                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 176                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 177                 };
 178
 179 #if defined(SIXTY_FOUR_BIT_LONG)
 180         if (l & 0xffffffff00000000L)
 181                 {
 182                 if (l & 0xffff000000000000L)
 183                         {
 184                         if (l & 0xff00000000000000L)
 185                                 {
 186                                 return(bits[(int)(l>>56)]+56);
 187                                 }
 188                         else    return(bits[(int)(l>>48)]+48);
 189                         }
 190                 else
 191                         {
 192                         if (l & 0x0000ff0000000000L)
 193                                 {
 194                                 return(bits[(int)(l>>40)]+40);
 195                                 }
 196                         else    return(bits[(int)(l>>32)]+32);
 197                         }
 198                 }
 199         else
 200 #else
 201 #ifdef SIXTY_FOUR_BIT
 202         if (l & 0xffffffff00000000LL)
 203                 {
 204                 if (l & 0xffff000000000000LL)
 205                         {
 206                         if (l & 0xff00000000000000LL)
 207                                 {
 208                                 return(bits[(int)(l>>56)]+56);
 209                                 }
 210                         else    return(bits[(int)(l>>48)]+48);
 211                         }
 212                 else
 213                         {
 214                         if (l & 0x0000ff0000000000LL)
 215                                 {
 216                                 return(bits[(int)(l>>40)]+40);
 217                                 }
 218                         else    return(bits[(int)(l>>32)]+32);
 219                         }
 220                 }
 221         else
 222 #endif
 223 #endif
 224                 {
 225 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 226                 if (l & 0xffff0000L)
 227                         {
 228                         if (l & 0xff000000L)
 229                                 return(bits[(int)(l>>24L)]+24);
 230                         else    return(bits[(int)(l>>16L)]+16);
 231                         }
 232                 else
 233 #endif
 234                         {
 235 #if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 236                         if (l & 0xff00L)
 237                                 return(bits[(int)(l>>8)]+8);
 238                         else
 239 #endif
 240                                 return(bits[(int)(l   )]  );
 241                         }
 242                 }
 243         }
 244
 245 int BN_num_bits(const BIGNUM *a)
 246         {
 247         BN_ULONG l;
 248         int i;
 249
 250         bn_check_top(a);
 251
 252         if (a->top == 0) return(0);
 253         l=a->d[a->top-1];
 254         assert(l != 0);
 255         i=(a->top-1)*BN_BITS2;
 256         return(i+BN_num_bits_word(l));
 257         }
 258
 259 void BN_clear_free(BIGNUM *a)
 260         {
 261         int i;
 262
 263         if (a == NULL) return;
 264         if (a->d != NULL)
 265                 {
 266                 memset(a->d,0,a->dmax*sizeof(a->d[0]));
 267                 if (!(BN_get_flags(a,BN_FLG_STATIC_DATA)))
 268                         OPENSSL_free(a->d);
 269                 }
 270         i=BN_get_flags(a,BN_FLG_MALLOCED);
 271         memset(a,0,sizeof(BIGNUM));
 272         if (i)
 273                 OPENSSL_free(a);
 274         }
 275
 276 void BN_free(BIGNUM *a)
 277         {
 278         if (a == NULL) return;
 279         if ((a->d != NULL) && !(BN_get_flags(a,BN_FLG_STATIC_DATA)))
 280                 OPENSSL_free(a->d);
 281         a->flags|=BN_FLG_FREE; /* REMOVE? */
 282         if (a->flags & BN_FLG_MALLOCED)
 283                 OPENSSL_free(a);
 284         }
 285
 286 void BN_init(BIGNUM *a)
 287         {
 288         memset(a,0,sizeof(BIGNUM));
 289         }
 290
 291 BIGNUM *BN_new(void)
 292         {
 293         BIGNUM *ret;
 294
 295         if ((ret=(BIGNUM *)OPENSSL_malloc(sizeof(BIGNUM))) == NULL)
 296                 {
 297                 BNerr(BN_F_BN_NEW,ERR_R_MALLOC_FAILURE);
 298                 return(NULL);
 299                 }
 300         ret->flags=BN_FLG_MALLOCED;
 301         ret->top=0;
 302         ret->neg=0;
 303         ret->dmax=0;
 304         ret->d=NULL;
 305         return(ret);
 306         }
 307
 308 /* This is an internal function that should not be used in applications.
 309  * It ensures that 'b' has enough room for a 'words' word number number.
 310  * It is mostly used by the various BIGNUM routines. If there is an error,
 311  * NULL is returned. If not, 'b' is returned. */
 312
 313 BIGNUM *bn_expand2(BIGNUM *b, int words)
 314         {
 315         BN_ULONG *A,*a;
 316         const BN_ULONG *B;
 317         int i;
 318
 319         bn_check_top(b);
 320
 321         if (words > b->dmax)
 322                 {
 323                 if (words > (INT_MAX/(4*BN_BITS2)))
 324                         {
 325                         BNerr(BN_F_BN_EXPAND2,BN_R_BIGNUM_TOO_LONG);
 326                         return NULL;
 327                         }
 328
 329                 bn_check_top(b);
 330                 if (BN_get_flags(b,BN_FLG_STATIC_DATA))
 331                         {
 332                         BNerr(BN_F_BN_EXPAND2,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
 333                         return(NULL);
 334                         }
 335                 a=A=(BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG)*(words+1));
 336                 if (A == NULL)
 337                         {
 338                         BNerr(BN_F_BN_EXPAND2,ERR_R_MALLOC_FAILURE);
 339                         return(NULL);
 340                         }
 341 #if 1
 342                 B=b->d;
 343                 /* Check if the previous number needs to be copied */
 344                 if (B != NULL)
 345                         {
 346 #if 0
 347                         /* This lot is an unrolled loop to copy b->top
 348                          * BN_ULONGs from B to A
 349                          */
 350 /*
 351  * I have nothing against unrolling but it's usually done for
 352  * several reasons, namely:
 353  * - minimize percentage of decision making code, i.e. branches;
 354  * - avoid cache trashing;
 355  * - make it possible to schedule loads earlier;
 356  * Now let's examine the code below. The cornerstone of C is
 357  * "programmer is always right" and that's what we love it for:-)
 358  * For this very reason C compilers have to be paranoid when it
 359  * comes to data aliasing and assume the worst. Yeah, but what
 360  * does it mean in real life? This means that loop body below will
 361  * be compiled to sequence of loads immediately followed by stores
 362  * as compiler assumes the worst, something in A==B+1 style. As a
 363  * result CPU pipeline is going to starve for incoming data. Secondly
 364  * if A and B happen to share same cache line such code is going to
 365  * cause severe cache trashing. Both factors have severe impact on
 366  * performance of modern CPUs and this is the reason why this
 367  * particular piece of code is #ifdefed away and replaced by more
 368  * "friendly" version found in #else section below. This comment
 369  * also applies to BN_copy function.
 370  *
 371  *                                      <appro@fy.chalmers.se>
 372  */
 373                         for (i=b->top&(~7); i>0; i-=8)
 374                                 {
 375                                 A[0]=B[0]; A[1]=B[1]; A[2]=B[2]; A[3]=B[3];
 376                                 A[4]=B[4]; A[5]=B[5]; A[6]=B[6]; A[7]=B[7];
 377                                 A+=8;
 378                                 B+=8;
 379                                 }
 380                         switch (b->top&7)
 381                                 {
 382                         case 7:
 383                                 A[6]=B[6];
 384                         case 6:
 385                                 A[5]=B[5];
 386                         case 5:
 387                                 A[4]=B[4];
 388                         case 4:
 389                                 A[3]=B[3];
 390                         case 3:
 391                                 A[2]=B[2];
 392                         case 2:
 393                                 A[1]=B[1];
 394                         case 1:
 395                                 A[0]=B[0];
 396                         case 0:
 397                                 /* I need the 'case 0' entry for utrix cc.
 398                                  * If the optimizer is turned on, it does the
 399                                  * switch table by doing
 400                                  * a=top&7
 401                                  * a--;
 402                                  * goto jump_table[a];
 403                                  * If top is 0, this makes us jump to 0xffffffc
 404                                  * which is rather bad :-(.
 405                                  * eric 23-Apr-1998
 406                                  */
 407                                 ;
 408                                 }
 409 #else
 410                         for (i=b->top>>2; i>0; i--,A+=4,B+=4)
 411                                 {
 412                                 /*
 413                                  * The fact that the loop is unrolled
 414                                  * 4-wise is a tribute to Intel. It's
 415                                  * the one that doesn't have enough
 416                                  * registers to accomodate more data.
 417                                  * I'd unroll it 8-wise otherwise:-)
 418                                  *
 419                                  *              <appro@fy.chalmers.se>
 420                                  */
 421                                 BN_ULONG a0,a1,a2,a3;
 422                                 a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3];
 423                                 A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3;
 424                                 }
 425                         switch (b->top&3)
 426                                 {
 427                                 case 3: A[2]=B[2];
 428                                 case 2: A[1]=B[1];
 429                                 case 1: A[0]=B[0];
 430                                 case 0: ; /* ultrix cc workaround, see above */
 431                                 }
 432 #endif
 433                         OPENSSL_free(b->d);
 434                         }
 435
 436                 b->d=a;
 437                 b->dmax=words;
 438
 439                 /* Now need to zero any data between b->top and b->max */
 440
 441                 A= &(b->d[b->top]);
 442                 for (i=(b->dmax - b->top)>>3; i>0; i--,A+=8)
 443                         {
 444                         A[0]=0; A[1]=0; A[2]=0; A[3]=0;
 445                         A[4]=0; A[5]=0; A[6]=0; A[7]=0;
 446                         }
 447                 for (i=(b->dmax - b->top)&7; i>0; i--,A++)
 448                         A[0]=0;
 449 #else
 450                         memset(A,0,sizeof(BN_ULONG)*(words+1));
 451                         memcpy(A,b->d,sizeof(b->d[0])*b->top);
 452                         b->d=a;
 453                         b->max=words;
 454 #endif
 455
 456 /*              memset(&(p[b->max]),0,((words+1)-b->max)*sizeof(BN_ULONG)); */
 457 /*      { int i; for (i=b->max; i<words+1; i++) p[i]=i;} */
 458
 459                 }
 460         return(b);
 461         }
 462
 463 BIGNUM *BN_dup(const BIGNUM *a)
 464         {
 465         BIGNUM *r;
 466
 467         if (a == NULL) return NULL;
 468
 469         bn_check_top(a);
 470
 471         r=BN_new();
 472         if (r == NULL) return(NULL);
 473         return((BIGNUM *)BN_copy(r,a));
 474         }
 475
 476 BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
 477         {
 478         int i;
 479         BN_ULONG *A;
 480         const BN_ULONG *B;
 481
 482         bn_check_top(b);
 483
 484         if (a == b) return(a);
 485         if (bn_wexpand(a,b->top) == NULL) return(NULL);
 486
 487 #if 1
 488         A=a->d;
 489         B=b->d;
 490         for (i=b->top>>2; i>0; i--,A+=4,B+=4)
 491                 {
 492                 BN_ULONG a0,a1,a2,a3;
 493                 a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3];
 494                 A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3;
 495                 }
 496         switch (b->top&3)
 497                 {
 498                 case 3: A[2]=B[2];
 499                 case 2: A[1]=B[1];
 500                 case 1: A[0]=B[0];
 501                 case 0: ; /* ultrix cc workaround, see comments in bn_expand2 */
 502                 }
 503 #else
 504         memcpy(a->d,b->d,sizeof(b->d[0])*b->top);
 505 #endif
 506
 507 /*      memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));*/
 508         a->top=b->top;
 509         if ((a->top == 0) && (a->d != NULL))
 510                 a->d[0]=0;
 511         a->neg=b->neg;
 512         return(a);
 513         }
 514
 515 void BN_clear(BIGNUM *a)
 516         {
 517         if (a->d != NULL)
 518                 memset(a->d,0,a->dmax*sizeof(a->d[0]));
 519         a->top=0;
 520         a->neg=0;
 521         }
 522
 523 BN_ULONG BN_get_word(BIGNUM *a)
 524         {
 525         int i,n;
 526         BN_ULONG ret=0;
 527
 528         n=BN_num_bytes(a);
 529         if (n > sizeof(BN_ULONG))
 530                 return(BN_MASK2);
 531         for (i=a->top-1; i>=0; i--)
 532                 {
 533 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
 534                 ret<<=BN_BITS4; /* stops the compiler complaining */
 535                 ret<<=BN_BITS4;
 536 #else
 537                 ret=0;
 538 #endif
 539                 ret|=a->d[i];
 540                 }
 541         return(ret);
 542         }
 543
 544 int BN_set_word(BIGNUM *a, BN_ULONG w)
 545         {
 546         int i,n;
 547         if (bn_expand(a,sizeof(BN_ULONG)*8) == NULL) return(0);
 548
 549         n=sizeof(BN_ULONG)/BN_BYTES;
 550         a->neg=0;
 551         a->top=0;
 552         a->d[0]=(BN_ULONG)w&BN_MASK2;
 553         if (a->d[0] != 0) a->top=1;
 554         for (i=1; i<n; i++)
 555                 {
 556                 /* the following is done instead of
 557                  * w>>=BN_BITS2 so compilers don't complain
 558                  * on builds where sizeof(long) == BN_TYPES */
 559 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
 560                 w>>=BN_BITS4;
 561                 w>>=BN_BITS4;
 562 #else
 563                 w=0;
 564 #endif
 565                 a->d[i]=(BN_ULONG)w&BN_MASK2;
 566                 if (a->d[i] != 0) a->top=i+1;
 567                 }
 568         return(1);
 569         }
 570
 571 /* ignore negative */
 572 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
 573         {
 574         unsigned int i,m;
 575         unsigned int n;
 576         BN_ULONG l;
 577
 578         if (ret == NULL) ret=BN_new();
 579         if (ret == NULL) return(NULL);
 580         l=0;
 581         n=len;
 582         if (n == 0)
 583                 {
 584                 ret->top=0;
 585                 return(ret);
 586                 }
 587         if (bn_expand(ret,(int)(n+2)*8) == NULL)
 588                 return(NULL);
 589         i=((n-1)/BN_BYTES)+1;
 590         m=((n-1)%(BN_BYTES));
 591         ret->top=i;
 592         while (n-- > 0)
 593                 {
 594                 l=(l<<8L)| *(s++);
 595                 if (m-- == 0)
 596                         {
 597                         ret->d[--i]=l;
 598                         l=0;
 599                         m=BN_BYTES-1;
 600                         }
 601                 }
 602         /* need to call this due to clear byte at top if avoiding
 603          * having the top bit set (-ve number) */
 604         bn_fix_top(ret);
 605         return(ret);
 606         }
 607
 608 /* ignore negative */
 609 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
 610         {
 611         int n,i;
 612         BN_ULONG l;
 613
 614         n=i=BN_num_bytes(a);
 615         while (i-- > 0)
 616                 {
 617                 l=a->d[i/BN_BYTES];
 618                 *(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff;
 619                 }
 620         return(n);
 621         }
 622
 623 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
 624         {
 625         int i;
 626         BN_ULONG t1,t2,*ap,*bp;
 627
 628         bn_check_top(a);
 629         bn_check_top(b);
 630
 631         i=a->top-b->top;
 632         if (i != 0) return(i);
 633         ap=a->d;
 634         bp=b->d;
 635         for (i=a->top-1; i>=0; i--)
 636                 {
 637                 t1= ap[i];
 638                 t2= bp[i];
 639                 if (t1 != t2)
 640                         return(t1 > t2?1:-1);
 641                 }
 642         return(0);
 643         }
 644
 645 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
 646         {
 647         int i;
 648         int gt,lt;
 649         BN_ULONG t1,t2;
 650
 651         if ((a == NULL) || (b == NULL))
 652                 {
 653                 if (a != NULL)
 654                         return(-1);
 655                 else if (b != NULL)
 656                         return(1);
 657                 else
 658                         return(0);
 659                 }
 660
 661         bn_check_top(a);
 662         bn_check_top(b);
 663
 664         if (a->neg != b->neg)
 665                 {
 666                 if (a->neg)
 667                         return(-1);
 668                 else    return(1);
 669                 }
 670         if (a->neg == 0)
 671                 { gt=1; lt= -1; }
 672         else    { gt= -1; lt=1; }
 673
 674         if (a->top > b->top) return(gt);
 675         if (a->top < b->top) return(lt);
 676         for (i=a->top-1; i>=0; i--)
 677                 {
 678                 t1=a->d[i];
 679                 t2=b->d[i];
 680                 if (t1 > t2) return(gt);
 681                 if (t1 < t2) return(lt);
 682                 }
 683         return(0);
 684         }
 685
 686 int BN_set_bit(BIGNUM *a, int n)
 687         {
 688         int i,j,k;
 689
 690         i=n/BN_BITS2;
 691         j=n%BN_BITS2;
 692         if (a->top <= i)
 693                 {
 694                 if (bn_wexpand(a,i+1) == NULL) return(0);
 695                 for(k=a->top; k<i+1; k++)
 696                         a->d[k]=0;
 697                 a->top=i+1;
 698                 }
 699
 700         a->d[i]|=(((BN_ULONG)1)<<j);
 701         return(1);
 702         }
 703
 704 int BN_clear_bit(BIGNUM *a, int n)
 705         {
 706         int i,j;
 707
 708         i=n/BN_BITS2;
 709         j=n%BN_BITS2;
 710         if (a->top <= i) return(0);
 711
 712         a->d[i]&=(~(((BN_ULONG)1)<<j));
 713         bn_fix_top(a);
 714         return(1);
 715         }
 716
 717 int BN_is_bit_set(const BIGNUM *a, int n)
 718         {
 719         int i,j;
 720
 721         if (n < 0) return(0);
 722         i=n/BN_BITS2;
 723         j=n%BN_BITS2;
 724         if (a->top <= i) return(0);
 725         return((a->d[i]&(((BN_ULONG)1)<<j))?1:0);
 726         }
 727
 728 int BN_mask_bits(BIGNUM *a, int n)
 729         {
 730         int b,w;
 731
 732         w=n/BN_BITS2;
 733         b=n%BN_BITS2;
 734         if (w >= a->top) return(0);
 735         if (b == 0)
 736                 a->top=w;
 737         else
 738                 {
 739                 a->top=w+1;
 740                 a->d[w]&= ~(BN_MASK2<<b);
 741                 }
 742         bn_fix_top(a);
 743         return(1);
 744         }
 745
 746 int bn_cmp_words(BN_ULONG *a, BN_ULONG *b, int n)
 747         {
 748         int i;
 749         BN_ULONG aa,bb;
 750
 751         aa=a[n-1];
 752         bb=b[n-1];
 753         if (aa != bb) return((aa > bb)?1:-1);
 754         for (i=n-2; i>=0; i--)
 755                 {
 756                 aa=a[i];
 757                 bb=b[i];
 758                 if (aa != bb) return((aa > bb)?1:-1);
 759                 }
 760         return(0);
 761         }
 762