stdlib/gmp-impl.h

   1 /* Include file for internal GNU MP types and definitions.
   2
   3 Copyright (C) 1991, 1993, 1994, 1995, 1996, 2011 Free Software Foundation, Inc.
   4
   5 This file is part of the GNU MP Library.
   6
   7 The GNU MP Library is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU Lesser General Public License as published by
   9 the Free Software Foundation; either version 2.1 of the License, or (at your
  10 option) any later version.
  11
  12 The GNU MP Library is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  15 License for more details.
  16
  17 You should have received a copy of the GNU Lesser General Public License
  18 along with the GNU MP Library; see the file COPYING.LIB.  If not, see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* When using gcc, make sure to use its builtin alloca.  */
  22 #if ! defined (alloca) && defined (__GNUC__)
  23 #define alloca __builtin_alloca
  24 #define HAVE_ALLOCA
  25 #endif
  26
  27 /* When using cc, do whatever necessary to allow use of alloca.  For many
  28    machines, this means including alloca.h.  IBM's compilers need a #pragma
  29    in "each module that needs to use alloca".  */
  30 #if ! defined (alloca)
  31 /* We need lots of variants for MIPS, to cover all versions and perversions
  32    of OSes for MIPS.  */
  33 #if defined (__mips) || defined (MIPSEL) || defined (MIPSEB) \
  34  || defined (_MIPSEL) || defined (_MIPSEB) || defined (__sgi) \
  35  || defined (__alpha) || defined (__sparc) || defined (sparc) \
  36  || defined (__ksr__)
  37 #include <alloca.h>
  38 #define HAVE_ALLOCA
  39 #endif
  40 #if defined (_IBMR2)
  41 #pragma alloca
  42 #define HAVE_ALLOCA
  43 #endif
  44 #if defined (__DECC)
  45 #define alloca(x) __ALLOCA(x)
  46 #define HAVE_ALLOCA
  47 #endif
  48 #endif
  49
  50 #if ! defined (HAVE_ALLOCA) || USE_STACK_ALLOC
  51 #include "stack-alloc.h"
  52 #else
  53 #define TMP_DECL(m)
  54 #define TMP_ALLOC(x) alloca(x)
  55 #define TMP_MARK(m)
  56 #define TMP_FREE(m)
  57 #endif
  58
  59 #ifndef NULL
  60 #define NULL ((void *) 0)
  61 #endif
  62
  63 #if ! defined (__GNUC__)
  64 #define inline                  /* Empty */
  65 #endif
  66
  67 #define ABS(x) (x >= 0 ? x : -x)
  68 #ifndef MIN
  69 #define MIN(l,o) ((l) < (o) ? (l) : (o))
  70 #endif
  71 #ifndef MAX
  72 #define MAX(h,i) ((h) > (i) ? (h) : (i))
  73 #endif
  74
  75 /* Field access macros.  */
  76 #define SIZ(x) ((x)->_mp_size)
  77 #define ABSIZ(x) ABS (SIZ (x))
  78 #define PTR(x) ((x)->_mp_d)
  79 #define EXP(x) ((x)->_mp_exp)
  80 #define PREC(x) ((x)->_mp_prec)
  81 #define ALLOC(x) ((x)->_mp_alloc)
  82
  83 #include "gmp-mparam.h"
  84 /* #include "longlong.h" */
  85
  86 #if defined (__STDC__)  || defined (__cplusplus)
  87 void *malloc (size_t);
  88 void *realloc (void *, size_t);
  89 void free (void *);
  90
  91 extern void *   (*_mp_allocate_func) (size_t);
  92 extern void *   (*_mp_reallocate_func) (void *, size_t, size_t);
  93 extern void     (*_mp_free_func) (void *, size_t);
  94
  95 void *_mp_default_allocate (size_t);
  96 void *_mp_default_reallocate (void *, size_t, size_t);
  97 void _mp_default_free (void *, size_t);
  98
  99 #else
 100
 101 #define const                   /* Empty */
 102 #define signed                  /* Empty */
 103
 104 void *malloc ();
 105 void *realloc ();
 106 void free ();
 107
 108 extern void *   (*_mp_allocate_func) ();
 109 extern void *   (*_mp_reallocate_func) ();
 110 extern void     (*_mp_free_func) ();
 111
 112 void *_mp_default_allocate ();
 113 void *_mp_default_reallocate ();
 114 void _mp_default_free ();
 115 #endif
 116
 117 /* Copy NLIMBS *limbs* from SRC to DST.  */
 118 #define MPN_COPY_INCR(DST, SRC, NLIMBS) \
 119   do {                                                                  \
 120     mp_size_t __i;                                                      \
 121     for (__i = 0; __i < (NLIMBS); __i++)                                \
 122       (DST)[__i] = (SRC)[__i];                                          \
 123   } while (0)
 124 #define MPN_COPY_DECR(DST, SRC, NLIMBS) \
 125   do {                                                                  \
 126     mp_size_t __i;                                                      \
 127     for (__i = (NLIMBS) - 1; __i >= 0; __i--)                           \
 128       (DST)[__i] = (SRC)[__i];                                          \
 129   } while (0)
 130 #define MPN_COPY MPN_COPY_INCR
 131
 132 /* Zero NLIMBS *limbs* AT DST.  */
 133 #define MPN_ZERO(DST, NLIMBS) \
 134   do {                                                                  \
 135     mp_size_t __i;                                                      \
 136     for (__i = 0; __i < (NLIMBS); __i++)                                \
 137       (DST)[__i] = 0;                                                   \
 138   } while (0)
 139
 140 #define MPN_NORMALIZE(DST, NLIMBS) \
 141   do {                                                                  \
 142     while (NLIMBS > 0)                                                  \
 143       {                                                                 \
 144         if ((DST)[(NLIMBS) - 1] != 0)                                   \
 145           break;                                                        \
 146         NLIMBS--;                                                       \
 147       }                                                                 \
 148   } while (0)
 149 #define MPN_NORMALIZE_NOT_ZERO(DST, NLIMBS) \
 150   do {                                                                  \
 151     while (1)                                                           \
 152       {                                                                 \
 153         if ((DST)[(NLIMBS) - 1] != 0)                                   \
 154           break;                                                        \
 155         NLIMBS--;                                                       \
 156       }                                                                 \
 157   } while (0)
 158
 159 /* Initialize the MP_INT X with space for NLIMBS limbs.
 160    X should be a temporary variable, and it will be automatically
 161    cleared out when the running function returns.
 162    We use __x here to make it possible to accept both mpz_ptr and mpz_t
 163    arguments.  */
 164 #define MPZ_TMP_INIT(X, NLIMBS) \
 165   do {                                                                  \
 166     mpz_ptr __x = (X);                                                  \
 167     __x->_mp_alloc = (NLIMBS);                                          \
 168     __x->_mp_d = (mp_ptr) TMP_ALLOC ((NLIMBS) * BYTES_PER_MP_LIMB);     \
 169   } while (0)
 170
 171 #define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \
 172   do {                                                                  \
 173     if ((size) < KARATSUBA_THRESHOLD)                                   \
 174       impn_mul_n_basecase (prodp, up, vp, size);                        \
 175     else                                                                \
 176       impn_mul_n (prodp, up, vp, size, tspace);                 \
 177   } while (0);
 178 #define MPN_SQR_N_RECURSE(prodp, up, size, tspace) \
 179   do {                                                                  \
 180     if ((size) < KARATSUBA_THRESHOLD)                                   \
 181       impn_sqr_n_basecase (prodp, up, size);                            \
 182     else                                                                \
 183       impn_sqr_n (prodp, up, size, tspace);                             \
 184   } while (0);
 185
 186 /* Structure for conversion between internal binary format and
 187    strings in base 2..36.  */
 188 struct bases
 189 {
 190   /* Number of digits in the conversion base that always fits in an mp_limb_t.
 191      For example, for base 10 on a machine where a mp_limb_t has 32 bits this
 192      is 9, since 10**9 is the largest number that fits into a mp_limb_t.  */
 193   int chars_per_limb;
 194
 195   /* log(2)/log(conversion_base) */
 196   float chars_per_bit_exactly;
 197
 198   /* base**chars_per_limb, i.e. the biggest number that fits a word, built by
 199      factors of base.  Exception: For 2, 4, 8, etc, big_base is log2(base),
 200      i.e. the number of bits used to represent each digit in the base.  */
 201   mp_limb_t big_base;
 202
 203   /* A BITS_PER_MP_LIMB bit approximation to 1/big_base, represented as a
 204      fixed-point number.  Instead of dividing by big_base an application can
 205      choose to multiply by big_base_inverted.  */
 206   mp_limb_t big_base_inverted;
 207 };
 208
 209 extern const struct bases __mp_bases[];
 210 extern mp_size_t __gmp_default_fp_limb_precision;
 211
 212 /* Divide the two-limb number in (NH,,NL) by D, with DI being the largest
 213    limb not larger than (2**(2*BITS_PER_MP_LIMB))/D - (2**BITS_PER_MP_LIMB).
 214    If this would yield overflow, DI should be the largest possible number
 215    (i.e., only ones).  For correct operation, the most significant bit of D
 216    has to be set.  Put the quotient in Q and the remainder in R.  */
 217 #define udiv_qrnnd_preinv(q, r, nh, nl, d, di) \
 218   do {                                                                  \
 219     mp_limb_t _q, _ql, _r;                                              \
 220     mp_limb_t _xh, _xl;                                                 \
 221     umul_ppmm (_q, _ql, (nh), (di));                                    \
 222     _q += (nh);                 /* DI is 2**BITS_PER_MP_LIMB too small */\
 223     umul_ppmm (_xh, _xl, _q, (d));                                      \
 224     sub_ddmmss (_xh, _r, (nh), (nl), _xh, _xl);                         \
 225     if (_xh != 0)                                                       \
 226       {                                                                 \
 227         sub_ddmmss (_xh, _r, _xh, _r, 0, (d));                          \
 228         _q += 1;                                                        \
 229         if (_xh != 0)                                                   \
 230           {                                                             \
 231             sub_ddmmss (_xh, _r, _xh, _r, 0, (d));                      \
 232             _q += 1;                                                    \
 233           }                                                             \
 234       }                                                                 \
 235     if (_r >= (d))                                                      \
 236       {                                                                 \
 237         _r -= (d);                                                      \
 238         _q += 1;                                                        \
 239       }                                                                 \
 240     (r) = _r;                                                           \
 241     (q) = _q;                                                           \
 242   } while (0)
 243 /* Like udiv_qrnnd_preinv, but for any value D.  DNORM is D shifted left
 244    so that its most significant bit is set.  LGUP is ceil(log2(D)).  */
 245 #define udiv_qrnnd_preinv2gen(q, r, nh, nl, d, di, dnorm, lgup) \
 246   do {                                                                  \
 247     mp_limb_t n2, n10, n1, nadj, q1;                                    \
 248     mp_limb_t _xh, _xl;                                                 \
 249     n2 = ((nh) << (BITS_PER_MP_LIMB - (lgup))) + ((nl) >> 1 >> (l - 1));\
 250     n10 = (nl) << (BITS_PER_MP_LIMB - (lgup));                          \
 251     n1 = ((mp_limb_signed_t) n10 >> (BITS_PER_MP_LIMB - 1));            \
 252     nadj = n10 + (n1 & (dnorm));                                        \
 253     umul_ppmm (_xh, _xl, di, n2 - n1);                                  \
 254     add_ssaaaa (_xh, _xl, _xh, _xl, 0, nadj);                           \
 255     q1 = ~(n2 + _xh);                                                   \
 256     umul_ppmm (_xh, _xl, q1, d);                                        \
 257     add_ssaaaa (_xh, _xl, _xh, _xl, nh, nl);                            \
 258     _xh -= (d);                                                         \
 259     (r) = _xl + ((d) & _xh);                                            \
 260     (q) = _xh - q1;                                                     \
 261   } while (0)
 262 /* Exactly like udiv_qrnnd_preinv, but branch-free.  It is not clear which
 263    version to use.  */
 264 #define udiv_qrnnd_preinv2norm(q, r, nh, nl, d, di) \
 265   do {                                                                  \
 266     mp_limb_t n2, n10, n1, nadj, q1;                                    \
 267     mp_limb_t _xh, _xl;                                                 \
 268     n2 = (nh);                                                          \
 269     n10 = (nl);                                                         \
 270     n1 = ((mp_limb_signed_t) n10 >> (BITS_PER_MP_LIMB - 1));            \
 271     nadj = n10 + (n1 & (d));                                            \
 272     umul_ppmm (_xh, _xl, di, n2 - n1);                                  \
 273     add_ssaaaa (_xh, _xl, _xh, _xl, 0, nadj);                           \
 274     q1 = ~(n2 + _xh);                                                   \
 275     umul_ppmm (_xh, _xl, q1, d);                                        \
 276     add_ssaaaa (_xh, _xl, _xh, _xl, nh, nl);                            \
 277     _xh -= (d);                                                         \
 278     (r) = _xl + ((d) & _xh);                                            \
 279     (q) = _xh - q1;                                                     \
 280   } while (0)
 281
 282 #if defined (__GNUC__)
 283 /* Define stuff for longlong.h.  */
 284 typedef unsigned int UQItype    __attribute__ ((mode (QI)));
 285 typedef          int SItype     __attribute__ ((mode (SI)));
 286 typedef unsigned int USItype    __attribute__ ((mode (SI)));
 287 typedef          int DItype     __attribute__ ((mode (DI)));
 288 typedef unsigned int UDItype    __attribute__ ((mode (DI)));
 289 #else
 290 typedef unsigned char UQItype;
 291 typedef          long SItype;
 292 typedef unsigned long USItype;
 293 #endif
 294
 295 typedef mp_limb_t UWtype;
 296 typedef unsigned int UHWtype;
 297 #define W_TYPE_SIZE BITS_PER_MP_LIMB
 298
 299 /* Internal mpn calls */
 300 #define impn_mul_n_basecase     __MPN(impn_mul_n_basecase)
 301 #define impn_mul_n              __MPN(impn_mul_n)
 302 #define impn_sqr_n_basecase     __MPN(impn_sqr_n_basecase)
 303 #define impn_sqr_n              __MPN(impn_sqr_n)
 304
 305 #ifndef _PROTO
 306 #if defined (__STDC__) || defined (__cplusplus)
 307 #define _PROTO(x) x
 308 #else
 309 #define _PROTO(x) ()
 310 #endif
 311 #endif
 312
 313 /* Prototypes for internal mpn calls.  */
 314 extern void impn_mul_n_basecase _PROTO ((mp_ptr prodp, mp_srcptr up,
 315                                          mp_srcptr vp, mp_size_t size));
 316 extern void impn_mul_n _PROTO ((mp_ptr prodp, mp_srcptr up, mp_srcptr vp,
 317                                 mp_size_t size, mp_ptr tspace));
 318 extern void impn_sqr_n_basecase _PROTO ((mp_ptr prodp, mp_srcptr up,
 319                                          mp_size_t size));
 320 extern void impn_sqr_n _PROTO ((mp_ptr prodp, mp_srcptr up, mp_size_t size,
 321                                 mp_ptr tspace));
 322
 323
 324
 325 #ifndef IEEE_DOUBLE_BIG_ENDIAN
 326 #define IEEE_DOUBLE_BIG_ENDIAN 1
 327 #endif
 328
 329 #ifndef IEEE_DOUBLE_MIXED_ENDIAN
 330 #define IEEE_DOUBLE_MIXED_ENDIAN 0
 331 #endif
 332
 333 #if IEEE_DOUBLE_MIXED_ENDIAN
 334 union ieee_double_extract
 335 {
 336   struct
 337     {
 338       unsigned int manh:20;
 339       unsigned int exp:11;
 340       unsigned int sig:1;
 341       unsigned int manl:32;
 342     } s;
 343   double d;
 344 };
 345 #else
 346 #if IEEE_DOUBLE_BIG_ENDIAN
 347 union ieee_double_extract
 348 {
 349   struct
 350     {
 351       unsigned int sig:1;
 352       unsigned int exp:11;
 353       unsigned int manh:20;
 354       unsigned int manl:32;
 355     } s;
 356   double d;
 357 };
 358 #else
 359 union ieee_double_extract
 360 {
 361   struct
 362     {
 363       unsigned int manl:32;
 364       unsigned int manh:20;
 365       unsigned int exp:11;
 366       unsigned int sig:1;
 367     } s;
 368   double d;
 369 };
 370 #endif
 371 #endif