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