1 #include "os.h"
2 #include <mp.h>
3 #include "dat.h"
4 
5 static mpdigit _mptwodata[1] = { 2 };
6 static mpint _mptwo =
7 {
8 	1,
9 	1,
10 	1,
11 	_mptwodata,
12 	MPstatic
13 };
14 mpint *mptwo = &_mptwo;
15 
16 static mpdigit _mponedata[1] = { 1 };
17 static mpint _mpone =
18 {
19 	1,
20 	1,
21 	1,
22 	_mponedata,
23 	MPstatic
24 };
25 mpint *mpone = &_mpone;
26 
27 static mpdigit _mpzerodata[1] = { 0 };
28 static mpint _mpzero =
29 {
30 	1,
31 	1,
32 	0,
33 	_mpzerodata,
34 	MPstatic
35 };
36 mpint *mpzero = &_mpzero;
37 
38 static int mpmindigits = 33;
39 
40 /* set minimum digit allocation */
41 void
42 mpsetminbits(int n)
43 {
44 	if(n < 0)
45 		sysfatal("mpsetminbits: n < 0");
46 	if(n == 0)
47 		n = 1;
48 	mpmindigits = DIGITS(n);
49 }
50 
51 /* allocate an n bit 0'd number  */
52 mpint*
53 mpnew(int n)
54 {
55 	mpint *b;
56 
57 	if(n < 0)
58 		sysfatal("mpsetminbits: n < 0");
59 
60 	b = mallocz(sizeof(mpint), 1);
61 	if(b == nil)
62 		sysfatal("mpnew: %r");
63 	n = DIGITS(n);
64 	if(n < mpmindigits)
65 		n = mpmindigits;
66 	b->p = (mpdigit*)mallocz(n*Dbytes, 1);
67 	if(b->p == nil)
68 		sysfatal("mpnew: %r");
69 	b->size = n;
70 	b->sign = 1;
71 
72 	return b;
73 }
74 
75 /* guarantee at least n significant bits */
76 void
77 mpbits(mpint *b, int m)
78 {
79 	int n;
80 
81 	n = DIGITS(m);
82 	if(b->size >= n){
83 		if(b->top >= n)
84 			return;
85 		memset(&b->p[b->top], 0, Dbytes*(n - b->top));
86 		b->top = n;
87 		return;
88 	}
89 	b->p = (mpdigit*)realloc(b->p, n*Dbytes);
90 	if(b->p == nil)
91 		sysfatal("mpbits: %r");
92 	memset(&b->p[b->top], 0, Dbytes*(n - b->top));
93 	b->size = n;
94 	b->top = n;
95 }
96 
97 void
98 mpfree(mpint *b)
99 {
100 	if(b == nil)
101 		return;
102 	if(b->flags & MPstatic)
103 		sysfatal("freeing mp constant");
104 	memset(b->p, 0, b->size*Dbytes);	/* information hiding */
105 	free(b->p);
106 	free(b);
107 }
108 
109 void
110 mpnorm(mpint *b)
111 {
112 	int i;
113 
114 	for(i = b->top-1; i >= 0; i--)
115 		if(b->p[i] != 0)
116 			break;
117 	b->top = i+1;
118 	if(b->top == 0)
119 		b->sign = 1;
120 }
121 
122 mpint*
123 mpcopy(mpint *old)
124 {
125 	mpint *new;
126 
127 	new = mpnew(Dbits*old->size);
128 	new->top = old->top;
129 	new->sign = old->sign;
130 	memmove(new->p, old->p, Dbytes*old->top);
131 	return new;
132 }
133 
134 void
135 mpassign(mpint *old, mpint *new)
136 {
137 	mpbits(new, Dbits*old->top);
138 	new->sign = old->sign;
139 	new->top = old->top;
140 	memmove(new->p, old->p, Dbytes*old->top);
141 }
142 
143 /* number of significant bits in mantissa */
144 int
145 mpsignif(mpint *n)
146 {
147 	int i, j;
148 	mpdigit d;
149 
150 	if(n->top == 0)
151 		return 0;
152 	for(i = n->top-1; i >= 0; i--){
153 		d = n->p[i];
154 		for(j = Dbits-1; j >= 0; j--){
155 			if(d & (((mpdigit)1)<<j))
156 				return i*Dbits + j + 1;
157 		}
158 	}
159 	return 0;
160 }
161 
162 /* k, where n = 2**k * q for odd q */
163 int
164 mplowbits0(mpint *n)
165 {
166 	int k, bit, digit;
167 	mpdigit d;
168 
169 	if(n->top==0)
170 		return 0;
171 	k = 0;
172 	bit = 0;
173 	digit = 0;
174 	d = n->p[0];
175 	for(;;){
176 		if(d & (1<<bit))
177 			break;
178 		k++;
179 		bit++;
180 		if(bit==Dbits){
181 			if(++digit >= n->top)
182 				return 0;
183 			d = n->p[digit];
184 			bit = 0;
185 		}
186 	}
187 	return k;
188 }