Back to index

glibc  2.9
gmp-impl.h
Go to the documentation of this file.
00001 /* Include file for internal GNU MP types and definitions.
00002 
00003 Copyright (C) 1991, 1993, 1994, 1995, 1996 Free Software Foundation, Inc.
00004 
00005 This file is part of the GNU MP Library.
00006 
00007 The GNU MP Library is free software; you can redistribute it and/or modify
00008 it under the terms of the GNU Lesser General Public License as published by
00009 the Free Software Foundation; either version 2.1 of the License, or (at your
00010 option) any later version.
00011 
00012 The GNU MP Library is distributed in the hope that it will be useful, but
00013 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
00014 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
00015 License for more details.
00016 
00017 You should have received a copy of the GNU Lesser General Public License
00018 along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
00019 the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
00020 MA 02111-1307, USA. */
00021 
00022 /* When using gcc, make sure to use its builtin alloca.  */
00023 #if ! defined (alloca) && defined (__GNUC__)
00024 #define alloca __builtin_alloca
00025 #define HAVE_ALLOCA
00026 #endif
00027 
00028 /* When using cc, do whatever necessary to allow use of alloca.  For many
00029    machines, this means including alloca.h.  IBM's compilers need a #pragma
00030    in "each module that needs to use alloca".  */
00031 #if ! defined (alloca)
00032 /* We need lots of variants for MIPS, to cover all versions and perversions
00033    of OSes for MIPS.  */
00034 #if defined (__mips) || defined (MIPSEL) || defined (MIPSEB) \
00035  || defined (_MIPSEL) || defined (_MIPSEB) || defined (__sgi) \
00036  || defined (__alpha) || defined (__sparc) || defined (sparc) \
00037  || defined (__ksr__)
00038 #include <alloca.h>
00039 #define HAVE_ALLOCA
00040 #endif
00041 #if defined (_IBMR2)
00042 #pragma alloca
00043 #define HAVE_ALLOCA
00044 #endif
00045 #if defined (__DECC)
00046 #define alloca(x) __ALLOCA(x)
00047 #define HAVE_ALLOCA
00048 #endif
00049 #endif
00050 
00051 #if ! defined (HAVE_ALLOCA) || USE_STACK_ALLOC
00052 #include "stack-alloc.h"
00053 #else
00054 #define TMP_DECL(m)
00055 #define TMP_ALLOC(x) alloca(x)
00056 #define TMP_MARK(m)
00057 #define TMP_FREE(m)
00058 #endif
00059 
00060 #ifndef NULL
00061 #define NULL ((void *) 0)
00062 #endif
00063 
00064 #if ! defined (__GNUC__)
00065 #define inline                     /* Empty */
00066 #endif
00067 
00068 #define ABS(x) (x >= 0 ? x : -x)
00069 #ifndef MIN
00070 #define MIN(l,o) ((l) < (o) ? (l) : (o))
00071 #endif
00072 #ifndef MAX
00073 #define MAX(h,i) ((h) > (i) ? (h) : (i))
00074 #endif
00075 
00076 /* Field access macros.  */
00077 #define SIZ(x) ((x)->_mp_size)
00078 #define ABSIZ(x) ABS (SIZ (x))
00079 #define PTR(x) ((x)->_mp_d)
00080 #define EXP(x) ((x)->_mp_exp)
00081 #define PREC(x) ((x)->_mp_prec)
00082 #define ALLOC(x) ((x)->_mp_alloc)
00083 
00084 #include "gmp-mparam.h"
00085 /* #include "longlong.h" */
00086 
00087 #if defined (__STDC__)  || defined (__cplusplus)
00088 void *malloc (size_t);
00089 void *realloc (void *, size_t);
00090 void free (void *);
00091 
00092 extern void * (*_mp_allocate_func) (size_t);
00093 extern void * (*_mp_reallocate_func) (void *, size_t, size_t);
00094 extern void   (*_mp_free_func) (void *, size_t);
00095 
00096 void *_mp_default_allocate (size_t);
00097 void *_mp_default_reallocate (void *, size_t, size_t);
00098 void _mp_default_free (void *, size_t);
00099 
00100 #else
00101 
00102 #define const               /* Empty */
00103 #define signed                     /* Empty */
00104 
00105 void *malloc ();
00106 void *realloc ();
00107 void free ();
00108 
00109 extern void * (*_mp_allocate_func) ();
00110 extern void * (*_mp_reallocate_func) ();
00111 extern void   (*_mp_free_func) ();
00112 
00113 void *_mp_default_allocate ();
00114 void *_mp_default_reallocate ();
00115 void _mp_default_free ();
00116 #endif
00117 
00118 /* Copy NLIMBS *limbs* from SRC to DST.  */
00119 #define MPN_COPY_INCR(DST, SRC, NLIMBS) \
00120   do {                                                         \
00121     mp_size_t __i;                                             \
00122     for (__i = 0; __i < (NLIMBS); __i++)                       \
00123       (DST)[__i] = (SRC)[__i];                                        \
00124   } while (0)
00125 #define MPN_COPY_DECR(DST, SRC, NLIMBS) \
00126   do {                                                         \
00127     mp_size_t __i;                                             \
00128     for (__i = (NLIMBS) - 1; __i >= 0; __i--)                         \
00129       (DST)[__i] = (SRC)[__i];                                        \
00130   } while (0)
00131 #define MPN_COPY MPN_COPY_INCR
00132 
00133 /* Zero NLIMBS *limbs* AT DST.  */
00134 #define MPN_ZERO(DST, NLIMBS) \
00135   do {                                                         \
00136     mp_size_t __i;                                             \
00137     for (__i = 0; __i < (NLIMBS); __i++)                       \
00138       (DST)[__i] = 0;                                                 \
00139   } while (0)
00140 
00141 #define MPN_NORMALIZE(DST, NLIMBS) \
00142   do {                                                         \
00143     while (NLIMBS > 0)                                                \
00144       {                                                               \
00145        if ((DST)[(NLIMBS) - 1] != 0)                                  \
00146          break;                                                \
00147        NLIMBS--;                                               \
00148       }                                                               \
00149   } while (0)
00150 #define MPN_NORMALIZE_NOT_ZERO(DST, NLIMBS) \
00151   do {                                                         \
00152     while (1)                                                  \
00153       {                                                               \
00154        if ((DST)[(NLIMBS) - 1] != 0)                                  \
00155          break;                                                \
00156        NLIMBS--;                                               \
00157       }                                                               \
00158   } while (0)
00159 
00160 /* Initialize the MP_INT X with space for NLIMBS limbs.
00161    X should be a temporary variable, and it will be automatically
00162    cleared out when the running function returns.
00163    We use __x here to make it possible to accept both mpz_ptr and mpz_t
00164    arguments.  */
00165 #define MPZ_TMP_INIT(X, NLIMBS) \
00166   do {                                                         \
00167     mpz_ptr __x = (X);                                                \
00168     __x->_mp_alloc = (NLIMBS);                                        \
00169     __x->_mp_d = (mp_ptr) TMP_ALLOC ((NLIMBS) * BYTES_PER_MP_LIMB);   \
00170   } while (0)
00171 
00172 #define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \
00173   do {                                                         \
00174     if ((size) < KARATSUBA_THRESHOLD)                                 \
00175       impn_mul_n_basecase (prodp, up, vp, size);               \
00176     else                                                       \
00177       impn_mul_n (prodp, up, vp, size, tspace);                \
00178   } while (0);
00179 #define MPN_SQR_N_RECURSE(prodp, up, size, tspace) \
00180   do {                                                         \
00181     if ((size) < KARATSUBA_THRESHOLD)                                 \
00182       impn_sqr_n_basecase (prodp, up, size);                          \
00183     else                                                       \
00184       impn_sqr_n (prodp, up, size, tspace);                           \
00185   } while (0);
00186 
00187 /* Structure for conversion between internal binary format and
00188    strings in base 2..36.  */
00189 struct bases
00190 {
00191   /* Number of digits in the conversion base that always fits in an mp_limb_t.
00192      For example, for base 10 on a machine where a mp_limb_t has 32 bits this
00193      is 9, since 10**9 is the largest number that fits into a mp_limb_t.  */
00194   int chars_per_limb;
00195 
00196   /* log(2)/log(conversion_base) */
00197   float chars_per_bit_exactly;
00198 
00199   /* base**chars_per_limb, i.e. the biggest number that fits a word, built by
00200      factors of base.  Exception: For 2, 4, 8, etc, big_base is log2(base),
00201      i.e. the number of bits used to represent each digit in the base.  */
00202   mp_limb_t big_base;
00203 
00204   /* A BITS_PER_MP_LIMB bit approximation to 1/big_base, represented as a
00205      fixed-point number.  Instead of dividing by big_base an application can
00206      choose to multiply by big_base_inverted.  */
00207   mp_limb_t big_base_inverted;
00208 };
00209 
00210 extern const struct bases __mp_bases[];
00211 extern mp_size_t __gmp_default_fp_limb_precision;
00212 
00213 /* Divide the two-limb number in (NH,,NL) by D, with DI being the largest
00214    limb not larger than (2**(2*BITS_PER_MP_LIMB))/D - (2**BITS_PER_MP_LIMB).
00215    If this would yield overflow, DI should be the largest possible number
00216    (i.e., only ones).  For correct operation, the most significant bit of D
00217    has to be set.  Put the quotient in Q and the remainder in R.  */
00218 #define udiv_qrnnd_preinv(q, r, nh, nl, d, di) \
00219   do {                                                         \
00220     mp_limb_t _q, _ql, _r;                                     \
00221     mp_limb_t _xh, _xl;                                               \
00222     umul_ppmm (_q, _ql, (nh), (di));                                  \
00223     _q += (nh);                    /* DI is 2**BITS_PER_MP_LIMB too small */\
00224     umul_ppmm (_xh, _xl, _q, (d));                             \
00225     sub_ddmmss (_xh, _r, (nh), (nl), _xh, _xl);                       \
00226     if (_xh != 0)                                              \
00227       {                                                               \
00228        sub_ddmmss (_xh, _r, _xh, _r, 0, (d));                         \
00229        _q += 1;                                                \
00230        if (_xh != 0)                                           \
00231          {                                                     \
00232            sub_ddmmss (_xh, _r, _xh, _r, 0, (d));                     \
00233            _q += 1;                                            \
00234          }                                                     \
00235       }                                                               \
00236     if (_r >= (d))                                             \
00237       {                                                               \
00238        _r -= (d);                                              \
00239        _q += 1;                                                \
00240       }                                                               \
00241     (r) = _r;                                                  \
00242     (q) = _q;                                                  \
00243   } while (0)
00244 /* Like udiv_qrnnd_preinv, but for for any value D.  DNORM is D shifted left
00245    so that its most significant bit is set.  LGUP is ceil(log2(D)).  */
00246 #define udiv_qrnnd_preinv2gen(q, r, nh, nl, d, di, dnorm, lgup) \
00247   do {                                                         \
00248     mp_limb_t n2, n10, n1, nadj, q1;                                  \
00249     mp_limb_t _xh, _xl;                                               \
00250     n2 = ((nh) << (BITS_PER_MP_LIMB - (lgup))) + ((nl) >> 1 >> (l - 1));\
00251     n10 = (nl) << (BITS_PER_MP_LIMB - (lgup));                        \
00252     n1 = ((mp_limb_signed_t) n10 >> (BITS_PER_MP_LIMB - 1));          \
00253     nadj = n10 + (n1 & (dnorm));                               \
00254     umul_ppmm (_xh, _xl, di, n2 - n1);                                \
00255     add_ssaaaa (_xh, _xl, _xh, _xl, 0, nadj);                         \
00256     q1 = ~(n2 + _xh);                                                 \
00257     umul_ppmm (_xh, _xl, q1, d);                               \
00258     add_ssaaaa (_xh, _xl, _xh, _xl, nh, nl);                          \
00259     _xh -= (d);                                                       \
00260     (r) = _xl + ((d) & _xh);                                          \
00261     (q) = _xh - q1;                                            \
00262   } while (0)
00263 /* Exactly like udiv_qrnnd_preinv, but branch-free.  It is not clear which
00264    version to use.  */
00265 #define udiv_qrnnd_preinv2norm(q, r, nh, nl, d, di) \
00266   do {                                                         \
00267     mp_limb_t n2, n10, n1, nadj, q1;                                  \
00268     mp_limb_t _xh, _xl;                                               \
00269     n2 = (nh);                                                        \
00270     n10 = (nl);                                                       \
00271     n1 = ((mp_limb_signed_t) n10 >> (BITS_PER_MP_LIMB - 1));          \
00272     nadj = n10 + (n1 & (d));                                          \
00273     umul_ppmm (_xh, _xl, di, n2 - n1);                                \
00274     add_ssaaaa (_xh, _xl, _xh, _xl, 0, nadj);                         \
00275     q1 = ~(n2 + _xh);                                                 \
00276     umul_ppmm (_xh, _xl, q1, d);                               \
00277     add_ssaaaa (_xh, _xl, _xh, _xl, nh, nl);                          \
00278     _xh -= (d);                                                       \
00279     (r) = _xl + ((d) & _xh);                                          \
00280     (q) = _xh - q1;                                            \
00281   } while (0)
00282 
00283 #if defined (__GNUC__)
00284 /* Define stuff for longlong.h.  */
00285 typedef unsigned int UQItype       __attribute__ ((mode (QI)));
00286 typedef        int SItype   __attribute__ ((mode (SI)));
00287 typedef unsigned int USItype       __attribute__ ((mode (SI)));
00288 typedef               int DItype   __attribute__ ((mode (DI)));
00289 typedef unsigned int UDItype       __attribute__ ((mode (DI)));
00290 #else
00291 typedef unsigned char UQItype;
00292 typedef        long SItype;
00293 typedef unsigned long USItype;
00294 #endif
00295 
00296 typedef mp_limb_t UWtype;
00297 typedef unsigned int UHWtype;
00298 #define W_TYPE_SIZE BITS_PER_MP_LIMB
00299 
00300 /* Internal mpn calls */
00301 #define impn_mul_n_basecase __MPN(impn_mul_n_basecase)
00302 #define impn_mul_n          __MPN(impn_mul_n)
00303 #define impn_sqr_n_basecase __MPN(impn_sqr_n_basecase)
00304 #define impn_sqr_n          __MPN(impn_sqr_n)
00305 
00306 #ifndef _PROTO
00307 #if defined (__STDC__) || defined (__cplusplus)
00308 #define _PROTO(x) x
00309 #else
00310 #define _PROTO(x) ()
00311 #endif
00312 #endif
00313 
00314 /* Prototypes for internal mpn calls.  */
00315 extern void impn_mul_n_basecase _PROTO ((mp_ptr prodp, mp_srcptr up,
00316                                     mp_srcptr vp, mp_size_t size));
00317 extern void impn_mul_n _PROTO ((mp_ptr prodp, mp_srcptr up, mp_srcptr vp,
00318                             mp_size_t size, mp_ptr tspace));
00319 extern void impn_sqr_n_basecase _PROTO ((mp_ptr prodp, mp_srcptr up,
00320                                     mp_size_t size));
00321 extern void impn_sqr_n _PROTO ((mp_ptr prodp, mp_srcptr up, mp_size_t size,
00322                             mp_ptr tspace));
00323 
00324 
00325 
00326 #ifndef IEEE_DOUBLE_BIG_ENDIAN
00327 #define IEEE_DOUBLE_BIG_ENDIAN 1
00328 #endif
00329 
00330 #ifndef IEEE_DOUBLE_MIXED_ENDIAN
00331 #define IEEE_DOUBLE_MIXED_ENDIAN 0
00332 #endif
00333 
00334 #if IEEE_DOUBLE_MIXED_ENDIAN
00335 union ieee_double_extract
00336 {
00337   struct
00338     {
00339       unsigned int manh:20;
00340       unsigned int exp:11;
00341       unsigned int sig:1;
00342       unsigned int manl:32;
00343     } s;
00344   double d;
00345 };
00346 #else
00347 #if IEEE_DOUBLE_BIG_ENDIAN
00348 union ieee_double_extract
00349 {
00350   struct
00351     {
00352       unsigned int sig:1;
00353       unsigned int exp:11;
00354       unsigned int manh:20;
00355       unsigned int manl:32;
00356     } s;
00357   double d;
00358 };
00359 #else
00360 union ieee_double_extract
00361 {
00362   struct
00363     {
00364       unsigned int manl:32;
00365       unsigned int manh:20;
00366       unsigned int exp:11;
00367       unsigned int sig:1;
00368     } s;
00369   double d;
00370 };
00371 #endif
00372 #endif