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
mpsetminbits(int n)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*
mpnew(int n)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
mpbits(mpint * b,int m)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
mpfree(mpint * b)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
mpnorm(mpint * b)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*
mpcopy(mpint * old)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
mpassign(mpint * old,mpint * new)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
mpsignif(mpint * n)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
mplowbits0(mpint * n)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 }
189
190