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