Back to index

plt-scheme  4.2.1
gmp-impl.h
Go to the documentation of this file.
00001 /* Include file for internal GNU MP types and definitions.
00002 
00003    THE CONTENTS OF THIS FILE ARE FOR INTERNAL USE AND ARE ALMOST CERTAIN TO
00004    BE SUBJECT TO INCOMPATIBLE CHANGES IN FUTURE GNU MP RELEASES.
00005 
00006 Copyright (C) 1991, 1993, 1994, 1995, 1996, 1997, 1999, 2000 Free Software
00007 Foundation, Inc.
00008 
00009 This file is part of the GNU MP Library.
00010 
00011 The GNU MP Library is free software; you can redistribute it and/or modify
00012 it under the terms of the GNU Lesser General Public License as published by
00013 the Free Software Foundation; either version 2.1 of the License, or (at your
00014 option) any later version.
00015 
00016 The GNU MP Library is distributed in the hope that it will be useful, but
00017 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
00018 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
00019 License for more details.
00020 
00021 You should have received a copy of the GNU Lesser General Public License
00022 along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
00023 the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
00024 MA 02111-1307, USA. */
00025 
00026 /* config.h.  Generated automatically by configure.  */
00027 /* config.in.  Generated automatically from configure.in by autoheader.  */
00028 /*
00029 Copyright (C) 2000 Free Software Foundation, Inc.
00030 
00031 This file is part of the GNU MP Library.
00032 
00033 The GNU MP Library is free software; you can redistribute it and/or modify
00034 it under the terms of the GNU Lesser General Public License as published by
00035 the Free Software Foundation; either version 2.1 of the License, or (at your
00036 option) any later version.
00037 
00038 The GNU MP Library is distributed in the hope that it will be useful, but
00039 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
00040 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
00041 License for more details.
00042 
00043 You should have received a copy of the GNU Lesser General Public License
00044 along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
00045 the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
00046 MA 02111-1307, USA.
00047 */
00048 
00049 /* Name of package */
00050 #define PACKAGE "gmp"
00051 
00052 /* Define if the system has the type `void'. */
00053 #define HAVE_VOID 1
00054 
00055 /* Define if cpp supports the ANSI # stringizing operator. */
00056 #define HAVE_STRINGIZE 1
00057 
00058 /* Version number of package */
00059 #define VERSION "3.1.1"
00060 
00061 #include "gmp-mparam.h"
00062 /* #include "longlong.h" */
00063 
00064 /* When using gcc, make sure to use its builtin alloca.  */
00065 #if ! defined (alloca) && defined (__GNUC__)
00066 #define alloca __builtin_alloca
00067 #define HAVE_ALLOCA
00068 #endif
00069 
00070 /* When using cc, do whatever necessary to allow use of alloca.  For many
00071    machines, this means including alloca.h.  IBM's compilers need a #pragma
00072    in "each module that needs to use alloca".  */
00073 #if ! defined (alloca)
00074 /* We need lots of variants for MIPS, to cover all versions and perversions
00075    of OSes for MIPS.  */
00076 #if defined (__mips) || defined (MIPSEL) || defined (MIPSEB) \
00077  || defined (_MIPSEL) || defined (_MIPSEB) || defined (__sgi) \
00078  || defined (__alpha) || defined (__sparc) || defined (sparc) \
00079  || defined (__ksr__)
00080 #include <alloca.h>
00081 #define HAVE_ALLOCA
00082 #endif
00083 #if defined (_IBMR2)
00084 #pragma alloca
00085 #define HAVE_ALLOCA
00086 #endif
00087 #if defined (__DECC)
00088 #define alloca(x) __ALLOCA(x)
00089 #define HAVE_ALLOCA
00090 #endif
00091 #endif
00092 
00093 #if defined (alloca)
00094 #define HAVE_ALLOCA
00095 #endif
00096 
00097 /* PLT Scheme: we turn off alloca to avoid stack-overflow issues. */
00098 #undef HAVE_ALLOCA
00099 
00100 #if ! defined (HAVE_ALLOCA) || USE_STACK_ALLOC
00101 struct tmp_stack
00102 {
00103   void *end;
00104   void *alloc_point;
00105   struct tmp_stack *prev;
00106 };
00107 
00108 struct tmp_marker
00109 {
00110   struct tmp_stack *which_chunk;
00111   void *alloc_point;
00112 };
00113 
00114 typedef struct tmp_marker tmp_marker;
00115 
00116 #if __STDC__
00117 void *__gmp_tmp_alloc (unsigned long);
00118 void __gmp_tmp_mark (tmp_marker *);
00119 void __gmp_tmp_free (tmp_marker *);
00120 #else
00121 void *__gmp_tmp_alloc ();
00122 void __gmp_tmp_mark ();
00123 void __gmp_tmp_free ();
00124 #endif
00125 
00126 #ifndef __TMP_ALIGN
00127 #define __TMP_ALIGN 8
00128 #endif
00129 
00130 #define TMP_DECL(marker) tmp_marker marker
00131 #define TMP_ALLOC(size) \
00132   __gmp_tmp_alloc (((unsigned long) (size) + __TMP_ALIGN - 1) & -__TMP_ALIGN)
00133 #define TMP_MARK(marker) __gmp_tmp_mark (&marker)
00134 #define TMP_FREE(marker) __gmp_tmp_free (&marker)
00135 #else
00136 #define TMP_DECL(m)
00137 #define TMP_ALLOC(x) alloca(x)
00138 #define TMP_MARK(m)
00139 #define TMP_FREE(m)
00140 #endif
00141 
00142 /* Allocating various types. */
00143 #define TMP_ALLOC_TYPE(n,type) ((type *) TMP_ALLOC ((n) * sizeof (type)))
00144 #define TMP_ALLOC_LIMBS(n)     TMP_ALLOC_TYPE(n,mp_limb_t)
00145 #define TMP_ALLOC_MP_PTRS(n)   TMP_ALLOC_TYPE(n,mp_ptr)
00146 
00147 
00148 #if ! defined (__GNUC__)    /* FIXME: Test for C++ compilers here,
00149                                __DECC understands __inline */
00150 #define inline                     /* Empty */
00151 #endif
00152 
00153 #define ABS(x) (x >= 0 ? x : -x)
00154 #define MIN(l,o) ((l) < (o) ? (l) : (o))
00155 #define MAX(h,i) ((h) > (i) ? (h) : (i))
00156 #define numberof(x)  (sizeof (x) / sizeof ((x)[0]))
00157 
00158 /* Field access macros.  */
00159 #define SIZ(x) ((x)->_mp_size)
00160 #define ABSIZ(x) ABS (SIZ (x))
00161 #define PTR(x) ((x)->_mp_d)
00162 #define LIMBS(x) ((x)->_mp_d)
00163 #define EXP(x) ((x)->_mp_exp)
00164 #define PREC(x) ((x)->_mp_prec)
00165 #define ALLOC(x) ((x)->_mp_alloc)
00166 
00167 /* Extra casts because shorts are promoted to ints by "~" and "<<".  "-1"
00168    rather than "1" in SIGNED_TYPE_MIN avoids warnings from some compilers
00169    about arithmetic overflow.  */
00170 #define UNSIGNED_TYPE_MAX(type)      ((type) ~ (type) 0)
00171 #define UNSIGNED_TYPE_HIGHBIT(type)  ((type) ~ (UNSIGNED_TYPE_MAX(type) >> 1))
00172 #define SIGNED_TYPE_MIN(type)        (((type) -1) << (8*sizeof(type)-1))
00173 #define SIGNED_TYPE_MAX(type)        ((type) ~ SIGNED_TYPE_MIN(type))
00174 #define SIGNED_TYPE_HIGHBIT(type)    SIGNED_TYPE_MIN(type)
00175 
00176 #define MP_LIMB_T_MAX      UNSIGNED_TYPE_MAX (mp_limb_t)
00177 #define MP_LIMB_T_HIGHBIT  UNSIGNED_TYPE_HIGHBIT (mp_limb_t)
00178 
00179 #define MP_SIZE_T_MAX      SIGNED_TYPE_MAX (mp_size_t)
00180 
00181 #ifndef ULONG_MAX
00182 #define ULONG_MAX          UNSIGNED_TYPE_MAX (unsigned long)
00183 #endif
00184 #define ULONG_HIGHBIT      UNSIGNED_TYPE_HIGHBIT (unsigned long)
00185 #define LONG_HIGHBIT       SIGNED_TYPE_HIGHBIT (long)
00186 #ifndef LONG_MAX
00187 #define LONG_MAX           SIGNED_TYPE_MAX (long)
00188 #endif
00189 
00190 #ifndef USHORT_MAX
00191 #define USHORT_MAX         UNSIGNED_TYPE_MAX (unsigned short)
00192 #endif
00193 #define USHORT_HIGHBIT     UNSIGNED_TYPE_HIGHBIT (unsigned short)
00194 #define SHORT_HIGHBIT      SIGNED_TYPE_HIGHBIT (short)
00195 #ifndef SHORT_MAX
00196 #define SHORT_MAX          SIGNED_TYPE_MAX (short)
00197 #endif
00198 
00199 
00200 /* Swap macros. */
00201 
00202 #define MP_LIMB_T_SWAP(x, y)                    \
00203   do {                                          \
00204     mp_limb_t __mp_limb_t_swap__tmp = (x);      \
00205     (x) = (y);                                  \
00206     (y) = __mp_limb_t_swap__tmp;                \
00207   } while (0)
00208 #define MP_SIZE_T_SWAP(x, y)                    \
00209   do {                                          \
00210     mp_size_t __mp_size_t_swap__tmp = (x);      \
00211     (x) = (y);                                  \
00212     (y) = __mp_size_t_swap__tmp;                \
00213   } while (0)
00214 
00215 #define MP_PTR_SWAP(x, y)               \
00216   do {                                  \
00217     mp_ptr __mp_ptr_swap__tmp = (x);    \
00218     (x) = (y);                          \
00219     (y) = __mp_ptr_swap__tmp;           \
00220   } while (0)
00221 #define MP_SRCPTR_SWAP(x, y)                    \
00222   do {                                          \
00223     mp_srcptr __mp_srcptr_swap__tmp = (x);      \
00224     (x) = (y);                                  \
00225     (y) = __mp_srcptr_swap__tmp;                \
00226   } while (0)
00227 
00228 #define MPN_PTR_SWAP(xp,xs, yp,ys)      \
00229   do {                                  \
00230     MP_PTR_SWAP (xp, yp);               \
00231     MP_SIZE_T_SWAP (xs, ys);            \
00232   } while(0)
00233 #define MPN_SRCPTR_SWAP(xp,xs, yp,ys)   \
00234   do {                                  \
00235     MP_SRCPTR_SWAP (xp, yp);            \
00236     MP_SIZE_T_SWAP (xs, ys);            \
00237   } while(0)
00238 
00239 #define MPZ_PTR_SWAP(x, y)              \
00240   do {                                  \
00241     mpz_ptr __mpz_ptr_swap__tmp = (x);  \
00242     (x) = (y);                          \
00243     (y) = __mpz_ptr_swap__tmp;          \
00244   } while (0)
00245 #define MPZ_SRCPTR_SWAP(x, y)                   \
00246   do {                                          \
00247     mpz_srcptr __mpz_srcptr_swap__tmp = (x);    \
00248     (x) = (y);                                  \
00249     (y) = __mpz_srcptr_swap__tmp;               \
00250   } while (0)
00251 
00252 
00253 #if defined (__cplusplus)
00254 extern "C" {
00255 #endif
00256 
00257 /* FIXME: These are purely internal, so do a search and replace to change
00258    them to __gmp forms, rather than using these macros. */
00259 #define _mp_allocate_func      __gmp_allocate_func
00260 #define _mp_reallocate_func    __gmp_reallocate_func
00261 #define _mp_free_func          __gmp_free_func
00262 #define _mp_default_allocate   __gmp_default_allocate
00263 #define _mp_default_reallocate __gmp_default_reallocate
00264 #define _mp_default_free       __gmp_default_free
00265 
00266 extern void * (*_mp_allocate_func) _PROTO ((size_t));
00267 extern void * (*_mp_reallocate_func) _PROTO ((void *, size_t, size_t));
00268 extern void   (*_mp_free_func) _PROTO ((void *, size_t));
00269 
00270 void *_mp_default_allocate _PROTO ((size_t));
00271 void *_mp_default_reallocate _PROTO ((void *, size_t, size_t));
00272 void _mp_default_free _PROTO ((void *, size_t));
00273 
00274 #define _MP_ALLOCATE_FUNC_TYPE(n,type) \
00275   ((type *) (*_mp_allocate_func) ((n) * sizeof (type)))
00276 #define _MP_ALLOCATE_FUNC_LIMBS(n)   _MP_ALLOCATE_FUNC_TYPE(n,mp_limb_t)
00277 
00278 #define _MP_FREE_FUNC_TYPE(p,n,type) (*_mp_free_func) (p, (n) * sizeof (type))
00279 #define _MP_FREE_FUNC_LIMBS(p,n)     _MP_FREE_FUNC_TYPE(p,n,mp_limb_t)
00280 
00281 
00282 #if (__STDC__-0) || defined (__cplusplus)
00283 
00284 #else
00285 
00286 #define const               /* Empty */
00287 #define signed                     /* Empty */
00288 
00289 #endif
00290 
00291 #if defined (__GNUC__) && defined (__i386__)
00292 #if 0                /* check that these actually improve things */
00293 #define MPN_COPY_INCR(DST, SRC, N)                             \
00294   __asm__ ("cld\n\trep\n\tmovsl" : :                                  \
00295           "D" (DST), "S" (SRC), "c" (N) :                      \
00296           "cx", "di", "si", "memory")
00297 #define MPN_COPY_DECR(DST, SRC, N)                             \
00298   __asm__ ("std\n\trep\n\tmovsl" : :                                  \
00299           "D" ((DST) + (N) - 1), "S" ((SRC) + (N) - 1), "c" (N) :     \
00300           "cx", "di", "si", "memory")
00301 #define MPN_NORMALIZE_NOT_ZERO(P, N)                                  \
00302   do {                                                         \
00303     __asm__ ("std\n\trepe\n\tscasl" : "=c" (N) :               \
00304             "a" (0), "D" ((P) + (N) - 1), "0" (N) :                   \
00305             "cx", "di");                                       \
00306     (N)++;                                                     \
00307   } while (0)
00308 #endif
00309 #endif
00310 
00311 #if HAVE_NATIVE_mpn_copyi
00312 #define mpn_copyi __MPN(copyi)
00313 void mpn_copyi _PROTO ((mp_ptr, mp_srcptr, mp_size_t));
00314 #endif
00315 
00316 /* Remap names of internal mpn functions.  */
00317 #define __clz_tab               __MPN(clz_tab)
00318 #define mpn_udiv_w_sdiv            __MPN(udiv_w_sdiv)
00319 #define mpn_reciprocal             __MPN(reciprocal)
00320 
00321 #define mpn_sb_divrem_mn    __MPN(sb_divrem_mn)
00322 #define mpn_bz_divrem_n            __MPN(bz_divrem_n)
00323 /* #define mpn_tdiv_q              __MPN(tdiv_q) */
00324 
00325 #define mpn_kara_mul_n      __MPN(kara_mul_n)
00326 void mpn_kara_mul_n _PROTO((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_ptr));
00327 
00328 #define mpn_kara_sqr_n  __MPN(kara_sqr_n)
00329 void mpn_kara_sqr_n _PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_ptr));
00330 
00331 #define mpn_toom3_mul_n  __MPN(toom3_mul_n)
00332 void mpn_toom3_mul_n _PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t,mp_ptr));
00333 
00334 #define mpn_toom3_sqr_n  __MPN(toom3_sqr_n)
00335 void mpn_toom3_sqr_n _PROTO((mp_ptr, mp_srcptr, mp_size_t, mp_ptr));
00336 
00337 #define mpn_fft_best_k  __MPN(fft_best_k)
00338 int mpn_fft_best_k _PROTO ((mp_size_t n, int sqr));
00339 
00340 #define mpn_mul_fft  __MPN(mul_fft)
00341 void mpn_mul_fft _PROTO ((mp_ptr op, mp_size_t pl,
00342                           mp_srcptr n, mp_size_t nl,
00343                           mp_srcptr m, mp_size_t ml,
00344                           int k));
00345 
00346 #define mpn_mul_fft_full  __MPN(mul_fft_full)
00347 void mpn_mul_fft_full _PROTO ((mp_ptr op,
00348                                mp_srcptr n, mp_size_t nl,
00349                                mp_srcptr m, mp_size_t ml));
00350 
00351 #define mpn_fft_next_size  __MPN(fft_next_size)
00352 mp_size_t mpn_fft_next_size _PROTO ((mp_size_t pl, int k));
00353 
00354 mp_limb_t mpn_sb_divrem_mn _PROTO ((mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t));
00355 mp_limb_t mpn_bz_divrem_n _PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_size_t));
00356 /* void mpn_tdiv_q _PROTO ((mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t)); */
00357 
00358 /* Copy NLIMBS *limbs* from SRC to DST, NLIMBS==0 allowed.  */
00359 #ifndef MPN_COPY_INCR
00360 #if HAVE_NATIVE_mpn_copyi
00361 #define MPN_COPY_INCR(DST, SRC, NLIMBS)   mpn_copyi (DST, SRC, NLIMBS)
00362 #else
00363 #define MPN_COPY_INCR(DST, SRC, NLIMBS) \
00364   do {                                                         \
00365     mp_size_t __i;                                             \
00366     for (__i = 0; __i < (NLIMBS); __i++)                       \
00367       (DST)[__i] = (SRC)[__i];                                        \
00368   } while (0)
00369 #endif
00370 #endif
00371 
00372 #if HAVE_NATIVE_mpn_copyd
00373 #define mpn_copyd __MPN(copyd)
00374 void mpn_copyd _PROTO ((mp_ptr, mp_srcptr, mp_size_t));
00375 #endif
00376 
00377 /* NLIMBS==0 allowed */
00378 #ifndef MPN_COPY_DECR
00379 #if HAVE_NATIVE_mpn_copyd
00380 #define MPN_COPY_DECR(DST, SRC, NLIMBS)   mpn_copyd (DST, SRC, NLIMBS)
00381 #else
00382 #define MPN_COPY_DECR(DST, SRC, NLIMBS) \
00383   do {                                                         \
00384     mp_size_t __i;                                             \
00385     for (__i = (NLIMBS) - 1; __i >= 0; __i--)                         \
00386       (DST)[__i] = (SRC)[__i];                                        \
00387   } while (0)
00388 #endif
00389 #endif
00390 
00391 /* Define MPN_COPY for vector computers.  Since #pragma cannot be in a macro,
00392    rely on function inlining. */
00393 #if defined (_CRAY) || defined (__uxp__)
00394 static inline void
00395 _MPN_COPY (d, s, n) mp_ptr d; mp_srcptr s; mp_size_t n;
00396 {
00397   int i;                           /* Faster for Cray with plain int */
00398 #pragma _CRI ivdep                 /* Cray PVP systems */
00399 #pragma loop noalias d,s           /* Fujitsu VPP systems */
00400   for (i = 0; i < n; i++)
00401     d[i] = s[i];
00402 }
00403 #define MPN_COPY _MPN_COPY
00404 #endif
00405 
00406 #ifndef MPN_COPY
00407 #define MPN_COPY MPN_COPY_INCR
00408 #endif
00409 
00410 /* Zero NLIMBS *limbs* AT DST.  */
00411 #ifndef MPN_ZERO
00412 #define MPN_ZERO(DST, NLIMBS) \
00413   do {                                                         \
00414     mp_size_t __i;                                             \
00415     for (__i = 0; __i < (NLIMBS); __i++)                       \
00416       (DST)[__i] = 0;                                                 \
00417   } while (0)
00418 #endif
00419 
00420 #ifndef MPN_NORMALIZE
00421 #define MPN_NORMALIZE(DST, NLIMBS) \
00422   do {                                                         \
00423     while (NLIMBS > 0)                                                \
00424       {                                                               \
00425        if ((DST)[(NLIMBS) - 1] != 0)                                  \
00426          break;                                                \
00427        NLIMBS--;                                               \
00428       }                                                               \
00429   } while (0)
00430 #endif
00431 #ifndef MPN_NORMALIZE_NOT_ZERO
00432 #define MPN_NORMALIZE_NOT_ZERO(DST, NLIMBS) \
00433   do {                                                         \
00434     while (1)                                                  \
00435       {                                                               \
00436        if ((DST)[(NLIMBS) - 1] != 0)                                  \
00437          break;                                                \
00438        NLIMBS--;                                               \
00439       }                                                               \
00440   } while (0)
00441 #endif
00442 
00443 /* Strip least significant zero limbs from ptr,size by incrementing ptr and
00444    decrementing size.  The number in ptr,size must be non-zero, ie. size!=0
00445    and somewhere a non-zero limb.  */
00446 #define MPN_STRIP_LOW_ZEROS_NOT_ZERO(ptr, size) \
00447   do                                            \
00448     {                                           \
00449       ASSERT ((size) != 0);                     \
00450       while ((ptr)[0] == 0)                     \
00451         {                                       \
00452           (ptr)++;                              \
00453           (size)--;                             \
00454           ASSERT (size >= 0);                   \
00455        }                                       \
00456     }                                           \
00457   while (0)
00458 
00459 /* Initialize X of type mpz_t with space for NLIMBS limbs.  X should be a
00460    temporary variable; it will be automatically cleared out at function
00461    return.  We use __x here to make it possible to accept both mpz_ptr and
00462    mpz_t arguments.  */
00463 #define MPZ_TMP_INIT(X, NLIMBS) \
00464   do {                                                         \
00465     mpz_ptr __x = (X);                                                \
00466     __x->_mp_alloc = (NLIMBS);                                        \
00467     __x->_mp_d = (mp_ptr) TMP_ALLOC ((NLIMBS) * BYTES_PER_MP_LIMB);   \
00468   } while (0)
00469 
00470 /* Realloc for an mpz_t WHAT if it has less thann NEEDED limbs.  */
00471 #define MPZ_REALLOC(what,needed) \
00472   do {                                                  \
00473     if ((needed) > ALLOC (what))                        \
00474       _mpz_realloc (what, needed);                      \
00475   } while (0)
00476 
00477 /* If KARATSUBA_MUL_THRESHOLD is not already defined, define it to a
00478    value which is good on most machines.  */
00479 #ifndef KARATSUBA_MUL_THRESHOLD
00480 #define KARATSUBA_MUL_THRESHOLD 32
00481 #endif
00482 
00483 /* If TOOM3_MUL_THRESHOLD is not already defined, define it to a
00484    value which is good on most machines.  */
00485 #ifndef TOOM3_MUL_THRESHOLD
00486 #define TOOM3_MUL_THRESHOLD 256
00487 #endif
00488 
00489 #ifndef KARATSUBA_SQR_THRESHOLD
00490 #define KARATSUBA_SQR_THRESHOLD (2*KARATSUBA_MUL_THRESHOLD)
00491 #endif
00492 
00493 #ifndef TOOM3_SQR_THRESHOLD
00494 #define TOOM3_SQR_THRESHOLD (2*TOOM3_MUL_THRESHOLD)
00495 #endif
00496 
00497 /* First k to use for an FFT modF multiply.  A modF FFT is an order
00498    log(2^k)/log(2^(k-1)) algorithm, so k=3 is merely 1.5 like karatsuba,
00499    whereas k=4 is 1.33 which is faster than toom3 at 1.485.    */
00500 #define FFT_FIRST_K  4
00501 
00502 /* Threshold at which FFT should be used to do a modF NxN -> N multiply. */
00503 #ifndef FFT_MODF_MUL_THRESHOLD
00504 #define FFT_MODF_MUL_THRESHOLD   (TOOM3_MUL_THRESHOLD * 3)
00505 #endif
00506 #ifndef FFT_MODF_SQR_THRESHOLD
00507 #define FFT_MODF_SQR_THRESHOLD   (TOOM3_SQR_THRESHOLD * 3)
00508 #endif
00509 
00510 /* Threshold at which FFT should be used to do an NxN -> 2N multiply.  This
00511    will be a size where FFT is using k=7 or k=8, since an FFT-k used for an
00512    NxN->2N multiply and not recursing into itself is an order
00513    log(2^k)/log(2^(k-2)) algorithm, so it'll be at least k=7 at 1.39 which
00514    is the first better than toom3.  */
00515 #ifndef FFT_MUL_THRESHOLD
00516 #define FFT_MUL_THRESHOLD   (FFT_MODF_MUL_THRESHOLD * 10)
00517 #endif
00518 #ifndef FFT_SQR_THRESHOLD
00519 #define FFT_SQR_THRESHOLD   (FFT_MODF_SQR_THRESHOLD * 10)
00520 #endif
00521 
00522 /* Table of thresholds for successive modF FFT "k"s.  The first entry is
00523    where FFT_FIRST_K+1 should be used, the second FFT_FIRST_K+2,
00524    etc.  See mpn_fft_best_k(). */
00525 #ifndef FFT_MUL_TABLE
00526 #define FFT_MUL_TABLE                           \
00527   { TOOM3_MUL_THRESHOLD * 4,   /* k=5 */        \
00528     TOOM3_MUL_THRESHOLD * 8,   /* k=6 */        \
00529     TOOM3_MUL_THRESHOLD * 16,  /* k=7 */        \
00530     TOOM3_MUL_THRESHOLD * 32,  /* k=8 */        \
00531     TOOM3_MUL_THRESHOLD * 96,  /* k=9 */        \
00532     TOOM3_MUL_THRESHOLD * 288, /* k=10 */       \
00533     0 }
00534 #endif
00535 #ifndef FFT_SQR_TABLE
00536 #define FFT_SQR_TABLE                           \
00537   { TOOM3_SQR_THRESHOLD * 4,   /* k=5 */        \
00538     TOOM3_SQR_THRESHOLD * 8,   /* k=6 */        \
00539     TOOM3_SQR_THRESHOLD * 16,  /* k=7 */        \
00540     TOOM3_SQR_THRESHOLD * 32,  /* k=8 */        \
00541     TOOM3_SQR_THRESHOLD * 96,  /* k=9 */        \
00542     TOOM3_SQR_THRESHOLD * 288, /* k=10 */       \
00543     0 }
00544 #endif
00545 
00546 #ifndef FFT_TABLE_ATTRS
00547 #define FFT_TABLE_ATTRS   static const
00548 #endif
00549 
00550 #define MPN_FFT_TABLE_SIZE  16
00551 
00552 
00553 /* Return non-zero if xp,xsize and yp,ysize overlap.
00554    If xp+xsize<=yp there's no overlap, or if yp+ysize<=xp there's no
00555    overlap.  If both these are false, there's an overlap. */
00556 #define MPN_OVERLAP_P(xp, xsize, yp, ysize) \
00557   ((xp) + (xsize) > (yp) && (yp) + (ysize) > (xp))
00558 
00559 
00560 /* ASSERT() is a private assertion checking scheme, similar to <assert.h>.
00561    ASSERT() does the check only if WANT_ASSERT is selected, ASSERT_ALWAYS()
00562    does it always.  Generally assertions are meant for development, but
00563    might help when looking for a problem later too.
00564 
00565    ASSERT_NOCARRY() uses ASSERT() to check the expression is zero, but if
00566    assertion checking is disabled, the expression is still evaluated.  This
00567    is meant for use with routines like mpn_add_n() where the return value
00568    represents a carry or whatever that shouldn't occur.  For example,
00569    ASSERT_NOCARRY (mpn_add_n (rp, s1p, s2p, size)); */
00570 
00571 #ifdef __LINE__
00572 #define ASSERT_LINE  __LINE__
00573 #else
00574 #define ASSERT_LINE  -1
00575 #endif
00576 
00577 #ifdef __FILE__
00578 #define ASSERT_FILE  __FILE__
00579 #else
00580 #define ASSERT_FILE  ""
00581 #endif
00582 
00583 static int __gmp_assert_fail _PROTO((const char *filename, int linenum,
00584                               const char *expr));
00585 
00586 #if HAVE_STRINGIZE
00587 #define ASSERT_FAIL(expr)  __gmp_assert_fail (ASSERT_FILE, ASSERT_LINE, #expr)
00588 #else
00589 #define ASSERT_FAIL(expr)  __gmp_assert_fail (ASSERT_FILE, ASSERT_LINE, "expr")
00590 #endif
00591 
00592 #if HAVE_VOID
00593 #define CAST_TO_VOID        (void)
00594 #else
00595 #define CAST_TO_VOID
00596 #endif
00597 
00598 #define ASSERT_ALWAYS(expr) ((expr) ? 0 : ASSERT_FAIL (expr))
00599 
00600 #if WANT_ASSERT
00601 #define ASSERT(expr)           ASSERT_ALWAYS (expr)
00602 #define ASSERT_NOCARRY(expr)   ASSERT_ALWAYS ((expr) == 0)
00603 
00604 #else
00605 #define ASSERT(expr)           (CAST_TO_VOID 0)
00606 #define ASSERT_NOCARRY(expr)   (expr)
00607 #endif
00608 
00609 
00610 #if HAVE_NATIVE_mpn_com_n
00611 #define mpn_com_n __MPN(com_n)
00612 void mpn_com_n _PROTO ((mp_ptr, mp_srcptr, mp_size_t));
00613 #else
00614 #define mpn_com_n(d,s,n)        \
00615   do                            \
00616     {                           \
00617       mp_ptr     __d = (d);     \
00618       mp_srcptr  __s = (s);     \
00619       mp_size_t  __n = (n);     \
00620       do                        \
00621         *__d++ = ~ *__s++;      \
00622       while (--__n);            \
00623     }                           \
00624   while (0)
00625 #endif
00626 
00627 #define MPN_LOGOPS_N_INLINE(d,s1,s2,n,dop,op,s2op)      \
00628   do                                                    \
00629     {                                                   \
00630       mp_ptr     __d = (d);                             \
00631       mp_srcptr  __s1 = (s1);                           \
00632       mp_srcptr  __s2 = (s2);                           \
00633       mp_size_t  __n = (n);                             \
00634       do                                                \
00635         *__d++ = dop (*__s1++ op s2op *__s2++);         \
00636       while (--__n);                                    \
00637     }                                                   \
00638   while (0)
00639 
00640 #if HAVE_NATIVE_mpn_and_n
00641 #define mpn_and_n __MPN(and_n)
00642 void mpn_and_n _PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
00643 #else
00644 #define mpn_and_n(d,s1,s2,n)  MPN_LOGOPS_N_INLINE(d,s1,s2,n, ,&, )
00645 #endif
00646 
00647 #if HAVE_NATIVE_mpn_andn_n
00648 #define mpn_andn_n __MPN(andn_n)
00649 void mpn_andn_n _PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
00650 #else
00651 #define mpn_andn_n(d,s1,s2,n) MPN_LOGOPS_N_INLINE(d,s1,s2,n, ,&,~)
00652 #endif
00653 
00654 #if HAVE_NATIVE_mpn_nand_n
00655 #define mpn_nand_n __MPN(nand_n)
00656 void mpn_nand_n _PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
00657 #else
00658 #define mpn_nand_n(d,s1,s2,n) MPN_LOGOPS_N_INLINE(d,s1,s2,n,~,&, )
00659 #endif
00660 
00661 #if HAVE_NATIVE_mpn_ior_n
00662 #define mpn_ior_n __MPN(ior_n)
00663 void mpn_ior_n _PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
00664 #else
00665 #define mpn_ior_n(d,s1,s2,n)  MPN_LOGOPS_N_INLINE(d,s1,s2,n, ,|, )
00666 #endif
00667 
00668 #if HAVE_NATIVE_mpn_iorn_n
00669 #define mpn_iorn_n __MPN(iorn_n)
00670 void mpn_iorn_n _PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
00671 #else
00672 #define mpn_iorn_n(d,s1,s2,n) MPN_LOGOPS_N_INLINE(d,s1,s2,n, ,|,~)
00673 #endif
00674 
00675 #if HAVE_NATIVE_mpn_nior_n
00676 #define mpn_nior_n __MPN(nior_n)
00677 void mpn_nior_n _PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
00678 #else
00679 #define mpn_nior_n(d,s1,s2,n) MPN_LOGOPS_N_INLINE(d,s1,s2,n,~,|, )
00680 #endif
00681 
00682 #if HAVE_NATIVE_mpn_xor_n
00683 #define mpn_xor_n __MPN(xor_n)
00684 void mpn_xor_n _PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
00685 #else
00686 #define mpn_xor_n(d,s1,s2,n)  MPN_LOGOPS_N_INLINE(d,s1,s2,n, ,^, )
00687 #endif
00688 
00689 #if HAVE_NATIVE_mpn_xnor_n
00690 #define mpn_xnor_n __MPN(xnor_n)
00691 void mpn_xnor_n _PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
00692 #else
00693 #define mpn_xnor_n(d,s1,s2,n) MPN_LOGOPS_N_INLINE(d,s1,s2,n,~,^, )
00694 #endif
00695 
00696 /* Structure for conversion between internal binary format and
00697    strings in base 2..36.  */
00698 struct bases
00699 {
00700   /* Number of digits in the conversion base that always fits in an mp_limb_t.
00701      For example, for base 10 on a machine where a mp_limb_t has 32 bits this
00702      is 9, since 10**9 is the largest number that fits into a mp_limb_t.  */
00703   int chars_per_limb;
00704 
00705   /* log(2)/log(conversion_base) */
00706   double chars_per_bit_exactly;
00707 
00708   /* base**chars_per_limb, i.e. the biggest number that fits a word, built by
00709      factors of base.  Exception: For 2, 4, 8, etc, big_base is log2(base),
00710      i.e. the number of bits used to represent each digit in the base.  */
00711   mp_limb_t big_base;
00712 
00713   /* A BITS_PER_MP_LIMB bit approximation to 1/big_base, represented as a
00714      fixed-point number.  Instead of dividing by big_base an application can
00715      choose to multiply by big_base_inverted.  */
00716   mp_limb_t big_base_inverted;
00717 };
00718 
00719 #define __mp_bases __MPN(mp_bases)
00720 extern const struct bases __mp_bases[];
00721 extern mp_size_t __gmp_default_fp_limb_precision;
00722 
00723 #if defined (__i386__)
00724 #define TARGET_REGISTER_STARVED 1
00725 #else
00726 #define TARGET_REGISTER_STARVED 0
00727 #endif
00728 
00729 /* Use a library function for invert_limb, if available. */
00730 #if ! defined (invert_limb) && HAVE_NATIVE_mpn_invert_limb
00731 #define mpn_invert_limb  __MPN(invert_limb)
00732 mp_limb_t mpn_invert_limb _PROTO ((mp_limb_t));
00733 #define invert_limb(invxl,xl)  (invxl = __MPN(invert_limb) (xl))
00734 #endif
00735 
00736 #ifndef invert_limb
00737 #define invert_limb(invxl,xl) \
00738   do {                                                         \
00739     mp_limb_t dummy;                                           \
00740     if (xl << 1 == 0)                                                 \
00741       invxl = ~(mp_limb_t) 0;                                         \
00742     else                                                       \
00743       udiv_qrnnd (invxl, dummy, -xl, 0, xl);                          \
00744   } while (0)
00745 #endif
00746 
00747 /* Divide the two-limb number in (NH,,NL) by D, with DI being the largest
00748    limb not larger than (2**(2*BITS_PER_MP_LIMB))/D - (2**BITS_PER_MP_LIMB).
00749    If this would yield overflow, DI should be the largest possible number
00750    (i.e., only ones).  For correct operation, the most significant bit of D
00751    has to be set.  Put the quotient in Q and the remainder in R.  */
00752 #define udiv_qrnnd_preinv(q, r, nh, nl, d, di) \
00753   do {                                                         \
00754     mp_limb_t _q, _ql, _r;                                     \
00755     mp_limb_t _xh, _xl;                                               \
00756     umul_ppmm (_q, _ql, (nh), (di));                                  \
00757     _q += (nh);                    /* DI is 2**BITS_PER_MP_LIMB too small */\
00758     umul_ppmm (_xh, _xl, _q, (d));                             \
00759     sub_ddmmss (_xh, _r, (nh), (nl), _xh, _xl);                       \
00760     if (_xh != 0)                                              \
00761       {                                                               \
00762        sub_ddmmss (_xh, _r, _xh, _r, 0, (d));                         \
00763        _q += 1;                                                \
00764        if (_xh != 0)                                           \
00765          {                                                     \
00766            sub_ddmmss (_xh, _r, _xh, _r, 0, (d));                     \
00767            _q += 1;                                            \
00768          }                                                     \
00769       }                                                               \
00770     if (_r >= (d))                                             \
00771       {                                                               \
00772        _r -= (d);                                              \
00773        _q += 1;                                                \
00774       }                                                               \
00775     (r) = _r;                                                  \
00776     (q) = _q;                                                  \
00777   } while (0)
00778 /* Like udiv_qrnnd_preinv, but for for any value D.  DNORM is D shifted left
00779    so that its most significant bit is set.  LGUP is ceil(log2(D)).  */
00780 #define udiv_qrnnd_preinv2gen(q, r, nh, nl, d, di, dnorm, lgup) \
00781   do {                                                         \
00782     mp_limb_t _n2, _n10, _n1, _nadj, _q1;                      \
00783     mp_limb_t _xh, _xl;                                               \
00784     _n2 = ((nh) << (BITS_PER_MP_LIMB - (lgup))) + ((nl) >> 1 >> (l - 1));\
00785     _n10 = (nl) << (BITS_PER_MP_LIMB - (lgup));                       \
00786     _n1 = ((mp_limb_signed_t) _n10 >> (BITS_PER_MP_LIMB - 1));        \
00787     _nadj = _n10 + (_n1 & (dnorm));                                   \
00788     umul_ppmm (_xh, _xl, di, _n2 - _n1);                       \
00789     add_ssaaaa (_xh, _xl, _xh, _xl, 0, _nadj);                        \
00790     _q1 = ~(_n2 + _xh);                                               \
00791     umul_ppmm (_xh, _xl, _q1, d);                              \
00792     add_ssaaaa (_xh, _xl, _xh, _xl, nh, nl);                          \
00793     _xh -= (d);                                                       \
00794     (r) = _xl + ((d) & _xh);                                          \
00795     (q) = _xh - _q1;                                           \
00796   } while (0)
00797 /* Exactly like udiv_qrnnd_preinv, but branch-free.  It is not clear which
00798    version to use.  */
00799 #define udiv_qrnnd_preinv2norm(q, r, nh, nl, d, di) \
00800   do {                                                         \
00801     mp_limb_t _n2, _n10, _n1, _nadj, _q1;                      \
00802     mp_limb_t _xh, _xl;                                               \
00803     _n2 = (nh);                                                       \
00804     _n10 = (nl);                                               \
00805     _n1 = ((mp_limb_signed_t) _n10 >> (BITS_PER_MP_LIMB - 1));        \
00806     _nadj = _n10 + (_n1 & (d));                                       \
00807     umul_ppmm (_xh, _xl, di, _n2 - _n1);                       \
00808     add_ssaaaa (_xh, _xl, _xh, _xl, 0, _nadj);                        \
00809     _q1 = ~(_n2 + _xh);                                               \
00810     umul_ppmm (_xh, _xl, _q1, d);                              \
00811     add_ssaaaa (_xh, _xl, _xh, _xl, nh, nl);                          \
00812     _xh -= (d);                                                       \
00813     (r) = _xl + ((d) & _xh);                                          \
00814     (q) = _xh - _q1;                                           \
00815   } while (0)
00816 
00817 
00818 /* modlimb_invert() sets "inv" to the multiplicative inverse of "n" modulo
00819    2^BITS_PER_MP_LIMB, ie. so that inv*n == 1 mod 2^BITS_PER_MP_LIMB.
00820    "n" must be odd (otherwise such an inverse doesn't exist).
00821 
00822    This is not to be confused with invert_limb(), which is completely
00823    different.
00824 
00825    The table lookup gives an inverse with the low 8 bits valid, and each
00826    multiply step doubles the number of bits.  See Jebelean's exact division
00827    paper, end of section 4 (reference in gmp.texi). */
00828 
00829 #define modlimb_invert_table  __gmp_modlimb_invert_table
00830 extern const unsigned char  modlimb_invert_table[128];
00831 
00832 #if BITS_PER_MP_LIMB <= 32
00833 #define modlimb_invert(inv,n)                                   \
00834   do {                                                          \
00835     mp_limb_t  __n = (n);                                       \
00836     mp_limb_t  __inv;                                           \
00837     ASSERT ((__n & 1) == 1);                                    \
00838     __inv = modlimb_invert_table[(__n&0xFF)/2]; /*  8 */        \
00839     __inv = 2 * __inv - __inv * __inv * __n;    /* 16 */        \
00840     __inv = 2 * __inv - __inv * __inv * __n;    /* 32 */        \
00841     ASSERT (__inv * __n == 1);                                  \
00842     (inv) = __inv;                                              \
00843   } while (0)
00844 #endif
00845 
00846 #if BITS_PER_MP_LIMB > 32 && BITS_PER_MP_LIMB <= 64
00847 #define modlimb_invert(inv,n)                                   \
00848   do {                                                          \
00849     mp_limb_t  __n = (n);                                       \
00850     mp_limb_t  __inv;                                           \
00851     ASSERT ((__n & 1) == 1);                                    \
00852     __inv = modlimb_invert_table[(__n&0xFF)/2]; /*  8 */        \
00853     __inv = 2 * __inv - __inv * __inv * __n;    /* 16 */        \
00854     __inv = 2 * __inv - __inv * __inv * __n;    /* 32 */        \
00855     __inv = 2 * __inv - __inv * __inv * __n;    /* 64 */        \
00856     ASSERT (__inv * __n == 1);                                  \
00857     (inv) = __inv;                                              \
00858   } while (0)
00859 #endif
00860 
00861 
00862 /* The `mode' attribute was introduced in GCC 2.2, but we can only distinguish
00863    between GCC 2 releases from 2.5, since __GNUC_MINOR__ wasn't introduced
00864    until then.  */
00865 #if (__GNUC__ - 0 > 2 || defined (__GNUC_MINOR__)) && ! defined (__APPLE_CC__)
00866 /* Define stuff for longlong.h.  */
00867 typedef unsigned int UQItype       __attribute__ ((mode (QI)));
00868 typedef               int SItype   __attribute__ ((mode (SI)));
00869 typedef unsigned int USItype       __attribute__ ((mode (SI)));
00870 typedef               int DItype   __attribute__ ((mode (DI)));
00871 typedef unsigned int UDItype       __attribute__ ((mode (DI)));
00872 #else
00873 typedef unsigned char UQItype;
00874 typedef               long SItype;
00875 typedef unsigned long USItype;
00876 #if defined _LONGLONG || defined _LONG_LONG_LIMB
00877 typedef       long long int DItype;
00878 typedef unsigned long long int UDItype;
00879 #else /* Assume `long' gives us a wide enough type.  Needed for hppa2.0w.  */
00880 typedef long int DItype;
00881 typedef unsigned long int UDItype;
00882 #endif
00883 #endif
00884 
00885 typedef mp_limb_t UWtype;
00886 typedef unsigned int UHWtype;
00887 #define W_TYPE_SIZE BITS_PER_MP_LIMB
00888 
00889 /* Define ieee_double_extract and _GMP_IEEE_FLOATS.  */
00890 
00891 #if (defined (__arm__) && (defined (__ARMWEL__) || defined (__linux__)))
00892 /* Special case for little endian ARM since floats remain in big-endian.  */
00893 #define _GMP_IEEE_FLOATS 1
00894 union ieee_double_extract
00895 {
00896   struct
00897     {
00898       unsigned int manh:20;
00899       unsigned int exp:11;
00900       unsigned int sig:1;
00901       unsigned int manl:32;
00902     } s;
00903   double d;
00904 };
00905 #else
00906 #if defined (_LITTLE_ENDIAN) || defined (__LITTLE_ENDIAN__)           \
00907  || defined (__alpha)                                                 \
00908  || defined (__clipper__)                                      \
00909  || defined (__cris)                                           \
00910  || defined (__i386__)                                                \
00911  || defined (__i860__)                                                \
00912  || defined (__i960__)                                                \
00913  || defined (MIPSEL) || defined (_MIPSEL)                      \
00914  || defined (__ns32000__)                                      \
00915  || defined (__WINNT) || defined (_WIN32)
00916 #define _GMP_IEEE_FLOATS 1
00917 union ieee_double_extract
00918 {
00919   struct
00920     {
00921       unsigned int manl:32;
00922       unsigned int manh:20;
00923       unsigned int exp:11;
00924       unsigned int sig:1;
00925     } s;
00926   double d;
00927 };
00928 #else /* Need this as an #else since the tests aren't made exclusive.  */
00929 #if defined (_BIG_ENDIAN) || defined (__BIG_ENDIAN__)                 \
00930  || defined (__a29k__) || defined (_AM29K)                            \
00931  || defined (__arm__)                                                 \
00932  || (defined (__convex__) && defined (_IEEE_FLOAT_))                  \
00933  || defined (_CRAYMPP)                                                \
00934  || defined (__i370__) || defined (__mvs__)                           \
00935  || defined (__mc68000__) || defined (__mc68020__) || defined (__m68k__)\
00936     || defined(mc68020)                                               \
00937  || defined (__m88000__)                                       \
00938  || defined (MIPSEB) || defined (_MIPSEB)                      \
00939  || defined (__hppa) || defined (__hppa__)                            \
00940  || defined (__pyr__)                                                 \
00941  || defined (__ibm032__)                                       \
00942  || defined (_IBMR2) || defined (_ARCH_PPC)                           \
00943  || defined (__sh__)                                           \
00944  || defined (__sparc) || defined (sparc)                       \
00945  || defined (__we32k__)
00946 #define _GMP_IEEE_FLOATS 1
00947 union ieee_double_extract
00948 {
00949   struct
00950     {
00951       unsigned int sig:1;
00952       unsigned int exp:11;
00953       unsigned int manh:20;
00954       unsigned int manl:32;
00955     } s;
00956   double d;
00957 };
00958 #endif
00959 #endif
00960 #endif
00961 
00962 /* Using "(2.0 * ((mp_limb_t) 1 << (BITS_PER_MP_LIMB - 1)))" doesn't work on
00963    SunOS 4.1.4 native /usr/ucb/cc (K&R), it comes out as -4294967296.0,
00964    presumably due to treating the mp_limb_t constant as signed rather than
00965    unsigned. */
00966 #define MP_BASE_AS_DOUBLE (4.0 * ((mp_limb_t) 1 << (BITS_PER_MP_LIMB - 2)))
00967 #if BITS_PER_MP_LIMB == 64
00968 #define LIMBS_PER_DOUBLE 2
00969 #else
00970 #define LIMBS_PER_DOUBLE 3
00971 #endif
00972 
00973 double __gmp_scale2 _PROTO ((double, int));
00974 int __gmp_extract_double _PROTO ((mp_ptr, double));
00975 
00976 extern int __gmp_junk;
00977 extern const int __gmp_0;
00978 #define GMP_ERROR(code)   (gmp_errno |= (code), __gmp_junk = 10/__gmp_0)
00979 #define DIVIDE_BY_ZERO    GMP_ERROR(GMP_ERROR_DIVISION_BY_ZERO)
00980 #define SQRT_OF_NEGATIVE  GMP_ERROR(GMP_ERROR_SQRT_OF_NEGATIVE)
00981 
00982 #if defined _LONG_LONG_LIMB
00983 #if defined (__STDC__)
00984 #define CNST_LIMB(C) C##LL
00985 #else
00986 #define CNST_LIMB(C) CLL
00987 #endif
00988 #else /* not _LONG_LONG_LIMB */
00989 #if defined (__STDC__)
00990 #define CNST_LIMB(C) C##L
00991 #else
00992 #define CNST_LIMB(C) CL
00993 #endif
00994 #endif /* _LONG_LONG_LIMB */
00995 
00996 /*** Stuff used by mpn/generic/prefsqr.c and mpn/generic/next_prime.c ***/
00997 #if BITS_PER_MP_LIMB == 32
00998 #define PP 0xC0CFD797L             /* 3 x 5 x 7 x 11 x 13 x ... x 29 */
00999 #define PP_INVERTED 0x53E5645CL
01000 #define PP_MAXPRIME 29
01001 #define PP_MASK 0x208A28A8L
01002 #endif
01003 
01004 #if BITS_PER_MP_LIMB == 64
01005 #define PP CNST_LIMB(0xE221F97C30E94E1D)  /* 3 x 5 x 7 x 11 x 13 x ... x 53 */
01006 #define PP_INVERTED CNST_LIMB(0x21CFE6CFC938B36B)
01007 #define PP_MAXPRIME 53
01008 #define PP_MASK CNST_LIMB(0x208A20A08A28A8)
01009 #endif
01010 
01011 
01012 /* BIT1 means a result value in bit 1 (second least significant bit), with a
01013    zero bit representing +1 and a one bit representing -1.  Bits other than
01014    bit 1 are garbage.
01015 
01016    JACOBI_TWOS_U_BIT1 and JACOBI_RECIP_UU_BIT1 are used in mpn_jacobi_base
01017    and their speed is important.  Expressions are used rather than
01018    conditionals to accumulate sign changes, which effectively means XORs
01019    instead of conditional JUMPs. */
01020 
01021 /* (a/0), with a signed; is 1 if a=+/-1, 0 otherwise */
01022 #define JACOBI_S0(a) \
01023   (((a) == 1) | ((a) == -1))
01024 
01025 /* (a/0), with a unsigned; is 1 if a=+/-1, 0 otherwise */
01026 #define JACOBI_U0(a) \
01027   ((a) == 1)
01028 
01029 /* (a/0), with a an mpz_t; is 1 if a=+/-1, 0 otherwise
01030    An mpz_t always has at least one limb of allocated space, so the fetch of
01031    the low limb is valid. */
01032 #define JACOBI_Z0(a) \
01033   (((SIZ(a) == 1) | (SIZ(a) == -1)) & (PTR(a)[0] == 1))
01034 
01035 /* Convert a bit1 to +1 or -1. */
01036 #define JACOBI_BIT1_TO_PN(result_bit1) \
01037   (1 - ((result_bit1) & 2))
01038 
01039 /* (2/b), with b unsigned and odd;
01040    is (-1)^((b^2-1)/8) which is 1 if b==1,7mod8 or -1 if b==3,5mod8 and
01041    hence obtained from (b>>1)^b */
01042 #define JACOBI_TWO_U_BIT1(b) \
01043   (ASSERT (b & 1), (((b) >> 1) ^ (b)))
01044 
01045 /* (2/b)^twos, with b unsigned and odd */
01046 #define JACOBI_TWOS_U_BIT1(twos, b) \
01047   (((twos) << 1) & JACOBI_TWO_U_BIT1 (b))
01048 
01049 /* (2/b)^twos, with b unsigned and odd */
01050 #define JACOBI_TWOS_U(twos, b) \
01051   (JACOBI_BIT1_TO_PN (JACOBI_TWOS_U_BIT1 (twos, b)))
01052 
01053 /* (a/b) effect due to sign of a: signed/unsigned, b odd;
01054    is (-1)^((b-1)/2) if a<0, or +1 if a>=0 */
01055 #define JACOBI_ASGN_SU_BIT1(a, b) \
01056   ((((a) < 0) << 1) & (b))
01057 
01058 /* (a/b) effect due to sign of b: signed/mpz;
01059    is -1 if a and b both negative, +1 otherwise */
01060 #define JACOBI_BSGN_SZ_BIT1(a, b) \
01061   ((((a) < 0) & (SIZ(b) < 0)) << 1)
01062 
01063 /* (a/b) effect due to sign of b: mpz/signed */
01064 #define JACOBI_BSGN_ZS_BIT1(a, b) \
01065   JACOBI_BSGN_SZ_BIT1(b, a)
01066 
01067 /* (a/b) reciprocity to switch to (b/a), a,b both unsigned and odd.
01068    Is (-1)^((a-1)*(b-1)/4), which means +1 if either a,b==1mod4 or -1 if
01069    both a,b==3mod4, achieved in bit 1 by a&b.  No ASSERT()s about a,b odd
01070    because this is used in a couple of places with only bit 1 of a or b
01071    valid. */
01072 #define JACOBI_RECIP_UU_BIT1(a, b) \
01073   ((a) & (b))
01074 
01075 
01076 /* For testing and debugging.  */
01077 #define MPZ_CHECK_FORMAT(z)                                           \
01078   (ASSERT_ALWAYS (SIZ(z) == 0 || PTR(z)[ABSIZ(z) - 1] != 0),          \
01079    ASSERT_ALWAYS (ALLOC(z) >= ABSIZ(z)))
01080 #define MPZ_PROVOKE_REALLOC(z)                                        \
01081   do { ALLOC(z) = ABSIZ(z); } while (0)
01082 
01083 
01084 #if TUNE_PROGRAM_BUILD
01085 /* Some extras wanted when recompiling some .c files for use by the tune
01086    program.  Not part of a normal build. */
01087 
01088 extern mp_size_t  mul_threshold[];
01089 extern mp_size_t  fft_modf_mul_threshold;
01090 extern mp_size_t  sqr_threshold[];
01091 extern mp_size_t  fft_modf_sqr_threshold;
01092 extern mp_size_t  bz_threshold[];
01093 extern mp_size_t  fib_threshold[];
01094 extern mp_size_t  powm_threshold[];
01095 extern mp_size_t  gcd_accel_threshold[];
01096 extern mp_size_t  gcdext_threshold[];
01097 
01098 #undef KARATSUBA_MUL_THRESHOLD
01099 #undef TOOM3_MUL_THRESHOLD
01100 #undef FFT_MUL_TABLE
01101 #undef FFT_MUL_THRESHOLD
01102 #undef FFT_MODF_MUL_THRESHOLD
01103 #undef KARATSUBA_SQR_THRESHOLD
01104 #undef TOOM3_SQR_THRESHOLD
01105 #undef FFT_SQR_TABLE
01106 #undef FFT_SQR_THRESHOLD
01107 #undef FFT_MODF_SQR_THRESHOLD
01108 #undef BZ_THRESHOLD
01109 #undef FIB_THRESHOLD
01110 #undef POWM_THRESHOLD
01111 #undef GCD_ACCEL_THRESHOLD
01112 #undef GCDEXT_THRESHOLD
01113 
01114 #define KARATSUBA_MUL_THRESHOLD  mul_threshold[0]
01115 #define TOOM3_MUL_THRESHOLD      mul_threshold[1]
01116 #define FFT_MUL_TABLE            0
01117 #define FFT_MUL_THRESHOLD        mul_threshold[2]
01118 #define FFT_MODF_MUL_THRESHOLD   fft_modf_mul_threshold
01119 #define KARATSUBA_SQR_THRESHOLD  sqr_threshold[0]
01120 #define TOOM3_SQR_THRESHOLD      sqr_threshold[1]
01121 #define FFT_SQR_TABLE            0
01122 #define FFT_SQR_THRESHOLD        sqr_threshold[2]
01123 #define FFT_MODF_SQR_THRESHOLD   fft_modf_sqr_threshold
01124 #define BZ_THRESHOLD             bz_threshold[0]
01125 #define FIB_THRESHOLD            fib_threshold[0]
01126 #define POWM_THRESHOLD           powm_threshold[0]
01127 #define GCD_ACCEL_THRESHOLD      gcd_accel_threshold[0]
01128 #define GCDEXT_THRESHOLD         gcdext_threshold[0]
01129 
01130 #define TOOM3_MUL_THRESHOLD_LIMIT  700
01131 
01132 #undef  FFT_TABLE_ATTRS
01133 #define FFT_TABLE_ATTRS
01134 extern mp_size_t mpn_fft_table[2][MPN_FFT_TABLE_SIZE];
01135 
01136 #endif /* TUNE_PROGRAM_BUILD */
01137 
01138 #if defined (__cplusplus)
01139 }
01140 #endif