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