xref: /dragonfly/contrib/gmp/gmp-impl.h (revision d2d4b659)
1 /* Include file for internal GNU MP types and definitions.
2 
3    THE CONTENTS OF THIS FILE ARE FOR INTERNAL USE AND ARE ALMOST CERTAIN TO
4    BE SUBJECT TO INCOMPATIBLE CHANGES IN FUTURE GNU MP RELEASES.
5 
6 Copyright 1991, 1993, 1994, 1995, 1996, 1997, 1999, 2000, 2001, 2002, 2003,
7 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012 Free Software Foundation,
8 Inc.
9 
10 This file is part of the GNU MP Library.
11 
12 The GNU MP Library is free software; you can redistribute it and/or modify
13 it under the terms of the GNU Lesser General Public License as published by
14 the Free Software Foundation; either version 3 of the License, or (at your
15 option) any later version.
16 
17 The GNU MP Library is distributed in the hope that it will be useful, but
18 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
19 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
20 License for more details.
21 
22 You should have received a copy of the GNU Lesser General Public License
23 along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
24 
25 
26 /* __GMP_DECLSPEC must be given on any global data that will be accessed
27    from outside libgmp, meaning from the test or development programs, or
28    from libgmpxx.  Failing to do this will result in an incorrect address
29    being used for the accesses.  On functions __GMP_DECLSPEC makes calls
30    from outside libgmp more efficient, but they'll still work fine without
31    it.  */
32 
33 
34 #ifndef __GMP_IMPL_H__
35 #define __GMP_IMPL_H__
36 
37 #if defined _CRAY
38 #include <intrinsics.h>  /* for _popcnt */
39 #endif
40 
41 /* limits.h is not used in general, since it's an ANSI-ism, and since on
42    solaris gcc 2.95 under -mcpu=ultrasparc in ABI=32 ends up getting wrong
43    values (the ABI=64 values).
44 
45    On Cray vector systems, however, we need the system limits.h since sizes
46    of signed and unsigned types can differ there, depending on compiler
47    options (eg. -hnofastmd), making our SHRT_MAX etc expressions fail.  For
48    reference, int can be 46 or 64 bits, whereas uint is always 64 bits; and
49    short can be 24, 32, 46 or 64 bits, and different for ushort.  */
50 
51 #if defined _CRAY
52 #include <limits.h>
53 #endif
54 
55 /* For fat.h and other fat binary stuff.
56    No need for __GMP_ATTRIBUTE_PURE or __GMP_NOTHROW, since functions
57    declared this way are only used to set function pointers in __gmp_cpuvec,
58    they're not called directly.  */
59 #define DECL_add_n(name) \
60   __GMP_DECLSPEC mp_limb_t name __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t))
61 #define DECL_addmul_1(name) \
62   __GMP_DECLSPEC mp_limb_t name __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_limb_t))
63 #define DECL_copyd(name) \
64   __GMP_DECLSPEC void name __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t))
65 #define DECL_copyi(name) \
66   DECL_copyd (name)
67 #define DECL_divexact_1(name) \
68   __GMP_DECLSPEC void name __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_limb_t))
69 #define DECL_divexact_by3c(name) \
70   __GMP_DECLSPEC mp_limb_t name __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_limb_t))
71 #define DECL_divrem_1(name) \
72   __GMP_DECLSPEC mp_limb_t name __GMP_PROTO ((mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t))
73 #define DECL_gcd_1(name) \
74   __GMP_DECLSPEC mp_limb_t name __GMP_PROTO ((mp_srcptr, mp_size_t, mp_limb_t))
75 #define DECL_lshift(name) \
76   __GMP_DECLSPEC mp_limb_t name __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, unsigned))
77 #define DECL_mod_1(name) \
78   __GMP_DECLSPEC mp_limb_t name __GMP_PROTO ((mp_srcptr, mp_size_t, mp_limb_t))
79 #define DECL_mod_34lsub1(name) \
80   __GMP_DECLSPEC mp_limb_t name __GMP_PROTO ((mp_srcptr, mp_size_t))
81 #define DECL_modexact_1c_odd(name) \
82   __GMP_DECLSPEC mp_limb_t name __GMP_PROTO ((mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t))
83 #define DECL_mul_1(name) \
84   DECL_addmul_1 (name)
85 #define DECL_mul_basecase(name) \
86   __GMP_DECLSPEC void name __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t))
87 #define DECL_preinv_divrem_1(name) \
88   __GMP_DECLSPEC mp_limb_t name __GMP_PROTO ((mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t, int))
89 #define DECL_preinv_mod_1(name) \
90   __GMP_DECLSPEC mp_limb_t name __GMP_PROTO ((mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t))
91 #define DECL_rshift(name) \
92   DECL_lshift (name)
93 #define DECL_sqr_basecase(name) \
94   __GMP_DECLSPEC void name __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t))
95 #define DECL_sub_n(name) \
96   DECL_add_n (name)
97 #define DECL_submul_1(name) \
98   DECL_addmul_1 (name)
99 
100 #if ! __GMP_WITHIN_CONFIGURE
101 #include "config.h"
102 #include "gmp-mparam.h"
103 #include "fib_table.h"
104 #include "mp_bases.h"
105 #if WANT_FAT_BINARY
106 #include "fat.h"
107 #endif
108 #endif
109 
110 #if HAVE_INTTYPES_H      /* for uint_least32_t */
111 # include <inttypes.h>
112 #else
113 # if HAVE_STDINT_H
114 #  include <stdint.h>
115 # endif
116 #endif
117 
118 #ifdef __cplusplus
119 #include <cstring>  /* for strlen */
120 #include <string>   /* for std::string */
121 #endif
122 
123 
124 #ifndef WANT_TMP_DEBUG  /* for TMP_ALLOC_LIMBS_2 and others */
125 #define WANT_TMP_DEBUG 0
126 #endif
127 
128 /* The following tries to get a good version of alloca.  The tests are
129    adapted from autoconf AC_FUNC_ALLOCA, with a couple of additions.
130    Whether this succeeds is tested by GMP_FUNC_ALLOCA and HAVE_ALLOCA will
131    be setup appropriately.
132 
133    ifndef alloca - a cpp define might already exist.
134        glibc <stdlib.h> includes <alloca.h> which uses GCC __builtin_alloca.
135        HP cc +Olibcalls adds a #define of alloca to __builtin_alloca.
136 
137    GCC __builtin_alloca - preferred whenever available.
138 
139    _AIX pragma - IBM compilers need a #pragma in "each module that needs to
140        use alloca".  Pragma indented to protect pre-ANSI cpp's.  _IBMR2 was
141        used in past versions of GMP, retained still in case it matters.
142 
143        The autoconf manual says this pragma needs to be at the start of a C
144        file, apart from comments and preprocessor directives.  Is that true?
145        xlc on aix 4.xxx doesn't seem to mind it being after prototypes etc
146        from gmp.h.
147 */
148 
149 #ifndef alloca
150 # ifdef __GNUC__
151 #  define alloca __builtin_alloca
152 # else
153 #  ifdef __DECC
154 #   define alloca(x) __ALLOCA(x)
155 #  else
156 #   ifdef _MSC_VER
157 #    include <malloc.h>
158 #    define alloca _alloca
159 #   else
160 #    if HAVE_ALLOCA_H
161 #     include <alloca.h>
162 #    else
163 #     if defined (_AIX) || defined (_IBMR2)
164  #pragma alloca
165 #     else
166        char *alloca ();
167 #     endif
168 #    endif
169 #   endif
170 #  endif
171 # endif
172 #endif
173 
174 
175 /* if not provided by gmp-mparam.h */
176 #ifndef BYTES_PER_MP_LIMB
177 #define BYTES_PER_MP_LIMB  SIZEOF_MP_LIMB_T
178 #endif
179 #define GMP_LIMB_BYTES  BYTES_PER_MP_LIMB
180 #ifndef GMP_LIMB_BITS
181 #define GMP_LIMB_BITS  (8 * SIZEOF_MP_LIMB_T)
182 #endif
183 
184 #define BITS_PER_ULONG  (8 * SIZEOF_UNSIGNED_LONG)
185 
186 
187 /* gmp_uint_least32_t is an unsigned integer type with at least 32 bits. */
188 #if HAVE_UINT_LEAST32_T
189 typedef uint_least32_t      gmp_uint_least32_t;
190 #else
191 #if SIZEOF_UNSIGNED_SHORT >= 4
192 typedef unsigned short      gmp_uint_least32_t;
193 #else
194 #if SIZEOF_UNSIGNED >= 4
195 typedef unsigned            gmp_uint_least32_t;
196 #else
197 typedef unsigned long       gmp_uint_least32_t;
198 #endif
199 #endif
200 #endif
201 
202 
203 /* gmp_intptr_t, for pointer to integer casts */
204 #if HAVE_INTPTR_T
205 typedef intptr_t            gmp_intptr_t;
206 #else /* fallback */
207 typedef size_t              gmp_intptr_t;
208 #endif
209 
210 
211 /* pre-inverse types for truncating division and modulo */
212 typedef struct {mp_limb_t inv32;} gmp_pi1_t;
213 typedef struct {mp_limb_t inv21, inv32, inv53;} gmp_pi2_t;
214 
215 
216 /* const and signed must match __gmp_const and __gmp_signed, so follow the
217    decision made for those in gmp.h.    */
218 #if ! __GMP_HAVE_CONST
219 #define const   /* empty */
220 #define signed  /* empty */
221 #endif
222 
223 /* "const" basically means a function does nothing but examine its arguments
224    and give a return value, it doesn't read or write any memory (neither
225    global nor pointed to by arguments), and has no other side-effects.  This
226    is more restrictive than "pure".  See info node "(gcc)Function
227    Attributes".  __GMP_NO_ATTRIBUTE_CONST_PURE lets tune/common.c etc turn
228    this off when trying to write timing loops.  */
229 #if HAVE_ATTRIBUTE_CONST && ! defined (__GMP_NO_ATTRIBUTE_CONST_PURE)
230 #define ATTRIBUTE_CONST  __attribute__ ((const))
231 #else
232 #define ATTRIBUTE_CONST
233 #endif
234 
235 #if HAVE_ATTRIBUTE_NORETURN
236 #define ATTRIBUTE_NORETURN  __attribute__ ((noreturn))
237 #else
238 #define ATTRIBUTE_NORETURN
239 #endif
240 
241 /* "malloc" means a function behaves like malloc in that the pointer it
242    returns doesn't alias anything.  */
243 #if HAVE_ATTRIBUTE_MALLOC
244 #define ATTRIBUTE_MALLOC  __attribute__ ((malloc))
245 #else
246 #define ATTRIBUTE_MALLOC
247 #endif
248 
249 
250 #if ! HAVE_STRCHR
251 #define strchr(s,c)  index(s,c)
252 #endif
253 
254 #if ! HAVE_MEMSET
255 #define memset(p, c, n)                 \
256   do {                                  \
257     ASSERT ((n) >= 0);                  \
258     char *__memset__p = (p);            \
259     int  __i;                           \
260     for (__i = 0; __i < (n); __i++)     \
261       __memset__p[__i] = (c);           \
262   } while (0)
263 #endif
264 
265 /* va_copy is standard in C99, and gcc provides __va_copy when in strict C89
266    mode.  Falling back to a memcpy will give maximum portability, since it
267    works no matter whether va_list is a pointer, struct or array.  */
268 #if ! defined (va_copy) && defined (__va_copy)
269 #define va_copy(dst,src)  __va_copy(dst,src)
270 #endif
271 #if ! defined (va_copy)
272 #define va_copy(dst,src) \
273   do { memcpy (&(dst), &(src), sizeof (va_list)); } while (0)
274 #endif
275 
276 
277 /* HAVE_HOST_CPU_alpha_CIX is 1 on an alpha with the CIX instructions
278    (ie. ctlz, ctpop, cttz).  */
279 #if HAVE_HOST_CPU_alphaev67 || HAVE_HOST_CPU_alphaev68  \
280   || HAVE_HOST_CPU_alphaev7
281 #define HAVE_HOST_CPU_alpha_CIX 1
282 #endif
283 
284 
285 #if defined (__cplusplus)
286 extern "C" {
287 #endif
288 
289 
290 /* Usage: TMP_DECL;
291           TMP_MARK;
292           ptr = TMP_ALLOC (bytes);
293           TMP_FREE;
294 
295    Small allocations should use TMP_SALLOC, big allocations should use
296    TMP_BALLOC.  Allocations that might be small or big should use TMP_ALLOC.
297 
298    Functions that use just TMP_SALLOC should use TMP_SDECL, TMP_SMARK, and
299    TMP_SFREE.
300 
301    TMP_DECL just declares a variable, but might be empty and so must be last
302    in a list of variables.  TMP_MARK must be done before any TMP_ALLOC.
303    TMP_ALLOC(0) is not allowed.  TMP_FREE doesn't need to be done if a
304    TMP_MARK was made, but then no TMP_ALLOCs.  */
305 
306 /* The alignment in bytes, used for TMP_ALLOCed blocks, when alloca or
307    __gmp_allocate_func doesn't already determine it.  Currently TMP_ALLOC
308    isn't used for "double"s, so that's not in the union.  */
309 union tmp_align_t {
310   mp_limb_t  l;
311   char       *p;
312 };
313 #define __TMP_ALIGN  sizeof (union tmp_align_t)
314 
315 /* Return "a" rounded upwards to a multiple of "m", if it isn't already.
316    "a" must be an unsigned type.
317    This is designed for use with a compile-time constant "m".
318    The POW2 case is expected to be usual, and gcc 3.0 and up recognises
319    "(-(8*n))%8" or the like is always zero, which means the rounding up in
320    the WANT_TMP_NOTREENTRANT version of TMP_ALLOC below will be a noop.  */
321 #define ROUND_UP_MULTIPLE(a,m)          \
322   (POW2_P(m) ? (a) + (-(a))%(m)         \
323    : (a)+(m)-1 - (((a)+(m)-1) % (m)))
324 
325 #if defined (WANT_TMP_ALLOCA) || defined (WANT_TMP_REENTRANT)
326 struct tmp_reentrant_t {
327   struct tmp_reentrant_t  *next;
328   size_t		  size;	  /* bytes, including header */
329 };
330 __GMP_DECLSPEC void *__gmp_tmp_reentrant_alloc __GMP_PROTO ((struct tmp_reentrant_t **, size_t)) ATTRIBUTE_MALLOC;
331 __GMP_DECLSPEC void  __gmp_tmp_reentrant_free __GMP_PROTO ((struct tmp_reentrant_t *));
332 #endif
333 
334 #if WANT_TMP_ALLOCA
335 #define TMP_SDECL
336 #define TMP_DECL		struct tmp_reentrant_t *__tmp_marker
337 #define TMP_SMARK
338 #define TMP_MARK		__tmp_marker = 0
339 #define TMP_SALLOC(n)		alloca(n)
340 #define TMP_BALLOC(n)		__gmp_tmp_reentrant_alloc (&__tmp_marker, n)
341 #define TMP_ALLOC(n)							\
342   (LIKELY ((n) < 65536) ? TMP_SALLOC(n) : TMP_BALLOC(n))
343 #define TMP_SFREE
344 #define TMP_FREE							   \
345   do {									   \
346     if (UNLIKELY (__tmp_marker != 0)) __gmp_tmp_reentrant_free (__tmp_marker); \
347   } while (0)
348 #endif
349 
350 #if WANT_TMP_REENTRANT
351 #define TMP_SDECL		TMP_DECL
352 #define TMP_DECL		struct tmp_reentrant_t *__tmp_marker
353 #define TMP_SMARK		TMP_MARK
354 #define TMP_MARK		__tmp_marker = 0
355 #define TMP_SALLOC(n)		TMP_ALLOC(n)
356 #define TMP_BALLOC(n)		TMP_ALLOC(n)
357 #define TMP_ALLOC(n)		__gmp_tmp_reentrant_alloc (&__tmp_marker, n)
358 #define TMP_SFREE		TMP_FREE
359 #define TMP_FREE		__gmp_tmp_reentrant_free (__tmp_marker)
360 #endif
361 
362 #if WANT_TMP_NOTREENTRANT
363 struct tmp_marker
364 {
365   struct tmp_stack *which_chunk;
366   void *alloc_point;
367 };
368 __GMP_DECLSPEC void *__gmp_tmp_alloc __GMP_PROTO ((unsigned long)) ATTRIBUTE_MALLOC;
369 __GMP_DECLSPEC void __gmp_tmp_mark __GMP_PROTO ((struct tmp_marker *));
370 __GMP_DECLSPEC void __gmp_tmp_free __GMP_PROTO ((struct tmp_marker *));
371 #define TMP_SDECL		TMP_DECL
372 #define TMP_DECL		struct tmp_marker __tmp_marker
373 #define TMP_SMARK		TMP_MARK
374 #define TMP_MARK		__gmp_tmp_mark (&__tmp_marker)
375 #define TMP_SALLOC(n)		TMP_ALLOC(n)
376 #define TMP_BALLOC(n)		TMP_ALLOC(n)
377 #define TMP_ALLOC(n)							\
378   __gmp_tmp_alloc (ROUND_UP_MULTIPLE ((unsigned long) (n), __TMP_ALIGN))
379 #define TMP_SFREE		TMP_FREE
380 #define TMP_FREE		__gmp_tmp_free (&__tmp_marker)
381 #endif
382 
383 #if WANT_TMP_DEBUG
384 /* See tal-debug.c for some comments. */
385 struct tmp_debug_t {
386   struct tmp_debug_entry_t  *list;
387   const char                *file;
388   int                       line;
389 };
390 struct tmp_debug_entry_t {
391   struct tmp_debug_entry_t  *next;
392   char                      *block;
393   size_t                    size;
394 };
395 __GMP_DECLSPEC void  __gmp_tmp_debug_mark  __GMP_PROTO ((const char *, int, struct tmp_debug_t **,
396 							 struct tmp_debug_t *,
397 							 const char *, const char *));
398 __GMP_DECLSPEC void *__gmp_tmp_debug_alloc __GMP_PROTO ((const char *, int, int,
399 							 struct tmp_debug_t **, const char *,
400 							 size_t)) ATTRIBUTE_MALLOC;
401 __GMP_DECLSPEC void  __gmp_tmp_debug_free  __GMP_PROTO ((const char *, int, int,
402 							 struct tmp_debug_t **,
403 							 const char *, const char *));
404 #define TMP_SDECL TMP_DECL_NAME(__tmp_xmarker, "__tmp_marker")
405 #define TMP_DECL TMP_DECL_NAME(__tmp_xmarker, "__tmp_marker")
406 #define TMP_SMARK TMP_MARK_NAME(__tmp_xmarker, "__tmp_marker")
407 #define TMP_MARK TMP_MARK_NAME(__tmp_xmarker, "__tmp_marker")
408 #define TMP_SFREE TMP_FREE_NAME(__tmp_xmarker, "__tmp_marker")
409 #define TMP_FREE TMP_FREE_NAME(__tmp_xmarker, "__tmp_marker")
410 /* The marker variable is designed to provoke an uninitialized variable
411    warning from the compiler if TMP_FREE is used without a TMP_MARK.
412    __tmp_marker_inscope does the same for TMP_ALLOC.  Runtime tests pick
413    these things up too.  */
414 #define TMP_DECL_NAME(marker, marker_name)                      \
415   int marker;                                                   \
416   int __tmp_marker_inscope;                                     \
417   const char *__tmp_marker_name = marker_name;                  \
418   struct tmp_debug_t  __tmp_marker_struct;                      \
419   /* don't demand NULL, just cast a zero */                     \
420   struct tmp_debug_t  *__tmp_marker = (struct tmp_debug_t *) 0
421 #define TMP_MARK_NAME(marker, marker_name)                      \
422   do {                                                          \
423     marker = 1;                                                 \
424     __tmp_marker_inscope = 1;                                   \
425     __gmp_tmp_debug_mark  (ASSERT_FILE, ASSERT_LINE,            \
426                            &__tmp_marker, &__tmp_marker_struct, \
427                            __tmp_marker_name, marker_name);     \
428   } while (0)
429 #define TMP_SALLOC(n)		TMP_ALLOC(n)
430 #define TMP_BALLOC(n)		TMP_ALLOC(n)
431 #define TMP_ALLOC(size)                                                 \
432   __gmp_tmp_debug_alloc (ASSERT_FILE, ASSERT_LINE,                      \
433                          __tmp_marker_inscope,                          \
434                          &__tmp_marker, __tmp_marker_name, size)
435 #define TMP_FREE_NAME(marker, marker_name)                      \
436   do {                                                          \
437     __gmp_tmp_debug_free  (ASSERT_FILE, ASSERT_LINE,            \
438                            marker, &__tmp_marker,               \
439                            __tmp_marker_name, marker_name);     \
440   } while (0)
441 #endif /* WANT_TMP_DEBUG */
442 
443 
444 /* Allocating various types. */
445 #define TMP_ALLOC_TYPE(n,type)  ((type *) TMP_ALLOC ((n) * sizeof (type)))
446 #define TMP_SALLOC_TYPE(n,type) ((type *) TMP_SALLOC ((n) * sizeof (type)))
447 #define TMP_BALLOC_TYPE(n,type) ((type *) TMP_BALLOC ((n) * sizeof (type)))
448 #define TMP_ALLOC_LIMBS(n)      TMP_ALLOC_TYPE(n,mp_limb_t)
449 #define TMP_SALLOC_LIMBS(n)     TMP_SALLOC_TYPE(n,mp_limb_t)
450 #define TMP_BALLOC_LIMBS(n)     TMP_BALLOC_TYPE(n,mp_limb_t)
451 #define TMP_ALLOC_MP_PTRS(n)    TMP_ALLOC_TYPE(n,mp_ptr)
452 #define TMP_SALLOC_MP_PTRS(n)   TMP_SALLOC_TYPE(n,mp_ptr)
453 #define TMP_BALLOC_MP_PTRS(n)   TMP_BALLOC_TYPE(n,mp_ptr)
454 
455 /* It's more efficient to allocate one block than two.  This is certainly
456    true of the malloc methods, but it can even be true of alloca if that
457    involves copying a chunk of stack (various RISCs), or a call to a stack
458    bounds check (mingw).  In any case, when debugging keep separate blocks
459    so a redzoning malloc debugger can protect each individually.  */
460 #define TMP_ALLOC_LIMBS_2(xp,xsize, yp,ysize)           \
461   do {                                                  \
462     if (WANT_TMP_DEBUG)                                 \
463       {                                                 \
464         (xp) = TMP_ALLOC_LIMBS (xsize);                 \
465         (yp) = TMP_ALLOC_LIMBS (ysize);                 \
466       }                                                 \
467     else                                                \
468       {                                                 \
469         (xp) = TMP_ALLOC_LIMBS ((xsize) + (ysize));     \
470         (yp) = (xp) + (xsize);                          \
471       }                                                 \
472   } while (0)
473 
474 
475 /* From gmp.h, nicer names for internal use. */
476 #define CRAY_Pragma(str)               __GMP_CRAY_Pragma(str)
477 #define MPN_CMP(result, xp, yp, size)  __GMPN_CMP(result, xp, yp, size)
478 #define LIKELY(cond)                   __GMP_LIKELY(cond)
479 #define UNLIKELY(cond)                 __GMP_UNLIKELY(cond)
480 
481 #define ABS(x) ((x) >= 0 ? (x) : -(x))
482 #define ABS_CAST(T,x) ((x) >= 0 ? (T)(x) : -((T)((x) + 1) - 1))
483 #undef MIN
484 #define MIN(l,o) ((l) < (o) ? (l) : (o))
485 #undef MAX
486 #define MAX(h,i) ((h) > (i) ? (h) : (i))
487 #define numberof(x)  (sizeof (x) / sizeof ((x)[0]))
488 
489 /* Field access macros.  */
490 #define SIZ(x) ((x)->_mp_size)
491 #define ABSIZ(x) ABS (SIZ (x))
492 #define PTR(x) ((x)->_mp_d)
493 #define LIMBS(x) ((x)->_mp_d)
494 #define EXP(x) ((x)->_mp_exp)
495 #define PREC(x) ((x)->_mp_prec)
496 #define ALLOC(x) ((x)->_mp_alloc)
497 
498 /* n-1 inverts any low zeros and the lowest one bit.  If n&(n-1) leaves zero
499    then that lowest one bit must have been the only bit set.  n==0 will
500    return true though, so avoid that.  */
501 #define POW2_P(n)  (((n) & ((n) - 1)) == 0)
502 
503 
504 /* The "short" defines are a bit different because shorts are promoted to
505    ints by ~ or >> etc.
506 
507    #ifndef's are used since on some systems (HP?) header files other than
508    limits.h setup these defines.  We could forcibly #undef in that case, but
509    there seems no need to worry about that.  */
510 
511 #ifndef ULONG_MAX
512 #define ULONG_MAX   __GMP_ULONG_MAX
513 #endif
514 #ifndef UINT_MAX
515 #define UINT_MAX    __GMP_UINT_MAX
516 #endif
517 #ifndef USHRT_MAX
518 #define USHRT_MAX   __GMP_USHRT_MAX
519 #endif
520 #define MP_LIMB_T_MAX      (~ (mp_limb_t) 0)
521 
522 /* Must cast ULONG_MAX etc to unsigned long etc, since they might not be
523    unsigned on a K&R compiler.  In particular the HP-UX 10 bundled K&R cc
524    treats the plain decimal values in <limits.h> as signed.  */
525 #define ULONG_HIGHBIT      (ULONG_MAX ^ ((unsigned long) ULONG_MAX >> 1))
526 #define UINT_HIGHBIT       (UINT_MAX ^ ((unsigned) UINT_MAX >> 1))
527 #define USHRT_HIGHBIT      ((unsigned short) (USHRT_MAX ^ ((unsigned short) USHRT_MAX >> 1)))
528 #define GMP_LIMB_HIGHBIT  (MP_LIMB_T_MAX ^ (MP_LIMB_T_MAX >> 1))
529 
530 #ifndef LONG_MIN
531 #define LONG_MIN           ((long) ULONG_HIGHBIT)
532 #endif
533 #ifndef LONG_MAX
534 #define LONG_MAX           (-(LONG_MIN+1))
535 #endif
536 
537 #ifndef INT_MIN
538 #define INT_MIN            ((int) UINT_HIGHBIT)
539 #endif
540 #ifndef INT_MAX
541 #define INT_MAX            (-(INT_MIN+1))
542 #endif
543 
544 #ifndef SHRT_MIN
545 #define SHRT_MIN           ((short) USHRT_HIGHBIT)
546 #endif
547 #ifndef SHRT_MAX
548 #define SHRT_MAX           ((short) (-(SHRT_MIN+1)))
549 #endif
550 
551 #if __GMP_MP_SIZE_T_INT
552 #define MP_SIZE_T_MAX      INT_MAX
553 #define MP_SIZE_T_MIN      INT_MIN
554 #else
555 #define MP_SIZE_T_MAX      LONG_MAX
556 #define MP_SIZE_T_MIN      LONG_MIN
557 #endif
558 
559 /* mp_exp_t is the same as mp_size_t */
560 #define MP_EXP_T_MAX   MP_SIZE_T_MAX
561 #define MP_EXP_T_MIN   MP_SIZE_T_MIN
562 
563 #define LONG_HIGHBIT       LONG_MIN
564 #define INT_HIGHBIT        INT_MIN
565 #define SHRT_HIGHBIT       SHRT_MIN
566 
567 
568 #define GMP_NUMB_HIGHBIT  (CNST_LIMB(1) << (GMP_NUMB_BITS-1))
569 
570 #if GMP_NAIL_BITS == 0
571 #define GMP_NAIL_LOWBIT   CNST_LIMB(0)
572 #else
573 #define GMP_NAIL_LOWBIT   (CNST_LIMB(1) << GMP_NUMB_BITS)
574 #endif
575 
576 #if GMP_NAIL_BITS != 0
577 /* Set various *_THRESHOLD values to be used for nails.  Thus we avoid using
578    code that has not yet been qualified.  */
579 
580 #undef  DC_DIV_QR_THRESHOLD
581 #define DC_DIV_QR_THRESHOLD              50
582 
583 #undef DIVREM_1_NORM_THRESHOLD
584 #undef DIVREM_1_UNNORM_THRESHOLD
585 #undef MOD_1_NORM_THRESHOLD
586 #undef MOD_1_UNNORM_THRESHOLD
587 #undef USE_PREINV_DIVREM_1
588 #undef DIVREM_2_THRESHOLD
589 #undef DIVEXACT_1_THRESHOLD
590 #define DIVREM_1_NORM_THRESHOLD           MP_SIZE_T_MAX  /* no preinv */
591 #define DIVREM_1_UNNORM_THRESHOLD         MP_SIZE_T_MAX  /* no preinv */
592 #define MOD_1_NORM_THRESHOLD              MP_SIZE_T_MAX  /* no preinv */
593 #define MOD_1_UNNORM_THRESHOLD            MP_SIZE_T_MAX  /* no preinv */
594 #define USE_PREINV_DIVREM_1               0  /* no preinv */
595 #define DIVREM_2_THRESHOLD                MP_SIZE_T_MAX  /* no preinv */
596 
597 /* mpn/generic/mul_fft.c is not nails-capable. */
598 #undef  MUL_FFT_THRESHOLD
599 #undef  SQR_FFT_THRESHOLD
600 #define MUL_FFT_THRESHOLD                MP_SIZE_T_MAX
601 #define SQR_FFT_THRESHOLD                MP_SIZE_T_MAX
602 #endif
603 
604 /* Swap macros. */
605 
606 #define MP_LIMB_T_SWAP(x, y)                    \
607   do {                                          \
608     mp_limb_t __mp_limb_t_swap__tmp = (x);      \
609     (x) = (y);                                  \
610     (y) = __mp_limb_t_swap__tmp;                \
611   } while (0)
612 #define MP_SIZE_T_SWAP(x, y)                    \
613   do {                                          \
614     mp_size_t __mp_size_t_swap__tmp = (x);      \
615     (x) = (y);                                  \
616     (y) = __mp_size_t_swap__tmp;                \
617   } while (0)
618 
619 #define MP_PTR_SWAP(x, y)               \
620   do {                                  \
621     mp_ptr __mp_ptr_swap__tmp = (x);    \
622     (x) = (y);                          \
623     (y) = __mp_ptr_swap__tmp;           \
624   } while (0)
625 #define MP_SRCPTR_SWAP(x, y)                    \
626   do {                                          \
627     mp_srcptr __mp_srcptr_swap__tmp = (x);      \
628     (x) = (y);                                  \
629     (y) = __mp_srcptr_swap__tmp;                \
630   } while (0)
631 
632 #define MPN_PTR_SWAP(xp,xs, yp,ys)      \
633   do {                                  \
634     MP_PTR_SWAP (xp, yp);               \
635     MP_SIZE_T_SWAP (xs, ys);            \
636   } while(0)
637 #define MPN_SRCPTR_SWAP(xp,xs, yp,ys)   \
638   do {                                  \
639     MP_SRCPTR_SWAP (xp, yp);            \
640     MP_SIZE_T_SWAP (xs, ys);            \
641   } while(0)
642 
643 #define MPZ_PTR_SWAP(x, y)              \
644   do {                                  \
645     mpz_ptr __mpz_ptr_swap__tmp = (x);  \
646     (x) = (y);                          \
647     (y) = __mpz_ptr_swap__tmp;          \
648   } while (0)
649 #define MPZ_SRCPTR_SWAP(x, y)                   \
650   do {                                          \
651     mpz_srcptr __mpz_srcptr_swap__tmp = (x);    \
652     (x) = (y);                                  \
653     (y) = __mpz_srcptr_swap__tmp;               \
654   } while (0)
655 
656 
657 /* Enhancement: __gmp_allocate_func could have "__attribute__ ((malloc))",
658    but current gcc (3.0) doesn't seem to support that.  */
659 __GMP_DECLSPEC extern void * (*__gmp_allocate_func) __GMP_PROTO ((size_t));
660 __GMP_DECLSPEC extern void * (*__gmp_reallocate_func) __GMP_PROTO ((void *, size_t, size_t));
661 __GMP_DECLSPEC extern void   (*__gmp_free_func) __GMP_PROTO ((void *, size_t));
662 
663 __GMP_DECLSPEC void *__gmp_default_allocate __GMP_PROTO ((size_t));
664 __GMP_DECLSPEC void *__gmp_default_reallocate __GMP_PROTO ((void *, size_t, size_t));
665 __GMP_DECLSPEC void __gmp_default_free __GMP_PROTO ((void *, size_t));
666 
667 #define __GMP_ALLOCATE_FUNC_TYPE(n,type) \
668   ((type *) (*__gmp_allocate_func) ((n) * sizeof (type)))
669 #define __GMP_ALLOCATE_FUNC_LIMBS(n)   __GMP_ALLOCATE_FUNC_TYPE (n, mp_limb_t)
670 
671 #define __GMP_REALLOCATE_FUNC_TYPE(p, old_size, new_size, type) \
672   ((type *) (*__gmp_reallocate_func)                            \
673    (p, (old_size) * sizeof (type), (new_size) * sizeof (type)))
674 #define __GMP_REALLOCATE_FUNC_LIMBS(p, old_size, new_size) \
675   __GMP_REALLOCATE_FUNC_TYPE(p, old_size, new_size, mp_limb_t)
676 
677 #define __GMP_FREE_FUNC_TYPE(p,n,type) (*__gmp_free_func) (p, (n) * sizeof (type))
678 #define __GMP_FREE_FUNC_LIMBS(p,n)     __GMP_FREE_FUNC_TYPE (p, n, mp_limb_t)
679 
680 #define __GMP_REALLOCATE_FUNC_MAYBE(ptr, oldsize, newsize)      \
681   do {                                                          \
682     if ((oldsize) != (newsize))                                 \
683       (ptr) = (*__gmp_reallocate_func) (ptr, oldsize, newsize); \
684   } while (0)
685 
686 #define __GMP_REALLOCATE_FUNC_MAYBE_TYPE(ptr, oldsize, newsize, type)   \
687   do {                                                                  \
688     if ((oldsize) != (newsize))                                         \
689       (ptr) = (type *) (*__gmp_reallocate_func)                         \
690         (ptr, (oldsize) * sizeof (type), (newsize) * sizeof (type));    \
691   } while (0)
692 
693 
694 /* Dummy for non-gcc, code involving it will go dead. */
695 #if ! defined (__GNUC__) || __GNUC__ < 2
696 #define __builtin_constant_p(x)   0
697 #endif
698 
699 
700 /* In gcc 2.96 and up on i386, tail calls are optimized to jumps if the
701    stack usage is compatible.  __attribute__ ((regparm (N))) helps by
702    putting leading parameters in registers, avoiding extra stack.
703 
704    regparm cannot be used with calls going through the PLT, because the
705    binding code there may clobber the registers (%eax, %edx, %ecx) used for
706    the regparm parameters.  Calls to local (ie. static) functions could
707    still use this, if we cared to differentiate locals and globals.
708 
709    On athlon-unknown-freebsd4.9 with gcc 3.3.3, regparm cannot be used with
710    -p or -pg profiling, since that version of gcc doesn't realize the
711    .mcount calls will clobber the parameter registers.  Other systems are
712    ok, like debian with glibc 2.3.2 (mcount doesn't clobber), but we don't
713    bother to try to detect this.  regparm is only an optimization so we just
714    disable it when profiling (profiling being a slowdown anyway).  */
715 
716 #if HAVE_HOST_CPU_FAMILY_x86 && __GMP_GNUC_PREREQ (2,96) && ! defined (PIC) \
717   && ! WANT_PROFILING_PROF && ! WANT_PROFILING_GPROF
718 #define USE_LEADING_REGPARM 1
719 #else
720 #define USE_LEADING_REGPARM 0
721 #endif
722 
723 /* Macros for altering parameter order according to regparm usage. */
724 #if USE_LEADING_REGPARM
725 #define REGPARM_2_1(a,b,x)    x,a,b
726 #define REGPARM_3_1(a,b,c,x)  x,a,b,c
727 #define REGPARM_ATTR(n) __attribute__ ((regparm (n)))
728 #else
729 #define REGPARM_2_1(a,b,x)    a,b,x
730 #define REGPARM_3_1(a,b,c,x)  a,b,c,x
731 #define REGPARM_ATTR(n)
732 #endif
733 
734 
735 /* ASM_L gives a local label for a gcc asm block, for use when temporary
736    local labels like "1:" might not be available, which is the case for
737    instance on the x86s (the SCO assembler doesn't support them).
738 
739    The label generated is made unique by including "%=" which is a unique
740    number for each insn.  This ensures the same name can be used in multiple
741    asm blocks, perhaps via a macro.  Since jumps between asm blocks are not
742    allowed there's no need for a label to be usable outside a single
743    block.  */
744 
745 #define ASM_L(name)  LSYM_PREFIX "asm_%=_" #name
746 
747 
748 #if defined (__GNUC__) && HAVE_HOST_CPU_FAMILY_x86
749 #if 0
750 /* FIXME: Check that these actually improve things.
751    FIXME: Need a cld after each std.
752    FIXME: Can't have inputs in clobbered registers, must describe them as
753    dummy outputs, and add volatile. */
754 #define MPN_COPY_INCR(DST, SRC, N)					\
755   __asm__ ("cld\n\trep\n\tmovsl" : :					\
756 	   "D" (DST), "S" (SRC), "c" (N) :				\
757 	   "cx", "di", "si", "memory")
758 #define MPN_COPY_DECR(DST, SRC, N)					\
759   __asm__ ("std\n\trep\n\tmovsl" : :					\
760 	   "D" ((DST) + (N) - 1), "S" ((SRC) + (N) - 1), "c" (N) :	\
761 	   "cx", "di", "si", "memory")
762 #endif
763 #endif
764 
765 
766 __GMP_DECLSPEC void __gmpz_aorsmul_1 __GMP_PROTO ((REGPARM_3_1 (mpz_ptr, mpz_srcptr, mp_limb_t, mp_size_t))) REGPARM_ATTR(1);
767 #define mpz_aorsmul_1(w,u,v,sub)  __gmpz_aorsmul_1 (REGPARM_3_1 (w, u, v, sub))
768 
769 #define mpz_n_pow_ui __gmpz_n_pow_ui
770 __GMP_DECLSPEC void    mpz_n_pow_ui __GMP_PROTO ((mpz_ptr, mp_srcptr, mp_size_t, unsigned long));
771 
772 
773 #define mpn_addmul_1c __MPN(addmul_1c)
774 __GMP_DECLSPEC mp_limb_t mpn_addmul_1c __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t));
775 
776 #define mpn_addmul_2 __MPN(addmul_2)
777 __GMP_DECLSPEC mp_limb_t mpn_addmul_2 __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr));
778 
779 #define mpn_addmul_3 __MPN(addmul_3)
780 __GMP_DECLSPEC mp_limb_t mpn_addmul_3 __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr));
781 
782 #define mpn_addmul_4 __MPN(addmul_4)
783 __GMP_DECLSPEC mp_limb_t mpn_addmul_4 __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr));
784 
785 #define mpn_addmul_5 __MPN(addmul_5)
786 __GMP_DECLSPEC mp_limb_t mpn_addmul_5 __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr));
787 
788 #define mpn_addmul_6 __MPN(addmul_6)
789 __GMP_DECLSPEC mp_limb_t mpn_addmul_6 __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr));
790 
791 #define mpn_addmul_7 __MPN(addmul_7)
792 __GMP_DECLSPEC mp_limb_t mpn_addmul_7 __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr));
793 
794 #define mpn_addmul_8 __MPN(addmul_8)
795 __GMP_DECLSPEC mp_limb_t mpn_addmul_8 __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr));
796 
797 /* mpn_addlsh1_n(c,a,b,n), when it exists, sets {c,n} to {a,n}+2*{b,n}, and
798    returns the carry out (0, 1 or 2).  */
799 #define mpn_addlsh1_n __MPN(addlsh1_n)
800 __GMP_DECLSPEC mp_limb_t mpn_addlsh1_n __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
801 
802 /* mpn_addlsh2_n(c,a,b,n), when it exists, sets {c,n} to {a,n}+4*{b,n}, and
803    returns the carry out (0, ..., 4).  */
804 #define mpn_addlsh2_n __MPN(addlsh2_n)
805 __GMP_DECLSPEC mp_limb_t mpn_addlsh2_n __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
806 
807 /* mpn_addlsh_n(c,a,b,n,k), when it exists, sets {c,n} to {a,n}+2^k*{b,n}, and
808    returns the carry out (0, ..., 2^k).  */
809 #define mpn_addlsh_n __MPN(addlsh_n)
810   __GMP_DECLSPEC mp_limb_t mpn_addlsh_n __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, unsigned int));
811 
812 /* mpn_sublsh1_n(c,a,b,n), when it exists, sets {c,n} to {a,n}-2*{b,n}, and
813    returns the borrow out (0, 1 or 2).  */
814 #define mpn_sublsh1_n __MPN(sublsh1_n)
815 __GMP_DECLSPEC mp_limb_t mpn_sublsh1_n __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
816 
817 /* mpn_rsblsh1_n(c,a,b,n), when it exists, sets {c,n} to 2*{b,n}-{a,n}, and
818    returns the carry out (-1, 0, 1).  */
819 #define mpn_rsblsh1_n __MPN(rsblsh1_n)
820 __GMP_DECLSPEC mp_limb_signed_t mpn_rsblsh1_n __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
821 
822 /* mpn_sublsh2_n(c,a,b,n), when it exists, sets {c,n} to {a,n}-4*{b,n}, and
823    returns the borrow out (FIXME 0, 1, 2 or 3).  */
824 #define mpn_sublsh2_n __MPN(sublsh2_n)
825 __GMP_DECLSPEC mp_limb_t mpn_sublsh2_n __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
826 
827 /* mpn_rsblsh2_n(c,a,b,n), when it exists, sets {c,n} to 4*{b,n}-{a,n}, and
828    returns the carry out (-1, ..., 3).  */
829 #define mpn_rsblsh2_n __MPN(rsblsh2_n)
830 __GMP_DECLSPEC mp_limb_signed_t mpn_rsblsh2_n __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
831 
832 /* mpn_rsblsh_n(c,a,b,n,k), when it exists, sets {c,n} to 2^k*{b,n}-{a,n}, and
833    returns the carry out (-1, 0, ..., 2^k-1).  */
834 #define mpn_rsblsh_n __MPN(rsblsh_n)
835 __GMP_DECLSPEC mp_limb_signed_t mpn_rsblsh_n __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, unsigned int));
836 
837 /* mpn_rsh1add_n(c,a,b,n), when it exists, sets {c,n} to ({a,n} + {b,n}) >> 1,
838    and returns the bit rshifted out (0 or 1).  */
839 #define mpn_rsh1add_n __MPN(rsh1add_n)
840 __GMP_DECLSPEC mp_limb_t mpn_rsh1add_n __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
841 #define mpn_rsh1add_nc __MPN(rsh1add_nc)
842 __GMP_DECLSPEC mp_limb_t mpn_rsh1add_nc __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t));
843 
844 /* mpn_rsh1sub_n(c,a,b,n), when it exists, sets {c,n} to ({a,n} - {b,n}) >> 1,
845    and returns the bit rshifted out (0 or 1).  If there's a borrow from the
846    subtract, it's stored as a 1 in the high bit of c[n-1], like a twos
847    complement negative.  */
848 #define mpn_rsh1sub_n __MPN(rsh1sub_n)
849 __GMP_DECLSPEC mp_limb_t mpn_rsh1sub_n __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
850 #define mpn_rsh1sub_nc __MPN(rsh1sub_nc)
851 __GMP_DECLSPEC mp_limb_t mpn_rsh1sub_nc __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t));
852 
853 #define mpn_lshiftc __MPN(lshiftc)
854 __GMP_DECLSPEC mp_limb_t mpn_lshiftc __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, unsigned int));
855 
856 #define mpn_add_n_sub_n __MPN(add_n_sub_n)
857 __GMP_DECLSPEC mp_limb_t mpn_add_n_sub_n __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
858 
859 #define mpn_add_n_sub_nc __MPN(add_n_sub_nc)
860 __GMP_DECLSPEC mp_limb_t mpn_add_n_sub_nc __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t));
861 
862 #define mpn_addaddmul_1msb0 __MPN(addaddmul_1msb0)
863 __GMP_DECLSPEC mp_limb_t mpn_addaddmul_1msb0 __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t));
864 
865 #define mpn_divrem_1c __MPN(divrem_1c)
866 __GMP_DECLSPEC mp_limb_t mpn_divrem_1c __GMP_PROTO ((mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t));
867 
868 #define mpn_dump __MPN(dump)
869 __GMP_DECLSPEC void mpn_dump __GMP_PROTO ((mp_srcptr, mp_size_t));
870 
871 #define mpn_fib2_ui __MPN(fib2_ui)
872 __GMP_DECLSPEC mp_size_t mpn_fib2_ui __GMP_PROTO ((mp_ptr, mp_ptr, unsigned long));
873 
874 /* Remap names of internal mpn functions.  */
875 #define __clz_tab               __MPN(clz_tab)
876 #define mpn_udiv_w_sdiv		__MPN(udiv_w_sdiv)
877 
878 #define mpn_jacobi_base __MPN(jacobi_base)
879 __GMP_DECLSPEC int mpn_jacobi_base __GMP_PROTO ((mp_limb_t, mp_limb_t, int)) ATTRIBUTE_CONST;
880 
881 #define mpn_mod_1c __MPN(mod_1c)
882 __GMP_DECLSPEC mp_limb_t mpn_mod_1c __GMP_PROTO ((mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t)) __GMP_ATTRIBUTE_PURE;
883 
884 #define mpn_mul_1c __MPN(mul_1c)
885 __GMP_DECLSPEC mp_limb_t mpn_mul_1c __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t));
886 
887 #define mpn_mul_2 __MPN(mul_2)
888 __GMP_DECLSPEC mp_limb_t mpn_mul_2 __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr));
889 
890 #define mpn_mul_3 __MPN(mul_3)
891 __GMP_DECLSPEC mp_limb_t mpn_mul_3 __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr));
892 
893 #define mpn_mul_4 __MPN(mul_4)
894 __GMP_DECLSPEC mp_limb_t mpn_mul_4 __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr));
895 
896 #ifndef mpn_mul_basecase  /* if not done with cpuvec in a fat binary */
897 #define mpn_mul_basecase __MPN(mul_basecase)
898 __GMP_DECLSPEC void mpn_mul_basecase __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t));
899 #endif
900 
901 #define mpn_mullo_n __MPN(mullo_n)
902 __GMP_DECLSPEC void mpn_mullo_n __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
903 
904 #define mpn_mullo_basecase __MPN(mullo_basecase)
905 __GMP_DECLSPEC void mpn_mullo_basecase __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
906 
907 #define mpn_sqr __MPN(sqr)
908 __GMP_DECLSPEC void mpn_sqr __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t));
909 
910 #ifndef mpn_sqr_basecase  /* if not done with cpuvec in a fat binary */
911 #define mpn_sqr_basecase __MPN(sqr_basecase)
912 __GMP_DECLSPEC void mpn_sqr_basecase __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t));
913 #endif
914 
915 #define mpn_submul_1c __MPN(submul_1c)
916 __GMP_DECLSPEC mp_limb_t mpn_submul_1c __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t));
917 
918 #define mpn_redc_1 __MPN(redc_1)
919 __GMP_DECLSPEC void mpn_redc_1 __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_limb_t));
920 
921 #define mpn_redc_2 __MPN(redc_2)
922 __GMP_DECLSPEC void mpn_redc_2 __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_srcptr));
923 #define mpn_redc_n __MPN(redc_n)
924 __GMP_DECLSPEC void mpn_redc_n __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_srcptr));
925 
926 
927 #define mpn_mod_1_1p_cps __MPN(mod_1_1p_cps)
928 __GMP_DECLSPEC void mpn_mod_1_1p_cps __GMP_PROTO ((mp_limb_t [4], mp_limb_t));
929 #define mpn_mod_1_1p __MPN(mod_1_1p)
930 __GMP_DECLSPEC mp_limb_t mpn_mod_1_1p __GMP_PROTO ((mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t [4])) __GMP_ATTRIBUTE_PURE;
931 
932 #define mpn_mod_1s_2p_cps __MPN(mod_1s_2p_cps)
933 __GMP_DECLSPEC void mpn_mod_1s_2p_cps __GMP_PROTO ((mp_limb_t [5], mp_limb_t));
934 #define mpn_mod_1s_2p __MPN(mod_1s_2p)
935 __GMP_DECLSPEC mp_limb_t mpn_mod_1s_2p __GMP_PROTO ((mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t [5])) __GMP_ATTRIBUTE_PURE;
936 
937 #define mpn_mod_1s_3p_cps __MPN(mod_1s_3p_cps)
938 __GMP_DECLSPEC void mpn_mod_1s_3p_cps __GMP_PROTO ((mp_limb_t [6], mp_limb_t));
939 #define mpn_mod_1s_3p __MPN(mod_1s_3p)
940 __GMP_DECLSPEC mp_limb_t mpn_mod_1s_3p __GMP_PROTO ((mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t [6])) __GMP_ATTRIBUTE_PURE;
941 
942 #define mpn_mod_1s_4p_cps __MPN(mod_1s_4p_cps)
943 __GMP_DECLSPEC void mpn_mod_1s_4p_cps __GMP_PROTO ((mp_limb_t [7], mp_limb_t));
944 #define mpn_mod_1s_4p __MPN(mod_1s_4p)
945 __GMP_DECLSPEC mp_limb_t mpn_mod_1s_4p __GMP_PROTO ((mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t [7])) __GMP_ATTRIBUTE_PURE;
946 
947 #define mpn_bc_mulmod_bnm1 __MPN(bc_mulmod_bnm1)
948 __GMP_DECLSPEC void mpn_bc_mulmod_bnm1 __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_ptr));
949 #define mpn_mulmod_bnm1 __MPN(mulmod_bnm1)
950 __GMP_DECLSPEC void mpn_mulmod_bnm1 __GMP_PROTO ((mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
951 #define mpn_mulmod_bnm1_next_size __MPN(mulmod_bnm1_next_size)
952 __GMP_DECLSPEC mp_size_t mpn_mulmod_bnm1_next_size __GMP_PROTO ((mp_size_t)) ATTRIBUTE_CONST;
953 static inline mp_size_t
mpn_mulmod_bnm1_itch(mp_size_t rn,mp_size_t an,mp_size_t bn)954 mpn_mulmod_bnm1_itch (mp_size_t rn, mp_size_t an, mp_size_t bn) {
955   mp_size_t n, itch;
956   n = rn >> 1;
957   itch = rn + 4 +
958     (an > n ? (bn > n ? rn : n) : 0);
959   return itch;
960 }
961 
962 #define mpn_sqrmod_bnm1 __MPN(sqrmod_bnm1)
963 __GMP_DECLSPEC void mpn_sqrmod_bnm1 __GMP_PROTO ((mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
964 #define mpn_sqrmod_bnm1_next_size __MPN(sqrmod_bnm1_next_size)
965 __GMP_DECLSPEC mp_size_t mpn_sqrmod_bnm1_next_size __GMP_PROTO ((mp_size_t)) ATTRIBUTE_CONST;
966 static inline mp_size_t
mpn_sqrmod_bnm1_itch(mp_size_t rn,mp_size_t an)967 mpn_sqrmod_bnm1_itch (mp_size_t rn, mp_size_t an) {
968   mp_size_t n, itch;
969   n = rn >> 1;
970   itch = rn + 3 +
971     (an > n ? an : 0);
972   return itch;
973 }
974 
975 typedef __gmp_randstate_struct *gmp_randstate_ptr;
976 typedef const __gmp_randstate_struct *gmp_randstate_srcptr;
977 
978 /* Pseudo-random number generator function pointers structure.  */
979 typedef struct {
980   void (*randseed_fn) __GMP_PROTO ((gmp_randstate_t, mpz_srcptr));
981   void (*randget_fn) __GMP_PROTO ((gmp_randstate_t, mp_ptr, unsigned long int));
982   void (*randclear_fn) __GMP_PROTO ((gmp_randstate_t));
983   void (*randiset_fn) __GMP_PROTO ((gmp_randstate_ptr, gmp_randstate_srcptr));
984 } gmp_randfnptr_t;
985 
986 /* Macro to obtain a void pointer to the function pointers structure.  */
987 #define RNG_FNPTR(rstate) ((rstate)->_mp_algdata._mp_lc)
988 
989 /* Macro to obtain a pointer to the generator's state.
990    When used as a lvalue the rvalue needs to be cast to mp_ptr.  */
991 #define RNG_STATE(rstate) ((rstate)->_mp_seed->_mp_d)
992 
993 /* Write a given number of random bits to rp.  */
994 #define _gmp_rand(rp, state, bits)                              \
995   do {                                                          \
996     gmp_randstate_ptr  __rstate = (state);                      \
997     (*((gmp_randfnptr_t *) RNG_FNPTR (__rstate))->randget_fn)   \
998        (__rstate, rp, bits);                                    \
999   } while (0)
1000 
1001 __GMP_DECLSPEC void __gmp_randinit_mt_noseed __GMP_PROTO ((gmp_randstate_t));
1002 
1003 
1004 /* __gmp_rands is the global state for the old-style random functions, and
1005    is also used in the test programs (hence the __GMP_DECLSPEC).
1006 
1007    There's no seeding here, so mpz_random etc will generate the same
1008    sequence every time.  This is not unlike the C library random functions
1009    if you don't seed them, so perhaps it's acceptable.  Digging up a seed
1010    from /dev/random or the like would work on many systems, but might
1011    encourage a false confidence, since it'd be pretty much impossible to do
1012    something that would work reliably everywhere.  In any case the new style
1013    functions are recommended to applications which care about randomness, so
1014    the old functions aren't too important.  */
1015 
1016 __GMP_DECLSPEC extern char             __gmp_rands_initialized;
1017 __GMP_DECLSPEC extern gmp_randstate_t  __gmp_rands;
1018 
1019 #define RANDS                                       \
1020   ((__gmp_rands_initialized ? 0                     \
1021     : (__gmp_rands_initialized = 1,                 \
1022        __gmp_randinit_mt_noseed (__gmp_rands), 0)), \
1023    __gmp_rands)
1024 
1025 /* this is used by the test programs, to free memory */
1026 #define RANDS_CLEAR()                   \
1027   do {                                  \
1028     if (__gmp_rands_initialized)        \
1029       {                                 \
1030         __gmp_rands_initialized = 0;    \
1031         gmp_randclear (__gmp_rands);    \
1032       }                                 \
1033   } while (0)
1034 
1035 
1036 /* For a threshold between algorithms A and B, size>=thresh is where B
1037    should be used.  Special value MP_SIZE_T_MAX means only ever use A, or
1038    value 0 means only ever use B.  The tests for these special values will
1039    be compile-time constants, so the compiler should be able to eliminate
1040    the code for the unwanted algorithm.  */
1041 
1042 #define ABOVE_THRESHOLD(size,thresh)    \
1043   ((thresh) == 0                        \
1044    || ((thresh) != MP_SIZE_T_MAX        \
1045        && (size) >= (thresh)))
1046 #define BELOW_THRESHOLD(size,thresh)  (! ABOVE_THRESHOLD (size, thresh))
1047 
1048 #define MPN_TOOM22_MUL_MINSIZE    4
1049 #define MPN_TOOM2_SQR_MINSIZE     4
1050 
1051 #define MPN_TOOM33_MUL_MINSIZE   17
1052 #define MPN_TOOM3_SQR_MINSIZE    17
1053 
1054 #define MPN_TOOM44_MUL_MINSIZE   30
1055 #define MPN_TOOM4_SQR_MINSIZE    30
1056 
1057 #define MPN_TOOM6H_MUL_MINSIZE   46
1058 #define MPN_TOOM6_SQR_MINSIZE    46
1059 
1060 #define MPN_TOOM8H_MUL_MINSIZE   86
1061 #define MPN_TOOM8_SQR_MINSIZE    86
1062 
1063 #define MPN_TOOM32_MUL_MINSIZE   10
1064 #define MPN_TOOM42_MUL_MINSIZE   10
1065 #define MPN_TOOM43_MUL_MINSIZE   49 /* ??? */
1066 #define MPN_TOOM53_MUL_MINSIZE   49 /* ??? */
1067 #define MPN_TOOM63_MUL_MINSIZE   49
1068 
1069 #define   mpn_sqr_diagonal __MPN(sqr_diagonal)
1070 __GMP_DECLSPEC void      mpn_sqr_diagonal __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t));
1071 
1072 #define   mpn_toom_interpolate_5pts __MPN(toom_interpolate_5pts)
1073 __GMP_DECLSPEC void      mpn_toom_interpolate_5pts __GMP_PROTO ((mp_ptr, mp_ptr, mp_ptr, mp_size_t, mp_size_t, int, mp_limb_t));
1074 
1075 enum toom6_flags {toom6_all_pos = 0, toom6_vm1_neg = 1, toom6_vm2_neg = 2};
1076 #define   mpn_toom_interpolate_6pts __MPN(toom_interpolate_6pts)
1077 __GMP_DECLSPEC void      mpn_toom_interpolate_6pts __GMP_PROTO ((mp_ptr, mp_size_t, enum toom6_flags, mp_ptr, mp_ptr, mp_ptr, mp_size_t));
1078 
1079 enum toom7_flags { toom7_w1_neg = 1, toom7_w3_neg = 2 };
1080 #define   mpn_toom_interpolate_7pts __MPN(toom_interpolate_7pts)
1081 __GMP_DECLSPEC void      mpn_toom_interpolate_7pts __GMP_PROTO ((mp_ptr, mp_size_t, enum toom7_flags, mp_ptr, mp_ptr, mp_ptr, mp_ptr, mp_size_t, mp_ptr));
1082 
1083 #define mpn_toom_interpolate_8pts __MPN(toom_interpolate_8pts)
1084 __GMP_DECLSPEC void      mpn_toom_interpolate_8pts __GMP_PROTO ((mp_ptr, mp_size_t, mp_ptr, mp_ptr, mp_size_t, mp_ptr));
1085 
1086 #define mpn_toom_interpolate_12pts __MPN(toom_interpolate_12pts)
1087 __GMP_DECLSPEC void      mpn_toom_interpolate_12pts __GMP_PROTO ((mp_ptr, mp_ptr, mp_ptr, mp_ptr, mp_size_t, mp_size_t, int, mp_ptr));
1088 
1089 #define mpn_toom_interpolate_16pts __MPN(toom_interpolate_16pts)
1090 __GMP_DECLSPEC void      mpn_toom_interpolate_16pts __GMP_PROTO ((mp_ptr, mp_ptr, mp_ptr, mp_ptr, mp_ptr, mp_size_t, mp_size_t, int, mp_ptr));
1091 
1092 #define   mpn_toom_couple_handling __MPN(toom_couple_handling)
1093 __GMP_DECLSPEC void mpn_toom_couple_handling __GMP_PROTO ((mp_ptr, mp_size_t, mp_ptr, int, mp_size_t, int, int));
1094 
1095 #define   mpn_toom_eval_dgr3_pm1 __MPN(toom_eval_dgr3_pm1)
1096 __GMP_DECLSPEC int mpn_toom_eval_dgr3_pm1 __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_size_t, mp_ptr));
1097 
1098 #define   mpn_toom_eval_dgr3_pm2 __MPN(toom_eval_dgr3_pm2)
1099 __GMP_DECLSPEC int mpn_toom_eval_dgr3_pm2 __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_size_t, mp_ptr));
1100 
1101 #define   mpn_toom_eval_pm1 __MPN(toom_eval_pm1)
1102 __GMP_DECLSPEC int mpn_toom_eval_pm1 __GMP_PROTO ((mp_ptr, mp_ptr, unsigned, mp_srcptr, mp_size_t, mp_size_t, mp_ptr));
1103 
1104 #define   mpn_toom_eval_pm2 __MPN(toom_eval_pm2)
1105 __GMP_DECLSPEC int mpn_toom_eval_pm2 __GMP_PROTO ((mp_ptr, mp_ptr, unsigned, mp_srcptr, mp_size_t, mp_size_t, mp_ptr));
1106 
1107 #define   mpn_toom_eval_pm2exp __MPN(toom_eval_pm2exp)
1108 __GMP_DECLSPEC int mpn_toom_eval_pm2exp __GMP_PROTO ((mp_ptr, mp_ptr, unsigned, mp_srcptr, mp_size_t, mp_size_t, unsigned, mp_ptr));
1109 
1110 #define   mpn_toom_eval_pm2rexp __MPN(toom_eval_pm2rexp)
1111 __GMP_DECLSPEC int mpn_toom_eval_pm2rexp __GMP_PROTO ((mp_ptr, mp_ptr, unsigned, mp_srcptr, mp_size_t, mp_size_t, unsigned, mp_ptr));
1112 
1113 #define   mpn_toom22_mul __MPN(toom22_mul)
1114 __GMP_DECLSPEC void      mpn_toom22_mul __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1115 
1116 #define   mpn_toom32_mul __MPN(toom32_mul)
1117 __GMP_DECLSPEC void      mpn_toom32_mul __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1118 
1119 #define   mpn_toom42_mul __MPN(toom42_mul)
1120 __GMP_DECLSPEC void      mpn_toom42_mul __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1121 
1122 #define   mpn_toom52_mul __MPN(toom52_mul)
1123 __GMP_DECLSPEC void      mpn_toom52_mul __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1124 
1125 #define   mpn_toom62_mul __MPN(toom62_mul)
1126 __GMP_DECLSPEC void      mpn_toom62_mul __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1127 
1128 #define   mpn_toom2_sqr __MPN(toom2_sqr)
1129 __GMP_DECLSPEC void      mpn_toom2_sqr __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_ptr));
1130 
1131 #define   mpn_toom33_mul __MPN(toom33_mul)
1132 __GMP_DECLSPEC void      mpn_toom33_mul __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1133 
1134 #define   mpn_toom43_mul __MPN(toom43_mul)
1135 __GMP_DECLSPEC void      mpn_toom43_mul __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1136 
1137 #define   mpn_toom53_mul __MPN(toom53_mul)
1138 __GMP_DECLSPEC void      mpn_toom53_mul __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1139 
1140 #define   mpn_toom63_mul __MPN(toom63_mul)
1141 __GMP_DECLSPEC void      mpn_toom63_mul __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1142 
1143 #define   mpn_toom3_sqr __MPN(toom3_sqr)
1144 __GMP_DECLSPEC void      mpn_toom3_sqr __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_ptr));
1145 
1146 #define   mpn_toom44_mul __MPN(toom44_mul)
1147 __GMP_DECLSPEC void      mpn_toom44_mul __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1148 
1149 #define   mpn_toom4_sqr __MPN(toom4_sqr)
1150 __GMP_DECLSPEC void      mpn_toom4_sqr __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_ptr));
1151 
1152 #define   mpn_toom6h_mul __MPN(toom6h_mul)
1153 __GMP_DECLSPEC void      mpn_toom6h_mul __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1154 
1155 #define   mpn_toom6_sqr __MPN(toom6_sqr)
1156 __GMP_DECLSPEC void      mpn_toom6_sqr __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_ptr));
1157 
1158 #define   mpn_toom8h_mul __MPN(toom8h_mul)
1159 __GMP_DECLSPEC void      mpn_toom8h_mul __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1160 
1161 #define   mpn_toom8_sqr __MPN(toom8_sqr)
1162 __GMP_DECLSPEC void      mpn_toom8_sqr __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_ptr));
1163 
1164 #define   mpn_fft_best_k __MPN(fft_best_k)
1165 __GMP_DECLSPEC int       mpn_fft_best_k __GMP_PROTO ((mp_size_t, int)) ATTRIBUTE_CONST;
1166 
1167 #define   mpn_mul_fft __MPN(mul_fft)
1168 __GMP_DECLSPEC mp_limb_t mpn_mul_fft __GMP_PROTO ((mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, int));
1169 
1170 #define   mpn_mul_fft_full __MPN(mul_fft_full)
1171 __GMP_DECLSPEC void      mpn_mul_fft_full __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t));
1172 
1173 #define   mpn_nussbaumer_mul __MPN(nussbaumer_mul)
1174 __GMP_DECLSPEC void      mpn_nussbaumer_mul __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t));
1175 
1176 #define   mpn_fft_next_size __MPN(fft_next_size)
1177 __GMP_DECLSPEC mp_size_t mpn_fft_next_size __GMP_PROTO ((mp_size_t, int)) ATTRIBUTE_CONST;
1178 
1179 #define   mpn_sbpi1_div_qr __MPN(sbpi1_div_qr)
1180 __GMP_DECLSPEC mp_limb_t mpn_sbpi1_div_qr __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t));
1181 
1182 #define   mpn_sbpi1_div_q __MPN(sbpi1_div_q)
1183 __GMP_DECLSPEC mp_limb_t mpn_sbpi1_div_q __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t));
1184 
1185 #define   mpn_sbpi1_divappr_q __MPN(sbpi1_divappr_q)
1186 __GMP_DECLSPEC mp_limb_t mpn_sbpi1_divappr_q __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t));
1187 
1188 #define   mpn_dcpi1_div_qr __MPN(dcpi1_div_qr)
1189 __GMP_DECLSPEC mp_limb_t mpn_dcpi1_div_qr __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, gmp_pi1_t *));
1190 #define   mpn_dcpi1_div_qr_n __MPN(dcpi1_div_qr_n)
1191 __GMP_DECLSPEC mp_limb_t mpn_dcpi1_div_qr_n __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_size_t, gmp_pi1_t *, mp_ptr));
1192 
1193 #define   mpn_dcpi1_div_q __MPN(dcpi1_div_q)
1194 __GMP_DECLSPEC mp_limb_t mpn_dcpi1_div_q __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, gmp_pi1_t *));
1195 
1196 #define   mpn_dcpi1_divappr_q __MPN(dcpi1_divappr_q)
1197 __GMP_DECLSPEC mp_limb_t mpn_dcpi1_divappr_q __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, gmp_pi1_t *));
1198 #define   mpn_dcpi1_divappr_q_n __MPN(dcpi1_divappr_q_n)
1199 __GMP_DECLSPEC mp_limb_t mpn_dcpi1_divappr_q_n __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_size_t, gmp_pi1_t *, mp_ptr));
1200 
1201 #define   mpn_mu_div_qr __MPN(mu_div_qr)
1202 __GMP_DECLSPEC mp_limb_t mpn_mu_div_qr __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1203 #define   mpn_mu_div_qr_itch __MPN(mu_div_qr_itch)
1204 __GMP_DECLSPEC mp_size_t mpn_mu_div_qr_itch __GMP_PROTO ((mp_size_t, mp_size_t, int));
1205 #define   mpn_mu_div_qr_choose_in __MPN(mu_div_qr_choose_in)
1206 __GMP_DECLSPEC mp_size_t mpn_mu_div_qr_choose_in __GMP_PROTO ((mp_size_t, mp_size_t, int));
1207 
1208 #define   mpn_preinv_mu_div_qr __MPN(preinv_mu_div_qr)
1209 __GMP_DECLSPEC mp_limb_t mpn_preinv_mu_div_qr __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1210 #define   mpn_preinv_mu_div_qr_itch __MPN(preinv_mu_div_qr_itch)
1211 __GMP_DECLSPEC mp_size_t mpn_preinv_mu_div_qr_itch __GMP_PROTO ((mp_size_t, mp_size_t, mp_size_t));
1212 
1213 #define   mpn_mu_divappr_q __MPN(mu_divappr_q)
1214 __GMP_DECLSPEC mp_limb_t mpn_mu_divappr_q __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1215 #define   mpn_mu_divappr_q_itch __MPN(mu_divappr_q_itch)
1216 __GMP_DECLSPEC mp_size_t mpn_mu_divappr_q_itch __GMP_PROTO ((mp_size_t, mp_size_t, int));
1217 #define   mpn_mu_divappr_q_choose_in __MPN(mu_divappr_q_choose_in)
1218 __GMP_DECLSPEC mp_size_t mpn_mu_divappr_q_choose_in __GMP_PROTO ((mp_size_t, mp_size_t, int));
1219 
1220 #define   mpn_preinv_mu_divappr_q __MPN(preinv_mu_divappr_q)
1221 __GMP_DECLSPEC mp_limb_t mpn_preinv_mu_divappr_q __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1222 
1223 #define   mpn_mu_div_q __MPN(mu_div_q)
1224 __GMP_DECLSPEC mp_limb_t mpn_mu_div_q __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1225 #define   mpn_mu_div_q_itch __MPN(mu_div_q_itch)
1226 __GMP_DECLSPEC mp_size_t mpn_mu_div_q_itch __GMP_PROTO ((mp_size_t, mp_size_t, int));
1227 
1228 #define  mpn_div_q __MPN(div_q)
1229 __GMP_DECLSPEC void mpn_div_q __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1230 
1231 #define   mpn_invert __MPN(invert)
1232 __GMP_DECLSPEC void      mpn_invert __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_ptr));
1233 #define mpn_invert_itch(n)  mpn_invertappr_itch(n)
1234 
1235 #define   mpn_ni_invertappr __MPN(ni_invertappr)
1236 __GMP_DECLSPEC mp_limb_t mpn_ni_invertappr __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_ptr));
1237 #define   mpn_invertappr __MPN(invertappr)
1238 __GMP_DECLSPEC mp_limb_t mpn_invertappr __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_ptr));
1239 #define mpn_invertappr_itch(n)  (3 * (n) + 2)
1240 
1241 #define   mpn_binvert __MPN(binvert)
1242 __GMP_DECLSPEC void      mpn_binvert __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_ptr));
1243 #define   mpn_binvert_itch __MPN(binvert_itch)
1244 __GMP_DECLSPEC mp_size_t mpn_binvert_itch __GMP_PROTO ((mp_size_t));
1245 
1246 #define mpn_bdiv_q_1 __MPN(bdiv_q_1)
1247 __GMP_DECLSPEC mp_limb_t mpn_bdiv_q_1 __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_limb_t));
1248 
1249 #define mpn_pi1_bdiv_q_1 __MPN(pi1_bdiv_q_1)
1250 __GMP_DECLSPEC mp_limb_t mpn_pi1_bdiv_q_1 __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t, int));
1251 
1252 #define   mpn_sbpi1_bdiv_qr __MPN(sbpi1_bdiv_qr)
1253 __GMP_DECLSPEC mp_limb_t mpn_sbpi1_bdiv_qr __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t));
1254 
1255 #define   mpn_sbpi1_bdiv_q __MPN(sbpi1_bdiv_q)
1256 __GMP_DECLSPEC void      mpn_sbpi1_bdiv_q __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t));
1257 
1258 #define   mpn_dcpi1_bdiv_qr __MPN(dcpi1_bdiv_qr)
1259 __GMP_DECLSPEC mp_limb_t mpn_dcpi1_bdiv_qr __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t));
1260 #define   mpn_dcpi1_bdiv_qr_n_itch __MPN(dcpi1_bdiv_qr_n_itch)
1261 __GMP_DECLSPEC mp_size_t mpn_dcpi1_bdiv_qr_n_itch __GMP_PROTO ((mp_size_t));
1262 
1263 #define   mpn_dcpi1_bdiv_qr_n __MPN(dcpi1_bdiv_qr_n)
1264 __GMP_DECLSPEC mp_limb_t mpn_dcpi1_bdiv_qr_n __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_limb_t, mp_ptr));
1265 #define   mpn_dcpi1_bdiv_q __MPN(dcpi1_bdiv_q)
1266 __GMP_DECLSPEC void      mpn_dcpi1_bdiv_q __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t));
1267 
1268 #define   mpn_dcpi1_bdiv_q_n_itch __MPN(dcpi1_bdiv_q_n_itch)
1269 __GMP_DECLSPEC mp_size_t mpn_dcpi1_bdiv_q_n_itch __GMP_PROTO ((mp_size_t));
1270 #define   mpn_dcpi1_bdiv_q_n __MPN(dcpi1_bdiv_q_n)
1271 __GMP_DECLSPEC void      mpn_dcpi1_bdiv_q_n __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_limb_t, mp_ptr));
1272 
1273 #define   mpn_mu_bdiv_qr __MPN(mu_bdiv_qr)
1274 __GMP_DECLSPEC mp_limb_t mpn_mu_bdiv_qr __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1275 #define   mpn_mu_bdiv_qr_itch __MPN(mu_bdiv_qr_itch)
1276 __GMP_DECLSPEC mp_size_t mpn_mu_bdiv_qr_itch __GMP_PROTO ((mp_size_t, mp_size_t));
1277 
1278 #define   mpn_mu_bdiv_q __MPN(mu_bdiv_q)
1279 __GMP_DECLSPEC void      mpn_mu_bdiv_q __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1280 #define   mpn_mu_bdiv_q_itch __MPN(mu_bdiv_q_itch)
1281 __GMP_DECLSPEC mp_size_t mpn_mu_bdiv_q_itch __GMP_PROTO ((mp_size_t, mp_size_t));
1282 
1283 #define   mpn_bdiv_qr __MPN(bdiv_qr)
1284 __GMP_DECLSPEC mp_limb_t mpn_bdiv_qr __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1285 #define   mpn_bdiv_qr_itch __MPN(bdiv_qr_itch)
1286 __GMP_DECLSPEC mp_size_t mpn_bdiv_qr_itch __GMP_PROTO ((mp_size_t, mp_size_t));
1287 
1288 #define   mpn_bdiv_q __MPN(bdiv_q)
1289 __GMP_DECLSPEC void      mpn_bdiv_q __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1290 #define   mpn_bdiv_q_itch __MPN(bdiv_q_itch)
1291 __GMP_DECLSPEC mp_size_t mpn_bdiv_q_itch __GMP_PROTO ((mp_size_t, mp_size_t));
1292 
1293 #define   mpn_divexact __MPN(divexact)
1294 __GMP_DECLSPEC void      mpn_divexact __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t));
1295 #define   mpn_divexact_itch __MPN(divexact_itch)
1296 __GMP_DECLSPEC mp_size_t mpn_divexact_itch __GMP_PROTO ((mp_size_t, mp_size_t));
1297 
1298 #define   mpn_bdiv_dbm1c __MPN(bdiv_dbm1c)
1299 __GMP_DECLSPEC mp_limb_t mpn_bdiv_dbm1c __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t));
1300 #define   mpn_bdiv_dbm1(dst, src, size, divisor) \
1301   mpn_bdiv_dbm1c (dst, src, size, divisor, __GMP_CAST (mp_limb_t, 0))
1302 
1303 #define   mpn_powm __MPN(powm)
1304 __GMP_DECLSPEC void      mpn_powm __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1305 #define   mpn_powlo __MPN(powlo)
1306 __GMP_DECLSPEC void      mpn_powlo __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_size_t, mp_ptr));
1307 #define   mpn_powm_sec __MPN(powm_sec)
1308 __GMP_DECLSPEC void      mpn_powm_sec __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
1309 #define   mpn_powm_sec_itch __MPN(powm_sec_itch)
1310 __GMP_DECLSPEC mp_size_t mpn_powm_sec_itch __GMP_PROTO ((mp_size_t, mp_size_t, mp_size_t));
1311 #define   mpn_subcnd_n __MPN(subcnd_n)
1312 __GMP_DECLSPEC mp_limb_t mpn_subcnd_n __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t));
1313 #define   mpn_tabselect __MPN(tabselect)
1314 __GMP_DECLSPEC void      mpn_tabselect __GMP_PROTO ((volatile mp_limb_t *, volatile mp_limb_t *, mp_size_t, mp_size_t, mp_size_t));
1315 #define mpn_redc_1_sec __MPN(redc_1_sec)
1316 __GMP_DECLSPEC void mpn_redc_1_sec __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_limb_t));
1317 
1318 #ifndef DIVEXACT_BY3_METHOD
1319 #if GMP_NUMB_BITS % 2 == 0 && ! defined (HAVE_NATIVE_mpn_divexact_by3c)
1320 #define DIVEXACT_BY3_METHOD 0	/* default to using mpn_bdiv_dbm1c */
1321 #else
1322 #define DIVEXACT_BY3_METHOD 1
1323 #endif
1324 #endif
1325 
1326 #if DIVEXACT_BY3_METHOD == 0
1327 #undef mpn_divexact_by3
1328 #define mpn_divexact_by3(dst,src,size) \
1329   (3 & mpn_bdiv_dbm1 (dst, src, size, __GMP_CAST (mp_limb_t, GMP_NUMB_MASK / 3)))
1330 /* override mpn_divexact_by3c defined in gmp.h */
1331 /*
1332 #undef mpn_divexact_by3c
1333 #define mpn_divexact_by3c(dst,src,size,cy) \
1334   (3 & mpn_bdiv_dbm1c (dst, src, size, __GMP_CAST (mp_limb_t, GMP_NUMB_MASK / 3, GMP_NUMB_MASK / 3 * cy)))
1335 */
1336 #endif
1337 
1338 #if GMP_NUMB_BITS % 4 == 0
1339 #define mpn_divexact_by5(dst,src,size) \
1340   (7 & 3 * mpn_bdiv_dbm1 (dst, src, size, __GMP_CAST (mp_limb_t, GMP_NUMB_MASK / 5)))
1341 #endif
1342 
1343 #if GMP_NUMB_BITS % 6 == 0
1344 #define mpn_divexact_by7(dst,src,size) \
1345   (7 & 1 * mpn_bdiv_dbm1 (dst, src, size, __GMP_CAST (mp_limb_t, GMP_NUMB_MASK / 7)))
1346 #endif
1347 
1348 #if GMP_NUMB_BITS % 6 == 0
1349 #define mpn_divexact_by9(dst,src,size) \
1350   (15 & 7 * mpn_bdiv_dbm1 (dst, src, size, __GMP_CAST (mp_limb_t, GMP_NUMB_MASK / 9)))
1351 #endif
1352 
1353 #if GMP_NUMB_BITS % 10 == 0
1354 #define mpn_divexact_by11(dst,src,size) \
1355   (15 & 5 * mpn_bdiv_dbm1 (dst, src, size, __GMP_CAST (mp_limb_t, GMP_NUMB_MASK / 11)))
1356 #endif
1357 
1358 #if GMP_NUMB_BITS % 12 == 0
1359 #define mpn_divexact_by13(dst,src,size) \
1360   (15 & 3 * mpn_bdiv_dbm1 (dst, src, size, __GMP_CAST (mp_limb_t, GMP_NUMB_MASK / 13)))
1361 #endif
1362 
1363 #if GMP_NUMB_BITS % 4 == 0
1364 #define mpn_divexact_by15(dst,src,size) \
1365   (15 & 1 * mpn_bdiv_dbm1 (dst, src, size, __GMP_CAST (mp_limb_t, GMP_NUMB_MASK / 15)))
1366 #endif
1367 
1368 #define mpz_divexact_gcd  __gmpz_divexact_gcd
1369 __GMP_DECLSPEC void    mpz_divexact_gcd __GMP_PROTO ((mpz_ptr, mpz_srcptr, mpz_srcptr));
1370 
1371 #define mpz_inp_str_nowhite __gmpz_inp_str_nowhite
1372 #ifdef _GMP_H_HAVE_FILE
1373 __GMP_DECLSPEC size_t  mpz_inp_str_nowhite __GMP_PROTO ((mpz_ptr, FILE *, int, int, size_t));
1374 #endif
1375 
1376 #define mpn_divisible_p __MPN(divisible_p)
1377 __GMP_DECLSPEC int     mpn_divisible_p __GMP_PROTO ((mp_srcptr, mp_size_t, mp_srcptr, mp_size_t)) __GMP_ATTRIBUTE_PURE;
1378 
1379 #define   mpn_rootrem __MPN(rootrem)
1380 __GMP_DECLSPEC mp_size_t mpn_rootrem __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_limb_t));
1381 
1382 
1383 #if defined (_CRAY)
1384 #define MPN_COPY_INCR(dst, src, n)					\
1385   do {									\
1386     int __i;		/* Faster on some Crays with plain int */	\
1387     _Pragma ("_CRI ivdep");						\
1388     for (__i = 0; __i < (n); __i++)					\
1389       (dst)[__i] = (src)[__i];						\
1390   } while (0)
1391 #endif
1392 
1393 /* used by test programs, hence __GMP_DECLSPEC */
1394 #ifndef mpn_copyi  /* if not done with cpuvec in a fat binary */
1395 #define mpn_copyi __MPN(copyi)
1396 __GMP_DECLSPEC void mpn_copyi __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t));
1397 #endif
1398 
1399 #if ! defined (MPN_COPY_INCR) && HAVE_NATIVE_mpn_copyi
1400 #define MPN_COPY_INCR(dst, src, size)                   \
1401   do {                                                  \
1402     ASSERT ((size) >= 0);                               \
1403     ASSERT (MPN_SAME_OR_INCR_P (dst, src, size));       \
1404     mpn_copyi (dst, src, size);                         \
1405   } while (0)
1406 #endif
1407 
1408 /* Copy N limbs from SRC to DST incrementing, N==0 allowed.  */
1409 #if ! defined (MPN_COPY_INCR)
1410 #define MPN_COPY_INCR(dst, src, n)                      \
1411   do {                                                  \
1412     ASSERT ((n) >= 0);                                  \
1413     ASSERT (MPN_SAME_OR_INCR_P (dst, src, n));          \
1414     if ((n) != 0)                                       \
1415       {                                                 \
1416 	mp_size_t __n = (n) - 1;                        \
1417 	mp_ptr __dst = (dst);                           \
1418 	mp_srcptr __src = (src);                        \
1419 	mp_limb_t __x;                                  \
1420 	__x = *__src++;                                 \
1421 	if (__n != 0)                                   \
1422 	  {                                             \
1423 	    do                                          \
1424 	      {                                         \
1425 		*__dst++ = __x;                         \
1426 		__x = *__src++;                         \
1427 	      }                                         \
1428 	    while (--__n);                              \
1429 	  }                                             \
1430 	*__dst++ = __x;                                 \
1431       }                                                 \
1432   } while (0)
1433 #endif
1434 
1435 
1436 #if defined (_CRAY)
1437 #define MPN_COPY_DECR(dst, src, n)					\
1438   do {									\
1439     int __i;		/* Faster on some Crays with plain int */	\
1440     _Pragma ("_CRI ivdep");						\
1441     for (__i = (n) - 1; __i >= 0; __i--)				\
1442       (dst)[__i] = (src)[__i];						\
1443   } while (0)
1444 #endif
1445 
1446 /* used by test programs, hence __GMP_DECLSPEC */
1447 #ifndef mpn_copyd  /* if not done with cpuvec in a fat binary */
1448 #define mpn_copyd __MPN(copyd)
1449 __GMP_DECLSPEC void mpn_copyd __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t));
1450 #endif
1451 
1452 #if ! defined (MPN_COPY_DECR) && HAVE_NATIVE_mpn_copyd
1453 #define MPN_COPY_DECR(dst, src, size)                   \
1454   do {                                                  \
1455     ASSERT ((size) >= 0);                               \
1456     ASSERT (MPN_SAME_OR_DECR_P (dst, src, size));       \
1457     mpn_copyd (dst, src, size);                         \
1458   } while (0)
1459 #endif
1460 
1461 /* Copy N limbs from SRC to DST decrementing, N==0 allowed.  */
1462 #if ! defined (MPN_COPY_DECR)
1463 #define MPN_COPY_DECR(dst, src, n)                      \
1464   do {                                                  \
1465     ASSERT ((n) >= 0);                                  \
1466     ASSERT (MPN_SAME_OR_DECR_P (dst, src, n));          \
1467     if ((n) != 0)                                       \
1468       {                                                 \
1469 	mp_size_t __n = (n) - 1;                        \
1470 	mp_ptr __dst = (dst) + __n;                     \
1471 	mp_srcptr __src = (src) + __n;                  \
1472 	mp_limb_t __x;                                  \
1473 	__x = *__src--;                                 \
1474 	if (__n != 0)                                   \
1475 	  {                                             \
1476 	    do                                          \
1477 	      {                                         \
1478 		*__dst-- = __x;                         \
1479 		__x = *__src--;                         \
1480 	      }                                         \
1481 	    while (--__n);                              \
1482 	  }                                             \
1483 	*__dst-- = __x;                                 \
1484       }                                                 \
1485   } while (0)
1486 #endif
1487 
1488 
1489 #ifndef MPN_COPY
1490 #define MPN_COPY(d,s,n)                         \
1491   do {                                          \
1492     ASSERT (MPN_SAME_OR_SEPARATE_P (d, s, n));  \
1493     MPN_COPY_INCR (d, s, n);                    \
1494   } while (0)
1495 #endif
1496 
1497 
1498 /* Set {dst,size} to the limbs of {src,size} in reverse order. */
1499 #define MPN_REVERSE(dst, src, size)                     \
1500   do {                                                  \
1501     mp_ptr     __dst = (dst);                           \
1502     mp_size_t  __size = (size);                         \
1503     mp_srcptr  __src = (src) + __size - 1;              \
1504     mp_size_t  __i;                                     \
1505     ASSERT ((size) >= 0);                               \
1506     ASSERT (! MPN_OVERLAP_P (dst, size, src, size));    \
1507     CRAY_Pragma ("_CRI ivdep");                         \
1508     for (__i = 0; __i < __size; __i++)                  \
1509       {                                                 \
1510         *__dst = *__src;                                \
1511         __dst++;                                        \
1512         __src--;                                        \
1513       }                                                 \
1514   } while (0)
1515 
1516 
1517 /* Zero n limbs at dst.
1518 
1519    For power and powerpc we want an inline stu/bdnz loop for zeroing.  On
1520    ppc630 for instance this is optimal since it can sustain only 1 store per
1521    cycle.
1522 
1523    gcc 2.95.x (for powerpc64 -maix64, or powerpc32) doesn't recognise the
1524    "for" loop in the generic code below can become stu/bdnz.  The do/while
1525    here helps it get to that.  The same caveat about plain -mpowerpc64 mode
1526    applies here as to __GMPN_COPY_INCR in gmp.h.
1527 
1528    xlc 3.1 already generates stu/bdnz from the generic C, and does so from
1529    this loop too.
1530 
1531    Enhancement: GLIBC does some trickery with dcbz to zero whole cache lines
1532    at a time.  MPN_ZERO isn't all that important in GMP, so it might be more
1533    trouble than it's worth to do the same, though perhaps a call to memset
1534    would be good when on a GNU system.  */
1535 
1536 #if HAVE_HOST_CPU_FAMILY_power || HAVE_HOST_CPU_FAMILY_powerpc
1537 #define MPN_ZERO(dst, n)			\
1538   do {						\
1539     ASSERT ((n) >= 0);				\
1540     if ((n) != 0)				\
1541       {						\
1542 	mp_ptr __dst = (dst) - 1;		\
1543 	mp_size_t __n = (n);			\
1544 	do					\
1545 	  *++__dst = 0;				\
1546 	while (--__n);				\
1547       }						\
1548   } while (0)
1549 #endif
1550 
1551 #ifndef MPN_ZERO
1552 #define MPN_ZERO(dst, n)			\
1553   do {						\
1554     ASSERT ((n) >= 0);				\
1555     if ((n) != 0)				\
1556       {						\
1557 	mp_ptr __dst = (dst);			\
1558 	mp_size_t __n = (n);			\
1559 	do					\
1560 	  *__dst++ = 0;				\
1561 	while (--__n);				\
1562       }						\
1563   } while (0)
1564 #endif
1565 
1566 
1567 /* On the x86s repe/scasl doesn't seem useful, since it takes many cycles to
1568    start up and would need to strip a lot of zeros before it'd be faster
1569    than a simple cmpl loop.  Here are some times in cycles for
1570    std/repe/scasl/cld and cld/repe/scasl (the latter would be for stripping
1571    low zeros).
1572 
1573                 std   cld
1574            P5    18    16
1575            P6    46    38
1576            K6    36    13
1577            K7    21    20
1578 */
1579 #ifndef MPN_NORMALIZE
1580 #define MPN_NORMALIZE(DST, NLIMBS) \
1581   do {									\
1582     while ((NLIMBS) > 0)                                                \
1583       {									\
1584 	if ((DST)[(NLIMBS) - 1] != 0)					\
1585 	  break;							\
1586 	(NLIMBS)--;							\
1587       }									\
1588   } while (0)
1589 #endif
1590 #ifndef MPN_NORMALIZE_NOT_ZERO
1591 #define MPN_NORMALIZE_NOT_ZERO(DST, NLIMBS)     \
1592   do {                                          \
1593     ASSERT ((NLIMBS) >= 1);                     \
1594     while (1)                                   \
1595       {                                         \
1596 	if ((DST)[(NLIMBS) - 1] != 0)           \
1597 	  break;                                \
1598 	(NLIMBS)--;                             \
1599       }                                         \
1600   } while (0)
1601 #endif
1602 
1603 /* Strip least significant zero limbs from {ptr,size} by incrementing ptr
1604    and decrementing size.  low should be ptr[0], and will be the new ptr[0]
1605    on returning.  The number in {ptr,size} must be non-zero, ie. size!=0 and
1606    somewhere a non-zero limb.  */
1607 #define MPN_STRIP_LOW_ZEROS_NOT_ZERO(ptr, size, low)    \
1608   do {                                                  \
1609     ASSERT ((size) >= 1);                               \
1610     ASSERT ((low) == (ptr)[0]);                         \
1611                                                         \
1612     while ((low) == 0)                                  \
1613       {                                                 \
1614         (size)--;                                       \
1615         ASSERT ((size) >= 1);                           \
1616         (ptr)++;                                        \
1617         (low) = *(ptr);                                 \
1618       }                                                 \
1619   } while (0)
1620 
1621 /* Initialize X of type mpz_t with space for NLIMBS limbs.  X should be a
1622    temporary variable; it will be automatically cleared out at function
1623    return.  We use __x here to make it possible to accept both mpz_ptr and
1624    mpz_t arguments.  */
1625 #define MPZ_TMP_INIT(X, NLIMBS)                                         \
1626   do {                                                                  \
1627     mpz_ptr __x = (X);                                                  \
1628     ASSERT ((NLIMBS) >= 1);                                             \
1629     __x->_mp_alloc = (NLIMBS);                                          \
1630     __x->_mp_d = TMP_ALLOC_LIMBS (NLIMBS);				\
1631   } while (0)
1632 
1633 /* Realloc for an mpz_t WHAT if it has less than NEEDED limbs.  */
1634 #define MPZ_REALLOC(z,n) (UNLIKELY ((n) > ALLOC(z))     \
1635                           ? (mp_ptr) _mpz_realloc(z,n)  \
1636                           : PTR(z))
1637 
1638 #define MPZ_EQUAL_1_P(z)  (SIZ(z)==1 && PTR(z)[0] == 1)
1639 
1640 
1641 /* MPN_FIB2_SIZE(n) is the size in limbs required by mpn_fib2_ui for fp and
1642    f1p.
1643 
1644    From Knuth vol 1 section 1.2.8, F[n] = phi^n/sqrt(5) rounded to the
1645    nearest integer, where phi=(1+sqrt(5))/2 is the golden ratio.  So the
1646    number of bits required is n*log_2((1+sqrt(5))/2) = n*0.6942419.
1647 
1648    The multiplier used is 23/32=0.71875 for efficient calculation on CPUs
1649    without good floating point.  There's +2 for rounding up, and a further
1650    +2 since at the last step x limbs are doubled into a 2x+1 limb region
1651    whereas the actual F[2k] value might be only 2x-1 limbs.
1652 
1653    Note that a division is done first, since on a 32-bit system it's at
1654    least conceivable to go right up to n==ULONG_MAX.  (F[2^32-1] would be
1655    about 380Mbytes, plus temporary workspace of about 1.2Gbytes here and
1656    whatever a multiply of two 190Mbyte numbers takes.)
1657 
1658    Enhancement: When GMP_NUMB_BITS is not a power of 2 the division could be
1659    worked into the multiplier.  */
1660 
1661 #define MPN_FIB2_SIZE(n) \
1662   ((mp_size_t) ((n) / 32 * 23 / GMP_NUMB_BITS) + 4)
1663 
1664 
1665 /* FIB_TABLE(n) returns the Fibonacci number F[n].  Must have n in the range
1666    -1 <= n <= FIB_TABLE_LIMIT (that constant in fib_table.h).
1667 
1668    FIB_TABLE_LUCNUM_LIMIT (in fib_table.h) is the largest n for which L[n] =
1669    F[n] + 2*F[n-1] fits in a limb.  */
1670 
1671 __GMP_DECLSPEC extern const mp_limb_t __gmp_fib_table[];
1672 #define FIB_TABLE(n)  (__gmp_fib_table[(n)+1])
1673 
1674 #define SIEVESIZE 512		/* FIXME: Allow gmp_init_primesieve to choose */
1675 typedef struct
1676 {
1677   unsigned long d;		   /* current index in s[] */
1678   unsigned long s0;		   /* number corresponding to s[0] */
1679   unsigned long sqrt_s0;	   /* misnomer for sqrt(s[SIEVESIZE-1]) */
1680   unsigned char s[SIEVESIZE + 1];  /* sieve table */
1681 } gmp_primesieve_t;
1682 
1683 #define gmp_init_primesieve __gmp_init_primesieve
1684 __GMP_DECLSPEC void gmp_init_primesieve (gmp_primesieve_t *);
1685 
1686 #define gmp_nextprime __gmp_nextprime
1687 __GMP_DECLSPEC unsigned long int gmp_nextprime (gmp_primesieve_t *);
1688 
1689 
1690 #ifndef MUL_TOOM22_THRESHOLD
1691 #define MUL_TOOM22_THRESHOLD             30
1692 #endif
1693 
1694 #ifndef MUL_TOOM33_THRESHOLD
1695 #define MUL_TOOM33_THRESHOLD            100
1696 #endif
1697 
1698 #ifndef MUL_TOOM44_THRESHOLD
1699 #define MUL_TOOM44_THRESHOLD            300
1700 #endif
1701 
1702 #ifndef MUL_TOOM6H_THRESHOLD
1703 #define MUL_TOOM6H_THRESHOLD            350
1704 #endif
1705 
1706 #ifndef SQR_TOOM6_THRESHOLD
1707 #define SQR_TOOM6_THRESHOLD MUL_TOOM6H_THRESHOLD
1708 #endif
1709 
1710 #ifndef MUL_TOOM8H_THRESHOLD
1711 #define MUL_TOOM8H_THRESHOLD            450
1712 #endif
1713 
1714 #ifndef SQR_TOOM8_THRESHOLD
1715 #define SQR_TOOM8_THRESHOLD MUL_TOOM8H_THRESHOLD
1716 #endif
1717 
1718 #ifndef MUL_TOOM32_TO_TOOM43_THRESHOLD
1719 #define MUL_TOOM32_TO_TOOM43_THRESHOLD  100
1720 #endif
1721 
1722 #ifndef MUL_TOOM32_TO_TOOM53_THRESHOLD
1723 #define MUL_TOOM32_TO_TOOM53_THRESHOLD  110
1724 #endif
1725 
1726 #ifndef MUL_TOOM42_TO_TOOM53_THRESHOLD
1727 #define MUL_TOOM42_TO_TOOM53_THRESHOLD  100
1728 #endif
1729 
1730 #ifndef MUL_TOOM42_TO_TOOM63_THRESHOLD
1731 #define MUL_TOOM42_TO_TOOM63_THRESHOLD  110
1732 #endif
1733 
1734 /* MUL_TOOM22_THRESHOLD_LIMIT is the maximum for MUL_TOOM22_THRESHOLD.  In a
1735    normal build MUL_TOOM22_THRESHOLD is a constant and we use that.  In a fat
1736    binary or tune program build MUL_TOOM22_THRESHOLD is a variable and a
1737    separate hard limit will have been defined.  Similarly for TOOM3.  */
1738 #ifndef MUL_TOOM22_THRESHOLD_LIMIT
1739 #define MUL_TOOM22_THRESHOLD_LIMIT  MUL_TOOM22_THRESHOLD
1740 #endif
1741 #ifndef MUL_TOOM33_THRESHOLD_LIMIT
1742 #define MUL_TOOM33_THRESHOLD_LIMIT  MUL_TOOM33_THRESHOLD
1743 #endif
1744 #ifndef MULLO_BASECASE_THRESHOLD_LIMIT
1745 #define MULLO_BASECASE_THRESHOLD_LIMIT  MULLO_BASECASE_THRESHOLD
1746 #endif
1747 
1748 /* SQR_BASECASE_THRESHOLD is where mpn_sqr_basecase should take over from
1749    mpn_mul_basecase.  Default is to use mpn_sqr_basecase from 0.  (Note that we
1750    certainly always want it if there's a native assembler mpn_sqr_basecase.)
1751 
1752    If it turns out that mpn_toom2_sqr becomes faster than mpn_mul_basecase
1753    before mpn_sqr_basecase does, then SQR_BASECASE_THRESHOLD is the toom2
1754    threshold and SQR_TOOM2_THRESHOLD is 0.  This oddity arises more or less
1755    because SQR_TOOM2_THRESHOLD represents the size up to which mpn_sqr_basecase
1756    should be used, and that may be never.  */
1757 
1758 #ifndef SQR_BASECASE_THRESHOLD
1759 #define SQR_BASECASE_THRESHOLD            0
1760 #endif
1761 
1762 #ifndef SQR_TOOM2_THRESHOLD
1763 #define SQR_TOOM2_THRESHOLD              50
1764 #endif
1765 
1766 #ifndef SQR_TOOM3_THRESHOLD
1767 #define SQR_TOOM3_THRESHOLD             120
1768 #endif
1769 
1770 #ifndef SQR_TOOM4_THRESHOLD
1771 #define SQR_TOOM4_THRESHOLD             400
1772 #endif
1773 
1774 /* See comments above about MUL_TOOM33_THRESHOLD_LIMIT.  */
1775 #ifndef SQR_TOOM3_THRESHOLD_LIMIT
1776 #define SQR_TOOM3_THRESHOLD_LIMIT  SQR_TOOM3_THRESHOLD
1777 #endif
1778 
1779 #ifndef DC_DIV_QR_THRESHOLD
1780 #define DC_DIV_QR_THRESHOLD              50
1781 #endif
1782 
1783 #ifndef DC_DIVAPPR_Q_THRESHOLD
1784 #define DC_DIVAPPR_Q_THRESHOLD          200
1785 #endif
1786 
1787 #ifndef DC_BDIV_QR_THRESHOLD
1788 #define DC_BDIV_QR_THRESHOLD             50
1789 #endif
1790 
1791 #ifndef DC_BDIV_Q_THRESHOLD
1792 #define DC_BDIV_Q_THRESHOLD             180
1793 #endif
1794 
1795 #ifndef DIVEXACT_JEB_THRESHOLD
1796 #define DIVEXACT_JEB_THRESHOLD           25
1797 #endif
1798 
1799 #ifndef INV_MULMOD_BNM1_THRESHOLD
1800 #define INV_MULMOD_BNM1_THRESHOLD  (5*MULMOD_BNM1_THRESHOLD)
1801 #endif
1802 
1803 #ifndef INV_APPR_THRESHOLD
1804 #define INV_APPR_THRESHOLD         INV_NEWTON_THRESHOLD
1805 #endif
1806 
1807 #ifndef INV_NEWTON_THRESHOLD
1808 #define INV_NEWTON_THRESHOLD            200
1809 #endif
1810 
1811 #ifndef BINV_NEWTON_THRESHOLD
1812 #define BINV_NEWTON_THRESHOLD           300
1813 #endif
1814 
1815 #ifndef MU_DIVAPPR_Q_THRESHOLD
1816 #define MU_DIVAPPR_Q_THRESHOLD         2000
1817 #endif
1818 
1819 #ifndef MU_DIV_QR_THRESHOLD
1820 #define MU_DIV_QR_THRESHOLD            2000
1821 #endif
1822 
1823 #ifndef MUPI_DIV_QR_THRESHOLD
1824 #define MUPI_DIV_QR_THRESHOLD           200
1825 #endif
1826 
1827 #ifndef MU_BDIV_Q_THRESHOLD
1828 #define MU_BDIV_Q_THRESHOLD            2000
1829 #endif
1830 
1831 #ifndef MU_BDIV_QR_THRESHOLD
1832 #define MU_BDIV_QR_THRESHOLD           2000
1833 #endif
1834 
1835 #ifndef MULMOD_BNM1_THRESHOLD
1836 #define MULMOD_BNM1_THRESHOLD            16
1837 #endif
1838 
1839 #ifndef SQRMOD_BNM1_THRESHOLD
1840 #define SQRMOD_BNM1_THRESHOLD            16
1841 #endif
1842 
1843 #ifndef MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD
1844 #define MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD  (INV_MULMOD_BNM1_THRESHOLD/2)
1845 #endif
1846 
1847 #if HAVE_NATIVE_mpn_addmul_2 || HAVE_NATIVE_mpn_redc_2
1848 
1849 #ifndef REDC_1_TO_REDC_2_THRESHOLD
1850 #define REDC_1_TO_REDC_2_THRESHOLD       15
1851 #endif
1852 #ifndef REDC_2_TO_REDC_N_THRESHOLD
1853 #define REDC_2_TO_REDC_N_THRESHOLD      100
1854 #endif
1855 
1856 #else
1857 
1858 #ifndef REDC_1_TO_REDC_N_THRESHOLD
1859 #define REDC_1_TO_REDC_N_THRESHOLD      100
1860 #endif
1861 
1862 #endif /* HAVE_NATIVE_mpn_addmul_2 || HAVE_NATIVE_mpn_redc_2 */
1863 
1864 
1865 /* First k to use for an FFT modF multiply.  A modF FFT is an order
1866    log(2^k)/log(2^(k-1)) algorithm, so k=3 is merely 1.5 like karatsuba,
1867    whereas k=4 is 1.33 which is faster than toom3 at 1.485.    */
1868 #define FFT_FIRST_K  4
1869 
1870 /* Threshold at which FFT should be used to do a modF NxN -> N multiply. */
1871 #ifndef MUL_FFT_MODF_THRESHOLD
1872 #define MUL_FFT_MODF_THRESHOLD   (MUL_TOOM33_THRESHOLD * 3)
1873 #endif
1874 #ifndef SQR_FFT_MODF_THRESHOLD
1875 #define SQR_FFT_MODF_THRESHOLD   (SQR_TOOM3_THRESHOLD * 3)
1876 #endif
1877 
1878 /* Threshold at which FFT should be used to do an NxN -> 2N multiply.  This
1879    will be a size where FFT is using k=7 or k=8, since an FFT-k used for an
1880    NxN->2N multiply and not recursing into itself is an order
1881    log(2^k)/log(2^(k-2)) algorithm, so it'll be at least k=7 at 1.39 which
1882    is the first better than toom3.  */
1883 #ifndef MUL_FFT_THRESHOLD
1884 #define MUL_FFT_THRESHOLD   (MUL_FFT_MODF_THRESHOLD * 10)
1885 #endif
1886 #ifndef SQR_FFT_THRESHOLD
1887 #define SQR_FFT_THRESHOLD   (SQR_FFT_MODF_THRESHOLD * 10)
1888 #endif
1889 
1890 /* Table of thresholds for successive modF FFT "k"s.  The first entry is
1891    where FFT_FIRST_K+1 should be used, the second FFT_FIRST_K+2,
1892    etc.  See mpn_fft_best_k(). */
1893 #ifndef MUL_FFT_TABLE
1894 #define MUL_FFT_TABLE                           \
1895   { MUL_TOOM33_THRESHOLD * 4,   /* k=5 */        \
1896     MUL_TOOM33_THRESHOLD * 8,   /* k=6 */        \
1897     MUL_TOOM33_THRESHOLD * 16,  /* k=7 */        \
1898     MUL_TOOM33_THRESHOLD * 32,  /* k=8 */        \
1899     MUL_TOOM33_THRESHOLD * 96,  /* k=9 */        \
1900     MUL_TOOM33_THRESHOLD * 288, /* k=10 */       \
1901     0 }
1902 #endif
1903 #ifndef SQR_FFT_TABLE
1904 #define SQR_FFT_TABLE                           \
1905   { SQR_TOOM3_THRESHOLD * 4,   /* k=5 */        \
1906     SQR_TOOM3_THRESHOLD * 8,   /* k=6 */        \
1907     SQR_TOOM3_THRESHOLD * 16,  /* k=7 */        \
1908     SQR_TOOM3_THRESHOLD * 32,  /* k=8 */        \
1909     SQR_TOOM3_THRESHOLD * 96,  /* k=9 */        \
1910     SQR_TOOM3_THRESHOLD * 288, /* k=10 */       \
1911     0 }
1912 #endif
1913 
1914 struct fft_table_nk
1915 {
1916   unsigned int n:27;
1917   unsigned int k:5;
1918 };
1919 
1920 #ifndef FFT_TABLE_ATTRS
1921 #define FFT_TABLE_ATTRS   static const
1922 #endif
1923 
1924 #define MPN_FFT_TABLE_SIZE  16
1925 
1926 
1927 #ifndef DC_DIV_QR_THRESHOLD
1928 #define DC_DIV_QR_THRESHOLD    (3 * MUL_TOOM22_THRESHOLD)
1929 #endif
1930 
1931 #ifndef GET_STR_DC_THRESHOLD
1932 #define GET_STR_DC_THRESHOLD             18
1933 #endif
1934 
1935 #ifndef GET_STR_PRECOMPUTE_THRESHOLD
1936 #define GET_STR_PRECOMPUTE_THRESHOLD     35
1937 #endif
1938 
1939 #ifndef SET_STR_DC_THRESHOLD
1940 #define SET_STR_DC_THRESHOLD            750
1941 #endif
1942 
1943 #ifndef SET_STR_PRECOMPUTE_THRESHOLD
1944 #define SET_STR_PRECOMPUTE_THRESHOLD   2000
1945 #endif
1946 
1947 /* Return non-zero if xp,xsize and yp,ysize overlap.
1948    If xp+xsize<=yp there's no overlap, or if yp+ysize<=xp there's no
1949    overlap.  If both these are false, there's an overlap. */
1950 #define MPN_OVERLAP_P(xp, xsize, yp, ysize) \
1951   ((xp) + (xsize) > (yp) && (yp) + (ysize) > (xp))
1952 #define MEM_OVERLAP_P(xp, xsize, yp, ysize)     \
1953   (   (char *) (xp) + (xsize) > (char *) (yp)   \
1954    && (char *) (yp) + (ysize) > (char *) (xp))
1955 
1956 /* Return non-zero if xp,xsize and yp,ysize are either identical or not
1957    overlapping.  Return zero if they're partially overlapping. */
1958 #define MPN_SAME_OR_SEPARATE_P(xp, yp, size)    \
1959   MPN_SAME_OR_SEPARATE2_P(xp, size, yp, size)
1960 #define MPN_SAME_OR_SEPARATE2_P(xp, xsize, yp, ysize)           \
1961   ((xp) == (yp) || ! MPN_OVERLAP_P (xp, xsize, yp, ysize))
1962 
1963 /* Return non-zero if dst,dsize and src,ssize are either identical or
1964    overlapping in a way suitable for an incrementing/decrementing algorithm.
1965    Return zero if they're partially overlapping in an unsuitable fashion. */
1966 #define MPN_SAME_OR_INCR2_P(dst, dsize, src, ssize)             \
1967   ((dst) <= (src) || ! MPN_OVERLAP_P (dst, dsize, src, ssize))
1968 #define MPN_SAME_OR_INCR_P(dst, src, size)      \
1969   MPN_SAME_OR_INCR2_P(dst, size, src, size)
1970 #define MPN_SAME_OR_DECR2_P(dst, dsize, src, ssize)             \
1971   ((dst) >= (src) || ! MPN_OVERLAP_P (dst, dsize, src, ssize))
1972 #define MPN_SAME_OR_DECR_P(dst, src, size)      \
1973   MPN_SAME_OR_DECR2_P(dst, size, src, size)
1974 
1975 
1976 /* ASSERT() is a private assertion checking scheme, similar to <assert.h>.
1977    ASSERT() does the check only if WANT_ASSERT is selected, ASSERT_ALWAYS()
1978    does it always.  Generally assertions are meant for development, but
1979    might help when looking for a problem later too.
1980 
1981    Note that strings shouldn't be used within the ASSERT expression,
1982    eg. ASSERT(strcmp(s,"notgood")!=0), since the quotes upset the "expr"
1983    used in the !HAVE_STRINGIZE case (ie. K&R).  */
1984 
1985 #ifdef __LINE__
1986 #define ASSERT_LINE  __LINE__
1987 #else
1988 #define ASSERT_LINE  -1
1989 #endif
1990 
1991 #ifdef __FILE__
1992 #define ASSERT_FILE  __FILE__
1993 #else
1994 #define ASSERT_FILE  ""
1995 #endif
1996 
1997 __GMP_DECLSPEC void __gmp_assert_header __GMP_PROTO ((const char *, int));
1998 __GMP_DECLSPEC void __gmp_assert_fail __GMP_PROTO ((const char *, int, const char *)) ATTRIBUTE_NORETURN;
1999 
2000 #if HAVE_STRINGIZE
2001 #define ASSERT_FAIL(expr)  __gmp_assert_fail (ASSERT_FILE, ASSERT_LINE, #expr)
2002 #else
2003 #define ASSERT_FAIL(expr)  __gmp_assert_fail (ASSERT_FILE, ASSERT_LINE, "expr")
2004 #endif
2005 
2006 #define ASSERT_ALWAYS(expr)     \
2007   do {                          \
2008     if (!(expr))                \
2009       ASSERT_FAIL (expr);       \
2010   } while (0)
2011 
2012 #if WANT_ASSERT
2013 #define ASSERT(expr)   ASSERT_ALWAYS (expr)
2014 #else
2015 #define ASSERT(expr)   do {} while (0)
2016 #endif
2017 
2018 
2019 /* ASSERT_CARRY checks the expression is non-zero, and ASSERT_NOCARRY checks
2020    that it's zero.  In both cases if assertion checking is disabled the
2021    expression is still evaluated.  These macros are meant for use with
2022    routines like mpn_add_n() where the return value represents a carry or
2023    whatever that should or shouldn't occur in some context.  For example,
2024    ASSERT_NOCARRY (mpn_add_n (rp, s1p, s2p, size)); */
2025 #if WANT_ASSERT
2026 #define ASSERT_CARRY(expr)     ASSERT_ALWAYS ((expr) != 0)
2027 #define ASSERT_NOCARRY(expr)   ASSERT_ALWAYS ((expr) == 0)
2028 #else
2029 #define ASSERT_CARRY(expr)     (expr)
2030 #define ASSERT_NOCARRY(expr)   (expr)
2031 #endif
2032 
2033 
2034 /* ASSERT_CODE includes code when assertion checking is wanted.  This is the
2035    same as writing "#if WANT_ASSERT", but more compact.  */
2036 #if WANT_ASSERT
2037 #define ASSERT_CODE(expr)  expr
2038 #else
2039 #define ASSERT_CODE(expr)
2040 #endif
2041 
2042 
2043 /* Test that an mpq_t is in fully canonical form.  This can be used as
2044    protection on routines like mpq_equal which give wrong results on
2045    non-canonical inputs.  */
2046 #if WANT_ASSERT
2047 #define ASSERT_MPQ_CANONICAL(q)                         \
2048   do {                                                  \
2049     ASSERT (q->_mp_den._mp_size > 0);                   \
2050     if (q->_mp_num._mp_size == 0)                       \
2051       {                                                 \
2052         /* zero should be 0/1 */                        \
2053         ASSERT (mpz_cmp_ui (mpq_denref(q), 1L) == 0);   \
2054       }                                                 \
2055     else                                                \
2056       {                                                 \
2057         /* no common factors */                         \
2058         mpz_t  __g;                                     \
2059         mpz_init (__g);                                 \
2060         mpz_gcd (__g, mpq_numref(q), mpq_denref(q));    \
2061         ASSERT (mpz_cmp_ui (__g, 1) == 0);              \
2062         mpz_clear (__g);                                \
2063       }                                                 \
2064   } while (0)
2065 #else
2066 #define ASSERT_MPQ_CANONICAL(q)  do {} while (0)
2067 #endif
2068 
2069 /* Check that the nail parts are zero. */
2070 #define ASSERT_ALWAYS_LIMB(limb)                \
2071   do {                                          \
2072     mp_limb_t  __nail = (limb) & GMP_NAIL_MASK; \
2073     ASSERT_ALWAYS (__nail == 0);                \
2074   } while (0)
2075 #define ASSERT_ALWAYS_MPN(ptr, size)            \
2076   do {                                          \
2077     /* let whole loop go dead when no nails */  \
2078     if (GMP_NAIL_BITS != 0)                     \
2079       {                                         \
2080         mp_size_t  __i;                         \
2081         for (__i = 0; __i < (size); __i++)      \
2082           ASSERT_ALWAYS_LIMB ((ptr)[__i]);      \
2083       }                                         \
2084   } while (0)
2085 #if WANT_ASSERT
2086 #define ASSERT_LIMB(limb)       ASSERT_ALWAYS_LIMB (limb)
2087 #define ASSERT_MPN(ptr, size)   ASSERT_ALWAYS_MPN (ptr, size)
2088 #else
2089 #define ASSERT_LIMB(limb)       do {} while (0)
2090 #define ASSERT_MPN(ptr, size)   do {} while (0)
2091 #endif
2092 
2093 
2094 /* Assert that an mpn region {ptr,size} is zero, or non-zero.
2095    size==0 is allowed, and in that case {ptr,size} considered to be zero.  */
2096 #if WANT_ASSERT
2097 #define ASSERT_MPN_ZERO_P(ptr,size)     \
2098   do {                                  \
2099     mp_size_t  __i;                     \
2100     ASSERT ((size) >= 0);               \
2101     for (__i = 0; __i < (size); __i++)  \
2102       ASSERT ((ptr)[__i] == 0);         \
2103   } while (0)
2104 #define ASSERT_MPN_NONZERO_P(ptr,size)  \
2105   do {                                  \
2106     mp_size_t  __i;                     \
2107     int        __nonzero = 0;           \
2108     ASSERT ((size) >= 0);               \
2109     for (__i = 0; __i < (size); __i++)  \
2110       if ((ptr)[__i] != 0)              \
2111         {                               \
2112           __nonzero = 1;                \
2113           break;                        \
2114         }                               \
2115     ASSERT (__nonzero);                 \
2116   } while (0)
2117 #else
2118 #define ASSERT_MPN_ZERO_P(ptr,size)     do {} while (0)
2119 #define ASSERT_MPN_NONZERO_P(ptr,size)  do {} while (0)
2120 #endif
2121 
2122 
2123 #if ! HAVE_NATIVE_mpn_com
2124 #undef mpn_com
2125 #define mpn_com(d,s,n)                                  \
2126   do {                                                  \
2127     mp_ptr     __d = (d);                               \
2128     mp_srcptr  __s = (s);                               \
2129     mp_size_t  __n = (n);                               \
2130     ASSERT (__n >= 1);                                  \
2131     ASSERT (MPN_SAME_OR_SEPARATE_P (__d, __s, __n));    \
2132     do                                                  \
2133       *__d++ = (~ *__s++) & GMP_NUMB_MASK;              \
2134     while (--__n);                                      \
2135   } while (0)
2136 #endif
2137 
2138 #define MPN_LOGOPS_N_INLINE(rp, up, vp, n, operation)			\
2139   do {									\
2140     mp_srcptr	__up = (up);						\
2141     mp_srcptr	__vp = (vp);						\
2142     mp_ptr	__rp = (rp);						\
2143     mp_size_t	__n = (n);						\
2144     mp_limb_t __a, __b;							\
2145     ASSERT (__n > 0);							\
2146     ASSERT (MPN_SAME_OR_SEPARATE_P (__rp, __up, __n));			\
2147     ASSERT (MPN_SAME_OR_SEPARATE_P (__rp, __vp, __n));			\
2148     __up += __n;							\
2149     __vp += __n;							\
2150     __rp += __n;							\
2151     __n = -__n;								\
2152     do {								\
2153       __a = __up[__n];							\
2154       __b = __vp[__n];							\
2155       __rp[__n] = operation;						\
2156     } while (++__n);							\
2157   } while (0)
2158 
2159 
2160 #if ! HAVE_NATIVE_mpn_and_n
2161 #undef mpn_and_n
2162 #define mpn_and_n(rp, up, vp, n) \
2163   MPN_LOGOPS_N_INLINE (rp, up, vp, n, __a & __b)
2164 #endif
2165 
2166 #if ! HAVE_NATIVE_mpn_andn_n
2167 #undef mpn_andn_n
2168 #define mpn_andn_n(rp, up, vp, n) \
2169   MPN_LOGOPS_N_INLINE (rp, up, vp, n, __a & ~__b)
2170 #endif
2171 
2172 #if ! HAVE_NATIVE_mpn_nand_n
2173 #undef mpn_nand_n
2174 #define mpn_nand_n(rp, up, vp, n) \
2175   MPN_LOGOPS_N_INLINE (rp, up, vp, n, ~(__a & __b) & GMP_NUMB_MASK)
2176 #endif
2177 
2178 #if ! HAVE_NATIVE_mpn_ior_n
2179 #undef mpn_ior_n
2180 #define mpn_ior_n(rp, up, vp, n) \
2181   MPN_LOGOPS_N_INLINE (rp, up, vp, n, __a | __b)
2182 #endif
2183 
2184 #if ! HAVE_NATIVE_mpn_iorn_n
2185 #undef mpn_iorn_n
2186 #define mpn_iorn_n(rp, up, vp, n) \
2187   MPN_LOGOPS_N_INLINE (rp, up, vp, n, (__a | ~__b) & GMP_NUMB_MASK)
2188 #endif
2189 
2190 #if ! HAVE_NATIVE_mpn_nior_n
2191 #undef mpn_nior_n
2192 #define mpn_nior_n(rp, up, vp, n) \
2193   MPN_LOGOPS_N_INLINE (rp, up, vp, n, ~(__a | __b) & GMP_NUMB_MASK)
2194 #endif
2195 
2196 #if ! HAVE_NATIVE_mpn_xor_n
2197 #undef mpn_xor_n
2198 #define mpn_xor_n(rp, up, vp, n) \
2199   MPN_LOGOPS_N_INLINE (rp, up, vp, n, __a ^ __b)
2200 #endif
2201 
2202 #if ! HAVE_NATIVE_mpn_xnor_n
2203 #undef mpn_xnor_n
2204 #define mpn_xnor_n(rp, up, vp, n) \
2205   MPN_LOGOPS_N_INLINE (rp, up, vp, n, ~(__a ^ __b) & GMP_NUMB_MASK)
2206 #endif
2207 
2208 #define mpn_trialdiv __MPN(trialdiv)
2209 __GMP_DECLSPEC mp_limb_t mpn_trialdiv __GMP_PROTO ((mp_srcptr, mp_size_t, mp_size_t, int *));
2210 
2211 #define mpn_remove __MPN(remove)
2212 __GMP_DECLSPEC mp_bitcnt_t mpn_remove __GMP_PROTO ((mp_ptr, mp_size_t *, mp_ptr, mp_size_t, mp_ptr, mp_size_t, mp_bitcnt_t));
2213 
2214 
2215 /* ADDC_LIMB sets w=x+y and cout to 0 or 1 for a carry from that addition. */
2216 #if GMP_NAIL_BITS == 0
2217 #define ADDC_LIMB(cout, w, x, y)        \
2218   do {                                  \
2219     mp_limb_t  __x = (x);               \
2220     mp_limb_t  __y = (y);               \
2221     mp_limb_t  __w = __x + __y;         \
2222     (w) = __w;                          \
2223     (cout) = __w < __x;                 \
2224   } while (0)
2225 #else
2226 #define ADDC_LIMB(cout, w, x, y)        \
2227   do {                                  \
2228     mp_limb_t  __w;                     \
2229     ASSERT_LIMB (x);                    \
2230     ASSERT_LIMB (y);                    \
2231     __w = (x) + (y);                    \
2232     (w) = __w & GMP_NUMB_MASK;          \
2233     (cout) = __w >> GMP_NUMB_BITS;      \
2234   } while (0)
2235 #endif
2236 
2237 /* SUBC_LIMB sets w=x-y and cout to 0 or 1 for a borrow from that
2238    subtract.  */
2239 #if GMP_NAIL_BITS == 0
2240 #define SUBC_LIMB(cout, w, x, y)        \
2241   do {                                  \
2242     mp_limb_t  __x = (x);               \
2243     mp_limb_t  __y = (y);               \
2244     mp_limb_t  __w = __x - __y;         \
2245     (w) = __w;                          \
2246     (cout) = __w > __x;                 \
2247   } while (0)
2248 #else
2249 #define SUBC_LIMB(cout, w, x, y)        \
2250   do {                                  \
2251     mp_limb_t  __w = (x) - (y);         \
2252     (w) = __w & GMP_NUMB_MASK;          \
2253     (cout) = __w >> (GMP_LIMB_BITS-1);  \
2254   } while (0)
2255 #endif
2256 
2257 
2258 /* MPN_INCR_U does {ptr,size} += n, MPN_DECR_U does {ptr,size} -= n, both
2259    expecting no carry (or borrow) from that.
2260 
2261    The size parameter is only for the benefit of assertion checking.  In a
2262    normal build it's unused and the carry/borrow is just propagated as far
2263    as it needs to go.
2264 
2265    On random data, usually only one or two limbs of {ptr,size} get updated,
2266    so there's no need for any sophisticated looping, just something compact
2267    and sensible.
2268 
2269    FIXME: Switch all code from mpn_{incr,decr}_u to MPN_{INCR,DECR}_U,
2270    declaring their operand sizes, then remove the former.  This is purely
2271    for the benefit of assertion checking.  */
2272 
2273 #if defined (__GNUC__) && HAVE_HOST_CPU_FAMILY_x86 && GMP_NAIL_BITS == 0      \
2274   && GMP_LIMB_BITS == 32 && ! defined (NO_ASM) && ! WANT_ASSERT
2275 /* Better flags handling than the generic C gives on i386, saving a few
2276    bytes of code and maybe a cycle or two.  */
2277 
2278 #define MPN_IORD_U(ptr, incr, aors)					\
2279   do {									\
2280     mp_ptr  __ptr_dummy;						\
2281     if (__builtin_constant_p (incr) && (incr) == 1)			\
2282       {									\
2283         __asm__ __volatile__						\
2284           ("\n" ASM_L(top) ":\n"					\
2285            "\t" aors " $1, (%0)\n"					\
2286            "\tleal 4(%0),%0\n"						\
2287            "\tjc " ASM_L(top)						\
2288            : "=r" (__ptr_dummy)						\
2289            : "0"  (ptr)							\
2290            : "memory");							\
2291       }									\
2292     else								\
2293       {									\
2294         __asm__ __volatile__						\
2295           (   aors  " %2,(%0)\n"					\
2296            "\tjnc " ASM_L(done) "\n"					\
2297            ASM_L(top) ":\n"						\
2298            "\t" aors " $1,4(%0)\n"					\
2299            "\tleal 4(%0),%0\n"						\
2300            "\tjc " ASM_L(top) "\n"					\
2301            ASM_L(done) ":\n"						\
2302            : "=r" (__ptr_dummy)						\
2303            : "0"  (ptr),						\
2304              "ri" (incr)						\
2305            : "memory");							\
2306       }									\
2307   } while (0)
2308 
2309 #define MPN_INCR_U(ptr, size, incr)  MPN_IORD_U (ptr, incr, "addl")
2310 #define MPN_DECR_U(ptr, size, incr)  MPN_IORD_U (ptr, incr, "subl")
2311 #define mpn_incr_u(ptr, incr)  MPN_INCR_U (ptr, 0, incr)
2312 #define mpn_decr_u(ptr, incr)  MPN_DECR_U (ptr, 0, incr)
2313 #endif
2314 
2315 #if GMP_NAIL_BITS == 0
2316 #ifndef mpn_incr_u
2317 #define mpn_incr_u(p,incr)                              \
2318   do {                                                  \
2319     mp_limb_t __x;                                      \
2320     mp_ptr __p = (p);                                   \
2321     if (__builtin_constant_p (incr) && (incr) == 1)     \
2322       {                                                 \
2323         while (++(*(__p++)) == 0)                       \
2324           ;                                             \
2325       }                                                 \
2326     else                                                \
2327       {                                                 \
2328         __x = *__p + (incr);                            \
2329         *__p = __x;                                     \
2330         if (__x < (incr))                               \
2331           while (++(*(++__p)) == 0)                     \
2332             ;                                           \
2333       }                                                 \
2334   } while (0)
2335 #endif
2336 #ifndef mpn_decr_u
2337 #define mpn_decr_u(p,incr)                              \
2338   do {                                                  \
2339     mp_limb_t __x;                                      \
2340     mp_ptr __p = (p);                                   \
2341     if (__builtin_constant_p (incr) && (incr) == 1)     \
2342       {                                                 \
2343         while ((*(__p++))-- == 0)                       \
2344           ;                                             \
2345       }                                                 \
2346     else                                                \
2347       {                                                 \
2348         __x = *__p;                                     \
2349         *__p = __x - (incr);                            \
2350         if (__x < (incr))                               \
2351           while ((*(++__p))-- == 0)                     \
2352             ;                                           \
2353       }                                                 \
2354   } while (0)
2355 #endif
2356 #endif
2357 
2358 #if GMP_NAIL_BITS >= 1
2359 #ifndef mpn_incr_u
2360 #define mpn_incr_u(p,incr)                              \
2361   do {							\
2362     mp_limb_t __x;					\
2363     mp_ptr __p = (p);					\
2364     if (__builtin_constant_p (incr) && (incr) == 1)	\
2365       {							\
2366 	do						\
2367 	  {						\
2368 	    __x = (*__p + 1) & GMP_NUMB_MASK;		\
2369 	    *__p++ = __x;				\
2370 	  }						\
2371 	while (__x == 0);				\
2372       }							\
2373     else						\
2374       {							\
2375 	__x = (*__p + (incr));				\
2376 	*__p++ = __x & GMP_NUMB_MASK;			\
2377 	if (__x >> GMP_NUMB_BITS != 0)			\
2378 	  {						\
2379 	    do						\
2380 	      {						\
2381 		__x = (*__p + 1) & GMP_NUMB_MASK;	\
2382 		*__p++ = __x;				\
2383 	      }						\
2384 	    while (__x == 0);				\
2385 	  }						\
2386       }							\
2387   } while (0)
2388 #endif
2389 #ifndef mpn_decr_u
2390 #define mpn_decr_u(p,incr)				\
2391   do {							\
2392     mp_limb_t __x;					\
2393     mp_ptr __p = (p);					\
2394     if (__builtin_constant_p (incr) && (incr) == 1)	\
2395       {							\
2396 	do						\
2397 	  {						\
2398 	    __x = *__p;					\
2399 	    *__p++ = (__x - 1) & GMP_NUMB_MASK;		\
2400 	  }						\
2401 	while (__x == 0);				\
2402       }							\
2403     else						\
2404       {							\
2405 	__x = *__p - (incr);				\
2406 	*__p++ = __x & GMP_NUMB_MASK;			\
2407 	if (__x >> GMP_NUMB_BITS != 0)			\
2408 	  {						\
2409 	    do						\
2410 	      {						\
2411 		__x = *__p;				\
2412 		*__p++ = (__x - 1) & GMP_NUMB_MASK;	\
2413 	      }						\
2414 	    while (__x == 0);				\
2415 	  }						\
2416       }							\
2417   } while (0)
2418 #endif
2419 #endif
2420 
2421 #ifndef MPN_INCR_U
2422 #if WANT_ASSERT
2423 #define MPN_INCR_U(ptr, size, n)                        \
2424   do {                                                  \
2425     ASSERT ((size) >= 1);                               \
2426     ASSERT_NOCARRY (mpn_add_1 (ptr, ptr, size, n));     \
2427   } while (0)
2428 #else
2429 #define MPN_INCR_U(ptr, size, n)   mpn_incr_u (ptr, n)
2430 #endif
2431 #endif
2432 
2433 #ifndef MPN_DECR_U
2434 #if WANT_ASSERT
2435 #define MPN_DECR_U(ptr, size, n)                        \
2436   do {                                                  \
2437     ASSERT ((size) >= 1);                               \
2438     ASSERT_NOCARRY (mpn_sub_1 (ptr, ptr, size, n));     \
2439   } while (0)
2440 #else
2441 #define MPN_DECR_U(ptr, size, n)   mpn_decr_u (ptr, n)
2442 #endif
2443 #endif
2444 
2445 
2446 /* Structure for conversion between internal binary format and
2447    strings in base 2..36.  */
2448 struct bases
2449 {
2450   /* Number of digits in the conversion base that always fits in an mp_limb_t.
2451      For example, for base 10 on a machine where a mp_limb_t has 32 bits this
2452      is 9, since 10**9 is the largest number that fits into a mp_limb_t.  */
2453   int chars_per_limb;
2454 
2455   /* log(2)/log(conversion_base) */
2456   double chars_per_bit_exactly;
2457 
2458   /* base**chars_per_limb, i.e. the biggest number that fits a word, built by
2459      factors of base.  Exception: For 2, 4, 8, etc, big_base is log2(base),
2460      i.e. the number of bits used to represent each digit in the base.  */
2461   mp_limb_t big_base;
2462 
2463   /* A GMP_LIMB_BITS bit approximation to 1/big_base, represented as a
2464      fixed-point number.  Instead of dividing by big_base an application can
2465      choose to multiply by big_base_inverted.  */
2466   mp_limb_t big_base_inverted;
2467 };
2468 
2469 #define   mp_bases __MPN(bases)
2470 __GMP_DECLSPEC extern const struct bases mp_bases[257];
2471 
2472 
2473 /* For power of 2 bases this is exact.  For other bases the result is either
2474    exact or one too big.
2475 
2476    To be exact always it'd be necessary to examine all the limbs of the
2477    operand, since numbers like 100..000 and 99...999 generally differ only
2478    in the lowest limb.  It'd be possible to examine just a couple of high
2479    limbs to increase the probability of being exact, but that doesn't seem
2480    worth bothering with.  */
2481 
2482 #define MPN_SIZEINBASE(result, ptr, size, base)                         \
2483   do {                                                                  \
2484     int       __lb_base, __cnt;                                         \
2485     size_t __totbits;                                                   \
2486                                                                         \
2487     ASSERT ((size) >= 0);                                               \
2488     ASSERT ((base) >= 2);                                               \
2489     ASSERT ((base) < numberof (mp_bases));                              \
2490                                                                         \
2491     /* Special case for X == 0.  */                                     \
2492     if ((size) == 0)                                                    \
2493       (result) = 1;                                                     \
2494     else                                                                \
2495       {                                                                 \
2496         /* Calculate the total number of significant bits of X.  */     \
2497         count_leading_zeros (__cnt, (ptr)[(size)-1]);                   \
2498         __totbits = (size_t) (size) * GMP_NUMB_BITS - (__cnt - GMP_NAIL_BITS);\
2499                                                                         \
2500         if (POW2_P (base))                                              \
2501           {                                                             \
2502             __lb_base = mp_bases[base].big_base;                        \
2503             (result) = (__totbits + __lb_base - 1) / __lb_base;         \
2504           }                                                             \
2505         else                                                            \
2506           (result) = (size_t)                                           \
2507             (__totbits * mp_bases[base].chars_per_bit_exactly) + 1;     \
2508       }                                                                 \
2509   } while (0)
2510 
2511 /* eliminate mp_bases lookups for base==16 */
2512 #define MPN_SIZEINBASE_16(result, ptr, size)                            \
2513   do {                                                                  \
2514     int       __cnt;                                                    \
2515     mp_size_t __totbits;                                                \
2516                                                                         \
2517     ASSERT ((size) >= 0);                                               \
2518                                                                         \
2519     /* Special case for X == 0.  */                                     \
2520     if ((size) == 0)                                                    \
2521       (result) = 1;                                                     \
2522     else                                                                \
2523       {                                                                 \
2524         /* Calculate the total number of significant bits of X.  */     \
2525         count_leading_zeros (__cnt, (ptr)[(size)-1]);                   \
2526         __totbits = (size_t) (size) * GMP_NUMB_BITS - (__cnt - GMP_NAIL_BITS);\
2527         (result) = (__totbits + 4 - 1) / 4;                             \
2528       }                                                                 \
2529   } while (0)
2530 
2531 /* bit count to limb count, rounding up */
2532 #define BITS_TO_LIMBS(n)  (((n) + (GMP_NUMB_BITS - 1)) / GMP_NUMB_BITS)
2533 
2534 /* MPN_SET_UI sets an mpn (ptr, cnt) to given ui.  MPZ_FAKE_UI creates fake
2535    mpz_t from ui.  The zp argument must have room for LIMBS_PER_ULONG limbs
2536    in both cases (LIMBS_PER_ULONG is also defined here.) */
2537 #if BITS_PER_ULONG <= GMP_NUMB_BITS /* need one limb per ulong */
2538 
2539 #define LIMBS_PER_ULONG 1
2540 #define MPN_SET_UI(zp, zn, u)   \
2541   (zp)[0] = (u);                \
2542   (zn) = ((zp)[0] != 0);
2543 #define MPZ_FAKE_UI(z, zp, u)   \
2544   (zp)[0] = (u);                \
2545   PTR (z) = (zp);               \
2546   SIZ (z) = ((zp)[0] != 0);     \
2547   ASSERT_CODE (ALLOC (z) = 1);
2548 
2549 #else /* need two limbs per ulong */
2550 
2551 #define LIMBS_PER_ULONG 2
2552 #define MPN_SET_UI(zp, zn, u)                          \
2553   (zp)[0] = (u) & GMP_NUMB_MASK;                       \
2554   (zp)[1] = (u) >> GMP_NUMB_BITS;                      \
2555   (zn) = ((zp)[1] != 0 ? 2 : (zp)[0] != 0 ? 1 : 0);
2556 #define MPZ_FAKE_UI(z, zp, u)                          \
2557   (zp)[0] = (u) & GMP_NUMB_MASK;                       \
2558   (zp)[1] = (u) >> GMP_NUMB_BITS;                      \
2559   SIZ (z) = ((zp)[1] != 0 ? 2 : (zp)[0] != 0 ? 1 : 0); \
2560   PTR (z) = (zp);                                      \
2561   ASSERT_CODE (ALLOC (z) = 2);
2562 
2563 #endif
2564 
2565 
2566 #if HAVE_HOST_CPU_FAMILY_x86
2567 #define TARGET_REGISTER_STARVED 1
2568 #else
2569 #define TARGET_REGISTER_STARVED 0
2570 #endif
2571 
2572 
2573 /* LIMB_HIGHBIT_TO_MASK(n) examines the high bit of a limb value and turns 1
2574    or 0 there into a limb 0xFF..FF or 0 respectively.
2575 
2576    On most CPUs this is just an arithmetic right shift by GMP_LIMB_BITS-1,
2577    but C99 doesn't guarantee signed right shifts are arithmetic, so we have
2578    a little compile-time test and a fallback to a "? :" form.  The latter is
2579    necessary for instance on Cray vector systems.
2580 
2581    Recent versions of gcc (eg. 3.3) will in fact optimize a "? :" like this
2582    to an arithmetic right shift anyway, but it's good to get the desired
2583    shift on past versions too (in particular since an important use of
2584    LIMB_HIGHBIT_TO_MASK is in udiv_qrnnd_preinv).  */
2585 
2586 #define LIMB_HIGHBIT_TO_MASK(n)                                 \
2587   (((mp_limb_signed_t) -1 >> 1) < 0                             \
2588    ? (mp_limb_signed_t) (n) >> (GMP_LIMB_BITS - 1)              \
2589    : (n) & GMP_LIMB_HIGHBIT ? MP_LIMB_T_MAX : CNST_LIMB(0))
2590 
2591 
2592 /* Use a library function for invert_limb, if available. */
2593 #define   mpn_invert_limb __MPN(invert_limb)
2594 __GMP_DECLSPEC mp_limb_t mpn_invert_limb __GMP_PROTO ((mp_limb_t)) ATTRIBUTE_CONST;
2595 #if ! defined (invert_limb) && HAVE_NATIVE_mpn_invert_limb
2596 #define invert_limb(invxl,xl)           \
2597   do {                                  \
2598     (invxl) = mpn_invert_limb (xl);     \
2599   } while (0)
2600 #endif
2601 
2602 #ifndef invert_limb
2603 #define invert_limb(invxl,xl)                   \
2604   do {                                          \
2605     mp_limb_t dummy;                            \
2606     ASSERT ((xl) != 0);                         \
2607     udiv_qrnnd (invxl, dummy, ~(xl), ~CNST_LIMB(0), xl);  \
2608   } while (0)
2609 #endif
2610 
2611 #define invert_pi1(dinv, d1, d0)				\
2612   do {								\
2613     mp_limb_t v, p, t1, t0, mask;				\
2614     invert_limb (v, d1);					\
2615     p = d1 * v;							\
2616     p += d0;							\
2617     if (p < d0)							\
2618       {								\
2619 	v--;							\
2620 	mask = -(p >= d1);					\
2621 	p -= d1;						\
2622 	v += mask;						\
2623 	p -= mask & d1;						\
2624       }								\
2625     umul_ppmm (t1, t0, d0, v);					\
2626     p += t1;							\
2627     if (p < t1)							\
2628       {								\
2629         v--;							\
2630 	if (UNLIKELY (p >= d1))					\
2631 	  {							\
2632 	    if (p > d1 || t0 >= d0)				\
2633 	      v--;						\
2634 	  }							\
2635       }								\
2636     (dinv).inv32 = v;						\
2637   } while (0)
2638 
2639 
2640 #ifndef udiv_qrnnd_preinv
2641 #define udiv_qrnnd_preinv udiv_qrnnd_preinv3
2642 #endif
2643 
2644 /* Divide the two-limb number in (NH,,NL) by D, with DI being the largest
2645    limb not larger than (2**(2*GMP_LIMB_BITS))/D - (2**GMP_LIMB_BITS).
2646    If this would yield overflow, DI should be the largest possible number
2647    (i.e., only ones).  For correct operation, the most significant bit of D
2648    has to be set.  Put the quotient in Q and the remainder in R.  */
2649 #define udiv_qrnnd_preinv1(q, r, nh, nl, d, di)				\
2650   do {									\
2651     mp_limb_t _q, _ql, _r;						\
2652     mp_limb_t _xh, _xl;							\
2653     ASSERT ((d) != 0);							\
2654     umul_ppmm (_q, _ql, (nh), (di));					\
2655     _q += (nh);	/* Compensate, di is 2**GMP_LIMB_BITS too small */	\
2656     umul_ppmm (_xh, _xl, _q, (d));					\
2657     sub_ddmmss (_xh, _r, (nh), (nl), _xh, _xl);				\
2658     if (_xh != 0)							\
2659       {									\
2660 	sub_ddmmss (_xh, _r, _xh, _r, 0, (d));				\
2661 	_q += 1;							\
2662 	if (_xh != 0)							\
2663 	  {								\
2664 	    _r -= (d);							\
2665 	    _q += 1;							\
2666 	  }								\
2667       }									\
2668     if (_r >= (d))							\
2669       {									\
2670 	_r -= (d);							\
2671 	_q += 1;							\
2672       }									\
2673     (r) = _r;								\
2674     (q) = _q;								\
2675   } while (0)
2676 
2677 /* Like udiv_qrnnd_preinv, but branch-free. */
2678 #define udiv_qrnnd_preinv2(q, r, nh, nl, d, di)				\
2679   do {									\
2680     mp_limb_t _n2, _n10, _nmask, _nadj, _q1;				\
2681     mp_limb_t _xh, _xl;							\
2682     _n2 = (nh);								\
2683     _n10 = (nl);							\
2684     _nmask = LIMB_HIGHBIT_TO_MASK (_n10);				\
2685     _nadj = _n10 + (_nmask & (d));					\
2686     umul_ppmm (_xh, _xl, di, _n2 - _nmask);				\
2687     add_ssaaaa (_xh, _xl, _xh, _xl, _n2, _nadj);			\
2688     _q1 = ~_xh;								\
2689     umul_ppmm (_xh, _xl, _q1, d);					\
2690     add_ssaaaa (_xh, _xl, _xh, _xl, nh, nl);				\
2691     _xh -= (d);					/* xh = 0 or -1 */	\
2692     (r) = _xl + ((d) & _xh);						\
2693     (q) = _xh - _q1;							\
2694   } while (0)
2695 
2696 /* Like udiv_qrnnd_preinv2, but for for any value D.  DNORM is D shifted left
2697    so that its most significant bit is set.  LGUP is ceil(log2(D)).  */
2698 #define udiv_qrnnd_preinv2gen(q, r, nh, nl, d, di, dnorm, lgup) \
2699   do {									\
2700     mp_limb_t _n2, _n10, _nmask, _nadj, _q1;				\
2701     mp_limb_t _xh, _xl;							\
2702     _n2 = ((nh) << (GMP_LIMB_BITS - (lgup))) + ((nl) >> 1 >> (l - 1));	\
2703     _n10 = (nl) << (GMP_LIMB_BITS - (lgup));				\
2704     _nmask = LIMB_HIGHBIT_TO_MASK (_n10);				\
2705     _nadj = _n10 + (_nmask & (dnorm));					\
2706     umul_ppmm (_xh, _xl, di, _n2 - _nmask);				\
2707     add_ssaaaa (_xh, _xl, _xh, _xl, _n2, _nadj);			\
2708     _q1 = ~_xh;								\
2709     umul_ppmm (_xh, _xl, _q1, d);					\
2710     add_ssaaaa (_xh, _xl, _xh, _xl, nh, nl);				\
2711     _xh -= (d);								\
2712     (r) = _xl + ((d) & _xh);						\
2713     (q) = _xh - _q1;							\
2714   } while (0)
2715 
2716 /* udiv_qrnnd_preinv3 -- Based on work by Niels M�ller and Torbj�rn Granlund.
2717 
2718    We write things strangely below, to help gcc.  A more straightforward
2719    version:
2720 
2721    _r = (nl) - _qh * (d);
2722    _t = _r + (d);
2723    if (_r >= _ql)
2724      {
2725        _qh--;
2726        _r = _t;
2727      }
2728 
2729    For one operation shorter critical path, one may want to use this form:
2730 
2731    _p = _qh * (d)
2732    _s = (nl) + (d);
2733    _r = (nl) - _p;
2734    _t = _s - _p;
2735    if (_r >= _ql)
2736      {
2737        _qh--;
2738        _r = _t;
2739      }
2740 */
2741 #define udiv_qrnnd_preinv3(q, r, nh, nl, d, di)				\
2742   do {									\
2743     mp_limb_t _qh, _ql, _r;						\
2744     umul_ppmm (_qh, _ql, (nh), (di));					\
2745     if (__builtin_constant_p (nl) && (nl) == 0)				\
2746       _qh += (nh) + 1;							\
2747     else								\
2748       add_ssaaaa (_qh, _ql, _qh, _ql, (nh) + 1, (nl));			\
2749     _r = (nl) - _qh * (d);						\
2750     if (_r > _ql)	/* both > and >= should be OK */		\
2751       {									\
2752 	_r += (d);							\
2753 	_qh--;								\
2754       }									\
2755     if (UNLIKELY (_r >= (d)))						\
2756       {									\
2757 	_r -= (d);							\
2758 	_qh++;								\
2759       }									\
2760     (r) = _r;								\
2761     (q) = _qh;								\
2762   } while (0)
2763 
2764 /* Compute r = nh*B mod d, where di is the inverse of d.  */
2765 #define udiv_rnd_preinv(r, nh, d, di)					\
2766   do {									\
2767     mp_limb_t _qh, _ql, _r;						\
2768     umul_ppmm (_qh, _ql, (nh), (di));					\
2769     _qh += (nh) + 1;							\
2770     _r = - _qh * (d);							\
2771     if (_r > _ql)							\
2772       _r += (d);							\
2773     (r) = _r;								\
2774   } while (0)
2775 
2776 /* Compute quotient the quotient and remainder for n / d. Requires d
2777    >= B^2 / 2 and n < d B. di is the inverse
2778 
2779      floor ((B^3 - 1) / (d0 + d1 B)) - B.
2780 
2781    NOTE: Output variables are updated multiple times. Only some inputs
2782    and outputs may overlap.
2783 */
2784 #define udiv_qr_3by2(q, r1, r0, n2, n1, n0, d1, d0, dinv)		\
2785   do {									\
2786     mp_limb_t _q0, _t1, _t0, _mask;					\
2787     umul_ppmm ((q), _q0, (n2), (dinv));					\
2788     add_ssaaaa ((q), _q0, (q), _q0, (n2), (n1));			\
2789 									\
2790     /* Compute the two most significant limbs of n - q'd */		\
2791     (r1) = (n1) - (d1) * (q);						\
2792     (r0) = (n0);							\
2793     sub_ddmmss ((r1), (r0), (r1), (r0), (d1), (d0));			\
2794     umul_ppmm (_t1, _t0, (d0), (q));					\
2795     sub_ddmmss ((r1), (r0), (r1), (r0), _t1, _t0);			\
2796     (q)++;								\
2797 									\
2798     /* Conditionally adjust q and the remainders */			\
2799     _mask = - (mp_limb_t) ((r1) >= _q0);				\
2800     (q) += _mask;							\
2801     add_ssaaaa ((r1), (r0), (r1), (r0), _mask & (d1), _mask & (d0));	\
2802     if (UNLIKELY ((r1) >= (d1)))					\
2803       {									\
2804 	if ((r1) > (d1) || (r0) >= (d0))				\
2805 	  {								\
2806 	    (q)++;							\
2807 	    sub_ddmmss ((r1), (r0), (r1), (r0), (d1), (d0));		\
2808 	  }								\
2809       }									\
2810   } while (0)
2811 
2812 #ifndef mpn_preinv_divrem_1  /* if not done with cpuvec in a fat binary */
2813 #define   mpn_preinv_divrem_1 __MPN(preinv_divrem_1)
2814 __GMP_DECLSPEC mp_limb_t mpn_preinv_divrem_1 __GMP_PROTO ((mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t, int));
2815 #endif
2816 
2817 
2818 /* USE_PREINV_DIVREM_1 is whether to use mpn_preinv_divrem_1, as opposed to the
2819    plain mpn_divrem_1.  The default is yes, since the few CISC chips where
2820    preinv is not good have defines saying so.  */
2821 #ifndef USE_PREINV_DIVREM_1
2822 #define USE_PREINV_DIVREM_1   1
2823 #endif
2824 
2825 #if USE_PREINV_DIVREM_1
2826 #define MPN_DIVREM_OR_PREINV_DIVREM_1(qp,xsize,ap,size,d,dinv,shift)    \
2827   mpn_preinv_divrem_1 (qp, xsize, ap, size, d, dinv, shift)
2828 #else
2829 #define MPN_DIVREM_OR_PREINV_DIVREM_1(qp,xsize,ap,size,d,dinv,shift)    \
2830   mpn_divrem_1 (qp, xsize, ap, size, d)
2831 #endif
2832 
2833 #ifndef PREINV_MOD_1_TO_MOD_1_THRESHOLD
2834 #define PREINV_MOD_1_TO_MOD_1_THRESHOLD 10
2835 #endif
2836 
2837 /* This selection may seem backwards.  The reason mpn_mod_1 typically takes
2838    over for larger sizes is that it uses the mod_1_1 function.  */
2839 #define MPN_MOD_OR_PREINV_MOD_1(src,size,divisor,inverse)       	\
2840   (BELOW_THRESHOLD (size, PREINV_MOD_1_TO_MOD_1_THRESHOLD)		\
2841    ? mpn_preinv_mod_1 (src, size, divisor, inverse)			\
2842    : mpn_mod_1 (src, size, divisor))
2843 
2844 
2845 #ifndef mpn_mod_34lsub1  /* if not done with cpuvec in a fat binary */
2846 #define   mpn_mod_34lsub1 __MPN(mod_34lsub1)
2847 __GMP_DECLSPEC mp_limb_t mpn_mod_34lsub1 __GMP_PROTO ((mp_srcptr, mp_size_t)) __GMP_ATTRIBUTE_PURE;
2848 #endif
2849 
2850 
2851 /* DIVEXACT_1_THRESHOLD is at what size to use mpn_divexact_1, as opposed to
2852    plain mpn_divrem_1.  Likewise BMOD_1_TO_MOD_1_THRESHOLD for
2853    mpn_modexact_1_odd against plain mpn_mod_1.  On most CPUs divexact and
2854    modexact are faster at all sizes, so the defaults are 0.  Those CPUs
2855    where this is not right have a tuned threshold.  */
2856 #ifndef DIVEXACT_1_THRESHOLD
2857 #define DIVEXACT_1_THRESHOLD  0
2858 #endif
2859 #ifndef BMOD_1_TO_MOD_1_THRESHOLD
2860 #define BMOD_1_TO_MOD_1_THRESHOLD  10
2861 #endif
2862 
2863 #ifndef mpn_divexact_1  /* if not done with cpuvec in a fat binary */
2864 #define mpn_divexact_1 __MPN(divexact_1)
2865 __GMP_DECLSPEC void    mpn_divexact_1 __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_limb_t));
2866 #endif
2867 
2868 #define MPN_DIVREM_OR_DIVEXACT_1(dst, src, size, divisor)                     \
2869   do {                                                                        \
2870     if (BELOW_THRESHOLD (size, DIVEXACT_1_THRESHOLD))                         \
2871       ASSERT_NOCARRY (mpn_divrem_1 (dst, (mp_size_t) 0, src, size, divisor)); \
2872     else                                                                      \
2873       {                                                                       \
2874         ASSERT (mpn_mod_1 (src, size, divisor) == 0);                         \
2875         mpn_divexact_1 (dst, src, size, divisor);                             \
2876       }                                                                       \
2877   } while (0)
2878 
2879 #ifndef mpn_modexact_1c_odd  /* if not done with cpuvec in a fat binary */
2880 #define   mpn_modexact_1c_odd __MPN(modexact_1c_odd)
2881 __GMP_DECLSPEC mp_limb_t mpn_modexact_1c_odd __GMP_PROTO ((mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t)) __GMP_ATTRIBUTE_PURE;
2882 #endif
2883 
2884 #if HAVE_NATIVE_mpn_modexact_1_odd
2885 #define   mpn_modexact_1_odd  __MPN(modexact_1_odd)
2886 __GMP_DECLSPEC mp_limb_t mpn_modexact_1_odd __GMP_PROTO ((mp_srcptr, mp_size_t, mp_limb_t)) __GMP_ATTRIBUTE_PURE;
2887 #else
2888 #define mpn_modexact_1_odd(src,size,divisor) \
2889   mpn_modexact_1c_odd (src, size, divisor, CNST_LIMB(0))
2890 #endif
2891 
2892 #define MPN_MOD_OR_MODEXACT_1_ODD(src,size,divisor)			\
2893   (BELOW_THRESHOLD (size, BMOD_1_TO_MOD_1_THRESHOLD)			\
2894    ? mpn_modexact_1_odd (src, size, divisor)				\
2895    : mpn_mod_1 (src, size, divisor))
2896 
2897 /* binvert_limb() sets inv to the multiplicative inverse of n modulo
2898    2^GMP_NUMB_BITS, ie. satisfying inv*n == 1 mod 2^GMP_NUMB_BITS.
2899    n must be odd (otherwise such an inverse doesn't exist).
2900 
2901    This is not to be confused with invert_limb(), which is completely
2902    different.
2903 
2904    The table lookup gives an inverse with the low 8 bits valid, and each
2905    multiply step doubles the number of bits.  See Jebelean "An algorithm for
2906    exact division" end of section 4 (reference in gmp.texi).
2907 
2908    Possible enhancement: Could use UHWtype until the last step, if half-size
2909    multiplies are faster (might help under _LONG_LONG_LIMB).
2910 
2911    Alternative: As noted in Granlund and Montgomery "Division by Invariant
2912    Integers using Multiplication" (reference in gmp.texi), n itself gives a
2913    3-bit inverse immediately, and could be used instead of a table lookup.
2914    A 4-bit inverse can be obtained effectively from xoring bits 1 and 2 into
2915    bit 3, for instance with (((n + 2) & 4) << 1) ^ n.  */
2916 
2917 #define binvert_limb_table  __gmp_binvert_limb_table
2918 __GMP_DECLSPEC extern const unsigned char  binvert_limb_table[128];
2919 
2920 #define binvert_limb(inv,n)						\
2921   do {									\
2922     mp_limb_t  __n = (n);						\
2923     mp_limb_t  __inv;							\
2924     ASSERT ((__n & 1) == 1);						\
2925 									\
2926     __inv = binvert_limb_table[(__n/2) & 0x7F]; /*  8 */		\
2927     if (GMP_NUMB_BITS > 8)   __inv = 2 * __inv - __inv * __inv * __n;	\
2928     if (GMP_NUMB_BITS > 16)  __inv = 2 * __inv - __inv * __inv * __n;	\
2929     if (GMP_NUMB_BITS > 32)  __inv = 2 * __inv - __inv * __inv * __n;	\
2930 									\
2931     if (GMP_NUMB_BITS > 64)						\
2932       {									\
2933 	int  __invbits = 64;						\
2934 	do {								\
2935 	  __inv = 2 * __inv - __inv * __inv * __n;			\
2936 	  __invbits *= 2;						\
2937 	} while (__invbits < GMP_NUMB_BITS);				\
2938       }									\
2939 									\
2940     ASSERT ((__inv * __n & GMP_NUMB_MASK) == 1);			\
2941     (inv) = __inv & GMP_NUMB_MASK;					\
2942   } while (0)
2943 #define modlimb_invert binvert_limb  /* backward compatibility */
2944 
2945 /* Multiplicative inverse of 3, modulo 2^GMP_NUMB_BITS.
2946    Eg. 0xAAAAAAAB for 32 bits, 0xAAAAAAAAAAAAAAAB for 64 bits.
2947    GMP_NUMB_MAX/3*2+1 is right when GMP_NUMB_BITS is even, but when it's odd
2948    we need to start from GMP_NUMB_MAX>>1. */
2949 #define MODLIMB_INVERSE_3 (((GMP_NUMB_MAX >> (GMP_NUMB_BITS % 2)) / 3) * 2 + 1)
2950 
2951 /* ceil(GMP_NUMB_MAX/3) and ceil(2*GMP_NUMB_MAX/3).
2952    These expressions work because GMP_NUMB_MAX%3 != 0 for all GMP_NUMB_BITS. */
2953 #define GMP_NUMB_CEIL_MAX_DIV3   (GMP_NUMB_MAX / 3 + 1)
2954 #define GMP_NUMB_CEIL_2MAX_DIV3  ((GMP_NUMB_MAX>>1) / 3 + 1 + GMP_NUMB_HIGHBIT)
2955 
2956 
2957 /* Set r to -a mod d.  a>=d is allowed.  Can give r>d.  All should be limbs.
2958 
2959    It's not clear whether this is the best way to do this calculation.
2960    Anything congruent to -a would be fine for the one limb congruence
2961    tests.  */
2962 
2963 #define NEG_MOD(r, a, d)						\
2964   do {									\
2965     ASSERT ((d) != 0);							\
2966     ASSERT_LIMB (a);							\
2967     ASSERT_LIMB (d);							\
2968 									\
2969     if ((a) <= (d))							\
2970       {									\
2971         /* small a is reasonably likely */				\
2972         (r) = (d) - (a);						\
2973       }									\
2974     else								\
2975       {									\
2976         unsigned   __twos;						\
2977         mp_limb_t  __dnorm;						\
2978         count_leading_zeros (__twos, d);				\
2979         __twos -= GMP_NAIL_BITS;					\
2980         __dnorm = (d) << __twos;					\
2981         (r) = ((a) <= __dnorm ? __dnorm : 2*__dnorm) - (a);		\
2982       }									\
2983 									\
2984     ASSERT_LIMB (r);							\
2985   } while (0)
2986 
2987 /* A bit mask of all the least significant zero bits of n, or -1 if n==0. */
2988 #define LOW_ZEROS_MASK(n)  (((n) & -(n)) - 1)
2989 
2990 
2991 /* ULONG_PARITY sets "p" to 1 if there's an odd number of 1 bits in "n", or
2992    to 0 if there's an even number.  "n" should be an unsigned long and "p"
2993    an int.  */
2994 
2995 #if defined (__GNUC__) && ! defined (NO_ASM) && HAVE_HOST_CPU_alpha_CIX
2996 #define ULONG_PARITY(p, n)						\
2997   do {									\
2998     int __p;								\
2999     __asm__ ("ctpop %1, %0" : "=r" (__p) : "r" (n));			\
3000     (p) = __p & 1;							\
3001   } while (0)
3002 #endif
3003 
3004 /* Cray intrinsic _popcnt. */
3005 #ifdef _CRAY
3006 #define ULONG_PARITY(p, n)      \
3007   do {                          \
3008     (p) = _popcnt (n) & 1;      \
3009   } while (0)
3010 #endif
3011 
3012 #if defined (__GNUC__) && ! defined (__INTEL_COMPILER)			\
3013     && ! defined (NO_ASM) && defined (__ia64)
3014 /* unsigned long is either 32 or 64 bits depending on the ABI, zero extend
3015    to a 64 bit unsigned long long for popcnt */
3016 #define ULONG_PARITY(p, n)						\
3017   do {									\
3018     unsigned long long  __n = (unsigned long) (n);			\
3019     int  __p;								\
3020     __asm__ ("popcnt %0 = %1" : "=r" (__p) : "r" (__n));		\
3021     (p) = __p & 1;							\
3022   } while (0)
3023 #endif
3024 
3025 #if defined (__GNUC__) && ! defined (__INTEL_COMPILER)			\
3026     && ! defined (NO_ASM) && HAVE_HOST_CPU_FAMILY_x86
3027 #if __GMP_GNUC_PREREQ (3,1)
3028 #define __GMP_qm "=Qm"
3029 #define __GMP_q "=Q"
3030 #else
3031 #define __GMP_qm "=qm"
3032 #define __GMP_q "=q"
3033 #endif
3034 #define ULONG_PARITY(p, n)						\
3035   do {									\
3036     char	   __p;							\
3037     unsigned long  __n = (n);						\
3038     __n ^= (__n >> 16);							\
3039     __asm__ ("xorb %h1, %b1\n\t"					\
3040 	     "setpo %0"							\
3041 	 : __GMP_qm (__p), __GMP_q (__n)				\
3042 	 : "1" (__n));							\
3043     (p) = __p;								\
3044   } while (0)
3045 #endif
3046 
3047 #if ! defined (ULONG_PARITY)
3048 #define ULONG_PARITY(p, n)						\
3049   do {									\
3050     unsigned long  __n = (n);						\
3051     int  __p = 0;							\
3052     do									\
3053       {									\
3054         __p ^= 0x96696996L >> (__n & 0x1F);				\
3055         __n >>= 5;							\
3056       }									\
3057     while (__n != 0);							\
3058 									\
3059     (p) = __p & 1;							\
3060   } while (0)
3061 #endif
3062 
3063 
3064 /* 3 cycles on 604 or 750 since shifts and rlwimi's can pair.  gcc (as of
3065    version 3.1 at least) doesn't seem to know how to generate rlwimi for
3066    anything other than bit-fields, so use "asm".  */
3067 #if defined (__GNUC__) && ! defined (NO_ASM)                    \
3068   && HAVE_HOST_CPU_FAMILY_powerpc && GMP_LIMB_BITS == 32
3069 #define BSWAP_LIMB(dst, src)						\
3070   do {									\
3071     mp_limb_t  __bswapl_src = (src);					\
3072     mp_limb_t  __tmp1 = __bswapl_src >> 24;		/* low byte */	\
3073     mp_limb_t  __tmp2 = __bswapl_src << 24;		/* high byte */	\
3074     __asm__ ("rlwimi %0, %2, 24, 16, 23"		/* 2nd low */	\
3075 	 : "=r" (__tmp1) : "0" (__tmp1), "r" (__bswapl_src));		\
3076     __asm__ ("rlwimi %0, %2,  8,  8, 15"		/* 3nd high */	\
3077 	 : "=r" (__tmp2) : "0" (__tmp2), "r" (__bswapl_src));		\
3078     (dst) = __tmp1 | __tmp2;				/* whole */	\
3079   } while (0)
3080 #endif
3081 
3082 /* bswap is available on i486 and up and is fast.  A combination rorw $8 /
3083    roll $16 / rorw $8 is used in glibc for plain i386 (and in the linux
3084    kernel with xchgb instead of rorw), but this is not done here, because
3085    i386 means generic x86 and mixing word and dword operations will cause
3086    partial register stalls on P6 chips.  */
3087 #if defined (__GNUC__) && ! defined (NO_ASM)            \
3088   && HAVE_HOST_CPU_FAMILY_x86 && ! HAVE_HOST_CPU_i386   \
3089   && GMP_LIMB_BITS == 32
3090 #define BSWAP_LIMB(dst, src)						\
3091   do {									\
3092     __asm__ ("bswap %0" : "=r" (dst) : "0" (src));			\
3093   } while (0)
3094 #endif
3095 
3096 #if defined (__GNUC__) && ! defined (NO_ASM)            \
3097   && defined (__amd64__) && GMP_LIMB_BITS == 64
3098 #define BSWAP_LIMB(dst, src)						\
3099   do {									\
3100     __asm__ ("bswap %q0" : "=r" (dst) : "0" (src));			\
3101   } while (0)
3102 #endif
3103 
3104 #if defined (__GNUC__) && ! defined (__INTEL_COMPILER)			\
3105     && ! defined (NO_ASM) && defined (__ia64) && GMP_LIMB_BITS == 64
3106 #define BSWAP_LIMB(dst, src)						\
3107   do {									\
3108     __asm__ ("mux1 %0 = %1, @rev" : "=r" (dst) :  "r" (src));		\
3109   } while (0)
3110 #endif
3111 
3112 /* As per glibc. */
3113 #if defined (__GNUC__) && ! defined (NO_ASM)                    \
3114   && HAVE_HOST_CPU_FAMILY_m68k && GMP_LIMB_BITS == 32
3115 #define BSWAP_LIMB(dst, src)						\
3116   do {									\
3117     mp_limb_t  __bswapl_src = (src);					\
3118     __asm__ ("ror%.w %#8, %0\n\t"					\
3119 	     "swap   %0\n\t"						\
3120 	     "ror%.w %#8, %0"						\
3121 	     : "=d" (dst)						\
3122 	     : "0" (__bswapl_src));					\
3123   } while (0)
3124 #endif
3125 
3126 #if ! defined (BSWAP_LIMB)
3127 #if GMP_LIMB_BITS == 8
3128 #define BSWAP_LIMB(dst, src)            \
3129   do { (dst) = (src); } while (0)
3130 #endif
3131 #if GMP_LIMB_BITS == 16
3132 #define BSWAP_LIMB(dst, src)                    \
3133   do {                                          \
3134     (dst) = ((src) << 8) + ((src) >> 8);        \
3135   } while (0)
3136 #endif
3137 #if GMP_LIMB_BITS == 32
3138 #define BSWAP_LIMB(dst, src)    \
3139   do {                          \
3140     (dst) =                     \
3141       ((src) << 24)             \
3142       + (((src) & 0xFF00) << 8) \
3143       + (((src) >> 8) & 0xFF00) \
3144       + ((src) >> 24);          \
3145   } while (0)
3146 #endif
3147 #if GMP_LIMB_BITS == 64
3148 #define BSWAP_LIMB(dst, src)            \
3149   do {                                  \
3150     (dst) =                             \
3151       ((src) << 56)                     \
3152       + (((src) & 0xFF00) << 40)        \
3153       + (((src) & 0xFF0000) << 24)      \
3154       + (((src) & 0xFF000000) << 8)     \
3155       + (((src) >> 8) & 0xFF000000)     \
3156       + (((src) >> 24) & 0xFF0000)      \
3157       + (((src) >> 40) & 0xFF00)        \
3158       + ((src) >> 56);                  \
3159   } while (0)
3160 #endif
3161 #endif
3162 
3163 #if ! defined (BSWAP_LIMB)
3164 #define BSWAP_LIMB(dst, src)                            \
3165   do {                                                  \
3166     mp_limb_t  __bswapl_src = (src);                    \
3167     mp_limb_t  __dst = 0;                               \
3168     int        __i;                                     \
3169     for (__i = 0; __i < BYTES_PER_MP_LIMB; __i++)       \
3170       {                                                 \
3171         __dst = (__dst << 8) | (__bswapl_src & 0xFF);   \
3172         __bswapl_src >>= 8;                             \
3173       }                                                 \
3174     (dst) = __dst;                                      \
3175   } while (0)
3176 #endif
3177 
3178 
3179 /* Apparently lwbrx might be slow on some PowerPC chips, so restrict it to
3180    those we know are fast.  */
3181 #if defined (__GNUC__) && ! defined (NO_ASM)                            \
3182   && GMP_LIMB_BITS == 32 && HAVE_LIMB_BIG_ENDIAN                        \
3183   && (HAVE_HOST_CPU_powerpc604                                          \
3184       || HAVE_HOST_CPU_powerpc604e                                      \
3185       || HAVE_HOST_CPU_powerpc750                                       \
3186       || HAVE_HOST_CPU_powerpc7400)
3187 #define BSWAP_LIMB_FETCH(limb, src)					\
3188   do {									\
3189     mp_srcptr  __blf_src = (src);					\
3190     mp_limb_t  __limb;							\
3191     __asm__ ("lwbrx %0, 0, %1"						\
3192 	     : "=r" (__limb)						\
3193 	     : "r" (__blf_src),						\
3194 	       "m" (*__blf_src));					\
3195     (limb) = __limb;							\
3196   } while (0)
3197 #endif
3198 
3199 #if ! defined (BSWAP_LIMB_FETCH)
3200 #define BSWAP_LIMB_FETCH(limb, src)  BSWAP_LIMB (limb, *(src))
3201 #endif
3202 
3203 
3204 /* On the same basis that lwbrx might be slow, restrict stwbrx to those we
3205    know are fast.  FIXME: Is this necessary?  */
3206 #if defined (__GNUC__) && ! defined (NO_ASM)                            \
3207   && GMP_LIMB_BITS == 32 && HAVE_LIMB_BIG_ENDIAN                        \
3208   && (HAVE_HOST_CPU_powerpc604                                          \
3209       || HAVE_HOST_CPU_powerpc604e                                      \
3210       || HAVE_HOST_CPU_powerpc750                                       \
3211       || HAVE_HOST_CPU_powerpc7400)
3212 #define BSWAP_LIMB_STORE(dst, limb)					\
3213   do {									\
3214     mp_ptr     __dst = (dst);						\
3215     mp_limb_t  __limb = (limb);						\
3216     __asm__ ("stwbrx %1, 0, %2"						\
3217 	     : "=m" (*__dst)						\
3218 	     : "r" (__limb),						\
3219 	       "r" (__dst));						\
3220   } while (0)
3221 #endif
3222 
3223 #if ! defined (BSWAP_LIMB_STORE)
3224 #define BSWAP_LIMB_STORE(dst, limb)  BSWAP_LIMB (*(dst), limb)
3225 #endif
3226 
3227 
3228 /* Byte swap limbs from {src,size} and store at {dst,size}. */
3229 #define MPN_BSWAP(dst, src, size)                       \
3230   do {                                                  \
3231     mp_ptr     __dst = (dst);                           \
3232     mp_srcptr  __src = (src);                           \
3233     mp_size_t  __size = (size);                         \
3234     mp_size_t  __i;                                     \
3235     ASSERT ((size) >= 0);                               \
3236     ASSERT (MPN_SAME_OR_SEPARATE_P (dst, src, size));   \
3237     CRAY_Pragma ("_CRI ivdep");                         \
3238     for (__i = 0; __i < __size; __i++)                  \
3239       {                                                 \
3240         BSWAP_LIMB_FETCH (*__dst, __src);               \
3241         __dst++;                                        \
3242         __src++;                                        \
3243       }                                                 \
3244   } while (0)
3245 
3246 /* Byte swap limbs from {dst,size} and store in reverse order at {src,size}. */
3247 #define MPN_BSWAP_REVERSE(dst, src, size)               \
3248   do {                                                  \
3249     mp_ptr     __dst = (dst);                           \
3250     mp_size_t  __size = (size);                         \
3251     mp_srcptr  __src = (src) + __size - 1;              \
3252     mp_size_t  __i;                                     \
3253     ASSERT ((size) >= 0);                               \
3254     ASSERT (! MPN_OVERLAP_P (dst, size, src, size));    \
3255     CRAY_Pragma ("_CRI ivdep");                         \
3256     for (__i = 0; __i < __size; __i++)                  \
3257       {                                                 \
3258         BSWAP_LIMB_FETCH (*__dst, __src);               \
3259         __dst++;                                        \
3260         __src--;                                        \
3261       }                                                 \
3262   } while (0)
3263 
3264 
3265 /* No processor claiming to be SPARC v9 compliant seems to
3266    implement the POPC instruction.  Disable pattern for now.  */
3267 #if 0
3268 #if defined __GNUC__ && defined __sparc_v9__ && GMP_LIMB_BITS == 64
3269 #define popc_limb(result, input)					\
3270   do {									\
3271     DItype __res;							\
3272     __asm__ ("popc %1,%0" : "=r" (result) : "rI" (input));		\
3273   } while (0)
3274 #endif
3275 #endif
3276 
3277 #if defined (__GNUC__) && ! defined (NO_ASM) && HAVE_HOST_CPU_alpha_CIX
3278 #define popc_limb(result, input)					\
3279   do {									\
3280     __asm__ ("ctpop %1, %0" : "=r" (result) : "r" (input));		\
3281   } while (0)
3282 #endif
3283 
3284 /* Cray intrinsic. */
3285 #ifdef _CRAY
3286 #define popc_limb(result, input)        \
3287   do {                                  \
3288     (result) = _popcnt (input);         \
3289   } while (0)
3290 #endif
3291 
3292 #if defined (__GNUC__) && ! defined (__INTEL_COMPILER)			\
3293     && ! defined (NO_ASM) && defined (__ia64) && GMP_LIMB_BITS == 64
3294 #define popc_limb(result, input)					\
3295   do {									\
3296     __asm__ ("popcnt %0 = %1" : "=r" (result) : "r" (input));		\
3297   } while (0)
3298 #endif
3299 
3300 /* Cool population count of an mp_limb_t.
3301    You have to figure out how this works, We won't tell you!
3302 
3303    The constants could also be expressed as:
3304      0x55... = [2^N / 3]     = [(2^N-1)/3]
3305      0x33... = [2^N / 5]     = [(2^N-1)/5]
3306      0x0f... = [2^N / 17]    = [(2^N-1)/17]
3307      (N is GMP_LIMB_BITS, [] denotes truncation.) */
3308 
3309 #if ! defined (popc_limb) && GMP_LIMB_BITS == 8
3310 #define popc_limb(result, input)					\
3311   do {									\
3312     mp_limb_t  __x = (input);						\
3313     __x -= (__x >> 1) & MP_LIMB_T_MAX/3;				\
3314     __x = ((__x >> 2) & MP_LIMB_T_MAX/5) + (__x & MP_LIMB_T_MAX/5);	\
3315     __x = ((__x >> 4) + __x) & MP_LIMB_T_MAX/17;			\
3316     (result) = __x & 0xff;						\
3317   } while (0)
3318 #endif
3319 
3320 #if ! defined (popc_limb) && GMP_LIMB_BITS == 16
3321 #define popc_limb(result, input)					\
3322   do {									\
3323     mp_limb_t  __x = (input);						\
3324     __x -= (__x >> 1) & MP_LIMB_T_MAX/3;				\
3325     __x = ((__x >> 2) & MP_LIMB_T_MAX/5) + (__x & MP_LIMB_T_MAX/5);	\
3326     __x = ((__x >> 4) + __x) & MP_LIMB_T_MAX/17;			\
3327     __x = ((__x >> 8) + __x);						\
3328     (result) = __x & 0xff;						\
3329   } while (0)
3330 #endif
3331 
3332 #if ! defined (popc_limb) && GMP_LIMB_BITS == 32
3333 #define popc_limb(result, input)					\
3334   do {									\
3335     mp_limb_t  __x = (input);						\
3336     __x -= (__x >> 1) & MP_LIMB_T_MAX/3;				\
3337     __x = ((__x >> 2) & MP_LIMB_T_MAX/5) + (__x & MP_LIMB_T_MAX/5);	\
3338     __x = ((__x >> 4) + __x) & MP_LIMB_T_MAX/17;			\
3339     __x = ((__x >> 8) + __x);						\
3340     __x = ((__x >> 16) + __x);						\
3341     (result) = __x & 0xff;						\
3342   } while (0)
3343 #endif
3344 
3345 #if ! defined (popc_limb) && GMP_LIMB_BITS == 64
3346 #define popc_limb(result, input)					\
3347   do {									\
3348     mp_limb_t  __x = (input);						\
3349     __x -= (__x >> 1) & MP_LIMB_T_MAX/3;				\
3350     __x = ((__x >> 2) & MP_LIMB_T_MAX/5) + (__x & MP_LIMB_T_MAX/5);	\
3351     __x = ((__x >> 4) + __x) & MP_LIMB_T_MAX/17;			\
3352     __x = ((__x >> 8) + __x);						\
3353     __x = ((__x >> 16) + __x);						\
3354     __x = ((__x >> 32) + __x);						\
3355     (result) = __x & 0xff;						\
3356   } while (0)
3357 #endif
3358 
3359 
3360 /* Define stuff for longlong.h.  */
3361 #if HAVE_ATTRIBUTE_MODE
3362 typedef unsigned int UQItype	__attribute__ ((mode (QI)));
3363 typedef		 int SItype	__attribute__ ((mode (SI)));
3364 typedef unsigned int USItype	__attribute__ ((mode (SI)));
3365 typedef		 int DItype	__attribute__ ((mode (DI)));
3366 typedef unsigned int UDItype	__attribute__ ((mode (DI)));
3367 #else
3368 typedef unsigned char UQItype;
3369 typedef		 long SItype;
3370 typedef unsigned long USItype;
3371 #if HAVE_LONG_LONG
3372 typedef	long long int DItype;
3373 typedef unsigned long long int UDItype;
3374 #else /* Assume `long' gives us a wide enough type.  Needed for hppa2.0w.  */
3375 typedef long int DItype;
3376 typedef unsigned long int UDItype;
3377 #endif
3378 #endif
3379 
3380 typedef mp_limb_t UWtype;
3381 typedef unsigned int UHWtype;
3382 #define W_TYPE_SIZE GMP_LIMB_BITS
3383 
3384 /* Define ieee_double_extract and _GMP_IEEE_FLOATS.
3385 
3386    Bit field packing is "implementation defined" according to C99, which
3387    leaves us at the compiler's mercy here.  For some systems packing is
3388    defined in the ABI (eg. x86).  In any case so far it seems universal that
3389    little endian systems pack from low to high, and big endian from high to
3390    low within the given type.
3391 
3392    Within the fields we rely on the integer endianness being the same as the
3393    float endianness, this is true everywhere we know of and it'd be a fairly
3394    strange system that did anything else.  */
3395 
3396 #if HAVE_DOUBLE_IEEE_LITTLE_SWAPPED
3397 #define _GMP_IEEE_FLOATS 1
3398 union ieee_double_extract
3399 {
3400   struct
3401     {
3402       gmp_uint_least32_t manh:20;
3403       gmp_uint_least32_t exp:11;
3404       gmp_uint_least32_t sig:1;
3405       gmp_uint_least32_t manl:32;
3406     } s;
3407   double d;
3408 };
3409 #endif
3410 
3411 #if HAVE_DOUBLE_IEEE_LITTLE_ENDIAN
3412 #define _GMP_IEEE_FLOATS 1
3413 union ieee_double_extract
3414 {
3415   struct
3416     {
3417       gmp_uint_least32_t manl:32;
3418       gmp_uint_least32_t manh:20;
3419       gmp_uint_least32_t exp:11;
3420       gmp_uint_least32_t sig:1;
3421     } s;
3422   double d;
3423 };
3424 #endif
3425 
3426 #if HAVE_DOUBLE_IEEE_BIG_ENDIAN
3427 #define _GMP_IEEE_FLOATS 1
3428 union ieee_double_extract
3429 {
3430   struct
3431     {
3432       gmp_uint_least32_t sig:1;
3433       gmp_uint_least32_t exp:11;
3434       gmp_uint_least32_t manh:20;
3435       gmp_uint_least32_t manl:32;
3436     } s;
3437   double d;
3438 };
3439 #endif
3440 
3441 
3442 /* Use (4.0 * ...) instead of (2.0 * ...) to work around buggy compilers
3443    that don't convert ulong->double correctly (eg. SunOS 4 native cc).  */
3444 #define MP_BASE_AS_DOUBLE (4.0 * ((mp_limb_t) 1 << (GMP_NUMB_BITS - 2)))
3445 /* Maximum number of limbs it will take to store any `double'.
3446    We assume doubles have 53 mantissa bits.  */
3447 #define LIMBS_PER_DOUBLE ((53 + GMP_NUMB_BITS - 2) / GMP_NUMB_BITS + 1)
3448 
3449 __GMP_DECLSPEC int __gmp_extract_double __GMP_PROTO ((mp_ptr, double));
3450 
3451 #define mpn_get_d __gmpn_get_d
3452 __GMP_DECLSPEC double mpn_get_d __GMP_PROTO ((mp_srcptr, mp_size_t, mp_size_t, long)) __GMP_ATTRIBUTE_PURE;
3453 
3454 
3455 /* DOUBLE_NAN_INF_ACTION executes code a_nan if x is a NaN, or executes
3456    a_inf if x is an infinity.  Both are considered unlikely values, for
3457    branch prediction.  */
3458 
3459 #if _GMP_IEEE_FLOATS
3460 #define DOUBLE_NAN_INF_ACTION(x, a_nan, a_inf)  \
3461   do {                                          \
3462     union ieee_double_extract  u;               \
3463     u.d = (x);                                  \
3464     if (UNLIKELY (u.s.exp == 0x7FF))            \
3465       {                                         \
3466         if (u.s.manl == 0 && u.s.manh == 0)     \
3467           { a_inf; }                            \
3468         else                                    \
3469           { a_nan; }                            \
3470       }                                         \
3471   } while (0)
3472 #endif
3473 
3474 #if HAVE_DOUBLE_VAX_D || HAVE_DOUBLE_VAX_G || HAVE_DOUBLE_CRAY_CFP
3475 /* no nans or infs in these formats */
3476 #define DOUBLE_NAN_INF_ACTION(x, a_nan, a_inf)  \
3477   do { } while (0)
3478 #endif
3479 
3480 #ifndef DOUBLE_NAN_INF_ACTION
3481 /* Unknown format, try something generic.
3482    NaN should be "unordered", so x!=x.
3483    Inf should be bigger than DBL_MAX.  */
3484 #define DOUBLE_NAN_INF_ACTION(x, a_nan, a_inf)                  \
3485   do {                                                          \
3486     {                                                           \
3487       if (UNLIKELY ((x) != (x)))                                \
3488         { a_nan; }                                              \
3489       else if (UNLIKELY ((x) > DBL_MAX || (x) < -DBL_MAX))      \
3490         { a_inf; }                                              \
3491     }                                                           \
3492   } while (0)
3493 #endif
3494 
3495 /* On m68k, x86 and amd64, gcc (and maybe other compilers) can hold doubles
3496    in the coprocessor, which means a bigger exponent range than normal, and
3497    depending on the rounding mode, a bigger mantissa than normal.  (See
3498    "Disappointments" in the gcc manual.)  FORCE_DOUBLE stores and fetches
3499    "d" through memory to force any rounding and overflows to occur.
3500 
3501    On amd64, and on x86s with SSE2, gcc (depending on options) uses the xmm
3502    registers, where there's no such extra precision and no need for the
3503    FORCE_DOUBLE.  We don't bother to detect this since the present uses for
3504    FORCE_DOUBLE are only in test programs and default generic C code.
3505 
3506    Not quite sure that an "automatic volatile" will use memory, but it does
3507    in gcc.  An asm("":"=m"(d):"0"(d)) can't be used to trick gcc, since
3508    apparently matching operands like "0" are only allowed on a register
3509    output.  gcc 3.4 warns about this, though in fact it and past versions
3510    seem to put the operand through memory as hoped.  */
3511 
3512 #if (HAVE_HOST_CPU_FAMILY_m68k || HAVE_HOST_CPU_FAMILY_x86      \
3513      || defined (__amd64__))
3514 #define FORCE_DOUBLE(d) \
3515   do { volatile double __gmp_force = (d); (d) = __gmp_force; } while (0)
3516 #else
3517 #define FORCE_DOUBLE(d)  do { } while (0)
3518 #endif
3519 
3520 
3521 __GMP_DECLSPEC extern int __gmp_junk;
3522 __GMP_DECLSPEC extern const int __gmp_0;
3523 __GMP_DECLSPEC void __gmp_exception __GMP_PROTO ((int)) ATTRIBUTE_NORETURN;
3524 __GMP_DECLSPEC void __gmp_divide_by_zero __GMP_PROTO ((void)) ATTRIBUTE_NORETURN;
3525 __GMP_DECLSPEC void __gmp_sqrt_of_negative __GMP_PROTO ((void)) ATTRIBUTE_NORETURN;
3526 __GMP_DECLSPEC void __gmp_invalid_operation __GMP_PROTO ((void)) ATTRIBUTE_NORETURN;
3527 #define GMP_ERROR(code)   __gmp_exception (code)
3528 #define DIVIDE_BY_ZERO    __gmp_divide_by_zero ()
3529 #define SQRT_OF_NEGATIVE  __gmp_sqrt_of_negative ()
3530 
3531 #if defined _LONG_LONG_LIMB
3532 #if __GMP_HAVE_TOKEN_PASTE
3533 #define CNST_LIMB(C) ((mp_limb_t) C##LL)
3534 #else
3535 #define CNST_LIMB(C) ((mp_limb_t) C/**/LL)
3536 #endif
3537 #else /* not _LONG_LONG_LIMB */
3538 #if __GMP_HAVE_TOKEN_PASTE
3539 #define CNST_LIMB(C) ((mp_limb_t) C##L)
3540 #else
3541 #define CNST_LIMB(C) ((mp_limb_t) C/**/L)
3542 #endif
3543 #endif /* _LONG_LONG_LIMB */
3544 
3545 /* Stuff used by mpn/generic/perfsqr.c and mpz/prime_p.c */
3546 #if GMP_NUMB_BITS == 2
3547 #define PP 0x3					/* 3 */
3548 #define PP_FIRST_OMITTED 5
3549 #endif
3550 #if GMP_NUMB_BITS == 4
3551 #define PP 0xF					/* 3 x 5 */
3552 #define PP_FIRST_OMITTED 7
3553 #endif
3554 #if GMP_NUMB_BITS == 8
3555 #define PP 0x69					/* 3 x 5 x 7 */
3556 #define PP_FIRST_OMITTED 11
3557 #endif
3558 #if GMP_NUMB_BITS == 16
3559 #define PP 0x3AA7				/* 3 x 5 x 7 x 11 x 13 */
3560 #define PP_FIRST_OMITTED 17
3561 #endif
3562 #if GMP_NUMB_BITS == 32
3563 #define PP 0xC0CFD797L				/* 3 x 5 x 7 x 11 x ... x 29 */
3564 #define PP_INVERTED 0x53E5645CL
3565 #define PP_FIRST_OMITTED 31
3566 #endif
3567 #if GMP_NUMB_BITS == 64
3568 #define PP CNST_LIMB(0xE221F97C30E94E1D)	/* 3 x 5 x 7 x 11 x ... x 53 */
3569 #define PP_INVERTED CNST_LIMB(0x21CFE6CFC938B36B)
3570 #define PP_FIRST_OMITTED 59
3571 #endif
3572 #ifndef PP_FIRST_OMITTED
3573 #define PP_FIRST_OMITTED 3
3574 #endif
3575 
3576 
3577 
3578 /* BIT1 means a result value in bit 1 (second least significant bit), with a
3579    zero bit representing +1 and a one bit representing -1.  Bits other than
3580    bit 1 are garbage.  These are meant to be kept in "int"s, and casts are
3581    used to ensure the expressions are "int"s even if a and/or b might be
3582    other types.
3583 
3584    JACOBI_TWOS_U_BIT1 and JACOBI_RECIP_UU_BIT1 are used in mpn_jacobi_base
3585    and their speed is important.  Expressions are used rather than
3586    conditionals to accumulate sign changes, which effectively means XORs
3587    instead of conditional JUMPs. */
3588 
3589 /* (a/0), with a signed; is 1 if a=+/-1, 0 otherwise */
3590 #define JACOBI_S0(a)   (((a) == 1) | ((a) == -1))
3591 
3592 /* (a/0), with a unsigned; is 1 if a=+/-1, 0 otherwise */
3593 #define JACOBI_U0(a)   ((a) == 1)
3594 
3595 /* (a/0), with a given by low and size;
3596    is 1 if a=+/-1, 0 otherwise */
3597 #define JACOBI_LS0(alow,asize) \
3598   (((asize) == 1 || (asize) == -1) && (alow) == 1)
3599 
3600 /* (a/0), with a an mpz_t;
3601    fetch of low limb always valid, even if size is zero */
3602 #define JACOBI_Z0(a)   JACOBI_LS0 (PTR(a)[0], SIZ(a))
3603 
3604 /* (0/b), with b unsigned; is 1 if b=1, 0 otherwise */
3605 #define JACOBI_0U(b)   ((b) == 1)
3606 
3607 /* (0/b), with b unsigned; is 1 if b=+/-1, 0 otherwise */
3608 #define JACOBI_0S(b)   ((b) == 1 || (b) == -1)
3609 
3610 /* (0/b), with b given by low and size; is 1 if b=+/-1, 0 otherwise */
3611 #define JACOBI_0LS(blow,bsize) \
3612   (((bsize) == 1 || (bsize) == -1) && (blow) == 1)
3613 
3614 /* Convert a bit1 to +1 or -1. */
3615 #define JACOBI_BIT1_TO_PN(result_bit1) \
3616   (1 - ((int) (result_bit1) & 2))
3617 
3618 /* (2/b), with b unsigned and odd;
3619    is (-1)^((b^2-1)/8) which is 1 if b==1,7mod8 or -1 if b==3,5mod8 and
3620    hence obtained from (b>>1)^b */
3621 #define JACOBI_TWO_U_BIT1(b) \
3622   ((int) (((b) >> 1) ^ (b)))
3623 
3624 /* (2/b)^twos, with b unsigned and odd */
3625 #define JACOBI_TWOS_U_BIT1(twos, b) \
3626   ((int) ((twos) << 1) & JACOBI_TWO_U_BIT1 (b))
3627 
3628 /* (2/b)^twos, with b unsigned and odd */
3629 #define JACOBI_TWOS_U(twos, b) \
3630   (JACOBI_BIT1_TO_PN (JACOBI_TWOS_U_BIT1 (twos, b)))
3631 
3632 /* (-1/b), with b odd (signed or unsigned);
3633    is (-1)^((b-1)/2) */
3634 #define JACOBI_N1B_BIT1(b) \
3635   ((int) (b))
3636 
3637 /* (a/b) effect due to sign of a: signed/unsigned, b odd;
3638    is (-1/b) if a<0, or +1 if a>=0 */
3639 #define JACOBI_ASGN_SU_BIT1(a, b) \
3640   ((((a) < 0) << 1) & JACOBI_N1B_BIT1(b))
3641 
3642 /* (a/b) effect due to sign of b: signed/signed;
3643    is -1 if a and b both negative, +1 otherwise */
3644 #define JACOBI_BSGN_SS_BIT1(a, b) \
3645   ((((a)<0) & ((b)<0)) << 1)
3646 
3647 /* (a/b) effect due to sign of b: signed/mpz;
3648    is -1 if a and b both negative, +1 otherwise */
3649 #define JACOBI_BSGN_SZ_BIT1(a, b) \
3650   JACOBI_BSGN_SS_BIT1 (a, SIZ(b))
3651 
3652 /* (a/b) effect due to sign of b: mpz/signed;
3653    is -1 if a and b both negative, +1 otherwise */
3654 #define JACOBI_BSGN_ZS_BIT1(a, b) \
3655   JACOBI_BSGN_SZ_BIT1 (b, a)
3656 
3657 /* (a/b) reciprocity to switch to (b/a), a,b both unsigned and odd;
3658    is (-1)^((a-1)*(b-1)/4), which means +1 if either a,b==1mod4, or -1 if
3659    both a,b==3mod4, achieved in bit 1 by a&b.  No ASSERT()s about a,b odd
3660    because this is used in a couple of places with only bit 1 of a or b
3661    valid. */
3662 #define JACOBI_RECIP_UU_BIT1(a, b) \
3663   ((int) ((a) & (b)))
3664 
3665 /* Strip low zero limbs from {b_ptr,b_size} by incrementing b_ptr and
3666    decrementing b_size.  b_low should be b_ptr[0] on entry, and will be
3667    updated for the new b_ptr.  result_bit1 is updated according to the
3668    factors of 2 stripped, as per (a/2).  */
3669 #define JACOBI_STRIP_LOW_ZEROS(result_bit1, a, b_ptr, b_size, b_low)    \
3670   do {                                                                  \
3671     ASSERT ((b_size) >= 1);                                             \
3672     ASSERT ((b_low) == (b_ptr)[0]);                                     \
3673                                                                         \
3674     while (UNLIKELY ((b_low) == 0))                                     \
3675       {                                                                 \
3676         (b_size)--;                                                     \
3677         ASSERT ((b_size) >= 1);                                         \
3678         (b_ptr)++;                                                      \
3679         (b_low) = *(b_ptr);                                             \
3680                                                                         \
3681         ASSERT (((a) & 1) != 0);                                        \
3682         if ((GMP_NUMB_BITS % 2) == 1)                                   \
3683           (result_bit1) ^= JACOBI_TWO_U_BIT1(a);                        \
3684       }                                                                 \
3685   } while (0)
3686 
3687 /* Set a_rem to {a_ptr,a_size} reduced modulo b, either using mod_1 or
3688    modexact_1_odd, but in either case leaving a_rem<b.  b must be odd and
3689    unsigned.  modexact_1_odd effectively calculates -a mod b, and
3690    result_bit1 is adjusted for the factor of -1.
3691 
3692    The way mpn_modexact_1_odd sometimes bases its remainder on a_size and
3693    sometimes on a_size-1 means if GMP_NUMB_BITS is odd we can't know what
3694    factor to introduce into result_bit1, so for that case use mpn_mod_1
3695    unconditionally.
3696 
3697    FIXME: mpn_modexact_1_odd is more efficient, so some way to get it used
3698    for odd GMP_NUMB_BITS would be good.  Perhaps it could mung its result,
3699    or not skip a divide step, or something. */
3700 
3701 #define JACOBI_MOD_OR_MODEXACT_1_ODD(result_bit1, a_rem, a_ptr, a_size, b) \
3702   do {                                                                     \
3703     mp_srcptr  __a_ptr  = (a_ptr);                                         \
3704     mp_size_t  __a_size = (a_size);                                        \
3705     mp_limb_t  __b      = (b);                                             \
3706                                                                            \
3707     ASSERT (__a_size >= 1);                                                \
3708     ASSERT (__b & 1);                                                      \
3709                                                                            \
3710     if ((GMP_NUMB_BITS % 2) != 0                                           \
3711         || ABOVE_THRESHOLD (__a_size, BMOD_1_TO_MOD_1_THRESHOLD))          \
3712       {                                                                    \
3713         (a_rem) = mpn_mod_1 (__a_ptr, __a_size, __b);                      \
3714       }                                                                    \
3715     else                                                                   \
3716       {                                                                    \
3717         (result_bit1) ^= JACOBI_N1B_BIT1 (__b);                            \
3718         (a_rem) = mpn_modexact_1_odd (__a_ptr, __a_size, __b);             \
3719       }                                                                    \
3720   } while (0)
3721 
3722 /* Matrix multiplication */
3723 #define   mpn_matrix22_mul __MPN(matrix22_mul)
3724 __GMP_DECLSPEC void      mpn_matrix22_mul __GMP_PROTO ((mp_ptr, mp_ptr, mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_srcptr, mp_srcptr, mp_srcptr, mp_size_t, mp_ptr));
3725 #define   mpn_matrix22_mul_strassen __MPN(matrix22_mul_strassen)
3726 __GMP_DECLSPEC void      mpn_matrix22_mul_strassen __GMP_PROTO ((mp_ptr, mp_ptr, mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_srcptr, mp_srcptr, mp_srcptr, mp_size_t, mp_ptr));
3727 #define   mpn_matrix22_mul_itch __MPN(matrix22_mul_itch)
3728 __GMP_DECLSPEC mp_size_t mpn_matrix22_mul_itch __GMP_PROTO ((mp_size_t, mp_size_t));
3729 
3730 #ifndef MATRIX22_STRASSEN_THRESHOLD
3731 #define MATRIX22_STRASSEN_THRESHOLD 30
3732 #endif
3733 
3734 /* HGCD definitions */
3735 
3736 /* Extract one numb, shifting count bits left
3737     ________  ________
3738    |___xh___||___xl___|
3739 	  |____r____|
3740    >count <
3741 
3742    The count includes any nail bits, so it should work fine if count
3743    is computed using count_leading_zeros. If GMP_NAIL_BITS > 0, all of
3744    xh, xl and r include nail bits. Must have 0 < count < GMP_LIMB_BITS.
3745 
3746    FIXME: Omit masking with GMP_NUMB_MASK, and let callers do that for
3747    those calls where the count high bits of xh may be non-zero.
3748 */
3749 
3750 #define MPN_EXTRACT_NUMB(count, xh, xl)				\
3751   ((((xh) << ((count) - GMP_NAIL_BITS)) & GMP_NUMB_MASK) |	\
3752    ((xl) >> (GMP_LIMB_BITS - (count))))
3753 
3754 
3755 /* The matrix non-negative M = (u, u'; v,v') keeps track of the
3756    reduction (a;b) = M (alpha; beta) where alpha, beta are smaller
3757    than a, b. The determinant must always be one, so that M has an
3758    inverse (v', -u'; -v, u). Elements always fit in GMP_NUMB_BITS - 1
3759    bits. */
3760 struct hgcd_matrix1
3761 {
3762   mp_limb_t u[2][2];
3763 };
3764 
3765 #define mpn_hgcd2 __MPN (hgcd2)
3766 __GMP_DECLSPEC int mpn_hgcd2 __GMP_PROTO ((mp_limb_t, mp_limb_t, mp_limb_t, mp_limb_t,	struct hgcd_matrix1 *));
3767 
3768 #define mpn_hgcd_mul_matrix1_vector __MPN (hgcd_mul_matrix1_vector)
3769 __GMP_DECLSPEC mp_size_t mpn_hgcd_mul_matrix1_vector __GMP_PROTO ((const struct hgcd_matrix1 *, mp_ptr, mp_srcptr, mp_ptr, mp_size_t));
3770 
3771 #define mpn_hgcd_mul_matrix1_inverse_vector __MPN (hgcd_mul_matrix1_inverse_vector)
3772 __GMP_DECLSPEC mp_size_t mpn_hgcd_mul_matrix1_inverse_vector __GMP_PROTO ((const struct hgcd_matrix1 *, mp_ptr, mp_srcptr, mp_ptr, mp_size_t));
3773 
3774 struct hgcd_matrix
3775 {
3776   mp_size_t alloc;		/* for sanity checking only */
3777   mp_size_t n;
3778   mp_ptr p[2][2];
3779 };
3780 
3781 #define MPN_HGCD_MATRIX_INIT_ITCH(n) (4 * ((n+1)/2 + 1))
3782 
3783 #define mpn_hgcd_matrix_init __MPN (hgcd_matrix_init)
3784 __GMP_DECLSPEC void mpn_hgcd_matrix_init __GMP_PROTO ((struct hgcd_matrix *, mp_size_t, mp_ptr));
3785 
3786 #define mpn_hgcd_matrix_mul __MPN (hgcd_matrix_mul)
3787 __GMP_DECLSPEC void mpn_hgcd_matrix_mul __GMP_PROTO ((struct hgcd_matrix *, const struct hgcd_matrix *, mp_ptr));
3788 
3789 #define mpn_hgcd_matrix_adjust __MPN (hgcd_matrix_adjust)
3790 __GMP_DECLSPEC mp_size_t mpn_hgcd_matrix_adjust __GMP_PROTO ((struct hgcd_matrix *, mp_size_t, mp_ptr, mp_ptr, mp_size_t, mp_ptr));
3791 
3792 #define mpn_hgcd_itch __MPN (hgcd_itch)
3793 __GMP_DECLSPEC mp_size_t mpn_hgcd_itch __GMP_PROTO ((mp_size_t));
3794 
3795 #define mpn_hgcd __MPN (hgcd)
3796 __GMP_DECLSPEC mp_size_t mpn_hgcd __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, struct hgcd_matrix *, mp_ptr));
3797 
3798 #define MPN_HGCD_LEHMER_ITCH(n) (n)
3799 
3800 #define mpn_hgcd_lehmer __MPN (hgcd_lehmer)
3801 __GMP_DECLSPEC mp_size_t mpn_hgcd_lehmer __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, struct hgcd_matrix *, mp_ptr));
3802 
3803 /* Needs storage for the quotient */
3804 #define MPN_GCD_SUBDIV_STEP_ITCH(n) (n)
3805 
3806 #define mpn_gcd_subdiv_step __MPN(gcd_subdiv_step)
3807 __GMP_DECLSPEC mp_size_t mpn_gcd_subdiv_step __GMP_PROTO ((mp_ptr, mp_size_t *, mp_ptr, mp_ptr, mp_size_t, mp_ptr));
3808 
3809 #define MPN_GCD_LEHMER_N_ITCH(n) (n)
3810 
3811 #define mpn_gcd_lehmer_n __MPN(gcd_lehmer_n)
3812 __GMP_DECLSPEC mp_size_t mpn_gcd_lehmer_n __GMP_PROTO ((mp_ptr, mp_ptr, mp_ptr, mp_size_t, mp_ptr));
3813 
3814 #define mpn_gcdext_subdiv_step __MPN(gcdext_subdiv_step)
3815 __GMP_DECLSPEC mp_size_t mpn_gcdext_subdiv_step __GMP_PROTO ((mp_ptr, mp_size_t *, mp_ptr, mp_size_t *, mp_ptr, mp_ptr, mp_size_t, mp_ptr, mp_ptr, mp_size_t *, mp_ptr, mp_ptr));
3816 
3817 #define MPN_GCDEXT_LEHMER_N_ITCH(n) (4*(n) + 3)
3818 
3819 #define mpn_gcdext_lehmer_n __MPN(gcdext_lehmer_n)
3820 __GMP_DECLSPEC mp_size_t mpn_gcdext_lehmer_n __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t *, mp_ptr, mp_ptr, mp_size_t, mp_ptr));
3821 
3822 /* 4*(an + 1) + 4*(bn + 1) + an */
3823 #define MPN_GCDEXT_LEHMER_ITCH(an, bn) (5*(an) + 4*(bn) + 8)
3824 
3825 #ifndef HGCD_THRESHOLD
3826 #define HGCD_THRESHOLD 400
3827 #endif
3828 
3829 #ifndef GCD_DC_THRESHOLD
3830 #define GCD_DC_THRESHOLD 1000
3831 #endif
3832 
3833 #ifndef GCDEXT_DC_THRESHOLD
3834 #define GCDEXT_DC_THRESHOLD 600
3835 #endif
3836 
3837 /* Definitions for mpn_set_str and mpn_get_str */
3838 struct powers
3839 {
3840   mp_ptr p;			/* actual power value */
3841   mp_size_t n;			/* # of limbs at p */
3842   mp_size_t shift;		/* weight of lowest limb, in limb base B */
3843   size_t digits_in_base;	/* number of corresponding digits */
3844   int base;
3845 };
3846 typedef struct powers powers_t;
3847 #define mpn_dc_set_str_powtab_alloc(n) ((n) + GMP_LIMB_BITS)
3848 #define mpn_dc_set_str_itch(n) ((n) + GMP_LIMB_BITS)
3849 #define mpn_dc_get_str_powtab_alloc(n) ((n) + 2 * GMP_LIMB_BITS)
3850 #define mpn_dc_get_str_itch(n) ((n) + GMP_LIMB_BITS)
3851 
3852 #define   mpn_dc_set_str __MPN(dc_set_str)
3853 __GMP_DECLSPEC mp_size_t mpn_dc_set_str __GMP_PROTO ((mp_ptr, const unsigned char *, size_t, const powers_t *, mp_ptr));
3854 #define   mpn_bc_set_str __MPN(bc_set_str)
3855 __GMP_DECLSPEC mp_size_t mpn_bc_set_str __GMP_PROTO ((mp_ptr, const unsigned char *, size_t, int));
3856 #define   mpn_set_str_compute_powtab __MPN(set_str_compute_powtab)
3857 __GMP_DECLSPEC void      mpn_set_str_compute_powtab __GMP_PROTO ((powers_t *, mp_ptr, mp_size_t, int));
3858 
3859 
3860 /* __GMPF_BITS_TO_PREC applies a minimum 53 bits, rounds upwards to a whole
3861    limb and adds an extra limb.  __GMPF_PREC_TO_BITS drops that extra limb,
3862    hence giving back the user's size in bits rounded up.  Notice that
3863    converting prec->bits->prec gives an unchanged value.  */
3864 #define __GMPF_BITS_TO_PREC(n)						\
3865   ((mp_size_t) ((__GMP_MAX (53, n) + 2 * GMP_NUMB_BITS - 1) / GMP_NUMB_BITS))
3866 #define __GMPF_PREC_TO_BITS(n) \
3867   ((mp_bitcnt_t) (n) * GMP_NUMB_BITS - GMP_NUMB_BITS)
3868 
3869 __GMP_DECLSPEC extern mp_size_t __gmp_default_fp_limb_precision;
3870 
3871 
3872 /* Set n to the number of significant digits an mpf of the given _mp_prec
3873    field, in the given base.  This is a rounded up value, designed to ensure
3874    there's enough digits to reproduce all the guaranteed part of the value.
3875 
3876    There are prec many limbs, but the high might be only "1" so forget it
3877    and just count prec-1 limbs into chars.  +1 rounds that upwards, and a
3878    further +1 is because the limbs usually won't fall on digit boundaries.
3879 
3880    FIXME: If base is a power of 2 and the bits per digit divides
3881    GMP_LIMB_BITS then the +2 is unnecessary.  This happens always for
3882    base==2, and in base==16 with the current 32 or 64 bit limb sizes. */
3883 
3884 #define MPF_SIGNIFICANT_DIGITS(n, base, prec)                           \
3885   do {                                                                  \
3886     ASSERT (base >= 2 && base < numberof (mp_bases));                   \
3887     (n) = 2 + (size_t) ((((size_t) (prec) - 1) * GMP_NUMB_BITS)         \
3888                         * mp_bases[(base)].chars_per_bit_exactly);      \
3889   } while (0)
3890 
3891 
3892 /* Decimal point string, from the current C locale.  Needs <langinfo.h> for
3893    nl_langinfo and constants, preferably with _GNU_SOURCE defined to get
3894    DECIMAL_POINT from glibc, and needs <locale.h> for localeconv, each under
3895    their respective #if HAVE_FOO_H.
3896 
3897    GLIBC recommends nl_langinfo because getting only one facet can be
3898    faster, apparently. */
3899 
3900 /* DECIMAL_POINT seems to need _GNU_SOURCE defined to get it from glibc. */
3901 #if HAVE_NL_LANGINFO && defined (DECIMAL_POINT)
3902 #define GMP_DECIMAL_POINT  (nl_langinfo (DECIMAL_POINT))
3903 #endif
3904 /* RADIXCHAR is deprecated, still in unix98 or some such. */
3905 #if HAVE_NL_LANGINFO && defined (RADIXCHAR) && ! defined (GMP_DECIMAL_POINT)
3906 #define GMP_DECIMAL_POINT  (nl_langinfo (RADIXCHAR))
3907 #endif
3908 /* localeconv is slower since it returns all locale stuff */
3909 #if HAVE_LOCALECONV && ! defined (GMP_DECIMAL_POINT)
3910 #define GMP_DECIMAL_POINT  (localeconv()->decimal_point)
3911 #endif
3912 #if ! defined (GMP_DECIMAL_POINT)
3913 #define GMP_DECIMAL_POINT  (".")
3914 #endif
3915 
3916 
3917 #define DOPRNT_CONV_FIXED        1
3918 #define DOPRNT_CONV_SCIENTIFIC   2
3919 #define DOPRNT_CONV_GENERAL      3
3920 
3921 #define DOPRNT_JUSTIFY_NONE      0
3922 #define DOPRNT_JUSTIFY_LEFT      1
3923 #define DOPRNT_JUSTIFY_RIGHT     2
3924 #define DOPRNT_JUSTIFY_INTERNAL  3
3925 
3926 #define DOPRNT_SHOWBASE_YES      1
3927 #define DOPRNT_SHOWBASE_NO       2
3928 #define DOPRNT_SHOWBASE_NONZERO  3
3929 
3930 struct doprnt_params_t {
3931   int         base;          /* negative for upper case */
3932   int         conv;          /* choices above */
3933   const char  *expfmt;       /* exponent format */
3934   int         exptimes4;     /* exponent multiply by 4 */
3935   char        fill;          /* character */
3936   int         justify;       /* choices above */
3937   int         prec;          /* prec field, or -1 for all digits */
3938   int         showbase;      /* choices above */
3939   int         showpoint;     /* if radix point always shown */
3940   int         showtrailing;  /* if trailing zeros wanted */
3941   char        sign;          /* '+', ' ', or '\0' */
3942   int         width;         /* width field */
3943 };
3944 
3945 #if _GMP_H_HAVE_VA_LIST
3946 
3947 __GMP_DECLSPEC typedef int (*doprnt_format_t) __GMP_PROTO ((void *, const char *, va_list));
3948 __GMP_DECLSPEC typedef int (*doprnt_memory_t) __GMP_PROTO ((void *, const char *, size_t));
3949 __GMP_DECLSPEC typedef int (*doprnt_reps_t)   __GMP_PROTO ((void *, int, int));
3950 __GMP_DECLSPEC typedef int (*doprnt_final_t)  __GMP_PROTO ((void *));
3951 
3952 struct doprnt_funs_t {
3953   doprnt_format_t  format;
3954   doprnt_memory_t  memory;
3955   doprnt_reps_t    reps;
3956   doprnt_final_t   final;   /* NULL if not required */
3957 };
3958 
3959 extern const struct doprnt_funs_t  __gmp_fprintf_funs;
3960 extern const struct doprnt_funs_t  __gmp_sprintf_funs;
3961 extern const struct doprnt_funs_t  __gmp_snprintf_funs;
3962 extern const struct doprnt_funs_t  __gmp_obstack_printf_funs;
3963 extern const struct doprnt_funs_t  __gmp_ostream_funs;
3964 
3965 /* "buf" is a __gmp_allocate_func block of "alloc" many bytes.  The first
3966    "size" of these have been written.  "alloc > size" is maintained, so
3967    there's room to store a '\0' at the end.  "result" is where the
3968    application wants the final block pointer.  */
3969 struct gmp_asprintf_t {
3970   char    **result;
3971   char    *buf;
3972   size_t  size;
3973   size_t  alloc;
3974 };
3975 
3976 #define GMP_ASPRINTF_T_INIT(d, output)                          \
3977   do {                                                          \
3978     (d).result = (output);                                      \
3979     (d).alloc = 256;                                            \
3980     (d).buf = (char *) (*__gmp_allocate_func) ((d).alloc);      \
3981     (d).size = 0;                                               \
3982   } while (0)
3983 
3984 /* If a realloc is necessary, use twice the size actually required, so as to
3985    avoid repeated small reallocs.  */
3986 #define GMP_ASPRINTF_T_NEED(d, n)                                       \
3987   do {                                                                  \
3988     size_t  alloc, newsize, newalloc;                                   \
3989     ASSERT ((d)->alloc >= (d)->size + 1);                               \
3990                                                                         \
3991     alloc = (d)->alloc;                                                 \
3992     newsize = (d)->size + (n);                                          \
3993     if (alloc <= newsize)                                               \
3994       {                                                                 \
3995         newalloc = 2*newsize;                                           \
3996         (d)->alloc = newalloc;                                          \
3997         (d)->buf = __GMP_REALLOCATE_FUNC_TYPE ((d)->buf,                \
3998                                                alloc, newalloc, char);  \
3999       }                                                                 \
4000   } while (0)
4001 
4002 __GMP_DECLSPEC int __gmp_asprintf_memory __GMP_PROTO ((struct gmp_asprintf_t *, const char *, size_t));
4003 __GMP_DECLSPEC int __gmp_asprintf_reps __GMP_PROTO ((struct gmp_asprintf_t *, int, int));
4004 __GMP_DECLSPEC int __gmp_asprintf_final __GMP_PROTO ((struct gmp_asprintf_t *));
4005 
4006 /* buf is where to write the next output, and size is how much space is left
4007    there.  If the application passed size==0 then that's what we'll have
4008    here, and nothing at all should be written.  */
4009 struct gmp_snprintf_t {
4010   char    *buf;
4011   size_t  size;
4012 };
4013 
4014 /* Add the bytes printed by the call to the total retval, or bail out on an
4015    error.  */
4016 #define DOPRNT_ACCUMULATE(call) \
4017   do {                          \
4018     int  __ret;                 \
4019     __ret = call;               \
4020     if (__ret == -1)            \
4021       goto error;               \
4022     retval += __ret;            \
4023   } while (0)
4024 #define DOPRNT_ACCUMULATE_FUN(fun, params)      \
4025   do {                                          \
4026     ASSERT ((fun) != NULL);                     \
4027     DOPRNT_ACCUMULATE ((*(fun)) params);        \
4028   } while (0)
4029 
4030 #define DOPRNT_FORMAT(fmt, ap)                          \
4031   DOPRNT_ACCUMULATE_FUN (funs->format, (data, fmt, ap))
4032 #define DOPRNT_MEMORY(ptr, len)                                 \
4033   DOPRNT_ACCUMULATE_FUN (funs->memory, (data, ptr, len))
4034 #define DOPRNT_REPS(c, n)                               \
4035   DOPRNT_ACCUMULATE_FUN (funs->reps, (data, c, n))
4036 
4037 #define DOPRNT_STRING(str)      DOPRNT_MEMORY (str, strlen (str))
4038 
4039 #define DOPRNT_REPS_MAYBE(c, n) \
4040   do {                          \
4041     if ((n) != 0)               \
4042       DOPRNT_REPS (c, n);       \
4043   } while (0)
4044 #define DOPRNT_MEMORY_MAYBE(ptr, len)   \
4045   do {                                  \
4046     if ((len) != 0)                     \
4047       DOPRNT_MEMORY (ptr, len);         \
4048   } while (0)
4049 
4050 __GMP_DECLSPEC int __gmp_doprnt __GMP_PROTO ((const struct doprnt_funs_t *, void *, const char *, va_list));
4051 __GMP_DECLSPEC int __gmp_doprnt_integer __GMP_PROTO ((const struct doprnt_funs_t *, void *, const struct doprnt_params_t *, const char *));
4052 
4053 #define __gmp_doprnt_mpf __gmp_doprnt_mpf2
4054 __GMP_DECLSPEC int __gmp_doprnt_mpf __GMP_PROTO ((const struct doprnt_funs_t *, void *, const struct doprnt_params_t *, const char *, mpf_srcptr));
4055 
4056 __GMP_DECLSPEC int __gmp_replacement_vsnprintf __GMP_PROTO ((char *, size_t, const char *, va_list));
4057 #endif /* _GMP_H_HAVE_VA_LIST */
4058 
4059 
4060 typedef int (*gmp_doscan_scan_t)  __GMP_PROTO ((void *, const char *, ...));
4061 typedef void *(*gmp_doscan_step_t) __GMP_PROTO ((void *, int));
4062 typedef int (*gmp_doscan_get_t)   __GMP_PROTO ((void *));
4063 typedef int (*gmp_doscan_unget_t) __GMP_PROTO ((int, void *));
4064 
4065 struct gmp_doscan_funs_t {
4066   gmp_doscan_scan_t   scan;
4067   gmp_doscan_step_t   step;
4068   gmp_doscan_get_t    get;
4069   gmp_doscan_unget_t  unget;
4070 };
4071 extern const struct gmp_doscan_funs_t  __gmp_fscanf_funs;
4072 extern const struct gmp_doscan_funs_t  __gmp_sscanf_funs;
4073 
4074 #if _GMP_H_HAVE_VA_LIST
4075 __GMP_DECLSPEC int __gmp_doscan __GMP_PROTO ((const struct gmp_doscan_funs_t *, void *, const char *, va_list));
4076 #endif
4077 
4078 
4079 /* For testing and debugging.  */
4080 #define MPZ_CHECK_FORMAT(z)					\
4081   do {                                                          \
4082     ASSERT_ALWAYS (SIZ(z) == 0 || PTR(z)[ABSIZ(z) - 1] != 0);	\
4083     ASSERT_ALWAYS (ALLOC(z) >= ABSIZ(z));			\
4084     ASSERT_ALWAYS_MPN (PTR(z), ABSIZ(z));                       \
4085   } while (0)
4086 
4087 #define MPQ_CHECK_FORMAT(q)                             \
4088   do {                                                  \
4089     MPZ_CHECK_FORMAT (mpq_numref (q));                  \
4090     MPZ_CHECK_FORMAT (mpq_denref (q));                  \
4091     ASSERT_ALWAYS (SIZ(mpq_denref(q)) >= 1);            \
4092                                                         \
4093     if (SIZ(mpq_numref(q)) == 0)                        \
4094       {                                                 \
4095         /* should have zero as 0/1 */                   \
4096         ASSERT_ALWAYS (SIZ(mpq_denref(q)) == 1          \
4097                        && PTR(mpq_denref(q))[0] == 1);  \
4098       }                                                 \
4099     else                                                \
4100       {                                                 \
4101         /* should have no common factors */             \
4102         mpz_t  g;                                       \
4103         mpz_init (g);                                   \
4104         mpz_gcd (g, mpq_numref(q), mpq_denref(q));      \
4105         ASSERT_ALWAYS (mpz_cmp_ui (g, 1) == 0);         \
4106         mpz_clear (g);                                  \
4107       }                                                 \
4108   } while (0)
4109 
4110 #define MPF_CHECK_FORMAT(f)                             \
4111   do {                                                  \
4112     ASSERT_ALWAYS (PREC(f) >= __GMPF_BITS_TO_PREC(53)); \
4113     ASSERT_ALWAYS (ABSIZ(f) <= PREC(f)+1);              \
4114     if (SIZ(f) == 0)                                    \
4115       ASSERT_ALWAYS (EXP(f) == 0);                      \
4116     if (SIZ(f) != 0)                                    \
4117       ASSERT_ALWAYS (PTR(f)[ABSIZ(f) - 1] != 0);        \
4118   } while (0)
4119 
4120 
4121 #define MPZ_PROVOKE_REALLOC(z)					\
4122   do { ALLOC(z) = ABSIZ(z); } while (0)
4123 
4124 
4125 /* Enhancement: The "mod" and "gcd_1" functions below could have
4126    __GMP_ATTRIBUTE_PURE, but currently (gcc 3.3) that's not supported on
4127    function pointers, only actual functions.  It probably doesn't make much
4128    difference to the gmp code, since hopefully we arrange calls so there's
4129    no great need for the compiler to move things around.  */
4130 
4131 #if WANT_FAT_BINARY && (HAVE_HOST_CPU_FAMILY_x86 || HAVE_HOST_CPU_FAMILY_x86_64)
4132 /* NOTE: The function pointers in this struct are also in CPUVEC_FUNCS_LIST
4133    in mpn/x86/x86-defs.m4.  Be sure to update that when changing here.  */
4134 struct cpuvec_t {
4135   DECL_add_n           ((*add_n));
4136   DECL_addmul_1        ((*addmul_1));
4137   DECL_copyd           ((*copyd));
4138   DECL_copyi           ((*copyi));
4139   DECL_divexact_1      ((*divexact_1));
4140   DECL_divexact_by3c   ((*divexact_by3c));
4141   DECL_divrem_1        ((*divrem_1));
4142   DECL_gcd_1           ((*gcd_1));
4143   DECL_lshift          ((*lshift));
4144   DECL_mod_1           ((*mod_1));
4145   DECL_mod_34lsub1     ((*mod_34lsub1));
4146   DECL_modexact_1c_odd ((*modexact_1c_odd));
4147   DECL_mul_1           ((*mul_1));
4148   DECL_mul_basecase    ((*mul_basecase));
4149   DECL_preinv_divrem_1 ((*preinv_divrem_1));
4150   DECL_preinv_mod_1    ((*preinv_mod_1));
4151   DECL_rshift          ((*rshift));
4152   DECL_sqr_basecase    ((*sqr_basecase));
4153   DECL_sub_n           ((*sub_n));
4154   DECL_submul_1        ((*submul_1));
4155   int                  initialized;
4156   mp_size_t            mul_toom22_threshold;
4157   mp_size_t            mul_toom33_threshold;
4158   mp_size_t            sqr_toom2_threshold;
4159   mp_size_t            sqr_toom3_threshold;
4160 };
4161 __GMP_DECLSPEC extern struct cpuvec_t __gmpn_cpuvec;
4162 #endif /* x86 fat binary */
4163 
4164 __GMP_DECLSPEC void __gmpn_cpuvec_init __GMP_PROTO ((void));
4165 
4166 /* Get a threshold "field" from __gmpn_cpuvec, running __gmpn_cpuvec_init()
4167    if that hasn't yet been done (to establish the right values).  */
4168 #define CPUVEC_THRESHOLD(field)                                               \
4169   ((LIKELY (__gmpn_cpuvec.initialized) ? 0 : (__gmpn_cpuvec_init (), 0)),     \
4170    __gmpn_cpuvec.field)
4171 
4172 
4173 #if HAVE_NATIVE_mpn_add_nc
4174 #define mpn_add_nc __MPN(add_nc)
4175 __GMP_DECLSPEC mp_limb_t mpn_add_nc __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t));
4176 #else
4177 static inline
4178 mp_limb_t
mpn_add_nc(mp_ptr rp,mp_srcptr up,mp_srcptr vp,mp_size_t n,mp_limb_t ci)4179 mpn_add_nc (mp_ptr rp, mp_srcptr up, mp_srcptr vp, mp_size_t n, mp_limb_t ci)
4180 {
4181   mp_limb_t co;
4182   co = mpn_add_n (rp, up, vp, n);
4183   co += mpn_add_1 (rp, rp, n, ci);
4184   return co;
4185 }
4186 #endif
4187 
4188 #if HAVE_NATIVE_mpn_sub_nc
4189 #define mpn_sub_nc __MPN(sub_nc)
4190 __GMP_DECLSPEC mp_limb_t mpn_sub_nc __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t));
4191 #else
4192 static inline mp_limb_t
mpn_sub_nc(mp_ptr rp,mp_srcptr up,mp_srcptr vp,mp_size_t n,mp_limb_t ci)4193 mpn_sub_nc (mp_ptr rp, mp_srcptr up, mp_srcptr vp, mp_size_t n, mp_limb_t ci)
4194 {
4195   mp_limb_t co;
4196   co = mpn_sub_n (rp, up, vp, n);
4197   co += mpn_sub_1 (rp, rp, n, ci);
4198   return co;
4199 }
4200 #endif
4201 
4202 static inline int
mpn_zero_p(mp_srcptr ap,mp_size_t n)4203 mpn_zero_p (mp_srcptr ap, mp_size_t n)
4204 {
4205   mp_size_t i;
4206   for (i = n - 1; i >= 0; i--)
4207     {
4208       if (ap[i] != 0)
4209 	return 0;
4210     }
4211   return 1;
4212 }
4213 
4214 #if TUNE_PROGRAM_BUILD
4215 /* Some extras wanted when recompiling some .c files for use by the tune
4216    program.  Not part of a normal build.
4217 
4218    It's necessary to keep these thresholds as #defines (just to an
4219    identically named variable), since various defaults are established based
4220    on #ifdef in the .c files.  For some this is not so (the defaults are
4221    instead established above), but all are done this way for consistency. */
4222 
4223 #undef	MUL_TOOM22_THRESHOLD
4224 #define MUL_TOOM22_THRESHOLD		mul_toom22_threshold
4225 extern mp_size_t			mul_toom22_threshold;
4226 
4227 #undef	MUL_TOOM33_THRESHOLD
4228 #define MUL_TOOM33_THRESHOLD		mul_toom33_threshold
4229 extern mp_size_t			mul_toom33_threshold;
4230 
4231 #undef	MUL_TOOM44_THRESHOLD
4232 #define MUL_TOOM44_THRESHOLD		mul_toom44_threshold
4233 extern mp_size_t			mul_toom44_threshold;
4234 
4235 #undef	MUL_TOOM6H_THRESHOLD
4236 #define MUL_TOOM6H_THRESHOLD		mul_toom6h_threshold
4237 extern mp_size_t			mul_toom6h_threshold;
4238 
4239 #undef	MUL_TOOM8H_THRESHOLD
4240 #define MUL_TOOM8H_THRESHOLD		mul_toom8h_threshold
4241 extern mp_size_t			mul_toom8h_threshold;
4242 
4243 #undef	MUL_TOOM32_TO_TOOM43_THRESHOLD
4244 #define MUL_TOOM32_TO_TOOM43_THRESHOLD	mul_toom32_to_toom43_threshold
4245 extern mp_size_t			mul_toom32_to_toom43_threshold;
4246 
4247 #undef	MUL_TOOM32_TO_TOOM53_THRESHOLD
4248 #define MUL_TOOM32_TO_TOOM53_THRESHOLD	mul_toom32_to_toom53_threshold
4249 extern mp_size_t			mul_toom32_to_toom53_threshold;
4250 
4251 #undef	MUL_TOOM42_TO_TOOM53_THRESHOLD
4252 #define MUL_TOOM42_TO_TOOM53_THRESHOLD	mul_toom42_to_toom53_threshold
4253 extern mp_size_t			mul_toom42_to_toom53_threshold;
4254 
4255 #undef	MUL_TOOM42_TO_TOOM63_THRESHOLD
4256 #define MUL_TOOM42_TO_TOOM63_THRESHOLD	mul_toom42_to_toom63_threshold
4257 extern mp_size_t			mul_toom42_to_toom63_threshold;
4258 
4259 #undef	MUL_FFT_THRESHOLD
4260 #define MUL_FFT_THRESHOLD		mul_fft_threshold
4261 extern mp_size_t			mul_fft_threshold;
4262 
4263 #undef	MUL_FFT_MODF_THRESHOLD
4264 #define MUL_FFT_MODF_THRESHOLD		mul_fft_modf_threshold
4265 extern mp_size_t			mul_fft_modf_threshold;
4266 
4267 #undef	MUL_FFT_TABLE
4268 #define MUL_FFT_TABLE			{ 0 }
4269 
4270 #undef	MUL_FFT_TABLE3
4271 #define MUL_FFT_TABLE3			{ {0,0} }
4272 
4273 /* A native mpn_sqr_basecase is not tuned and SQR_BASECASE_THRESHOLD should
4274    remain as zero (always use it). */
4275 #if ! HAVE_NATIVE_mpn_sqr_basecase
4276 #undef	SQR_BASECASE_THRESHOLD
4277 #define SQR_BASECASE_THRESHOLD		sqr_basecase_threshold
4278 extern mp_size_t			sqr_basecase_threshold;
4279 #endif
4280 
4281 #if TUNE_PROGRAM_BUILD_SQR
4282 #undef	SQR_TOOM2_THRESHOLD
4283 #define SQR_TOOM2_THRESHOLD		SQR_TOOM2_MAX_GENERIC
4284 #else
4285 #undef	SQR_TOOM2_THRESHOLD
4286 #define SQR_TOOM2_THRESHOLD		sqr_toom2_threshold
4287 extern mp_size_t			sqr_toom2_threshold;
4288 #endif
4289 
4290 #undef	SQR_TOOM3_THRESHOLD
4291 #define SQR_TOOM3_THRESHOLD		sqr_toom3_threshold
4292 extern mp_size_t			sqr_toom3_threshold;
4293 
4294 #undef	SQR_TOOM4_THRESHOLD
4295 #define SQR_TOOM4_THRESHOLD		sqr_toom4_threshold
4296 extern mp_size_t			sqr_toom4_threshold;
4297 
4298 #undef	SQR_TOOM6_THRESHOLD
4299 #define SQR_TOOM6_THRESHOLD		sqr_toom6_threshold
4300 extern mp_size_t			sqr_toom6_threshold;
4301 
4302 #undef	SQR_TOOM8_THRESHOLD
4303 #define SQR_TOOM8_THRESHOLD		sqr_toom8_threshold
4304 extern mp_size_t			sqr_toom8_threshold;
4305 
4306 #undef  SQR_FFT_THRESHOLD
4307 #define SQR_FFT_THRESHOLD		sqr_fft_threshold
4308 extern mp_size_t			sqr_fft_threshold;
4309 
4310 #undef  SQR_FFT_MODF_THRESHOLD
4311 #define SQR_FFT_MODF_THRESHOLD		sqr_fft_modf_threshold
4312 extern mp_size_t			sqr_fft_modf_threshold;
4313 
4314 #undef	SQR_FFT_TABLE
4315 #define SQR_FFT_TABLE			{ 0 }
4316 
4317 #undef	SQR_FFT_TABLE3
4318 #define SQR_FFT_TABLE3			{ {0,0} }
4319 
4320 #undef	MULLO_BASECASE_THRESHOLD
4321 #define MULLO_BASECASE_THRESHOLD	mullo_basecase_threshold
4322 extern mp_size_t			mullo_basecase_threshold;
4323 
4324 #undef	MULLO_DC_THRESHOLD
4325 #define MULLO_DC_THRESHOLD		mullo_dc_threshold
4326 extern mp_size_t			mullo_dc_threshold;
4327 
4328 #undef	MULLO_MUL_N_THRESHOLD
4329 #define MULLO_MUL_N_THRESHOLD		mullo_mul_n_threshold
4330 extern mp_size_t			mullo_mul_n_threshold;
4331 
4332 #undef	DC_DIV_QR_THRESHOLD
4333 #define DC_DIV_QR_THRESHOLD		dc_div_qr_threshold
4334 extern mp_size_t			dc_div_qr_threshold;
4335 
4336 #undef	DC_DIVAPPR_Q_THRESHOLD
4337 #define DC_DIVAPPR_Q_THRESHOLD		dc_divappr_q_threshold
4338 extern mp_size_t			dc_divappr_q_threshold;
4339 
4340 #undef	DC_BDIV_Q_THRESHOLD
4341 #define DC_BDIV_Q_THRESHOLD		dc_bdiv_q_threshold
4342 extern mp_size_t			dc_bdiv_q_threshold;
4343 
4344 #undef	DC_BDIV_QR_THRESHOLD
4345 #define DC_BDIV_QR_THRESHOLD		dc_bdiv_qr_threshold
4346 extern mp_size_t			dc_bdiv_qr_threshold;
4347 
4348 #undef	MU_DIV_QR_THRESHOLD
4349 #define MU_DIV_QR_THRESHOLD		mu_div_qr_threshold
4350 extern mp_size_t			mu_div_qr_threshold;
4351 
4352 #undef	MU_DIVAPPR_Q_THRESHOLD
4353 #define MU_DIVAPPR_Q_THRESHOLD		mu_divappr_q_threshold
4354 extern mp_size_t			mu_divappr_q_threshold;
4355 
4356 #undef	MUPI_DIV_QR_THRESHOLD
4357 #define MUPI_DIV_QR_THRESHOLD		mupi_div_qr_threshold
4358 extern mp_size_t			mupi_div_qr_threshold;
4359 
4360 #undef	MU_BDIV_QR_THRESHOLD
4361 #define MU_BDIV_QR_THRESHOLD		mu_bdiv_qr_threshold
4362 extern mp_size_t			mu_bdiv_qr_threshold;
4363 
4364 #undef	MU_BDIV_Q_THRESHOLD
4365 #define MU_BDIV_Q_THRESHOLD		mu_bdiv_q_threshold
4366 extern mp_size_t			mu_bdiv_q_threshold;
4367 
4368 #undef	INV_MULMOD_BNM1_THRESHOLD
4369 #define INV_MULMOD_BNM1_THRESHOLD	inv_mulmod_bnm1_threshold
4370 extern mp_size_t			inv_mulmod_bnm1_threshold;
4371 
4372 #undef	INV_NEWTON_THRESHOLD
4373 #define INV_NEWTON_THRESHOLD		inv_newton_threshold
4374 extern mp_size_t			inv_newton_threshold;
4375 
4376 #undef	INV_APPR_THRESHOLD
4377 #define INV_APPR_THRESHOLD		inv_appr_threshold
4378 extern mp_size_t			inv_appr_threshold;
4379 
4380 #undef	BINV_NEWTON_THRESHOLD
4381 #define BINV_NEWTON_THRESHOLD		binv_newton_threshold
4382 extern mp_size_t			binv_newton_threshold;
4383 
4384 #undef	REDC_1_TO_REDC_2_THRESHOLD
4385 #define REDC_1_TO_REDC_2_THRESHOLD	redc_1_to_redc_2_threshold
4386 extern mp_size_t			redc_1_to_redc_2_threshold;
4387 
4388 #undef	REDC_2_TO_REDC_N_THRESHOLD
4389 #define REDC_2_TO_REDC_N_THRESHOLD	redc_2_to_redc_n_threshold
4390 extern mp_size_t			redc_2_to_redc_n_threshold;
4391 
4392 #undef	REDC_1_TO_REDC_N_THRESHOLD
4393 #define REDC_1_TO_REDC_N_THRESHOLD	redc_1_to_redc_n_threshold
4394 extern mp_size_t			redc_1_to_redc_n_threshold;
4395 
4396 #undef	MATRIX22_STRASSEN_THRESHOLD
4397 #define MATRIX22_STRASSEN_THRESHOLD	matrix22_strassen_threshold
4398 extern mp_size_t			matrix22_strassen_threshold;
4399 
4400 #undef	HGCD_THRESHOLD
4401 #define HGCD_THRESHOLD			hgcd_threshold
4402 extern mp_size_t			hgcd_threshold;
4403 
4404 #undef	GCD_DC_THRESHOLD
4405 #define GCD_DC_THRESHOLD		gcd_dc_threshold
4406 extern mp_size_t			gcd_dc_threshold;
4407 
4408 #undef  GCDEXT_DC_THRESHOLD
4409 #define GCDEXT_DC_THRESHOLD		gcdext_dc_threshold
4410 extern mp_size_t			gcdext_dc_threshold;
4411 
4412 #undef  DIVREM_1_NORM_THRESHOLD
4413 #define DIVREM_1_NORM_THRESHOLD		divrem_1_norm_threshold
4414 extern mp_size_t			divrem_1_norm_threshold;
4415 
4416 #undef  DIVREM_1_UNNORM_THRESHOLD
4417 #define DIVREM_1_UNNORM_THRESHOLD	divrem_1_unnorm_threshold
4418 extern mp_size_t			divrem_1_unnorm_threshold;
4419 
4420 #undef	MOD_1_NORM_THRESHOLD
4421 #define MOD_1_NORM_THRESHOLD		mod_1_norm_threshold
4422 extern mp_size_t			mod_1_norm_threshold;
4423 
4424 #undef	MOD_1_UNNORM_THRESHOLD
4425 #define MOD_1_UNNORM_THRESHOLD		mod_1_unnorm_threshold
4426 extern mp_size_t			mod_1_unnorm_threshold;
4427 
4428 #undef	MOD_1N_TO_MOD_1_1_THRESHOLD
4429 #define MOD_1N_TO_MOD_1_1_THRESHOLD	mod_1n_to_mod_1_1_threshold
4430 extern mp_size_t			mod_1n_to_mod_1_1_threshold;
4431 
4432 #undef	MOD_1U_TO_MOD_1_1_THRESHOLD
4433 #define MOD_1U_TO_MOD_1_1_THRESHOLD	mod_1u_to_mod_1_1_threshold
4434 extern mp_size_t			mod_1u_to_mod_1_1_threshold;
4435 
4436 #undef	MOD_1_1_TO_MOD_1_2_THRESHOLD
4437 #define MOD_1_1_TO_MOD_1_2_THRESHOLD	mod_1_1_to_mod_1_2_threshold
4438 extern mp_size_t			mod_1_1_to_mod_1_2_threshold;
4439 
4440 #undef	MOD_1_2_TO_MOD_1_4_THRESHOLD
4441 #define MOD_1_2_TO_MOD_1_4_THRESHOLD	mod_1_2_to_mod_1_4_threshold
4442 extern mp_size_t			mod_1_2_to_mod_1_4_threshold;
4443 
4444 #undef	PREINV_MOD_1_TO_MOD_1_THRESHOLD
4445 #define PREINV_MOD_1_TO_MOD_1_THRESHOLD	preinv_mod_1_to_mod_1_threshold
4446 extern mp_size_t			preinv_mod_1_to_mod_1_threshold;
4447 
4448 #if ! UDIV_PREINV_ALWAYS
4449 #undef	DIVREM_2_THRESHOLD
4450 #define DIVREM_2_THRESHOLD		divrem_2_threshold
4451 extern mp_size_t			divrem_2_threshold;
4452 #endif
4453 
4454 #undef	MULMOD_BNM1_THRESHOLD
4455 #define MULMOD_BNM1_THRESHOLD		mulmod_bnm1_threshold
4456 extern mp_size_t			mulmod_bnm1_threshold;
4457 
4458 #undef	SQRMOD_BNM1_THRESHOLD
4459 #define SQRMOD_BNM1_THRESHOLD		sqrmod_bnm1_threshold
4460 extern mp_size_t			sqrmod_bnm1_threshold;
4461 
4462 #undef	GET_STR_DC_THRESHOLD
4463 #define GET_STR_DC_THRESHOLD		get_str_dc_threshold
4464 extern mp_size_t			get_str_dc_threshold;
4465 
4466 #undef  GET_STR_PRECOMPUTE_THRESHOLD
4467 #define GET_STR_PRECOMPUTE_THRESHOLD	get_str_precompute_threshold
4468 extern mp_size_t			get_str_precompute_threshold;
4469 
4470 #undef	SET_STR_DC_THRESHOLD
4471 #define SET_STR_DC_THRESHOLD		set_str_dc_threshold
4472 extern mp_size_t			set_str_dc_threshold;
4473 
4474 #undef  SET_STR_PRECOMPUTE_THRESHOLD
4475 #define SET_STR_PRECOMPUTE_THRESHOLD	set_str_precompute_threshold
4476 extern mp_size_t			set_str_precompute_threshold;
4477 
4478 #undef  FFT_TABLE_ATTRS
4479 #define FFT_TABLE_ATTRS
4480 extern mp_size_t  mpn_fft_table[2][MPN_FFT_TABLE_SIZE];
4481 #define FFT_TABLE3_SIZE 2000	/* generous space for tuning */
4482 extern struct fft_table_nk mpn_fft_table3[2][FFT_TABLE3_SIZE];
4483 
4484 /* Sizes the tune program tests up to, used in a couple of recompilations. */
4485 #undef MUL_TOOM22_THRESHOLD_LIMIT
4486 #undef MUL_TOOM33_THRESHOLD_LIMIT
4487 #undef MULLO_BASECASE_THRESHOLD_LIMIT
4488 #undef SQR_TOOM3_THRESHOLD_LIMIT
4489 #define SQR_TOOM2_MAX_GENERIC           200
4490 #define MUL_TOOM22_THRESHOLD_LIMIT      700
4491 #define MUL_TOOM33_THRESHOLD_LIMIT      700
4492 #define SQR_TOOM3_THRESHOLD_LIMIT       400
4493 #define MUL_TOOM44_THRESHOLD_LIMIT     1000
4494 #define SQR_TOOM4_THRESHOLD_LIMIT      1000
4495 #define MUL_TOOM6H_THRESHOLD_LIMIT     1100
4496 #define SQR_TOOM6_THRESHOLD_LIMIT      1100
4497 #define MUL_TOOM8H_THRESHOLD_LIMIT     1200
4498 #define SQR_TOOM8_THRESHOLD_LIMIT      1200
4499 #define MULLO_BASECASE_THRESHOLD_LIMIT  200
4500 #define GET_STR_THRESHOLD_LIMIT         150
4501 
4502 #endif /* TUNE_PROGRAM_BUILD */
4503 
4504 #if defined (__cplusplus)
4505 }
4506 #endif
4507 
4508 /* FIXME: Make these itch functions less conservative.  Also consider making
4509    them dependent on just 'an', and compute the allocation directly from 'an'
4510    instead of via n.  */
4511 
4512 /* toom22/toom2: Scratch need is 2*(an + k), k is the recursion depth.
4513    k is ths smallest k such that
4514      ceil(an/2^k) < MUL_TOOM22_THRESHOLD.
4515    which implies that
4516      k = bitsize of floor ((an-1)/(MUL_TOOM22_THRESHOLD-1))
4517        = 1 + floor (log_2 (floor ((an-1)/(MUL_TOOM22_THRESHOLD-1))))
4518 */
4519 #define mpn_toom22_mul_itch(an, bn) \
4520   (2 * ((an) + GMP_NUMB_BITS))
4521 #define mpn_toom2_sqr_itch(an) \
4522   (2 * ((an) + GMP_NUMB_BITS))
4523 
4524 /* toom33/toom3: Scratch need is 5an/2 + 10k, k is the recursion depth.
4525    We use 3an + C, so that we can use a smaller constant.
4526  */
4527 #define mpn_toom33_mul_itch(an, bn) \
4528   (3 * (an) + GMP_NUMB_BITS)
4529 #define mpn_toom3_sqr_itch(an) \
4530   (3 * (an) + GMP_NUMB_BITS)
4531 
4532 /* toom33/toom3: Scratch need is 8an/3 + 13k, k is the recursion depth.
4533    We use 3an + C, so that we can use a smaller constant.
4534  */
4535 #define mpn_toom44_mul_itch(an, bn) \
4536   (3 * (an) + GMP_NUMB_BITS)
4537 #define mpn_toom4_sqr_itch(an) \
4538   (3 * (an) + GMP_NUMB_BITS)
4539 
4540 #define mpn_toom6_sqr_itch(n)						\
4541 ( ((n) - SQR_TOOM6_THRESHOLD)*2 +					\
4542    MAX(SQR_TOOM6_THRESHOLD*2 + GMP_NUMB_BITS*6,			\
4543        mpn_toom4_sqr_itch(SQR_TOOM6_THRESHOLD)) )
4544 
4545 #define mpn_toom6_mul_n_itch(n)						\
4546 ( ((n) - MUL_TOOM6H_THRESHOLD)*2 +					\
4547    MAX(MUL_TOOM6H_THRESHOLD*2 + GMP_NUMB_BITS*6,			\
4548        mpn_toom44_mul_itch(MUL_TOOM6H_THRESHOLD,MUL_TOOM6H_THRESHOLD)) )
4549 
4550 static inline mp_size_t
mpn_toom6h_mul_itch(mp_size_t an,mp_size_t bn)4551 mpn_toom6h_mul_itch (mp_size_t an, mp_size_t bn) {
4552   mp_size_t estimatedN;
4553   estimatedN = (an + bn) / (size_t) 10 + 1;
4554   return mpn_toom6_mul_n_itch (estimatedN * 6);
4555 }
4556 
4557 #define mpn_toom8_sqr_itch(n)						\
4558 ( (((n)*15)>>3) - ((SQR_TOOM8_THRESHOLD*15)>>3) +			\
4559    MAX(((SQR_TOOM8_THRESHOLD*15)>>3) + GMP_NUMB_BITS*6,		\
4560        mpn_toom6_sqr_itch(SQR_TOOM8_THRESHOLD)) )
4561 
4562 #define mpn_toom8_mul_n_itch(n)						\
4563 ( (((n)*15)>>3) - ((MUL_TOOM8H_THRESHOLD*15)>>3) +			\
4564    MAX(((MUL_TOOM8H_THRESHOLD*15)>>3) + GMP_NUMB_BITS*6,		\
4565        mpn_toom6_mul_n_itch(MUL_TOOM8H_THRESHOLD)) )
4566 
4567 static inline mp_size_t
mpn_toom8h_mul_itch(mp_size_t an,mp_size_t bn)4568 mpn_toom8h_mul_itch (mp_size_t an, mp_size_t bn) {
4569   mp_size_t estimatedN;
4570   estimatedN = (an + bn) / (size_t) 14 + 1;
4571   return mpn_toom8_mul_n_itch (estimatedN * 8);
4572 }
4573 
4574 static inline mp_size_t
mpn_toom32_mul_itch(mp_size_t an,mp_size_t bn)4575 mpn_toom32_mul_itch (mp_size_t an, mp_size_t bn)
4576 {
4577   mp_size_t n = 1 + (2 * an >= 3 * bn ? (an - 1) / (size_t) 3 : (bn - 1) >> 1);
4578   mp_size_t itch = 2 * n + 1;
4579 
4580   return itch;
4581 }
4582 
4583 static inline mp_size_t
mpn_toom42_mul_itch(mp_size_t an,mp_size_t bn)4584 mpn_toom42_mul_itch (mp_size_t an, mp_size_t bn)
4585 {
4586   mp_size_t n = an >= 2 * bn ? (an + 3) >> 2 : (bn + 1) >> 1;
4587   return 6 * n + 3;
4588 }
4589 
4590 static inline mp_size_t
mpn_toom43_mul_itch(mp_size_t an,mp_size_t bn)4591 mpn_toom43_mul_itch (mp_size_t an, mp_size_t bn)
4592 {
4593   mp_size_t n = 1 + (3 * an >= 4 * bn ? (an - 1) >> 2 : (bn - 1) / (size_t) 3);
4594 
4595   return 6*n + 4;
4596 }
4597 
4598 static inline mp_size_t
mpn_toom52_mul_itch(mp_size_t an,mp_size_t bn)4599 mpn_toom52_mul_itch (mp_size_t an, mp_size_t bn)
4600 {
4601   mp_size_t n = 1 + (2 * an >= 5 * bn ? (an - 1) / (size_t) 5 : (bn - 1) >> 1);
4602   return 6*n + 4;
4603 }
4604 
4605 static inline mp_size_t
mpn_toom53_mul_itch(mp_size_t an,mp_size_t bn)4606 mpn_toom53_mul_itch (mp_size_t an, mp_size_t bn)
4607 {
4608   mp_size_t n = 1 + (3 * an >= 5 * bn ? (an - 1) / (size_t) 5 : (bn - 1) / (size_t) 3);
4609   return 10 * n + 10;
4610 }
4611 
4612 static inline mp_size_t
mpn_toom62_mul_itch(mp_size_t an,mp_size_t bn)4613 mpn_toom62_mul_itch (mp_size_t an, mp_size_t bn)
4614 {
4615   mp_size_t n = 1 + (an >= 3 * bn ? (an - 1) / (size_t) 6 : (bn - 1) >> 1);
4616   return 10 * n + 10;
4617 }
4618 
4619 static inline mp_size_t
mpn_toom63_mul_itch(mp_size_t an,mp_size_t bn)4620 mpn_toom63_mul_itch (mp_size_t an, mp_size_t bn)
4621 {
4622   mp_size_t n = 1 + (an >= 2 * bn ? (an - 1) / (size_t) 6 : (bn - 1) / (size_t) 3);
4623   return 9 * n + 3;
4624 }
4625 
4626 #if 0
4627 #define mpn_fft_mul mpn_mul_fft_full
4628 #else
4629 #define mpn_fft_mul mpn_nussbaumer_mul
4630 #endif
4631 
4632 #ifdef __cplusplus
4633 
4634 /* A little helper for a null-terminated __gmp_allocate_func string.
4635    The destructor ensures it's freed even if an exception is thrown.
4636    The len field is needed by the destructor, and can be used by anyone else
4637    to avoid a second strlen pass over the data.
4638 
4639    Since our input is a C string, using strlen is correct.  Perhaps it'd be
4640    more C++-ish style to use std::char_traits<char>::length, but char_traits
4641    isn't available in gcc 2.95.4.  */
4642 
4643 class gmp_allocated_string {
4644  public:
4645   char *str;
4646   size_t len;
gmp_allocated_string(char * arg)4647   gmp_allocated_string(char *arg)
4648   {
4649     str = arg;
4650     len = std::strlen (str);
4651   }
~gmp_allocated_string()4652   ~gmp_allocated_string()
4653   {
4654     (*__gmp_free_func) (str, len+1);
4655   }
4656 };
4657 
4658 std::istream &__gmpz_operator_in_nowhite (std::istream &, mpz_ptr, char);
4659 int __gmp_istream_set_base (std::istream &, char &, bool &, bool &);
4660 void __gmp_istream_set_digits (std::string &, std::istream &, char &, bool &, int);
4661 void __gmp_doprnt_params_from_ios (struct doprnt_params_t *p, std::ios &o);
4662 std::ostream& __gmp_doprnt_integer_ostream (std::ostream &o, struct doprnt_params_t *p, char *s);
4663 extern const struct doprnt_funs_t  __gmp_asprintf_funs_noformat;
4664 
4665 #endif /* __cplusplus */
4666 
4667 #endif /* __GMP_IMPL_H__ */
4668