1 #ifndef MPFQ_H_
2 #define MPFQ_H_
3
4 /* This header contains common declarations used by mpfq modules */
5
6 /* we always include stdio.h, otherwise our inclusion of gmp.h might
7 * prevent gmp's I/O functions to ever be exposed... */
8 #include <stdio.h>
9 #include <stdlib.h>
10 #include <string.h>
11 #include <gmp.h>
12
13 #ifdef __cplusplus
14 extern "C" {
15 #endif
16
17
18
19 /*** Constants for field_specify ***/
20
21 #define MPFQ_DONE 0 /* At the end of the variadic option functions */
22 #define MPFQ_PRIME_MPN 1 /* mp_limb_t *, size depending on implementation. Prefer MPFQ_PRIME_MPZ */
23 #define MPFQ_POLYNOMIAL 2 /* this expects an mpfq polynomial */
24 #define MPFQ_DEGREE 3 /* int */
25 #define MPFQ_IO_TYPE 4 /* for setopt */
26 #define MPFQ_SIMD_GROUPSIZE 5 /* int (SIMD group size) */
27 #define MPFQ_GROUPSIZE 5 /* (for compatibility, just in case) */
28 #define MPFQ_PRIME_MPZ 6 /* mpz_t */
29 #define MPFQ_MANDATORY_TAG 7 /* force the tag to be this one ; this is
30 * of course pointless for the low-level
31 * implementation, but
32 * mpfq_vbase_oo_field_init_byfeatures
33 * uses it. */
34
35 #define BUILD_BITMASK(x) ((x) == GMP_LIMB_BITS ? ((mp_limb_t) - 1) : (~ - ((mp_limb_t) 1 << (x))))
36
37 #define LEXGE2(X,Y,A,B) (X>A || (X == A && Y >= B))
38 #define LEXGE3(X,Y,Z,A,B,C) (X>A || (X == A && LEXGE2(Y,Z,B,C)))
39 #define LEXLE2(X,Y,A,B) LEXGE2(A,B,X,Y)
40 #define LEXLE3(X,Y,Z,A,B,C) LEXGE3(A,B,C,X,Y,Z)
41
42 #ifndef GMP_VERSION_ATLEAST
43 #ifndef __GNU_MP_VERSION
44 #define GMP_VERSION_ATLEAST(X,Y,Z) 0
45 #else
46 #define GMP_VERSION_ATLEAST(X,Y,Z) \
47 LEXGE3(__GNU_MP_VERSION,__GNU_MP_VERSION_MINOR,__GNU_MP_VERSION_PATCHLEVEL,X,Y,Z)
48 #endif
49 #endif
50
51 #ifndef GMP_VERSION_ATMOST
52 #ifndef __GNU_MP_VERSION
53 #define GMP_VERSION_ATMOST(X,Y,Z) 1
54 #else
55 #define GMP_VERSION_ATMOST(X,Y,Z) \
56 LEXLE3(__GNU_MP_VERSION,__GNU_MP_VERSION_MINOR,__GNU_MP_VERSION_PATCHLEVEL,X,Y,Z)
57 #endif
58 #endif
59
60 #ifndef GNUC_VERSION
61 #ifndef __GNUC__
62 #define GNUC_VERSION(X,Y,Z) 0
63 #else
64 #define GNUC_VERSION(X,Y,Z) \
65 (__GNUC__ == X && __GNUC_MINOR__ == Y && __GNUC_PATCHLEVEL__ == Z)
66 #endif
67 #endif
68
69 #ifndef GNUC_VERSION_ATLEAST
70 #ifndef __GNUC__
71 #define GNUC_VERSION_ATLEAST(X,Y,Z) 0
72 #else
73 #define GNUC_VERSION_ATLEAST(X,Y,Z) \
74 LEXGE3(__GNUC__,__GNUC_MINOR__,__GNUC_PATCHLEVEL__,X,Y,Z)
75 #endif
76 #endif
77
78 #ifndef GNUC_VERSION_ATMOST
79 #ifndef __GNUC__
80 #define GNUC_VERSION_ATMOST(X,Y,Z) 0
81 #else
82 #define GNUC_VERSION_ATMOST(X,Y,Z) \
83 LEXLE3(__GNUC__,__GNUC_MINOR__,__GNUC_PATCHLEVEL__,X,Y,Z)
84 #endif
85 #endif
86
87 /* typedef unsigned long ulong; */
88
89 #ifndef MAX
90 #define MAX(h,i) ((h) > (i) ? (h) : (i))
91 #endif
92
93 #ifndef MIN
94 #define MIN(l,o) ((l) < (o) ? (l) : (o))
95 #endif
96
97 #ifndef __cplusplus
98 #ifndef max
99 #define max(a,b) ((a) > (b) ? (a) : (b))
100 #endif
101
102 #ifndef min
103 #define min(a,b) ((a) < (b) ? (a) : (b))
104 #endif
105 #endif /* __cplusplus */
106
107
108 #ifndef ABS
109 #define ABS(x) ((x) >= 0 ? (x) : -(x))
110 #endif
111
112 #if GNUC_VERSION_ATLEAST(3,4,0)
113 /* according to
114 * http://gcc.gnu.org/onlinedocs/gcc-3.1.1/gcc/Variable-Attributes.html#Variable%20Attributes
115 * the 'unused' attribute already existed in 3.1.1 ; however the rules
116 * for its usage remained quirky until 3.4.0, so we prefer to stick to
117 * the more modern way of using the unused attribute, and recommend
118 * setting the -Wno-unused flag for pre-3.4 versions of gcc
119 */
120 #ifndef MAYBE_UNUSED
121 #define MAYBE_UNUSED __attribute__((unused))
122 #endif
123 #endif
124
125 #if GNUC_VERSION_ATLEAST(3,1,0) /* apparently */
126 #ifndef MPFQ_EXPECT
127 #define MPFQ_EXPECT(x,val) __builtin_expect(x,val)
128 #endif
129 #endif
130
131 #if GNUC_VERSION_ATLEAST(3,4,0)
132 #define mpfq_clzl(x) __builtin_clzl(x)
133 #define mpfq_ctzl(x) __builtin_ctzl(x)
134 #define mpfq_parityl(x) __builtin_parityl(x)
135 #else
136 /* provide slow fallbacks */
137 static inline int mpfq_clzl(unsigned long x)
138 {
139 static const int t[4] = { 2, 1, 0, 0 };
140 int a = 0;
141 int res;
142 #if (GMP_LIMB_BITS == 64)
143 if (x >> 32) { a += 32; x >>= 32; }
144 #endif
145 if (x >> 16) { a += 16; x >>= 16; }
146 if (x >> 8) { a += 8; x >>= 8; }
147 if (x >> 4) { a += 4; x >>= 4; }
148 if (x >> 2) { a += 2; x >>= 2; }
149 res = GMP_LIMB_BITS - 2 - a + t[x];
150 return res;
151 }
152 static inline int mpfq_ctzl(unsigned long x)
153 {
154 return GMP_LIMB_BITS - mpfq_clzl(x & - x);
155 }
156 static inline int mpfq_parityl(unsigned long x)
157 {
158 static const int t[4] = { 0, 1, 1, 0, };
159 #if (GMP_LIMB_BITS == 64)
160 x ^= (x >> 32);
161 #endif
162 x ^= (x >> 16);
163 x ^= (x >> 8);
164 x ^= (x >> 4);
165 x ^= (x >> 2);
166 return t[x & 3UL];
167 }
168 #endif
169
170 #ifndef MAYBE_UNUSED
171 #define MAYBE_UNUSED /**/
172 #endif
173
174 #ifndef MPFQ_EXPECT
175 #define MPFQ_EXPECT(x,val) (x)
176 #endif
177
178 #ifndef MPFQ_UNLIKELY
179 #define MPFQ_UNLIKELY(x) MPFQ_EXPECT(x, 0)
180 #endif
181 #ifndef MPFQ_LIKELY
182 #define MPFQ_LIKELY(x) MPFQ_EXPECT(x, 1)
183 #endif
184
185 /* This macro is used to guard against some trivial false positives
186 * returned by static analyzer */
187 #if defined(__COVERITY__)
188 #define ASSERT_FOR_STATIC_ANALYZER(x) do { \
189 if (!(x)) { \
190 abort(); \
191 } \
192 } while (0)
193 #else
194 #define ASSERT_FOR_STATIC_ANALYZER(x)
195 #endif
196
197
mpfq_clzlx(unsigned long * x,int n)198 static inline int mpfq_clzlx(unsigned long * x, int n)
199 {
200 int r = 0;
201 for( ; n > 0 && MPFQ_UNLIKELY(!x[n-1]) ; --n) r+=GMP_LIMB_BITS;
202 if (n == 0) return r;
203 r += mpfq_clzl(x[n-1]);
204 return r;
205 }
206
mpfq_ctzlx(unsigned long * x,int n)207 static inline int mpfq_ctzlx(unsigned long * x, int n)
208 {
209 int r = 0;
210 for( ; n > 0 && MPFQ_UNLIKELY(!*x) ; --n,++x) r+=GMP_LIMB_BITS;
211 if (n == 0) return r;
212 r += mpfq_ctzl(*x);
213 return r;
214 }
215
216 /*** Some useful macros ***/
217
218 /* use these only for the large malloc()s, please */
mpfq_malloc_check(size_t s)219 static inline void * mpfq_malloc_check(size_t s) {
220 void * r = malloc(s);
221 #ifdef MPFQ_TRACK_MALLOC
222 if (s>>28) { fprintf(stderr, "MALLOC(%.1f)\n", s/1048576.); }
223 #endif
224 if (!r) {
225 fprintf(stderr, "malloc(%zu) failed\n", s);
226 abort();
227 }
228 return r;
229 }
230
mpfq_realloc_check(void * p,size_t os,size_t s)231 static inline void * mpfq_realloc_check(void * p, size_t os, size_t s) {
232 void * r = realloc(p, s);
233 #ifdef MPFQ_TRACK_MALLOC
234 if (s>>28) { fprintf(stderr, "REALLOC(%.1f, %.1f)\n", os/1048576., s/1048576.); }
235 #endif
236 if (s && !r) {
237 fprintf(stderr, "realloc(%zu, %zu) failed\n", os, s);
238 abort();
239 }
240 return r;
241 }
242
mpfq_free(void * p,size_t s MAYBE_UNUSED)243 static inline void mpfq_free(void * p, size_t s MAYBE_UNUSED)
244 {
245 #ifdef MPFQ_TRACK_MALLOC
246 if (s>>28) { fprintf(stderr, "FREE(%.1f)\n", s/1048576.); }
247 #endif
248 free(p);
249 }
250
malloc_failed()251 static inline void malloc_failed() {
252 fprintf(stderr, "malloc() failed\n");
253 abort();
254 }
255
256
257 /* Given the fact that copies are always very small, we're probably
258 * better off giving the compiler the opportunity to optimize all this
259 * away.
260 */
261
262 /* dst and src known to not overlap, except possibly if dst == src */
mpfq_copy(mp_limb_t * dst,const mp_limb_t * src,mp_size_t n)263 static inline void mpfq_copy(mp_limb_t * dst, const mp_limb_t * src, mp_size_t n) {
264 // if (dst != src) mpn_copyi(dst, src, n);
265 for( ; n-- ; ) *dst++ = *src++;
266 }
267
268 /* dst and src possibly overlap, copy increasingly so that src >= dst is ok */
mpfq_copyi(mp_limb_t * dst,const mp_limb_t * src,mp_size_t n)269 static inline void mpfq_copyi(mp_limb_t * dst, const mp_limb_t * src, mp_size_t n) {
270 // mpn_copyi(dst, src, n);
271 for( ; n-- ; ) *dst++ = *src++;
272 }
273
274 /* dst and src possibly overlap, copy decreasingly so that src <= dst is ok */
mpfq_copyd(mp_limb_t * dst,const mp_limb_t * src,mp_size_t n)275 static inline void mpfq_copyd(mp_limb_t * dst, const mp_limb_t * src, mp_size_t n) {
276 // mpn_copyd(dst, src, n);
277 for(dst += n, src += n ; n-- ; ) *--dst = *--src;
278 }
279
mpfq_zero(mp_limb_t * dst,mp_size_t n)280 static inline void mpfq_zero(mp_limb_t * dst, mp_size_t n) {
281 // mpn_zero(dst, 0, n);
282 for( ; n-- ; ) *dst++ = 0;
283 }
284
285
286
287 #ifdef __cplusplus
288 }
289 #endif
290
291 #endif /* MPFQ_H_ */
292