stdlib/gmp-impl.h

   1 /* Include file for internal GNU MP types and definitions.
   2
   3 Copyright (C) 1991-2017 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) || defined (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 /* Get MAX/MIN macros.  */
  68 #include <sys/param.h>
  69
  70 /* Field access macros.  */
  71 #define SIZ(x) ((x)->_mp_size)
  72 #define PTR(x) ((x)->_mp_d)
  73 #define EXP(x) ((x)->_mp_exp)
  74 #define PREC(x) ((x)->_mp_prec)
  75 #define ALLOC(x) ((x)->_mp_alloc)
  76
  77 #include "gmp-mparam.h"
  78 /* #include "longlong.h" */
  79
  80 #if defined (__STDC__)  || defined (__cplusplus)
  81 void *malloc (size_t);
  82 void *realloc (void *, size_t);
  83 void free (void *);
  84
  85 extern void *   (*_mp_allocate_func) (size_t);
  86 extern void *   (*_mp_reallocate_func) (void *, size_t, size_t);
  87 extern void     (*_mp_free_func) (void *, size_t);
  88
  89 void *_mp_default_allocate (size_t);
  90 void *_mp_default_reallocate (void *, size_t, size_t);
  91 void _mp_default_free (void *, size_t);
  92
  93 #else
  94
  95 #define const                   /* Empty */
  96 #define signed                  /* Empty */
  97
  98 void *malloc ();
  99 void *realloc ();
 100 void free ();
 101
 102 extern void *   (*_mp_allocate_func) ();
 103 extern void *   (*_mp_reallocate_func) ();
 104 extern void     (*_mp_free_func) ();
 105
 106 void *_mp_default_allocate ();
 107 void *_mp_default_reallocate ();
 108 void _mp_default_free ();
 109 #endif
 110
 111 /* Copy NLIMBS *limbs* from SRC to DST.  */
 112 #define MPN_COPY_INCR(DST, SRC, NLIMBS) \
 113   do {                                                                  \
 114     mp_size_t __i;                                                      \
 115     for (__i = 0; __i < (NLIMBS); __i++)                                \
 116       (DST)[__i] = (SRC)[__i];                                          \
 117   } while (0)
 118 #define MPN_COPY_DECR(DST, SRC, NLIMBS) \
 119   do {                                                                  \
 120     mp_size_t __i;                                                      \
 121     for (__i = (NLIMBS) - 1; __i >= 0; __i--)                           \
 122       (DST)[__i] = (SRC)[__i];                                          \
 123   } while (0)
 124 #define MPN_COPY MPN_COPY_INCR
 125
 126 /* Zero NLIMBS *limbs* AT DST.  */
 127 #define MPN_ZERO(DST, NLIMBS) \
 128   do {                                                                  \
 129     mp_size_t __i;                                                      \
 130     for (__i = 0; __i < (NLIMBS); __i++)                                \
 131       (DST)[__i] = 0;                                                   \
 132   } while (0)
 133
 134 #define MPN_NORMALIZE(DST, NLIMBS) \
 135   do {                                                                  \
 136     while (NLIMBS > 0)                                                  \
 137       {                                                                 \
 138         if ((DST)[(NLIMBS) - 1] != 0)                                   \
 139           break;                                                        \
 140         NLIMBS--;                                                       \
 141       }                                                                 \
 142   } while (0)
 143 #define MPN_NORMALIZE_NOT_ZERO(DST, NLIMBS) \
 144   do {                                                                  \
 145     while (1)                                                           \
 146       {                                                                 \
 147         if ((DST)[(NLIMBS) - 1] != 0)                                   \
 148           break;                                                        \
 149         NLIMBS--;                                                       \
 150       }                                                                 \
 151   } while (0)
 152
 153 /* Initialize the MP_INT X with space for NLIMBS limbs.
 154    X should be a temporary variable, and it will be automatically
 155    cleared out when the running function returns.
 156    We use __x here to make it possible to accept both mpz_ptr and mpz_t
 157    arguments.  */
 158 #define MPZ_TMP_INIT(X, NLIMBS) \
 159   do {                                                                  \
 160     mpz_ptr __x = (X);                                                  \
 161     __x->_mp_alloc = (NLIMBS);                                          \
 162     __x->_mp_d = (mp_ptr) TMP_ALLOC ((NLIMBS) * BYTES_PER_MP_LIMB);     \
 163   } while (0)
 164
 165 #define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \
 166   do {                                                                  \
 167     if ((size) < KARATSUBA_THRESHOLD)                                   \
 168       impn_mul_n_basecase (prodp, up, vp, size);                        \
 169     else                                                                \
 170       impn_mul_n (prodp, up, vp, size, tspace);                 \
 171   } while (0);
 172 #define MPN_SQR_N_RECURSE(prodp, up, size, tspace) \
 173   do {                                                                  \
 174     if ((size) < KARATSUBA_THRESHOLD)                                   \
 175       impn_sqr_n_basecase (prodp, up, size);                            \
 176     else                                                                \
 177       impn_sqr_n (prodp, up, size, tspace);                             \
 178   } while (0);
 179
 180 /* Structure for conversion between internal binary format and
 181    strings in base 2..36.  */
 182 struct bases
 183 {
 184   /* Number of digits in the conversion base that always fits in an mp_limb_t.
 185      For example, for base 10 on a machine where a mp_limb_t has 32 bits this
 186      is 9, since 10**9 is the largest number that fits into a mp_limb_t.  */
 187   int chars_per_limb;
 188
 189   /* log(2)/log(conversion_base) */
 190   float chars_per_bit_exactly;
 191
 192   /* base**chars_per_limb, i.e. the biggest number that fits a word, built by
 193      factors of base.  Exception: For 2, 4, 8, etc, big_base is log2(base),
 194      i.e. the number of bits used to represent each digit in the base.  */
 195   mp_limb_t big_base;
 196
 197   /* A BITS_PER_MP_LIMB bit approximation to 1/big_base, represented as a
 198      fixed-point number.  Instead of dividing by big_base an application can
 199      choose to multiply by big_base_inverted.  */
 200   mp_limb_t big_base_inverted;
 201 };
 202
 203 extern const struct bases __mp_bases[];
 204 extern mp_size_t __gmp_default_fp_limb_precision;
 205
 206 /* Divide the two-limb number in (NH,,NL) by D, with DI being the largest
 207    limb not larger than (2**(2*BITS_PER_MP_LIMB))/D - (2**BITS_PER_MP_LIMB).
 208    If this would yield overflow, DI should be the largest possible number
 209    (i.e., only ones).  For correct operation, the most significant bit of D
 210    has to be set.  Put the quotient in Q and the remainder in R.  */
 211 #define udiv_qrnnd_preinv(q, r, nh, nl, d, di) \
 212   do {                                                                  \
 213     mp_limb_t _ql __attribute__ ((unused));                             \
 214     mp_limb_t _q, _r;                                                   \
 215     mp_limb_t _xh, _xl;                                                 \
 216     umul_ppmm (_q, _ql, (nh), (di));                                    \
 217     _q += (nh);                 /* DI is 2**BITS_PER_MP_LIMB too small */\
 218     umul_ppmm (_xh, _xl, _q, (d));                                      \
 219     sub_ddmmss (_xh, _r, (nh), (nl), _xh, _xl);                         \
 220     if (_xh != 0)                                                       \
 221       {                                                                 \
 222         sub_ddmmss (_xh, _r, _xh, _r, 0, (d));                          \
 223         _q += 1;                                                        \
 224         if (_xh != 0)                                                   \
 225           {                                                             \
 226             sub_ddmmss (_xh, _r, _xh, _r, 0, (d));                      \
 227             _q += 1;                                                    \
 228           }                                                             \
 229       }                                                                 \
 230     if (_r >= (d))                                                      \
 231       {                                                                 \
 232         _r -= (d);                                                      \
 233         _q += 1;                                                        \
 234       }                                                                 \
 235     (r) = _r;                                                           \
 236     (q) = _q;                                                           \
 237   } while (0)
 238 /* Like udiv_qrnnd_preinv, but for any value D.  DNORM is D shifted left
 239    so that its most significant bit is set.  LGUP is ceil(log2(D)).  */
 240 #define udiv_qrnnd_preinv2gen(q, r, nh, nl, d, di, dnorm, lgup) \
 241   do {                                                                  \
 242     mp_limb_t n2, n10, n1, nadj, q1;                                    \
 243     mp_limb_t _xh, _xl;                                                 \
 244     n2 = ((nh) << (BITS_PER_MP_LIMB - (lgup))) + ((nl) >> 1 >> (l - 1));\
 245     n10 = (nl) << (BITS_PER_MP_LIMB - (lgup));                          \
 246     n1 = ((mp_limb_signed_t) n10 >> (BITS_PER_MP_LIMB - 1));            \
 247     nadj = n10 + (n1 & (dnorm));                                        \
 248     umul_ppmm (_xh, _xl, di, n2 - n1);                                  \
 249     add_ssaaaa (_xh, _xl, _xh, _xl, 0, nadj);                           \
 250     q1 = ~(n2 + _xh);                                                   \
 251     umul_ppmm (_xh, _xl, q1, d);                                        \
 252     add_ssaaaa (_xh, _xl, _xh, _xl, nh, nl);                            \
 253     _xh -= (d);                                                         \
 254     (r) = _xl + ((d) & _xh);                                            \
 255     (q) = _xh - q1;                                                     \
 256   } while (0)
 257 /* Exactly like udiv_qrnnd_preinv, but branch-free.  It is not clear which
 258    version to use.  */
 259 #define udiv_qrnnd_preinv2norm(q, r, nh, nl, d, di) \
 260   do {                                                                  \
 261     mp_limb_t n2, n10, n1, nadj, q1;                                    \
 262     mp_limb_t _xh, _xl;                                                 \
 263     n2 = (nh);                                                          \
 264     n10 = (nl);                                                         \
 265     n1 = ((mp_limb_signed_t) n10 >> (BITS_PER_MP_LIMB - 1));            \
 266     nadj = n10 + (n1 & (d));                                            \
 267     umul_ppmm (_xh, _xl, di, n2 - n1);                                  \
 268     add_ssaaaa (_xh, _xl, _xh, _xl, 0, nadj);                           \
 269     q1 = ~(n2 + _xh);                                                   \
 270     umul_ppmm (_xh, _xl, q1, d);                                        \
 271     add_ssaaaa (_xh, _xl, _xh, _xl, nh, nl);                            \
 272     _xh -= (d);                                                         \
 273     (r) = _xl + ((d) & _xh);                                            \
 274     (q) = _xh - q1;                                                     \
 275   } while (0)
 276
 277 #if defined (__GNUC__)
 278 /* Define stuff for longlong.h.  */
 279 typedef unsigned int UQItype    __attribute__ ((mode (QI)));
 280 typedef          int SItype     __attribute__ ((mode (SI)));
 281 typedef unsigned int USItype    __attribute__ ((mode (SI)));
 282 typedef          int DItype     __attribute__ ((mode (DI)));
 283 typedef unsigned int UDItype    __attribute__ ((mode (DI)));
 284 #else
 285 typedef unsigned char UQItype;
 286 typedef          long SItype;
 287 typedef unsigned long USItype;
 288 #endif
 289
 290 typedef mp_limb_t UWtype;
 291 typedef unsigned int UHWtype;
 292 #define W_TYPE_SIZE BITS_PER_MP_LIMB
 293
 294 /* Internal mpn calls */
 295 #define impn_mul_n_basecase     __MPN(impn_mul_n_basecase)
 296 #define impn_mul_n              __MPN(impn_mul_n)
 297 #define impn_sqr_n_basecase     __MPN(impn_sqr_n_basecase)
 298 #define impn_sqr_n              __MPN(impn_sqr_n)
 299
 300 #ifndef _PROTO
 301 #if defined (__STDC__) || defined (__cplusplus)
 302 #define _PROTO(x) x
 303 #else
 304 #define _PROTO(x) ()
 305 #endif
 306 #endif
 307
 308 /* Prototypes for internal mpn calls.  */
 309 extern void impn_mul_n_basecase _PROTO ((mp_ptr prodp, mp_srcptr up,
 310                                          mp_srcptr vp, mp_size_t size));
 311 extern void impn_mul_n _PROTO ((mp_ptr prodp, mp_srcptr up, mp_srcptr vp,
 312                                 mp_size_t size, mp_ptr tspace));
 313 extern void impn_sqr_n_basecase _PROTO ((mp_ptr prodp, mp_srcptr up,
 314                                          mp_size_t size));
 315 extern void impn_sqr_n _PROTO ((mp_ptr prodp, mp_srcptr up, mp_size_t size,
 316                                 mp_ptr tspace));
 317
 318
 319
 320 #ifndef IEEE_DOUBLE_BIG_ENDIAN
 321 #define IEEE_DOUBLE_BIG_ENDIAN 1
 322 #endif
 323
 324 #ifndef IEEE_DOUBLE_MIXED_ENDIAN
 325 #define IEEE_DOUBLE_MIXED_ENDIAN 0
 326 #endif
 327
 328 #if IEEE_DOUBLE_MIXED_ENDIAN
 329 union ieee_double_extract
 330 {
 331   struct
 332     {
 333       unsigned int manh:20;
 334       unsigned int exp:11;
 335       unsigned int sig:1;
 336       unsigned int manl:32;
 337     } s;
 338   double d;
 339 };
 340 #else
 341 #if IEEE_DOUBLE_BIG_ENDIAN
 342 union ieee_double_extract
 343 {
 344   struct
 345     {
 346       unsigned int sig:1;
 347       unsigned int exp:11;
 348       unsigned int manh:20;
 349       unsigned int manl:32;
 350     } s;
 351   double d;
 352 };
 353 #else
 354 union ieee_double_extract
 355 {
 356   struct
 357     {
 358       unsigned int manl:32;
 359       unsigned int manh:20;
 360       unsigned int exp:11;
 361       unsigned int sig:1;
 362     } s;
 363   double d;
 364 };
 365 #endif
 366 #endif