1 /*
2 Copyright (C) 2009 William Hart
3
4 This file is part of FLINT.
5
6 FLINT is free software: you can redistribute it and/or modify it under
7 the terms of the GNU Lesser General Public License (LGPL) as published
8 by the Free Software Foundation; either version 2.1 of the License, or
9 (at your option) any later version. See <http://www.gnu.org/licenses/>.
10 */
11
12 #ifndef FLINT_H
13 #define FLINT_H
14
15 #undef ulong
16 #define ulong ulongxx /* ensure vendor doesn't typedef ulong */
17 #if !defined(_MSC_VER)
18 #include <sys/param.h> /* for BSD define */
19 #endif
20 #include <gmp.h>
21 #include <mpfr.h>
22 #include <stdarg.h>
23 #include <stdio.h>
24 #include <stdlib.h> /* for alloca on FreeBSD */
25 #if (!defined(BSD) && !defined(__MINGW64__) && !defined(__MINGW32__) && !defined(_MSC_VER)) || defined(__GNU__)
26 /* MinGW and FreeBSD have alloca, but not alloca.h */
27 #include <alloca.h>
28 #endif
29 #if defined(__MINGW32__)
30 #include <malloc.h> /* for alloca on MinGW */
31 #endif
32 #include "limits.h"
33 #include "longlong.h"
34 #include "flint-config.h"
35 #undef ulong
36
37 #ifdef FLINT_INLINES_C
38 #define FLINT_INLINE FLINT_DLL
39 #else
40 #define FLINT_INLINE static __inline__
41 #endif
42
43 #if HAVE_GC
44 #include "gc.h"
45 #endif
46
47 #if WANT_ASSERT
48 #include <assert.h>
49 #endif
50
51 #ifdef __cplusplus
52 extern "C" {
53 #endif
54
55 /* flint version number */
56
57 #define __FLINT_VERSION 2
58 #define __FLINT_VERSION_MINOR 6
59 #define __FLINT_VERSION_PATCHLEVEL 0
60 #define FLINT_VERSION "2.6.0"
61 #define __FLINT_RELEASE (__FLINT_VERSION * 10000 + \
62 __FLINT_VERSION_MINOR * 100 + \
63 __FLINT_VERSION_PATCHLEVEL)
64
65 /*
66 Check mpir and mpfr version numbers
67 */
68 #if __GNU_MP_VERSION < 5
69 #error GMP 5.0.0 or MPIR 2.6.0 or later are required
70 #endif
71
72 #if MPFR_VERSION_MAJOR < 3
73 #error MPFR 3.0.0 or later is required
74 #endif
75
76 /*
77 We define alternative key words for "asm" and "inline", allowing
78 the code to be compiled with the "-ansi" flag under GCC
79 */
80 #ifndef __GNUC__
81 #define __asm__ asm
82 #define __inline__ inline
83 #endif
84
85 extern char flint_version[];
86
87 #define ulong mp_limb_t
88 #define slong mp_limb_signed_t
89
90 FLINT_DLL void * flint_malloc(size_t size);
91 FLINT_DLL void * flint_realloc(void * ptr, size_t size);
92 FLINT_DLL void * flint_calloc(size_t num, size_t size);
93 FLINT_DLL void flint_free(void * ptr);
94
95 typedef void (*flint_cleanup_function_t)(void);
96 FLINT_DLL void flint_register_cleanup_function(flint_cleanup_function_t cleanup_function);
97 FLINT_DLL void flint_cleanup(void);
98 FLINT_DLL void flint_cleanup_master(void);
99
100 FLINT_DLL void __flint_set_memory_functions(void *(*alloc_func) (size_t),
101 void *(*calloc_func) (size_t, size_t), void *(*realloc_func) (void *, size_t),
102 void (*free_func) (void *));
103
104 #ifdef __GNUC__
105 #define FLINT_NORETURN __attribute__ ((noreturn))
106 #else
107 #define FLINT_NORETURN
108 #endif
109
110 FLINT_DLL FLINT_NORETURN void flint_abort(void);
111 FLINT_DLL void flint_set_abort(FLINT_NORETURN void (*func)(void));
112 /* flint_abort is calling abort by default
113 * if flint_set_abort is used, then instead of abort this function
114 * is called. EXPERIMENTALLY use at your own risk!
115 * May disappear in future versions.
116 */
117
118
119 #if defined(_WIN64) || defined(__mips64)
120 #if defined(__MINGW64__)
121 #define WORD_FMT "%I64"
122 #define WORD_WIDTH_FMT "%*I64"
123 #else
124 #define WORD_FMT "%ll"
125 #define WORD_WIDTH_FMT "%*ll"
126 #endif
127 #define WORD(xx) (xx##LL)
128 #define UWORD(xx) (xx##ULL)
129 #ifndef FLINT_NO_WORDMAC
130 #define UWORD_MAX ULLONG_MAX
131 #define UWORD_MIN ULLONG_MIN
132 #define WORD_MAX LLONG_MAX
133 #define WORD_MIN LLONG_MIN
134 #endif
135 #else
136 #define WORD_FMT "%l"
137 #define WORD_WIDTH_FMT "%*l"
138 #define WORD(xx) (xx##L)
139 #define UWORD(xx) (xx##UL)
140 #ifndef FLINT_NO_WORDMAC
141 #define UWORD_MAX ULONG_MAX
142 #define UWORD_MIN ULONG_MIN
143 #define WORD_MAX LONG_MAX
144 #define WORD_MIN LONG_MIN
145 #endif
146 #endif
147
148 #if GMP_LIMB_BITS == 64
149 #define FLINT_BITS 64
150 #define FLINT_D_BITS 53
151 #define FLINT64 1
152 #else
153 #define FLINT_BITS 32
154 #define FLINT_D_BITS 31
155 #endif
156
157 #define flint_bitcnt_t ulong
158
159 #if HAVE_TLS
160 #if __STDC_VERSION__ >= 201112L
161 #define FLINT_TLS_PREFIX _Thread_local
162 #elif defined(_MSC_VER)
163 #define FLINT_TLS_PREFIX __declspec(thread)
164 #elif defined(__GNUC__)
165 #define FLINT_TLS_PREFIX __thread
166 #else
167 #error "thread local prefix defined in C11 or later"
168 #endif
169 #else
170 #define FLINT_TLS_PREFIX
171 #endif
172
173 FLINT_DLL int flint_get_num_threads(void);
174 FLINT_DLL void flint_set_num_threads(int num_threads);
175 FLINT_DLL void _flint_set_num_workers(int num_workers);
176 FLINT_DLL int flint_set_num_workers(int num_workers);
177 FLINT_DLL void flint_reset_num_workers(int max_workers);
178 FLINT_DLL int flint_set_thread_affinity(int * cpus, slong length);
179 FLINT_DLL int flint_restore_thread_affinity();
180
181 int flint_test_multiplier(void);
182
183 typedef struct
184 {
185 gmp_randstate_t gmp_state;
186 int gmp_init;
187 mp_limb_t __randval;
188 mp_limb_t __randval2;
189 } flint_rand_s;
190
191 typedef flint_rand_s flint_rand_t[1];
192
193 FLINT_INLINE
flint_randinit(flint_rand_t state)194 void flint_randinit(flint_rand_t state)
195 {
196 state->gmp_init = 0;
197 #if FLINT64
198 state->__randval = UWORD(13845646450878251009);
199 state->__randval2 = UWORD(13142370077570254774);
200 #else
201 state->__randval = UWORD(4187301858);
202 state->__randval2 = UWORD(3721271368);
203 #endif
204 }
205
206 FLINT_INLINE
flint_randseed(flint_rand_t state,ulong seed1,ulong seed2)207 void flint_randseed(flint_rand_t state, ulong seed1, ulong seed2)
208 {
209 state->__randval = seed1;
210 state->__randval2 = seed2;
211 }
212
213 FLINT_INLINE
flint_get_randseed(ulong * seed1,ulong * seed2,flint_rand_t state)214 void flint_get_randseed(ulong * seed1, ulong * seed2, flint_rand_t state)
215 {
216 *seed1 = state->__randval;
217 *seed2 = state->__randval2;
218 }
219
220
221 FLINT_INLINE
_flint_rand_init_gmp(flint_rand_t state)222 void _flint_rand_init_gmp(flint_rand_t state)
223 {
224 if (!state->gmp_init)
225 {
226 gmp_randinit_default(state->gmp_state);
227 state->gmp_init = 1;
228 }
229 }
230
231 FLINT_INLINE
flint_randclear(flint_rand_t state)232 void flint_randclear(flint_rand_t state)
233 {
234 if (state->gmp_init)
235 gmp_randclear(state->gmp_state);
236 }
237
238 FLINT_INLINE
flint_rand_alloc(void)239 flint_rand_s * flint_rand_alloc(void)
240 {
241 return (flint_rand_s *) flint_malloc(sizeof(flint_rand_s));
242 }
243
244 FLINT_INLINE
flint_rand_free(flint_rand_s * state)245 void flint_rand_free(flint_rand_s * state)
246 {
247 flint_free(state);
248 }
249
250 #if HAVE_GC
251 #define FLINT_GC_INIT() GC_init()
252 #else
253 #define FLINT_GC_INIT()
254 #endif
255
256 #define FLINT_TEST_INIT(xxx) \
257 flint_rand_t xxx; \
258 FLINT_GC_INIT(); \
259 flint_randinit(xxx)
260
261 #define FLINT_TEST_CLEANUP(xxx) \
262 flint_randclear(xxx); \
263 flint_cleanup_master();
264
265 /*
266 We define this here as there is no mpfr.h
267 */
268 typedef __mpfr_struct flint_mpfr;
269
270 #if WANT_ASSERT
271 #define FLINT_ASSERT(param) assert(param)
272 #else
273 #define FLINT_ASSERT(param)
274 #endif
275
276 #if defined(__GNUC__)
277 #define FLINT_UNUSED(x) UNUSED_ ## x __attribute__((unused))
278 #define FLINT_SET_BUT_UNUSED(x) x __attribute__((unused))
279 #if __GNUC__ >= 4
280 #define FLINT_WARN_UNUSED __attribute__((warn_unused_result))
281 #else
282 #define FLINT_WARN_UNUSED
283 #endif
284 #else
285 #define __attribute__(x)
286 #define FLINT_UNUSED(x) x
287 #define FLINT_SET_BUT_UNUSED(x) x
288 #define FLINT_WARN_UNUSED
289 #endif
290
291 #define FLINT_MAX(x, y) ((x) > (y) ? (x) : (y))
292 #define FLINT_MIN(x, y) ((x) > (y) ? (y) : (x))
293 #define FLINT_ABS(x) ((slong)(x) < 0 ? (-(x)) : (x))
294 #define FLINT_SIGN_EXT(x) (-(ulong)((slong)(x) < 0))
295
296 #define MP_PTR_SWAP(x, y) \
297 do { \
298 mp_limb_t * __txxx; \
299 __txxx = x; \
300 x = y; \
301 y = __txxx; \
302 } while (0)
303
304 #define r_shift(in, shift) \
305 ((shift == FLINT_BITS) ? WORD(0) : ((in) >> (shift)))
306
307 #define l_shift(in, shift) \
308 ((shift == FLINT_BITS) ? WORD(0) : ((in) << (shift)))
309
310 #ifdef NEED_CLZ_TAB
311 FLINT_DLL extern const unsigned char __flint_clz_tab[128];
312 #endif
313
314 static __inline__
FLINT_BIT_COUNT(mp_limb_t x)315 mp_limb_t FLINT_BIT_COUNT(mp_limb_t x)
316 {
317 mp_limb_t zeros = FLINT_BITS;
318 if (x) count_leading_zeros(zeros, x);
319 return FLINT_BITS - zeros;
320 }
321
322 #define FLINT_FLOG2(k) (FLINT_BIT_COUNT(k) - 1)
323
324 #define FLINT_CLOG2(k) FLINT_BIT_COUNT((k) - 1)
325
326 #define flint_mpn_zero(xxx, nnn) \
327 do \
328 { \
329 slong ixxx; \
330 for (ixxx = 0; ixxx < (nnn); ixxx++) \
331 (xxx)[ixxx] = UWORD(0); \
332 } while (0)
333
334 #define flint_mpn_copyi(xxx, yyy, nnn) \
335 do { \
336 slong ixxx; \
337 for (ixxx = 0; ixxx < (nnn); ixxx++) \
338 (xxx)[ixxx] = (yyy)[ixxx]; \
339 } while (0)
340
341 #define flint_mpn_copyd(xxx, yyy, nnn) \
342 do { \
343 slong ixxx; \
344 for (ixxx = nnn - 1; ixxx >= 0; ixxx--) \
345 (xxx)[ixxx] = (yyy)[ixxx]; \
346 } while (0)
347
348 #define flint_mpn_store(xxx, nnn, yyy) \
349 do \
350 { \
351 slong ixxx; \
352 for (ixxx = 0; ixxx < nnn; ixxx++) \
353 (xxx)[ixxx] = yyy; \
354 } while (0)
355
356 /* temporary allocation */
357 #define TMP_INIT \
358 typedef struct __tmp_struct { \
359 void * block; \
360 struct __tmp_struct * next; \
361 } __tmp_t; \
362 __tmp_t * __tmp_root; \
363 __tmp_t * __tpx
364
365 #define TMP_START \
366 __tmp_root = NULL
367
368 #if WANT_ASSERT
369 #define TMP_ALLOC(size) \
370 (__tpx = (__tmp_t *) alloca(sizeof(__tmp_t)), \
371 __tpx->next = __tmp_root, \
372 __tmp_root = __tpx, \
373 __tpx->block = flint_malloc(size))
374 #else
375 #define TMP_ALLOC(size) \
376 (((size) > 8192) ? \
377 (__tpx = (__tmp_t *) alloca(sizeof(__tmp_t)), \
378 __tpx->next = __tmp_root, \
379 __tmp_root = __tpx, \
380 __tpx->block = flint_malloc(size)) : \
381 alloca(size))
382 #endif
383
384
385 #define TMP_END \
386 while (__tmp_root) { \
387 flint_free(__tmp_root->block); \
388 __tmp_root = __tmp_root->next; \
389 }
390
391 /* compatibility between gmp and mpir */
392 #ifndef mpn_com_n
393 #define mpn_com_n mpn_com
394 #endif
395
396 #ifndef mpn_neg_n
397 #define mpn_neg_n mpn_neg
398 #endif
399
400 #ifndef mpn_tdiv_q
401 /* substitute for mpir's mpn_tdiv_q */
402 static __inline__ void
mpn_tdiv_q(mp_ptr qp,mp_srcptr np,mp_size_t nn,mp_srcptr dp,mp_size_t dn)403 mpn_tdiv_q(mp_ptr qp, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
404 {
405 mp_ptr _scratch;
406 TMP_INIT;
407 TMP_START;
408 _scratch = (mp_ptr) TMP_ALLOC(dn * sizeof(mp_limb_t));
409 mpn_tdiv_qr(qp, _scratch, 0, np, nn, dp, dn);
410 TMP_END;
411 }
412 #endif
413
414 /* Newton iteration macros */
415 #define FLINT_NEWTON_INIT(from, to) \
416 { \
417 slong __steps[FLINT_BITS], __i, __from, __to; \
418 __steps[__i = 0] = __to = (to); \
419 __from = (from); \
420 while (__to > __from) \
421 __steps[++__i] = (__to = (__to + 1) / 2); \
422
423 #define FLINT_NEWTON_BASECASE(bc_to) { slong bc_to = __to;
424
425 #define FLINT_NEWTON_END_BASECASE }
426
427 #define FLINT_NEWTON_LOOP(step_from, step_to) \
428 { \
429 for (__i--; __i >= 0; __i--) \
430 { \
431 slong step_from = __steps[__i+1]; \
432 slong step_to = __steps[__i]; \
433
434 #define FLINT_NEWTON_END_LOOP }}
435
436 #define FLINT_NEWTON_END }
437
438 FLINT_DLL int parse_fmt(int * floating, const char * fmt);
439
440 FLINT_DLL int flint_printf(const char * str, ...); /* flint version of printf */
441 FLINT_DLL int flint_vprintf(const char * str, va_list ap); /* va_list version of flint_printf */
442 FLINT_DLL int flint_fprintf(FILE * f, const char * str, ...); /* flint version of fprintf */
443 FLINT_DLL int flint_sprintf(char * s, const char * str, ...); /* flint version of sprintf */
444
445 FLINT_DLL int flint_scanf(const char * str, ...); /* flint version of scanf */
446 FLINT_DLL int flint_fscanf(FILE * f, const char * str, ...); /* flint version of fscanf */
447 FLINT_DLL int flint_sscanf(const char * s, const char * str, ...); /* flint version of sscanf */
448
flint_mul_sizes(slong x,slong y)449 FLINT_INLINE slong flint_mul_sizes(slong x, slong y)
450 {
451 ulong hi, lo;
452
453 umul_ppmm(hi, lo, (ulong) x, (ulong) y);
454 if (hi != 0 || lo > WORD_MAX)
455 {
456 flint_printf("Exception (flint). Overflow creating size %wd x %wd object.\n", x, y);
457 flint_abort();
458 }
459 return lo;
460 }
461
462 #include "gmpcompat.h"
463 #include "exception.h"
464
465 #ifdef __cplusplus
466 }
467 #endif
468
469 #endif
470