1 /* Test mpn_fib2m.
2
3 Copyright 2018 Free Software Foundation, Inc.
4
5 This file is part of the GNU MP Library test suite.
6
7 The GNU MP Library test suite is free software; you can redistribute it
8 and/or modify it under the terms of the GNU General Public License as
9 published by the Free Software Foundation; either version 3 of the License,
10 or (at your option) any later version.
11
12 The GNU MP Library test suite is distributed in the hope that it will be
13 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
15 Public License for more details.
16
17 You should have received a copy of the GNU General Public License along with
18 the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */
19
20 #include <stdio.h>
21 #include <stdlib.h>
22
23 #include "gmp-impl.h"
24 #include "tests.h"
25
26 #define MAX_K_BITS 16
27 #define MAX_K (1L << MAX_K_BITS)
28 #define MIN_K 1
29
30 #define MAX_MN 20
31 #define MAX_KN 30
32
33 #define COUNT 200
34
35 static int
test_fib2_fib2m(int count,gmp_randstate_ptr rands)36 test_fib2_fib2m (int count, gmp_randstate_ptr rands)
37 {
38 int test;
39 mp_ptr fk, fks1, fkm, fks1m, mp, qp;
40 mp_size_t mn, fn, size, max_mn;
41 TMP_DECL;
42
43 size = MPN_FIB2_SIZE (MAX_K);
44 max_mn = size / 4 + 10;
45 ASSERT (max_mn < size);
46
47 TMP_MARK;
48 fk = TMP_ALLOC_LIMBS (size);
49 fks1 = TMP_ALLOC_LIMBS (size);
50 qp = TMP_ALLOC_LIMBS (size);
51 mp = TMP_ALLOC_LIMBS (max_mn);
52 fkm = 1 + TMP_ALLOC_LIMBS (max_mn * 2 + 1 + 2);
53 fks1m = 1 + TMP_ALLOC_LIMBS (max_mn * 2 + 1 + 2);
54
55 for (test = 1; test <= count; ++test)
56 {
57 mp_limb_t fk_before, fk_after, fk1_before, fk1_after;
58 int signflip;
59 unsigned long k;
60
61 k = MIN_K +
62 gmp_urandomm_ui (rands, test < MAX_K_BITS ?
63 MAX_K >> test : (MAX_K - MIN_K));
64
65 fn = mpn_fib2_ui (fk, fks1, k);
66 do {
67 mn = gmp_urandomm_ui (rands, MAX_K) % (fn / 4 + 10);
68 } while (mn == 0);
69 ASSERT (mn <= max_mn);
70 mpn_random2 (mp, mn);
71 ASSERT (mp [mn - 1] != 0);
72
73 if (fn >= mn)
74 {
75 mpn_tdiv_qr (qp, fk, 0, fk, fn, mp, mn);
76 mpn_tdiv_qr (qp, fks1, 0, fks1, fn, mp, mn);
77 }
78 else
79 {
80 MPN_ZERO (fk + fn, mn - fn);
81 MPN_ZERO (fks1 + fn, mn - fn);
82 }
83
84 mpn_random2 (fkm - 1, 2*mn+1+2);
85 fk_before = fkm [-1];
86 fk_after = fkm [2 * mn + 1];
87
88 mpn_random2 (fks1m - 1, 2*mn+1+2);
89 fk1_before = fks1m [-1];
90 fk1_after = fks1m [2 * mn + 1];
91
92 qp [0] = k;
93 signflip = mpn_fib2m (fkm, fks1m, qp, 1, mp, mn);
94 if (fkm [-1] != fk_before || fkm [2 * mn + 1] != fk_after
95 || fks1m [-1] != fk1_before || fks1m [2 * mn + 1] != fk1_after)
96 {
97 printf ("REDZONE violation in test %d, k = %lu, mn = %u\n",
98 test, k, (unsigned) mn);
99 if (fkm[-1] != fk_before)
100 {
101 printf ("before fkm:"); mpn_dump (fkm - 1, 1);
102 printf ("keep: "); mpn_dump (&fk_before, 1);
103 }
104 if (fkm[2 * mn + 1] != fk_after)
105 {
106 printf ("after fkm:"); mpn_dump (fkm + 2 * mn + 1, 1);
107 printf ("keep: "); mpn_dump (&fk_after, 1);
108 }
109 if (fks1m[-1] != fk1_before)
110 {
111 printf ("before fks1m:"); mpn_dump (fks1m - 1, 1);
112 printf ("keep: "); mpn_dump (&fk1_before, 1);
113 }
114 if (fks1m[2 * mn + 1] != fk1_after)
115 {
116 printf ("after fks1m:"); mpn_dump (fks1m + 2 * mn + 1, 1);
117 printf ("keep: "); mpn_dump (&fk1_after, 1);
118 }
119 abort();
120 }
121
122 if (mpn_cmp (fkm, fk, mn) != 0)
123 {
124 if (mpn_sub_n (fk, mp, fk, mn) || mpn_cmp (fkm, fk, mn) != 0)
125 {
126 printf ("ERROR(k) in test %d, k = %lu, mn = %u\n",
127 test, k, (unsigned) mn);
128 mpn_dump (fk, mn);
129 mpn_dump (fkm, mn);
130 mpn_dump (mp, mn);
131 abort();
132 }
133 signflip ^= 1;
134 }
135
136 if (mpn_cmp (fks1m, fks1, mn) != 0)
137 {
138 if (mpn_sub_n (fks1, mp, fks1, mn) || mpn_cmp (fks1m, fks1, mn) != 0)
139 {
140 printf ("ERROR(k-1) in test %d, k = %lu, mn = %u\n",
141 test, k, (unsigned) mn);
142 mpn_dump (fks1, mn);
143 mpn_dump (fks1m, mn);
144 mpn_dump (mp, mn);
145 abort();
146 }
147 signflip ^= 1;
148 }
149
150 if (signflip != 0 && ! mpn_zero_p (fks1m, mn) && ! mpn_zero_p (fkm, mn))
151 {
152 if ((mp [0] & 1) == 0) /* Should we test only odd modulus-es? */
153 {
154 if (! mpn_lshift (fks1m, fks1m, mn, 1) &&
155 mpn_cmp (mp, fks1m, mn) == 0)
156 continue;
157 if (! mpn_lshift (fkm, fkm, mn, 1) &&
158 mpn_cmp (mp, fkm, mn) == 0)
159 continue;
160 }
161 printf ("ERROR(sign) in test %d, k = %lu, mn = %u\n",
162 test, k, (unsigned) mn);
163 abort();
164 }
165 }
166 TMP_FREE;
167 return 0;
168 }
169
170 static int
test_fib2m_2exp(int count,gmp_randstate_ptr rands)171 test_fib2m_2exp (int count, gmp_randstate_ptr rands)
172 {
173 int test;
174 mp_ptr fka, fks1a, fkb, fks1b, mp, kp;
175 TMP_DECL;
176
177 TMP_MARK;
178 kp = TMP_ALLOC_LIMBS (MAX_KN);
179 mp = TMP_ALLOC_LIMBS (MAX_MN);
180 fka = 1 + TMP_ALLOC_LIMBS (MAX_MN * 2 + 1 + 2);
181 fks1a = 1 + TMP_ALLOC_LIMBS (MAX_MN * 2 + 1 + 2);
182 fkb = 1 + TMP_ALLOC_LIMBS (MAX_MN * 2 + 1 + 2);
183 fks1b = 1 + TMP_ALLOC_LIMBS (MAX_MN * 2 + 1 + 2);
184
185 for (test = 1; test <= count; ++test)
186 {
187 mp_limb_t fka_before, fka_after, fk1a_before, fk1a_after;
188 mp_limb_t fkb_before, fkb_after, fk1b_before, fk1b_after;
189 mp_size_t mn, kn;
190 int signflip;
191 mp_bitcnt_t exp2;
192
193 mn = gmp_urandomm_ui (rands, MAX_MN - 1) + 1;
194 mpn_random2 (mp, mn);
195
196 exp2 = MIN_K + 1 + gmp_urandomm_ui (rands, MAX_KN * GMP_NUMB_BITS - MIN_K - 1);
197
198 kn = BITS_TO_LIMBS (exp2);
199 MPN_ZERO (kp, kn - 1);
200 kp [kn - 1] = CNST_LIMB (1) << ((exp2 - 1) % GMP_NUMB_BITS);
201
202 mpn_random2 (fka - 1, 2*mn+1+2);
203 fka_before = fka [-1];
204 fka_after = fka [2 * mn + 1];
205
206 mpn_random2 (fks1a - 1, 2*mn+1+2);
207 fk1a_before = fks1a [-1];
208 fk1a_after = fks1a [2 * mn + 1];
209
210 signflip = mpn_fib2m (fka, fks1a, kp, kn, mp, mn);
211 if (fka [-1] != fka_before || fka [2 * mn + 1] != fka_after
212 || fks1a [-1] != fk1a_before || fks1a [2 * mn + 1] != fk1a_after)
213 {
214 printf ("REDZONE(a) violation in test %d, exp2 = %lu\n", test, exp2);
215 if (fka[-1] != fka_before)
216 {
217 printf ("before fka:"); mpn_dump (fka - 1, 1);
218 printf ("keep: "); mpn_dump (&fka_before, 1);
219 }
220 if (fka[2 * mn + 1] != fka_after)
221 {
222 printf ("after fka:"); mpn_dump (fka + 2 * mn + 1, 1);
223 printf ("keep: "); mpn_dump (&fka_after, 1);
224 }
225 if (fks1a[-1] != fk1a_before)
226 {
227 printf ("before fks1a:"); mpn_dump (fks1a - 1, 1);
228 printf ("keep: "); mpn_dump (&fk1a_before, 1);
229 }
230 if (fks1a[2 * mn + 1] != fk1a_after)
231 {
232 printf ("after fks1a:"); mpn_dump (fks1a + 2 * mn + 1, 1);
233 printf ("keep: "); mpn_dump (&fk1a_after, 1);
234 }
235 abort();
236 }
237
238 if (signflip && ! mpn_zero_p (fks1a, mn))
239 mpn_sub_n (fks1a, mp, fks1a, mn);
240 if (mpn_sub_n (fka, fka, fks1a, mn))
241 ASSERT_CARRY (mpn_add_n (fka, fka, mp, mn));
242
243 mpn_sub_1 (kp, kp, kn, 1);
244 ASSERT (exp2 % GMP_NUMB_BITS == 1 || kp [kn - 1] != 0);
245 kn -= kp [kn - 1] == 0;
246
247 mpn_random2 (fkb - 1, 2*mn+1+2);
248 fkb_before = fkb [-1];
249 fkb_after = fkb [2 * mn + 1];
250
251 mpn_random2 (fks1b - 1, 2*mn+1+2);
252 fk1b_before = fks1b [-1];
253 fk1b_after = fks1b [2 * mn + 1];
254
255 signflip = mpn_fib2m (fkb, fks1b, kp, kn, mp, mn);
256 if (fkb [-1] != fkb_before || fkb [2 * mn + 1] != fkb_after
257 || fks1b [-1] != fk1b_before || fks1b [2 * mn + 1] != fk1b_after)
258 {
259 printf ("REDZONE(b) violation in test %d, exp2 = %lu\n", test, exp2);
260 if (fkb[-1] != fkb_before)
261 {
262 printf ("before fkb:"); mpn_dump (fkb - 1, 1);
263 printf ("keep: "); mpn_dump (&fkb_before, 1);
264 }
265 if (fkb[2 * mn + 1] != fkb_after)
266 {
267 printf ("after fkb:"); mpn_dump (fkb + 2 * mn + 1, 1);
268 printf ("keep: "); mpn_dump (&fkb_after, 1);
269 }
270 if (fks1b[-1] != fk1b_before)
271 {
272 printf ("before fks1b:"); mpn_dump (fks1b - 1, 1);
273 printf ("keep: "); mpn_dump (&fk1b_before, 1);
274 }
275 if (fks1b[2 * mn + 1] != fk1b_after)
276 {
277 printf ("after fks1b:"); mpn_dump (fks1b + 2 * mn + 1, 1);
278 printf ("keep: "); mpn_dump (&fk1b_after, 1);
279 }
280 abort();
281 }
282
283 if (mpn_cmp (fks1a, fkb, mn) != 0)
284 {
285 if (mpn_sub_n (fkb, mp, fkb, mn) || mpn_cmp (fks1a, fkb, mn) != 0)
286 {
287 printf ("ERROR(k) in test %d, exp2 = %lu\n", test, exp2);
288 mpn_dump (fks1a, mn);
289 mpn_dump (fkb, mn);
290 mpn_dump (mp, mn);
291 abort();
292 }
293 signflip ^= 1;
294 }
295
296 if (mpn_cmp (fka, fks1b, mn) != 0)
297 {
298 if (mpn_sub_n (fks1b, mp, fks1b, mn) || mpn_cmp (fka, fks1b, mn) != 0)
299 {
300 printf ("ERROR(k-1) in test %d, exp2 = %lu\n", test, exp2);
301 mpn_dump (fka, mn);
302 mpn_dump (fks1b, mn);
303 mpn_dump (mp, mn);
304 abort();
305 }
306 signflip ^= 1;
307 }
308
309 if (signflip != 0 && ! mpn_zero_p (fks1b, mn) && ! mpn_zero_p (fkb, mn))
310 {
311 if ((mp [0] & 1) == 0) /* Should we test only odd modulus-es? */
312 {
313 if (! mpn_lshift (fks1b, fks1b, mn, 1) &&
314 mpn_cmp (mp, fks1b, mn) == 0)
315 continue;
316 if (! mpn_lshift (fkb, fkb, mn, 1) &&
317 mpn_cmp (mp, fkb, mn) == 0)
318 continue;
319 }
320 printf ("ERROR(sign) in test %d, exp2 = %lu\n",
321 test, exp2);
322 abort();
323 }
324 }
325 TMP_FREE;
326 return 0;
327 }
328
329 int
main(int argc,char ** argv)330 main (int argc, char **argv)
331 {
332 int count = COUNT;
333 gmp_randstate_ptr rands;
334
335 tests_start ();
336 TESTS_REPS (count, argv, argc);
337 rands = RANDS;
338
339 test_fib2_fib2m (count / 2, rands);
340 test_fib2m_2exp (count / 2, rands);
341
342 tests_end ();
343 exit (0);
344 }
345