Subversion Repositories planix.SVN

Rev

Rev 33 | Details | Compare with Previous | Last modification | View Log | RSS feed

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