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