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"
5 b3f61791 2004-03-21 devnull static mpdigit _mptwodata[1] = { 2 };
6 b3f61791 2004-03-21 devnull static mpint _mptwo =
11 b3f61791 2004-03-21 devnull _mptwodata,
14 b3f61791 2004-03-21 devnull mpint *mptwo = &_mptwo;
16 b3f61791 2004-03-21 devnull static mpdigit _mponedata[1] = { 1 };
17 b3f61791 2004-03-21 devnull static mpint _mpone =
22 b3f61791 2004-03-21 devnull _mponedata,
25 b3f61791 2004-03-21 devnull mpint *mpone = &_mpone;
27 b3f61791 2004-03-21 devnull static mpdigit _mpzerodata[1] = { 0 };
28 b3f61791 2004-03-21 devnull static mpint _mpzero =
33 b3f61791 2004-03-21 devnull _mpzerodata,
36 b3f61791 2004-03-21 devnull mpint *mpzero = &_mpzero;
38 b3f61791 2004-03-21 devnull static int mpmindigits = 33;
40 b3f61791 2004-03-21 devnull // set minimum digit allocation
42 b3f61791 2004-03-21 devnull mpsetminbits(int n)
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)
48 b3f61791 2004-03-21 devnull mpmindigits = DIGITS(n);
51 b3f61791 2004-03-21 devnull // allocate an n bit 0'd number
53 b3f61791 2004-03-21 devnull mpnew(int n)
55 b3f61791 2004-03-21 devnull mpint *b;
57 b3f61791 2004-03-21 devnull if(n < 0)
58 b3f61791 2004-03-21 devnull sysfatal("mpsetminbits: n < 0");
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;
72 b3f61791 2004-03-21 devnull return b;
75 b3f61791 2004-03-21 devnull // guarantee at least n significant bits
77 b3f61791 2004-03-21 devnull mpbits(mpint *b, int m)
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)
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;
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;
98 b3f61791 2004-03-21 devnull mpfree(mpint *b)
100 b3f61791 2004-03-21 devnull if(b == nil)
102 b3f61791 2004-03-21 devnull if(b->flags & MPstatic)
103 b3f61791 2004-03-21 devnull sysfatal("freeing mp constant");
104 b3f61791 2004-03-21 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);
110 b3f61791 2004-03-21 devnull mpnorm(mpint *b)
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)
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;
123 b3f61791 2004-03-21 devnull mpcopy(mpint *old)
125 b3f61791 2004-03-21 devnull mpint *new;
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;
135 b3f61791 2004-03-21 devnull mpassign(mpint *old, mpint *new)
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);
143 b3f61791 2004-03-21 devnull // number of significant bits in mantissa
145 b3f61791 2004-03-21 devnull mpsignif(mpint *n)
147 b3f61791 2004-03-21 devnull int i, j;
148 b3f61791 2004-03-21 devnull mpdigit d;
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;
159 b3f61791 2004-03-21 devnull return 0;
162 b3f61791 2004-03-21 devnull // k, where n = 2**k * q for odd q
164 b3f61791 2004-03-21 devnull mplowbits0(mpint *n)
166 b3f61791 2004-03-21 devnull int k, bit, digit;
167 b3f61791 2004-03-21 devnull mpdigit d;
169 b3f61791 2004-03-21 devnull if(n->top==0)
170 b3f61791 2004-03-21 devnull return 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))
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;
187 b3f61791 2004-03-21 devnull return k;