File: | polly/lib/External/isl/imath/imath.c |
Warning: | line 2131, column 9 Use of zero-allocated memory |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* | |||
2 | Name: imath.c | |||
3 | Purpose: Arbitrary precision integer arithmetic routines. | |||
4 | Author: M. J. Fromberger <http://spinning-yarns.org/michael/> | |||
5 | ||||
6 | Copyright (C) 2002-2007 Michael J. Fromberger, All Rights Reserved. | |||
7 | ||||
8 | Permission is hereby granted, free of charge, to any person obtaining a copy | |||
9 | of this software and associated documentation files (the "Software"), to deal | |||
10 | in the Software without restriction, including without limitation the rights | |||
11 | to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |||
12 | copies of the Software, and to permit persons to whom the Software is | |||
13 | furnished to do so, subject to the following conditions: | |||
14 | ||||
15 | The above copyright notice and this permission notice shall be included in | |||
16 | all copies or substantial portions of the Software. | |||
17 | ||||
18 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |||
19 | IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |||
20 | FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |||
21 | AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |||
22 | LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |||
23 | OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE | |||
24 | SOFTWARE. | |||
25 | */ | |||
26 | ||||
27 | #include "imath.h" | |||
28 | ||||
29 | #if DEBUG | |||
30 | #include <stdio.h> | |||
31 | #endif | |||
32 | ||||
33 | #include <stdlib.h> | |||
34 | #include <string.h> | |||
35 | #include <ctype.h> | |||
36 | ||||
37 | #include <assert.h> | |||
38 | ||||
39 | #if DEBUG | |||
40 | #define STATICstatic /* public */ | |||
41 | #else | |||
42 | #define STATICstatic static | |||
43 | #endif | |||
44 | ||||
45 | const mp_result MP_OK = 0; /* no error, all is well */ | |||
46 | const mp_result MP_FALSE = 0; /* boolean false */ | |||
47 | const mp_result MP_TRUE = -1; /* boolean true */ | |||
48 | const mp_result MP_MEMORY = -2; /* out of memory */ | |||
49 | const mp_result MP_RANGE = -3; /* argument out of range */ | |||
50 | const mp_result MP_UNDEF = -4; /* result undefined */ | |||
51 | const mp_result MP_TRUNC = -5; /* output truncated */ | |||
52 | const mp_result MP_BADARG = -6; /* invalid null argument */ | |||
53 | const mp_result MP_MINERR = -6; | |||
54 | ||||
55 | const mp_sign MP_NEG = 1; /* value is strictly negative */ | |||
56 | const mp_sign MP_ZPOS = 0; /* value is non-negative */ | |||
57 | ||||
58 | STATICstatic const char *s_unknown_err = "unknown result code"; | |||
59 | STATICstatic const char *s_error_msg[] = { | |||
60 | "error code 0", | |||
61 | "boolean true", | |||
62 | "out of memory", | |||
63 | "argument out of range", | |||
64 | "result undefined", | |||
65 | "output truncated", | |||
66 | "invalid argument", | |||
67 | NULL((void*)0) | |||
68 | }; | |||
69 | ||||
70 | /* Argument checking macros | |||
71 | Use CHECK() where a return value is required; NRCHECK() elsewhere */ | |||
72 | #define CHECK(TEST)((TEST) ? (void) (0) : __assert_fail ("TEST", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 72, __PRETTY_FUNCTION__)) assert(TEST)((TEST) ? (void) (0) : __assert_fail ("TEST", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 72, __PRETTY_FUNCTION__)) | |||
73 | #define NRCHECK(TEST)((TEST) ? (void) (0) : __assert_fail ("TEST", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 73, __PRETTY_FUNCTION__)) assert(TEST)((TEST) ? (void) (0) : __assert_fail ("TEST", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 73, __PRETTY_FUNCTION__)) | |||
74 | ||||
75 | /* The ith entry of this table gives the value of log_i(2). | |||
76 | ||||
77 | An integer value n requires ceil(log_i(n)) digits to be represented | |||
78 | in base i. Since it is easy to compute lg(n), by counting bits, we | |||
79 | can compute log_i(n) = lg(n) * log_i(2). | |||
80 | ||||
81 | The use of this table eliminates a dependency upon linkage against | |||
82 | the standard math libraries. | |||
83 | ||||
84 | If MP_MAX_RADIX is increased, this table should be expanded too. | |||
85 | */ | |||
86 | STATICstatic const double s_log2[] = { | |||
87 | 0.000000000, 0.000000000, 1.000000000, 0.630929754, /* (D)(D) 2 3 */ | |||
88 | 0.500000000, 0.430676558, 0.386852807, 0.356207187, /* 4 5 6 7 */ | |||
89 | 0.333333333, 0.315464877, 0.301029996, 0.289064826, /* 8 9 10 11 */ | |||
90 | 0.278942946, 0.270238154, 0.262649535, 0.255958025, /* 12 13 14 15 */ | |||
91 | 0.250000000, 0.244650542, 0.239812467, 0.235408913, /* 16 17 18 19 */ | |||
92 | 0.231378213, 0.227670249, 0.224243824, 0.221064729, /* 20 21 22 23 */ | |||
93 | 0.218104292, 0.215338279, 0.212746054, 0.210309918, /* 24 25 26 27 */ | |||
94 | 0.208014598, 0.205846832, 0.203795047, 0.201849087, /* 28 29 30 31 */ | |||
95 | 0.200000000, 0.198239863, 0.196561632, 0.194959022, /* 32 33 34 35 */ | |||
96 | 0.193426404, /* 36 */ | |||
97 | }; | |||
98 | ||||
99 | ||||
100 | ||||
101 | /* Return the number of digits needed to represent a static value */ | |||
102 | #define MP_VALUE_DIGITS(V)((sizeof(V)+(sizeof(mp_digit)-1))/sizeof(mp_digit)) \ | |||
103 | ((sizeof(V)+(sizeof(mp_digit)-1))/sizeof(mp_digit)) | |||
104 | ||||
105 | /* Round precision P to nearest word boundary */ | |||
106 | #define ROUND_PREC(P)((mp_size)(2*(((P)+1)/2))) ((mp_size)(2*(((P)+1)/2))) | |||
107 | ||||
108 | /* Set array P of S digits to zero */ | |||
109 | #define ZERO(P, S)do{ mp_size i__ = (S) * sizeof(mp_digit); mp_digit *p__ = (P) ; memset(p__, 0, i__); } while(0) \ | |||
110 | do{ \ | |||
111 | mp_size i__ = (S) * sizeof(mp_digit); \ | |||
112 | mp_digit *p__ = (P); \ | |||
113 | memset(p__, 0, i__); \ | |||
114 | } while(0) | |||
115 | ||||
116 | /* Copy S digits from array P to array Q */ | |||
117 | #define COPY(P, Q, S)do{ mp_size i__ = (S) * sizeof(mp_digit); mp_digit *p__ = (P) , *q__ = (Q); memcpy(q__, p__, i__); } while(0) \ | |||
118 | do{ \ | |||
119 | mp_size i__ = (S) * sizeof(mp_digit); \ | |||
120 | mp_digit *p__ = (P), *q__ = (Q); \ | |||
121 | memcpy(q__, p__, i__); \ | |||
122 | } while(0) | |||
123 | ||||
124 | /* Reverse N elements of type T in array A */ | |||
125 | #define REV(T, A, N)do{ T *u_ = (A), *v_ = u_ + (N) - 1; while (u_ < v_) { T xch = *u_; *u_++ = *v_; *v_-- = xch; } } while(0) \ | |||
126 | do{ \ | |||
127 | T *u_ = (A), *v_ = u_ + (N) - 1; \ | |||
128 | while (u_ < v_) { \ | |||
129 | T xch = *u_; \ | |||
130 | *u_++ = *v_; \ | |||
131 | *v_-- = xch; \ | |||
132 | } \ | |||
133 | } while(0) | |||
134 | ||||
135 | #define CLAMP(Z)do{ mp_int z_ = (Z); mp_size uz_ = ((z_)->used); mp_digit * dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0) \ | |||
136 | do{ \ | |||
137 | mp_int z_ = (Z); \ | |||
138 | mp_size uz_ = MP_USED(z_)((z_)->used); \ | |||
139 | mp_digit *dz_ = MP_DIGITS(z_)((z_)->digits) + uz_ -1; \ | |||
140 | while (uz_ > 1 && (*dz_-- == 0)) \ | |||
141 | --uz_; \ | |||
142 | MP_USED(z_)((z_)->used) = uz_; \ | |||
143 | } while(0) | |||
144 | ||||
145 | /* Select min/max. Do not provide expressions for which multiple | |||
146 | evaluation would be problematic, e.g. x++ */ | |||
147 | #define MIN(A, B)((B)<(A)?(B):(A)) ((B)<(A)?(B):(A)) | |||
148 | #define MAX(A, B)((B)>(A)?(B):(A)) ((B)>(A)?(B):(A)) | |||
149 | ||||
150 | /* Exchange lvalues A and B of type T, e.g. | |||
151 | SWAP(int, x, y) where x and y are variables of type int. */ | |||
152 | #define SWAP(T, A, B)do{ T t_ = (A); A = (B); B = t_; } while(0) \ | |||
153 | do{ \ | |||
154 | T t_ = (A); \ | |||
155 | A = (B); \ | |||
156 | B = t_; \ | |||
157 | } while(0) | |||
158 | ||||
159 | /* Used to set up and access simple temp stacks within functions. */ | |||
160 | #define DECLARE_TEMP(N)mpz_t temp[(N)]; int last__ = 0 \ | |||
161 | mpz_t temp[(N)]; \ | |||
162 | int last__ = 0 | |||
163 | #define CLEANUP_TEMP()CLEANUP: while (--last__ >= 0) mp_int_clear((temp + (last__ ))) \ | |||
164 | CLEANUP: \ | |||
165 | while (--last__ >= 0) \ | |||
166 | mp_int_clear(TEMP(last__)(temp + (last__))) | |||
167 | #define TEMP(K)(temp + (K)) (temp + (K)) | |||
168 | #define LAST_TEMP()(temp + (last__)) TEMP(last__)(temp + (last__)) | |||
169 | #define SETUP(E)do{ if ((res = (E)) != MP_OK) goto CLEANUP; ++(last__); } while (0) \ | |||
170 | do{ \ | |||
171 | if ((res = (E)) != MP_OK) \ | |||
172 | goto CLEANUP; \ | |||
173 | ++(last__); \ | |||
174 | } while(0) | |||
175 | ||||
176 | /* Compare value to zero. */ | |||
177 | #define CMPZ(Z)(((Z)->used==1&&(Z)->digits[0]==0)?0:((Z)->sign ==MP_NEG)?-1:1) \ | |||
178 | (((Z)->used==1&&(Z)->digits[0]==0)?0:((Z)->sign==MP_NEG)?-1:1) | |||
179 | ||||
180 | /* Multiply X by Y into Z, ignoring signs. Requires that Z have | |||
181 | enough storage preallocated to hold the result. */ | |||
182 | #define UMUL(X, Y, Z)do{ mp_size ua_ = ((X)->used), ub_ = ((Y)->used); mp_size o_ = ua_ + ub_; do{ mp_size i__ = (o_) * sizeof(mp_digit); mp_digit *p__ = (((Z)->digits)); memset(p__, 0, i__); } while(0); ( void) s_kmul(((X)->digits), ((Y)->digits), ((Z)->digits ), ua_, ub_); ((Z)->used) = o_; do{ mp_int z_ = (Z); mp_size uz_ = ((z_)->used); mp_digit *dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_) ->used) = uz_; } while(0); } while(0) \ | |||
183 | do{ \ | |||
184 | mp_size ua_ = MP_USED(X)((X)->used), ub_ = MP_USED(Y)((Y)->used); \ | |||
185 | mp_size o_ = ua_ + ub_; \ | |||
186 | ZERO(MP_DIGITS(Z), o_)do{ mp_size i__ = (o_) * sizeof(mp_digit); mp_digit *p__ = (( (Z)->digits)); memset(p__, 0, i__); } while(0); \ | |||
187 | (void) s_kmul(MP_DIGITS(X)((X)->digits), MP_DIGITS(Y)((Y)->digits), MP_DIGITS(Z)((Z)->digits), ua_, ub_); \ | |||
188 | MP_USED(Z)((Z)->used) = o_; \ | |||
189 | CLAMP(Z)do{ mp_int z_ = (Z); mp_size uz_ = ((z_)->used); mp_digit * dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0); \ | |||
190 | } while(0) | |||
191 | ||||
192 | /* Square X into Z. Requires that Z have enough storage to hold the | |||
193 | result. */ | |||
194 | #define USQR(X, Z)do{ mp_size ua_ = ((X)->used), o_ = ua_ + ua_; do{ mp_size i__ = (o_) * sizeof(mp_digit); mp_digit *p__ = (((Z)->digits )); memset(p__, 0, i__); } while(0); (void) s_ksqr(((X)->digits ), ((Z)->digits), ua_); ((Z)->used) = o_; do{ mp_int z_ = (Z); mp_size uz_ = ((z_)->used); mp_digit *dz_ = ((z_)-> digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0); } while(0) \ | |||
195 | do{ \ | |||
196 | mp_size ua_ = MP_USED(X)((X)->used), o_ = ua_ + ua_; \ | |||
197 | ZERO(MP_DIGITS(Z), o_)do{ mp_size i__ = (o_) * sizeof(mp_digit); mp_digit *p__ = (( (Z)->digits)); memset(p__, 0, i__); } while(0); \ | |||
198 | (void) s_ksqr(MP_DIGITS(X)((X)->digits), MP_DIGITS(Z)((Z)->digits), ua_); \ | |||
199 | MP_USED(Z)((Z)->used) = o_; \ | |||
200 | CLAMP(Z)do{ mp_int z_ = (Z); mp_size uz_ = ((z_)->used); mp_digit * dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0); \ | |||
201 | } while(0) | |||
202 | ||||
203 | #define UPPER_HALF(W)((mp_word)((W) >> (sizeof(mp_digit) * 8))) ((mp_word)((W) >> MP_DIGIT_BIT(sizeof(mp_digit) * 8))) | |||
204 | #define LOWER_HALF(W)((mp_digit)(W)) ((mp_digit)(W)) | |||
205 | #define HIGH_BIT_SET(W)((W) >> ((sizeof(mp_word) * 8) - 1)) ((W) >> (MP_WORD_BIT(sizeof(mp_word) * 8) - 1)) | |||
206 | #define ADD_WILL_OVERFLOW(W, V)((((18446744073709551615UL)) - (V)) < (W)) ((MP_WORD_MAX((18446744073709551615UL)) - (V)) < (W)) | |||
207 | ||||
208 | ||||
209 | ||||
210 | /* Default number of digits allocated to a new mp_int */ | |||
211 | #if IMATH_TEST | |||
212 | mp_size default_precision = MP_DEFAULT_PREC8; | |||
213 | #else | |||
214 | STATICstatic const mp_size default_precision = MP_DEFAULT_PREC8; | |||
215 | #endif | |||
216 | ||||
217 | /* Minimum number of digits to invoke recursive multiply */ | |||
218 | #if IMATH_TEST | |||
219 | mp_size multiply_threshold = MP_MULT_THRESH22; | |||
220 | #else | |||
221 | STATICstatic const mp_size multiply_threshold = MP_MULT_THRESH22; | |||
222 | #endif | |||
223 | ||||
224 | /* Allocate a buffer of (at least) num digits, or return | |||
225 | NULL if that couldn't be done. */ | |||
226 | STATICstatic mp_digit *s_alloc(mp_size num); | |||
227 | ||||
228 | /* Release a buffer of digits allocated by s_alloc(). */ | |||
229 | STATICstatic void s_free(void *ptr); | |||
230 | ||||
231 | /* Insure that z has at least min digits allocated, resizing if | |||
232 | necessary. Returns true if successful, false if out of memory. */ | |||
233 | STATICstatic int s_pad(mp_int z, mp_size min); | |||
234 | ||||
235 | /* Fill in a "fake" mp_int on the stack with a given value */ | |||
236 | STATICstatic void s_fake(mp_int z, mp_small value, mp_digit vbuf[]); | |||
237 | STATICstatic void s_ufake(mp_int z, mp_usmall value, mp_digit vbuf[]); | |||
238 | ||||
239 | /* Compare two runs of digits of given length, returns <0, 0, >0 */ | |||
240 | STATICstatic int s_cdig(mp_digit *da, mp_digit *db, mp_size len); | |||
241 | ||||
242 | /* Pack the unsigned digits of v into array t */ | |||
243 | STATICstatic int s_uvpack(mp_usmall v, mp_digit t[]); | |||
244 | ||||
245 | /* Compare magnitudes of a and b, returns <0, 0, >0 */ | |||
246 | STATICstatic int s_ucmp(mp_int a, mp_int b); | |||
247 | ||||
248 | /* Compare magnitudes of a and v, returns <0, 0, >0 */ | |||
249 | STATICstatic int s_vcmp(mp_int a, mp_small v); | |||
250 | STATICstatic int s_uvcmp(mp_int a, mp_usmall uv); | |||
251 | ||||
252 | /* Unsigned magnitude addition; assumes dc is big enough. | |||
253 | Carry out is returned (no memory allocated). */ | |||
254 | STATICstatic mp_digit s_uadd(mp_digit *da, mp_digit *db, mp_digit *dc, | |||
255 | mp_size size_a, mp_size size_b); | |||
256 | ||||
257 | /* Unsigned magnitude subtraction. Assumes dc is big enough. */ | |||
258 | STATICstatic void s_usub(mp_digit *da, mp_digit *db, mp_digit *dc, | |||
259 | mp_size size_a, mp_size size_b); | |||
260 | ||||
261 | /* Unsigned recursive multiplication. Assumes dc is big enough. */ | |||
262 | STATICstatic int s_kmul(mp_digit *da, mp_digit *db, mp_digit *dc, | |||
263 | mp_size size_a, mp_size size_b); | |||
264 | ||||
265 | /* Unsigned magnitude multiplication. Assumes dc is big enough. */ | |||
266 | STATICstatic void s_umul(mp_digit *da, mp_digit *db, mp_digit *dc, | |||
267 | mp_size size_a, mp_size size_b); | |||
268 | ||||
269 | /* Unsigned recursive squaring. Assumes dc is big enough. */ | |||
270 | STATICstatic int s_ksqr(mp_digit *da, mp_digit *dc, mp_size size_a); | |||
271 | ||||
272 | /* Unsigned magnitude squaring. Assumes dc is big enough. */ | |||
273 | STATICstatic void s_usqr(mp_digit *da, mp_digit *dc, mp_size size_a); | |||
274 | ||||
275 | /* Single digit addition. Assumes a is big enough. */ | |||
276 | STATICstatic void s_dadd(mp_int a, mp_digit b); | |||
277 | ||||
278 | /* Single digit multiplication. Assumes a is big enough. */ | |||
279 | STATICstatic void s_dmul(mp_int a, mp_digit b); | |||
280 | ||||
281 | /* Single digit multiplication on buffers; assumes dc is big enough. */ | |||
282 | STATICstatic void s_dbmul(mp_digit *da, mp_digit b, mp_digit *dc, | |||
283 | mp_size size_a); | |||
284 | ||||
285 | /* Single digit division. Replaces a with the quotient, | |||
286 | returns the remainder. */ | |||
287 | STATICstatic mp_digit s_ddiv(mp_int a, mp_digit b); | |||
288 | ||||
289 | /* Quick division by a power of 2, replaces z (no allocation) */ | |||
290 | STATICstatic void s_qdiv(mp_int z, mp_size p2); | |||
291 | ||||
292 | /* Quick remainder by a power of 2, replaces z (no allocation) */ | |||
293 | STATICstatic void s_qmod(mp_int z, mp_size p2); | |||
294 | ||||
295 | /* Quick multiplication by a power of 2, replaces z. | |||
296 | Allocates if necessary; returns false in case this fails. */ | |||
297 | STATICstatic int s_qmul(mp_int z, mp_size p2); | |||
298 | ||||
299 | /* Quick subtraction from a power of 2, replaces z. | |||
300 | Allocates if necessary; returns false in case this fails. */ | |||
301 | STATICstatic int s_qsub(mp_int z, mp_size p2); | |||
302 | ||||
303 | /* Return maximum k such that 2^k divides z. */ | |||
304 | STATICstatic int s_dp2k(mp_int z); | |||
305 | ||||
306 | /* Return k >= 0 such that z = 2^k, or -1 if there is no such k. */ | |||
307 | STATICstatic int s_isp2(mp_int z); | |||
308 | ||||
309 | /* Set z to 2^k. May allocate; returns false in case this fails. */ | |||
310 | STATICstatic int s_2expt(mp_int z, mp_small k); | |||
311 | ||||
312 | /* Normalize a and b for division, returns normalization constant */ | |||
313 | STATICstatic int s_norm(mp_int a, mp_int b); | |||
314 | ||||
315 | /* Compute constant mu for Barrett reduction, given modulus m, result | |||
316 | replaces z, m is untouched. */ | |||
317 | STATICstatic mp_result s_brmu(mp_int z, mp_int m); | |||
318 | ||||
319 | /* Reduce a modulo m, using Barrett's algorithm. */ | |||
320 | STATICstatic int s_reduce(mp_int x, mp_int m, mp_int mu, mp_int q1, mp_int q2); | |||
321 | ||||
322 | /* Modular exponentiation, using Barrett reduction */ | |||
323 | STATICstatic mp_result s_embar(mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c); | |||
324 | ||||
325 | /* Unsigned magnitude division. Assumes |a| > |b|. Allocates temporaries; | |||
326 | overwrites a with quotient, b with remainder. */ | |||
327 | STATICstatic mp_result s_udiv_knuth(mp_int a, mp_int b); | |||
328 | ||||
329 | /* Compute the number of digits in radix r required to represent the given | |||
330 | value. Does not account for sign flags, terminators, etc. */ | |||
331 | STATICstatic int s_outlen(mp_int z, mp_size r); | |||
332 | ||||
333 | /* Guess how many digits of precision will be needed to represent a radix r | |||
334 | value of the specified number of digits. Returns a value guaranteed to be | |||
335 | no smaller than the actual number required. */ | |||
336 | STATICstatic mp_size s_inlen(int len, mp_size r); | |||
337 | ||||
338 | /* Convert a character to a digit value in radix r, or | |||
339 | -1 if out of range */ | |||
340 | STATICstatic int s_ch2val(char c, int r); | |||
341 | ||||
342 | /* Convert a digit value to a character */ | |||
343 | STATICstatic char s_val2ch(int v, int caps); | |||
344 | ||||
345 | /* Take 2's complement of a buffer in place */ | |||
346 | STATICstatic void s_2comp(unsigned char *buf, int len); | |||
347 | ||||
348 | /* Convert a value to binary, ignoring sign. On input, *limpos is the bound on | |||
349 | how many bytes should be written to buf; on output, *limpos is set to the | |||
350 | number of bytes actually written. */ | |||
351 | STATICstatic mp_result s_tobin(mp_int z, unsigned char *buf, int *limpos, int pad); | |||
352 | ||||
353 | #if DEBUG | |||
354 | /* Dump a representation of the mp_int to standard output */ | |||
355 | void s_print(char *tag, mp_int z); | |||
356 | void s_print_buf(char *tag, mp_digit *buf, mp_size num); | |||
357 | #endif | |||
358 | ||||
359 | mp_result mp_int_init(mp_int z) | |||
360 | { | |||
361 | if (z == NULL((void*)0)) | |||
362 | return MP_BADARG; | |||
363 | ||||
364 | z->single = 0; | |||
365 | z->digits = &(z->single); | |||
366 | z->alloc = 1; | |||
367 | z->used = 1; | |||
368 | z->sign = MP_ZPOS; | |||
369 | ||||
370 | return MP_OK; | |||
371 | } | |||
372 | ||||
373 | mp_int mp_int_alloc(void) | |||
374 | { | |||
375 | mp_int out = malloc(sizeof(mpz_t)); | |||
376 | ||||
377 | if (out != NULL((void*)0)) | |||
378 | mp_int_init(out); | |||
379 | ||||
380 | return out; | |||
381 | } | |||
382 | ||||
383 | mp_result mp_int_init_size(mp_int z, mp_size prec) | |||
384 | { | |||
385 | CHECK(z != NULL)((z != ((void*)0)) ? (void) (0) : __assert_fail ("z != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 385, __PRETTY_FUNCTION__)); | |||
386 | ||||
387 | if (prec == 0) | |||
388 | prec = default_precision; | |||
389 | else if (prec == 1) | |||
390 | return mp_int_init(z); | |||
391 | else | |||
392 | prec = (mp_size) ROUND_PREC(prec)((mp_size)(2*(((prec)+1)/2))); | |||
393 | ||||
394 | if ((MP_DIGITS(z)((z)->digits) = s_alloc(prec)) == NULL((void*)0)) | |||
395 | return MP_MEMORY; | |||
396 | ||||
397 | z->digits[0] = 0; | |||
398 | MP_USED(z)((z)->used) = 1; | |||
399 | MP_ALLOC(z)((z)->alloc) = prec; | |||
400 | MP_SIGN(z)((z)->sign) = MP_ZPOS; | |||
401 | ||||
402 | return MP_OK; | |||
403 | } | |||
404 | ||||
405 | mp_result mp_int_init_copy(mp_int z, mp_int old) | |||
406 | { | |||
407 | mp_result res; | |||
408 | mp_size uold; | |||
409 | ||||
410 | CHECK(z != NULL && old != NULL)((z != ((void*)0) && old != ((void*)0)) ? (void) (0) : __assert_fail ("z != ((void*)0) && old != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 410, __PRETTY_FUNCTION__)); | |||
411 | ||||
412 | uold = MP_USED(old)((old)->used); | |||
413 | if (uold == 1) { | |||
414 | mp_int_init(z); | |||
415 | } | |||
416 | else { | |||
417 | mp_size target = MAX(uold, default_precision)((default_precision)>(uold)?(default_precision):(uold)); | |||
418 | ||||
419 | if ((res = mp_int_init_size(z, target)) != MP_OK) | |||
420 | return res; | |||
421 | } | |||
422 | ||||
423 | MP_USED(z)((z)->used) = uold; | |||
424 | MP_SIGN(z)((z)->sign) = MP_SIGN(old)((old)->sign); | |||
425 | COPY(MP_DIGITS(old), MP_DIGITS(z), uold)do{ mp_size i__ = (uold) * sizeof(mp_digit); mp_digit *p__ = ( ((old)->digits)), *q__ = (((z)->digits)); memcpy(q__, p__ , i__); } while(0); | |||
426 | ||||
427 | return MP_OK; | |||
428 | } | |||
429 | ||||
430 | mp_result mp_int_init_value(mp_int z, mp_small value) | |||
431 | { | |||
432 | mpz_t vtmp; | |||
433 | mp_digit vbuf[MP_VALUE_DIGITS(value)((sizeof(value)+(sizeof(mp_digit)-1))/sizeof(mp_digit))]; | |||
434 | ||||
435 | s_fake(&vtmp, value, vbuf); | |||
436 | return mp_int_init_copy(z, &vtmp); | |||
437 | } | |||
438 | ||||
439 | mp_result mp_int_init_uvalue(mp_int z, mp_usmall uvalue) | |||
440 | { | |||
441 | mpz_t vtmp; | |||
442 | mp_digit vbuf[MP_VALUE_DIGITS(uvalue)((sizeof(uvalue)+(sizeof(mp_digit)-1))/sizeof(mp_digit))]; | |||
443 | ||||
444 | s_ufake(&vtmp, uvalue, vbuf); | |||
445 | return mp_int_init_copy(z, &vtmp); | |||
446 | } | |||
447 | ||||
448 | mp_result mp_int_set_value(mp_int z, mp_small value) | |||
449 | { | |||
450 | mpz_t vtmp; | |||
451 | mp_digit vbuf[MP_VALUE_DIGITS(value)((sizeof(value)+(sizeof(mp_digit)-1))/sizeof(mp_digit))]; | |||
452 | ||||
453 | s_fake(&vtmp, value, vbuf); | |||
454 | return mp_int_copy(&vtmp, z); | |||
455 | } | |||
456 | ||||
457 | mp_result mp_int_set_uvalue(mp_int z, mp_usmall uvalue) | |||
458 | { | |||
459 | mpz_t vtmp; | |||
460 | mp_digit vbuf[MP_VALUE_DIGITS(uvalue)((sizeof(uvalue)+(sizeof(mp_digit)-1))/sizeof(mp_digit))]; | |||
461 | ||||
462 | s_ufake(&vtmp, uvalue, vbuf); | |||
463 | return mp_int_copy(&vtmp, z); | |||
464 | } | |||
465 | ||||
466 | void mp_int_clear(mp_int z) | |||
467 | { | |||
468 | if (z == NULL((void*)0)) | |||
469 | return; | |||
470 | ||||
471 | if (MP_DIGITS(z)((z)->digits) != NULL((void*)0)) { | |||
472 | if (MP_DIGITS(z)((z)->digits) != &(z->single)) | |||
473 | s_free(MP_DIGITS(z)((z)->digits)); | |||
474 | ||||
475 | MP_DIGITS(z)((z)->digits) = NULL((void*)0); | |||
476 | } | |||
477 | } | |||
478 | ||||
479 | void mp_int_free(mp_int z) | |||
480 | { | |||
481 | NRCHECK(z != NULL)((z != ((void*)0)) ? (void) (0) : __assert_fail ("z != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 481, __PRETTY_FUNCTION__)); | |||
482 | ||||
483 | mp_int_clear(z); | |||
484 | free(z); /* note: NOT s_free() */ | |||
485 | } | |||
486 | ||||
487 | mp_result mp_int_copy(mp_int a, mp_int c) | |||
488 | { | |||
489 | CHECK(a != NULL && c != NULL)((a != ((void*)0) && c != ((void*)0)) ? (void) (0) : __assert_fail ("a != ((void*)0) && c != ((void*)0)", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 489, __PRETTY_FUNCTION__)); | |||
490 | ||||
491 | if (a != c) { | |||
492 | mp_size ua = MP_USED(a)((a)->used); | |||
493 | mp_digit *da, *dc; | |||
494 | ||||
495 | if (!s_pad(c, ua)) | |||
496 | return MP_MEMORY; | |||
497 | ||||
498 | da = MP_DIGITS(a)((a)->digits); dc = MP_DIGITS(c)((c)->digits); | |||
499 | COPY(da, dc, ua)do{ mp_size i__ = (ua) * sizeof(mp_digit); mp_digit *p__ = (da ), *q__ = (dc); memcpy(q__, p__, i__); } while(0); | |||
500 | ||||
501 | MP_USED(c)((c)->used) = ua; | |||
502 | MP_SIGN(c)((c)->sign) = MP_SIGN(a)((a)->sign); | |||
503 | } | |||
504 | ||||
505 | return MP_OK; | |||
506 | } | |||
507 | ||||
508 | void mp_int_swap(mp_int a, mp_int c) | |||
509 | { | |||
510 | if (a != c) { | |||
511 | mpz_t tmp = *a; | |||
512 | ||||
513 | *a = *c; | |||
514 | *c = tmp; | |||
515 | ||||
516 | if (MP_DIGITS(a)((a)->digits) == &(c->single)) | |||
517 | MP_DIGITS(a)((a)->digits) = &(a->single); | |||
518 | if (MP_DIGITS(c)((c)->digits) == &(a->single)) | |||
519 | MP_DIGITS(c)((c)->digits) = &(c->single); | |||
520 | } | |||
521 | } | |||
522 | ||||
523 | void mp_int_zero(mp_int z) | |||
524 | { | |||
525 | NRCHECK(z != NULL)((z != ((void*)0)) ? (void) (0) : __assert_fail ("z != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 525, __PRETTY_FUNCTION__)); | |||
526 | ||||
527 | z->digits[0] = 0; | |||
528 | MP_USED(z)((z)->used) = 1; | |||
529 | MP_SIGN(z)((z)->sign) = MP_ZPOS; | |||
530 | } | |||
531 | ||||
532 | mp_result mp_int_abs(mp_int a, mp_int c) | |||
533 | { | |||
534 | mp_result res; | |||
535 | ||||
536 | CHECK(a != NULL && c != NULL)((a != ((void*)0) && c != ((void*)0)) ? (void) (0) : __assert_fail ("a != ((void*)0) && c != ((void*)0)", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 536, __PRETTY_FUNCTION__)); | |||
537 | ||||
538 | if ((res = mp_int_copy(a, c)) != MP_OK) | |||
539 | return res; | |||
540 | ||||
541 | MP_SIGN(c)((c)->sign) = MP_ZPOS; | |||
542 | return MP_OK; | |||
543 | } | |||
544 | ||||
545 | mp_result mp_int_neg(mp_int a, mp_int c) | |||
546 | { | |||
547 | mp_result res; | |||
548 | ||||
549 | CHECK(a != NULL && c != NULL)((a != ((void*)0) && c != ((void*)0)) ? (void) (0) : __assert_fail ("a != ((void*)0) && c != ((void*)0)", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 549, __PRETTY_FUNCTION__)); | |||
550 | ||||
551 | if ((res = mp_int_copy(a, c)) != MP_OK) | |||
552 | return res; | |||
553 | ||||
554 | if (CMPZ(c)(((c)->used==1&&(c)->digits[0]==0)?0:((c)->sign ==MP_NEG)?-1:1) != 0) | |||
555 | MP_SIGN(c)((c)->sign) = 1 - MP_SIGN(a)((a)->sign); | |||
556 | ||||
557 | return MP_OK; | |||
558 | } | |||
559 | ||||
560 | mp_result mp_int_add(mp_int a, mp_int b, mp_int c) | |||
561 | { | |||
562 | mp_size ua, ub, uc, max; | |||
563 | ||||
564 | CHECK(a != NULL && b != NULL && c != NULL)((a != ((void*)0) && b != ((void*)0) && c != ( (void*)0)) ? (void) (0) : __assert_fail ("a != ((void*)0) && b != ((void*)0) && c != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 564, __PRETTY_FUNCTION__)); | |||
565 | ||||
566 | ua = MP_USED(a)((a)->used); ub = MP_USED(b)((b)->used); uc = MP_USED(c)((c)->used); | |||
567 | max = MAX(ua, ub)((ub)>(ua)?(ub):(ua)); | |||
568 | ||||
569 | if (MP_SIGN(a)((a)->sign) == MP_SIGN(b)((b)->sign)) { | |||
570 | /* Same sign -- add magnitudes, preserve sign of addends */ | |||
571 | mp_digit carry; | |||
572 | ||||
573 | if (!s_pad(c, max)) | |||
574 | return MP_MEMORY; | |||
575 | ||||
576 | carry = s_uadd(MP_DIGITS(a)((a)->digits), MP_DIGITS(b)((b)->digits), MP_DIGITS(c)((c)->digits), ua, ub); | |||
577 | uc = max; | |||
578 | ||||
579 | if (carry) { | |||
580 | if (!s_pad(c, max + 1)) | |||
581 | return MP_MEMORY; | |||
582 | ||||
583 | c->digits[max] = carry; | |||
584 | ++uc; | |||
585 | } | |||
586 | ||||
587 | MP_USED(c)((c)->used) = uc; | |||
588 | MP_SIGN(c)((c)->sign) = MP_SIGN(a)((a)->sign); | |||
589 | ||||
590 | } | |||
591 | else { | |||
592 | /* Different signs -- subtract magnitudes, preserve sign of greater */ | |||
593 | mp_int x, y; | |||
594 | int cmp = s_ucmp(a, b); /* magnitude comparision, sign ignored */ | |||
595 | ||||
596 | /* Set x to max(a, b), y to min(a, b) to simplify later code. | |||
597 | A special case yields zero for equal magnitudes. | |||
598 | */ | |||
599 | if (cmp == 0) { | |||
600 | mp_int_zero(c); | |||
601 | return MP_OK; | |||
602 | } | |||
603 | else if (cmp < 0) { | |||
604 | x = b; y = a; | |||
605 | } | |||
606 | else { | |||
607 | x = a; y = b; | |||
608 | } | |||
609 | ||||
610 | if (!s_pad(c, MP_USED(x)((x)->used))) | |||
611 | return MP_MEMORY; | |||
612 | ||||
613 | /* Subtract smaller from larger */ | |||
614 | s_usub(MP_DIGITS(x)((x)->digits), MP_DIGITS(y)((y)->digits), MP_DIGITS(c)((c)->digits), MP_USED(x)((x)->used), MP_USED(y)((y)->used)); | |||
615 | MP_USED(c)((c)->used) = MP_USED(x)((x)->used); | |||
616 | CLAMP(c)do{ mp_int z_ = (c); mp_size uz_ = ((z_)->used); mp_digit * dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0); | |||
617 | ||||
618 | /* Give result the sign of the larger */ | |||
619 | MP_SIGN(c)((c)->sign) = MP_SIGN(x)((x)->sign); | |||
620 | } | |||
621 | ||||
622 | return MP_OK; | |||
623 | } | |||
624 | ||||
625 | mp_result mp_int_add_value(mp_int a, mp_small value, mp_int c) | |||
626 | { | |||
627 | mpz_t vtmp; | |||
628 | mp_digit vbuf[MP_VALUE_DIGITS(value)((sizeof(value)+(sizeof(mp_digit)-1))/sizeof(mp_digit))]; | |||
629 | ||||
630 | s_fake(&vtmp, value, vbuf); | |||
631 | ||||
632 | return mp_int_add(a, &vtmp, c); | |||
633 | } | |||
634 | ||||
635 | mp_result mp_int_sub(mp_int a, mp_int b, mp_int c) | |||
636 | { | |||
637 | mp_size ua, ub, uc, max; | |||
638 | ||||
639 | CHECK(a != NULL && b != NULL && c != NULL)((a != ((void*)0) && b != ((void*)0) && c != ( (void*)0)) ? (void) (0) : __assert_fail ("a != ((void*)0) && b != ((void*)0) && c != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 639, __PRETTY_FUNCTION__)); | |||
640 | ||||
641 | ua = MP_USED(a)((a)->used); ub = MP_USED(b)((b)->used); uc = MP_USED(c)((c)->used); | |||
642 | max = MAX(ua, ub)((ub)>(ua)?(ub):(ua)); | |||
643 | ||||
644 | if (MP_SIGN(a)((a)->sign) != MP_SIGN(b)((b)->sign)) { | |||
645 | /* Different signs -- add magnitudes and keep sign of a */ | |||
646 | mp_digit carry; | |||
647 | ||||
648 | if (!s_pad(c, max)) | |||
649 | return MP_MEMORY; | |||
650 | ||||
651 | carry = s_uadd(MP_DIGITS(a)((a)->digits), MP_DIGITS(b)((b)->digits), MP_DIGITS(c)((c)->digits), ua, ub); | |||
652 | uc = max; | |||
653 | ||||
654 | if (carry) { | |||
655 | if (!s_pad(c, max + 1)) | |||
656 | return MP_MEMORY; | |||
657 | ||||
658 | c->digits[max] = carry; | |||
659 | ++uc; | |||
660 | } | |||
661 | ||||
662 | MP_USED(c)((c)->used) = uc; | |||
663 | MP_SIGN(c)((c)->sign) = MP_SIGN(a)((a)->sign); | |||
664 | ||||
665 | } | |||
666 | else { | |||
667 | /* Same signs -- subtract magnitudes */ | |||
668 | mp_int x, y; | |||
669 | mp_sign osign; | |||
670 | int cmp = s_ucmp(a, b); | |||
671 | ||||
672 | if (!s_pad(c, max)) | |||
673 | return MP_MEMORY; | |||
674 | ||||
675 | if (cmp >= 0) { | |||
676 | x = a; y = b; osign = MP_ZPOS; | |||
677 | } | |||
678 | else { | |||
679 | x = b; y = a; osign = MP_NEG; | |||
680 | } | |||
681 | ||||
682 | if (MP_SIGN(a)((a)->sign) == MP_NEG && cmp != 0) | |||
683 | osign = 1 - osign; | |||
684 | ||||
685 | s_usub(MP_DIGITS(x)((x)->digits), MP_DIGITS(y)((y)->digits), MP_DIGITS(c)((c)->digits), MP_USED(x)((x)->used), MP_USED(y)((y)->used)); | |||
686 | MP_USED(c)((c)->used) = MP_USED(x)((x)->used); | |||
687 | CLAMP(c)do{ mp_int z_ = (c); mp_size uz_ = ((z_)->used); mp_digit * dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0); | |||
688 | ||||
689 | MP_SIGN(c)((c)->sign) = osign; | |||
690 | } | |||
691 | ||||
692 | return MP_OK; | |||
693 | } | |||
694 | ||||
695 | mp_result mp_int_sub_value(mp_int a, mp_small value, mp_int c) | |||
696 | { | |||
697 | mpz_t vtmp; | |||
698 | mp_digit vbuf[MP_VALUE_DIGITS(value)((sizeof(value)+(sizeof(mp_digit)-1))/sizeof(mp_digit))]; | |||
699 | ||||
700 | s_fake(&vtmp, value, vbuf); | |||
701 | ||||
702 | return mp_int_sub(a, &vtmp, c); | |||
703 | } | |||
704 | ||||
705 | mp_result mp_int_mul(mp_int a, mp_int b, mp_int c) | |||
706 | { | |||
707 | mp_digit *out; | |||
708 | mp_size osize, ua, ub, p = 0; | |||
709 | mp_sign osign; | |||
710 | ||||
711 | CHECK(a != NULL && b != NULL && c != NULL)((a != ((void*)0) && b != ((void*)0) && c != ( (void*)0)) ? (void) (0) : __assert_fail ("a != ((void*)0) && b != ((void*)0) && c != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 711, __PRETTY_FUNCTION__)); | |||
712 | ||||
713 | /* If either input is zero, we can shortcut multiplication */ | |||
714 | if (mp_int_compare_zero(a) == 0 || mp_int_compare_zero(b) == 0) { | |||
715 | mp_int_zero(c); | |||
716 | return MP_OK; | |||
717 | } | |||
718 | ||||
719 | /* Output is positive if inputs have same sign, otherwise negative */ | |||
720 | osign = (MP_SIGN(a)((a)->sign) == MP_SIGN(b)((b)->sign)) ? MP_ZPOS : MP_NEG; | |||
721 | ||||
722 | /* If the output is not identical to any of the inputs, we'll write the | |||
723 | results directly; otherwise, allocate a temporary space. */ | |||
724 | ua = MP_USED(a)((a)->used); ub = MP_USED(b)((b)->used); | |||
725 | osize = MAX(ua, ub)((ub)>(ua)?(ub):(ua)); | |||
726 | osize = 4 * ((osize + 1) / 2); | |||
727 | ||||
728 | if (c
| |||
729 | p = ROUND_PREC(osize)((mp_size)(2*(((osize)+1)/2))); | |||
730 | p = MAX(p, default_precision)((default_precision)>(p)?(default_precision):(p)); | |||
731 | ||||
732 | if ((out = s_alloc(p)) == NULL((void*)0)) | |||
733 | return MP_MEMORY; | |||
734 | } | |||
735 | else { | |||
736 | if (!s_pad(c, osize)) | |||
737 | return MP_MEMORY; | |||
738 | ||||
739 | out = MP_DIGITS(c)((c)->digits); | |||
740 | } | |||
741 | ZERO(out, osize)do{ mp_size i__ = (osize) * sizeof(mp_digit); mp_digit *p__ = (out); memset(p__, 0, i__); } while(0); | |||
742 | ||||
743 | if (!s_kmul(MP_DIGITS(a)((a)->digits), MP_DIGITS(b)((b)->digits), out, ua, ub)) | |||
744 | return MP_MEMORY; | |||
745 | ||||
746 | /* If we allocated a new buffer, get rid of whatever memory c was already | |||
747 | using, and fix up its fields to reflect that. | |||
748 | */ | |||
749 | if (out != MP_DIGITS(c)((c)->digits)) { | |||
750 | if ((void *) MP_DIGITS(c)((c)->digits) != (void *) c) | |||
751 | s_free(MP_DIGITS(c)((c)->digits)); | |||
752 | MP_DIGITS(c)((c)->digits) = out; | |||
753 | MP_ALLOC(c)((c)->alloc) = p; | |||
754 | } | |||
755 | ||||
756 | MP_USED(c)((c)->used) = osize; /* might not be true, but we'll fix it ... */ | |||
757 | CLAMP(c)do{ mp_int z_ = (c); mp_size uz_ = ((z_)->used); mp_digit * dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0); /* ... right here */ | |||
758 | MP_SIGN(c)((c)->sign) = osign; | |||
759 | ||||
760 | return MP_OK; | |||
761 | } | |||
762 | ||||
763 | mp_result mp_int_mul_value(mp_int a, mp_small value, mp_int c) | |||
764 | { | |||
765 | mpz_t vtmp; | |||
766 | mp_digit vbuf[MP_VALUE_DIGITS(value)((sizeof(value)+(sizeof(mp_digit)-1))/sizeof(mp_digit))]; | |||
767 | ||||
768 | s_fake(&vtmp, value, vbuf); | |||
769 | ||||
770 | return mp_int_mul(a, &vtmp, c); | |||
771 | } | |||
772 | ||||
773 | mp_result mp_int_mul_pow2(mp_int a, mp_small p2, mp_int c) | |||
774 | { | |||
775 | mp_result res; | |||
776 | CHECK(a != NULL && c != NULL && p2 >= 0)((a != ((void*)0) && c != ((void*)0) && p2 >= 0) ? (void) (0) : __assert_fail ("a != ((void*)0) && c != ((void*)0) && p2 >= 0" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 776, __PRETTY_FUNCTION__)); | |||
777 | ||||
778 | if ((res = mp_int_copy(a, c)) != MP_OK) | |||
779 | return res; | |||
780 | ||||
781 | if (s_qmul(c, (mp_size) p2)) | |||
782 | return MP_OK; | |||
783 | else | |||
784 | return MP_MEMORY; | |||
785 | } | |||
786 | ||||
787 | mp_result mp_int_sqr(mp_int a, mp_int c) | |||
788 | { | |||
789 | mp_digit *out; | |||
790 | mp_size osize, p = 0; | |||
791 | ||||
792 | CHECK(a != NULL && c != NULL)((a != ((void*)0) && c != ((void*)0)) ? (void) (0) : __assert_fail ("a != ((void*)0) && c != ((void*)0)", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 792, __PRETTY_FUNCTION__)); | |||
793 | ||||
794 | /* Get a temporary buffer big enough to hold the result */ | |||
795 | osize = (mp_size) 4 * ((MP_USED(a)((a)->used) + 1) / 2); | |||
796 | if (a == c) { | |||
797 | p = ROUND_PREC(osize)((mp_size)(2*(((osize)+1)/2))); | |||
798 | p = MAX(p, default_precision)((default_precision)>(p)?(default_precision):(p)); | |||
799 | ||||
800 | if ((out = s_alloc(p)) == NULL((void*)0)) | |||
801 | return MP_MEMORY; | |||
802 | } | |||
803 | else { | |||
804 | if (!s_pad(c, osize)) | |||
805 | return MP_MEMORY; | |||
806 | ||||
807 | out = MP_DIGITS(c)((c)->digits); | |||
808 | } | |||
809 | ZERO(out, osize)do{ mp_size i__ = (osize) * sizeof(mp_digit); mp_digit *p__ = (out); memset(p__, 0, i__); } while(0); | |||
810 | ||||
811 | s_ksqr(MP_DIGITS(a)((a)->digits), out, MP_USED(a)((a)->used)); | |||
812 | ||||
813 | /* Get rid of whatever memory c was already using, and fix up its fields to | |||
814 | reflect the new digit array it's using | |||
815 | */ | |||
816 | if (out != MP_DIGITS(c)((c)->digits)) { | |||
817 | if ((void *) MP_DIGITS(c)((c)->digits) != (void *) c) | |||
818 | s_free(MP_DIGITS(c)((c)->digits)); | |||
819 | MP_DIGITS(c)((c)->digits) = out; | |||
820 | MP_ALLOC(c)((c)->alloc) = p; | |||
821 | } | |||
822 | ||||
823 | MP_USED(c)((c)->used) = osize; /* might not be true, but we'll fix it ... */ | |||
824 | CLAMP(c)do{ mp_int z_ = (c); mp_size uz_ = ((z_)->used); mp_digit * dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0); /* ... right here */ | |||
825 | MP_SIGN(c)((c)->sign) = MP_ZPOS; | |||
826 | ||||
827 | return MP_OK; | |||
828 | } | |||
829 | ||||
830 | mp_result mp_int_div(mp_int a, mp_int b, mp_int q, mp_int r) | |||
831 | { | |||
832 | int cmp, lg; | |||
833 | mp_result res = MP_OK; | |||
834 | mp_int qout, rout; | |||
835 | mp_sign sa = MP_SIGN(a)((a)->sign), sb = MP_SIGN(b)((b)->sign); | |||
836 | DECLARE_TEMP(2)mpz_t temp[(2)]; int last__ = 0; | |||
837 | ||||
838 | CHECK(a != NULL && b != NULL && q != r)((a != ((void*)0) && b != ((void*)0) && q != r ) ? (void) (0) : __assert_fail ("a != ((void*)0) && b != ((void*)0) && q != r" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 838, __PRETTY_FUNCTION__)); | |||
839 | ||||
840 | if (CMPZ(b)(((b)->used==1&&(b)->digits[0]==0)?0:((b)->sign ==MP_NEG)?-1:1) == 0) | |||
841 | return MP_UNDEF; | |||
842 | else if ((cmp = s_ucmp(a, b)) < 0) { | |||
843 | /* If |a| < |b|, no division is required: | |||
844 | q = 0, r = a | |||
845 | */ | |||
846 | if (r && (res = mp_int_copy(a, r)) != MP_OK) | |||
847 | return res; | |||
848 | ||||
849 | if (q) | |||
850 | mp_int_zero(q); | |||
851 | ||||
852 | return MP_OK; | |||
853 | } | |||
854 | else if (cmp == 0) { | |||
855 | /* If |a| = |b|, no division is required: | |||
856 | q = 1 or -1, r = 0 | |||
857 | */ | |||
858 | if (r) | |||
859 | mp_int_zero(r); | |||
860 | ||||
861 | if (q) { | |||
862 | mp_int_zero(q); | |||
863 | q->digits[0] = 1; | |||
864 | ||||
865 | if (sa != sb) | |||
866 | MP_SIGN(q)((q)->sign) = MP_NEG; | |||
867 | } | |||
868 | ||||
869 | return MP_OK; | |||
870 | } | |||
871 | ||||
872 | /* When |a| > |b|, real division is required. We need someplace to store | |||
873 | quotient and remainder, but q and r are allowed to be NULL or to overlap | |||
874 | with the inputs. | |||
875 | */ | |||
876 | if ((lg = s_isp2(b)) < 0) { | |||
877 | if (q && b != q) { | |||
878 | if ((res = mp_int_copy(a, q)) != MP_OK) | |||
879 | goto CLEANUP; | |||
880 | else | |||
881 | qout = q; | |||
882 | } | |||
883 | else { | |||
884 | qout = LAST_TEMP()(temp + (last__)); | |||
885 | SETUP(mp_int_init_copy(LAST_TEMP(), a))do{ if ((res = (mp_int_init_copy((temp + (last__)), a))) != MP_OK ) goto CLEANUP; ++(last__); } while(0); | |||
886 | } | |||
887 | ||||
888 | if (r && a != r) { | |||
889 | if ((res = mp_int_copy(b, r)) != MP_OK) | |||
890 | goto CLEANUP; | |||
891 | else | |||
892 | rout = r; | |||
893 | } | |||
894 | else { | |||
895 | rout = LAST_TEMP()(temp + (last__)); | |||
896 | SETUP(mp_int_init_copy(LAST_TEMP(), b))do{ if ((res = (mp_int_init_copy((temp + (last__)), b))) != MP_OK ) goto CLEANUP; ++(last__); } while(0); | |||
897 | } | |||
898 | ||||
899 | if ((res = s_udiv_knuth(qout, rout)) != MP_OK) goto CLEANUP; | |||
900 | } | |||
901 | else { | |||
902 | if (q && (res = mp_int_copy(a, q)) != MP_OK) goto CLEANUP; | |||
903 | if (r && (res = mp_int_copy(a, r)) != MP_OK) goto CLEANUP; | |||
904 | ||||
905 | if (q) s_qdiv(q, (mp_size) lg); qout = q; | |||
906 | if (r) s_qmod(r, (mp_size) lg); rout = r; | |||
907 | } | |||
908 | ||||
909 | /* Recompute signs for output */ | |||
910 | if (rout) { | |||
911 | MP_SIGN(rout)((rout)->sign) = sa; | |||
912 | if (CMPZ(rout)(((rout)->used==1&&(rout)->digits[0]==0)?0:((rout )->sign==MP_NEG)?-1:1) == 0) | |||
913 | MP_SIGN(rout)((rout)->sign) = MP_ZPOS; | |||
914 | } | |||
915 | if (qout) { | |||
916 | MP_SIGN(qout)((qout)->sign) = (sa == sb) ? MP_ZPOS : MP_NEG; | |||
917 | if (CMPZ(qout)(((qout)->used==1&&(qout)->digits[0]==0)?0:((qout )->sign==MP_NEG)?-1:1) == 0) | |||
918 | MP_SIGN(qout)((qout)->sign) = MP_ZPOS; | |||
919 | } | |||
920 | ||||
921 | if (q && (res = mp_int_copy(qout, q)) != MP_OK) goto CLEANUP; | |||
922 | if (r && (res = mp_int_copy(rout, r)) != MP_OK) goto CLEANUP; | |||
923 | ||||
924 | CLEANUP_TEMP()CLEANUP: while (--last__ >= 0) mp_int_clear((temp + (last__ ))); | |||
925 | return res; | |||
926 | } | |||
927 | ||||
928 | mp_result mp_int_mod(mp_int a, mp_int m, mp_int c) | |||
929 | { | |||
930 | mp_result res; | |||
931 | mpz_t tmp; | |||
932 | mp_int out; | |||
933 | ||||
934 | if (m == c) { | |||
935 | mp_int_init(&tmp); | |||
936 | out = &tmp; | |||
937 | } | |||
938 | else { | |||
939 | out = c; | |||
940 | } | |||
941 | ||||
942 | if ((res = mp_int_div(a, m, NULL((void*)0), out)) != MP_OK) | |||
943 | goto CLEANUP; | |||
944 | ||||
945 | if (CMPZ(out)(((out)->used==1&&(out)->digits[0]==0)?0:((out) ->sign==MP_NEG)?-1:1) < 0) | |||
946 | res = mp_int_add(out, m, c); | |||
947 | else | |||
948 | res = mp_int_copy(out, c); | |||
949 | ||||
950 | CLEANUP: | |||
951 | if (out != c) | |||
952 | mp_int_clear(&tmp); | |||
953 | ||||
954 | return res; | |||
955 | } | |||
956 | ||||
957 | mp_result mp_int_div_value(mp_int a, mp_small value, mp_int q, mp_small *r) | |||
958 | { | |||
959 | mpz_t vtmp, rtmp; | |||
960 | mp_digit vbuf[MP_VALUE_DIGITS(value)((sizeof(value)+(sizeof(mp_digit)-1))/sizeof(mp_digit))]; | |||
961 | mp_result res; | |||
962 | ||||
963 | mp_int_init(&rtmp); | |||
964 | s_fake(&vtmp, value, vbuf); | |||
965 | ||||
966 | if ((res = mp_int_div(a, &vtmp, q, &rtmp)) != MP_OK) | |||
967 | goto CLEANUP; | |||
968 | ||||
969 | if (r) | |||
970 | (void) mp_int_to_int(&rtmp, r); /* can't fail */ | |||
971 | ||||
972 | CLEANUP: | |||
973 | mp_int_clear(&rtmp); | |||
974 | return res; | |||
975 | } | |||
976 | ||||
977 | mp_result mp_int_div_pow2(mp_int a, mp_small p2, mp_int q, mp_int r) | |||
978 | { | |||
979 | mp_result res = MP_OK; | |||
980 | ||||
981 | CHECK(a != NULL && p2 >= 0 && q != r)((a != ((void*)0) && p2 >= 0 && q != r) ? ( void) (0) : __assert_fail ("a != ((void*)0) && p2 >= 0 && q != r" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 981, __PRETTY_FUNCTION__)); | |||
982 | ||||
983 | if (q != NULL((void*)0) && (res = mp_int_copy(a, q)) == MP_OK) | |||
984 | s_qdiv(q, (mp_size) p2); | |||
985 | ||||
986 | if (res == MP_OK && r != NULL((void*)0) && (res = mp_int_copy(a, r)) == MP_OK) | |||
987 | s_qmod(r, (mp_size) p2); | |||
988 | ||||
989 | return res; | |||
990 | } | |||
991 | ||||
992 | mp_result mp_int_expt(mp_int a, mp_small b, mp_int c) | |||
993 | { | |||
994 | mpz_t t; | |||
995 | mp_result res; | |||
996 | unsigned int v = labs(b); | |||
997 | ||||
998 | CHECK(c != NULL)((c != ((void*)0)) ? (void) (0) : __assert_fail ("c != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 998, __PRETTY_FUNCTION__)); | |||
999 | if (b
| |||
1000 | return MP_RANGE; | |||
1001 | ||||
1002 | if ((res = mp_int_init_copy(&t, a)) != MP_OK) | |||
1003 | return res; | |||
1004 | ||||
1005 | (void) mp_int_set_value(c, 1); | |||
1006 | while (v != 0) { | |||
1007 | if (v & 1) { | |||
1008 | if ((res = mp_int_mul(c, &t, c)) != MP_OK) | |||
1009 | goto CLEANUP; | |||
1010 | } | |||
1011 | ||||
1012 | v >>= 1; | |||
1013 | if (v == 0) break; | |||
1014 | ||||
1015 | if ((res = mp_int_sqr(&t, &t)) != MP_OK) | |||
1016 | goto CLEANUP; | |||
1017 | } | |||
1018 | ||||
1019 | CLEANUP: | |||
1020 | mp_int_clear(&t); | |||
1021 | return res; | |||
1022 | } | |||
1023 | ||||
1024 | mp_result mp_int_expt_value(mp_small a, mp_small b, mp_int c) | |||
1025 | { | |||
1026 | mpz_t t; | |||
1027 | mp_result res; | |||
1028 | unsigned int v = labs(b); | |||
1029 | ||||
1030 | CHECK(c != NULL)((c != ((void*)0)) ? (void) (0) : __assert_fail ("c != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1030, __PRETTY_FUNCTION__)); | |||
1031 | if (b < 0) | |||
1032 | return MP_RANGE; | |||
1033 | ||||
1034 | if ((res = mp_int_init_value(&t, a)) != MP_OK) | |||
1035 | return res; | |||
1036 | ||||
1037 | (void) mp_int_set_value(c, 1); | |||
1038 | while (v != 0) { | |||
1039 | if (v & 1) { | |||
1040 | if ((res = mp_int_mul(c, &t, c)) != MP_OK) | |||
1041 | goto CLEANUP; | |||
1042 | } | |||
1043 | ||||
1044 | v >>= 1; | |||
1045 | if (v == 0) break; | |||
1046 | ||||
1047 | if ((res = mp_int_sqr(&t, &t)) != MP_OK) | |||
1048 | goto CLEANUP; | |||
1049 | } | |||
1050 | ||||
1051 | CLEANUP: | |||
1052 | mp_int_clear(&t); | |||
1053 | return res; | |||
1054 | } | |||
1055 | ||||
1056 | mp_result mp_int_expt_full(mp_int a, mp_int b, mp_int c) | |||
1057 | { | |||
1058 | mpz_t t; | |||
1059 | mp_result res; | |||
1060 | unsigned ix, jx; | |||
1061 | ||||
1062 | CHECK(a != NULL && b != NULL && c != NULL)((a != ((void*)0) && b != ((void*)0) && c != ( (void*)0)) ? (void) (0) : __assert_fail ("a != ((void*)0) && b != ((void*)0) && c != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1062, __PRETTY_FUNCTION__)); | |||
1063 | if (MP_SIGN(b)((b)->sign) == MP_NEG) | |||
1064 | return MP_RANGE; | |||
1065 | ||||
1066 | if ((res = mp_int_init_copy(&t, a)) != MP_OK) | |||
1067 | return res; | |||
1068 | ||||
1069 | (void) mp_int_set_value(c, 1); | |||
1070 | for (ix = 0; ix < MP_USED(b)((b)->used); ++ix) { | |||
1071 | mp_digit d = b->digits[ix]; | |||
1072 | ||||
1073 | for (jx = 0; jx < MP_DIGIT_BIT(sizeof(mp_digit) * 8); ++jx) { | |||
1074 | if (d & 1) { | |||
1075 | if ((res = mp_int_mul(c, &t, c)) != MP_OK) | |||
1076 | goto CLEANUP; | |||
1077 | } | |||
1078 | ||||
1079 | d >>= 1; | |||
1080 | if (d == 0 && ix + 1 == MP_USED(b)((b)->used)) | |||
1081 | break; | |||
1082 | if ((res = mp_int_sqr(&t, &t)) != MP_OK) | |||
1083 | goto CLEANUP; | |||
1084 | } | |||
1085 | } | |||
1086 | ||||
1087 | CLEANUP: | |||
1088 | mp_int_clear(&t); | |||
1089 | return res; | |||
1090 | } | |||
1091 | ||||
1092 | int mp_int_compare(mp_int a, mp_int b) | |||
1093 | { | |||
1094 | mp_sign sa; | |||
1095 | ||||
1096 | CHECK(a != NULL && b != NULL)((a != ((void*)0) && b != ((void*)0)) ? (void) (0) : __assert_fail ("a != ((void*)0) && b != ((void*)0)", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1096, __PRETTY_FUNCTION__)); | |||
1097 | ||||
1098 | sa = MP_SIGN(a)((a)->sign); | |||
1099 | if (sa == MP_SIGN(b)((b)->sign)) { | |||
1100 | int cmp = s_ucmp(a, b); | |||
1101 | ||||
1102 | /* If they're both zero or positive, the normal comparison applies; if both | |||
1103 | negative, the sense is reversed. */ | |||
1104 | if (sa == MP_ZPOS) | |||
1105 | return cmp; | |||
1106 | else | |||
1107 | return -cmp; | |||
1108 | ||||
1109 | } | |||
1110 | else { | |||
1111 | if (sa == MP_ZPOS) | |||
1112 | return 1; | |||
1113 | else | |||
1114 | return -1; | |||
1115 | } | |||
1116 | } | |||
1117 | ||||
1118 | int mp_int_compare_unsigned(mp_int a, mp_int b) | |||
1119 | { | |||
1120 | NRCHECK(a != NULL && b != NULL)((a != ((void*)0) && b != ((void*)0)) ? (void) (0) : __assert_fail ("a != ((void*)0) && b != ((void*)0)", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1120, __PRETTY_FUNCTION__)); | |||
1121 | ||||
1122 | return s_ucmp(a, b); | |||
1123 | } | |||
1124 | ||||
1125 | int mp_int_compare_zero(mp_int z) | |||
1126 | { | |||
1127 | NRCHECK(z != NULL)((z != ((void*)0)) ? (void) (0) : __assert_fail ("z != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1127, __PRETTY_FUNCTION__)); | |||
1128 | ||||
1129 | if (MP_USED(z)((z)->used) == 1 && z->digits[0] == 0) | |||
1130 | return 0; | |||
1131 | else if (MP_SIGN(z)((z)->sign) == MP_ZPOS) | |||
1132 | return 1; | |||
1133 | else | |||
1134 | return -1; | |||
1135 | } | |||
1136 | ||||
1137 | int mp_int_compare_value(mp_int z, mp_small value) | |||
1138 | { | |||
1139 | mp_sign vsign = (value < 0) ? MP_NEG : MP_ZPOS; | |||
1140 | int cmp; | |||
1141 | ||||
1142 | CHECK(z != NULL)((z != ((void*)0)) ? (void) (0) : __assert_fail ("z != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1142, __PRETTY_FUNCTION__)); | |||
1143 | ||||
1144 | if (vsign == MP_SIGN(z)((z)->sign)) { | |||
1145 | cmp = s_vcmp(z, value); | |||
1146 | ||||
1147 | return (vsign == MP_ZPOS) ? cmp : -cmp; | |||
1148 | } | |||
1149 | else { | |||
1150 | return (value < 0) ? 1 : -1; | |||
1151 | } | |||
1152 | } | |||
1153 | ||||
1154 | int mp_int_compare_uvalue(mp_int z, mp_usmall uv) | |||
1155 | { | |||
1156 | CHECK(z != NULL)((z != ((void*)0)) ? (void) (0) : __assert_fail ("z != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1156, __PRETTY_FUNCTION__)); | |||
1157 | ||||
1158 | if (MP_SIGN(z)((z)->sign) == MP_NEG) | |||
1159 | return -1; | |||
1160 | else | |||
1161 | return s_uvcmp(z, uv); | |||
1162 | } | |||
1163 | ||||
1164 | mp_result mp_int_exptmod(mp_int a, mp_int b, mp_int m, mp_int c) | |||
1165 | { | |||
1166 | mp_result res; | |||
1167 | mp_size um; | |||
1168 | mp_int s; | |||
1169 | DECLARE_TEMP(3)mpz_t temp[(3)]; int last__ = 0; | |||
1170 | ||||
1171 | CHECK(a != NULL && b != NULL && c != NULL && m != NULL)((a != ((void*)0) && b != ((void*)0) && c != ( (void*)0) && m != ((void*)0)) ? (void) (0) : __assert_fail ("a != ((void*)0) && b != ((void*)0) && c != ((void*)0) && m != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1171, __PRETTY_FUNCTION__)); | |||
1172 | ||||
1173 | /* Zero moduli and negative exponents are not considered. */ | |||
1174 | if (CMPZ(m)(((m)->used==1&&(m)->digits[0]==0)?0:((m)->sign ==MP_NEG)?-1:1) == 0) | |||
1175 | return MP_UNDEF; | |||
1176 | if (CMPZ(b)(((b)->used==1&&(b)->digits[0]==0)?0:((b)->sign ==MP_NEG)?-1:1) < 0) | |||
1177 | return MP_RANGE; | |||
1178 | ||||
1179 | um = MP_USED(m)((m)->used); | |||
1180 | SETUP(mp_int_init_size(TEMP(0), 2 * um))do{ if ((res = (mp_int_init_size((temp + (0)), 2 * um))) != MP_OK ) goto CLEANUP; ++(last__); } while(0); | |||
1181 | SETUP(mp_int_init_size(TEMP(1), 2 * um))do{ if ((res = (mp_int_init_size((temp + (1)), 2 * um))) != MP_OK ) goto CLEANUP; ++(last__); } while(0); | |||
1182 | ||||
1183 | if (c == b || c == m) { | |||
1184 | SETUP(mp_int_init_size(TEMP(2), 2 * um))do{ if ((res = (mp_int_init_size((temp + (2)), 2 * um))) != MP_OK ) goto CLEANUP; ++(last__); } while(0); | |||
1185 | s = TEMP(2)(temp + (2)); | |||
1186 | } | |||
1187 | else { | |||
1188 | s = c; | |||
1189 | } | |||
1190 | ||||
1191 | if ((res = mp_int_mod(a, m, TEMP(0)(temp + (0)))) != MP_OK) goto CLEANUP; | |||
1192 | ||||
1193 | if ((res = s_brmu(TEMP(1)(temp + (1)), m)) != MP_OK) goto CLEANUP; | |||
1194 | ||||
1195 | if ((res = s_embar(TEMP(0)(temp + (0)), b, m, TEMP(1)(temp + (1)), s)) != MP_OK) | |||
1196 | goto CLEANUP; | |||
1197 | ||||
1198 | res = mp_int_copy(s, c); | |||
1199 | ||||
1200 | CLEANUP_TEMP()CLEANUP: while (--last__ >= 0) mp_int_clear((temp + (last__ ))); | |||
1201 | return res; | |||
1202 | } | |||
1203 | ||||
1204 | mp_result mp_int_exptmod_evalue(mp_int a, mp_small value, mp_int m, mp_int c) | |||
1205 | { | |||
1206 | mpz_t vtmp; | |||
1207 | mp_digit vbuf[MP_VALUE_DIGITS(value)((sizeof(value)+(sizeof(mp_digit)-1))/sizeof(mp_digit))]; | |||
1208 | ||||
1209 | s_fake(&vtmp, value, vbuf); | |||
1210 | ||||
1211 | return mp_int_exptmod(a, &vtmp, m, c); | |||
1212 | } | |||
1213 | ||||
1214 | mp_result mp_int_exptmod_bvalue(mp_small value, mp_int b, | |||
1215 | mp_int m, mp_int c) | |||
1216 | { | |||
1217 | mpz_t vtmp; | |||
1218 | mp_digit vbuf[MP_VALUE_DIGITS(value)((sizeof(value)+(sizeof(mp_digit)-1))/sizeof(mp_digit))]; | |||
1219 | ||||
1220 | s_fake(&vtmp, value, vbuf); | |||
1221 | ||||
1222 | return mp_int_exptmod(&vtmp, b, m, c); | |||
1223 | } | |||
1224 | ||||
1225 | mp_result mp_int_exptmod_known(mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c) | |||
1226 | { | |||
1227 | mp_result res; | |||
1228 | mp_size um; | |||
1229 | mp_int s; | |||
1230 | DECLARE_TEMP(2)mpz_t temp[(2)]; int last__ = 0; | |||
1231 | ||||
1232 | CHECK(a && b && m && c)((a && b && m && c) ? (void) (0) : __assert_fail ("a && b && m && c", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1232, __PRETTY_FUNCTION__)); | |||
1233 | ||||
1234 | /* Zero moduli and negative exponents are not considered. */ | |||
1235 | if (CMPZ(m)(((m)->used==1&&(m)->digits[0]==0)?0:((m)->sign ==MP_NEG)?-1:1) == 0) | |||
1236 | return MP_UNDEF; | |||
1237 | if (CMPZ(b)(((b)->used==1&&(b)->digits[0]==0)?0:((b)->sign ==MP_NEG)?-1:1) < 0) | |||
1238 | return MP_RANGE; | |||
1239 | ||||
1240 | um = MP_USED(m)((m)->used); | |||
1241 | SETUP(mp_int_init_size(TEMP(0), 2 * um))do{ if ((res = (mp_int_init_size((temp + (0)), 2 * um))) != MP_OK ) goto CLEANUP; ++(last__); } while(0); | |||
1242 | ||||
1243 | if (c == b || c == m) { | |||
1244 | SETUP(mp_int_init_size(TEMP(1), 2 * um))do{ if ((res = (mp_int_init_size((temp + (1)), 2 * um))) != MP_OK ) goto CLEANUP; ++(last__); } while(0); | |||
1245 | s = TEMP(1)(temp + (1)); | |||
1246 | } | |||
1247 | else { | |||
1248 | s = c; | |||
1249 | } | |||
1250 | ||||
1251 | if ((res = mp_int_mod(a, m, TEMP(0)(temp + (0)))) != MP_OK) goto CLEANUP; | |||
1252 | ||||
1253 | if ((res = s_embar(TEMP(0)(temp + (0)), b, m, mu, s)) != MP_OK) | |||
1254 | goto CLEANUP; | |||
1255 | ||||
1256 | res = mp_int_copy(s, c); | |||
1257 | ||||
1258 | CLEANUP_TEMP()CLEANUP: while (--last__ >= 0) mp_int_clear((temp + (last__ ))); | |||
1259 | return res; | |||
1260 | } | |||
1261 | ||||
1262 | mp_result mp_int_redux_const(mp_int m, mp_int c) | |||
1263 | { | |||
1264 | CHECK(m != NULL && c != NULL && m != c)((m != ((void*)0) && c != ((void*)0) && m != c ) ? (void) (0) : __assert_fail ("m != ((void*)0) && c != ((void*)0) && m != c" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1264, __PRETTY_FUNCTION__)); | |||
1265 | ||||
1266 | return s_brmu(c, m); | |||
1267 | } | |||
1268 | ||||
1269 | mp_result mp_int_invmod(mp_int a, mp_int m, mp_int c) | |||
1270 | { | |||
1271 | mp_result res; | |||
1272 | mp_sign sa; | |||
1273 | DECLARE_TEMP(2)mpz_t temp[(2)]; int last__ = 0; | |||
1274 | ||||
1275 | CHECK(a != NULL && m != NULL && c != NULL)((a != ((void*)0) && m != ((void*)0) && c != ( (void*)0)) ? (void) (0) : __assert_fail ("a != ((void*)0) && m != ((void*)0) && c != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1275, __PRETTY_FUNCTION__)); | |||
1276 | ||||
1277 | if (CMPZ(a)(((a)->used==1&&(a)->digits[0]==0)?0:((a)->sign ==MP_NEG)?-1:1) == 0 || CMPZ(m)(((m)->used==1&&(m)->digits[0]==0)?0:((m)->sign ==MP_NEG)?-1:1) <= 0) | |||
1278 | return MP_RANGE; | |||
1279 | ||||
1280 | sa = MP_SIGN(a)((a)->sign); /* need this for the result later */ | |||
1281 | ||||
1282 | for (last__ = 0; last__ < 2; ++last__) | |||
1283 | mp_int_init(LAST_TEMP()(temp + (last__))); | |||
1284 | ||||
1285 | if ((res = mp_int_egcd(a, m, TEMP(0)(temp + (0)), TEMP(1)(temp + (1)), NULL((void*)0))) != MP_OK) | |||
1286 | goto CLEANUP; | |||
1287 | ||||
1288 | if (mp_int_compare_value(TEMP(0)(temp + (0)), 1) != 0) { | |||
1289 | res = MP_UNDEF; | |||
1290 | goto CLEANUP; | |||
1291 | } | |||
1292 | ||||
1293 | /* It is first necessary to constrain the value to the proper range */ | |||
1294 | if ((res = mp_int_mod(TEMP(1)(temp + (1)), m, TEMP(1)(temp + (1)))) != MP_OK) | |||
1295 | goto CLEANUP; | |||
1296 | ||||
1297 | /* Now, if 'a' was originally negative, the value we have is actually the | |||
1298 | magnitude of the negative representative; to get the positive value we | |||
1299 | have to subtract from the modulus. Otherwise, the value is okay as it | |||
1300 | stands. | |||
1301 | */ | |||
1302 | if (sa == MP_NEG) | |||
1303 | res = mp_int_sub(m, TEMP(1)(temp + (1)), c); | |||
1304 | else | |||
1305 | res = mp_int_copy(TEMP(1)(temp + (1)), c); | |||
1306 | ||||
1307 | CLEANUP_TEMP()CLEANUP: while (--last__ >= 0) mp_int_clear((temp + (last__ ))); | |||
1308 | return res; | |||
1309 | } | |||
1310 | ||||
1311 | /* Binary GCD algorithm due to Josef Stein, 1961 */ | |||
1312 | mp_result mp_int_gcd(mp_int a, mp_int b, mp_int c) | |||
1313 | { | |||
1314 | int ca, cb, k = 0; | |||
1315 | mpz_t u, v, t; | |||
1316 | mp_result res; | |||
1317 | ||||
1318 | CHECK(a != NULL && b != NULL && c != NULL)((a != ((void*)0) && b != ((void*)0) && c != ( (void*)0)) ? (void) (0) : __assert_fail ("a != ((void*)0) && b != ((void*)0) && c != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1318, __PRETTY_FUNCTION__)); | |||
1319 | ||||
1320 | ca = CMPZ(a)(((a)->used==1&&(a)->digits[0]==0)?0:((a)->sign ==MP_NEG)?-1:1); | |||
1321 | cb = CMPZ(b)(((b)->used==1&&(b)->digits[0]==0)?0:((b)->sign ==MP_NEG)?-1:1); | |||
1322 | if (ca == 0 && cb == 0) | |||
1323 | return MP_UNDEF; | |||
1324 | else if (ca == 0) | |||
1325 | return mp_int_abs(b, c); | |||
1326 | else if (cb == 0) | |||
1327 | return mp_int_abs(a, c); | |||
1328 | ||||
1329 | mp_int_init(&t); | |||
1330 | if ((res = mp_int_init_copy(&u, a)) != MP_OK) | |||
1331 | goto U; | |||
1332 | if ((res = mp_int_init_copy(&v, b)) != MP_OK) | |||
1333 | goto V; | |||
1334 | ||||
1335 | MP_SIGN(&u)((&u)->sign) = MP_ZPOS; MP_SIGN(&v)((&v)->sign) = MP_ZPOS; | |||
1336 | ||||
1337 | { /* Divide out common factors of 2 from u and v */ | |||
1338 | int div2_u = s_dp2k(&u), div2_v = s_dp2k(&v); | |||
1339 | ||||
1340 | k = MIN(div2_u, div2_v)((div2_v)<(div2_u)?(div2_v):(div2_u)); | |||
1341 | s_qdiv(&u, (mp_size) k); | |||
1342 | s_qdiv(&v, (mp_size) k); | |||
1343 | } | |||
1344 | ||||
1345 | if (mp_int_is_odd(&u)((&u)->digits[0] & 1)) { | |||
1346 | if ((res = mp_int_neg(&v, &t)) != MP_OK) | |||
1347 | goto CLEANUP; | |||
1348 | } | |||
1349 | else { | |||
1350 | if ((res = mp_int_copy(&u, &t)) != MP_OK) | |||
1351 | goto CLEANUP; | |||
1352 | } | |||
1353 | ||||
1354 | for (;;) { | |||
1355 | s_qdiv(&t, s_dp2k(&t)); | |||
1356 | ||||
1357 | if (CMPZ(&t)(((&t)->used==1&&(&t)->digits[0]==0)?0: ((&t)->sign==MP_NEG)?-1:1) > 0) { | |||
1358 | if ((res = mp_int_copy(&t, &u)) != MP_OK) | |||
1359 | goto CLEANUP; | |||
1360 | } | |||
1361 | else { | |||
1362 | if ((res = mp_int_neg(&t, &v)) != MP_OK) | |||
1363 | goto CLEANUP; | |||
1364 | } | |||
1365 | ||||
1366 | if ((res = mp_int_sub(&u, &v, &t)) != MP_OK) | |||
1367 | goto CLEANUP; | |||
1368 | ||||
1369 | if (CMPZ(&t)(((&t)->used==1&&(&t)->digits[0]==0)?0: ((&t)->sign==MP_NEG)?-1:1) == 0) | |||
1370 | break; | |||
1371 | } | |||
1372 | ||||
1373 | if ((res = mp_int_abs(&u, c)) != MP_OK) | |||
1374 | goto CLEANUP; | |||
1375 | if (!s_qmul(c, (mp_size) k)) | |||
1376 | res = MP_MEMORY; | |||
1377 | ||||
1378 | CLEANUP: | |||
1379 | mp_int_clear(&v); | |||
1380 | V: mp_int_clear(&u); | |||
1381 | U: mp_int_clear(&t); | |||
1382 | ||||
1383 | return res; | |||
1384 | } | |||
1385 | ||||
1386 | /* This is the binary GCD algorithm again, but this time we keep track of the | |||
1387 | elementary matrix operations as we go, so we can get values x and y | |||
1388 | satisfying c = ax + by. | |||
1389 | */ | |||
1390 | mp_result mp_int_egcd(mp_int a, mp_int b, mp_int c, | |||
1391 | mp_int x, mp_int y) | |||
1392 | { | |||
1393 | int k, ca, cb; | |||
1394 | mp_result res; | |||
1395 | DECLARE_TEMP(8)mpz_t temp[(8)]; int last__ = 0; | |||
1396 | ||||
1397 | CHECK(a != NULL && b != NULL && c != NULL &&((a != ((void*)0) && b != ((void*)0) && c != ( (void*)0) && (x != ((void*)0) || y != ((void*)0))) ? ( void) (0) : __assert_fail ("a != ((void*)0) && b != ((void*)0) && c != ((void*)0) && (x != ((void*)0) || y != ((void*)0))" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1398, __PRETTY_FUNCTION__)) | |||
1398 | (x != NULL || y != NULL))((a != ((void*)0) && b != ((void*)0) && c != ( (void*)0) && (x != ((void*)0) || y != ((void*)0))) ? ( void) (0) : __assert_fail ("a != ((void*)0) && b != ((void*)0) && c != ((void*)0) && (x != ((void*)0) || y != ((void*)0))" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1398, __PRETTY_FUNCTION__)); | |||
1399 | ||||
1400 | ca = CMPZ(a)(((a)->used==1&&(a)->digits[0]==0)?0:((a)->sign ==MP_NEG)?-1:1); | |||
1401 | cb = CMPZ(b)(((b)->used==1&&(b)->digits[0]==0)?0:((b)->sign ==MP_NEG)?-1:1); | |||
1402 | if (ca == 0 && cb == 0) | |||
1403 | return MP_UNDEF; | |||
1404 | else if (ca == 0) { | |||
1405 | if ((res = mp_int_abs(b, c)) != MP_OK) return res; | |||
1406 | mp_int_zero(x); (void) mp_int_set_value(y, 1); return MP_OK; | |||
1407 | } | |||
1408 | else if (cb == 0) { | |||
1409 | if ((res = mp_int_abs(a, c)) != MP_OK) return res; | |||
1410 | (void) mp_int_set_value(x, 1); mp_int_zero(y); return MP_OK; | |||
1411 | } | |||
1412 | ||||
1413 | /* Initialize temporaries: | |||
1414 | A:0, B:1, C:2, D:3, u:4, v:5, ou:6, ov:7 */ | |||
1415 | for (last__ = 0; last__ < 4; ++last__) | |||
1416 | mp_int_init(LAST_TEMP()(temp + (last__))); | |||
1417 | TEMP(0)(temp + (0))->digits[0] = 1; | |||
1418 | TEMP(3)(temp + (3))->digits[0] = 1; | |||
1419 | ||||
1420 | SETUP(mp_int_init_copy(TEMP(4), a))do{ if ((res = (mp_int_init_copy((temp + (4)), a))) != MP_OK) goto CLEANUP; ++(last__); } while(0); | |||
1421 | SETUP(mp_int_init_copy(TEMP(5), b))do{ if ((res = (mp_int_init_copy((temp + (5)), b))) != MP_OK) goto CLEANUP; ++(last__); } while(0); | |||
1422 | ||||
1423 | /* We will work with absolute values here */ | |||
1424 | MP_SIGN(TEMP(4))(((temp + (4)))->sign) = MP_ZPOS; | |||
1425 | MP_SIGN(TEMP(5))(((temp + (5)))->sign) = MP_ZPOS; | |||
1426 | ||||
1427 | { /* Divide out common factors of 2 from u and v */ | |||
1428 | int div2_u = s_dp2k(TEMP(4)(temp + (4))), div2_v = s_dp2k(TEMP(5)(temp + (5))); | |||
1429 | ||||
1430 | k = MIN(div2_u, div2_v)((div2_v)<(div2_u)?(div2_v):(div2_u)); | |||
1431 | s_qdiv(TEMP(4)(temp + (4)), k); | |||
1432 | s_qdiv(TEMP(5)(temp + (5)), k); | |||
1433 | } | |||
1434 | ||||
1435 | SETUP(mp_int_init_copy(TEMP(6), TEMP(4)))do{ if ((res = (mp_int_init_copy((temp + (6)), (temp + (4)))) ) != MP_OK) goto CLEANUP; ++(last__); } while(0); | |||
1436 | SETUP(mp_int_init_copy(TEMP(7), TEMP(5)))do{ if ((res = (mp_int_init_copy((temp + (7)), (temp + (5)))) ) != MP_OK) goto CLEANUP; ++(last__); } while(0); | |||
1437 | ||||
1438 | for (;;) { | |||
1439 | while (mp_int_is_even(TEMP(4))!(((temp + (4)))->digits[0] & 1)) { | |||
1440 | s_qdiv(TEMP(4)(temp + (4)), 1); | |||
1441 | ||||
1442 | if (mp_int_is_odd(TEMP(0))(((temp + (0)))->digits[0] & 1) || mp_int_is_odd(TEMP(1))(((temp + (1)))->digits[0] & 1)) { | |||
1443 | if ((res = mp_int_add(TEMP(0)(temp + (0)), TEMP(7)(temp + (7)), TEMP(0)(temp + (0)))) != MP_OK) | |||
1444 | goto CLEANUP; | |||
1445 | if ((res = mp_int_sub(TEMP(1)(temp + (1)), TEMP(6)(temp + (6)), TEMP(1)(temp + (1)))) != MP_OK) | |||
1446 | goto CLEANUP; | |||
1447 | } | |||
1448 | ||||
1449 | s_qdiv(TEMP(0)(temp + (0)), 1); | |||
1450 | s_qdiv(TEMP(1)(temp + (1)), 1); | |||
1451 | } | |||
1452 | ||||
1453 | while (mp_int_is_even(TEMP(5))!(((temp + (5)))->digits[0] & 1)) { | |||
1454 | s_qdiv(TEMP(5)(temp + (5)), 1); | |||
1455 | ||||
1456 | if (mp_int_is_odd(TEMP(2))(((temp + (2)))->digits[0] & 1) || mp_int_is_odd(TEMP(3))(((temp + (3)))->digits[0] & 1)) { | |||
1457 | if ((res = mp_int_add(TEMP(2)(temp + (2)), TEMP(7)(temp + (7)), TEMP(2)(temp + (2)))) != MP_OK) | |||
1458 | goto CLEANUP; | |||
1459 | if ((res = mp_int_sub(TEMP(3)(temp + (3)), TEMP(6)(temp + (6)), TEMP(3)(temp + (3)))) != MP_OK) | |||
1460 | goto CLEANUP; | |||
1461 | } | |||
1462 | ||||
1463 | s_qdiv(TEMP(2)(temp + (2)), 1); | |||
1464 | s_qdiv(TEMP(3)(temp + (3)), 1); | |||
1465 | } | |||
1466 | ||||
1467 | if (mp_int_compare(TEMP(4)(temp + (4)), TEMP(5)(temp + (5))) >= 0) { | |||
1468 | if ((res = mp_int_sub(TEMP(4)(temp + (4)), TEMP(5)(temp + (5)), TEMP(4)(temp + (4)))) != MP_OK) goto CLEANUP; | |||
1469 | if ((res = mp_int_sub(TEMP(0)(temp + (0)), TEMP(2)(temp + (2)), TEMP(0)(temp + (0)))) != MP_OK) goto CLEANUP; | |||
1470 | if ((res = mp_int_sub(TEMP(1)(temp + (1)), TEMP(3)(temp + (3)), TEMP(1)(temp + (1)))) != MP_OK) goto CLEANUP; | |||
1471 | } | |||
1472 | else { | |||
1473 | if ((res = mp_int_sub(TEMP(5)(temp + (5)), TEMP(4)(temp + (4)), TEMP(5)(temp + (5)))) != MP_OK) goto CLEANUP; | |||
1474 | if ((res = mp_int_sub(TEMP(2)(temp + (2)), TEMP(0)(temp + (0)), TEMP(2)(temp + (2)))) != MP_OK) goto CLEANUP; | |||
1475 | if ((res = mp_int_sub(TEMP(3)(temp + (3)), TEMP(1)(temp + (1)), TEMP(3)(temp + (3)))) != MP_OK) goto CLEANUP; | |||
1476 | } | |||
1477 | ||||
1478 | if (CMPZ(TEMP(4))((((temp + (4)))->used==1&&((temp + (4)))->digits [0]==0)?0:(((temp + (4)))->sign==MP_NEG)?-1:1) == 0) { | |||
1479 | if (x && (res = mp_int_copy(TEMP(2)(temp + (2)), x)) != MP_OK) goto CLEANUP; | |||
1480 | if (y && (res = mp_int_copy(TEMP(3)(temp + (3)), y)) != MP_OK) goto CLEANUP; | |||
1481 | if (c) { | |||
1482 | if (!s_qmul(TEMP(5)(temp + (5)), k)) { | |||
1483 | res = MP_MEMORY; | |||
1484 | goto CLEANUP; | |||
1485 | } | |||
1486 | ||||
1487 | res = mp_int_copy(TEMP(5)(temp + (5)), c); | |||
1488 | } | |||
1489 | ||||
1490 | break; | |||
1491 | } | |||
1492 | } | |||
1493 | ||||
1494 | CLEANUP_TEMP()CLEANUP: while (--last__ >= 0) mp_int_clear((temp + (last__ ))); | |||
1495 | return res; | |||
1496 | } | |||
1497 | ||||
1498 | mp_result mp_int_lcm(mp_int a, mp_int b, mp_int c) | |||
1499 | { | |||
1500 | mpz_t lcm; | |||
1501 | mp_result res; | |||
1502 | ||||
1503 | CHECK(a != NULL && b != NULL && c != NULL)((a != ((void*)0) && b != ((void*)0) && c != ( (void*)0)) ? (void) (0) : __assert_fail ("a != ((void*)0) && b != ((void*)0) && c != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1503, __PRETTY_FUNCTION__)); | |||
1504 | ||||
1505 | /* Since a * b = gcd(a, b) * lcm(a, b), we can compute | |||
1506 | lcm(a, b) = (a / gcd(a, b)) * b. | |||
1507 | ||||
1508 | This formulation insures everything works even if the input | |||
1509 | variables share space. | |||
1510 | */ | |||
1511 | if ((res = mp_int_init(&lcm)) != MP_OK) | |||
1512 | return res; | |||
1513 | if ((res = mp_int_gcd(a, b, &lcm)) != MP_OK) | |||
1514 | goto CLEANUP; | |||
1515 | if ((res = mp_int_div(a, &lcm, &lcm, NULL((void*)0))) != MP_OK) | |||
1516 | goto CLEANUP; | |||
1517 | if ((res = mp_int_mul(&lcm, b, &lcm)) != MP_OK) | |||
1518 | goto CLEANUP; | |||
1519 | ||||
1520 | res = mp_int_copy(&lcm, c); | |||
1521 | ||||
1522 | CLEANUP: | |||
1523 | mp_int_clear(&lcm); | |||
1524 | ||||
1525 | return res; | |||
1526 | } | |||
1527 | ||||
1528 | int mp_int_divisible_value(mp_int a, mp_small v) | |||
1529 | { | |||
1530 | mp_small rem = 0; | |||
1531 | ||||
1532 | if (mp_int_div_value(a, v, NULL((void*)0), &rem) != MP_OK) | |||
1533 | return 0; | |||
1534 | ||||
1535 | return rem == 0; | |||
1536 | } | |||
1537 | ||||
1538 | int mp_int_is_pow2(mp_int z) | |||
1539 | { | |||
1540 | CHECK(z != NULL)((z != ((void*)0)) ? (void) (0) : __assert_fail ("z != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1540, __PRETTY_FUNCTION__)); | |||
1541 | ||||
1542 | return s_isp2(z); | |||
1543 | } | |||
1544 | ||||
1545 | /* Implementation of Newton's root finding method, based loosely on a patch | |||
1546 | contributed by Hal Finkel <half@halssoftware.com> | |||
1547 | modified by M. J. Fromberger. | |||
1548 | */ | |||
1549 | mp_result mp_int_root(mp_int a, mp_small b, mp_int c) | |||
1550 | { | |||
1551 | mp_result res = MP_OK; | |||
1552 | int flips = 0; | |||
1553 | DECLARE_TEMP(5)mpz_t temp[(5)]; int last__ = 0; | |||
1554 | ||||
1555 | CHECK(a != NULL && c != NULL && b > 0)((a != ((void*)0) && c != ((void*)0) && b > 0) ? (void) (0) : __assert_fail ("a != ((void*)0) && c != ((void*)0) && b > 0" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1555, __PRETTY_FUNCTION__)); | |||
| ||||
1556 | ||||
1557 | if (b == 1) { | |||
1558 | return mp_int_copy(a, c); | |||
1559 | } | |||
1560 | if (MP_SIGN(a)((a)->sign) == MP_NEG) { | |||
1561 | if (b % 2 == 0) | |||
1562 | return MP_UNDEF; /* root does not exist for negative a with even b */ | |||
1563 | else | |||
1564 | flips = 1; | |||
1565 | } | |||
1566 | ||||
1567 | SETUP(mp_int_init_copy(LAST_TEMP(), a))do{ if ((res = (mp_int_init_copy((temp + (last__)), a))) != MP_OK ) goto CLEANUP; ++(last__); } while(0); | |||
1568 | SETUP(mp_int_init_copy(LAST_TEMP(), a))do{ if ((res = (mp_int_init_copy((temp + (last__)), a))) != MP_OK ) goto CLEANUP; ++(last__); } while(0); | |||
1569 | SETUP(mp_int_init(LAST_TEMP()))do{ if ((res = (mp_int_init((temp + (last__))))) != MP_OK) goto CLEANUP; ++(last__); } while(0); | |||
1570 | SETUP(mp_int_init(LAST_TEMP()))do{ if ((res = (mp_int_init((temp + (last__))))) != MP_OK) goto CLEANUP; ++(last__); } while(0); | |||
1571 | SETUP(mp_int_init(LAST_TEMP()))do{ if ((res = (mp_int_init((temp + (last__))))) != MP_OK) goto CLEANUP; ++(last__); } while(0); | |||
1572 | ||||
1573 | (void) mp_int_abs(TEMP(0)(temp + (0)), TEMP(0)(temp + (0))); | |||
1574 | (void) mp_int_abs(TEMP(1)(temp + (1)), TEMP(1)(temp + (1))); | |||
1575 | ||||
1576 | for (;;) { | |||
1577 | if ((res = mp_int_expt(TEMP(1)(temp + (1)), b, TEMP(2)(temp + (2)))) != MP_OK) | |||
1578 | goto CLEANUP; | |||
1579 | ||||
1580 | if (mp_int_compare_unsigned(TEMP(2)(temp + (2)), TEMP(0)(temp + (0))) <= 0) | |||
1581 | break; | |||
1582 | ||||
1583 | if ((res = mp_int_sub(TEMP(2)(temp + (2)), TEMP(0)(temp + (0)), TEMP(2)(temp + (2)))) != MP_OK) | |||
1584 | goto CLEANUP; | |||
1585 | if ((res = mp_int_expt(TEMP(1)(temp + (1)), b - 1, TEMP(3)(temp + (3)))) != MP_OK) | |||
1586 | goto CLEANUP; | |||
1587 | if ((res = mp_int_mul_value(TEMP(3)(temp + (3)), b, TEMP(3)(temp + (3)))) != MP_OK) | |||
1588 | goto CLEANUP; | |||
1589 | if ((res = mp_int_div(TEMP(2)(temp + (2)), TEMP(3)(temp + (3)), TEMP(4)(temp + (4)), NULL((void*)0))) != MP_OK) | |||
1590 | goto CLEANUP; | |||
1591 | if ((res = mp_int_sub(TEMP(1)(temp + (1)), TEMP(4)(temp + (4)), TEMP(4)(temp + (4)))) != MP_OK) | |||
1592 | goto CLEANUP; | |||
1593 | ||||
1594 | if (mp_int_compare_unsigned(TEMP(1)(temp + (1)), TEMP(4)(temp + (4))) == 0) { | |||
1595 | if ((res = mp_int_sub_value(TEMP(4)(temp + (4)), 1, TEMP(4)(temp + (4)))) != MP_OK) | |||
1596 | goto CLEANUP; | |||
1597 | } | |||
1598 | if ((res = mp_int_copy(TEMP(4)(temp + (4)), TEMP(1)(temp + (1)))) != MP_OK) | |||
1599 | goto CLEANUP; | |||
1600 | } | |||
1601 | ||||
1602 | if ((res = mp_int_copy(TEMP(1)(temp + (1)), c)) != MP_OK) | |||
1603 | goto CLEANUP; | |||
1604 | ||||
1605 | /* If the original value of a was negative, flip the output sign. */ | |||
1606 | if (flips) | |||
1607 | (void) mp_int_neg(c, c); /* cannot fail */ | |||
1608 | ||||
1609 | CLEANUP_TEMP()CLEANUP: while (--last__ >= 0) mp_int_clear((temp + (last__ ))); | |||
1610 | return res; | |||
1611 | } | |||
1612 | ||||
1613 | mp_result mp_int_to_int(mp_int z, mp_small *out) | |||
1614 | { | |||
1615 | mp_usmall uv = 0; | |||
1616 | mp_size uz; | |||
1617 | mp_digit *dz; | |||
1618 | mp_sign sz; | |||
1619 | ||||
1620 | CHECK(z != NULL)((z != ((void*)0)) ? (void) (0) : __assert_fail ("z != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1620, __PRETTY_FUNCTION__)); | |||
1621 | ||||
1622 | /* Make sure the value is representable as a small integer */ | |||
1623 | sz = MP_SIGN(z)((z)->sign); | |||
1624 | if ((sz == MP_ZPOS && mp_int_compare_value(z, MP_SMALL_MAX9223372036854775807L) > 0) || | |||
1625 | mp_int_compare_value(z, MP_SMALL_MIN(-9223372036854775807L -1L)) < 0) | |||
1626 | return MP_RANGE; | |||
1627 | ||||
1628 | uz = MP_USED(z)((z)->used); | |||
1629 | dz = MP_DIGITS(z)((z)->digits) + uz - 1; | |||
1630 | ||||
1631 | while (uz > 0) { | |||
1632 | uv <<= MP_DIGIT_BIT(sizeof(mp_digit) * 8)/2; | |||
1633 | uv = (uv << (MP_DIGIT_BIT(sizeof(mp_digit) * 8)/2)) | *dz--; | |||
1634 | --uz; | |||
1635 | } | |||
1636 | ||||
1637 | if (out) | |||
1638 | *out = (mp_small)((sz == MP_NEG) ? -uv : uv); | |||
1639 | ||||
1640 | return MP_OK; | |||
1641 | } | |||
1642 | ||||
1643 | mp_result mp_int_to_uint(mp_int z, mp_usmall *out) | |||
1644 | { | |||
1645 | mp_usmall uv = 0; | |||
1646 | mp_size uz; | |||
1647 | mp_digit *dz; | |||
1648 | mp_sign sz; | |||
1649 | ||||
1650 | CHECK(z != NULL)((z != ((void*)0)) ? (void) (0) : __assert_fail ("z != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1650, __PRETTY_FUNCTION__)); | |||
1651 | ||||
1652 | /* Make sure the value is representable as an unsigned small integer */ | |||
1653 | sz = MP_SIGN(z)((z)->sign); | |||
1654 | if (sz == MP_NEG || mp_int_compare_uvalue(z, MP_USMALL_MAX(9223372036854775807L *2UL+1UL)) > 0) | |||
1655 | return MP_RANGE; | |||
1656 | ||||
1657 | uz = MP_USED(z)((z)->used); | |||
1658 | dz = MP_DIGITS(z)((z)->digits) + uz - 1; | |||
1659 | ||||
1660 | while (uz > 0) { | |||
1661 | uv <<= MP_DIGIT_BIT(sizeof(mp_digit) * 8)/2; | |||
1662 | uv = (uv << (MP_DIGIT_BIT(sizeof(mp_digit) * 8)/2)) | *dz--; | |||
1663 | --uz; | |||
1664 | } | |||
1665 | ||||
1666 | if (out) | |||
1667 | *out = uv; | |||
1668 | ||||
1669 | return MP_OK; | |||
1670 | } | |||
1671 | ||||
1672 | mp_result mp_int_to_string(mp_int z, mp_size radix, | |||
1673 | char *str, int limit) | |||
1674 | { | |||
1675 | mp_result res; | |||
1676 | int cmp = 0; | |||
1677 | ||||
1678 | CHECK(z != NULL && str != NULL && limit >= 2)((z != ((void*)0) && str != ((void*)0) && limit >= 2) ? (void) (0) : __assert_fail ("z != ((void*)0) && str != ((void*)0) && limit >= 2" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1678, __PRETTY_FUNCTION__)); | |||
1679 | ||||
1680 | if (radix < MP_MIN_RADIX2 || radix > MP_MAX_RADIX36) | |||
1681 | return MP_RANGE; | |||
1682 | ||||
1683 | if (CMPZ(z)(((z)->used==1&&(z)->digits[0]==0)?0:((z)->sign ==MP_NEG)?-1:1) == 0) { | |||
1684 | *str++ = s_val2ch(0, 1); | |||
1685 | } | |||
1686 | else { | |||
1687 | mpz_t tmp; | |||
1688 | char *h, *t; | |||
1689 | ||||
1690 | if ((res = mp_int_init_copy(&tmp, z)) != MP_OK) | |||
1691 | return res; | |||
1692 | ||||
1693 | if (MP_SIGN(z)((z)->sign) == MP_NEG) { | |||
1694 | *str++ = '-'; | |||
1695 | --limit; | |||
1696 | } | |||
1697 | h = str; | |||
1698 | ||||
1699 | /* Generate digits in reverse order until finished or limit reached */ | |||
1700 | for (/* */; limit > 0; --limit) { | |||
1701 | mp_digit d; | |||
1702 | ||||
1703 | if ((cmp = CMPZ(&tmp)(((&tmp)->used==1&&(&tmp)->digits[0]==0 )?0:((&tmp)->sign==MP_NEG)?-1:1)) == 0) | |||
1704 | break; | |||
1705 | ||||
1706 | d = s_ddiv(&tmp, (mp_digit)radix); | |||
1707 | *str++ = s_val2ch(d, 1); | |||
1708 | } | |||
1709 | t = str - 1; | |||
1710 | ||||
1711 | /* Put digits back in correct output order */ | |||
1712 | while (h < t) { | |||
1713 | char tc = *h; | |||
1714 | *h++ = *t; | |||
1715 | *t-- = tc; | |||
1716 | } | |||
1717 | ||||
1718 | mp_int_clear(&tmp); | |||
1719 | } | |||
1720 | ||||
1721 | *str = '\0'; | |||
1722 | if (cmp == 0) | |||
1723 | return MP_OK; | |||
1724 | else | |||
1725 | return MP_TRUNC; | |||
1726 | } | |||
1727 | ||||
1728 | mp_result mp_int_string_len(mp_int z, mp_size radix) | |||
1729 | { | |||
1730 | int len; | |||
1731 | ||||
1732 | CHECK(z != NULL)((z != ((void*)0)) ? (void) (0) : __assert_fail ("z != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1732, __PRETTY_FUNCTION__)); | |||
1733 | ||||
1734 | if (radix < MP_MIN_RADIX2 || radix > MP_MAX_RADIX36) | |||
1735 | return MP_RANGE; | |||
1736 | ||||
1737 | len = s_outlen(z, radix) + 1; /* for terminator */ | |||
1738 | ||||
1739 | /* Allow for sign marker on negatives */ | |||
1740 | if (MP_SIGN(z)((z)->sign) == MP_NEG) | |||
1741 | len += 1; | |||
1742 | ||||
1743 | return len; | |||
1744 | } | |||
1745 | ||||
1746 | /* Read zero-terminated string into z */ | |||
1747 | mp_result mp_int_read_string(mp_int z, mp_size radix, const char *str) | |||
1748 | { | |||
1749 | return mp_int_read_cstring(z, radix, str, NULL((void*)0)); | |||
1750 | } | |||
1751 | ||||
1752 | mp_result mp_int_read_cstring(mp_int z, mp_size radix, const char *str, char **end) | |||
1753 | { | |||
1754 | int ch; | |||
1755 | ||||
1756 | CHECK(z != NULL && str != NULL)((z != ((void*)0) && str != ((void*)0)) ? (void) (0) : __assert_fail ("z != ((void*)0) && str != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1756, __PRETTY_FUNCTION__)); | |||
1757 | ||||
1758 | if (radix < MP_MIN_RADIX2 || radix > MP_MAX_RADIX36) | |||
1759 | return MP_RANGE; | |||
1760 | ||||
1761 | /* Skip leading whitespace */ | |||
1762 | while (isspace((int)*str)((*__ctype_b_loc ())[(int) (((int)*str))] & (unsigned short int) _ISspace)) | |||
1763 | ++str; | |||
1764 | ||||
1765 | /* Handle leading sign tag (+/-, positive default) */ | |||
1766 | switch (*str) { | |||
1767 | case '-': | |||
1768 | MP_SIGN(z)((z)->sign) = MP_NEG; | |||
1769 | ++str; | |||
1770 | break; | |||
1771 | case '+': | |||
1772 | ++str; /* fallthrough */ | |||
1773 | default: | |||
1774 | MP_SIGN(z)((z)->sign) = MP_ZPOS; | |||
1775 | break; | |||
1776 | } | |||
1777 | ||||
1778 | /* Skip leading zeroes */ | |||
1779 | while ((ch = s_ch2val(*str, radix)) == 0) | |||
1780 | ++str; | |||
1781 | ||||
1782 | /* Make sure there is enough space for the value */ | |||
1783 | if (!s_pad(z, s_inlen(strlen(str), radix))) | |||
1784 | return MP_MEMORY; | |||
1785 | ||||
1786 | MP_USED(z)((z)->used) = 1; z->digits[0] = 0; | |||
1787 | ||||
1788 | while (*str != '\0' && ((ch = s_ch2val(*str, radix)) >= 0)) { | |||
1789 | s_dmul(z, (mp_digit)radix); | |||
1790 | s_dadd(z, (mp_digit)ch); | |||
1791 | ++str; | |||
1792 | } | |||
1793 | ||||
1794 | CLAMP(z)do{ mp_int z_ = (z); mp_size uz_ = ((z_)->used); mp_digit * dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0); | |||
1795 | ||||
1796 | /* Override sign for zero, even if negative specified. */ | |||
1797 | if (CMPZ(z)(((z)->used==1&&(z)->digits[0]==0)?0:((z)->sign ==MP_NEG)?-1:1) == 0) | |||
1798 | MP_SIGN(z)((z)->sign) = MP_ZPOS; | |||
1799 | ||||
1800 | if (end != NULL((void*)0)) | |||
1801 | *end = (char *)str; | |||
1802 | ||||
1803 | /* Return a truncation error if the string has unprocessed characters | |||
1804 | remaining, so the caller can tell if the whole string was done */ | |||
1805 | if (*str != '\0') | |||
1806 | return MP_TRUNC; | |||
1807 | else | |||
1808 | return MP_OK; | |||
1809 | } | |||
1810 | ||||
1811 | mp_result mp_int_count_bits(mp_int z) | |||
1812 | { | |||
1813 | mp_size nbits = 0, uz; | |||
1814 | mp_digit d; | |||
1815 | ||||
1816 | CHECK(z != NULL)((z != ((void*)0)) ? (void) (0) : __assert_fail ("z != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1816, __PRETTY_FUNCTION__)); | |||
1817 | ||||
1818 | uz = MP_USED(z)((z)->used); | |||
1819 | if (uz == 1 && z->digits[0] == 0) | |||
1820 | return 1; | |||
1821 | ||||
1822 | --uz; | |||
1823 | nbits = uz * MP_DIGIT_BIT(sizeof(mp_digit) * 8); | |||
1824 | d = z->digits[uz]; | |||
1825 | ||||
1826 | while (d != 0) { | |||
1827 | d >>= 1; | |||
1828 | ++nbits; | |||
1829 | } | |||
1830 | ||||
1831 | return nbits; | |||
1832 | } | |||
1833 | ||||
1834 | mp_result mp_int_to_binary(mp_int z, unsigned char *buf, int limit) | |||
1835 | { | |||
1836 | static const int PAD_FOR_2C = 1; | |||
1837 | ||||
1838 | mp_result res; | |||
1839 | int limpos = limit; | |||
1840 | ||||
1841 | CHECK(z != NULL && buf != NULL)((z != ((void*)0) && buf != ((void*)0)) ? (void) (0) : __assert_fail ("z != ((void*)0) && buf != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1841, __PRETTY_FUNCTION__)); | |||
1842 | ||||
1843 | res = s_tobin(z, buf, &limpos, PAD_FOR_2C); | |||
1844 | ||||
1845 | if (MP_SIGN(z)((z)->sign) == MP_NEG) | |||
1846 | s_2comp(buf, limpos); | |||
1847 | ||||
1848 | return res; | |||
1849 | } | |||
1850 | ||||
1851 | mp_result mp_int_read_binary(mp_int z, unsigned char *buf, int len) | |||
1852 | { | |||
1853 | mp_size need, i; | |||
1854 | unsigned char *tmp; | |||
1855 | mp_digit *dz; | |||
1856 | ||||
1857 | CHECK(z != NULL && buf != NULL && len > 0)((z != ((void*)0) && buf != ((void*)0) && len > 0) ? (void) (0) : __assert_fail ("z != ((void*)0) && buf != ((void*)0) && len > 0" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1857, __PRETTY_FUNCTION__)); | |||
1858 | ||||
1859 | /* Figure out how many digits are needed to represent this value */ | |||
1860 | need = ((len * CHAR_BIT8) + (MP_DIGIT_BIT(sizeof(mp_digit) * 8) - 1)) / MP_DIGIT_BIT(sizeof(mp_digit) * 8); | |||
1861 | if (!s_pad(z, need)) | |||
1862 | return MP_MEMORY; | |||
1863 | ||||
1864 | mp_int_zero(z); | |||
1865 | ||||
1866 | /* If the high-order bit is set, take the 2's complement before reading the | |||
1867 | value (it will be restored afterward) */ | |||
1868 | if (buf[0] >> (CHAR_BIT8 - 1)) { | |||
1869 | MP_SIGN(z)((z)->sign) = MP_NEG; | |||
1870 | s_2comp(buf, len); | |||
1871 | } | |||
1872 | ||||
1873 | dz = MP_DIGITS(z)((z)->digits); | |||
1874 | for (tmp = buf, i = len; i > 0; --i, ++tmp) { | |||
1875 | s_qmul(z, (mp_size) CHAR_BIT8); | |||
1876 | *dz |= *tmp; | |||
1877 | } | |||
1878 | ||||
1879 | /* Restore 2's complement if we took it before */ | |||
1880 | if (MP_SIGN(z)((z)->sign) == MP_NEG) | |||
1881 | s_2comp(buf, len); | |||
1882 | ||||
1883 | return MP_OK; | |||
1884 | } | |||
1885 | ||||
1886 | mp_result mp_int_binary_len(mp_int z) | |||
1887 | { | |||
1888 | mp_result res = mp_int_count_bits(z); | |||
1889 | int bytes = mp_int_unsigned_len(z); | |||
1890 | ||||
1891 | if (res <= 0) | |||
1892 | return res; | |||
1893 | ||||
1894 | bytes = (res + (CHAR_BIT8 - 1)) / CHAR_BIT8; | |||
1895 | ||||
1896 | /* If the highest-order bit falls exactly on a byte boundary, we need to pad | |||
1897 | with an extra byte so that the sign will be read correctly when reading it | |||
1898 | back in. */ | |||
1899 | if (bytes * CHAR_BIT8 == res) | |||
1900 | ++bytes; | |||
1901 | ||||
1902 | return bytes; | |||
1903 | } | |||
1904 | ||||
1905 | mp_result mp_int_to_unsigned(mp_int z, unsigned char *buf, int limit) | |||
1906 | { | |||
1907 | static const int NO_PADDING = 0; | |||
1908 | ||||
1909 | CHECK(z != NULL && buf != NULL)((z != ((void*)0) && buf != ((void*)0)) ? (void) (0) : __assert_fail ("z != ((void*)0) && buf != ((void*)0)" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1909, __PRETTY_FUNCTION__)); | |||
1910 | ||||
1911 | return s_tobin(z, buf, &limit, NO_PADDING); | |||
1912 | } | |||
1913 | ||||
1914 | mp_result mp_int_read_unsigned(mp_int z, unsigned char *buf, int len) | |||
1915 | { | |||
1916 | mp_size need, i; | |||
1917 | unsigned char *tmp; | |||
1918 | ||||
1919 | CHECK(z != NULL && buf != NULL && len > 0)((z != ((void*)0) && buf != ((void*)0) && len > 0) ? (void) (0) : __assert_fail ("z != ((void*)0) && buf != ((void*)0) && len > 0" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1919, __PRETTY_FUNCTION__)); | |||
1920 | ||||
1921 | /* Figure out how many digits are needed to represent this value */ | |||
1922 | need = ((len * CHAR_BIT8) + (MP_DIGIT_BIT(sizeof(mp_digit) * 8) - 1)) / MP_DIGIT_BIT(sizeof(mp_digit) * 8); | |||
1923 | if (!s_pad(z, need)) | |||
1924 | return MP_MEMORY; | |||
1925 | ||||
1926 | mp_int_zero(z); | |||
1927 | ||||
1928 | for (tmp = buf, i = len; i > 0; --i, ++tmp) { | |||
1929 | (void) s_qmul(z, CHAR_BIT8); | |||
1930 | *MP_DIGITS(z)((z)->digits) |= *tmp; | |||
1931 | } | |||
1932 | ||||
1933 | return MP_OK; | |||
1934 | } | |||
1935 | ||||
1936 | mp_result mp_int_unsigned_len(mp_int z) | |||
1937 | { | |||
1938 | mp_result res = mp_int_count_bits(z); | |||
1939 | int bytes; | |||
1940 | ||||
1941 | if (res <= 0) | |||
1942 | return res; | |||
1943 | ||||
1944 | bytes = (res + (CHAR_BIT8 - 1)) / CHAR_BIT8; | |||
1945 | ||||
1946 | return bytes; | |||
1947 | } | |||
1948 | ||||
1949 | const char *mp_error_string(mp_result res) | |||
1950 | { | |||
1951 | int ix; | |||
1952 | if (res > 0) | |||
1953 | return s_unknown_err; | |||
1954 | ||||
1955 | res = -res; | |||
1956 | for (ix = 0; ix < res && s_error_msg[ix] != NULL((void*)0); ++ix) | |||
1957 | ; | |||
1958 | ||||
1959 | if (s_error_msg[ix] != NULL((void*)0)) | |||
1960 | return s_error_msg[ix]; | |||
1961 | else | |||
1962 | return s_unknown_err; | |||
1963 | } | |||
1964 | ||||
1965 | /*------------------------------------------------------------------------*/ | |||
1966 | /* Private functions for internal use. These make assumptions. */ | |||
1967 | ||||
1968 | STATICstatic mp_digit *s_alloc(mp_size num) | |||
1969 | { | |||
1970 | mp_digit *out = malloc(num * sizeof(mp_digit)); | |||
1971 | ||||
1972 | assert(out != NULL)((out != ((void*)0)) ? (void) (0) : __assert_fail ("out != NULL" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1972, __PRETTY_FUNCTION__)); /* for debugging */ | |||
1973 | #if DEBUG > 1 | |||
1974 | { | |||
1975 | mp_digit v = (mp_digit) 0xdeadbeef; | |||
1976 | int ix; | |||
1977 | ||||
1978 | for (ix = 0; ix < num; ++ix) | |||
1979 | out[ix] = v; | |||
1980 | } | |||
1981 | #endif | |||
1982 | ||||
1983 | return out; | |||
1984 | } | |||
1985 | ||||
1986 | STATICstatic mp_digit *s_realloc(mp_digit *old, mp_size osize, mp_size nsize) | |||
1987 | { | |||
1988 | #if DEBUG > 1 | |||
1989 | mp_digit *new = s_alloc(nsize); | |||
1990 | int ix; | |||
1991 | ||||
1992 | for (ix = 0; ix < nsize; ++ix) | |||
1993 | new[ix] = (mp_digit) 0xdeadbeef; | |||
1994 | ||||
1995 | memcpy(new, old, osize * sizeof(mp_digit)); | |||
1996 | #else | |||
1997 | mp_digit *new = realloc(old, nsize * sizeof(mp_digit)); | |||
1998 | ||||
1999 | assert(new != NULL)((new != ((void*)0)) ? (void) (0) : __assert_fail ("new != NULL" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 1999, __PRETTY_FUNCTION__)); /* for debugging */ | |||
2000 | #endif | |||
2001 | return new; | |||
2002 | } | |||
2003 | ||||
2004 | STATICstatic void s_free(void *ptr) | |||
2005 | { | |||
2006 | free(ptr); | |||
2007 | } | |||
2008 | ||||
2009 | STATICstatic int s_pad(mp_int z, mp_size min) | |||
2010 | { | |||
2011 | if (MP_ALLOC(z)((z)->alloc) < min) { | |||
2012 | mp_size nsize = ROUND_PREC(min)((mp_size)(2*(((min)+1)/2))); | |||
2013 | mp_digit *tmp; | |||
2014 | ||||
2015 | if ((void *)z->digits == (void *)z) { | |||
2016 | if ((tmp = s_alloc(nsize)) == NULL((void*)0)) | |||
2017 | return 0; | |||
2018 | ||||
2019 | COPY(MP_DIGITS(z), tmp, MP_USED(z))do{ mp_size i__ = (((z)->used)) * sizeof(mp_digit); mp_digit *p__ = (((z)->digits)), *q__ = (tmp); memcpy(q__, p__, i__ ); } while(0); | |||
2020 | } | |||
2021 | else if ((tmp = s_realloc(MP_DIGITS(z)((z)->digits), MP_ALLOC(z)((z)->alloc), nsize)) == NULL((void*)0)) | |||
2022 | return 0; | |||
2023 | ||||
2024 | MP_DIGITS(z)((z)->digits) = tmp; | |||
2025 | MP_ALLOC(z)((z)->alloc) = nsize; | |||
2026 | } | |||
2027 | ||||
2028 | return 1; | |||
2029 | } | |||
2030 | ||||
2031 | /* Note: This will not work correctly when value == MP_SMALL_MIN */ | |||
2032 | STATICstatic void s_fake(mp_int z, mp_small value, mp_digit vbuf[]) | |||
2033 | { | |||
2034 | mp_usmall uv = (mp_usmall) (value < 0) ? -value : value; | |||
2035 | s_ufake(z, uv, vbuf); | |||
2036 | if (value < 0) | |||
2037 | z->sign = MP_NEG; | |||
2038 | } | |||
2039 | ||||
2040 | STATICstatic void s_ufake(mp_int z, mp_usmall value, mp_digit vbuf[]) | |||
2041 | { | |||
2042 | mp_size ndig = (mp_size) s_uvpack(value, vbuf); | |||
2043 | ||||
2044 | z->used = ndig; | |||
2045 | z->alloc = MP_VALUE_DIGITS(value)((sizeof(value)+(sizeof(mp_digit)-1))/sizeof(mp_digit)); | |||
2046 | z->sign = MP_ZPOS; | |||
2047 | z->digits = vbuf; | |||
2048 | } | |||
2049 | ||||
2050 | STATICstatic int s_cdig(mp_digit *da, mp_digit *db, mp_size len) | |||
2051 | { | |||
2052 | mp_digit *dat = da + len - 1, *dbt = db + len - 1; | |||
2053 | ||||
2054 | for (/* */; len != 0; --len, --dat, --dbt) { | |||
2055 | if (*dat > *dbt) | |||
2056 | return 1; | |||
2057 | else if (*dat < *dbt) | |||
2058 | return -1; | |||
2059 | } | |||
2060 | ||||
2061 | return 0; | |||
2062 | } | |||
2063 | ||||
2064 | STATICstatic int s_uvpack(mp_usmall uv, mp_digit t[]) | |||
2065 | { | |||
2066 | int ndig = 0; | |||
2067 | ||||
2068 | if (uv == 0) | |||
2069 | t[ndig++] = 0; | |||
2070 | else { | |||
2071 | while (uv != 0) { | |||
2072 | t[ndig++] = (mp_digit) uv; | |||
2073 | uv >>= MP_DIGIT_BIT(sizeof(mp_digit) * 8)/2; | |||
2074 | uv >>= MP_DIGIT_BIT(sizeof(mp_digit) * 8)/2; | |||
2075 | } | |||
2076 | } | |||
2077 | ||||
2078 | return ndig; | |||
2079 | } | |||
2080 | ||||
2081 | STATICstatic int s_ucmp(mp_int a, mp_int b) | |||
2082 | { | |||
2083 | mp_size ua = MP_USED(a)((a)->used), ub = MP_USED(b)((b)->used); | |||
2084 | ||||
2085 | if (ua > ub) | |||
2086 | return 1; | |||
2087 | else if (ub > ua) | |||
2088 | return -1; | |||
2089 | else | |||
2090 | return s_cdig(MP_DIGITS(a)((a)->digits), MP_DIGITS(b)((b)->digits), ua); | |||
2091 | } | |||
2092 | ||||
2093 | STATICstatic int s_vcmp(mp_int a, mp_small v) | |||
2094 | { | |||
2095 | mp_usmall uv = (v < 0) ? -(mp_usmall) v : (mp_usmall) v; | |||
2096 | return s_uvcmp(a, uv); | |||
2097 | } | |||
2098 | ||||
2099 | STATICstatic int s_uvcmp(mp_int a, mp_usmall uv) | |||
2100 | { | |||
2101 | mpz_t vtmp; | |||
2102 | mp_digit vdig[MP_VALUE_DIGITS(uv)((sizeof(uv)+(sizeof(mp_digit)-1))/sizeof(mp_digit))]; | |||
2103 | ||||
2104 | s_ufake(&vtmp, uv, vdig); | |||
2105 | return s_ucmp(a, &vtmp); | |||
2106 | } | |||
2107 | ||||
2108 | STATICstatic mp_digit s_uadd(mp_digit *da, mp_digit *db, mp_digit *dc, | |||
2109 | mp_size size_a, mp_size size_b) | |||
2110 | { | |||
2111 | mp_size pos; | |||
2112 | mp_word w = 0; | |||
2113 | ||||
2114 | /* Insure that da is the longer of the two to simplify later code */ | |||
2115 | if (size_b
| |||
2116 | SWAP(mp_digit *, da, db)do{ mp_digit * t_ = (da); da = (db); db = t_; } while(0); | |||
2117 | SWAP(mp_size, size_a, size_b)do{ mp_size t_ = (size_a); size_a = (size_b); size_b = t_; } while (0); | |||
2118 | } | |||
2119 | ||||
2120 | /* Add corresponding digits until the shorter number runs out */ | |||
2121 | for (pos = 0; pos < size_b; ++pos, ++da, ++db, ++dc) { | |||
2122 | w = w + (mp_word) *da + (mp_word) *db; | |||
2123 | *dc = LOWER_HALF(w)((mp_digit)(w)); | |||
2124 | w = UPPER_HALF(w)((mp_word)((w) >> (sizeof(mp_digit) * 8))); | |||
2125 | } | |||
2126 | ||||
2127 | /* Propagate carries as far as necessary */ | |||
2128 | for (/* */; pos
| |||
2129 | w = w + *da; | |||
2130 | ||||
2131 | *dc = LOWER_HALF(w)((mp_digit)(w)); | |||
| ||||
2132 | w = UPPER_HALF(w)((mp_word)((w) >> (sizeof(mp_digit) * 8))); | |||
2133 | } | |||
2134 | ||||
2135 | /* Return carry out */ | |||
2136 | return (mp_digit)w; | |||
2137 | } | |||
2138 | ||||
2139 | STATICstatic void s_usub(mp_digit *da, mp_digit *db, mp_digit *dc, | |||
2140 | mp_size size_a, mp_size size_b) | |||
2141 | { | |||
2142 | mp_size pos; | |||
2143 | mp_word w = 0; | |||
2144 | ||||
2145 | /* We assume that |a| >= |b| so this should definitely hold */ | |||
2146 | assert(size_a >= size_b)((size_a >= size_b) ? (void) (0) : __assert_fail ("size_a >= size_b" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 2146, __PRETTY_FUNCTION__)); | |||
2147 | ||||
2148 | /* Subtract corresponding digits and propagate borrow */ | |||
2149 | for (pos = 0; pos < size_b; ++pos, ++da, ++db, ++dc) { | |||
2150 | w = ((mp_word)MP_DIGIT_MAX((4294967295U) * 1UL) + 1 + /* MP_RADIX */ | |||
2151 | (mp_word)*da) - w - (mp_word)*db; | |||
2152 | ||||
2153 | *dc = LOWER_HALF(w)((mp_digit)(w)); | |||
2154 | w = (UPPER_HALF(w)((mp_word)((w) >> (sizeof(mp_digit) * 8))) == 0); | |||
2155 | } | |||
2156 | ||||
2157 | /* Finish the subtraction for remaining upper digits of da */ | |||
2158 | for (/* */; pos < size_a; ++pos, ++da, ++dc) { | |||
2159 | w = ((mp_word)MP_DIGIT_MAX((4294967295U) * 1UL) + 1 + /* MP_RADIX */ | |||
2160 | (mp_word)*da) - w; | |||
2161 | ||||
2162 | *dc = LOWER_HALF(w)((mp_digit)(w)); | |||
2163 | w = (UPPER_HALF(w)((mp_word)((w) >> (sizeof(mp_digit) * 8))) == 0); | |||
2164 | } | |||
2165 | ||||
2166 | /* If there is a borrow out at the end, it violates the precondition */ | |||
2167 | assert(w == 0)((w == 0) ? (void) (0) : __assert_fail ("w == 0", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 2167, __PRETTY_FUNCTION__)); | |||
2168 | } | |||
2169 | ||||
2170 | STATICstatic int s_kmul(mp_digit *da, mp_digit *db, mp_digit *dc, | |||
2171 | mp_size size_a, mp_size size_b) | |||
2172 | { | |||
2173 | mp_size bot_size; | |||
2174 | ||||
2175 | /* Make sure b is the smaller of the two input values */ | |||
2176 | if (size_b
| |||
2177 | SWAP(mp_digit *, da, db)do{ mp_digit * t_ = (da); da = (db); db = t_; } while(0); | |||
2178 | SWAP(mp_size, size_a, size_b)do{ mp_size t_ = (size_a); size_a = (size_b); size_b = t_; } while (0); | |||
2179 | } | |||
2180 | ||||
2181 | /* Insure that the bottom is the larger half in an odd-length split; the code | |||
2182 | below relies on this being true. | |||
2183 | */ | |||
2184 | bot_size = (size_a + 1) / 2; | |||
2185 | ||||
2186 | /* If the values are big enough to bother with recursion, use the Karatsuba | |||
2187 | algorithm to compute the product; otherwise use the normal multiplication | |||
2188 | algorithm | |||
2189 | */ | |||
2190 | if (multiply_threshold
| |||
2191 | size_a >= multiply_threshold && | |||
2192 | size_b > bot_size) { | |||
2193 | ||||
2194 | mp_digit *t1, *t2, *t3, carry; | |||
2195 | ||||
2196 | mp_digit *a_top = da + bot_size; | |||
2197 | mp_digit *b_top = db + bot_size; | |||
2198 | ||||
2199 | mp_size at_size = size_a - bot_size; | |||
2200 | mp_size bt_size = size_b - bot_size; | |||
2201 | mp_size buf_size = 2 * bot_size; | |||
2202 | ||||
2203 | /* Do a single allocation for all three temporary buffers needed; each | |||
2204 | buffer must be big enough to hold the product of two bottom halves, and | |||
2205 | one buffer needs space for the completed product; twice the space is | |||
2206 | plenty. | |||
2207 | */ | |||
2208 | if ((t1 = s_alloc(4 * buf_size)) == NULL((void*)0)) return 0; | |||
2209 | t2 = t1 + buf_size; | |||
2210 | t3 = t2 + buf_size; | |||
2211 | ZERO(t1, 4 * buf_size)do{ mp_size i__ = (4 * buf_size) * sizeof(mp_digit); mp_digit *p__ = (t1); memset(p__, 0, i__); } while(0); | |||
2212 | ||||
2213 | /* t1 and t2 are initially used as temporaries to compute the inner product | |||
2214 | (a1 + a0)(b1 + b0) = a1b1 + a1b0 + a0b1 + a0b0 | |||
2215 | */ | |||
2216 | carry = s_uadd(da, a_top, t1, bot_size, at_size); /* t1 = a1 + a0 */ | |||
2217 | t1[bot_size] = carry; | |||
2218 | ||||
2219 | carry = s_uadd(db, b_top, t2, bot_size, bt_size); /* t2 = b1 + b0 */ | |||
2220 | t2[bot_size] = carry; | |||
2221 | ||||
2222 | (void) s_kmul(t1, t2, t3, bot_size + 1, bot_size + 1); /* t3 = t1 * t2 */ | |||
2223 | ||||
2224 | /* Now we'll get t1 = a0b0 and t2 = a1b1, and subtract them out so that | |||
2225 | we're left with only the pieces we want: t3 = a1b0 + a0b1 | |||
2226 | */ | |||
2227 | ZERO(t1, buf_size)do{ mp_size i__ = (buf_size) * sizeof(mp_digit); mp_digit *p__ = (t1); memset(p__, 0, i__); } while(0); | |||
2228 | ZERO(t2, buf_size)do{ mp_size i__ = (buf_size) * sizeof(mp_digit); mp_digit *p__ = (t2); memset(p__, 0, i__); } while(0); | |||
2229 | (void) s_kmul(da, db, t1, bot_size, bot_size); /* t1 = a0 * b0 */ | |||
2230 | (void) s_kmul(a_top, b_top, t2, at_size, bt_size); /* t2 = a1 * b1 */ | |||
2231 | ||||
2232 | /* Subtract out t1 and t2 to get the inner product */ | |||
2233 | s_usub(t3, t1, t3, buf_size + 2, buf_size); | |||
2234 | s_usub(t3, t2, t3, buf_size + 2, buf_size); | |||
2235 | ||||
2236 | /* Assemble the output value */ | |||
2237 | COPY(t1, dc, buf_size)do{ mp_size i__ = (buf_size) * sizeof(mp_digit); mp_digit *p__ = (t1), *q__ = (dc); memcpy(q__, p__, i__); } while(0); | |||
2238 | carry = s_uadd(t3, dc + bot_size, dc + bot_size, | |||
2239 | buf_size + 1, buf_size); | |||
2240 | assert(carry == 0)((carry == 0) ? (void) (0) : __assert_fail ("carry == 0", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 2240, __PRETTY_FUNCTION__)); | |||
2241 | ||||
2242 | carry = s_uadd(t2, dc + 2*bot_size, dc + 2*bot_size, | |||
2243 | buf_size, buf_size); | |||
2244 | assert(carry == 0)((carry == 0) ? (void) (0) : __assert_fail ("carry == 0", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 2244, __PRETTY_FUNCTION__)); | |||
2245 | ||||
2246 | s_free(t1); /* note t2 and t3 are just internal pointers to t1 */ | |||
2247 | } | |||
2248 | else { | |||
2249 | s_umul(da, db, dc, size_a, size_b); | |||
2250 | } | |||
2251 | ||||
2252 | return 1; | |||
2253 | } | |||
2254 | ||||
2255 | STATICstatic void s_umul(mp_digit *da, mp_digit *db, mp_digit *dc, | |||
2256 | mp_size size_a, mp_size size_b) | |||
2257 | { | |||
2258 | mp_size a, b; | |||
2259 | mp_word w; | |||
2260 | ||||
2261 | for (a = 0; a < size_a; ++a, ++dc, ++da) { | |||
2262 | mp_digit *dct = dc; | |||
2263 | mp_digit *dbt = db; | |||
2264 | ||||
2265 | if (*da == 0) | |||
2266 | continue; | |||
2267 | ||||
2268 | w = 0; | |||
2269 | for (b = 0; b < size_b; ++b, ++dbt, ++dct) { | |||
2270 | w = (mp_word)*da * (mp_word)*dbt + w + (mp_word)*dct; | |||
2271 | ||||
2272 | *dct = LOWER_HALF(w)((mp_digit)(w)); | |||
2273 | w = UPPER_HALF(w)((mp_word)((w) >> (sizeof(mp_digit) * 8))); | |||
2274 | } | |||
2275 | ||||
2276 | *dct = (mp_digit)w; | |||
2277 | } | |||
2278 | } | |||
2279 | ||||
2280 | STATICstatic int s_ksqr(mp_digit *da, mp_digit *dc, mp_size size_a) | |||
2281 | { | |||
2282 | if (multiply_threshold && size_a > multiply_threshold) { | |||
2283 | mp_size bot_size = (size_a + 1) / 2; | |||
2284 | mp_digit *a_top = da + bot_size; | |||
2285 | mp_digit *t1, *t2, *t3, carry; | |||
2286 | mp_size at_size = size_a - bot_size; | |||
2287 | mp_size buf_size = 2 * bot_size; | |||
2288 | ||||
2289 | if ((t1 = s_alloc(4 * buf_size)) == NULL((void*)0)) return 0; | |||
2290 | t2 = t1 + buf_size; | |||
2291 | t3 = t2 + buf_size; | |||
2292 | ZERO(t1, 4 * buf_size)do{ mp_size i__ = (4 * buf_size) * sizeof(mp_digit); mp_digit *p__ = (t1); memset(p__, 0, i__); } while(0); | |||
2293 | ||||
2294 | (void) s_ksqr(da, t1, bot_size); /* t1 = a0 ^ 2 */ | |||
2295 | (void) s_ksqr(a_top, t2, at_size); /* t2 = a1 ^ 2 */ | |||
2296 | ||||
2297 | (void) s_kmul(da, a_top, t3, bot_size, at_size); /* t3 = a0 * a1 */ | |||
2298 | ||||
2299 | /* Quick multiply t3 by 2, shifting left (can't overflow) */ | |||
2300 | { | |||
2301 | int i, top = bot_size + at_size; | |||
2302 | mp_word w, save = 0; | |||
2303 | ||||
2304 | for (i = 0; i < top; ++i) { | |||
2305 | w = t3[i]; | |||
2306 | w = (w << 1) | save; | |||
2307 | t3[i] = LOWER_HALF(w)((mp_digit)(w)); | |||
2308 | save = UPPER_HALF(w)((mp_word)((w) >> (sizeof(mp_digit) * 8))); | |||
2309 | } | |||
2310 | t3[i] = LOWER_HALF(save)((mp_digit)(save)); | |||
2311 | } | |||
2312 | ||||
2313 | /* Assemble the output value */ | |||
2314 | COPY(t1, dc, 2 * bot_size)do{ mp_size i__ = (2 * bot_size) * sizeof(mp_digit); mp_digit *p__ = (t1), *q__ = (dc); memcpy(q__, p__, i__); } while(0); | |||
2315 | carry = s_uadd(t3, dc + bot_size, dc + bot_size, | |||
2316 | buf_size + 1, buf_size); | |||
2317 | assert(carry == 0)((carry == 0) ? (void) (0) : __assert_fail ("carry == 0", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 2317, __PRETTY_FUNCTION__)); | |||
2318 | ||||
2319 | carry = s_uadd(t2, dc + 2*bot_size, dc + 2*bot_size, | |||
2320 | buf_size, buf_size); | |||
2321 | assert(carry == 0)((carry == 0) ? (void) (0) : __assert_fail ("carry == 0", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 2321, __PRETTY_FUNCTION__)); | |||
2322 | ||||
2323 | s_free(t1); /* note that t2 and t2 are internal pointers only */ | |||
2324 | ||||
2325 | } | |||
2326 | else { | |||
2327 | s_usqr(da, dc, size_a); | |||
2328 | } | |||
2329 | ||||
2330 | return 1; | |||
2331 | } | |||
2332 | ||||
2333 | STATICstatic void s_usqr(mp_digit *da, mp_digit *dc, mp_size size_a) | |||
2334 | { | |||
2335 | mp_size i, j; | |||
2336 | mp_word w; | |||
2337 | ||||
2338 | for (i = 0; i < size_a; ++i, dc += 2, ++da) { | |||
2339 | mp_digit *dct = dc, *dat = da; | |||
2340 | ||||
2341 | if (*da == 0) | |||
2342 | continue; | |||
2343 | ||||
2344 | /* Take care of the first digit, no rollover */ | |||
2345 | w = (mp_word)*dat * (mp_word)*dat + (mp_word)*dct; | |||
2346 | *dct = LOWER_HALF(w)((mp_digit)(w)); | |||
2347 | w = UPPER_HALF(w)((mp_word)((w) >> (sizeof(mp_digit) * 8))); | |||
2348 | ++dat; ++dct; | |||
2349 | ||||
2350 | for (j = i + 1; j < size_a; ++j, ++dat, ++dct) { | |||
2351 | mp_word t = (mp_word)*da * (mp_word)*dat; | |||
2352 | mp_word u = w + (mp_word)*dct, ov = 0; | |||
2353 | ||||
2354 | /* Check if doubling t will overflow a word */ | |||
2355 | if (HIGH_BIT_SET(t)((t) >> ((sizeof(mp_word) * 8) - 1))) | |||
2356 | ov = 1; | |||
2357 | ||||
2358 | w = t + t; | |||
2359 | ||||
2360 | /* Check if adding u to w will overflow a word */ | |||
2361 | if (ADD_WILL_OVERFLOW(w, u)((((18446744073709551615UL)) - (u)) < (w))) | |||
2362 | ov = 1; | |||
2363 | ||||
2364 | w += u; | |||
2365 | ||||
2366 | *dct = LOWER_HALF(w)((mp_digit)(w)); | |||
2367 | w = UPPER_HALF(w)((mp_word)((w) >> (sizeof(mp_digit) * 8))); | |||
2368 | if (ov) { | |||
2369 | w += MP_DIGIT_MAX((4294967295U) * 1UL); /* MP_RADIX */ | |||
2370 | ++w; | |||
2371 | } | |||
2372 | } | |||
2373 | ||||
2374 | w = w + *dct; | |||
2375 | *dct = (mp_digit)w; | |||
2376 | while ((w = UPPER_HALF(w)((mp_word)((w) >> (sizeof(mp_digit) * 8)))) != 0) { | |||
2377 | ++dct; w = w + *dct; | |||
2378 | *dct = LOWER_HALF(w)((mp_digit)(w)); | |||
2379 | } | |||
2380 | ||||
2381 | assert(w == 0)((w == 0) ? (void) (0) : __assert_fail ("w == 0", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 2381, __PRETTY_FUNCTION__)); | |||
2382 | } | |||
2383 | } | |||
2384 | ||||
2385 | STATICstatic void s_dadd(mp_int a, mp_digit b) | |||
2386 | { | |||
2387 | mp_word w = 0; | |||
2388 | mp_digit *da = MP_DIGITS(a)((a)->digits); | |||
2389 | mp_size ua = MP_USED(a)((a)->used); | |||
2390 | ||||
2391 | w = (mp_word)*da + b; | |||
2392 | *da++ = LOWER_HALF(w)((mp_digit)(w)); | |||
2393 | w = UPPER_HALF(w)((mp_word)((w) >> (sizeof(mp_digit) * 8))); | |||
2394 | ||||
2395 | for (ua -= 1; ua > 0; --ua, ++da) { | |||
2396 | w = (mp_word)*da + w; | |||
2397 | ||||
2398 | *da = LOWER_HALF(w)((mp_digit)(w)); | |||
2399 | w = UPPER_HALF(w)((mp_word)((w) >> (sizeof(mp_digit) * 8))); | |||
2400 | } | |||
2401 | ||||
2402 | if (w) { | |||
2403 | *da = (mp_digit)w; | |||
2404 | MP_USED(a)((a)->used) += 1; | |||
2405 | } | |||
2406 | } | |||
2407 | ||||
2408 | STATICstatic void s_dmul(mp_int a, mp_digit b) | |||
2409 | { | |||
2410 | mp_word w = 0; | |||
2411 | mp_digit *da = MP_DIGITS(a)((a)->digits); | |||
2412 | mp_size ua = MP_USED(a)((a)->used); | |||
2413 | ||||
2414 | while (ua > 0) { | |||
2415 | w = (mp_word)*da * b + w; | |||
2416 | *da++ = LOWER_HALF(w)((mp_digit)(w)); | |||
2417 | w = UPPER_HALF(w)((mp_word)((w) >> (sizeof(mp_digit) * 8))); | |||
2418 | --ua; | |||
2419 | } | |||
2420 | ||||
2421 | if (w) { | |||
2422 | *da = (mp_digit)w; | |||
2423 | MP_USED(a)((a)->used) += 1; | |||
2424 | } | |||
2425 | } | |||
2426 | ||||
2427 | STATICstatic void s_dbmul(mp_digit *da, mp_digit b, mp_digit *dc, mp_size size_a) | |||
2428 | { | |||
2429 | mp_word w = 0; | |||
2430 | ||||
2431 | while (size_a > 0) { | |||
2432 | w = (mp_word)*da++ * (mp_word)b + w; | |||
2433 | ||||
2434 | *dc++ = LOWER_HALF(w)((mp_digit)(w)); | |||
2435 | w = UPPER_HALF(w)((mp_word)((w) >> (sizeof(mp_digit) * 8))); | |||
2436 | --size_a; | |||
2437 | } | |||
2438 | ||||
2439 | if (w) | |||
2440 | *dc = LOWER_HALF(w)((mp_digit)(w)); | |||
2441 | } | |||
2442 | ||||
2443 | STATICstatic mp_digit s_ddiv(mp_int a, mp_digit b) | |||
2444 | { | |||
2445 | mp_word w = 0, qdigit; | |||
2446 | mp_size ua = MP_USED(a)((a)->used); | |||
2447 | mp_digit *da = MP_DIGITS(a)((a)->digits) + ua - 1; | |||
2448 | ||||
2449 | for (/* */; ua > 0; --ua, --da) { | |||
2450 | w = (w << MP_DIGIT_BIT(sizeof(mp_digit) * 8)) | *da; | |||
2451 | ||||
2452 | if (w >= b) { | |||
2453 | qdigit = w / b; | |||
2454 | w = w % b; | |||
2455 | } | |||
2456 | else { | |||
2457 | qdigit = 0; | |||
2458 | } | |||
2459 | ||||
2460 | *da = (mp_digit)qdigit; | |||
2461 | } | |||
2462 | ||||
2463 | CLAMP(a)do{ mp_int z_ = (a); mp_size uz_ = ((z_)->used); mp_digit * dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0); | |||
2464 | return (mp_digit)w; | |||
2465 | } | |||
2466 | ||||
2467 | STATICstatic void s_qdiv(mp_int z, mp_size p2) | |||
2468 | { | |||
2469 | mp_size ndig = p2 / MP_DIGIT_BIT(sizeof(mp_digit) * 8), nbits = p2 % MP_DIGIT_BIT(sizeof(mp_digit) * 8); | |||
2470 | mp_size uz = MP_USED(z)((z)->used); | |||
2471 | ||||
2472 | if (ndig) { | |||
2473 | mp_size mark; | |||
2474 | mp_digit *to, *from; | |||
2475 | ||||
2476 | if (ndig >= uz) { | |||
2477 | mp_int_zero(z); | |||
2478 | return; | |||
2479 | } | |||
2480 | ||||
2481 | to = MP_DIGITS(z)((z)->digits); from = to + ndig; | |||
2482 | ||||
2483 | for (mark = ndig; mark < uz; ++mark) | |||
2484 | *to++ = *from++; | |||
2485 | ||||
2486 | MP_USED(z)((z)->used) = uz - ndig; | |||
2487 | } | |||
2488 | ||||
2489 | if (nbits) { | |||
2490 | mp_digit d = 0, *dz, save; | |||
2491 | mp_size up = MP_DIGIT_BIT(sizeof(mp_digit) * 8) - nbits; | |||
2492 | ||||
2493 | uz = MP_USED(z)((z)->used); | |||
2494 | dz = MP_DIGITS(z)((z)->digits) + uz - 1; | |||
2495 | ||||
2496 | for (/* */; uz > 0; --uz, --dz) { | |||
2497 | save = *dz; | |||
2498 | ||||
2499 | *dz = (*dz >> nbits) | (d << up); | |||
2500 | d = save; | |||
2501 | } | |||
2502 | ||||
2503 | CLAMP(z)do{ mp_int z_ = (z); mp_size uz_ = ((z_)->used); mp_digit * dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0); | |||
2504 | } | |||
2505 | ||||
2506 | if (MP_USED(z)((z)->used) == 1 && z->digits[0] == 0) | |||
2507 | MP_SIGN(z)((z)->sign) = MP_ZPOS; | |||
2508 | } | |||
2509 | ||||
2510 | STATICstatic void s_qmod(mp_int z, mp_size p2) | |||
2511 | { | |||
2512 | mp_size start = p2 / MP_DIGIT_BIT(sizeof(mp_digit) * 8) + 1, rest = p2 % MP_DIGIT_BIT(sizeof(mp_digit) * 8); | |||
2513 | mp_size uz = MP_USED(z)((z)->used); | |||
2514 | mp_digit mask = (1u << rest) - 1; | |||
2515 | ||||
2516 | if (start <= uz) { | |||
2517 | MP_USED(z)((z)->used) = start; | |||
2518 | z->digits[start - 1] &= mask; | |||
2519 | CLAMP(z)do{ mp_int z_ = (z); mp_size uz_ = ((z_)->used); mp_digit * dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0); | |||
2520 | } | |||
2521 | } | |||
2522 | ||||
2523 | STATICstatic int s_qmul(mp_int z, mp_size p2) | |||
2524 | { | |||
2525 | mp_size uz, need, rest, extra, i; | |||
2526 | mp_digit *from, *to, d; | |||
2527 | ||||
2528 | if (p2 == 0) | |||
2529 | return 1; | |||
2530 | ||||
2531 | uz = MP_USED(z)((z)->used); | |||
2532 | need = p2 / MP_DIGIT_BIT(sizeof(mp_digit) * 8); rest = p2 % MP_DIGIT_BIT(sizeof(mp_digit) * 8); | |||
2533 | ||||
2534 | /* Figure out if we need an extra digit at the top end; this occurs if the | |||
2535 | topmost `rest' bits of the high-order digit of z are not zero, meaning | |||
2536 | they will be shifted off the end if not preserved */ | |||
2537 | extra = 0; | |||
2538 | if (rest != 0) { | |||
2539 | mp_digit *dz = MP_DIGITS(z)((z)->digits) + uz - 1; | |||
2540 | ||||
2541 | if ((*dz >> (MP_DIGIT_BIT(sizeof(mp_digit) * 8) - rest)) != 0) | |||
2542 | extra = 1; | |||
2543 | } | |||
2544 | ||||
2545 | if (!s_pad(z, uz + need + extra)) | |||
2546 | return 0; | |||
2547 | ||||
2548 | /* If we need to shift by whole digits, do that in one pass, then | |||
2549 | to back and shift by partial digits. | |||
2550 | */ | |||
2551 | if (need > 0) { | |||
2552 | from = MP_DIGITS(z)((z)->digits) + uz - 1; | |||
2553 | to = from + need; | |||
2554 | ||||
2555 | for (i = 0; i < uz; ++i) | |||
2556 | *to-- = *from--; | |||
2557 | ||||
2558 | ZERO(MP_DIGITS(z), need)do{ mp_size i__ = (need) * sizeof(mp_digit); mp_digit *p__ = ( ((z)->digits)); memset(p__, 0, i__); } while(0); | |||
2559 | uz += need; | |||
2560 | } | |||
2561 | ||||
2562 | if (rest) { | |||
2563 | d = 0; | |||
2564 | for (i = need, from = MP_DIGITS(z)((z)->digits) + need; i < uz; ++i, ++from) { | |||
2565 | mp_digit save = *from; | |||
2566 | ||||
2567 | *from = (*from << rest) | (d >> (MP_DIGIT_BIT(sizeof(mp_digit) * 8) - rest)); | |||
2568 | d = save; | |||
2569 | } | |||
2570 | ||||
2571 | d >>= (MP_DIGIT_BIT(sizeof(mp_digit) * 8) - rest); | |||
2572 | if (d != 0) { | |||
2573 | *from = d; | |||
2574 | uz += extra; | |||
2575 | } | |||
2576 | } | |||
2577 | ||||
2578 | MP_USED(z)((z)->used) = uz; | |||
2579 | CLAMP(z)do{ mp_int z_ = (z); mp_size uz_ = ((z_)->used); mp_digit * dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0); | |||
2580 | ||||
2581 | return 1; | |||
2582 | } | |||
2583 | ||||
2584 | /* Compute z = 2^p2 - |z|; requires that 2^p2 >= |z| | |||
2585 | The sign of the result is always zero/positive. | |||
2586 | */ | |||
2587 | STATICstatic int s_qsub(mp_int z, mp_size p2) | |||
2588 | { | |||
2589 | mp_digit hi = (1 << (p2 % MP_DIGIT_BIT(sizeof(mp_digit) * 8))), *zp; | |||
2590 | mp_size tdig = (p2 / MP_DIGIT_BIT(sizeof(mp_digit) * 8)), pos; | |||
2591 | mp_word w = 0; | |||
2592 | ||||
2593 | if (!s_pad(z, tdig + 1)) | |||
2594 | return 0; | |||
2595 | ||||
2596 | for (pos = 0, zp = MP_DIGITS(z)((z)->digits); pos < tdig; ++pos, ++zp) { | |||
2597 | w = ((mp_word) MP_DIGIT_MAX((4294967295U) * 1UL) + 1) - w - (mp_word)*zp; | |||
2598 | ||||
2599 | *zp = LOWER_HALF(w)((mp_digit)(w)); | |||
2600 | w = UPPER_HALF(w)((mp_word)((w) >> (sizeof(mp_digit) * 8))) ? 0 : 1; | |||
2601 | } | |||
2602 | ||||
2603 | w = ((mp_word) MP_DIGIT_MAX((4294967295U) * 1UL) + 1 + hi) - w - (mp_word)*zp; | |||
2604 | *zp = LOWER_HALF(w)((mp_digit)(w)); | |||
2605 | ||||
2606 | assert(UPPER_HALF(w) != 0)((((mp_word)((w) >> (sizeof(mp_digit) * 8))) != 0) ? (void ) (0) : __assert_fail ("UPPER_HALF(w) != 0", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 2606, __PRETTY_FUNCTION__)); /* no borrow out should be possible */ | |||
2607 | ||||
2608 | MP_SIGN(z)((z)->sign) = MP_ZPOS; | |||
2609 | CLAMP(z)do{ mp_int z_ = (z); mp_size uz_ = ((z_)->used); mp_digit * dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0); | |||
2610 | ||||
2611 | return 1; | |||
2612 | } | |||
2613 | ||||
2614 | STATICstatic int s_dp2k(mp_int z) | |||
2615 | { | |||
2616 | int k = 0; | |||
2617 | mp_digit *dp = MP_DIGITS(z)((z)->digits), d; | |||
2618 | ||||
2619 | if (MP_USED(z)((z)->used) == 1 && *dp == 0) | |||
2620 | return 1; | |||
2621 | ||||
2622 | while (*dp == 0) { | |||
2623 | k += MP_DIGIT_BIT(sizeof(mp_digit) * 8); | |||
2624 | ++dp; | |||
2625 | } | |||
2626 | ||||
2627 | d = *dp; | |||
2628 | while ((d & 1) == 0) { | |||
2629 | d >>= 1; | |||
2630 | ++k; | |||
2631 | } | |||
2632 | ||||
2633 | return k; | |||
2634 | } | |||
2635 | ||||
2636 | STATICstatic int s_isp2(mp_int z) | |||
2637 | { | |||
2638 | mp_size uz = MP_USED(z)((z)->used), k = 0; | |||
2639 | mp_digit *dz = MP_DIGITS(z)((z)->digits), d; | |||
2640 | ||||
2641 | while (uz > 1) { | |||
2642 | if (*dz++ != 0) | |||
2643 | return -1; | |||
2644 | k += MP_DIGIT_BIT(sizeof(mp_digit) * 8); | |||
2645 | --uz; | |||
2646 | } | |||
2647 | ||||
2648 | d = *dz; | |||
2649 | while (d > 1) { | |||
2650 | if (d & 1) | |||
2651 | return -1; | |||
2652 | ++k; d >>= 1; | |||
2653 | } | |||
2654 | ||||
2655 | return (int) k; | |||
2656 | } | |||
2657 | ||||
2658 | STATICstatic int s_2expt(mp_int z, mp_small k) | |||
2659 | { | |||
2660 | mp_size ndig, rest; | |||
2661 | mp_digit *dz; | |||
2662 | ||||
2663 | ndig = (k + MP_DIGIT_BIT(sizeof(mp_digit) * 8)) / MP_DIGIT_BIT(sizeof(mp_digit) * 8); | |||
2664 | rest = k % MP_DIGIT_BIT(sizeof(mp_digit) * 8); | |||
2665 | ||||
2666 | if (!s_pad(z, ndig)) | |||
2667 | return 0; | |||
2668 | ||||
2669 | dz = MP_DIGITS(z)((z)->digits); | |||
2670 | ZERO(dz, ndig)do{ mp_size i__ = (ndig) * sizeof(mp_digit); mp_digit *p__ = ( dz); memset(p__, 0, i__); } while(0); | |||
2671 | *(dz + ndig - 1) = (1 << rest); | |||
2672 | MP_USED(z)((z)->used) = ndig; | |||
2673 | ||||
2674 | return 1; | |||
2675 | } | |||
2676 | ||||
2677 | STATICstatic int s_norm(mp_int a, mp_int b) | |||
2678 | { | |||
2679 | mp_digit d = b->digits[MP_USED(b)((b)->used) - 1]; | |||
2680 | int k = 0; | |||
2681 | ||||
2682 | while (d < (1u << (mp_digit)(MP_DIGIT_BIT(sizeof(mp_digit) * 8) - 1))) { /* d < (MP_RADIX / 2) */ | |||
2683 | d <<= 1; | |||
2684 | ++k; | |||
2685 | } | |||
2686 | ||||
2687 | /* These multiplications can't fail */ | |||
2688 | if (k != 0) { | |||
2689 | (void) s_qmul(a, (mp_size) k); | |||
2690 | (void) s_qmul(b, (mp_size) k); | |||
2691 | } | |||
2692 | ||||
2693 | return k; | |||
2694 | } | |||
2695 | ||||
2696 | STATICstatic mp_result s_brmu(mp_int z, mp_int m) | |||
2697 | { | |||
2698 | mp_size um = MP_USED(m)((m)->used) * 2; | |||
2699 | ||||
2700 | if (!s_pad(z, um)) | |||
2701 | return MP_MEMORY; | |||
2702 | ||||
2703 | s_2expt(z, MP_DIGIT_BIT(sizeof(mp_digit) * 8) * um); | |||
2704 | return mp_int_div(z, m, z, NULL((void*)0)); | |||
2705 | } | |||
2706 | ||||
2707 | STATICstatic int s_reduce(mp_int x, mp_int m, mp_int mu, mp_int q1, mp_int q2) | |||
2708 | { | |||
2709 | mp_size um = MP_USED(m)((m)->used), umb_p1, umb_m1; | |||
2710 | ||||
2711 | umb_p1 = (um + 1) * MP_DIGIT_BIT(sizeof(mp_digit) * 8); | |||
2712 | umb_m1 = (um - 1) * MP_DIGIT_BIT(sizeof(mp_digit) * 8); | |||
2713 | ||||
2714 | if (mp_int_copy(x, q1) != MP_OK) | |||
2715 | return 0; | |||
2716 | ||||
2717 | /* Compute q2 = floor((floor(x / b^(k-1)) * mu) / b^(k+1)) */ | |||
2718 | s_qdiv(q1, umb_m1); | |||
2719 | UMUL(q1, mu, q2)do{ mp_size ua_ = ((q1)->used), ub_ = ((mu)->used); mp_size o_ = ua_ + ub_; do{ mp_size i__ = (o_) * sizeof(mp_digit); mp_digit *p__ = (((q2)->digits)); memset(p__, 0, i__); } while(0); (void) s_kmul(((q1)->digits), ((mu)->digits), ((q2)-> digits), ua_, ub_); ((q2)->used) = o_; do{ mp_int z_ = (q2 ); mp_size uz_ = ((z_)->used); mp_digit *dz_ = ((z_)->digits ) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_ ; ((z_)->used) = uz_; } while(0); } while(0); | |||
2720 | s_qdiv(q2, umb_p1); | |||
2721 | ||||
2722 | /* Set x = x mod b^(k+1) */ | |||
2723 | s_qmod(x, umb_p1); | |||
2724 | ||||
2725 | /* Now, q is a guess for the quotient a / m. | |||
2726 | Compute x - q * m mod b^(k+1), replacing x. This may be off | |||
2727 | by a factor of 2m, but no more than that. | |||
2728 | */ | |||
2729 | UMUL(q2, m, q1)do{ mp_size ua_ = ((q2)->used), ub_ = ((m)->used); mp_size o_ = ua_ + ub_; do{ mp_size i__ = (o_) * sizeof(mp_digit); mp_digit *p__ = (((q1)->digits)); memset(p__, 0, i__); } while(0); (void) s_kmul(((q2)->digits), ((m)->digits), ((q1)-> digits), ua_, ub_); ((q1)->used) = o_; do{ mp_int z_ = (q1 ); mp_size uz_ = ((z_)->used); mp_digit *dz_ = ((z_)->digits ) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_ ; ((z_)->used) = uz_; } while(0); } while(0); | |||
2730 | s_qmod(q1, umb_p1); | |||
2731 | (void) mp_int_sub(x, q1, x); /* can't fail */ | |||
2732 | ||||
2733 | /* The result may be < 0; if it is, add b^(k+1) to pin it in the proper | |||
2734 | range. */ | |||
2735 | if ((CMPZ(x)(((x)->used==1&&(x)->digits[0]==0)?0:((x)->sign ==MP_NEG)?-1:1) < 0) && !s_qsub(x, umb_p1)) | |||
2736 | return 0; | |||
2737 | ||||
2738 | /* If x > m, we need to back it off until it is in range. This will be | |||
2739 | required at most twice. */ | |||
2740 | if (mp_int_compare(x, m) >= 0) { | |||
2741 | (void) mp_int_sub(x, m, x); | |||
2742 | if (mp_int_compare(x, m) >= 0) | |||
2743 | (void) mp_int_sub(x, m, x); | |||
2744 | } | |||
2745 | ||||
2746 | /* At this point, x has been properly reduced. */ | |||
2747 | return 1; | |||
2748 | } | |||
2749 | ||||
2750 | /* Perform modular exponentiation using Barrett's method, where mu is the | |||
2751 | reduction constant for m. Assumes a < m, b > 0. */ | |||
2752 | STATICstatic mp_result s_embar(mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c) | |||
2753 | { | |||
2754 | mp_digit *db, *dbt, umu, d; | |||
2755 | mp_result res; | |||
2756 | DECLARE_TEMP(3)mpz_t temp[(3)]; int last__ = 0; | |||
2757 | ||||
2758 | umu = MP_USED(mu)((mu)->used); db = MP_DIGITS(b)((b)->digits); dbt = db + MP_USED(b)((b)->used) - 1; | |||
2759 | ||||
2760 | while (last__ < 3) { | |||
2761 | SETUP(mp_int_init_size(LAST_TEMP(), 4 * umu))do{ if ((res = (mp_int_init_size((temp + (last__)), 4 * umu)) ) != MP_OK) goto CLEANUP; ++(last__); } while(0); | |||
2762 | ZERO(MP_DIGITS(TEMP(last__ - 1)), MP_ALLOC(TEMP(last__ - 1)))do{ mp_size i__ = ((((temp + (last__ - 1)))->alloc)) * sizeof (mp_digit); mp_digit *p__ = ((((temp + (last__ - 1)))->digits )); memset(p__, 0, i__); } while(0); | |||
2763 | } | |||
2764 | ||||
2765 | (void) mp_int_set_value(c, 1); | |||
2766 | ||||
2767 | /* Take care of low-order digits */ | |||
2768 | while (db < dbt) { | |||
2769 | int i; | |||
2770 | ||||
2771 | for (d = *db, i = MP_DIGIT_BIT(sizeof(mp_digit) * 8); i > 0; --i, d >>= 1) { | |||
2772 | if (d & 1) { | |||
2773 | /* The use of a second temporary avoids allocation */ | |||
2774 | UMUL(c, a, TEMP(0))do{ mp_size ua_ = ((c)->used), ub_ = ((a)->used); mp_size o_ = ua_ + ub_; do{ mp_size i__ = (o_) * sizeof(mp_digit); mp_digit *p__ = ((((temp + (0)))->digits)); memset(p__, 0, i__); } while(0); (void) s_kmul(((c)->digits), ((a)->digits), ( ((temp + (0)))->digits), ua_, ub_); (((temp + (0)))->used ) = o_; do{ mp_int z_ = ((temp + (0))); mp_size uz_ = ((z_)-> used); mp_digit *dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_ ; } while(0); } while(0); | |||
2775 | if (!s_reduce(TEMP(0)(temp + (0)), m, mu, TEMP(1)(temp + (1)), TEMP(2)(temp + (2)))) { | |||
2776 | res = MP_MEMORY; goto CLEANUP; | |||
2777 | } | |||
2778 | mp_int_copy(TEMP(0)(temp + (0)), c); | |||
2779 | } | |||
2780 | ||||
2781 | ||||
2782 | USQR(a, TEMP(0))do{ mp_size ua_ = ((a)->used), o_ = ua_ + ua_; do{ mp_size i__ = (o_) * sizeof(mp_digit); mp_digit *p__ = ((((temp + (0 )))->digits)); memset(p__, 0, i__); } while(0); (void) s_ksqr (((a)->digits), (((temp + (0)))->digits), ua_); (((temp + (0)))->used) = o_; do{ mp_int z_ = ((temp + (0))); mp_size uz_ = ((z_)->used); mp_digit *dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_) ->used) = uz_; } while(0); } while(0); | |||
2783 | assert(MP_SIGN(TEMP(0)) == MP_ZPOS)(((((temp + (0)))->sign) == MP_ZPOS) ? (void) (0) : __assert_fail ("MP_SIGN(TEMP(0)) == MP_ZPOS", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 2783, __PRETTY_FUNCTION__)); | |||
2784 | if (!s_reduce(TEMP(0)(temp + (0)), m, mu, TEMP(1)(temp + (1)), TEMP(2)(temp + (2)))) { | |||
2785 | res = MP_MEMORY; goto CLEANUP; | |||
2786 | } | |||
2787 | assert(MP_SIGN(TEMP(0)) == MP_ZPOS)(((((temp + (0)))->sign) == MP_ZPOS) ? (void) (0) : __assert_fail ("MP_SIGN(TEMP(0)) == MP_ZPOS", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 2787, __PRETTY_FUNCTION__)); | |||
2788 | mp_int_copy(TEMP(0)(temp + (0)), a); | |||
2789 | } | |||
2790 | ||||
2791 | ++db; | |||
2792 | } | |||
2793 | ||||
2794 | /* Take care of highest-order digit */ | |||
2795 | d = *dbt; | |||
2796 | for (;;) { | |||
2797 | if (d & 1) { | |||
2798 | UMUL(c, a, TEMP(0))do{ mp_size ua_ = ((c)->used), ub_ = ((a)->used); mp_size o_ = ua_ + ub_; do{ mp_size i__ = (o_) * sizeof(mp_digit); mp_digit *p__ = ((((temp + (0)))->digits)); memset(p__, 0, i__); } while(0); (void) s_kmul(((c)->digits), ((a)->digits), ( ((temp + (0)))->digits), ua_, ub_); (((temp + (0)))->used ) = o_; do{ mp_int z_ = ((temp + (0))); mp_size uz_ = ((z_)-> used); mp_digit *dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_ ; } while(0); } while(0); | |||
2799 | if (!s_reduce(TEMP(0)(temp + (0)), m, mu, TEMP(1)(temp + (1)), TEMP(2)(temp + (2)))) { | |||
2800 | res = MP_MEMORY; goto CLEANUP; | |||
2801 | } | |||
2802 | mp_int_copy(TEMP(0)(temp + (0)), c); | |||
2803 | } | |||
2804 | ||||
2805 | d >>= 1; | |||
2806 | if (!d) break; | |||
2807 | ||||
2808 | USQR(a, TEMP(0))do{ mp_size ua_ = ((a)->used), o_ = ua_ + ua_; do{ mp_size i__ = (o_) * sizeof(mp_digit); mp_digit *p__ = ((((temp + (0 )))->digits)); memset(p__, 0, i__); } while(0); (void) s_ksqr (((a)->digits), (((temp + (0)))->digits), ua_); (((temp + (0)))->used) = o_; do{ mp_int z_ = ((temp + (0))); mp_size uz_ = ((z_)->used); mp_digit *dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_) ->used) = uz_; } while(0); } while(0); | |||
2809 | if (!s_reduce(TEMP(0)(temp + (0)), m, mu, TEMP(1)(temp + (1)), TEMP(2)(temp + (2)))) { | |||
2810 | res = MP_MEMORY; goto CLEANUP; | |||
2811 | } | |||
2812 | (void) mp_int_copy(TEMP(0)(temp + (0)), a); | |||
2813 | } | |||
2814 | ||||
2815 | CLEANUP_TEMP()CLEANUP: while (--last__ >= 0) mp_int_clear((temp + (last__ ))); | |||
2816 | return res; | |||
2817 | } | |||
2818 | ||||
2819 | /* Division of nonnegative integers | |||
2820 | ||||
2821 | This function implements division algorithm for unsigned multi-precision | |||
2822 | integers. The algorithm is based on Algorithm D from Knuth's "The Art of | |||
2823 | Computer Programming", 3rd ed. 1998, pg 272-273. | |||
2824 | ||||
2825 | We diverge from Knuth's algorithm in that we do not perform the subtraction | |||
2826 | from the remainder until we have determined that we have the correct | |||
2827 | quotient digit. This makes our algorithm less efficient that Knuth because | |||
2828 | we might have to perform multiple multiplication and comparison steps before | |||
2829 | the subtraction. The advantage is that it is easy to implement and ensure | |||
2830 | correctness without worrying about underflow from the subtraction. | |||
2831 | ||||
2832 | inputs: u a n+m digit integer in base b (b is 2^MP_DIGIT_BIT) | |||
2833 | v a n digit integer in base b (b is 2^MP_DIGIT_BIT) | |||
2834 | n >= 1 | |||
2835 | m >= 0 | |||
2836 | outputs: u / v stored in u | |||
2837 | u % v stored in v | |||
2838 | */ | |||
2839 | STATICstatic mp_result s_udiv_knuth(mp_int u, mp_int v) { | |||
2840 | mpz_t q, r, t; | |||
2841 | mp_result | |||
2842 | res = MP_OK; | |||
2843 | int k,j; | |||
2844 | mp_size m,n; | |||
2845 | ||||
2846 | /* Force signs to positive */ | |||
2847 | MP_SIGN(u)((u)->sign) = MP_ZPOS; | |||
2848 | MP_SIGN(v)((v)->sign) = MP_ZPOS; | |||
2849 | ||||
2850 | /* Use simple division algorithm when v is only one digit long */ | |||
2851 | if (MP_USED(v)((v)->used) == 1) { | |||
2852 | mp_digit d, rem; | |||
2853 | d = v->digits[0]; | |||
2854 | rem = s_ddiv(u, d); | |||
2855 | mp_int_set_value(v, rem); | |||
2856 | return MP_OK; | |||
2857 | } | |||
2858 | ||||
2859 | /* Algorithm D | |||
2860 | ||||
2861 | The n and m variables are defined as used by Knuth. | |||
2862 | u is an n digit number with digits u_{n-1}..u_0. | |||
2863 | v is an n+m digit number with digits from v_{m+n-1}..v_0. | |||
2864 | We require that n > 1 and m >= 0 | |||
2865 | */ | |||
2866 | n = MP_USED(v)((v)->used); | |||
2867 | m = MP_USED(u)((u)->used) - n; | |||
2868 | assert(n > 1)((n > 1) ? (void) (0) : __assert_fail ("n > 1", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 2868, __PRETTY_FUNCTION__)); | |||
2869 | assert(m >= 0)((m >= 0) ? (void) (0) : __assert_fail ("m >= 0", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 2869, __PRETTY_FUNCTION__)); | |||
2870 | ||||
2871 | /* D1: Normalize. | |||
2872 | The normalization step provides the necessary condition for Theorem B, | |||
2873 | which states that the quotient estimate for q_j, call it qhat | |||
2874 | ||||
2875 | qhat = u_{j+n}u_{j+n-1} / v_{n-1} | |||
2876 | ||||
2877 | is bounded by | |||
2878 | ||||
2879 | qhat - 2 <= q_j <= qhat. | |||
2880 | ||||
2881 | That is, qhat is always greater than the actual quotient digit q, | |||
2882 | and it is never more than two larger than the actual quotient digit. | |||
2883 | */ | |||
2884 | k = s_norm(u, v); | |||
2885 | ||||
2886 | /* Extend size of u by one if needed. | |||
2887 | ||||
2888 | The algorithm begins with a value of u that has one more digit of input. | |||
2889 | The normalization step sets u_{m+n}..u_0 = 2^k * u_{m+n-1}..u_0. If the | |||
2890 | multiplication did not increase the number of digits of u, we need to add | |||
2891 | a leading zero here. | |||
2892 | */ | |||
2893 | if (k == 0 || MP_USED(u)((u)->used) != m + n + 1) { | |||
2894 | if (!s_pad(u, m+n+1)) | |||
2895 | return MP_MEMORY; | |||
2896 | u->digits[m+n] = 0; | |||
2897 | u->used = m+n+1; | |||
2898 | } | |||
2899 | ||||
2900 | /* Add a leading 0 to v. | |||
2901 | ||||
2902 | The multiplication in step D4 multiplies qhat * 0v_{n-1}..v_0. We need to | |||
2903 | add the leading zero to v here to ensure that the multiplication will | |||
2904 | produce the full n+1 digit result. | |||
2905 | */ | |||
2906 | if (!s_pad(v, n+1)) return MP_MEMORY; v->digits[n] = 0; | |||
2907 | ||||
2908 | /* Initialize temporary variables q and t. | |||
2909 | q allocates space for m+1 digits to store the quotient digits | |||
2910 | t allocates space for n+1 digits to hold the result of q_j*v | |||
2911 | */ | |||
2912 | if ((res = mp_int_init_size(&q, m + 1)) != MP_OK) return res; | |||
2913 | if ((res = mp_int_init_size(&t, n + 1)) != MP_OK) goto CLEANUP; | |||
2914 | ||||
2915 | /* D2: Initialize j */ | |||
2916 | j = m; | |||
2917 | r.digits = MP_DIGITS(u)((u)->digits) + j; /* The contents of r are shared with u */ | |||
2918 | r.used = n + 1; | |||
2919 | r.sign = MP_ZPOS; | |||
2920 | r.alloc = MP_ALLOC(u)((u)->alloc); | |||
2921 | ZERO(t.digits, t.alloc)do{ mp_size i__ = (t.alloc) * sizeof(mp_digit); mp_digit *p__ = (t.digits); memset(p__, 0, i__); } while(0); | |||
2922 | ||||
2923 | /* Calculate the m+1 digits of the quotient result */ | |||
2924 | for (; j >= 0; j--) { | |||
2925 | /* D3: Calculate q' */ | |||
2926 | /* r->digits is aligned to position j of the number u */ | |||
2927 | mp_word pfx, qhat; | |||
2928 | pfx = r.digits[n]; | |||
2929 | pfx <<= MP_DIGIT_BIT(sizeof(mp_digit) * 8) / 2; | |||
2930 | pfx <<= MP_DIGIT_BIT(sizeof(mp_digit) * 8) / 2; | |||
2931 | pfx |= r.digits[n-1]; /* pfx = u_{j+n}{j+n-1} */ | |||
2932 | ||||
2933 | qhat = pfx / v->digits[n-1]; | |||
2934 | /* Check to see if qhat > b, and decrease qhat if so. | |||
2935 | Theorem B guarantess that qhat is at most 2 larger than the | |||
2936 | actual value, so it is possible that qhat is greater than | |||
2937 | the maximum value that will fit in a digit */ | |||
2938 | if (qhat > MP_DIGIT_MAX((4294967295U) * 1UL)) | |||
2939 | qhat = MP_DIGIT_MAX((4294967295U) * 1UL); | |||
2940 | ||||
2941 | /* D4,D5,D6: Multiply qhat * v and test for a correct value of q | |||
2942 | ||||
2943 | We proceed a bit different than the way described by Knuth. This way is | |||
2944 | simpler but less efficent. Instead of doing the multiply and subtract | |||
2945 | then checking for underflow, we first do the multiply of qhat * v and | |||
2946 | see if it is larger than the current remainder r. If it is larger, we | |||
2947 | decrease qhat by one and try again. We may need to decrease qhat one | |||
2948 | more time before we get a value that is smaller than r. | |||
2949 | ||||
2950 | This way is less efficent than Knuth becuase we do more multiplies, but | |||
2951 | we do not need to worry about underflow this way. | |||
2952 | */ | |||
2953 | /* t = qhat * v */ | |||
2954 | s_dbmul(MP_DIGITS(v)((v)->digits), (mp_digit) qhat, t.digits, n+1); t.used = n + 1; | |||
2955 | CLAMP(&t)do{ mp_int z_ = (&t); mp_size uz_ = ((z_)->used); mp_digit *dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0); | |||
2956 | ||||
2957 | /* Clamp r for the comparison. Comparisons do not like leading zeros. */ | |||
2958 | CLAMP(&r)do{ mp_int z_ = (&r); mp_size uz_ = ((z_)->used); mp_digit *dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0); | |||
2959 | if (s_ucmp(&t, &r) > 0) { /* would the remainder be negative? */ | |||
2960 | qhat -= 1; /* try a smaller q */ | |||
2961 | s_dbmul(MP_DIGITS(v)((v)->digits), (mp_digit) qhat, t.digits, n+1); | |||
2962 | t.used = n + 1; CLAMP(&t)do{ mp_int z_ = (&t); mp_size uz_ = ((z_)->used); mp_digit *dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0); | |||
2963 | if (s_ucmp(&t, &r) > 0) { /* would the remainder be negative? */ | |||
2964 | assert(qhat > 0)((qhat > 0) ? (void) (0) : __assert_fail ("qhat > 0", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 2964, __PRETTY_FUNCTION__)); | |||
2965 | qhat -= 1; /* try a smaller q */ | |||
2966 | s_dbmul(MP_DIGITS(v)((v)->digits), (mp_digit) qhat, t.digits, n+1); | |||
2967 | t.used = n + 1; CLAMP(&t)do{ mp_int z_ = (&t); mp_size uz_ = ((z_)->used); mp_digit *dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0); | |||
2968 | } | |||
2969 | assert(s_ucmp(&t, &r) <= 0 && "The mathematics failed us.")((s_ucmp(&t, &r) <= 0 && "The mathematics failed us." ) ? (void) (0) : __assert_fail ("s_ucmp(&t, &r) <= 0 && \"The mathematics failed us.\"" , "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 2969, __PRETTY_FUNCTION__)); | |||
2970 | } | |||
2971 | /* Unclamp r. The D algorithm expects r = u_{j+n}..u_j to always be n+1 | |||
2972 | digits long. */ | |||
2973 | r.used = n + 1; | |||
2974 | ||||
2975 | /* D4: Multiply and subtract | |||
2976 | ||||
2977 | Note: The multiply was completed above so we only need to subtract here. | |||
2978 | */ | |||
2979 | s_usub(r.digits, t.digits, r.digits, r.used, t.used); | |||
2980 | ||||
2981 | /* D5: Test remainder | |||
2982 | ||||
2983 | Note: Not needed because we always check that qhat is the correct value | |||
2984 | before performing the subtract. Value cast to mp_digit to prevent | |||
2985 | warning, qhat has been clamped to MP_DIGIT_MAX | |||
2986 | */ | |||
2987 | q.digits[j] = (mp_digit)qhat; | |||
2988 | ||||
2989 | /* D6: Add back | |||
2990 | Note: Not needed because we always check that qhat is the correct value | |||
2991 | before performing the subtract. | |||
2992 | */ | |||
2993 | ||||
2994 | /* D7: Loop on j */ | |||
2995 | r.digits--; | |||
2996 | ZERO(t.digits, t.alloc)do{ mp_size i__ = (t.alloc) * sizeof(mp_digit); mp_digit *p__ = (t.digits); memset(p__, 0, i__); } while(0); | |||
2997 | } | |||
2998 | ||||
2999 | /* Get rid of leading zeros in q */ | |||
3000 | q.used = m + 1; | |||
3001 | CLAMP(&q)do{ mp_int z_ = (&q); mp_size uz_ = ((z_)->used); mp_digit *dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0); | |||
3002 | ||||
3003 | /* Denormalize the remainder */ | |||
3004 | CLAMP(u)do{ mp_int z_ = (u); mp_size uz_ = ((z_)->used); mp_digit * dz_ = ((z_)->digits) + uz_ -1; while (uz_ > 1 && (*dz_-- == 0)) --uz_; ((z_)->used) = uz_; } while(0); /* use u here because the r.digits pointer is off-by-one */ | |||
3005 | if (k != 0) | |||
3006 | s_qdiv(u, k); | |||
3007 | ||||
3008 | mp_int_copy(u, v); /* ok: 0 <= r < v */ | |||
3009 | mp_int_copy(&q, u); /* ok: q <= u */ | |||
3010 | ||||
3011 | mp_int_clear(&t); | |||
3012 | CLEANUP: | |||
3013 | mp_int_clear(&q); | |||
3014 | return res; | |||
3015 | } | |||
3016 | ||||
3017 | STATICstatic int s_outlen(mp_int z, mp_size r) | |||
3018 | { | |||
3019 | mp_result bits; | |||
3020 | double raw; | |||
3021 | ||||
3022 | assert(r >= MP_MIN_RADIX && r <= MP_MAX_RADIX)((r >= 2 && r <= 36) ? (void) (0) : __assert_fail ("r >= MP_MIN_RADIX && r <= MP_MAX_RADIX", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 3022, __PRETTY_FUNCTION__)); | |||
3023 | ||||
3024 | bits = mp_int_count_bits(z); | |||
3025 | raw = (double)bits * s_log2[r]; | |||
3026 | ||||
3027 | return (int)(raw + 0.999999); | |||
3028 | } | |||
3029 | ||||
3030 | STATICstatic mp_size s_inlen(int len, mp_size r) | |||
3031 | { | |||
3032 | double raw = (double)len / s_log2[r]; | |||
3033 | mp_size bits = (mp_size)(raw + 0.5); | |||
3034 | ||||
3035 | return (mp_size)((bits + (MP_DIGIT_BIT(sizeof(mp_digit) * 8) - 1)) / MP_DIGIT_BIT(sizeof(mp_digit) * 8)) + 1; | |||
3036 | } | |||
3037 | ||||
3038 | STATICstatic int s_ch2val(char c, int r) | |||
3039 | { | |||
3040 | int out; | |||
3041 | ||||
3042 | if (isdigit((unsigned char) c)((*__ctype_b_loc ())[(int) (((unsigned char) c))] & (unsigned short int) _ISdigit)) | |||
3043 | out = c - '0'; | |||
3044 | else if (r > 10 && isalpha((unsigned char) c)((*__ctype_b_loc ())[(int) (((unsigned char) c))] & (unsigned short int) _ISalpha)) | |||
3045 | out = toupper(c)(__extension__ ({ int __res; if (sizeof (c) > 1) { if (__builtin_constant_p (c)) { int __c = (c); __res = __c < -128 || __c > 255 ? __c : (*__ctype_toupper_loc ())[__c]; } else __res = toupper (c); } else __res = (*__ctype_toupper_loc ())[(int) (c)]; __res ; })) - 'A' + 10; | |||
3046 | else | |||
3047 | return -1; | |||
3048 | ||||
3049 | return (out >= r) ? -1 : out; | |||
3050 | } | |||
3051 | ||||
3052 | STATICstatic char s_val2ch(int v, int caps) | |||
3053 | { | |||
3054 | assert(v >= 0)((v >= 0) ? (void) (0) : __assert_fail ("v >= 0", "/build/llvm-toolchain-snapshot-12~++20210119111113+4d3081331ad8/polly/lib/External/isl/imath/imath.c" , 3054, __PRETTY_FUNCTION__)); | |||
3055 | ||||
3056 | if (v < 10) | |||
3057 | return v + '0'; | |||
3058 | else { | |||
3059 | char out = (v - 10) + 'a'; | |||
3060 | ||||
3061 | if (caps) | |||
3062 | return toupper(out)(__extension__ ({ int __res; if (sizeof (out) > 1) { if (__builtin_constant_p (out)) { int __c = (out); __res = __c < -128 || __c > 255 ? __c : (*__ctype_toupper_loc ())[__c]; } else __res = toupper (out); } else __res = (*__ctype_toupper_loc ())[(int) (out)] ; __res; })); | |||
3063 | else | |||
3064 | return out; | |||
3065 | } | |||
3066 | } | |||
3067 | ||||
3068 | STATICstatic void s_2comp(unsigned char *buf, int len) | |||
3069 | { | |||
3070 | int i; | |||
3071 | unsigned short s = 1; | |||
3072 | ||||
3073 | for (i = len - 1; i >= 0; --i) { | |||
3074 | unsigned char c = ~buf[i]; | |||
3075 | ||||
3076 | s = c + s; | |||
3077 | c = s & UCHAR_MAX(127*2 +1); | |||
3078 | s >>= CHAR_BIT8; | |||
3079 | ||||
3080 | buf[i] = c; | |||
3081 | } | |||
3082 | ||||
3083 | /* last carry out is ignored */ | |||
3084 | } | |||
3085 | ||||
3086 | STATICstatic mp_result s_tobin(mp_int z, unsigned char *buf, int *limpos, int pad) | |||
3087 | { | |||
3088 | mp_size uz; | |||
3089 | mp_digit *dz; | |||
3090 | int pos = 0, limit = *limpos; | |||
3091 | ||||
3092 | uz = MP_USED(z)((z)->used); dz = MP_DIGITS(z)((z)->digits); | |||
3093 | while (uz > 0 && pos < limit) { | |||
3094 | mp_digit d = *dz++; | |||
3095 | int i; | |||
3096 | ||||
3097 | for (i = sizeof(mp_digit); i > 0 && pos < limit; --i) { | |||
3098 | buf[pos++] = (unsigned char)d; | |||
3099 | d >>= CHAR_BIT8; | |||
3100 | ||||
3101 | /* Don't write leading zeroes */ | |||
3102 | if (d == 0 && uz == 1) | |||
3103 | i = 0; /* exit loop without signaling truncation */ | |||
3104 | } | |||
3105 | ||||
3106 | /* Detect truncation (loop exited with pos >= limit) */ | |||
3107 | if (i > 0) break; | |||
3108 | ||||
3109 | --uz; | |||
3110 | } | |||
3111 | ||||
3112 | if (pad != 0 && (buf[pos - 1] >> (CHAR_BIT8 - 1))) { | |||
3113 | if (pos < limit) | |||
3114 | buf[pos++] = 0; | |||
3115 | else | |||
3116 | uz = 1; | |||
3117 | } | |||
3118 | ||||
3119 | /* Digits are in reverse order, fix that */ | |||
3120 | REV(unsigned char, buf, pos)do{ unsigned char *u_ = (buf), *v_ = u_ + (pos) - 1; while (u_ < v_) { unsigned char xch = *u_; *u_++ = *v_; *v_-- = xch ; } } while(0); | |||
3121 | ||||
3122 | /* Return the number of bytes actually written */ | |||
3123 | *limpos = pos; | |||
3124 | ||||
3125 | return (uz == 0) ? MP_OK : MP_TRUNC; | |||
3126 | } | |||
3127 | ||||
3128 | #if DEBUG | |||
3129 | void s_print(char *tag, mp_int z) | |||
3130 | { | |||
3131 | int i; | |||
3132 | ||||
3133 | fprintf(stderr, "%s: %c ", tag, | |||
3134 | (MP_SIGN(z)((z)->sign) == MP_NEG) ? '-' : '+'); | |||
3135 | ||||
3136 | for (i = MP_USED(z)((z)->used) - 1; i >= 0; --i) | |||
3137 | fprintf(stderr, "%0*X", (int)(MP_DIGIT_BIT(sizeof(mp_digit) * 8) / 4), z->digits[i]); | |||
3138 | ||||
3139 | fputc('\n', stderr); | |||
3140 | ||||
3141 | } | |||
3142 | ||||
3143 | void s_print_buf(char *tag, mp_digit *buf, mp_size num) | |||
3144 | { | |||
3145 | int i; | |||
3146 | ||||
3147 | fprintf(stderr, "%s: ", tag); | |||
3148 | ||||
3149 | for (i = num - 1; i >= 0; --i) | |||
3150 | fprintf(stderr, "%0*X", (int)(MP_DIGIT_BIT(sizeof(mp_digit) * 8) / 4), buf[i]); | |||
3151 | ||||
3152 | fputc('\n', stderr); | |||
3153 | } | |||
3154 | #endif | |||
3155 | ||||
3156 | /* Here there be dragons */ |