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