--- /dev/null
+/**************************************************************
+ *
+ * giants.h
+ *
+ * Header file for large-integer arithmetic library giants.c.
+ *
+ * Updates:
+ * 18 Jul 99 REC Added fer_mod().
+ * 30 Apr 98 JF USE_ASSEMBLER_MUL removed
+ * 29 Apr 98 JF Function prototypes cleaned up
+ * 20 Apr 97 RDW
+ *
+ * c. 1997 Perfectly Scientific, Inc.
+ * All Rights Reserved.
+ *
+ **************************************************************/
+
+
+/**************************************************************
+ *
+ * Error Codes
+ *
+ **************************************************************/
+
+#define DIVIDEBYZERO 1
+#define OVFLOW 2
+#define SIGN 3
+#define OVERRANGE 4
+#define AUTO_MUL 0
+#define GRAMMAR_MUL 1
+#define FFT_MUL 2
+#define KARAT_MUL 3
+
+/**************************************************************
+ *
+ * Preprocessor definitions
+ *
+ **************************************************************/
+
+/* 2^(16*MAX_SHORTS)-1 will fit into a giant, but take care:
+ * one usually has squares, etc. of giants involved, and
+ * every intermediate giant in a calculation must fit into
+ * this many shorts. Thus, if you want systematically to effect
+ * arithmetic on B-bit operands, you need MAX_SHORTS > B/8,
+ * perferably a tad larger than this; e.g. MAX_SHORTS > B/7.
+ */
+#define MAX_SHORTS (1<<19)
+
+#define INFINITY (-1)
+#define FA 0
+#define TR 1
+#define COLUMNWIDTH 64
+
+#define TWOPI (double)(2*3.1415926535897932384626433)
+#define SQRT2 (double)(1.414213562373095048801688724209)
+#define SQRTHALF (double)(0.707106781186547524400844362104)
+#define TWO16 (double)(65536.0)
+#define TWOM16 (double)(0.0000152587890625)
+
+/* Decimal digit ceiling in digit-input routines. */
+#define MAX_DIGITS 10000
+
+/* Next, mumber of shorts per operand
+ at which Karatsuba breaks over. */
+#define KARAT_BREAK 40
+
+/* Next, mumber of shorts per operand
+ at which FFT breaks over. */
+#define FFT_BREAK 200
+
+#define newmin(a,b) ((a)<(b)? (a) : (b))
+#define newmax(a,b) ((a)>(b)? (a) : (b))
+
+/* Maximum number of recursive steps needed to calculate
+ * gcds of integers. */
+#define STEPS 32
+
+/* The limit below which hgcd is too ponderous */
+#define GCDLIMIT 5000
+
+/* The limit below which ordinary ints will be used */
+#define INTLIMIT 31
+
+/* Size by which to increment the stack used in pushg() and popg(). */
+#define STACK_GROW 16
+
+#define gin(x) gread(x,stdin)
+#define gout(x) gwriteln(x,stdout)
+
+
+/**************************************************************
+ *
+ * Structure definitions
+ *
+ **************************************************************/
+
+typedef struct
+{
+ int sign;
+ unsigned short n[1]; /* number of shorts = abs(sign) */
+} giantstruct;
+
+typedef giantstruct *giant;
+
+typedef struct _matrix
+{
+ giant ul; /* upper left */
+ giant ur; /* upper right */
+ giant ll; /* lower left */
+ giant lr; /* lower right */
+} *gmatrix;
+
+typedef struct
+{
+ double re;
+ double im;
+} complex;
+
+
+/**************************************************************
+ *
+ * Function Prototypes
+ *
+ **************************************************************/
+
+/**************************************************************
+ *
+ * Initialization and utility functions
+ *
+ **************************************************************/
+
+/* trig lookups. */
+void init_sinCos(int);
+double s_sin(int);
+double s_cos(int);
+
+
+/* Creates a new giant, numshorts = INFINITY invokes the
+ * maximum MAX_SHORTS. */
+giant newgiant(int numshorts);
+
+/* Creates a new giant matrix, but does not malloc
+ * the component giants. */
+gmatrix newgmatrix(void);
+
+/* Returns the bit-length n; e.g. n=7 returns 3. */
+int bitlen(giant n);
+
+/* Returns the value of the pos bit of n. */
+int bitval(giant n, int pos);
+
+/* Returns whether g is one. */
+int isone(giant g);
+
+/* Returns whether g is zero. */
+int isZero(giant g);
+
+/* Copies one giant to another. */
+void gtog(giant src, giant dest);
+
+/* Integer <-> giant. */
+void itog(int n, giant g);
+signed int gtoi (giant);
+
+/* Returns the sign of g: -1, 0, 1. */
+int gsign(giant g);
+
+/* Returns 1, 0, -1 as a>b, a=b, a<b. */
+int gcompg(giant a, giant b);
+
+/* Set AUTO_MUL for automatic FFT crossover (this is the
+ * default), set FFT_MUL for forced FFT multiply, set
+ * GRAMMAR_MUL for forced grammar school multiply. */
+void setmulmode(int mode);
+
+/**************************************************************
+ *
+ * I/O Routines
+ *
+ **************************************************************/
+
+/* Output the giant in decimal, with optional newlines. */
+void gwrite(giant g, FILE *fp, int newlines);
+
+/* Output the giant in decimal, with both '\'-newline
+ * notation and a final newline. */
+void gwriteln(giant g, FILE *fp);
+
+/* Input the giant in decimal, assuming the formatting of
+ * 'gwriteln'. */
+void gread(giant g, FILE *fp);
+
+/**************************************************************
+ *
+ * Math Functions
+ *
+ **************************************************************/
+
+/* g := -g. */
+void negg(giant g);
+
+/* g := |g|. */
+void absg(giant g);
+
+/* g += i, with i non-negative and < 2^16. */
+void iaddg(int i,giant g);
+
+/* b += a. */
+void addg(giant a, giant b);
+
+/* b -= a. */
+void subg(giant a, giant b);
+
+/* Returns the number of trailing zero bits in g. */
+int numtrailzeros(giant g);
+
+/* u becomes greatest power of two not exceeding u/v. */
+void bdivg(giant v, giant u);
+
+/* Same as invg, but uses bdivg. */
+int binvg(giant n, giant x);
+
+/* If 1/x exists (mod n), 1 is returned and x := 1/x. If
+ * inverse does not exist, 0 is returned and x := GCD(n, x). */
+int invg(giant n, giant x);
+
+int mersenneinvg(int q, giant x);
+
+/* Classical GCD, x:= GCD(n, x). */
+void cgcdg(giant n, giant x);
+
+/* General GCD, x:= GCD(n, x). */
+void gcdg(giant n, giant x);
+
+/* Binary GCD, x:= GCD(n, x). */
+void bgcdg(giant n, giant x);
+
+/* g := m^n, no mod is performed. */
+void powerg(int a, int b, giant g);
+
+/* r becomes the steady-state reciprocal 2^(2b)/d, where
+ * b = bit-length of d-1. */
+void make_recip(giant d, giant r);
+
+/* n := [n/d], d positive, using stored reciprocal directly. */
+void divg_via_recip(giant d, giant r, giant n);
+
+/* n := n % d, d positive, using stored reciprocal directly. */
+void modg_via_recip(giant d, giant r, giant n);
+
+/* num := num % den, any positive den. */
+void modg(giant den, giant num);
+
+/* a becomes (a*b) (mod 2^q-k) where q % 16 == 0 and k is "small"
+ * (0 < k < 65535). Returns 0 if unsuccessful, otherwise 1. */
+int feemulmod(giant x, giant y, int q, int k);
+
+/* g := g/n, and (g mod n) is returned. */
+int idivg(int n, giant g);
+
+/* num := [num/den], any positive den. */
+void divg(giant den, giant num);
+
+/* num := [num/den], any positive den. */
+void powermod(giant x, int n, giant z);
+
+/* x := x^n (mod z). */
+void powermodg(giant x, giant n, giant z);
+
+/* x := x^n (mod 2^q+1). */
+void fermatpowermod(giant x, int n, int q);
+
+/* x := x^n (mod 2^q+1). */
+void fermatpowermodg(giant x, giant n, int q);
+
+/* x := x^n (mod 2^q-1). */
+void mersennepowermod(giant x, int n, int q);
+
+/* x := x^n (mod 2^q-1). */
+void mersennepowermodg(giant x, giant n, int q);
+
+/* Shift g left by bits, introducing zeros on the right. */
+void gshiftleft(int bits, giant g);
+
+/* Shift g right by bits, losing bits on the right. */
+void gshiftright(int bits, giant g);
+
+/* dest becomes lowermost n bits of src.
+ * Equivalent to dest = src % 2^n. */
+void extractbits(int n, giant src, giant dest);
+
+/* negate g. g is mod 2^n+1. */
+void fermatnegate(int n, giant g);
+
+/* g := g (mod 2^n-1). */
+void mersennemod(int n, giant g);
+
+/* g := g (mod 2^n+1). */
+void fermatmod(int n, giant g);
+
+/* g := g (mod 2^n+1). */
+void fer_mod(int n, giant g, giant modulus);
+
+/* g *= s. */
+void smulg(unsigned short s, giant g);
+
+/* g *= g. */
+void squareg(giant g);
+
+/* b *= a. */
+void mulg(giant a, giant b);
+
+/* A giant gcd. Modifies its arguments. */
+void ggcd(giant xx, giant yy);
projects / apple / security.git / blobdiff