1 #ifndef __MP_H__
2 #define __MP_H__ 1
3 #ifdef __cplusplus
4 extern "C" {
5 #endif
6 
7 AUTOLIB(mp)
8 
9 /*
10 #pragma	src	"/sys/src/libmp"
11 #pragma	lib	"libmp.a"
12 */
13 
14 #define _MPINT 1
15 
16 typedef uint mpdigit;
17 
18 /* the code assumes mpdigit to be at least an int */
19 /* mpdigit must be an atomic type.  mpdigit is defined */
20 /* in the architecture specific u.h */
21 
22 typedef struct mpint mpint;
23 
24 struct mpint
25 {
26 	int	sign;	/* +1 or -1 */
27 	int	size;	/* allocated digits */
28 	int	top;	/* significant digits */
29 	mpdigit	*p;
30 	char	flags;
31 };
32 
33 enum
34 {
35 	MPstatic=	0x01,
36 	Dbytes=		sizeof(mpdigit),	/* bytes per digit */
37 	Dbits=		Dbytes*8		/* bits per digit */
38 };
39 
40 /* allocation */
41 void	mpsetminbits(int n);	/* newly created mpint's get at least n bits */
42 mpint*	mpnew(int n);		/* create a new mpint with at least n bits */
43 void	mpfree(mpint *b);
44 void	mpbits(mpint *b, int n);	/* ensure that b has at least n bits */
45 void	mpnorm(mpint *b);		/* dump leading zeros */
46 mpint*	mpcopy(mpint *b);
47 void	mpassign(mpint *old, mpint *new);
48 
49 /* random bits */
50 mpint*	mprand(int bits, void (*gen)(uchar*, int), mpint *b);
51 
52 /* conversion */
53 mpint*	strtomp(char*, char**, int, mpint*);	/* ascii */
54 int	mpfmt(Fmt*);
55 char*	mptoa(mpint*, int, char*, int);
56 mpint*	letomp(uchar*, uint, mpint*);	/* byte array, little-endian */
57 int	mptole(mpint*, uchar*, uint, uchar**);
58 mpint*	betomp(uchar*, uint, mpint*);	/* byte array, little-endian */
59 int	mptobe(mpint*, uchar*, uint, uchar**);
60 uint	mptoui(mpint*);			/* unsigned int */
61 mpint*	uitomp(uint, mpint*);
62 int	mptoi(mpint*);			/* int */
63 mpint*	itomp(int, mpint*);
64 uvlong	mptouv(mpint*);			/* unsigned vlong */
65 mpint*	uvtomp(uvlong, mpint*);
66 vlong	mptov(mpint*);			/* vlong */
67 mpint*	vtomp(vlong, mpint*);
68 
69 /* divide 2 digits by one */
70 void	mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);
71 
72 /* in the following, the result mpint may be */
73 /* the same as one of the inputs. */
74 void	mpadd(mpint *b1, mpint *b2, mpint *sum);	/* sum = b1+b2 */
75 void	mpsub(mpint *b1, mpint *b2, mpint *diff);	/* diff = b1-b2 */
76 void	mpleft(mpint *b, int shift, mpint *res);	/* res = b<<shift */
77 void	mpright(mpint *b, int shift, mpint *res);	/* res = b>>shift */
78 void	mpmul(mpint *b1, mpint *b2, mpint *prod);	/* prod = b1*b2 */
79 void	mpexp(mpint *b, mpint *e, mpint *m, mpint *res);	/* res = b**e mod m */
80 void	mpmod(mpint *b, mpint *m, mpint *remainder);	/* remainder = b mod m */
81 
82 /* quotient = dividend/divisor, remainder = dividend % divisor */
83 void	mpdiv(mpint *dividend, mpint *divisor,  mpint *quotient, mpint *remainder);
84 
85 /* return neg, 0, pos as b1-b2 is neg, 0, pos */
86 int	mpcmp(mpint *b1, mpint *b2);
87 
88 /* extended gcd return d, x, and y, s.t. d = gcd(a,b) and ax+by = d */
89 void	mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y);
90 
91 /* res = b**-1 mod m */
92 void	mpinvert(mpint *b, mpint *m, mpint *res);
93 
94 /* bit counting */
95 int	mpsignif(mpint*);	/* number of sigificant bits in mantissa */
96 int	mplowbits0(mpint*);	/* k, where n = 2**k * q for odd q */
97 
98 /* well known constants */
99 extern mpint	*mpzero, *mpone, *mptwo;
100 
101 /* sum[0:alen] = a[0:alen-1] + b[0:blen-1] */
102 /* prereq: alen >= blen, sum has room for alen+1 digits */
103 void	mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *sum);
104 
105 /* diff[0:alen-1] = a[0:alen-1] - b[0:blen-1] */
106 /* prereq: alen >= blen, diff has room for alen digits */
107 void	mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *diff);
108 
109 /* p[0:n] += m * b[0:n-1] */
110 /* prereq: p has room for n+1 digits */
111 void	mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p);
112 
113 /* p[0:n] -= m * b[0:n-1] */
114 /* prereq: p has room for n+1 digits */
115 int	mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p);
116 
117 /* p[0:alen*blen-1] = a[0:alen-1] * b[0:blen-1] */
118 /* prereq: alen >= blen, p has room for m*n digits */
119 void	mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p);
120 
121 /* sign of a - b or zero if the same */
122 int	mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen);
123 
124 /* divide the 2 digit dividend by the one digit divisor and stick in quotient */
125 /* we assume that the result is one digit - overflow is all 1's */
126 void	mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);
127 
128 /* playing with magnitudes */
129 int	mpmagcmp(mpint *b1, mpint *b2);
130 void	mpmagadd(mpint *b1, mpint *b2, mpint *sum);	/* sum = b1+b2 */
131 void	mpmagsub(mpint *b1, mpint *b2, mpint *sum);	/* sum = b1+b2 */
132 
133 /* chinese remainder theorem */
134 typedef struct CRTpre	CRTpre;		/* precomputed values for converting */
135 					/*  twixt residues and mpint */
136 typedef struct CRTres	CRTres;		/* residue form of an mpint */
137 
138 struct CRTres
139 {
140 	int	n;		/* number of residues */
141 	mpint	*r[1];		/* residues */
142 };
143 
144 CRTpre*	crtpre(int, mpint**);			/* precompute conversion values */
145 CRTres*	crtin(CRTpre*, mpint*);			/* convert mpint to residues */
146 void	crtout(CRTpre*, CRTres*, mpint*);	/* convert residues to mpint */
147 void	crtprefree(CRTpre*);
148 void	crtresfree(CRTres*);
149 
150 
151 /* #pragma	varargck	type	"B"	mpint* */
152 #ifdef __cplusplus
153 }
154 #endif
155 #endif