stdio/gmp-impl.h

   1 /* Include file for internal GNU MP types and definitions.
   2
   3 Copyright (C) 1991, 1993, 1994 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 Library General Public License as published by
   9 the Free Software Foundation; either version 2 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 Library General Public
  15 License for more details.
  16
  17 You should have received a copy of the GNU Library General Public License
  18 along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
  19 the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
  20
  21 #if ! defined (alloca)
  22 #if defined (__GNUC__) || defined (__sparc__) || defined (sparc)
  23 #define alloca __builtin_alloca
  24 #endif
  25 #endif
  26
  27 #ifndef NULL
  28 #define NULL 0L
  29 #endif
  30
  31 #if ! defined (__GNUC__)
  32 #define inline                  /* Empty */
  33 void *alloca();
  34 #endif
  35
  36 #define ABS(x) (x >= 0 ? x : -x)
  37 #define MIN(l,o) ((l) < (o) ? (l) : (o))
  38 #define MAX(h,i) ((h) > (i) ? (h) : (i))
  39
  40 #include "gmp-mparam.h"
  41 /* #include "longlong.h" */
  42
  43 #ifdef __STDC__
  44 void *malloc (size_t);
  45 void *realloc (void *, size_t);
  46 void free (void *);
  47
  48 extern void *   (*_mp_allocate_func) (size_t);
  49 extern void *   (*_mp_reallocate_func) (void *, size_t, size_t);
  50 extern void     (*_mp_free_func) (void *, size_t);
  51
  52 void *_mp_default_allocate (size_t);
  53 void *_mp_default_reallocate (void *, size_t, size_t);
  54 void _mp_default_free (void *, size_t);
  55
  56 #else
  57
  58 #define const                   /* Empty */
  59 #define signed                  /* Empty */
  60
  61 void *malloc ();
  62 void *realloc ();
  63 void free ();
  64
  65 extern void *   (*_mp_allocate_func) ();
  66 extern void *   (*_mp_reallocate_func) ();
  67 extern void     (*_mp_free_func) ();
  68
  69 void *_mp_default_allocate ();
  70 void *_mp_default_reallocate ();
  71 void _mp_default_free ();
  72 #endif
  73
  74 /* Copy NLIMBS *limbs* from SRC to DST.  */
  75 #define MPN_COPY_INCR(DST, SRC, NLIMBS) \
  76   do {                                                                  \
  77     mp_size_t __i;                                                      \
  78     for (__i = 0; __i < (NLIMBS); __i++)                                \
  79       (DST)[__i] = (SRC)[__i];                                          \
  80   } while (0)
  81 #define MPN_COPY_DECR(DST, SRC, NLIMBS) \
  82   do {                                                                  \
  83     mp_size_t __i;                                                      \
  84     for (__i = (NLIMBS) - 1; __i >= 0; __i--)                           \
  85       (DST)[__i] = (SRC)[__i];                                          \
  86   } while (0)
  87 #define MPN_COPY MPN_COPY_INCR
  88
  89 /* Zero NLIMBS *limbs* AT DST.  */
  90 #define MPN_ZERO(DST, NLIMBS) \
  91   do {                                                                  \
  92     mp_size_t __i;                                                      \
  93     for (__i = 0; __i < (NLIMBS); __i++)                                \
  94       (DST)[__i] = 0;                                                   \
  95   } while (0)
  96
  97 #define MPN_NORMALIZE(DST, NLIMBS) \
  98   do {                                                                  \
  99     while (NLIMBS > 0)                                                  \
 100       {                                                                 \
 101         if ((DST)[(NLIMBS) - 1] != 0)                                   \
 102           break;                                                        \
 103         NLIMBS--;                                                       \
 104       }                                                                 \
 105   } while (0)
 106 #define MPN_NORMALIZE_NOT_ZERO(DST, NLIMBS) \
 107   do {                                                                  \
 108     while (1)                                                           \
 109       {                                                                 \
 110         if ((DST)[(NLIMBS) - 1] != 0)                                   \
 111           break;                                                        \
 112         NLIMBS--;                                                       \
 113       }                                                                 \
 114   } while (0)
 115
 116 /*  Swap (mp_ptr, mp_size_t) (U, UL) with (V, VL)  */
 117 #define MPN_SWAP(u, l, v, m) \
 118   do {                                                                  \
 119     { mp_ptr _; _ = (u), (u) = (v), (v) = _;}                           \
 120     { mp_size_t _; _ = (l), (l) = (m), (m) = _;}                        \
 121   } while (0)
 122
 123 /*  Return true iff the limb X has less bits than the limb Y.  */
 124 #define MPN_LESS_BITS_LIMB(x,y) ((x) < (y) && (x) < ((x) ^ (y)))
 125
 126 /*  Return true iff (mp_ptr, mp_size_t) (U, UL) has less bits than (V, VL).  */
 127 #define MPN_LESS_BITS(u, l, v, m) \
 128   ((l) < (m)                                                            \
 129    || ((l) == (m) && (l) != 0 && MPN_LESS_BITS_LIMB ((u)[(l - 1)], (v)[(l) - 1])))
 130
 131 /*  Return true iff (mp_ptr, mp_size_t) (U, UL) has more bits than (V, VL).  */
 132 #define MPN_MORE_BITS(u, l, v, m) MPN_LESS_BITS (v, m, u, l)
 133
 134 /*  Perform twos complement on (mp_ptr, mp_size_t) (U, UL),
 135     putting result at (v, VL).  Precondition: U[0] != 0.  */
 136 #define MPN_COMPL_INCR(u, v, l) \
 137   do {                                                                  \
 138     mp_size_t _ = 0;                                                    \
 139     (u)[0] = -(v)[_];                                                   \
 140     while (_++ < (l))                                                   \
 141       (u)[_] = ~(v)[_];                                                 \
 142   } while (0)
 143 #define MPN_COMPL MPN_COMPL_INCR
 144
 145 /* Initialize the MP_INT X with space for NLIMBS limbs.
 146    X should be a temporary variable, and it will be automatically
 147    cleared out when the running function returns.
 148    We use __x here to make it possible to accept both mpz_ptr and mpz_t
 149    arguments.  */
 150 #define MPZ_TMP_INIT(X, NLIMBS) \
 151   do {                                                                  \
 152     mpz_ptr __x = (X);                                                  \
 153     __x->alloc = (NLIMBS);                                              \
 154     __x->d = (mp_ptr) alloca ((NLIMBS) * BYTES_PER_MP_LIMB);            \
 155   } while (0)
 156
 157 #define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \
 158   do {                                                                  \
 159     if ((size) < KARATSUBA_THRESHOLD)                                   \
 160       ____mpn_mul_n_basecase (prodp, up, vp, size);                     \
 161     else                                                                \
 162       ____mpn_mul_n (prodp, up, vp, size, tspace);                      \
 163   } while (0);
 164 #define MPN_SQR_N_RECURSE(prodp, up, size, tspace) \
 165   do {                                                                  \
 166     if ((size) < KARATSUBA_THRESHOLD)                                   \
 167       ____mpn_sqr_n_basecase (prodp, up, size);                         \
 168     else                                                                \
 169       ____mpn_sqr_n (prodp, up, size, tspace);                          \
 170   } while (0);
 171
 172 /* Structure for conversion between internal binary format and
 173    strings in base 2..36.  */
 174 struct bases
 175 {
 176   /* Number of digits in the conversion base that always fits in
 177      an mp_limb.  For example, for base 10 this is 10, since
 178      2**32 = 4294967296 has ten digits.  */
 179   int chars_per_limb;
 180
 181   /* log(2)/log(conversion_base) */
 182   float chars_per_bit_exactly;
 183
 184   /* big_base is conversion_base**chars_per_limb, i.e. the biggest
 185      number that fits a word, built by factors of conversion_base.
 186      Exception: For 2, 4, 8, etc, big_base is log2(base), i.e. the
 187      number of bits used to represent each digit in the base.  */
 188   mp_limb big_base;
 189
 190   /* big_base_inverted is a BITS_PER_MP_LIMB bit approximation to
 191      1/big_base, represented as a fixed-point number.  Instead of
 192      dividing by big_base an application can choose to multiply
 193      by big_base_inverted.  */
 194   mp_limb big_base_inverted;
 195 };
 196
 197 extern const struct bases __mp_bases[];
 198 extern mp_size_t __gmp_default_fp_limb_precision;
 199
 200 /* Divide the two-limb number in (NH,,NL) by D, with DI being a 32 bit
 201    approximation to (2**(2*BITS_PER_MP_LIMB))/D - (2**BITS_PER_MP_LIMB).
 202    Put the quotient in Q and the remainder in R.  */
 203 #define udiv_qrnnd_preinv(q, r, nh, nl, d, di) \
 204   do {                                                                  \
 205     mp_limb _q, _ql, _r;                                                \
 206     mp_limb _xh, _xl;                                                   \
 207     umul_ppmm (_q, _ql, (nh), (di));                                    \
 208     _q += (nh);                 /* DI is 2**BITS_PER_MP_LIMB too small */\
 209     umul_ppmm (_xh, _xl, _q, (d));                                      \
 210     sub_ddmmss (_xh, _r, (nh), (nl), _xh, _xl);                         \
 211     if (_xh != 0)                                                       \
 212       {                                                                 \
 213         sub_ddmmss (_xh, _r, _xh, _r, 0, (d));                          \
 214         _q += 1;                                                        \
 215         if (_xh != 0)                                                   \
 216           {                                                             \
 217             sub_ddmmss (_xh, _r, _xh, _r, 0, (d));                      \
 218             _q += 1;                                                    \
 219           }                                                             \
 220       }                                                                 \
 221     if (_r >= (d))                                                      \
 222       {                                                                 \
 223         _r -= (d);                                                      \
 224         _q += 1;                                                        \
 225       }                                                                 \
 226     (r) = _r;                                                           \
 227     (q) = _q;                                                           \
 228   } while (0)
 229 #define udiv_qrnnd_preinv2gen(q, r, nh, nl, d, di, dnorm, lgup) \
 230   do {                                                                  \
 231     mp_limb n2, n10, n1, nadj, q1;                                      \
 232     mp_limb _xh, _xl;                                                   \
 233     n2 = ((nh) << (BITS_PER_MP_LIMB - (lgup))) + ((nl) >> 1 >> (l - 1));\
 234     n10 = (nl) << (BITS_PER_MP_LIMB - (lgup));                          \
 235     n1 = ((mp_limb_signed) n10 >> (BITS_PER_MP_LIMB - 1));              \
 236     nadj = n10 + (n1 & (dnorm));                                        \
 237     umul_ppmm (_xh, _xl, di, n2 - n1);                                  \
 238     add_ssaaaa (_xh, _xl, _xh, _xl, 0, nadj);                           \
 239     q1 = ~(n2 + _xh);                                                   \
 240     umul_ppmm (_xh, _xl, q1, d);                                        \
 241     add_ssaaaa (_xh, _xl, _xh, _xl, nh, nl);                            \
 242     _xh -= (d);                                                         \
 243     (r) = _xl + ((d) & _xh);                                            \
 244     (q) = _xh - q1;                                                     \
 245   } while (0)
 246 #define udiv_qrnnd_preinv2norm(q, r, nh, nl, d, di) \
 247   do {                                                                  \
 248     mp_limb n2, n10, n1, nadj, q1;                                      \
 249     mp_limb _xh, _xl;                                                   \
 250     n2 = (nh);                                                          \
 251     n10 = (nl);                                                         \
 252     n1 = ((mp_limb_signed) n10 >> (BITS_PER_MP_LIMB - 1));              \
 253     nadj = n10 + (n1 & (d));                                            \
 254     umul_ppmm (_xh, _xl, di, n2 - n1);                                  \
 255     add_ssaaaa (_xh, _xl, _xh, _xl, 0, nadj);                           \
 256     q1 = ~(n2 + _xh);                                                   \
 257     umul_ppmm (_xh, _xl, q1, d);                                        \
 258     add_ssaaaa (_xh, _xl, _xh, _xl, nh, nl);                            \
 259     _xh -= (d);                                                         \
 260     (r) = _xl + ((d) & _xh);                                            \
 261     (q) = _xh - q1;                                                     \
 262   } while (0)
 263
 264 #if defined (__GNUC__)
 265 /* Define stuff for longlong.h asm macros.  */
 266 #if __GNUC_NEW_ATTR_MODE_SYNTAX
 267 typedef unsigned int UQItype    __attribute__ ((mode ("QI")));
 268 typedef          int SItype     __attribute__ ((mode ("SI")));
 269 typedef unsigned int USItype    __attribute__ ((mode ("SI")));
 270 typedef          int DItype     __attribute__ ((mode ("DI")));
 271 typedef unsigned int UDItype    __attribute__ ((mode ("DI")));
 272 #else
 273 typedef unsigned int UQItype    __attribute__ ((mode (QI)));
 274 typedef          int SItype     __attribute__ ((mode (SI)));
 275 typedef unsigned int USItype    __attribute__ ((mode (SI)));
 276 typedef          int DItype     __attribute__ ((mode (DI)));
 277 typedef unsigned int UDItype    __attribute__ ((mode (DI)));
 278 #endif
 279 #endif
 280
 281 typedef mp_limb UWtype;
 282 typedef unsigned int UHWtype;
 283 #define W_TYPE_SIZE BITS_PER_MP_LIMB