libsecurity_cryptkit/lib/giantIntegers.h

   1 /* Copyright (c) 1998 Apple Computer, Inc.  All rights reserved.
   2  *
   3  * NOTICE: USE OF THE MATERIALS ACCOMPANYING THIS NOTICE IS SUBJECT
   4  * TO THE TERMS OF THE SIGNED "FAST ELLIPTIC ENCRYPTION (FEE) REFERENCE
   5  * SOURCE CODE EVALUATION AGREEMENT" BETWEEN APPLE COMPUTER, INC. AND THE
   6  * ORIGINAL LICENSEE THAT OBTAINED THESE MATERIALS FROM APPLE COMPUTER,
   7  * INC.  ANY USE OF THESE MATERIALS NOT PERMITTED BY SUCH AGREEMENT WILL
   8  * EXPOSE YOU TO LIABILITY.
   9  ***************************************************************************
  10  *
  11  * giantIntegers.h - large-integer arithmetic library.
  12  *
  13  * Revision History
  14  * ----------------
  15  * 05 Oct 98    Doug Mitchell at Apple
  16  *      Default "unsigned int" giantDigit for __i386__ and __i486__
  17  * 08 May 97    Doug Mitchell at Apple
  18  *      Changed size of giantstruct.n to 1 for Mac build
  19  *  ? ? 1991    Richard Crandall at Next
  20  *      Created.
  21  */
  22
  23 #ifndef _CK_NSGIANTINTS_H_
  24 #define _CK_NSGIANTINTS_H_
  25
  26 #include <security_cryptkit/ckconfig.h>
  27
  28 #ifdef __cplusplus
  29 extern "C" {
  30 #endif
  31
  32 /*
  33  * Size of giant digit.
  34  */
  35 #if     NeXT || __i386__ || __i486__
  36
  37 typedef unsigned int giantDigit;
  38
  39 /*
  40  * used to divide by GIANT_BITS_PER_DIGIT via shift - no easy way to get
  41  * the compiler to calculate this.
  42  */
  43 #define GIANT_LOG2_BITS_PER_DIGIT 5
  44
  45 #elif defined(macintosh) || defined(__ppc__)
  46
  47 typedef unsigned int giantDigit;
  48 #define GIANT_LOG2_BITS_PER_DIGIT       5
  49
  50 #else
  51
  52 typedef unsigned short giantDigit;
  53 #define GIANT_LOG2_BITS_PER_DIGIT       4
  54
  55 #endif
  56
  57 /* platform-independent digit manipulation macros */
  58
  59 #define GIANT_BYTES_PER_DIGIT   (sizeof(giantDigit))
  60 #define GIANT_BITS_PER_DIGIT    (8 * GIANT_BYTES_PER_DIGIT)
  61 #define GIANT_DIGIT_MASK        ((giantDigit)~0)
  62 #define BYTES_TO_GIANT_DIGITS(x)        \
  63         ((x + GIANT_BYTES_PER_DIGIT - 1) / GIANT_BYTES_PER_DIGIT)
  64
  65 #define MAX_DIGITS ((1<<18)+(1<<17))
  66                         /* 2^(16*MAX_DIGITS)-1 will fit into a giant. */
  67
  68 /*
  69  * The giant stack package is a local cache which allows us to avoid calls
  70  * to malloc() for borrowGiant(). On a 90 Mhz Pentium, enabling the
  71  * giant stack package shows about a 1.35 speedup factor over an identical
  72  * CryptKit without the giant stacks enabled.
  73  */
  74 #define GIANTS_VIA_STACK        CRYPTKIT_GIANT_STACK_ENABLE
  75
  76 typedef struct {
  77          int sign;              /* number of giantDigits = abs(sign) */
  78      unsigned capacity;         /* largest possible number of giantDigits */
  79          giantDigit n[1];               /* n[0] is l.s. digit */
  80 } giantstruct;
  81 typedef giantstruct *giant;
  82
  83 #if             GIANTS_VIA_STACK
  84 /*
  85  * For giant stack debug only
  86  * Set default giant size (i.e., for newGiant(0) and borrowGiant(0))
  87  */
  88 void setGiantSize(unsigned numDigits);
  89
  90 /*
  91  * Initialize giant stacks, with up to specified max giant size.
  92  */
  93 void initGiantStacks(unsigned maxDigits);
  94
  95 /*
  96  * Free giant stacks on shutdown.
  97  */
  98 void freeGiantStacks();
  99
 100 #endif  /* GIANTS_VIA_STACK */
 101
 102 giant newGiant(unsigned numDigits);
 103 giant copyGiant(giant x);
 104 void freeGiant(giant x);
 105
 106 giant borrowGiant(unsigned numDigits);  /* get a temporary */
 107 void returnGiant(giant);                /* return it */
 108 unsigned bitlen(giant n);               /* Returns the bit-length n;
 109                                          * e.g. n=7 returns 3. */
 110 int bitval(giant n, int pos);           /* Returns the value of bit pos of n */
 111 int isZero(giant g);                    /* Returns whether g is zero */
 112 int isone(giant g);                     /* Returns whether g is 1 */
 113 void gtog(giant src, giant dest);       /* Copies one giant to another */
 114 void int_to_giant(int n, giant g);      /* Gives a giant an int value */
 115 int gcompg(giant a, giant b);           /* Returns 1, 0, -1 as a>b, a=b, a<b */
 116 void addg(giant a, giant b);            /* b += a */
 117 void iaddg(int a, giant b);             /* b += a */
 118 void subg(giant a, giant b);            /* b -= a. */
 119 void imulg(unsigned n, giant g);        /* g *= n */
 120 void negg(giant g);                     /* g := -g. */
 121 int binvg(giant n, giant x);            /* Same as invg(), but uses binary
 122                                          * division. */
 123 int binvaux(giant p, giant x);
 124 void gmersennemod(int n, giant g);      /* g := g (mod 2^n-1). */
 125 void gshiftleft(int bits, giant g);     /* Shift g left by bits, introducing
 126                                          * zeros on the right. */
 127 void gshiftright(int bits, giant g);    /* Shift g right by bits, losing bits
 128                                          * on the right. */
 129 void extractbits(unsigned n, giant src, giant dest);
 130                                         /* dest becomes lowermost n bits of
 131                                          * src.  Equivalent to
 132                                          * dest = src % 2^n */
 133
 134 void grammarSquare(giant a);            /* g *= g. */
 135 #define gsquare(g) grammarSquare(g)
 136
 137 void mulg(giant a, giant b);            /* b *= a. */
 138 int gsign(giant g);                     /* Returns the sign of g: -1, 0, 1. */
 139 void gtrimSign(giant g);                /* Adjust sign for possible leading
 140                                          * (m.s.) zero digits */
 141
 142 void divg(giant d, giant n);            /* n becomes |n|/d. n is arbitrary,
 143                                          * but the denominator d must be
 144                                          * positive! */
 145 int scompg(int n, giant g);
 146 void modg(giant den, giant num);        /* num := num mod den, any positive
 147                                          * den. */
 148 void clearGiant(giant g);               /* zero a giant's data */
 149
 150 /*
 151  * Optimized modg and divg, with routine to calculate necessary reciprocal
 152  */
 153 void make_recip(giant d, giant r);
 154 void divg_via_recip(giant denom, giant recip, giant numer);
 155                                         /* numer := |n|/d. */
 156 void modg_via_recip(giant denom, giant recip, giant numer);
 157                                         /* num := num mod den */
 158
 159 #ifdef __cplusplus
 160 }
 161 #endif
 162
 163 #endif  /* _CK_NSGIANTINTS_H_ */