Subversion Repositories planix.SVN

Rev

Rev 2 | 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 
{
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 
		n = 1;
46 
	mpmindigits = DIGITS(n);
47 
}
48 
 
49 
// allocate an n bit 0'd number
50 
mpint*
51 
mpnew(int n)
52 
{
53 
	mpint *b;
54 
 
55 
	b = mallocz(sizeof(mpint), 1);
56 
	if(b == nil)
57 
		sysfatal("mpnew: %r");
58 
	n = DIGITS(n);
59 
	if(n < mpmindigits)
60 
		n = mpmindigits;
61 
	n = n;
62 
	b->p = (mpdigit*)mallocz(n*Dbytes, 1);
63 
	if(b->p == nil)
64 
		sysfatal("mpnew: %r");
65 
	b->size = n;
66 
	b->sign = 1;
67 
 
68 
	return b;
69 
}
70 
 
71 
// guarantee at least n significant bits
72 
void
73 
mpbits(mpint *b, int m)
74 
{
75 
	int n;
76 
 
77 
	n = DIGITS(m);
78 
	if(b->size >= n){
79 
		if(b->top >= n)
80 
			return;
81 
		memset(&b->p[b->top], 0, Dbytes*(n - b->top));
82 
		b->top = n;
83 
		return;
84 
	}
85 
	b->p = (mpdigit*)realloc(b->p, n*Dbytes);
86 
	if(b->p == nil)
87 
		sysfatal("mpbits: %r");
88 
	memset(&b->p[b->top], 0, Dbytes*(n - b->top));
89 
	b->size = n;
90 
	b->top = n;
91 
}
92 
 
93 
void
94 
mpfree(mpint *b)
95 
{
96 
	if(b == nil)
97 
		return;
98 
	if(b->flags & MPstatic)
99 
		sysfatal("freeing mp constant");
100 
	memset(b->p, 0, b->top*Dbytes);	// information hiding
101 
	free(b->p);
102 
	free(b);
103 
}
104 
 
105 
void
106 
mpnorm(mpint *b)
107 
{
108 
	int i;
109 
 
110 
	for(i = b->top-1; i >= 0; i--)
111 
		if(b->p[i] != 0)
112 
			break;
113 
	b->top = i+1;
114 
	if(b->top == 0)
115 
		b->sign = 1;
116 
}
117 
 
118 
mpint*
119 
mpcopy(mpint *old)
120 
{
121 
	mpint *new;
122 
 
123 
	new = mpnew(Dbits*old->size);
124 
	new->top = old->top;
125 
	new->sign = old->sign;
126 
	memmove(new->p, old->p, Dbytes*old->top);
127 
	return new;
128 
}
129 
 
130 
void
131 
mpassign(mpint *old, mpint *new)
132 
{
133 
	mpbits(new, Dbits*old->top);
134 
	new->sign = old->sign;
135 
	new->top = old->top;
136 
	memmove(new->p, old->p, Dbytes*old->top);
137 
}
138 
 
139 
// number of significant bits in mantissa
140 
int
141 
mpsignif(mpint *n)
142 
{
143 
	int i, j;
144 
	mpdigit d;
145 
 
146 
	if(n->top == 0)
147 
		return 0;
148 
	for(i = n->top-1; i >= 0; i--){
149 
		d = n->p[i];
150 
		for(j = Dbits-1; j >= 0; j--){
151 
			if(d & (((mpdigit)1)<<j))
152 
				return i*Dbits + j + 1;
153 
		}
154 
	}
155 
	return 0;
156 
}
157 
 
158 
// k, where n = 2**k * q for odd q
159 
int
160 
mplowbits0(mpint *n)
161 
{
162 
	int k, bit, digit;
163 
	mpdigit d;
164 
 
165 
	if(n->top==0)
166 
		return 0;
167 
	k = 0;
168 
	bit = 0;
169 
	digit = 0;
170 
	d = n->p[0];
171 
	for(;;){
172 
		if(d & (1<<bit))
173 
			break;
174 
		k++;
175 
		bit++;
176 
		if(bit==Dbits){
177 
			if(++digit >= n->top)
178 
				return 0;
179 
			d = n->p[digit];
180 
			bit = 0;
181 
		}
182 
	}
183 
	return k;
184 
}
185