aboutsummaryrefslogtreecommitdiff
path: root/include/mp.h
blob: d64bf0cba89b14176f6add8eb5f2617d7b1f7885 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#ifndef __MP_H__
#define __MP_H__ 1
#ifdef __cplusplus
extern "C" {
#endif

AUTOLIB(mp)

/*
#pragma	src	"/sys/src/libmp"
#pragma	lib	"libmp.a"
*/

#define _MPINT 1

typedef uint mpdigit;

/* the code assumes mpdigit to be at least an int */
/* mpdigit must be an atomic type.  mpdigit is defined */
/* in the architecture specific u.h */

typedef struct mpint mpint;

struct mpint
{
	int	sign;	/* +1 or -1 */
	int	size;	/* allocated digits */
	int	top;	/* significant digits */
	mpdigit	*p;
	char	flags;
};

enum
{
	MPstatic=	0x01,
	Dbytes=		sizeof(mpdigit),	/* bytes per digit */
	Dbits=		Dbytes*8		/* bits per digit */
};

/* allocation */
void	mpsetminbits(int n);	/* newly created mpint's get at least n bits */
mpint*	mpnew(int n);		/* create a new mpint with at least n bits */
void	mpfree(mpint *b);
void	mpbits(mpint *b, int n);	/* ensure that b has at least n bits */
void	mpnorm(mpint *b);		/* dump leading zeros */
mpint*	mpcopy(mpint *b);
void	mpassign(mpint *old, mpint *new);

/* random bits */
mpint*	mprand(int bits, void (*gen)(uchar*, int), mpint *b);

/* conversion */
mpint*	strtomp(char*, char**, int, mpint*);	/* ascii */
int	mpfmt(Fmt*);
char*	mptoa(mpint*, int, char*, int);
mpint*	letomp(uchar*, uint, mpint*);	/* byte array, little-endian */
int	mptole(mpint*, uchar*, uint, uchar**);
mpint*	betomp(uchar*, uint, mpint*);	/* byte array, little-endian */
int	mptobe(mpint*, uchar*, uint, uchar**);
uint	mptoui(mpint*);			/* unsigned int */
mpint*	uitomp(uint, mpint*);
int	mptoi(mpint*);			/* int */
mpint*	itomp(int, mpint*);
uvlong	mptouv(mpint*);			/* unsigned vlong */
mpint*	uvtomp(uvlong, mpint*);
vlong	mptov(mpint*);			/* vlong */
mpint*	vtomp(vlong, mpint*);

/* divide 2 digits by one */
void	mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);

/* in the following, the result mpint may be */
/* the same as one of the inputs. */
void	mpadd(mpint *b1, mpint *b2, mpint *sum);	/* sum = b1+b2 */
void	mpsub(mpint *b1, mpint *b2, mpint *diff);	/* diff = b1-b2 */
void	mpleft(mpint *b, int shift, mpint *res);	/* res = b<<shift */
void	mpright(mpint *b, int shift, mpint *res);	/* res = b>>shift */
void	mpmul(mpint *b1, mpint *b2, mpint *prod);	/* prod = b1*b2 */
void	mpexp(mpint *b, mpint *e, mpint *m, mpint *res);	/* res = b**e mod m */
void	mpmod(mpint *b, mpint *m, mpint *remainder);	/* remainder = b mod m */

/* quotient = dividend/divisor, remainder = dividend % divisor */
void	mpdiv(mpint *dividend, mpint *divisor,  mpint *quotient, mpint *remainder);

/* return neg, 0, pos as b1-b2 is neg, 0, pos */
int	mpcmp(mpint *b1, mpint *b2);

/* extended gcd return d, x, and y, s.t. d = gcd(a,b) and ax+by = d */
void	mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y);

/* res = b**-1 mod m */
void	mpinvert(mpint *b, mpint *m, mpint *res);

/* bit counting */
int	mpsignif(mpint*);	/* number of sigificant bits in mantissa */
int	mplowbits0(mpint*);	/* k, where n = 2**k * q for odd q */

/* well known constants */
extern mpint	*mpzero, *mpone, *mptwo;

/* sum[0:alen] = a[0:alen-1] + b[0:blen-1] */
/* prereq: alen >= blen, sum has room for alen+1 digits */
void	mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *sum);

/* diff[0:alen-1] = a[0:alen-1] - b[0:blen-1] */
/* prereq: alen >= blen, diff has room for alen digits */
void	mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *diff);

/* p[0:n] += m * b[0:n-1] */
/* prereq: p has room for n+1 digits */
void	mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p);

/* p[0:n] -= m * b[0:n-1] */
/* prereq: p has room for n+1 digits */
int	mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p);

/* p[0:alen*blen-1] = a[0:alen-1] * b[0:blen-1] */
/* prereq: alen >= blen, p has room for m*n digits */
void	mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p);

/* sign of a - b or zero if the same */
int	mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen);

/* divide the 2 digit dividend by the one digit divisor and stick in quotient */
/* we assume that the result is one digit - overflow is all 1's */
void	mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);

/* playing with magnitudes */
int	mpmagcmp(mpint *b1, mpint *b2);
void	mpmagadd(mpint *b1, mpint *b2, mpint *sum);	/* sum = b1+b2 */
void	mpmagsub(mpint *b1, mpint *b2, mpint *sum);	/* sum = b1+b2 */

/* chinese remainder theorem */
typedef struct CRTpre	CRTpre;		/* precomputed values for converting */
					/*  twixt residues and mpint */
typedef struct CRTres	CRTres;		/* residue form of an mpint */

struct CRTres
{
	int	n;		/* number of residues */
	mpint	*r[1];		/* residues */
};

CRTpre*	crtpre(int, mpint**);			/* precompute conversion values */
CRTres*	crtin(CRTpre*, mpint*);			/* convert mpint to residues */
void	crtout(CRTpre*, CRTres*, mpint*);	/* convert residues to mpint */
void	crtprefree(CRTpre*);
void	crtresfree(CRTres*);


/* #pragma	varargck	type	"B"	mpint* */
#ifdef __cplusplus
}
#endif
#endif