include/flint/flint.h

0001 /*
0002     Copyright (C) 2009 William Hart
0003
0004     This file is part of FLINT.
0005
0006     FLINT is free software: you can redistribute it and/or modify it under
0007     the terms of the GNU Lesser General Public License (LGPL) as published
0008     by the Free Software Foundation; either version 3 of the License, or
0009     (at your option) any later version.  See <https://www.gnu.org/licenses/>.
0010 */
0011
0012 #ifndef FLINT_H
0013 #define FLINT_H
0014
0015 #ifndef FLINT_NOSTDIO
0016 # include <stdio.h>
0017 #endif
0018
0019 #ifndef FLINT_NOSTDARG
0020 # include <stdarg.h>
0021 #endif
0022
0023 #include <stddef.h>
0024 #ifdef BUILDING_FLINT
0025 # include "config.h"
0026 #else
0027 # include "flint-config.h"
0028 #endif
0029
0030 #if FLINT_USES_GC
0031 # include "gc.h"
0032 #endif
0033
0034 #if FLINT_WANT_ASSERT
0035 # include <assert.h>
0036 #endif
0037
0038 #ifndef FLINT_DLL
0039 # define FLINT_DLL
0040 #endif
0041
0042 #ifndef alloca
0043 # ifdef __GNUC__
0044 #  define alloca __builtin_alloca
0045 # else
0046 #  ifdef _MSC_VER
0047 #   include <malloc.h>
0048 #   define alloca _alloca
0049 #  else
0050 #   include <alloca.h> /* We assume then that you have alloca.h */
0051 #  endif
0052 # endif
0053 #endif
0054
0055 #ifdef va_start
0056 # define FLINT_HAVE_VA_LIST 1
0057 #endif
0058
0059 #if defined(FILE)       || defined(_FILE_DEFINED) || defined(__DEFINED_FILE) \
0060  || defined(H_STDIO)    || defined(_H_STDIO)      || defined(_STDIO_H)       \
0061  || defined(_STDIO_H_)  || defined(__STDIO_H)     || defined(__STDIO_H__)    \
0062  || defined(__STDIO__)
0063 # define FLINT_HAVE_FILE 1
0064 #endif
0065
0066 #ifdef FLINT_INLINES_C
0067 # define FLINT_INLINE
0068 #else
0069 # define FLINT_INLINE static inline
0070 #endif
0071
0072 #ifdef __cplusplus
0073 extern "C" {
0074 #endif
0075
0076 /* FLINT version number */
0077
0078 #define __FLINT_VERSION 3
0079 #define __FLINT_VERSION_MINOR 6
0080 #define __FLINT_VERSION_PATCHLEVEL 0
0081 #define FLINT_VERSION "3.6.0"
0082 #define __FLINT_RELEASE_NUM(a,b,c) ((a)*10000 + (b)*100 + (c))
0083 #define __FLINT_RELEASE __FLINT_RELEASE_NUM(__FLINT_VERSION, __FLINT_VERSION_MINOR, __FLINT_VERSION_PATCHLEVEL)
0084
0085 FLINT_DLL extern char flint_version[];
0086
0087 struct __FLINT_FILE;
0088 typedef struct __FLINT_FILE FLINT_FILE;
0089
0090 #if FLINT_LONG_LONG
0091 typedef unsigned long long int ulong;
0092 typedef long long int slong;
0093 #else
0094 typedef unsigned long int ulong;
0095 typedef long int slong;
0096 #endif
0097
0098 typedef ulong flint_bitcnt_t;
0099 typedef ulong * nn_ptr;
0100 typedef const ulong * nn_srcptr;
0101
0102 #if FLINT_WANT_ASSERT
0103 # define FLINT_ASSERT(param) assert(param)
0104 #else
0105 # define FLINT_ASSERT(param)
0106 #endif
0107
0108 #if defined(__GNUC__)
0109 # define FLINT_FORCE_INLINE static __attribute__((always_inline)) inline
0110 # define FLINT_STATIC_NOINLINE static __attribute__((noinline))
0111 # if !FLINT_WANT_ASSERT
0112 #  define FLINT_UNUSED(x) UNUSED_ ## x __attribute__((unused))
0113 # else
0114    /* NOTE: This may or may not be required as some function inputs may be used
0115     * for assertions. */
0116 #  define FLINT_UNUSED(x) x
0117 # endif
0118 # define FLINT_SET_BUT_UNUSED(x) x __attribute__((unused))
0119 # define FLINT_CONST __attribute__ ((const))
0120 # define FLINT_WARN_UNUSED __attribute__((warn_unused_result))
0121 # define FLINT_UNLIKELY(x) __builtin_expect((x),0)
0122 # define FLINT_LIKELY(x) __builtin_expect((x),1)
0123 # define FLINT_CONSTANT_P __builtin_constant_p
0124 # define FLINT_UNREACHABLE __builtin_unreachable()
0125 # define FLINT_RETURNS_NONNULL __attribute__((returns_nonnull))
0126 # define FLINT_MALLOC __attribute__((malloc))
0127 # define FLINT_DEPRECATED __attribute__((deprecated))
0128 # define FLINT_FALLTHROUGH __attribute__((fallthrough))
0129 #else
0130 # define __attribute__(x)
0131 # if defined(_MSC_VER)
0132 #  define FLINT_FORCE_INLINE static __forceinline
0133 #  define FLINT_UNREACHABLE __assume(0)
0134 # else
0135 #  define FLINT_FORCE_INLINE static inline
0136 #  define FLINT_UNREACHABLE
0137 # endif
0138 # define FLINT_STATIC_NOINLINE static
0139 # define FLINT_UNUSED(x) x
0140 # define FLINT_SET_BUT_UNUSED(x) x
0141 # define FLINT_WARN_UNUSED
0142 # define FLINT_CONST
0143 # define FLINT_UNLIKELY(x) (x)
0144 # define FLINT_LIKELY(x) (x)
0145 # define FLINT_CONSTANT_P(x) 0
0146 # define FLINT_RETURNS_NONNULL
0147 # define FLINT_MALLOC
0148 # define FLINT_DEPRECATED
0149 # define FLINT_FALLTHROUGH
0150 #endif
0151
0152 #if defined(__cplusplus) || ( __STDC_VERSION__ >= 202300L )
0153 # define FLINT_NORETURN [[noreturn]]
0154 #else
0155 # define FLINT_NORETURN _Noreturn
0156 #endif
0157
0158 #if FLINT_USES_TLS
0159 # if __STDC_VERSION__ < 202300L && !defined(__cplusplus)
0160 #  define FLINT_TLS_PREFIX _Thread_local
0161 # else
0162 #  define FLINT_TLS_PREFIX thread_local
0163 # endif
0164 #else
0165 # define FLINT_TLS_PREFIX
0166 #endif
0167
0168 #if FLINT_LONG_LONG
0169 # define _WORD_FMT "ll"
0170 # define WORD_FMT "%ll"
0171 # define WORD_WIDTH_FMT "%*ll"
0172 # define WORD(xx) (xx##LL)
0173 # define UWORD(xx) (xx##ULL)
0174 #else
0175 # define _WORD_FMT "l"
0176 # define WORD_FMT "%l"
0177 # define WORD_WIDTH_FMT "%*l"
0178 # define WORD(xx) (xx##L)
0179 # define UWORD(xx) (xx##UL)
0180 #endif
0181
0182 #if FLINT_BITS == 64
0183 # define FLINT_D_BITS 53
0184 # define FLINT64 1
0185 # ifndef FLINT_NO_WORDMAC
0186 #  define UWORD_MAX UWORD(18446744073709551615)
0187 #  define UWORD_MIN UWORD(0)
0188 #  define WORD_MAX WORD(9223372036854775807)
0189 #  define WORD_MIN (-WORD_MAX - WORD(1))
0190 # endif
0191 #else
0192 # define FLINT_D_BITS 31
0193 # ifndef FLINT_NO_WORDMAC
0194 #  define UWORD_MAX UWORD(4294967295)
0195 #  define UWORD_MIN UWORD(0)
0196 #  define WORD_MAX WORD(2147483647)
0197 #  define WORD_MIN (-WORD_MAX - WORD(1))
0198 # endif
0199 #endif
0200
0201 /* memory ********************************************************************/
0202
0203 FLINT_WARN_UNUSED FLINT_MALLOC FLINT_RETURNS_NONNULL void * flint_malloc(size_t size);
0204 FLINT_WARN_UNUSED FLINT_RETURNS_NONNULL void * flint_realloc(void * ptr, size_t size);
0205 FLINT_WARN_UNUSED FLINT_RETURNS_NONNULL void * flint_calloc(size_t num, size_t size);
0206 void flint_free(void * ptr);
0207 FLINT_WARN_UNUSED FLINT_MALLOC FLINT_RETURNS_NONNULL void * flint_aligned_alloc(size_t alignment, size_t size);
0208 void flint_aligned_free(void * ptr);
0209
0210 typedef void (*flint_cleanup_function_t)(void);
0211 void flint_register_cleanup_function(flint_cleanup_function_t cleanup_function);
0212 void flint_cleanup(void);
0213 void flint_cleanup_master(void);
0214
0215 void __flint_set_all_memory_functions(
0216         void * (* alloc_func)(size_t),
0217         void * (* calloc_func)(size_t, size_t),
0218         void * (* realloc_func)(void *, size_t),
0219         void (* free_func)(void *),
0220         void * (* aligned_alloc_func)(size_t, size_t),
0221         void (* aligned_free_func)(void *));
0222
0223 void __flint_get_all_memory_functions(
0224         void * (** alloc_func)(size_t),
0225         void * (** calloc_func)(size_t, size_t),
0226         void * (** realloc_func)(void *, size_t),
0227         void (** free_func)(void *),
0228         void * (** aligned_alloc_func)(size_t, size_t),
0229         void (** aligned_free_func)(void *));
0230
0231 void __flint_set_memory_functions(
0232         void * (* alloc_func)(size_t),
0233         void * (* calloc_func)(size_t, size_t),
0234         void * (* realloc_func)(void *, size_t),
0235         void (* free_func)(void *));
0236
0237 void __flint_get_memory_functions(
0238         void * (** alloc_func)(size_t),
0239         void * (** calloc_func)(size_t, size_t),
0240         void * (** realloc_func)(void *, size_t),
0241         void (** free_func)(void *));
0242
0243 FLINT_NORETURN void flint_abort(void);
0244
0245 void flint_set_abort(void (*func)(void));
0246
0247 /* threads *******************************************************************/
0248
0249 int flint_get_num_threads(void);
0250 void flint_set_num_threads(int num_threads);
0251 void _flint_set_num_workers(int num_workers);
0252 int flint_set_num_workers(int num_workers);
0253 void flint_reset_num_workers(int max_workers);
0254 int flint_set_thread_affinity(int * cpus, slong length);
0255 int flint_restore_thread_affinity(void);
0256
0257 typedef int thread_pool_handle;
0258
0259 /* randomization and test utilities ******************************************/
0260
0261 FLINT_CONST double flint_test_multiplier(void);
0262
0263 typedef struct
0264 {
0265     void * __gmp_state;
0266     ulong __randval;
0267     ulong __randval2;
0268 }
0269 flint_rand_struct;
0270
0271 typedef flint_rand_struct flint_rand_t[1];
0272
0273 FLINT_INLINE
0274 void flint_rand_init(flint_rand_t state)
0275 {
0276     state->__gmp_state = NULL;
0277 #if FLINT64
0278     state->__randval = UWORD(13845646450878251009);
0279     state->__randval2 = UWORD(13142370077570254774);
0280 #else
0281     state->__randval = UWORD(4187301858);
0282     state->__randval2 = UWORD(3721271368);
0283 #endif
0284 }
0285
0286 FLINT_INLINE
0287 void flint_rand_set_seed(flint_rand_t state, ulong seed1, ulong seed2)
0288 {
0289     state->__randval = seed1;
0290     state->__randval2 = seed2;
0291 }
0292
0293 FLINT_INLINE
0294 void flint_rand_get_seed(ulong * seed1, ulong * seed2, flint_rand_t state)
0295 {
0296     *seed1 = state->__randval;
0297     *seed2 = state->__randval2;
0298 }
0299
0300 /* __gmp_state is deprecated; don't clean it up */
0301 FLINT_INLINE void flint_rand_clear(flint_rand_t FLINT_UNUSED(state)) { }
0302
0303 FLINT_DEPRECATED void _flint_rand_init_gmp_state(flint_rand_t state);
0304 FLINT_DEPRECATED void _flint_rand_clear_gmp_state(flint_rand_t state);
0305 FLINT_DEPRECATED void flint_randinit(flint_rand_t);
0306 FLINT_DEPRECATED void flint_randclear(flint_rand_t);
0307 FLINT_DEPRECATED void flint_randseed(flint_rand_t, ulong, ulong);
0308 FLINT_DEPRECATED void flint_get_randseed(ulong *, ulong *, flint_rand_t);
0309 FLINT_DEPRECATED flint_rand_struct * flint_rand_alloc(void);
0310 FLINT_DEPRECATED void flint_rand_free(flint_rand_struct * state);
0311
0312 /* defined in ulong_extras, but used throughout the test code */
0313 ulong n_randlimb(flint_rand_t);
0314 ulong n_randtest(flint_rand_t);
0315 ulong n_randtest_not_zero(flint_rand_t);
0316 ulong n_randint(flint_rand_t state, ulong limit);
0317
0318 #if FLINT_USES_GC
0319 # define FLINT_GC_INIT() GC_init()
0320 #else
0321 # define FLINT_GC_INIT()
0322 #endif
0323
0324 #define FLINT_TEST_INIT(xxx) \
0325    flint_rand_t xxx; \
0326    FLINT_GC_INIT(); \
0327    flint_rand_init(xxx)
0328
0329 #define FLINT_TEST_CLEAR(xxx) \
0330    flint_rand_clear(xxx); \
0331    flint_cleanup_master();
0332
0333 /* comparison macros *********************************************************/
0334
0335 #define FLINT_MAX(x, y) ((x) > (y) ? (x) : (y))
0336 #define FLINT_MIN(x, y) ((x) > (y) ? (y) : (x))
0337 #define FLINT_ABS(x) ((slong)(x) < 0 ? (-(x)) : (x))
0338 #define FLINT_UABS(x) (((slong)(x) < 0) ? (-(ulong)(x)) : ((ulong)(x)))
0339 #define FLINT_SIGN_EXT(x) (-(ulong)((slong)(x) < 0))
0340 #define FLINT_SGN(x) ((0 < (slong)(x)) - ((slong)(x) < 0))
0341 #define FLINT_SWAP(T, x, y) do { T _swap_t = (x); (x) = (y); (y) = _swap_t; } while(0)
0342
0343 /* sorting *******************************************************************/
0344
0345 void flint_merge_sort(void * buf, slong len, slong size, int (* cmp) (const void *, const void *, void *), void * data);
0346 void flint_sort(void * buf, slong len, slong size, int (* cmp) (const void *, const void *, void *), void * data);
0347
0348 /* allocation macros *********************************************************/
0349
0350 #define FLINT_ARRAY_ALLOC(n, T) (T *) flint_malloc((n)*sizeof(T))
0351 #define FLINT_ARRAY_REALLOC(p, n, T) (T *) flint_realloc(p, (n)*sizeof(T))
0352
0353 #define TMP_INIT \
0354    typedef struct __tmp_struct { \
0355       void * block; \
0356       struct __tmp_struct * next; \
0357    } __tmp_t; \
0358    __tmp_t * __tmp_root; \
0359    __tmp_t * __tpx
0360
0361 #define TMP_START \
0362    __tmp_root = NULL
0363
0364 #ifdef FLINT_WANT_ASSERT
0365 #define TMP_ALLOC(size) \
0366    (__tpx = (__tmp_t *) alloca(sizeof(__tmp_t)), \
0367        __tpx->next = __tmp_root, \
0368        __tmp_root = __tpx, \
0369        __tpx->block = flint_malloc(size))
0370 #else
0371 #define TMP_ALLOC(size) \
0372    (((size) > 8192) ? \
0373       (__tpx = (__tmp_t *) alloca(sizeof(__tmp_t)), \
0374        __tpx->next = __tmp_root, \
0375        __tmp_root = __tpx, \
0376        __tpx->block = flint_malloc(size)) : \
0377       alloca(size))
0378 #endif
0379
0380 #define TMP_ARRAY_ALLOC(n, T) (T *) TMP_ALLOC((n)*sizeof(T))
0381
0382 #define TMP_END \
0383    while (__tmp_root) { \
0384       flint_free(__tmp_root->block); \
0385       __tmp_root = __tmp_root->next; \
0386    }
0387
0388 /* downstream support ********************************************************/
0389
0390 #ifdef FLINT_HAVE_VA_LIST
0391 void flint_va_end(va_list vlist);
0392 #endif
0393
0394 /* I/O ***********************************************************************/
0395
0396 int parse_fmt(int * floating, const char * fmt);
0397
0398 int flint_printf(const char * str, ...);
0399 int flint_sprintf(char * s, const char * str, ...);
0400 int flint_snprintf(char * s, size_t n, const char * str, ...);
0401 int flint_scanf(const char * str, ...);
0402 int flint_sscanf(const char * s, const char * str, ...);
0403
0404 #if FLINT_HAVE_VA_LIST
0405 int flint_vprintf(const char * str, va_list ap);
0406 int flint_vsprintf(char * s, const char * str, va_list ap);
0407 int flint_vsnprintf(char * s, size_t n, const char * str, va_list ap);
0408 #endif
0409
0410 #if FLINT_HAVE_FILE
0411 int flint_fprintf(FILE * f, const char * str, ...);
0412 int flint_fscanf(FILE * f, const char * str, ...);
0413 #endif
0414
0415 #if FLINT_HAVE_VA_LIST && FLINT_HAVE_FILE
0416 int flint_vfprintf(FILE * f, const char * str, va_list ap);
0417 #endif
0418
0419 /* exceptions ****************************************************************/
0420
0421 typedef enum
0422 {
0423    FLINT_ERROR,     /* general error */
0424    FLINT_OVERFLOW,  /* overflow */
0425    FLINT_IMPINV,    /* impossible inverse */
0426    FLINT_DOMERR,    /* domain error */
0427    FLINT_DIVZERO,   /* divide by zero */
0428    FLINT_EXPOF,     /* exponent overflow */
0429    FLINT_INEXACT,   /* inexact error */
0430    FLINT_TEST_FAIL  /* test fail */
0431 } flint_err_t;
0432
0433 FLINT_NORETURN void flint_throw(flint_err_t exc, const char * msg, ...);
0434
0435 #if FLINT_HAVE_VA_LIST
0436 void flint_set_throw(void (* func)(flint_err_t, const char *, va_list));
0437 #endif
0438
0439 /* FLINT generic type definitions ********************************************/
0440
0441 typedef struct
0442 {
0443    ulong n;
0444    ulong ninv;
0445    flint_bitcnt_t norm;
0446 }
0447 nmod_t;
0448
0449 typedef slong fmpz;
0450 typedef fmpz fmpz_t[1];
0451
0452 typedef struct
0453 {
0454     fmpz num;
0455     fmpz den;
0456 }
0457 fmpq;
0458
0459 typedef fmpq fmpq_t[1];
0460
0461 #define fmpq_numref(__x) (&(__x)->num)
0462 #define fmpq_denref(__y) (&(__y)->den)
0463
0464 /* fmpz macros ***************************************************************/
0465
0466 /* The largest bit count for an fmpz to be small */
0467 #define SMALL_FMPZ_BITCOUNT_MAX (FLINT_BITS - 2)
0468
0469 /* Minimum and maximum value for a small fmpz */
0470 #define COEFF_MIN (-((WORD(1) << SMALL_FMPZ_BITCOUNT_MAX) - WORD(1)))
0471 #define COEFF_MAX ((WORD(1) << SMALL_FMPZ_BITCOUNT_MAX) - WORD(1))
0472
0473 /* Conversions between mpz_ptr and fmpz_t */
0474 #define PTR_TO_COEFF(x) (((ulong) (x) >> 2) | (WORD(1) << (FLINT_BITS - 2)))
0475 #define COEFF_TO_PTR(x) ((mpz_ptr) ((ulong) (x) << 2))
0476
0477 #define COEFF_IS_MPZ(x) (((x) >> SMALL_FMPZ_BITCOUNT_MAX) == WORD(1))
0478
0479 /* The minimum number of limbs that the fmpz collector should spit out */
0480 #define MPZ_MIN_ALLOC 2
0481
0482 /* NOTE: Never allocate less than MPZ_MIN_ALLOC */
0483 #define FLINT_MPZ_REALLOC(ptr, sz) ((int) (sz) > ((ptr)->_mp_alloc) ? (mp_ptr) mpz_realloc(ptr, sz) : (ptr)->_mp_d)
0484 #define FLINT_MPZ_REALLOC_TIGHT(ptr, sz) ((mp_ptr) mpz_realloc(ptr, FLINT_MAX(sz, MPZ_MIN_ALLOC)))
0485
0486 #ifdef __cplusplus
0487 }
0488 #endif
0489
0490 #endif