1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
|
// file kernel/n/h/numerix.h: natural integer definitions
/*-----------------------------------------------------------------------+
| Copyright 2005-2006, Michel Quercia (michel.quercia@prepas.org) |
| |
| This file is part of Numerix. Numerix is free software; you can |
| redistribute it and/or modify it under the terms of the GNU Lesser |
| General Public License as published by the Free Software Foundation; |
| either version 2.1 of the License, or (at your option) any later |
| version. |
| |
| The Numerix Library is distributed in the hope that it will be |
| useful, but WITHOUT ANY WARRANTY; without even the implied warranty |
| of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| Lesser General Public License for more details. |
| |
| You should have received a copy of the GNU Lesser General Public |
| License along with the GNU MP Library; see the file COPYING. If not, |
| write to the Free Software Foundation, Inc., 59 Temple Place - |
| Suite 330, Boston, MA 02111-1307, USA. |
+-----------------------------------------------------------------------+
| |
| Dfinitions pour la couche n |
| |
+-----------------------------------------------------------------------*/
/* fichier de configuration spcifique la machine cible */
#include "../../config.h"
/* options de compilation :
bits_32 -> architecture 32 bits
bits_64 -> architecture 64 bits
use_clong -> arithmtique en C, un chiffre = 1/2 mot
use_dlong -> arithmtique en C, un chiffre = 1 mot
use_slong -> arithmtique en C et assembleur, un chiffre = 1 mot
have_long_long -> utiliser le type long long pour les modes dlong/slong
*/
/* +-------------------------+
| Contrle de cohrence |
+-------------------------+ */
#if defined(bits_32) + defined(bits_64) < 1
#error "missing bits_xx definition"
#elif defined(bits_32) + defined(bits_64) > 1
#error "multiple bits_xx definitions"
#endif
/* mode = clong ou bien dlong ou bien slong */
#if defined(use_clong) + defined(use_dlong) + defined(use_slong) < 1
#error "missing use_xlong definition"
#elif defined(use_clong) + defined(use_dlong) + defined(use_slong) > 1
#error "multiple use_xlong definitions"
#endif /* use_xlong */
#ifdef bits_32
/* +------------------------+
| Architecture 32 bits |
+------------------------+ */
#define SIGN_m 0x80000000L /* masque bit de signe */
#define LONG_m 0x7fffffffL /* masque mot de longueur */
#ifdef use_clong
#define chiffres_per_long 2 /* conversion de longueur */
#define HW 16 /* bits par chiffre */
#define hw 4 /* log_2(HW) */
#define BASE_2 0x8000L /* base de numration/2 */
#define LMAX 0x20000000L /* longueur maximale */
#define chiffre unsigned short /* un chiffre */
#else
#define chiffres_per_long 1 /* conversion de longueur */
#define HW 32 /* bits par chiffre */
#define hw 5 /* log_2(HW) */
#define BASE_2 0x80000000L /* base de numration/2 */
#define LMAX 0x10000000L /* longueur maximale */
#define chiffre unsigned long /* un chiffre */
#endif /* use_clong */
#endif /* bits_32 */
#ifdef bits_64
/* +------------------------+
| Architecture 64 bits |
+------------------------+ */
#define SIGN_m 0x8000000000000000L /* masque bit de signe */
#define LONG_m 0x7fffffffffffffffL /* masque mot de longueur */
#ifdef use_clong
#define chiffres_per_long 2 /* conversion de longueur */
#define HW 32 /* bits par chiffre */
#define hw 5 /* log_2(HW) */
#define BASE_2 0x80000000L /* base de numration/2 */
#define LMAX 0x1000000000000000L /* longueur maximale */
#define chiffre unsigned int /* un chiffre */
#else
#define chiffres_per_long 1 /* conversion de longueur */
#define HW 64 /* bits par chiffre */
#define hw 6 /* log_2(HW) */
#define BASE_2 0x8000000000000000L /* base de numration/2 */
#define LMAX 0x800000000000000L /* longueur maximale */
#define chiffre unsigned long /* un chiffre */
#endif /* use_clong */
#endif /* bits_64 */
/* +--------------------+
| Double prcision |
+--------------------+ */
#if defined(use_clong)
#define ndouble unsigned long /* entier double non sign */
#define zdouble long /* entier double sign */
#elif defined(have_long_long)
#define ndouble unsigned long long /* entier double non sign */
#define zdouble long long /* entier double sign */
#else
#undef ndouble /* arithmtique double */
#undef zdouble /* prcision indisponible */
#endif
/* +-----------------------------------+
| prfixe des fonctions publiques |
+-----------------------------------+ */
#if defined(use_clong)
#define xn(nom) cn_##nom
#define xx(nom) cx_##nom
#elif defined(use_dlong)
#define xn(nom) dn_##nom
#define xx(nom) dx_##nom
#elif defined(use_slong)
#define xn(nom) sn_##nom
#define xx(nom) sx_##nom
#endif
/* include standards */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
/* +-----------------------+
| Liste des fonctions |
+-----------------------+ */
/*
dump.h doit tre lu en premier pour avoir le prototype de xn(internal_error)
Les autres fichiers peuvent tre chargs dans un ordre quelconque, ici
ils sont regroups par catgorie d'oprations
*/
#include "dump.h"
/* allocation mmoire */
#include "alloc.h"
/* addition/soustraction */
#include "add.h"
/* multiplication/carr */
#include "mul_n2.h"
#include "karatsuba.h"
#include "toom.h"
/* oprations modulo BASE^n +/- 1 */
#include "mmod.h"
#include "smod.h"
/* transformation de Fourier */
#include "fft.h"
#include "fftmul.h"
/* division/racine carre */
#include "div_n2.h"
#include "sqrt_n2.h"
#include "burnikel.h"
#include "zimmermann.h"
#include "moddiv.h"
#include "karp.h"
/* exponentiation */
#include "pow.h"
#include "powmod.h"
#include "montgomery.h"
/* pgcd */
#include "gcd.h"
/* test de primalit */
#include "prime.h"
/* divers */
#include "cmp.h"
#include "shift.h"
#include "random.h"
/* +-----------------------------------------------------------+
| Aiguillage des oprations selon la taille des oprandes |
+-----------------------------------------------------------+ */
extern inline void xn(mul)(chiffre *a, long la, chiffre *b, long lb, chiffre *c) {
(lb <= karamul_lim) ? xn(mul_n2)(a,la,b,lb,c) : xn(fftmul)(a,la,b,lb,c);
}
extern inline void xn(sqr)(chiffre *a, long la, chiffre *c) {
(la <= karasqr_lim) ? xn(sqr_n2)(a,la,c) : xn(fftsqr)(a,la,c);
}
extern inline void xn(div)(chiffre *a, long la, chiffre *b, long lb, chiffre *c) {
(lb <= burnidiv_lim) ? xn(div_n2) (a,la,b,lb,c) : xn(karpdiv)(a,la,b,lb,c,1);
}
|
