1 /* Run some tests on various mpn routines.
2
3 THIS IS A TEST PROGRAM USED ONLY FOR DEVELOPMENT. IT'S ALMOST CERTAIN TO
4 BE SUBJECT TO INCOMPATIBLE CHANGES IN FUTURE VERSIONS OF GMP.
5
6 Copyright 2000-2006, 2008, 2009, 2011, 2012 Free Software Foundation, Inc.
7
8 This file is part of the GNU MP Library test suite.
9
10 The GNU MP Library test suite is free software; you can redistribute it
11 and/or modify it under the terms of the GNU General Public License as
12 published by the Free Software Foundation; either version 3 of the License,
13 or (at your option) any later version.
14
15 The GNU MP Library test suite is distributed in the hope that it will be
16 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
18 Public License for more details.
19
20 You should have received a copy of the GNU General Public License along with
21 the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */
22
23
24 /* Usage: try [options] <function>...
25
26 For example, "./try mpn_add_n" to run tests of that function.
27
28 Combinations of alignments and overlaps are tested, with redzones above
29 or below the destinations, and with the sources write-protected.
30
31 The number of tests performed becomes ridiculously large with all the
32 combinations, and for that reason this can't be a part of a "make check",
33 it's meant only for development. The code isn't very pretty either.
34
35 During development it can help to disable the redzones, since seeing the
36 rest of the destination written can show where the wrong part is, or if
37 the dst pointers are off by 1 or whatever. The magic DEADVAL initial
38 fill (see below) will show locations never written.
39
40 The -s option can be used to test only certain size operands, which is
41 useful if some new code doesn't yet support say sizes less than the
42 unrolling, or whatever.
43
44 When a problem occurs it'll of course be necessary to run the program
45 under gdb to find out quite where, how and why it's going wrong. Disable
46 the spinner with the -W option when doing this, or single stepping won't
47 work. Using the "-1" option to run with simple data can be useful.
48
49 New functions to test can be added in try_array[]. If a new TYPE is
50 required then add it to the existing constants, set up its parameters in
51 param_init(), and add it to the call() function. Extra parameter fields
52 can be added if necessary, or further interpretations given to existing
53 fields.
54
55
56 Portability:
57
58 This program is not designed for use on Cray vector systems under Unicos,
59 it will fail to compile due to missing _SC_PAGE_SIZE. Those systems
60 don't really have pages or mprotect. We could arrange to run the tests
61 without the redzones, but we haven't bothered currently.
62
63
64 Enhancements:
65
66 umul_ppmm support is not very good, lots of source data is generated
67 whereas only two limbs are needed.
68
69 Make a little scheme for interpreting the "SIZE" selections uniformly.
70
71 Make tr->size==SIZE_2 work, for the benefit of find_a which wants just 2
72 source limbs. Possibly increase the default repetitions in that case.
73
74 Automatically detect gdb and disable the spinner (use -W for now).
75
76 Make a way to re-run a failing case in the debugger. Have an option to
77 snapshot each test case before it's run so the data is available if a
78 segv occurs. (This should be more reliable than the current print_all()
79 in the signal handler.)
80
81 When alignment means a dst isn't hard against the redzone, check the
82 space in between remains unchanged.
83
84 When a source overlaps a destination, don't run both s[i].high 0 and 1,
85 as s[i].high has no effect. Maybe encode s[i].high into overlap->s[i].
86
87 When partial overlaps aren't done, don't loop over source alignments
88 during overlaps.
89
90 Try to make the looping code a bit less horrible. Right now it's pretty
91 hard to see what iterations are actually done.
92
93 Perhaps specific setups and loops for each style of function under test
94 would be clearer than a parameterized general loop. There's lots of
95 stuff common to all functions, but the exceptions get messy.
96
97 When there's no overlap, run with both src>dst and src<dst. A subtle
98 calling-conventions violation occurred in a P6 copy which depended on the
99 relative location of src and dst.
100
101 multiplier_N is more or less a third source region for the addmul_N
102 routines, and could be done with the redzoned region scheme.
103
104 */
105
106
107 /* always do assertion checking */
108 #define WANT_ASSERT 1
109
110 #include "config.h"
111
112 #include <errno.h>
113 #include <limits.h>
114 #include <signal.h>
115 #include <stdio.h>
116 #include <stdlib.h>
117 #include <string.h>
118 #include <time.h>
119
120 #if HAVE_UNISTD_H
121 #include <unistd.h>
122 #endif
123
124 #if HAVE_SYS_MMAN_H
125 #include <sys/mman.h>
126 #endif
127
128 #include "gmp.h"
129 #include "gmp-impl.h"
130 #include "longlong.h"
131 #include "tests.h"
132
133
134 #if !HAVE_DECL_OPTARG
135 extern char *optarg;
136 extern int optind, opterr;
137 #endif
138
139 #if ! HAVE_DECL_SYS_NERR
140 extern int sys_nerr;
141 #endif
142
143 #if ! HAVE_DECL_SYS_ERRLIST
144 extern char *sys_errlist[];
145 #endif
146
147 #if ! HAVE_STRERROR
148 char *
strerror(int n)149 strerror (int n)
150 {
151 if (n < 0 || n >= sys_nerr)
152 return "errno out of range";
153 else
154 return sys_errlist[n];
155 }
156 #endif
157
158 /* Rumour has it some systems lack a define of PROT_NONE. */
159 #ifndef PROT_NONE
160 #define PROT_NONE 0
161 #endif
162
163 /* Dummy defines for when mprotect doesn't exist. */
164 #ifndef PROT_READ
165 #define PROT_READ 0
166 #endif
167 #ifndef PROT_WRITE
168 #define PROT_WRITE 0
169 #endif
170
171 /* _SC_PAGESIZE is standard, but hpux 9 and possibly other systems have
172 _SC_PAGE_SIZE instead. */
173 #if defined (_SC_PAGE_SIZE) && ! defined (_SC_PAGESIZE)
174 #define _SC_PAGESIZE _SC_PAGE_SIZE
175 #endif
176
177
178 #ifdef EXTRA_PROTOS
179 EXTRA_PROTOS
180 #endif
181 #ifdef EXTRA_PROTOS2
182 EXTRA_PROTOS2
183 #endif
184
185
186 #define DEFAULT_REPETITIONS 10
187
188 int option_repetitions = DEFAULT_REPETITIONS;
189 int option_spinner = 1;
190 int option_redzones = 1;
191 int option_firstsize = 0;
192 int option_lastsize = 500;
193 int option_firstsize2 = 0;
194
195 #define ALIGNMENTS 4
196 #define OVERLAPS 4
197 #define CARRY_RANDOMS 5
198 #define MULTIPLIER_RANDOMS 5
199 #define DIVISOR_RANDOMS 5
200 #define FRACTION_COUNT 4
201
202 int option_print = 0;
203
204 #define DATA_TRAND 0
205 #define DATA_ZEROS 1
206 #define DATA_SEQ 2
207 #define DATA_FFS 3
208 #define DATA_2FD 4
209 int option_data = DATA_TRAND;
210
211
212 mp_size_t pagesize;
213 #define PAGESIZE_LIMBS (pagesize / GMP_LIMB_BYTES)
214
215 /* must be a multiple of the page size */
216 #define REDZONE_BYTES (pagesize * 16)
217 #define REDZONE_LIMBS (REDZONE_BYTES / GMP_LIMB_BYTES)
218
219
220 #define MAX3(x,y,z) (MAX (x, MAX (y, z)))
221
222 #if GMP_LIMB_BITS == 32
223 #define DEADVAL CNST_LIMB(0xDEADBEEF)
224 #else
225 #define DEADVAL CNST_LIMB(0xDEADBEEFBADDCAFE)
226 #endif
227
228
229 struct region_t {
230 mp_ptr ptr;
231 mp_size_t size;
232 };
233
234
235 #define TRAP_NOWHERE 0
236 #define TRAP_REF 1
237 #define TRAP_FUN 2
238 #define TRAP_SETUPS 3
239 int trap_location = TRAP_NOWHERE;
240
241
242 #define NUM_SOURCES 5
243 #define NUM_DESTS 2
244
245 struct source_t {
246 struct region_t region;
247 int high;
248 mp_size_t align;
249 mp_ptr p;
250 };
251
252 struct source_t s[NUM_SOURCES];
253
254 struct dest_t {
255 int high;
256 mp_size_t align;
257 mp_size_t size;
258 };
259
260 struct dest_t d[NUM_DESTS];
261
262 struct source_each_t {
263 mp_ptr p;
264 };
265
266 struct dest_each_t {
267 struct region_t region;
268 mp_ptr p;
269 };
270
271 mp_size_t size;
272 mp_size_t size2;
273 unsigned long shift;
274 mp_limb_t carry;
275 mp_limb_t divisor;
276 mp_limb_t multiplier;
277 mp_limb_t multiplier_N[8];
278
279 struct each_t {
280 const char *name;
281 struct dest_each_t d[NUM_DESTS];
282 struct source_each_t s[NUM_SOURCES];
283 mp_limb_t retval;
284 };
285
286 struct each_t ref = { "Ref" };
287 struct each_t fun = { "Fun" };
288
289 #define SRC_SIZE(n) ((n) == 1 && tr->size2 ? size2 : size)
290
291 void validate_fail (void);
292
293
294 #if HAVE_TRY_NEW_C
295 #include "try-new.c"
296 #endif
297
298
299 typedef mp_limb_t (*tryfun_t) (ANYARGS);
300
301 struct try_t {
302 char retval;
303
304 char src[NUM_SOURCES];
305 char dst[NUM_DESTS];
306
307 #define SIZE_YES 1
308 #define SIZE_ALLOW_ZERO 2
309 #define SIZE_1 3 /* 1 limb */
310 #define SIZE_2 4 /* 2 limbs */
311 #define SIZE_3 5 /* 3 limbs */
312 #define SIZE_4 6 /* 4 limbs */
313 #define SIZE_6 7 /* 6 limbs */
314 #define SIZE_FRACTION 8 /* size2 is fraction for divrem etc */
315 #define SIZE_SIZE2 9
316 #define SIZE_PLUS_1 10
317 #define SIZE_SUM 11
318 #define SIZE_DIFF 12
319 #define SIZE_DIFF_PLUS_1 13
320 #define SIZE_DIFF_PLUS_3 14
321 #define SIZE_RETVAL 15
322 #define SIZE_CEIL_HALF 16
323 #define SIZE_GET_STR 17
324 #define SIZE_PLUS_MSIZE_SUB_1 18 /* size+msize-1 */
325 #define SIZE_ODD 19
326 char size;
327 char size2;
328 char dst_size[NUM_DESTS];
329
330 /* multiplier_N size in limbs */
331 mp_size_t msize;
332
333 char dst_bytes[NUM_DESTS];
334
335 char dst0_from_src1;
336
337 #define CARRY_BIT 1 /* single bit 0 or 1 */
338 #define CARRY_3 2 /* 0, 1, 2 */
339 #define CARRY_4 3 /* 0 to 3 */
340 #define CARRY_LIMB 4 /* any limb value */
341 #define CARRY_DIVISOR 5 /* carry<divisor */
342 char carry;
343
344 /* a fudge to tell the output when to print negatives */
345 char carry_sign;
346
347 char multiplier;
348 char shift;
349
350 #define DIVISOR_LIMB 1
351 #define DIVISOR_NORM 2
352 #define DIVISOR_ODD 3
353 char divisor;
354
355 #define DATA_NON_ZERO 1
356 #define DATA_GCD 2
357 #define DATA_SRC0_ODD 3
358 #define DATA_SRC0_HIGHBIT 4
359 #define DATA_SRC1_ODD 5
360 #define DATA_SRC1_ODD_PRIME 6
361 #define DATA_SRC1_HIGHBIT 7
362 #define DATA_MULTIPLE_DIVISOR 8
363 #define DATA_UDIV_QRNND 9
364 #define DATA_DIV_QR_1 10
365 char data;
366
367 /* Default is allow full overlap. */
368 #define OVERLAP_NONE 1
369 #define OVERLAP_LOW_TO_HIGH 2
370 #define OVERLAP_HIGH_TO_LOW 3
371 #define OVERLAP_NOT_SRCS 4
372 #define OVERLAP_NOT_SRC2 8
373 #define OVERLAP_NOT_DST2 16
374 char overlap;
375
376 tryfun_t reference;
377 const char *reference_name;
378
379 void (*validate) (void);
380 const char *validate_name;
381 };
382
383 struct try_t *tr;
384
385
386 void
validate_mod_34lsub1(void)387 validate_mod_34lsub1 (void)
388 {
389 #define CNST_34LSUB1 ((CNST_LIMB(1) << (3 * (GMP_NUMB_BITS / 4))) - 1)
390
391 mp_srcptr ptr = s[0].p;
392 int error = 0;
393 mp_limb_t got, got_mod, want, want_mod;
394
395 ASSERT (size >= 1);
396
397 got = fun.retval;
398 got_mod = got % CNST_34LSUB1;
399
400 want = refmpn_mod_34lsub1 (ptr, size);
401 want_mod = want % CNST_34LSUB1;
402
403 if (got_mod != want_mod)
404 {
405 gmp_printf ("got 0x%MX reduced from 0x%MX\n", got_mod, got);
406 gmp_printf ("want 0x%MX reduced from 0x%MX\n", want_mod, want);
407 error = 1;
408 }
409
410 if (error)
411 validate_fail ();
412 }
413
414 void
validate_divexact_1(void)415 validate_divexact_1 (void)
416 {
417 mp_srcptr src = s[0].p;
418 mp_srcptr dst = fun.d[0].p;
419 int error = 0;
420
421 ASSERT (size >= 1);
422
423 {
424 mp_ptr tp = refmpn_malloc_limbs (size);
425 mp_limb_t rem;
426
427 rem = refmpn_divrem_1 (tp, 0, src, size, divisor);
428 if (rem != 0)
429 {
430 gmp_printf ("Remainder a%%d == 0x%MX, mpn_divexact_1 undefined\n", rem);
431 error = 1;
432 }
433 if (! refmpn_equal_anynail (tp, dst, size))
434 {
435 printf ("Quotient a/d wrong\n");
436 mpn_trace ("fun ", dst, size);
437 mpn_trace ("want", tp, size);
438 error = 1;
439 }
440 free (tp);
441 }
442
443 if (error)
444 validate_fail ();
445 }
446
447 void
validate_bdiv_q_1(void)448 validate_bdiv_q_1
449 (void)
450 {
451 mp_srcptr src = s[0].p;
452 mp_srcptr dst = fun.d[0].p;
453 int error = 0;
454
455 ASSERT (size >= 1);
456
457 {
458 mp_ptr tp = refmpn_malloc_limbs (size + 1);
459
460 refmpn_mul_1 (tp, dst, size, divisor);
461 /* Set ignored low bits */
462 tp[0] |= (src[0] & LOW_ZEROS_MASK (divisor));
463 if (! refmpn_equal_anynail (tp, src, size))
464 {
465 printf ("Bdiv wrong: res * divisor != src (mod B^size)\n");
466 mpn_trace ("res ", dst, size);
467 mpn_trace ("src ", src, size);
468 error = 1;
469 }
470 free (tp);
471 }
472
473 if (error)
474 validate_fail ();
475 }
476
477
478 void
validate_modexact_1c_odd(void)479 validate_modexact_1c_odd (void)
480 {
481 mp_srcptr ptr = s[0].p;
482 mp_limb_t r = fun.retval;
483 int error = 0;
484
485 ASSERT (size >= 1);
486 ASSERT (divisor & 1);
487
488 if ((r & GMP_NAIL_MASK) != 0)
489 printf ("r has non-zero nail\n");
490
491 if (carry < divisor)
492 {
493 if (! (r < divisor))
494 {
495 printf ("Don't have r < divisor\n");
496 error = 1;
497 }
498 }
499 else /* carry >= divisor */
500 {
501 if (! (r <= divisor))
502 {
503 printf ("Don't have r <= divisor\n");
504 error = 1;
505 }
506 }
507
508 {
509 mp_limb_t c = carry % divisor;
510 mp_ptr tp = refmpn_malloc_limbs (size+1);
511 mp_size_t k;
512
513 for (k = size-1; k <= size; k++)
514 {
515 /* set {tp,size+1} to r*b^k + a - c */
516 refmpn_copyi (tp, ptr, size);
517 tp[size] = 0;
518 ASSERT_NOCARRY (refmpn_add_1 (tp+k, tp+k, size+1-k, r));
519 if (refmpn_sub_1 (tp, tp, size+1, c))
520 ASSERT_CARRY (mpn_add_1 (tp, tp, size+1, divisor));
521
522 if (refmpn_mod_1 (tp, size+1, divisor) == 0)
523 goto good_remainder;
524 }
525 printf ("Remainder matches neither r*b^(size-1) nor r*b^size\n");
526 error = 1;
527
528 good_remainder:
529 free (tp);
530 }
531
532 if (error)
533 validate_fail ();
534 }
535
536 void
validate_modexact_1_odd(void)537 validate_modexact_1_odd (void)
538 {
539 carry = 0;
540 validate_modexact_1c_odd ();
541 }
542
543 void
validate_div_qr_1_pi1(void)544 validate_div_qr_1_pi1 (void)
545 {
546 mp_srcptr up = ref.s[0].p;
547 mp_size_t un = size;
548 mp_size_t uh = ref.s[1].p[0];
549 mp_srcptr qp = fun.d[0].p;
550 mp_limb_t r = fun.retval;
551 mp_limb_t cy;
552 int cmp;
553 mp_ptr tp;
554 if (r >= divisor)
555 {
556 gmp_printf ("Bad remainder %Md, d = %Md\n", r, divisor);
557 validate_fail ();
558 }
559 tp = refmpn_malloc_limbs (un);
560 cy = refmpn_mul_1 (tp, qp, un, divisor);
561 cy += refmpn_add_1 (tp, tp, un, r);
562 if (cy != uh || refmpn_cmp (tp, up, un) != 0)
563 {
564 gmp_printf ("Incorrect result, size %ld.\n"
565 "d = %Mx, u = %Mx, %Nx\n"
566 "got: r = %Mx, q = %Nx\n"
567 "q d + r = %Mx, %Nx",
568 (long) un,
569 divisor, uh, up, un,
570 r, qp, un,
571 cy, tp, un);
572 validate_fail ();
573 }
574 free (tp);
575 }
576
577
578 void
validate_sqrtrem(void)579 validate_sqrtrem (void)
580 {
581 mp_srcptr orig_ptr = s[0].p;
582 mp_size_t orig_size = size;
583 mp_size_t root_size = (size+1)/2;
584 mp_srcptr root_ptr = fun.d[0].p;
585 mp_size_t rem_size = fun.retval;
586 mp_srcptr rem_ptr = fun.d[1].p;
587 mp_size_t prod_size = 2*root_size;
588 mp_ptr p;
589 int error = 0;
590
591 if (rem_size < 0 || rem_size > size)
592 {
593 printf ("Bad remainder size retval %ld\n", (long) rem_size);
594 validate_fail ();
595 }
596
597 p = refmpn_malloc_limbs (prod_size);
598
599 p[root_size] = refmpn_lshift (p, root_ptr, root_size, 1);
600 if (refmpn_cmp_twosizes (p,root_size+1, rem_ptr,rem_size) < 0)
601 {
602 printf ("Remainder bigger than 2*root\n");
603 error = 1;
604 }
605
606 refmpn_sqr (p, root_ptr, root_size);
607 if (rem_size != 0)
608 refmpn_add (p, p, prod_size, rem_ptr, rem_size);
609 if (refmpn_cmp_twosizes (p,prod_size, orig_ptr,orig_size) != 0)
610 {
611 printf ("root^2+rem != original\n");
612 mpn_trace ("prod", p, prod_size);
613 error = 1;
614 }
615 free (p);
616
617 if (error)
618 validate_fail ();
619 }
620
621
622 /* These types are indexes into the param[] array and are arbitrary so long
623 as they're all distinct and within the size of param[]. Renumber
624 whenever necessary or desired. */
625
626 enum {
627 TYPE_ADD = 1, TYPE_ADD_N, TYPE_ADD_NC, TYPE_SUB, TYPE_SUB_N, TYPE_SUB_NC,
628
629 TYPE_ADD_ERR1_N, TYPE_ADD_ERR2_N, TYPE_ADD_ERR3_N,
630 TYPE_SUB_ERR1_N, TYPE_SUB_ERR2_N, TYPE_SUB_ERR3_N,
631
632 TYPE_MUL_1, TYPE_MUL_1C,
633
634 TYPE_MUL_2, TYPE_MUL_3, TYPE_MUL_4, TYPE_MUL_5, TYPE_MUL_6,
635
636 TYPE_ADDMUL_1, TYPE_ADDMUL_1C, TYPE_SUBMUL_1, TYPE_SUBMUL_1C,
637
638 TYPE_ADDMUL_2, TYPE_ADDMUL_3, TYPE_ADDMUL_4, TYPE_ADDMUL_5, TYPE_ADDMUL_6,
639 TYPE_ADDMUL_7, TYPE_ADDMUL_8,
640
641 TYPE_ADDSUB_N, TYPE_ADDSUB_NC,
642
643 TYPE_RSHIFT, TYPE_LSHIFT, TYPE_LSHIFTC,
644
645 TYPE_COPY, TYPE_COPYI, TYPE_COPYD, TYPE_COM,
646
647 TYPE_ADDLSH1_N, TYPE_ADDLSH2_N, TYPE_ADDLSH_N,
648 TYPE_ADDLSH1_N_IP1, TYPE_ADDLSH2_N_IP1, TYPE_ADDLSH_N_IP1,
649 TYPE_ADDLSH1_N_IP2, TYPE_ADDLSH2_N_IP2, TYPE_ADDLSH_N_IP2,
650 TYPE_SUBLSH1_N, TYPE_SUBLSH2_N, TYPE_SUBLSH_N,
651 TYPE_SUBLSH1_N_IP1, TYPE_SUBLSH2_N_IP1, TYPE_SUBLSH_N_IP1,
652 TYPE_RSBLSH1_N, TYPE_RSBLSH2_N, TYPE_RSBLSH_N,
653 TYPE_RSH1ADD_N, TYPE_RSH1SUB_N,
654
655 TYPE_ADDLSH1_NC, TYPE_ADDLSH2_NC, TYPE_ADDLSH_NC,
656 TYPE_SUBLSH1_NC, TYPE_SUBLSH2_NC, TYPE_SUBLSH_NC,
657 TYPE_RSBLSH1_NC, TYPE_RSBLSH2_NC, TYPE_RSBLSH_NC,
658
659 TYPE_ADDCND_N, TYPE_SUBCND_N,
660
661 TYPE_MOD_1, TYPE_MOD_1C, TYPE_DIVMOD_1, TYPE_DIVMOD_1C, TYPE_DIVREM_1,
662 TYPE_DIVREM_1C, TYPE_PREINV_DIVREM_1, TYPE_DIVREM_2, TYPE_PREINV_MOD_1,
663 TYPE_DIV_QR_1N_PI1,
664 TYPE_MOD_34LSUB1, TYPE_UDIV_QRNND, TYPE_UDIV_QRNND_R,
665
666 TYPE_DIVEXACT_1, TYPE_BDIV_Q_1, TYPE_DIVEXACT_BY3, TYPE_DIVEXACT_BY3C,
667 TYPE_MODEXACT_1_ODD, TYPE_MODEXACT_1C_ODD,
668
669 TYPE_INVERT, TYPE_BINVERT,
670
671 TYPE_GCD, TYPE_GCD_1, TYPE_GCD_FINDA, TYPE_MPZ_JACOBI, TYPE_MPZ_KRONECKER,
672 TYPE_MPZ_KRONECKER_UI, TYPE_MPZ_KRONECKER_SI, TYPE_MPZ_UI_KRONECKER,
673 TYPE_MPZ_SI_KRONECKER, TYPE_MPZ_LEGENDRE,
674
675 TYPE_AND_N, TYPE_NAND_N, TYPE_ANDN_N, TYPE_IOR_N, TYPE_IORN_N, TYPE_NIOR_N,
676 TYPE_XOR_N, TYPE_XNOR_N,
677
678 TYPE_MUL_MN, TYPE_MUL_N, TYPE_SQR, TYPE_UMUL_PPMM, TYPE_UMUL_PPMM_R,
679 TYPE_MULLO_N, TYPE_MULMID_MN, TYPE_MULMID_N,
680
681 TYPE_SBPI1_DIV_QR, TYPE_TDIV_QR,
682
683 TYPE_SQRTREM, TYPE_ZERO, TYPE_GET_STR, TYPE_POPCOUNT, TYPE_HAMDIST,
684
685 TYPE_EXTRA
686 };
687
688 struct try_t param[TYPE_EXTRA];
689
690
691 void
param_init(void)692 param_init (void)
693 {
694 struct try_t *p;
695
696 #define COPY(index) memcpy (p, ¶m[index], sizeof (*p))
697
698 #if HAVE_STRINGIZE
699 #define REFERENCE(fun) \
700 p->reference = (tryfun_t) fun; \
701 p->reference_name = #fun
702 #define VALIDATE(fun) \
703 p->validate = fun; \
704 p->validate_name = #fun
705 #else
706 #define REFERENCE(fun) \
707 p->reference = (tryfun_t) fun; \
708 p->reference_name = "fun"
709 #define VALIDATE(fun) \
710 p->validate = fun; \
711 p->validate_name = "fun"
712 #endif
713
714
715 p = ¶m[TYPE_ADD_N];
716 p->retval = 1;
717 p->dst[0] = 1;
718 p->src[0] = 1;
719 p->src[1] = 1;
720 REFERENCE (refmpn_add_n);
721
722 p = ¶m[TYPE_ADD_NC];
723 COPY (TYPE_ADD_N);
724 p->carry = CARRY_BIT;
725 REFERENCE (refmpn_add_nc);
726
727 p = ¶m[TYPE_SUB_N];
728 COPY (TYPE_ADD_N);
729 REFERENCE (refmpn_sub_n);
730
731 p = ¶m[TYPE_SUB_NC];
732 COPY (TYPE_ADD_NC);
733 REFERENCE (refmpn_sub_nc);
734
735 p = ¶m[TYPE_ADD];
736 COPY (TYPE_ADD_N);
737 p->size = SIZE_ALLOW_ZERO;
738 p->size2 = 1;
739 REFERENCE (refmpn_add);
740
741 p = ¶m[TYPE_SUB];
742 COPY (TYPE_ADD);
743 REFERENCE (refmpn_sub);
744
745
746 p = ¶m[TYPE_ADD_ERR1_N];
747 p->retval = 1;
748 p->dst[0] = 1;
749 p->dst[1] = 1;
750 p->src[0] = 1;
751 p->src[1] = 1;
752 p->src[2] = 1;
753 p->dst_size[1] = SIZE_2;
754 p->carry = CARRY_BIT;
755 p->overlap = OVERLAP_NOT_DST2;
756 REFERENCE (refmpn_add_err1_n);
757
758 p = ¶m[TYPE_SUB_ERR1_N];
759 COPY (TYPE_ADD_ERR1_N);
760 REFERENCE (refmpn_sub_err1_n);
761
762 p = ¶m[TYPE_ADD_ERR2_N];
763 COPY (TYPE_ADD_ERR1_N);
764 p->src[3] = 1;
765 p->dst_size[1] = SIZE_4;
766 REFERENCE (refmpn_add_err2_n);
767
768 p = ¶m[TYPE_SUB_ERR2_N];
769 COPY (TYPE_ADD_ERR2_N);
770 REFERENCE (refmpn_sub_err2_n);
771
772 p = ¶m[TYPE_ADD_ERR3_N];
773 COPY (TYPE_ADD_ERR2_N);
774 p->src[4] = 1;
775 p->dst_size[1] = SIZE_6;
776 REFERENCE (refmpn_add_err3_n);
777
778 p = ¶m[TYPE_SUB_ERR3_N];
779 COPY (TYPE_ADD_ERR3_N);
780 REFERENCE (refmpn_sub_err3_n);
781
782 p = ¶m[TYPE_ADDCND_N];
783 COPY (TYPE_ADD_N);
784 p->carry = CARRY_BIT;
785 REFERENCE (refmpn_cnd_add_n);
786
787 p = ¶m[TYPE_SUBCND_N];
788 COPY (TYPE_ADD_N);
789 p->carry = CARRY_BIT;
790 REFERENCE (refmpn_cnd_sub_n);
791
792
793 p = ¶m[TYPE_MUL_1];
794 p->retval = 1;
795 p->dst[0] = 1;
796 p->src[0] = 1;
797 p->multiplier = 1;
798 p->overlap = OVERLAP_LOW_TO_HIGH;
799 REFERENCE (refmpn_mul_1);
800
801 p = ¶m[TYPE_MUL_1C];
802 COPY (TYPE_MUL_1);
803 p->carry = CARRY_LIMB;
804 REFERENCE (refmpn_mul_1c);
805
806
807 p = ¶m[TYPE_MUL_2];
808 p->retval = 1;
809 p->dst[0] = 1;
810 p->dst_size[0] = SIZE_PLUS_MSIZE_SUB_1;
811 p->src[0] = 1;
812 p->src[1] = 1;
813 p->msize = 2;
814 p->overlap = OVERLAP_NOT_SRC2;
815 REFERENCE (refmpn_mul_2);
816
817 p = ¶m[TYPE_MUL_3];
818 COPY (TYPE_MUL_2);
819 p->msize = 3;
820 REFERENCE (refmpn_mul_3);
821
822 p = ¶m[TYPE_MUL_4];
823 COPY (TYPE_MUL_2);
824 p->msize = 4;
825 REFERENCE (refmpn_mul_4);
826
827 p = ¶m[TYPE_MUL_5];
828 COPY (TYPE_MUL_2);
829 p->msize = 5;
830 REFERENCE (refmpn_mul_5);
831
832 p = ¶m[TYPE_MUL_6];
833 COPY (TYPE_MUL_2);
834 p->msize = 6;
835 REFERENCE (refmpn_mul_6);
836
837
838 p = ¶m[TYPE_ADDMUL_1];
839 p->retval = 1;
840 p->dst[0] = 1;
841 p->src[0] = 1;
842 p->multiplier = 1;
843 p->dst0_from_src1 = 1;
844 REFERENCE (refmpn_addmul_1);
845
846 p = ¶m[TYPE_ADDMUL_1C];
847 COPY (TYPE_ADDMUL_1);
848 p->carry = CARRY_LIMB;
849 REFERENCE (refmpn_addmul_1c);
850
851 p = ¶m[TYPE_SUBMUL_1];
852 COPY (TYPE_ADDMUL_1);
853 REFERENCE (refmpn_submul_1);
854
855 p = ¶m[TYPE_SUBMUL_1C];
856 COPY (TYPE_ADDMUL_1C);
857 REFERENCE (refmpn_submul_1c);
858
859
860 p = ¶m[TYPE_ADDMUL_2];
861 p->retval = 1;
862 p->dst[0] = 1;
863 p->dst_size[0] = SIZE_PLUS_MSIZE_SUB_1;
864 p->src[0] = 1;
865 p->src[1] = 1;
866 p->msize = 2;
867 p->dst0_from_src1 = 1;
868 p->overlap = OVERLAP_NONE;
869 REFERENCE (refmpn_addmul_2);
870
871 p = ¶m[TYPE_ADDMUL_3];
872 COPY (TYPE_ADDMUL_2);
873 p->msize = 3;
874 REFERENCE (refmpn_addmul_3);
875
876 p = ¶m[TYPE_ADDMUL_4];
877 COPY (TYPE_ADDMUL_2);
878 p->msize = 4;
879 REFERENCE (refmpn_addmul_4);
880
881 p = ¶m[TYPE_ADDMUL_5];
882 COPY (TYPE_ADDMUL_2);
883 p->msize = 5;
884 REFERENCE (refmpn_addmul_5);
885
886 p = ¶m[TYPE_ADDMUL_6];
887 COPY (TYPE_ADDMUL_2);
888 p->msize = 6;
889 REFERENCE (refmpn_addmul_6);
890
891 p = ¶m[TYPE_ADDMUL_7];
892 COPY (TYPE_ADDMUL_2);
893 p->msize = 7;
894 REFERENCE (refmpn_addmul_7);
895
896 p = ¶m[TYPE_ADDMUL_8];
897 COPY (TYPE_ADDMUL_2);
898 p->msize = 8;
899 REFERENCE (refmpn_addmul_8);
900
901
902 p = ¶m[TYPE_AND_N];
903 p->dst[0] = 1;
904 p->src[0] = 1;
905 p->src[1] = 1;
906 REFERENCE (refmpn_and_n);
907
908 p = ¶m[TYPE_ANDN_N];
909 COPY (TYPE_AND_N);
910 REFERENCE (refmpn_andn_n);
911
912 p = ¶m[TYPE_NAND_N];
913 COPY (TYPE_AND_N);
914 REFERENCE (refmpn_nand_n);
915
916 p = ¶m[TYPE_IOR_N];
917 COPY (TYPE_AND_N);
918 REFERENCE (refmpn_ior_n);
919
920 p = ¶m[TYPE_IORN_N];
921 COPY (TYPE_AND_N);
922 REFERENCE (refmpn_iorn_n);
923
924 p = ¶m[TYPE_NIOR_N];
925 COPY (TYPE_AND_N);
926 REFERENCE (refmpn_nior_n);
927
928 p = ¶m[TYPE_XOR_N];
929 COPY (TYPE_AND_N);
930 REFERENCE (refmpn_xor_n);
931
932 p = ¶m[TYPE_XNOR_N];
933 COPY (TYPE_AND_N);
934 REFERENCE (refmpn_xnor_n);
935
936
937 p = ¶m[TYPE_ADDSUB_N];
938 p->retval = 1;
939 p->dst[0] = 1;
940 p->dst[1] = 1;
941 p->src[0] = 1;
942 p->src[1] = 1;
943 REFERENCE (refmpn_add_n_sub_n);
944
945 p = ¶m[TYPE_ADDSUB_NC];
946 COPY (TYPE_ADDSUB_N);
947 p->carry = CARRY_4;
948 REFERENCE (refmpn_add_n_sub_nc);
949
950
951 p = ¶m[TYPE_COPY];
952 p->dst[0] = 1;
953 p->src[0] = 1;
954 p->overlap = OVERLAP_NONE;
955 p->size = SIZE_ALLOW_ZERO;
956 REFERENCE (refmpn_copy);
957
958 p = ¶m[TYPE_COPYI];
959 p->dst[0] = 1;
960 p->src[0] = 1;
961 p->overlap = OVERLAP_LOW_TO_HIGH;
962 p->size = SIZE_ALLOW_ZERO;
963 REFERENCE (refmpn_copyi);
964
965 p = ¶m[TYPE_COPYD];
966 p->dst[0] = 1;
967 p->src[0] = 1;
968 p->overlap = OVERLAP_HIGH_TO_LOW;
969 p->size = SIZE_ALLOW_ZERO;
970 REFERENCE (refmpn_copyd);
971
972 p = ¶m[TYPE_COM];
973 p->dst[0] = 1;
974 p->src[0] = 1;
975 REFERENCE (refmpn_com);
976
977
978 p = ¶m[TYPE_ADDLSH1_N];
979 COPY (TYPE_ADD_N);
980 REFERENCE (refmpn_addlsh1_n);
981
982 p = ¶m[TYPE_ADDLSH2_N];
983 COPY (TYPE_ADD_N);
984 REFERENCE (refmpn_addlsh2_n);
985
986 p = ¶m[TYPE_ADDLSH_N];
987 COPY (TYPE_ADD_N);
988 p->shift = 1;
989 REFERENCE (refmpn_addlsh_n);
990
991 p = ¶m[TYPE_ADDLSH1_N_IP1];
992 p->retval = 1;
993 p->dst[0] = 1;
994 p->src[0] = 1;
995 p->dst0_from_src1 = 1;
996 REFERENCE (refmpn_addlsh1_n_ip1);
997
998 p = ¶m[TYPE_ADDLSH2_N_IP1];
999 COPY (TYPE_ADDLSH1_N_IP1);
1000 REFERENCE (refmpn_addlsh2_n_ip1);
1001
1002 p = ¶m[TYPE_ADDLSH_N_IP1];
1003 COPY (TYPE_ADDLSH1_N_IP1);
1004 p->shift = 1;
1005 REFERENCE (refmpn_addlsh_n_ip1);
1006
1007 p = ¶m[TYPE_ADDLSH1_N_IP2];
1008 COPY (TYPE_ADDLSH1_N_IP1);
1009 REFERENCE (refmpn_addlsh1_n_ip2);
1010
1011 p = ¶m[TYPE_ADDLSH2_N_IP2];
1012 COPY (TYPE_ADDLSH1_N_IP1);
1013 REFERENCE (refmpn_addlsh2_n_ip2);
1014
1015 p = ¶m[TYPE_ADDLSH_N_IP2];
1016 COPY (TYPE_ADDLSH_N_IP1);
1017 REFERENCE (refmpn_addlsh_n_ip2);
1018
1019 p = ¶m[TYPE_SUBLSH1_N];
1020 COPY (TYPE_ADD_N);
1021 REFERENCE (refmpn_sublsh1_n);
1022
1023 p = ¶m[TYPE_SUBLSH2_N];
1024 COPY (TYPE_ADD_N);
1025 REFERENCE (refmpn_sublsh2_n);
1026
1027 p = ¶m[TYPE_SUBLSH_N];
1028 COPY (TYPE_ADDLSH_N);
1029 REFERENCE (refmpn_sublsh_n);
1030
1031 p = ¶m[TYPE_SUBLSH1_N_IP1];
1032 COPY (TYPE_ADDLSH1_N_IP1);
1033 REFERENCE (refmpn_sublsh1_n_ip1);
1034
1035 p = ¶m[TYPE_SUBLSH2_N_IP1];
1036 COPY (TYPE_ADDLSH1_N_IP1);
1037 REFERENCE (refmpn_sublsh2_n_ip1);
1038
1039 p = ¶m[TYPE_SUBLSH_N_IP1];
1040 COPY (TYPE_ADDLSH_N_IP1);
1041 REFERENCE (refmpn_sublsh_n_ip1);
1042
1043 p = ¶m[TYPE_RSBLSH1_N];
1044 COPY (TYPE_ADD_N);
1045 REFERENCE (refmpn_rsblsh1_n);
1046
1047 p = ¶m[TYPE_RSBLSH2_N];
1048 COPY (TYPE_ADD_N);
1049 REFERENCE (refmpn_rsblsh2_n);
1050
1051 p = ¶m[TYPE_RSBLSH_N];
1052 COPY (TYPE_ADDLSH_N);
1053 REFERENCE (refmpn_rsblsh_n);
1054
1055 p = ¶m[TYPE_RSH1ADD_N];
1056 COPY (TYPE_ADD_N);
1057 REFERENCE (refmpn_rsh1add_n);
1058
1059 p = ¶m[TYPE_RSH1SUB_N];
1060 COPY (TYPE_ADD_N);
1061 REFERENCE (refmpn_rsh1sub_n);
1062
1063
1064 p = ¶m[TYPE_ADDLSH1_NC];
1065 COPY (TYPE_ADDLSH1_N);
1066 p->carry = CARRY_3;
1067 REFERENCE (refmpn_addlsh1_nc);
1068
1069 p = ¶m[TYPE_ADDLSH2_NC];
1070 COPY (TYPE_ADDLSH2_N);
1071 p->carry = CARRY_4; /* FIXME */
1072 REFERENCE (refmpn_addlsh2_nc);
1073
1074 p = ¶m[TYPE_ADDLSH_NC];
1075 COPY (TYPE_ADDLSH_N);
1076 p->carry = CARRY_BIT; /* FIXME */
1077 REFERENCE (refmpn_addlsh_nc);
1078
1079 p = ¶m[TYPE_SUBLSH1_NC];
1080 COPY (TYPE_ADDLSH1_NC);
1081 REFERENCE (refmpn_sublsh1_nc);
1082
1083 p = ¶m[TYPE_SUBLSH2_NC];
1084 COPY (TYPE_ADDLSH2_NC);
1085 REFERENCE (refmpn_sublsh2_nc);
1086
1087 p = ¶m[TYPE_SUBLSH_NC];
1088 COPY (TYPE_ADDLSH_NC);
1089 REFERENCE (refmpn_sublsh_nc);
1090
1091 p = ¶m[TYPE_RSBLSH1_NC];
1092 COPY (TYPE_RSBLSH1_N);
1093 p->carry = CARRY_BIT; /* FIXME */
1094 REFERENCE (refmpn_rsblsh1_nc);
1095
1096 p = ¶m[TYPE_RSBLSH2_NC];
1097 COPY (TYPE_RSBLSH2_N);
1098 p->carry = CARRY_4; /* FIXME */
1099 REFERENCE (refmpn_rsblsh2_nc);
1100
1101 p = ¶m[TYPE_RSBLSH_NC];
1102 COPY (TYPE_RSBLSH_N);
1103 p->carry = CARRY_BIT; /* FIXME */
1104 REFERENCE (refmpn_rsblsh_nc);
1105
1106
1107 p = ¶m[TYPE_MOD_1];
1108 p->retval = 1;
1109 p->src[0] = 1;
1110 p->size = SIZE_ALLOW_ZERO;
1111 p->divisor = DIVISOR_LIMB;
1112 REFERENCE (refmpn_mod_1);
1113
1114 p = ¶m[TYPE_MOD_1C];
1115 COPY (TYPE_MOD_1);
1116 p->carry = CARRY_DIVISOR;
1117 REFERENCE (refmpn_mod_1c);
1118
1119 p = ¶m[TYPE_DIVMOD_1];
1120 COPY (TYPE_MOD_1);
1121 p->dst[0] = 1;
1122 REFERENCE (refmpn_divmod_1);
1123
1124 p = ¶m[TYPE_DIVMOD_1C];
1125 COPY (TYPE_DIVMOD_1);
1126 p->carry = CARRY_DIVISOR;
1127 REFERENCE (refmpn_divmod_1c);
1128
1129 p = ¶m[TYPE_DIVREM_1];
1130 COPY (TYPE_DIVMOD_1);
1131 p->size2 = SIZE_FRACTION;
1132 p->dst_size[0] = SIZE_SUM;
1133 REFERENCE (refmpn_divrem_1);
1134
1135 p = ¶m[TYPE_DIVREM_1C];
1136 COPY (TYPE_DIVREM_1);
1137 p->carry = CARRY_DIVISOR;
1138 REFERENCE (refmpn_divrem_1c);
1139
1140 p = ¶m[TYPE_PREINV_DIVREM_1];
1141 COPY (TYPE_DIVREM_1);
1142 p->size = SIZE_YES; /* ie. no size==0 */
1143 REFERENCE (refmpn_preinv_divrem_1);
1144
1145 p = ¶m[TYPE_DIV_QR_1N_PI1];
1146 p->retval = 1;
1147 p->src[0] = 1;
1148 p->src[1] = 1;
1149 /* SIZE_1 not supported. Always uses low limb only. */
1150 p->size2 = 1;
1151 p->dst[0] = 1;
1152 p->divisor = DIVISOR_NORM;
1153 p->data = DATA_DIV_QR_1;
1154 VALIDATE (validate_div_qr_1_pi1);
1155
1156 p = ¶m[TYPE_PREINV_MOD_1];
1157 p->retval = 1;
1158 p->src[0] = 1;
1159 p->divisor = DIVISOR_NORM;
1160 REFERENCE (refmpn_preinv_mod_1);
1161
1162 p = ¶m[TYPE_MOD_34LSUB1];
1163 p->retval = 1;
1164 p->src[0] = 1;
1165 VALIDATE (validate_mod_34lsub1);
1166
1167 p = ¶m[TYPE_UDIV_QRNND];
1168 p->retval = 1;
1169 p->src[0] = 1;
1170 p->dst[0] = 1;
1171 p->dst_size[0] = SIZE_1;
1172 p->divisor = UDIV_NEEDS_NORMALIZATION ? DIVISOR_NORM : DIVISOR_LIMB;
1173 p->data = DATA_UDIV_QRNND;
1174 p->overlap = OVERLAP_NONE;
1175 REFERENCE (refmpn_udiv_qrnnd);
1176
1177 p = ¶m[TYPE_UDIV_QRNND_R];
1178 COPY (TYPE_UDIV_QRNND);
1179 REFERENCE (refmpn_udiv_qrnnd_r);
1180
1181
1182 p = ¶m[TYPE_DIVEXACT_1];
1183 p->dst[0] = 1;
1184 p->src[0] = 1;
1185 p->divisor = DIVISOR_LIMB;
1186 p->data = DATA_MULTIPLE_DIVISOR;
1187 VALIDATE (validate_divexact_1);
1188 REFERENCE (refmpn_divmod_1);
1189
1190 p = ¶m[TYPE_BDIV_Q_1];
1191 p->dst[0] = 1;
1192 p->src[0] = 1;
1193 p->divisor = DIVISOR_LIMB;
1194 VALIDATE (validate_bdiv_q_1);
1195
1196 p = ¶m[TYPE_DIVEXACT_BY3];
1197 p->retval = 1;
1198 p->dst[0] = 1;
1199 p->src[0] = 1;
1200 REFERENCE (refmpn_divexact_by3);
1201
1202 p = ¶m[TYPE_DIVEXACT_BY3C];
1203 COPY (TYPE_DIVEXACT_BY3);
1204 p->carry = CARRY_3;
1205 REFERENCE (refmpn_divexact_by3c);
1206
1207
1208 p = ¶m[TYPE_MODEXACT_1_ODD];
1209 p->retval = 1;
1210 p->src[0] = 1;
1211 p->divisor = DIVISOR_ODD;
1212 VALIDATE (validate_modexact_1_odd);
1213
1214 p = ¶m[TYPE_MODEXACT_1C_ODD];
1215 COPY (TYPE_MODEXACT_1_ODD);
1216 p->carry = CARRY_LIMB;
1217 VALIDATE (validate_modexact_1c_odd);
1218
1219
1220 p = ¶m[TYPE_GCD_1];
1221 p->retval = 1;
1222 p->src[0] = 1;
1223 p->data = DATA_NON_ZERO;
1224 p->divisor = DIVISOR_LIMB;
1225 REFERENCE (refmpn_gcd_1);
1226
1227 p = ¶m[TYPE_GCD];
1228 p->retval = 1;
1229 p->dst[0] = 1;
1230 p->src[0] = 1;
1231 p->src[1] = 1;
1232 p->size2 = 1;
1233 p->dst_size[0] = SIZE_RETVAL;
1234 p->overlap = OVERLAP_NOT_SRCS;
1235 p->data = DATA_GCD;
1236 REFERENCE (refmpn_gcd);
1237
1238
1239 p = ¶m[TYPE_MPZ_LEGENDRE];
1240 p->retval = 1;
1241 p->src[0] = 1;
1242 p->size = SIZE_ALLOW_ZERO;
1243 p->src[1] = 1;
1244 p->data = DATA_SRC1_ODD_PRIME;
1245 p->size2 = 1;
1246 p->carry = CARRY_BIT;
1247 p->carry_sign = 1;
1248 REFERENCE (refmpz_legendre);
1249
1250 p = ¶m[TYPE_MPZ_JACOBI];
1251 p->retval = 1;
1252 p->src[0] = 1;
1253 p->size = SIZE_ALLOW_ZERO;
1254 p->src[1] = 1;
1255 p->data = DATA_SRC1_ODD;
1256 p->size2 = 1;
1257 p->carry = CARRY_BIT;
1258 p->carry_sign = 1;
1259 REFERENCE (refmpz_jacobi);
1260
1261 p = ¶m[TYPE_MPZ_KRONECKER];
1262 p->retval = 1;
1263 p->src[0] = 1;
1264 p->size = SIZE_ALLOW_ZERO;
1265 p->src[1] = 1;
1266 p->data = 0;
1267 p->size2 = 1;
1268 p->carry = CARRY_4;
1269 p->carry_sign = 1;
1270 REFERENCE (refmpz_kronecker);
1271
1272
1273 p = ¶m[TYPE_MPZ_KRONECKER_UI];
1274 p->retval = 1;
1275 p->src[0] = 1;
1276 p->size = SIZE_ALLOW_ZERO;
1277 p->multiplier = 1;
1278 p->carry = CARRY_BIT;
1279 REFERENCE (refmpz_kronecker_ui);
1280
1281 p = ¶m[TYPE_MPZ_KRONECKER_SI];
1282 COPY (TYPE_MPZ_KRONECKER_UI);
1283 REFERENCE (refmpz_kronecker_si);
1284
1285 p = ¶m[TYPE_MPZ_UI_KRONECKER];
1286 COPY (TYPE_MPZ_KRONECKER_UI);
1287 REFERENCE (refmpz_ui_kronecker);
1288
1289 p = ¶m[TYPE_MPZ_SI_KRONECKER];
1290 COPY (TYPE_MPZ_KRONECKER_UI);
1291 REFERENCE (refmpz_si_kronecker);
1292
1293
1294 p = ¶m[TYPE_SQR];
1295 p->dst[0] = 1;
1296 p->src[0] = 1;
1297 p->dst_size[0] = SIZE_SUM;
1298 p->overlap = OVERLAP_NONE;
1299 REFERENCE (refmpn_sqr);
1300
1301 p = ¶m[TYPE_MUL_N];
1302 COPY (TYPE_SQR);
1303 p->src[1] = 1;
1304 REFERENCE (refmpn_mul_n);
1305
1306 p = ¶m[TYPE_MULLO_N];
1307 COPY (TYPE_MUL_N);
1308 p->dst_size[0] = 0;
1309 REFERENCE (refmpn_mullo_n);
1310
1311 p = ¶m[TYPE_MUL_MN];
1312 COPY (TYPE_MUL_N);
1313 p->size2 = 1;
1314 REFERENCE (refmpn_mul_basecase);
1315
1316 p = ¶m[TYPE_MULMID_MN];
1317 COPY (TYPE_MUL_MN);
1318 p->dst_size[0] = SIZE_DIFF_PLUS_3;
1319 REFERENCE (refmpn_mulmid_basecase);
1320
1321 p = ¶m[TYPE_MULMID_N];
1322 COPY (TYPE_MUL_N);
1323 p->size = SIZE_ODD;
1324 p->size2 = SIZE_CEIL_HALF;
1325 p->dst_size[0] = SIZE_DIFF_PLUS_3;
1326 REFERENCE (refmpn_mulmid_n);
1327
1328 p = ¶m[TYPE_UMUL_PPMM];
1329 p->retval = 1;
1330 p->src[0] = 1;
1331 p->dst[0] = 1;
1332 p->dst_size[0] = SIZE_1;
1333 p->overlap = OVERLAP_NONE;
1334 REFERENCE (refmpn_umul_ppmm);
1335
1336 p = ¶m[TYPE_UMUL_PPMM_R];
1337 COPY (TYPE_UMUL_PPMM);
1338 REFERENCE (refmpn_umul_ppmm_r);
1339
1340
1341 p = ¶m[TYPE_RSHIFT];
1342 p->retval = 1;
1343 p->dst[0] = 1;
1344 p->src[0] = 1;
1345 p->shift = 1;
1346 p->overlap = OVERLAP_LOW_TO_HIGH;
1347 REFERENCE (refmpn_rshift);
1348
1349 p = ¶m[TYPE_LSHIFT];
1350 COPY (TYPE_RSHIFT);
1351 p->overlap = OVERLAP_HIGH_TO_LOW;
1352 REFERENCE (refmpn_lshift);
1353
1354 p = ¶m[TYPE_LSHIFTC];
1355 COPY (TYPE_RSHIFT);
1356 p->overlap = OVERLAP_HIGH_TO_LOW;
1357 REFERENCE (refmpn_lshiftc);
1358
1359
1360 p = ¶m[TYPE_POPCOUNT];
1361 p->retval = 1;
1362 p->src[0] = 1;
1363 REFERENCE (refmpn_popcount);
1364
1365 p = ¶m[TYPE_HAMDIST];
1366 COPY (TYPE_POPCOUNT);
1367 p->src[1] = 1;
1368 REFERENCE (refmpn_hamdist);
1369
1370
1371 p = ¶m[TYPE_SBPI1_DIV_QR];
1372 p->retval = 1;
1373 p->dst[0] = 1;
1374 p->dst[1] = 1;
1375 p->src[0] = 1;
1376 p->src[1] = 1;
1377 p->data = DATA_SRC1_HIGHBIT;
1378 p->size2 = 1;
1379 p->dst_size[0] = SIZE_DIFF;
1380 p->overlap = OVERLAP_NONE;
1381 REFERENCE (refmpn_sb_div_qr);
1382
1383 p = ¶m[TYPE_TDIV_QR];
1384 p->dst[0] = 1;
1385 p->dst[1] = 1;
1386 p->src[0] = 1;
1387 p->src[1] = 1;
1388 p->size2 = 1;
1389 p->dst_size[0] = SIZE_DIFF_PLUS_1;
1390 p->dst_size[1] = SIZE_SIZE2;
1391 p->overlap = OVERLAP_NONE;
1392 REFERENCE (refmpn_tdiv_qr);
1393
1394 p = ¶m[TYPE_SQRTREM];
1395 p->retval = 1;
1396 p->dst[0] = 1;
1397 p->dst[1] = 1;
1398 p->src[0] = 1;
1399 p->dst_size[0] = SIZE_CEIL_HALF;
1400 p->dst_size[1] = SIZE_RETVAL;
1401 p->overlap = OVERLAP_NONE;
1402 VALIDATE (validate_sqrtrem);
1403 REFERENCE (refmpn_sqrtrem);
1404
1405 p = ¶m[TYPE_ZERO];
1406 p->dst[0] = 1;
1407 p->size = SIZE_ALLOW_ZERO;
1408 REFERENCE (refmpn_zero);
1409
1410 p = ¶m[TYPE_GET_STR];
1411 p->retval = 1;
1412 p->src[0] = 1;
1413 p->size = SIZE_ALLOW_ZERO;
1414 p->dst[0] = 1;
1415 p->dst[1] = 1;
1416 p->dst_size[0] = SIZE_GET_STR;
1417 p->dst_bytes[0] = 1;
1418 p->overlap = OVERLAP_NONE;
1419 REFERENCE (refmpn_get_str);
1420
1421 p = ¶m[TYPE_BINVERT];
1422 p->dst[0] = 1;
1423 p->src[0] = 1;
1424 p->data = DATA_SRC0_ODD;
1425 p->overlap = OVERLAP_NONE;
1426 REFERENCE (refmpn_binvert);
1427
1428 p = ¶m[TYPE_INVERT];
1429 p->dst[0] = 1;
1430 p->src[0] = 1;
1431 p->data = DATA_SRC0_HIGHBIT;
1432 p->overlap = OVERLAP_NONE;
1433 REFERENCE (refmpn_invert);
1434
1435 #ifdef EXTRA_PARAM_INIT
1436 EXTRA_PARAM_INIT
1437 #endif
1438 }
1439
1440
1441 /* The following are macros if there's no native versions, so wrap them in
1442 functions that can be in try_array[]. */
1443
1444 void
MPN_COPY_fun(mp_ptr rp,mp_srcptr sp,mp_size_t size)1445 MPN_COPY_fun (mp_ptr rp, mp_srcptr sp, mp_size_t size)
1446 { MPN_COPY (rp, sp, size); }
1447
1448 void
MPN_COPY_INCR_fun(mp_ptr rp,mp_srcptr sp,mp_size_t size)1449 MPN_COPY_INCR_fun (mp_ptr rp, mp_srcptr sp, mp_size_t size)
1450 { MPN_COPY_INCR (rp, sp, size); }
1451
1452 void
MPN_COPY_DECR_fun(mp_ptr rp,mp_srcptr sp,mp_size_t size)1453 MPN_COPY_DECR_fun (mp_ptr rp, mp_srcptr sp, mp_size_t size)
1454 { MPN_COPY_DECR (rp, sp, size); }
1455
1456 void
__GMPN_COPY_fun(mp_ptr rp,mp_srcptr sp,mp_size_t size)1457 __GMPN_COPY_fun (mp_ptr rp, mp_srcptr sp, mp_size_t size)
1458 { __GMPN_COPY (rp, sp, size); }
1459
1460 #ifdef __GMPN_COPY_INCR
1461 void
__GMPN_COPY_INCR_fun(mp_ptr rp,mp_srcptr sp,mp_size_t size)1462 __GMPN_COPY_INCR_fun (mp_ptr rp, mp_srcptr sp, mp_size_t size)
1463 { __GMPN_COPY_INCR (rp, sp, size); }
1464 #endif
1465
1466 void
mpn_com_fun(mp_ptr rp,mp_srcptr sp,mp_size_t size)1467 mpn_com_fun (mp_ptr rp, mp_srcptr sp, mp_size_t size)
1468 { mpn_com (rp, sp, size); }
1469
1470 void
mpn_and_n_fun(mp_ptr rp,mp_srcptr s1,mp_srcptr s2,mp_size_t size)1471 mpn_and_n_fun (mp_ptr rp, mp_srcptr s1, mp_srcptr s2, mp_size_t size)
1472 { mpn_and_n (rp, s1, s2, size); }
1473
1474 void
mpn_andn_n_fun(mp_ptr rp,mp_srcptr s1,mp_srcptr s2,mp_size_t size)1475 mpn_andn_n_fun (mp_ptr rp, mp_srcptr s1, mp_srcptr s2, mp_size_t size)
1476 { mpn_andn_n (rp, s1, s2, size); }
1477
1478 void
mpn_nand_n_fun(mp_ptr rp,mp_srcptr s1,mp_srcptr s2,mp_size_t size)1479 mpn_nand_n_fun (mp_ptr rp, mp_srcptr s1, mp_srcptr s2, mp_size_t size)
1480 { mpn_nand_n (rp, s1, s2, size); }
1481
1482 void
mpn_ior_n_fun(mp_ptr rp,mp_srcptr s1,mp_srcptr s2,mp_size_t size)1483 mpn_ior_n_fun (mp_ptr rp, mp_srcptr s1, mp_srcptr s2, mp_size_t size)
1484 { mpn_ior_n (rp, s1, s2, size); }
1485
1486 void
mpn_iorn_n_fun(mp_ptr rp,mp_srcptr s1,mp_srcptr s2,mp_size_t size)1487 mpn_iorn_n_fun (mp_ptr rp, mp_srcptr s1, mp_srcptr s2, mp_size_t size)
1488 { mpn_iorn_n (rp, s1, s2, size); }
1489
1490 void
mpn_nior_n_fun(mp_ptr rp,mp_srcptr s1,mp_srcptr s2,mp_size_t size)1491 mpn_nior_n_fun (mp_ptr rp, mp_srcptr s1, mp_srcptr s2, mp_size_t size)
1492 { mpn_nior_n (rp, s1, s2, size); }
1493
1494 void
mpn_xor_n_fun(mp_ptr rp,mp_srcptr s1,mp_srcptr s2,mp_size_t size)1495 mpn_xor_n_fun (mp_ptr rp, mp_srcptr s1, mp_srcptr s2, mp_size_t size)
1496 { mpn_xor_n (rp, s1, s2, size); }
1497
1498 void
mpn_xnor_n_fun(mp_ptr rp,mp_srcptr s1,mp_srcptr s2,mp_size_t size)1499 mpn_xnor_n_fun (mp_ptr rp, mp_srcptr s1, mp_srcptr s2, mp_size_t size)
1500 { mpn_xnor_n (rp, s1, s2, size); }
1501
1502 mp_limb_t
udiv_qrnnd_fun(mp_limb_t * remptr,mp_limb_t n1,mp_limb_t n0,mp_limb_t d)1503 udiv_qrnnd_fun (mp_limb_t *remptr, mp_limb_t n1, mp_limb_t n0, mp_limb_t d)
1504 {
1505 mp_limb_t q;
1506 udiv_qrnnd (q, *remptr, n1, n0, d);
1507 return q;
1508 }
1509
1510 mp_limb_t
mpn_divexact_by3_fun(mp_ptr rp,mp_srcptr sp,mp_size_t size)1511 mpn_divexact_by3_fun (mp_ptr rp, mp_srcptr sp, mp_size_t size)
1512 {
1513 return mpn_divexact_by3 (rp, sp, size);
1514 }
1515
1516 #if HAVE_NATIVE_mpn_addlsh1_n_ip1
1517 mp_limb_t
mpn_addlsh1_n_ip1_fun(mp_ptr rp,mp_srcptr sp,mp_size_t size)1518 mpn_addlsh1_n_ip1_fun (mp_ptr rp, mp_srcptr sp, mp_size_t size)
1519 {
1520 return mpn_addlsh1_n_ip1 (rp, sp, size);
1521 }
1522 #endif
1523 #if HAVE_NATIVE_mpn_addlsh2_n_ip1
1524 mp_limb_t
mpn_addlsh2_n_ip1_fun(mp_ptr rp,mp_srcptr sp,mp_size_t size)1525 mpn_addlsh2_n_ip1_fun (mp_ptr rp, mp_srcptr sp, mp_size_t size)
1526 {
1527 return mpn_addlsh2_n_ip1 (rp, sp, size);
1528 }
1529 #endif
1530 #if HAVE_NATIVE_mpn_addlsh_n_ip1
1531 mp_limb_t
mpn_addlsh_n_ip1_fun(mp_ptr rp,mp_srcptr sp,mp_size_t size,unsigned int sh)1532 mpn_addlsh_n_ip1_fun (mp_ptr rp, mp_srcptr sp, mp_size_t size, unsigned int sh)
1533 {
1534 return mpn_addlsh_n_ip1 (rp, sp, size, sh);
1535 }
1536 #endif
1537 #if HAVE_NATIVE_mpn_addlsh1_n_ip2
1538 mp_limb_t
mpn_addlsh1_n_ip2_fun(mp_ptr rp,mp_srcptr sp,mp_size_t size)1539 mpn_addlsh1_n_ip2_fun (mp_ptr rp, mp_srcptr sp, mp_size_t size)
1540 {
1541 return mpn_addlsh1_n_ip2 (rp, sp, size);
1542 }
1543 #endif
1544 #if HAVE_NATIVE_mpn_addlsh2_n_ip2
1545 mp_limb_t
mpn_addlsh2_n_ip2_fun(mp_ptr rp,mp_srcptr sp,mp_size_t size)1546 mpn_addlsh2_n_ip2_fun (mp_ptr rp, mp_srcptr sp, mp_size_t size)
1547 {
1548 return mpn_addlsh2_n_ip2 (rp, sp, size);
1549 }
1550 #endif
1551 #if HAVE_NATIVE_mpn_addlsh_n_ip2
1552 mp_limb_t
mpn_addlsh_n_ip2_fun(mp_ptr rp,mp_srcptr sp,mp_size_t size,unsigned int sh)1553 mpn_addlsh_n_ip2_fun (mp_ptr rp, mp_srcptr sp, mp_size_t size, unsigned int sh)
1554 {
1555 return mpn_addlsh_n_ip2 (rp, sp, size, sh);
1556 }
1557 #endif
1558 #if HAVE_NATIVE_mpn_sublsh1_n_ip1
1559 mp_limb_t
mpn_sublsh1_n_ip1_fun(mp_ptr rp,mp_srcptr sp,mp_size_t size)1560 mpn_sublsh1_n_ip1_fun (mp_ptr rp, mp_srcptr sp, mp_size_t size)
1561 {
1562 return mpn_sublsh1_n_ip1 (rp, sp, size);
1563 }
1564 #endif
1565 #if HAVE_NATIVE_mpn_sublsh2_n_ip1
1566 mp_limb_t
mpn_sublsh2_n_ip1_fun(mp_ptr rp,mp_srcptr sp,mp_size_t size)1567 mpn_sublsh2_n_ip1_fun (mp_ptr rp, mp_srcptr sp, mp_size_t size)
1568 {
1569 return mpn_sublsh2_n_ip1 (rp, sp, size);
1570 }
1571 #endif
1572 #if HAVE_NATIVE_mpn_sublsh_n_ip1
1573 mp_limb_t
mpn_sublsh_n_ip1_fun(mp_ptr rp,mp_srcptr sp,mp_size_t size,unsigned int sh)1574 mpn_sublsh_n_ip1_fun (mp_ptr rp, mp_srcptr sp, mp_size_t size, unsigned int sh)
1575 {
1576 return mpn_sublsh_n_ip1 (rp, sp, size, sh);
1577 }
1578 #endif
1579
1580 mp_limb_t
mpn_modexact_1_odd_fun(mp_srcptr ptr,mp_size_t size,mp_limb_t divisor)1581 mpn_modexact_1_odd_fun (mp_srcptr ptr, mp_size_t size, mp_limb_t divisor)
1582 {
1583 return mpn_modexact_1_odd (ptr, size, divisor);
1584 }
1585
1586 void
mpn_toom22_mul_fun(mp_ptr dst,mp_srcptr src1,mp_srcptr src2,mp_size_t size)1587 mpn_toom22_mul_fun (mp_ptr dst, mp_srcptr src1, mp_srcptr src2, mp_size_t size)
1588 {
1589 mp_ptr tspace;
1590 TMP_DECL;
1591 TMP_MARK;
1592 tspace = TMP_ALLOC_LIMBS (mpn_toom22_mul_itch (size, size));
1593 mpn_toom22_mul (dst, src1, size, src2, size, tspace);
1594 TMP_FREE;
1595 }
1596 void
mpn_toom2_sqr_fun(mp_ptr dst,mp_srcptr src,mp_size_t size)1597 mpn_toom2_sqr_fun (mp_ptr dst, mp_srcptr src, mp_size_t size)
1598 {
1599 mp_ptr tspace;
1600 TMP_DECL;
1601 TMP_MARK;
1602 tspace = TMP_ALLOC_LIMBS (mpn_toom2_sqr_itch (size));
1603 mpn_toom2_sqr (dst, src, size, tspace);
1604 TMP_FREE;
1605 }
1606 void
mpn_toom33_mul_fun(mp_ptr dst,mp_srcptr src1,mp_srcptr src2,mp_size_t size)1607 mpn_toom33_mul_fun (mp_ptr dst, mp_srcptr src1, mp_srcptr src2, mp_size_t size)
1608 {
1609 mp_ptr tspace;
1610 TMP_DECL;
1611 TMP_MARK;
1612 tspace = TMP_ALLOC_LIMBS (mpn_toom33_mul_itch (size, size));
1613 mpn_toom33_mul (dst, src1, size, src2, size, tspace);
1614 TMP_FREE;
1615 }
1616 void
mpn_toom3_sqr_fun(mp_ptr dst,mp_srcptr src,mp_size_t size)1617 mpn_toom3_sqr_fun (mp_ptr dst, mp_srcptr src, mp_size_t size)
1618 {
1619 mp_ptr tspace;
1620 TMP_DECL;
1621 TMP_MARK;
1622 tspace = TMP_ALLOC_LIMBS (mpn_toom3_sqr_itch (size));
1623 mpn_toom3_sqr (dst, src, size, tspace);
1624 TMP_FREE;
1625 }
1626 void
mpn_toom44_mul_fun(mp_ptr dst,mp_srcptr src1,mp_srcptr src2,mp_size_t size)1627 mpn_toom44_mul_fun (mp_ptr dst, mp_srcptr src1, mp_srcptr src2, mp_size_t size)
1628 {
1629 mp_ptr tspace;
1630 TMP_DECL;
1631 TMP_MARK;
1632 tspace = TMP_ALLOC_LIMBS (mpn_toom44_mul_itch (size, size));
1633 mpn_toom44_mul (dst, src1, size, src2, size, tspace);
1634 TMP_FREE;
1635 }
1636 void
mpn_toom4_sqr_fun(mp_ptr dst,mp_srcptr src,mp_size_t size)1637 mpn_toom4_sqr_fun (mp_ptr dst, mp_srcptr src, mp_size_t size)
1638 {
1639 mp_ptr tspace;
1640 TMP_DECL;
1641 TMP_MARK;
1642 tspace = TMP_ALLOC_LIMBS (mpn_toom4_sqr_itch (size));
1643 mpn_toom4_sqr (dst, src, size, tspace);
1644 TMP_FREE;
1645 }
1646
1647 void
mpn_toom42_mulmid_fun(mp_ptr dst,mp_srcptr src1,mp_srcptr src2,mp_size_t size)1648 mpn_toom42_mulmid_fun (mp_ptr dst, mp_srcptr src1, mp_srcptr src2,
1649 mp_size_t size)
1650 {
1651 mp_ptr tspace;
1652 mp_size_t n;
1653 TMP_DECL;
1654 TMP_MARK;
1655 tspace = TMP_ALLOC_LIMBS (mpn_toom42_mulmid_itch (size));
1656 mpn_toom42_mulmid (dst, src1, src2, size, tspace);
1657 TMP_FREE;
1658 }
1659
1660 mp_limb_t
umul_ppmm_fun(mp_limb_t * lowptr,mp_limb_t m1,mp_limb_t m2)1661 umul_ppmm_fun (mp_limb_t *lowptr, mp_limb_t m1, mp_limb_t m2)
1662 {
1663 mp_limb_t high;
1664 umul_ppmm (high, *lowptr, m1, m2);
1665 return high;
1666 }
1667
1668 void
MPN_ZERO_fun(mp_ptr ptr,mp_size_t size)1669 MPN_ZERO_fun (mp_ptr ptr, mp_size_t size)
1670 { MPN_ZERO (ptr, size); }
1671
1672
1673 struct choice_t {
1674 const char *name;
1675 tryfun_t function;
1676 int type;
1677 mp_size_t minsize;
1678 };
1679
1680 #if HAVE_STRINGIZE
1681 #define TRY(fun) #fun, (tryfun_t) fun
1682 #define TRY_FUNFUN(fun) #fun, (tryfun_t) fun##_fun
1683 #else
1684 #define TRY(fun) "fun", (tryfun_t) fun
1685 #define TRY_FUNFUN(fun) "fun", (tryfun_t) fun/**/_fun
1686 #endif
1687
1688 const struct choice_t choice_array[] = {
1689 { TRY(mpn_add), TYPE_ADD },
1690 { TRY(mpn_sub), TYPE_SUB },
1691
1692 { TRY(mpn_add_n), TYPE_ADD_N },
1693 { TRY(mpn_sub_n), TYPE_SUB_N },
1694
1695 #if HAVE_NATIVE_mpn_add_nc
1696 { TRY(mpn_add_nc), TYPE_ADD_NC },
1697 #endif
1698 #if HAVE_NATIVE_mpn_sub_nc
1699 { TRY(mpn_sub_nc), TYPE_SUB_NC },
1700 #endif
1701
1702 #if HAVE_NATIVE_mpn_add_n_sub_n
1703 { TRY(mpn_add_n_sub_n), TYPE_ADDSUB_N },
1704 #endif
1705 #if HAVE_NATIVE_mpn_add_n_sub_nc
1706 { TRY(mpn_add_n_sub_nc), TYPE_ADDSUB_NC },
1707 #endif
1708
1709 { TRY(mpn_add_err1_n), TYPE_ADD_ERR1_N },
1710 { TRY(mpn_sub_err1_n), TYPE_SUB_ERR1_N },
1711 { TRY(mpn_add_err2_n), TYPE_ADD_ERR2_N },
1712 { TRY(mpn_sub_err2_n), TYPE_SUB_ERR2_N },
1713 { TRY(mpn_add_err3_n), TYPE_ADD_ERR3_N },
1714 { TRY(mpn_sub_err3_n), TYPE_SUB_ERR3_N },
1715
1716 { TRY(mpn_addmul_1), TYPE_ADDMUL_1 },
1717 { TRY(mpn_submul_1), TYPE_SUBMUL_1 },
1718 #if HAVE_NATIVE_mpn_addmul_1c
1719 { TRY(mpn_addmul_1c), TYPE_ADDMUL_1C },
1720 #endif
1721 #if HAVE_NATIVE_mpn_submul_1c
1722 { TRY(mpn_submul_1c), TYPE_SUBMUL_1C },
1723 #endif
1724
1725 #if HAVE_NATIVE_mpn_addmul_2
1726 { TRY(mpn_addmul_2), TYPE_ADDMUL_2, 2 },
1727 #endif
1728 #if HAVE_NATIVE_mpn_addmul_3
1729 { TRY(mpn_addmul_3), TYPE_ADDMUL_3, 3 },
1730 #endif
1731 #if HAVE_NATIVE_mpn_addmul_4
1732 { TRY(mpn_addmul_4), TYPE_ADDMUL_4, 4 },
1733 #endif
1734 #if HAVE_NATIVE_mpn_addmul_5
1735 { TRY(mpn_addmul_5), TYPE_ADDMUL_5, 5 },
1736 #endif
1737 #if HAVE_NATIVE_mpn_addmul_6
1738 { TRY(mpn_addmul_6), TYPE_ADDMUL_6, 6 },
1739 #endif
1740 #if HAVE_NATIVE_mpn_addmul_7
1741 { TRY(mpn_addmul_7), TYPE_ADDMUL_7, 7 },
1742 #endif
1743 #if HAVE_NATIVE_mpn_addmul_8
1744 { TRY(mpn_addmul_8), TYPE_ADDMUL_8, 8 },
1745 #endif
1746
1747 { TRY_FUNFUN(mpn_com), TYPE_COM },
1748
1749 { TRY_FUNFUN(MPN_COPY), TYPE_COPY },
1750 { TRY_FUNFUN(MPN_COPY_INCR), TYPE_COPYI },
1751 { TRY_FUNFUN(MPN_COPY_DECR), TYPE_COPYD },
1752
1753 { TRY_FUNFUN(__GMPN_COPY), TYPE_COPY },
1754 #ifdef __GMPN_COPY_INCR
1755 { TRY_FUNFUN(__GMPN_COPY_INCR), TYPE_COPYI },
1756 #endif
1757
1758 #if HAVE_NATIVE_mpn_copyi
1759 { TRY(mpn_copyi), TYPE_COPYI },
1760 #endif
1761 #if HAVE_NATIVE_mpn_copyd
1762 { TRY(mpn_copyd), TYPE_COPYD },
1763 #endif
1764
1765 { TRY(mpn_cnd_add_n), TYPE_ADDCND_N },
1766 { TRY(mpn_cnd_sub_n), TYPE_SUBCND_N },
1767 #if HAVE_NATIVE_mpn_addlsh1_n == 1
1768 { TRY(mpn_addlsh1_n), TYPE_ADDLSH1_N },
1769 #endif
1770 #if HAVE_NATIVE_mpn_addlsh2_n == 1
1771 { TRY(mpn_addlsh2_n), TYPE_ADDLSH2_N },
1772 #endif
1773 #if HAVE_NATIVE_mpn_addlsh_n
1774 { TRY(mpn_addlsh_n), TYPE_ADDLSH_N },
1775 #endif
1776 #if HAVE_NATIVE_mpn_addlsh1_n_ip1
1777 { TRY_FUNFUN(mpn_addlsh1_n_ip1), TYPE_ADDLSH1_N_IP1 },
1778 #endif
1779 #if HAVE_NATIVE_mpn_addlsh2_n_ip1
1780 { TRY_FUNFUN(mpn_addlsh2_n_ip1), TYPE_ADDLSH2_N_IP1 },
1781 #endif
1782 #if HAVE_NATIVE_mpn_addlsh_n_ip1
1783 { TRY_FUNFUN(mpn_addlsh_n_ip1), TYPE_ADDLSH_N_IP1 },
1784 #endif
1785 #if HAVE_NATIVE_mpn_addlsh1_n_ip2
1786 { TRY_FUNFUN(mpn_addlsh1_n_ip2), TYPE_ADDLSH1_N_IP2 },
1787 #endif
1788 #if HAVE_NATIVE_mpn_addlsh2_n_ip2
1789 { TRY_FUNFUN(mpn_addlsh2_n_ip2), TYPE_ADDLSH2_N_IP2 },
1790 #endif
1791 #if HAVE_NATIVE_mpn_addlsh_n_ip2
1792 { TRY_FUNFUN(mpn_addlsh_n_ip2), TYPE_ADDLSH_N_IP2 },
1793 #endif
1794 #if HAVE_NATIVE_mpn_sublsh1_n == 1
1795 { TRY(mpn_sublsh1_n), TYPE_SUBLSH1_N },
1796 #endif
1797 #if HAVE_NATIVE_mpn_sublsh2_n == 1
1798 { TRY(mpn_sublsh2_n), TYPE_SUBLSH2_N },
1799 #endif
1800 #if HAVE_NATIVE_mpn_sublsh_n
1801 { TRY(mpn_sublsh_n), TYPE_SUBLSH_N },
1802 #endif
1803 #if HAVE_NATIVE_mpn_sublsh1_n_ip1
1804 { TRY_FUNFUN(mpn_sublsh1_n_ip1), TYPE_SUBLSH1_N_IP1 },
1805 #endif
1806 #if HAVE_NATIVE_mpn_sublsh2_n_ip1
1807 { TRY_FUNFUN(mpn_sublsh2_n_ip1), TYPE_SUBLSH2_N_IP1 },
1808 #endif
1809 #if HAVE_NATIVE_mpn_sublsh_n_ip1
1810 { TRY_FUNFUN(mpn_sublsh_n_ip1), TYPE_SUBLSH_N_IP1 },
1811 #endif
1812 #if HAVE_NATIVE_mpn_rsblsh1_n == 1
1813 { TRY(mpn_rsblsh1_n), TYPE_RSBLSH1_N },
1814 #endif
1815 #if HAVE_NATIVE_mpn_rsblsh2_n == 1
1816 { TRY(mpn_rsblsh2_n), TYPE_RSBLSH2_N },
1817 #endif
1818 #if HAVE_NATIVE_mpn_rsblsh_n
1819 { TRY(mpn_rsblsh_n), TYPE_RSBLSH_N },
1820 #endif
1821 #if HAVE_NATIVE_mpn_rsh1add_n
1822 { TRY(mpn_rsh1add_n), TYPE_RSH1ADD_N },
1823 #endif
1824 #if HAVE_NATIVE_mpn_rsh1sub_n
1825 { TRY(mpn_rsh1sub_n), TYPE_RSH1SUB_N },
1826 #endif
1827
1828 #if HAVE_NATIVE_mpn_addlsh1_nc
1829 { TRY(mpn_addlsh1_nc), TYPE_ADDLSH1_NC },
1830 #endif
1831 #if HAVE_NATIVE_mpn_addlsh2_nc
1832 { TRY(mpn_addlsh2_nc), TYPE_ADDLSH2_NC },
1833 #endif
1834 #if HAVE_NATIVE_mpn_addlsh_nc
1835 { TRY(mpn_addlsh_nc), TYPE_ADDLSH_NC },
1836 #endif
1837 #if HAVE_NATIVE_mpn_sublsh1_nc
1838 { TRY(mpn_sublsh1_nc), TYPE_SUBLSH1_NC },
1839 #endif
1840 #if HAVE_NATIVE_mpn_sublsh2_nc
1841 { TRY(mpn_sublsh2_nc), TYPE_SUBLSH2_NC },
1842 #endif
1843 #if HAVE_NATIVE_mpn_sublsh_nc
1844 { TRY(mpn_sublsh_nc), TYPE_SUBLSH_NC },
1845 #endif
1846 #if HAVE_NATIVE_mpn_rsblsh1_nc
1847 { TRY(mpn_rsblsh1_nc), TYPE_RSBLSH1_NC },
1848 #endif
1849 #if HAVE_NATIVE_mpn_rsblsh2_nc
1850 { TRY(mpn_rsblsh2_nc), TYPE_RSBLSH2_NC },
1851 #endif
1852 #if HAVE_NATIVE_mpn_rsblsh_nc
1853 { TRY(mpn_rsblsh_nc), TYPE_RSBLSH_NC },
1854 #endif
1855
1856 { TRY_FUNFUN(mpn_and_n), TYPE_AND_N },
1857 { TRY_FUNFUN(mpn_andn_n), TYPE_ANDN_N },
1858 { TRY_FUNFUN(mpn_nand_n), TYPE_NAND_N },
1859 { TRY_FUNFUN(mpn_ior_n), TYPE_IOR_N },
1860 { TRY_FUNFUN(mpn_iorn_n), TYPE_IORN_N },
1861 { TRY_FUNFUN(mpn_nior_n), TYPE_NIOR_N },
1862 { TRY_FUNFUN(mpn_xor_n), TYPE_XOR_N },
1863 { TRY_FUNFUN(mpn_xnor_n), TYPE_XNOR_N },
1864
1865 { TRY(mpn_divrem_1), TYPE_DIVREM_1 },
1866 #if USE_PREINV_DIVREM_1
1867 { TRY(mpn_preinv_divrem_1), TYPE_PREINV_DIVREM_1 },
1868 #endif
1869 { TRY(mpn_mod_1), TYPE_MOD_1 },
1870 #if USE_PREINV_MOD_1
1871 { TRY(mpn_preinv_mod_1), TYPE_PREINV_MOD_1 },
1872 #endif
1873 #if HAVE_NATIVE_mpn_divrem_1c
1874 { TRY(mpn_divrem_1c), TYPE_DIVREM_1C },
1875 #endif
1876 #if HAVE_NATIVE_mpn_mod_1c
1877 { TRY(mpn_mod_1c), TYPE_MOD_1C },
1878 #endif
1879 { TRY(mpn_div_qr_1n_pi1), TYPE_DIV_QR_1N_PI1 },
1880 #if GMP_NUMB_BITS % 4 == 0
1881 { TRY(mpn_mod_34lsub1), TYPE_MOD_34LSUB1 },
1882 #endif
1883
1884 { TRY_FUNFUN(udiv_qrnnd), TYPE_UDIV_QRNND, 2 },
1885 #if HAVE_NATIVE_mpn_udiv_qrnnd
1886 { TRY(mpn_udiv_qrnnd), TYPE_UDIV_QRNND, 2 },
1887 #endif
1888 #if HAVE_NATIVE_mpn_udiv_qrnnd_r
1889 { TRY(mpn_udiv_qrnnd_r), TYPE_UDIV_QRNND_R, 2 },
1890 #endif
1891
1892 { TRY(mpn_divexact_1), TYPE_DIVEXACT_1 },
1893 { TRY(mpn_bdiv_q_1), TYPE_BDIV_Q_1 },
1894 { TRY_FUNFUN(mpn_divexact_by3), TYPE_DIVEXACT_BY3 },
1895 { TRY(mpn_divexact_by3c), TYPE_DIVEXACT_BY3C },
1896
1897 { TRY_FUNFUN(mpn_modexact_1_odd), TYPE_MODEXACT_1_ODD },
1898 { TRY(mpn_modexact_1c_odd), TYPE_MODEXACT_1C_ODD },
1899
1900
1901 { TRY(mpn_sbpi1_div_qr), TYPE_SBPI1_DIV_QR, 3},
1902 { TRY(mpn_tdiv_qr), TYPE_TDIV_QR },
1903
1904 { TRY(mpn_mul_1), TYPE_MUL_1 },
1905 #if HAVE_NATIVE_mpn_mul_1c
1906 { TRY(mpn_mul_1c), TYPE_MUL_1C },
1907 #endif
1908 #if HAVE_NATIVE_mpn_mul_2
1909 { TRY(mpn_mul_2), TYPE_MUL_2, 2 },
1910 #endif
1911 #if HAVE_NATIVE_mpn_mul_3
1912 { TRY(mpn_mul_3), TYPE_MUL_3, 3 },
1913 #endif
1914 #if HAVE_NATIVE_mpn_mul_4
1915 { TRY(mpn_mul_4), TYPE_MUL_4, 4 },
1916 #endif
1917 #if HAVE_NATIVE_mpn_mul_5
1918 { TRY(mpn_mul_5), TYPE_MUL_5, 5 },
1919 #endif
1920 #if HAVE_NATIVE_mpn_mul_6
1921 { TRY(mpn_mul_6), TYPE_MUL_6, 6 },
1922 #endif
1923
1924 { TRY(mpn_rshift), TYPE_RSHIFT },
1925 { TRY(mpn_lshift), TYPE_LSHIFT },
1926 { TRY(mpn_lshiftc), TYPE_LSHIFTC },
1927
1928
1929 { TRY(mpn_mul_basecase), TYPE_MUL_MN },
1930 { TRY(mpn_mulmid_basecase), TYPE_MULMID_MN },
1931 { TRY(mpn_mullo_basecase), TYPE_MULLO_N },
1932 #if SQR_TOOM2_THRESHOLD > 0
1933 { TRY(mpn_sqr_basecase), TYPE_SQR },
1934 #endif
1935
1936 { TRY(mpn_mul), TYPE_MUL_MN },
1937 { TRY(mpn_mul_n), TYPE_MUL_N },
1938 { TRY(mpn_sqr), TYPE_SQR },
1939
1940 { TRY_FUNFUN(umul_ppmm), TYPE_UMUL_PPMM, 2 },
1941 #if HAVE_NATIVE_mpn_umul_ppmm
1942 { TRY(mpn_umul_ppmm), TYPE_UMUL_PPMM, 2 },
1943 #endif
1944 #if HAVE_NATIVE_mpn_umul_ppmm_r
1945 { TRY(mpn_umul_ppmm_r), TYPE_UMUL_PPMM_R, 2 },
1946 #endif
1947
1948 { TRY_FUNFUN(mpn_toom22_mul), TYPE_MUL_N, MPN_TOOM22_MUL_MINSIZE },
1949 { TRY_FUNFUN(mpn_toom2_sqr), TYPE_SQR, MPN_TOOM2_SQR_MINSIZE },
1950 { TRY_FUNFUN(mpn_toom33_mul), TYPE_MUL_N, MPN_TOOM33_MUL_MINSIZE },
1951 { TRY_FUNFUN(mpn_toom3_sqr), TYPE_SQR, MPN_TOOM3_SQR_MINSIZE },
1952 { TRY_FUNFUN(mpn_toom44_mul), TYPE_MUL_N, MPN_TOOM44_MUL_MINSIZE },
1953 { TRY_FUNFUN(mpn_toom4_sqr), TYPE_SQR, MPN_TOOM4_SQR_MINSIZE },
1954
1955 { TRY(mpn_mulmid_n), TYPE_MULMID_N, 1 },
1956 { TRY(mpn_mulmid), TYPE_MULMID_MN, 1 },
1957 { TRY_FUNFUN(mpn_toom42_mulmid), TYPE_MULMID_N,
1958 (2 * MPN_TOOM42_MULMID_MINSIZE - 1) },
1959
1960 { TRY(mpn_gcd_1), TYPE_GCD_1 },
1961 { TRY(mpn_gcd), TYPE_GCD },
1962 { TRY(mpz_legendre), TYPE_MPZ_LEGENDRE },
1963 { TRY(mpz_jacobi), TYPE_MPZ_JACOBI },
1964 { TRY(mpz_kronecker), TYPE_MPZ_KRONECKER },
1965 { TRY(mpz_kronecker_ui), TYPE_MPZ_KRONECKER_UI },
1966 { TRY(mpz_kronecker_si), TYPE_MPZ_KRONECKER_SI },
1967 { TRY(mpz_ui_kronecker), TYPE_MPZ_UI_KRONECKER },
1968 { TRY(mpz_si_kronecker), TYPE_MPZ_SI_KRONECKER },
1969
1970 { TRY(mpn_popcount), TYPE_POPCOUNT },
1971 { TRY(mpn_hamdist), TYPE_HAMDIST },
1972
1973 { TRY(mpn_sqrtrem), TYPE_SQRTREM },
1974
1975 { TRY_FUNFUN(MPN_ZERO), TYPE_ZERO },
1976
1977 { TRY(mpn_get_str), TYPE_GET_STR },
1978
1979 { TRY(mpn_binvert), TYPE_BINVERT },
1980 { TRY(mpn_invert), TYPE_INVERT },
1981
1982 #ifdef EXTRA_ROUTINES
1983 EXTRA_ROUTINES
1984 #endif
1985 };
1986
1987 const struct choice_t *choice = NULL;
1988
1989
1990 void
mprotect_maybe(void * addr,size_t len,int prot)1991 mprotect_maybe (void *addr, size_t len, int prot)
1992 {
1993 if (!option_redzones)
1994 return;
1995
1996 #if HAVE_MPROTECT
1997 if (mprotect (addr, len, prot) != 0)
1998 {
1999 fprintf (stderr, "Cannot mprotect %p 0x%X 0x%X: %s\n",
2000 addr, (unsigned) len, prot, strerror (errno));
2001 exit (1);
2002 }
2003 #else
2004 {
2005 static int warned = 0;
2006 if (!warned)
2007 {
2008 fprintf (stderr,
2009 "mprotect not available, bounds testing not performed\n");
2010 warned = 1;
2011 }
2012 }
2013 #endif
2014 }
2015
2016 /* round "a" up to a multiple of "m" */
2017 size_t
round_up_multiple(size_t a,size_t m)2018 round_up_multiple (size_t a, size_t m)
2019 {
2020 unsigned long r;
2021
2022 r = a % m;
2023 if (r == 0)
2024 return a;
2025 else
2026 return a + (m - r);
2027 }
2028
2029
2030 /* On some systems it seems that only an mmap'ed region can be mprotect'ed,
2031 for instance HP-UX 10.
2032
2033 mmap will almost certainly return a pointer already aligned to a page
2034 boundary, but it's easy enough to share the alignment handling with the
2035 malloc case. */
2036
2037 void
malloc_region(struct region_t * r,mp_size_t n)2038 malloc_region (struct region_t *r, mp_size_t n)
2039 {
2040 mp_ptr p;
2041 size_t nbytes;
2042
2043 ASSERT ((pagesize % GMP_LIMB_BYTES) == 0);
2044
2045 n = round_up_multiple (n, PAGESIZE_LIMBS);
2046 r->size = n;
2047
2048 nbytes = n*GMP_LIMB_BYTES + 2*REDZONE_BYTES + pagesize;
2049
2050 #if defined (MAP_ANONYMOUS) && ! defined (MAP_ANON)
2051 #define MAP_ANON MAP_ANONYMOUS
2052 #endif
2053
2054 #if HAVE_MMAP && defined (MAP_ANON)
2055 /* note must pass fd=-1 for MAP_ANON on BSD */
2056 p = (mp_ptr) mmap (NULL, nbytes, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANON, -1, 0);
2057 if (p == (void *) -1)
2058 {
2059 fprintf (stderr, "Cannot mmap %#x anon bytes: %s\n",
2060 (unsigned) nbytes, strerror (errno));
2061 exit (1);
2062 }
2063 #else
2064 p = (mp_ptr) malloc (nbytes);
2065 ASSERT_ALWAYS (p != NULL);
2066 #endif
2067
2068 p = (mp_ptr) align_pointer (p, pagesize);
2069
2070 mprotect_maybe (p, REDZONE_BYTES, PROT_NONE);
2071 p += REDZONE_LIMBS;
2072 r->ptr = p;
2073
2074 mprotect_maybe (p + n, REDZONE_BYTES, PROT_NONE);
2075 }
2076
2077 void
mprotect_region(const struct region_t * r,int prot)2078 mprotect_region (const struct region_t *r, int prot)
2079 {
2080 mprotect_maybe (r->ptr, r->size, prot);
2081 }
2082
2083
2084 /* First four entries must be 0,1,2,3 for the benefit of CARRY_BIT, CARRY_3,
2085 and CARRY_4 */
2086 mp_limb_t carry_array[] = {
2087 0, 1, 2, 3,
2088 4,
2089 CNST_LIMB(1) << 8,
2090 CNST_LIMB(1) << 16,
2091 GMP_NUMB_MAX
2092 };
2093 int carry_index;
2094
2095 #define CARRY_COUNT \
2096 ((tr->carry == CARRY_BIT) ? 2 \
2097 : tr->carry == CARRY_3 ? 3 \
2098 : tr->carry == CARRY_4 ? 4 \
2099 : (tr->carry == CARRY_LIMB || tr->carry == CARRY_DIVISOR) \
2100 ? numberof(carry_array) + CARRY_RANDOMS \
2101 : 1)
2102
2103 #define MPN_RANDOM_ALT(index,dst,size) \
2104 (((index) & 1) ? refmpn_random (dst, size) : refmpn_random2 (dst, size))
2105
2106 /* The dummy value after MPN_RANDOM_ALT ensures both sides of the ":" have
2107 the same type */
2108 #define CARRY_ITERATION \
2109 for (carry_index = 0; \
2110 (carry_index < numberof (carry_array) \
2111 ? (carry = carry_array[carry_index]) \
2112 : (MPN_RANDOM_ALT (carry_index, &carry, 1), (mp_limb_t) 0)), \
2113 (tr->carry == CARRY_DIVISOR ? carry %= divisor : 0), \
2114 carry_index < CARRY_COUNT; \
2115 carry_index++)
2116
2117
2118 mp_limb_t multiplier_array[] = {
2119 0, 1, 2, 3,
2120 CNST_LIMB(1) << 8,
2121 CNST_LIMB(1) << 16,
2122 GMP_NUMB_MAX - 2,
2123 GMP_NUMB_MAX - 1,
2124 GMP_NUMB_MAX
2125 };
2126 int multiplier_index;
2127
2128 mp_limb_t divisor_array[] = {
2129 1, 2, 3,
2130 CNST_LIMB(1) << 8,
2131 CNST_LIMB(1) << 16,
2132 CNST_LIMB(1) << (GMP_NUMB_BITS/2 - 1),
2133 GMP_NUMB_MAX >> (GMP_NUMB_BITS/2),
2134 GMP_NUMB_HIGHBIT,
2135 GMP_NUMB_HIGHBIT + 1,
2136 GMP_NUMB_MAX - 2,
2137 GMP_NUMB_MAX - 1,
2138 GMP_NUMB_MAX
2139 };
2140
2141 int divisor_index;
2142
2143 /* The dummy value after MPN_RANDOM_ALT ensures both sides of the ":" have
2144 the same type */
2145 #define ARRAY_ITERATION(var, index, limit, array, randoms, cond) \
2146 for (index = 0; \
2147 (index < numberof (array) \
2148 ? (var = array[index]) \
2149 : (MPN_RANDOM_ALT (index, &var, 1), (mp_limb_t) 0)), \
2150 index < limit; \
2151 index++)
2152
2153 #define MULTIPLIER_COUNT \
2154 (tr->multiplier \
2155 ? numberof (multiplier_array) + MULTIPLIER_RANDOMS \
2156 : 1)
2157
2158 #define MULTIPLIER_ITERATION \
2159 ARRAY_ITERATION(multiplier, multiplier_index, MULTIPLIER_COUNT, \
2160 multiplier_array, MULTIPLIER_RANDOMS, TRY_MULTIPLIER)
2161
2162 #define DIVISOR_COUNT \
2163 (tr->divisor \
2164 ? numberof (divisor_array) + DIVISOR_RANDOMS \
2165 : 1)
2166
2167 #define DIVISOR_ITERATION \
2168 ARRAY_ITERATION(divisor, divisor_index, DIVISOR_COUNT, divisor_array, \
2169 DIVISOR_RANDOMS, TRY_DIVISOR)
2170
2171
2172 /* overlap_array[].s[i] is where s[i] should be, 0 or 1 means overlapping
2173 d[0] or d[1] respectively, -1 means a separate (write-protected)
2174 location. */
2175
2176 struct overlap_t {
2177 int s[NUM_SOURCES];
2178 } overlap_array[] = {
2179 { { -1, -1, -1, -1, -1 } },
2180 { { 0, -1, -1, -1, -1 } },
2181 { { -1, 0, -1, -1, -1 } },
2182 { { 0, 0, -1, -1, -1 } },
2183 { { 1, -1, -1, -1, -1 } },
2184 { { -1, 1, -1, -1, -1 } },
2185 { { 1, 1, -1, -1, -1 } },
2186 { { 0, 1, -1, -1, -1 } },
2187 { { 1, 0, -1, -1, -1 } },
2188 };
2189
2190 struct overlap_t *overlap, *overlap_limit;
2191
2192 #define OVERLAP_COUNT \
2193 (tr->overlap & OVERLAP_NONE ? 1 \
2194 : tr->overlap & OVERLAP_NOT_SRCS ? 3 \
2195 : tr->overlap & OVERLAP_NOT_SRC2 ? 2 \
2196 : tr->overlap & OVERLAP_NOT_DST2 ? 4 \
2197 : tr->dst[1] ? 9 \
2198 : tr->src[1] ? 4 \
2199 : tr->dst[0] ? 2 \
2200 : 1)
2201
2202 #define OVERLAP_ITERATION \
2203 for (overlap = &overlap_array[0], \
2204 overlap_limit = &overlap_array[OVERLAP_COUNT]; \
2205 overlap < overlap_limit; \
2206 overlap++)
2207
2208
2209 int base = 10;
2210
2211 #define T_RAND_COUNT 2
2212 int t_rand;
2213
2214 void
t_random(mp_ptr ptr,mp_size_t n)2215 t_random (mp_ptr ptr, mp_size_t n)
2216 {
2217 if (n == 0)
2218 return;
2219
2220 switch (option_data) {
2221 case DATA_TRAND:
2222 switch (t_rand) {
2223 case 0: refmpn_random (ptr, n); break;
2224 case 1: refmpn_random2 (ptr, n); break;
2225 default: abort();
2226 }
2227 break;
2228 case DATA_SEQ:
2229 {
2230 static mp_limb_t counter = 0;
2231 mp_size_t i;
2232 for (i = 0; i < n; i++)
2233 ptr[i] = ++counter;
2234 }
2235 break;
2236 case DATA_ZEROS:
2237 refmpn_zero (ptr, n);
2238 break;
2239 case DATA_FFS:
2240 refmpn_fill (ptr, n, GMP_NUMB_MAX);
2241 break;
2242 case DATA_2FD:
2243 /* Special value 0x2FFF...FFFD, which divided by 3 gives 0xFFF...FFF,
2244 inducing the q1_ff special case in the mul-by-inverse part of some
2245 versions of divrem_1 and mod_1. */
2246 refmpn_fill (ptr, n, (mp_limb_t) -1);
2247 ptr[n-1] = 2;
2248 ptr[0] -= 2;
2249 break;
2250
2251 default:
2252 abort();
2253 }
2254 }
2255 #define T_RAND_ITERATION \
2256 for (t_rand = 0; t_rand < T_RAND_COUNT; t_rand++)
2257
2258
2259 void
print_each(const struct each_t * e)2260 print_each (const struct each_t *e)
2261 {
2262 int i;
2263
2264 printf ("%s %s\n", e->name, e == &ref ? tr->reference_name : choice->name);
2265 if (tr->retval)
2266 mpn_trace (" retval", &e->retval, 1);
2267
2268 for (i = 0; i < NUM_DESTS; i++)
2269 {
2270 if (tr->dst[i])
2271 {
2272 if (tr->dst_bytes[i])
2273 byte_tracen (" d[%d]", i, e->d[i].p, d[i].size);
2274 else
2275 mpn_tracen (" d[%d]", i, e->d[i].p, d[i].size);
2276 printf (" located %p\n", (void *) (e->d[i].p));
2277 }
2278 }
2279
2280 for (i = 0; i < NUM_SOURCES; i++)
2281 if (tr->src[i])
2282 printf (" s[%d] located %p\n", i, (void *) (e->s[i].p));
2283 }
2284
2285
2286 void
print_all(void)2287 print_all (void)
2288 {
2289 int i;
2290
2291 printf ("\n");
2292 printf ("size %ld\n", (long) size);
2293 if (tr->size2)
2294 printf ("size2 %ld\n", (long) size2);
2295
2296 for (i = 0; i < NUM_DESTS; i++)
2297 if (d[i].size != size)
2298 printf ("d[%d].size %ld\n", i, (long) d[i].size);
2299
2300 if (tr->multiplier)
2301 mpn_trace (" multiplier", &multiplier, 1);
2302 if (tr->divisor)
2303 mpn_trace (" divisor", &divisor, 1);
2304 if (tr->shift)
2305 printf (" shift %lu\n", shift);
2306 if (tr->carry)
2307 mpn_trace (" carry", &carry, 1);
2308 if (tr->msize)
2309 mpn_trace (" multiplier_N", multiplier_N, tr->msize);
2310
2311 for (i = 0; i < NUM_DESTS; i++)
2312 if (tr->dst[i])
2313 printf (" d[%d] %s, align %ld, size %ld\n",
2314 i, d[i].high ? "high" : "low",
2315 (long) d[i].align, (long) d[i].size);
2316
2317 for (i = 0; i < NUM_SOURCES; i++)
2318 {
2319 if (tr->src[i])
2320 {
2321 printf (" s[%d] %s, align %ld, ",
2322 i, s[i].high ? "high" : "low", (long) s[i].align);
2323 switch (overlap->s[i]) {
2324 case -1:
2325 printf ("no overlap\n");
2326 break;
2327 default:
2328 printf ("==d[%d]%s\n",
2329 overlap->s[i],
2330 tr->overlap == OVERLAP_LOW_TO_HIGH ? "+a"
2331 : tr->overlap == OVERLAP_HIGH_TO_LOW ? "-a"
2332 : "");
2333 break;
2334 }
2335 printf (" s[%d]=", i);
2336 if (tr->carry_sign && (carry & (1 << i)))
2337 printf ("-");
2338 mpn_trace (NULL, s[i].p, SRC_SIZE(i));
2339 }
2340 }
2341
2342 if (tr->dst0_from_src1)
2343 mpn_trace (" d[0]", s[1].region.ptr, size);
2344
2345 if (tr->reference)
2346 print_each (&ref);
2347 print_each (&fun);
2348 }
2349
2350 void
compare(void)2351 compare (void)
2352 {
2353 int error = 0;
2354 int i;
2355
2356 if (tr->retval && ref.retval != fun.retval)
2357 {
2358 gmp_printf ("Different return values (%Mu, %Mu)\n",
2359 ref.retval, fun.retval);
2360 error = 1;
2361 }
2362
2363 for (i = 0; i < NUM_DESTS; i++)
2364 {
2365 switch (tr->dst_size[i]) {
2366 case SIZE_RETVAL:
2367 case SIZE_GET_STR:
2368 d[i].size = ref.retval;
2369 break;
2370 }
2371 }
2372
2373 for (i = 0; i < NUM_DESTS; i++)
2374 {
2375 if (! tr->dst[i])
2376 continue;
2377
2378 if (tr->dst_bytes[i])
2379 {
2380 if (memcmp (ref.d[i].p, fun.d[i].p, d[i].size) != 0)
2381 {
2382 printf ("Different d[%d] data results, low diff at %ld, high diff at %ld\n",
2383 i,
2384 (long) byte_diff_lowest (ref.d[i].p, fun.d[i].p, d[i].size),
2385 (long) byte_diff_highest (ref.d[i].p, fun.d[i].p, d[i].size));
2386 error = 1;
2387 }
2388 }
2389 else
2390 {
2391 if (d[i].size != 0
2392 && ! refmpn_equal_anynail (ref.d[i].p, fun.d[i].p, d[i].size))
2393 {
2394 printf ("Different d[%d] data results, low diff at %ld, high diff at %ld\n",
2395 i,
2396 (long) mpn_diff_lowest (ref.d[i].p, fun.d[i].p, d[i].size),
2397 (long) mpn_diff_highest (ref.d[i].p, fun.d[i].p, d[i].size));
2398 error = 1;
2399 }
2400 }
2401 }
2402
2403 if (error)
2404 {
2405 print_all();
2406 abort();
2407 }
2408 }
2409
2410
2411 /* The functions are cast if the return value should be a long rather than
2412 the default mp_limb_t. This is necessary under _LONG_LONG_LIMB. This
2413 might not be enough if some actual calling conventions checking is
2414 implemented on a long long limb system. */
2415
2416 void
call(struct each_t * e,tryfun_t function)2417 call (struct each_t *e, tryfun_t function)
2418 {
2419 switch (choice->type) {
2420 case TYPE_ADD:
2421 case TYPE_SUB:
2422 e->retval = CALLING_CONVENTIONS (function)
2423 (e->d[0].p, e->s[0].p, size, e->s[1].p, size2);
2424 break;
2425
2426 case TYPE_ADD_N:
2427 case TYPE_SUB_N:
2428 case TYPE_ADDLSH1_N:
2429 case TYPE_ADDLSH2_N:
2430 case TYPE_SUBLSH1_N:
2431 case TYPE_SUBLSH2_N:
2432 case TYPE_RSBLSH1_N:
2433 case TYPE_RSBLSH2_N:
2434 case TYPE_RSH1ADD_N:
2435 case TYPE_RSH1SUB_N:
2436 e->retval = CALLING_CONVENTIONS (function)
2437 (e->d[0].p, e->s[0].p, e->s[1].p, size);
2438 break;
2439 case TYPE_ADDLSH_N:
2440 case TYPE_SUBLSH_N:
2441 case TYPE_RSBLSH_N:
2442 e->retval = CALLING_CONVENTIONS (function)
2443 (e->d[0].p, e->s[0].p, e->s[1].p, size, shift);
2444 break;
2445 case TYPE_ADDLSH_NC:
2446 case TYPE_SUBLSH_NC:
2447 case TYPE_RSBLSH_NC:
2448 e->retval = CALLING_CONVENTIONS (function)
2449 (e->d[0].p, e->s[0].p, e->s[1].p, size, shift, carry);
2450 break;
2451 case TYPE_ADDLSH1_NC:
2452 case TYPE_ADDLSH2_NC:
2453 case TYPE_SUBLSH1_NC:
2454 case TYPE_SUBLSH2_NC:
2455 case TYPE_RSBLSH1_NC:
2456 case TYPE_RSBLSH2_NC:
2457 case TYPE_ADD_NC:
2458 case TYPE_SUB_NC:
2459 e->retval = CALLING_CONVENTIONS (function)
2460 (e->d[0].p, e->s[0].p, e->s[1].p, size, carry);
2461 break;
2462 case TYPE_ADDCND_N:
2463 case TYPE_SUBCND_N:
2464 e->retval = CALLING_CONVENTIONS (function)
2465 (carry, e->d[0].p, e->s[0].p, e->s[1].p, size);
2466 break;
2467 case TYPE_ADD_ERR1_N:
2468 case TYPE_SUB_ERR1_N:
2469 e->retval = CALLING_CONVENTIONS (function)
2470 (e->d[0].p, e->s[0].p, e->s[1].p, e->d[1].p, e->s[2].p, size, carry);
2471 break;
2472 case TYPE_ADD_ERR2_N:
2473 case TYPE_SUB_ERR2_N:
2474 e->retval = CALLING_CONVENTIONS (function)
2475 (e->d[0].p, e->s[0].p, e->s[1].p, e->d[1].p, e->s[2].p, e->s[3].p, size, carry);
2476 break;
2477 case TYPE_ADD_ERR3_N:
2478 case TYPE_SUB_ERR3_N:
2479 e->retval = CALLING_CONVENTIONS (function)
2480 (e->d[0].p, e->s[0].p, e->s[1].p, e->d[1].p, e->s[2].p, e->s[3].p, e->s[4].p, size, carry);
2481 break;
2482
2483 case TYPE_MUL_1:
2484 case TYPE_ADDMUL_1:
2485 case TYPE_SUBMUL_1:
2486 e->retval = CALLING_CONVENTIONS (function)
2487 (e->d[0].p, e->s[0].p, size, multiplier);
2488 break;
2489 case TYPE_MUL_1C:
2490 case TYPE_ADDMUL_1C:
2491 case TYPE_SUBMUL_1C:
2492 e->retval = CALLING_CONVENTIONS (function)
2493 (e->d[0].p, e->s[0].p, size, multiplier, carry);
2494 break;
2495
2496 case TYPE_MUL_2:
2497 case TYPE_MUL_3:
2498 case TYPE_MUL_4:
2499 case TYPE_MUL_5:
2500 case TYPE_MUL_6:
2501 if (size == 1)
2502 abort ();
2503 e->retval = CALLING_CONVENTIONS (function)
2504 (e->d[0].p, e->s[0].p, size, multiplier_N);
2505 break;
2506
2507 case TYPE_ADDMUL_2:
2508 case TYPE_ADDMUL_3:
2509 case TYPE_ADDMUL_4:
2510 case TYPE_ADDMUL_5:
2511 case TYPE_ADDMUL_6:
2512 case TYPE_ADDMUL_7:
2513 case TYPE_ADDMUL_8:
2514 if (size == 1)
2515 abort ();
2516 e->retval = CALLING_CONVENTIONS (function)
2517 (e->d[0].p, e->s[0].p, size, multiplier_N);
2518 break;
2519
2520 case TYPE_AND_N:
2521 case TYPE_ANDN_N:
2522 case TYPE_NAND_N:
2523 case TYPE_IOR_N:
2524 case TYPE_IORN_N:
2525 case TYPE_NIOR_N:
2526 case TYPE_XOR_N:
2527 case TYPE_XNOR_N:
2528 CALLING_CONVENTIONS (function) (e->d[0].p, e->s[0].p, e->s[1].p, size);
2529 break;
2530
2531 case TYPE_ADDSUB_N:
2532 e->retval = CALLING_CONVENTIONS (function)
2533 (e->d[0].p, e->d[1].p, e->s[0].p, e->s[1].p, size);
2534 break;
2535 case TYPE_ADDSUB_NC:
2536 e->retval = CALLING_CONVENTIONS (function)
2537 (e->d[0].p, e->d[1].p, e->s[0].p, e->s[1].p, size, carry);
2538 break;
2539
2540 case TYPE_COPY:
2541 case TYPE_COPYI:
2542 case TYPE_COPYD:
2543 case TYPE_COM:
2544 CALLING_CONVENTIONS (function) (e->d[0].p, e->s[0].p, size);
2545 break;
2546
2547 case TYPE_ADDLSH1_N_IP1:
2548 case TYPE_ADDLSH2_N_IP1:
2549 case TYPE_ADDLSH1_N_IP2:
2550 case TYPE_ADDLSH2_N_IP2:
2551 case TYPE_SUBLSH1_N_IP1:
2552 case TYPE_SUBLSH2_N_IP1:
2553 case TYPE_DIVEXACT_BY3:
2554 e->retval = CALLING_CONVENTIONS (function) (e->d[0].p, e->s[0].p, size);
2555 break;
2556 case TYPE_DIVEXACT_BY3C:
2557 e->retval = CALLING_CONVENTIONS (function) (e->d[0].p, e->s[0].p, size,
2558 carry);
2559 break;
2560
2561
2562 case TYPE_DIVMOD_1:
2563 case TYPE_DIVEXACT_1:
2564 case TYPE_BDIV_Q_1:
2565 e->retval = CALLING_CONVENTIONS (function)
2566 (e->d[0].p, e->s[0].p, size, divisor);
2567 break;
2568 case TYPE_DIVMOD_1C:
2569 e->retval = CALLING_CONVENTIONS (function)
2570 (e->d[0].p, e->s[0].p, size, divisor, carry);
2571 break;
2572 case TYPE_DIVREM_1:
2573 e->retval = CALLING_CONVENTIONS (function)
2574 (e->d[0].p, size2, e->s[0].p, size, divisor);
2575 break;
2576 case TYPE_DIVREM_1C:
2577 e->retval = CALLING_CONVENTIONS (function)
2578 (e->d[0].p, size2, e->s[0].p, size, divisor, carry);
2579 break;
2580 case TYPE_PREINV_DIVREM_1:
2581 {
2582 mp_limb_t dinv;
2583 unsigned shift;
2584 shift = refmpn_count_leading_zeros (divisor);
2585 dinv = refmpn_invert_limb (divisor << shift);
2586 e->retval = CALLING_CONVENTIONS (function)
2587 (e->d[0].p, size2, e->s[0].p, size, divisor, dinv, shift);
2588 }
2589 break;
2590 case TYPE_MOD_1:
2591 case TYPE_MODEXACT_1_ODD:
2592 e->retval = CALLING_CONVENTIONS (function)
2593 (e->s[0].p, size, divisor);
2594 break;
2595 case TYPE_MOD_1C:
2596 case TYPE_MODEXACT_1C_ODD:
2597 e->retval = CALLING_CONVENTIONS (function)
2598 (e->s[0].p, size, divisor, carry);
2599 break;
2600 case TYPE_PREINV_MOD_1:
2601 e->retval = CALLING_CONVENTIONS (function)
2602 (e->s[0].p, size, divisor, refmpn_invert_limb (divisor));
2603 break;
2604 case TYPE_DIV_QR_1N_PI1:
2605 {
2606 mp_limb_t dinv = refmpn_invert_limb (divisor);
2607 e->retval = CALLING_CONVENTIONS (function)
2608 (e->d[0].p, e->s[0].p, size, e->s[1].p[0], divisor, dinv);
2609 break;
2610 }
2611
2612 case TYPE_MOD_34LSUB1:
2613 e->retval = CALLING_CONVENTIONS (function) (e->s[0].p, size);
2614 break;
2615
2616 case TYPE_UDIV_QRNND:
2617 e->retval = CALLING_CONVENTIONS (function)
2618 (e->d[0].p, e->s[0].p[1], e->s[0].p[0], divisor);
2619 break;
2620 case TYPE_UDIV_QRNND_R:
2621 e->retval = CALLING_CONVENTIONS (function)
2622 (e->s[0].p[1], e->s[0].p[0], divisor, e->d[0].p);
2623 break;
2624
2625 case TYPE_SBPI1_DIV_QR:
2626 {
2627 gmp_pi1_t dinv;
2628 invert_pi1 (dinv, e->s[1].p[size2-1], e->s[1].p[size2-2]); /* FIXME: use refinvert_pi1 */
2629 refmpn_copyi (e->d[1].p, e->s[0].p, size); /* dividend */
2630 refmpn_fill (e->d[0].p, size-size2, 0x98765432); /* quotient */
2631 e->retval = CALLING_CONVENTIONS (function)
2632 (e->d[0].p, e->d[1].p, size, e->s[1].p, size2, dinv.inv32);
2633 refmpn_zero (e->d[1].p+size2, size-size2); /* excess over remainder */
2634 }
2635 break;
2636
2637 case TYPE_TDIV_QR:
2638 CALLING_CONVENTIONS (function) (e->d[0].p, e->d[1].p, 0,
2639 e->s[0].p, size, e->s[1].p, size2);
2640 break;
2641
2642 case TYPE_GCD_1:
2643 /* Must have a non-zero src, but this probably isn't the best way to do
2644 it. */
2645 if (refmpn_zero_p (e->s[0].p, size))
2646 e->retval = 0;
2647 else
2648 e->retval = CALLING_CONVENTIONS (function) (e->s[0].p, size, divisor);
2649 break;
2650
2651 case TYPE_GCD:
2652 /* Sources are destroyed, so they're saved and replaced, but a general
2653 approach to this might be better. Note that it's still e->s[0].p and
2654 e->s[1].p that are passed, to get the desired alignments. */
2655 {
2656 mp_ptr s0 = refmpn_malloc_limbs (size);
2657 mp_ptr s1 = refmpn_malloc_limbs (size2);
2658 refmpn_copyi (s0, e->s[0].p, size);
2659 refmpn_copyi (s1, e->s[1].p, size2);
2660
2661 mprotect_region (&s[0].region, PROT_READ|PROT_WRITE);
2662 mprotect_region (&s[1].region, PROT_READ|PROT_WRITE);
2663 e->retval = CALLING_CONVENTIONS (function) (e->d[0].p,
2664 e->s[0].p, size,
2665 e->s[1].p, size2);
2666 refmpn_copyi (e->s[0].p, s0, size);
2667 refmpn_copyi (e->s[1].p, s1, size2);
2668 free (s0);
2669 free (s1);
2670 }
2671 break;
2672
2673 case TYPE_GCD_FINDA:
2674 {
2675 /* FIXME: do this with a flag */
2676 mp_limb_t c[2];
2677 c[0] = e->s[0].p[0];
2678 c[0] += (c[0] == 0);
2679 c[1] = e->s[0].p[0];
2680 c[1] += (c[1] == 0);
2681 e->retval = CALLING_CONVENTIONS (function) (c);
2682 }
2683 break;
2684
2685 case TYPE_MPZ_LEGENDRE:
2686 case TYPE_MPZ_JACOBI:
2687 {
2688 mpz_t a, b;
2689 PTR(a) = e->s[0].p; SIZ(a) = (carry==0 ? size : -size);
2690 PTR(b) = e->s[1].p; SIZ(b) = size2;
2691 e->retval = CALLING_CONVENTIONS (function) (a, b);
2692 }
2693 break;
2694 case TYPE_MPZ_KRONECKER:
2695 {
2696 mpz_t a, b;
2697 PTR(a) = e->s[0].p; SIZ(a) = ((carry&1)==0 ? size : -size);
2698 PTR(b) = e->s[1].p; SIZ(b) = ((carry&2)==0 ? size2 : -size2);
2699 e->retval = CALLING_CONVENTIONS (function) (a, b);
2700 }
2701 break;
2702 case TYPE_MPZ_KRONECKER_UI:
2703 {
2704 mpz_t a;
2705 PTR(a) = e->s[0].p; SIZ(a) = (carry==0 ? size : -size);
2706 e->retval = CALLING_CONVENTIONS(function) (a, (unsigned long)multiplier);
2707 }
2708 break;
2709 case TYPE_MPZ_KRONECKER_SI:
2710 {
2711 mpz_t a;
2712 PTR(a) = e->s[0].p; SIZ(a) = (carry==0 ? size : -size);
2713 e->retval = CALLING_CONVENTIONS (function) (a, (long) multiplier);
2714 }
2715 break;
2716 case TYPE_MPZ_UI_KRONECKER:
2717 {
2718 mpz_t b;
2719 PTR(b) = e->s[0].p; SIZ(b) = (carry==0 ? size : -size);
2720 e->retval = CALLING_CONVENTIONS(function) ((unsigned long)multiplier, b);
2721 }
2722 break;
2723 case TYPE_MPZ_SI_KRONECKER:
2724 {
2725 mpz_t b;
2726 PTR(b) = e->s[0].p; SIZ(b) = (carry==0 ? size : -size);
2727 e->retval = CALLING_CONVENTIONS (function) ((long) multiplier, b);
2728 }
2729 break;
2730
2731 case TYPE_MUL_MN:
2732 case TYPE_MULMID_MN:
2733 CALLING_CONVENTIONS (function)
2734 (e->d[0].p, e->s[0].p, size, e->s[1].p, size2);
2735 break;
2736 case TYPE_MUL_N:
2737 case TYPE_MULLO_N:
2738 CALLING_CONVENTIONS (function) (e->d[0].p, e->s[0].p, e->s[1].p, size);
2739 break;
2740 case TYPE_MULMID_N:
2741 CALLING_CONVENTIONS (function) (e->d[0].p, e->s[0].p, e->s[1].p,
2742 (size + 1) / 2);
2743 break;
2744 case TYPE_SQR:
2745 CALLING_CONVENTIONS (function) (e->d[0].p, e->s[0].p, size);
2746 break;
2747
2748 case TYPE_UMUL_PPMM:
2749 e->retval = CALLING_CONVENTIONS (function)
2750 (e->d[0].p, e->s[0].p[0], e->s[0].p[1]);
2751 break;
2752 case TYPE_UMUL_PPMM_R:
2753 e->retval = CALLING_CONVENTIONS (function)
2754 (e->s[0].p[0], e->s[0].p[1], e->d[0].p);
2755 break;
2756
2757 case TYPE_ADDLSH_N_IP1:
2758 case TYPE_ADDLSH_N_IP2:
2759 case TYPE_SUBLSH_N_IP1:
2760 case TYPE_LSHIFT:
2761 case TYPE_LSHIFTC:
2762 case TYPE_RSHIFT:
2763 e->retval = CALLING_CONVENTIONS (function)
2764 (e->d[0].p, e->s[0].p, size, shift);
2765 break;
2766
2767 case TYPE_POPCOUNT:
2768 e->retval = (* (unsigned long (*)(ANYARGS))
2769 CALLING_CONVENTIONS (function)) (e->s[0].p, size);
2770 break;
2771 case TYPE_HAMDIST:
2772 e->retval = (* (unsigned long (*)(ANYARGS))
2773 CALLING_CONVENTIONS (function)) (e->s[0].p, e->s[1].p, size);
2774 break;
2775
2776 case TYPE_SQRTREM:
2777 e->retval = (* (long (*)(ANYARGS)) CALLING_CONVENTIONS (function))
2778 (e->d[0].p, e->d[1].p, e->s[0].p, size);
2779 break;
2780
2781 case TYPE_ZERO:
2782 CALLING_CONVENTIONS (function) (e->d[0].p, size);
2783 break;
2784
2785 case TYPE_GET_STR:
2786 {
2787 size_t sizeinbase, fill;
2788 char *dst;
2789 MPN_SIZEINBASE (sizeinbase, e->s[0].p, size, base);
2790 ASSERT_ALWAYS (sizeinbase <= d[0].size);
2791 fill = d[0].size - sizeinbase;
2792 if (d[0].high)
2793 {
2794 memset (e->d[0].p, 0xBA, fill);
2795 dst = (char *) e->d[0].p + fill;
2796 }
2797 else
2798 {
2799 dst = (char *) e->d[0].p;
2800 memset (dst + sizeinbase, 0xBA, fill);
2801 }
2802 if (POW2_P (base))
2803 {
2804 e->retval = CALLING_CONVENTIONS (function) (dst, base,
2805 e->s[0].p, size);
2806 }
2807 else
2808 {
2809 refmpn_copy (e->d[1].p, e->s[0].p, size);
2810 e->retval = CALLING_CONVENTIONS (function) (dst, base,
2811 e->d[1].p, size);
2812 }
2813 refmpn_zero (e->d[1].p, size); /* clobbered or unused */
2814 }
2815 break;
2816
2817 case TYPE_INVERT:
2818 {
2819 mp_ptr scratch;
2820 TMP_DECL;
2821 TMP_MARK;
2822 scratch = TMP_ALLOC_LIMBS (mpn_invert_itch (size));
2823 CALLING_CONVENTIONS (function) (e->d[0].p, e->s[0].p, size, scratch);
2824 TMP_FREE;
2825 }
2826 break;
2827 case TYPE_BINVERT:
2828 {
2829 mp_ptr scratch;
2830 TMP_DECL;
2831 TMP_MARK;
2832 scratch = TMP_ALLOC_LIMBS (mpn_binvert_itch (size));
2833 CALLING_CONVENTIONS (function) (e->d[0].p, e->s[0].p, size, scratch);
2834 TMP_FREE;
2835 }
2836 break;
2837
2838 #ifdef EXTRA_CALL
2839 EXTRA_CALL
2840 #endif
2841
2842 default:
2843 printf ("Unknown routine type %d\n", choice->type);
2844 abort ();
2845 break;
2846 }
2847 }
2848
2849
2850 void
pointer_setup(struct each_t * e)2851 pointer_setup (struct each_t *e)
2852 {
2853 int i, j;
2854
2855 for (i = 0; i < NUM_DESTS; i++)
2856 {
2857 switch (tr->dst_size[i]) {
2858 case 0:
2859 case SIZE_RETVAL: /* will be adjusted later */
2860 d[i].size = size;
2861 break;
2862
2863 case SIZE_1:
2864 d[i].size = 1;
2865 break;
2866 case SIZE_2:
2867 d[i].size = 2;
2868 break;
2869 case SIZE_3:
2870 d[i].size = 3;
2871 break;
2872 case SIZE_4:
2873 d[i].size = 4;
2874 break;
2875 case SIZE_6:
2876 d[i].size = 6;
2877 break;
2878
2879 case SIZE_PLUS_1:
2880 d[i].size = size+1;
2881 break;
2882 case SIZE_PLUS_MSIZE_SUB_1:
2883 d[i].size = size + tr->msize - 1;
2884 break;
2885
2886 case SIZE_SUM:
2887 if (tr->size2)
2888 d[i].size = size + size2;
2889 else
2890 d[i].size = 2*size;
2891 break;
2892
2893 case SIZE_SIZE2:
2894 d[i].size = size2;
2895 break;
2896
2897 case SIZE_DIFF:
2898 d[i].size = size - size2;
2899 break;
2900
2901 case SIZE_DIFF_PLUS_1:
2902 d[i].size = size - size2 + 1;
2903 break;
2904
2905 case SIZE_DIFF_PLUS_3:
2906 d[i].size = size - size2 + 3;
2907 break;
2908
2909 case SIZE_CEIL_HALF:
2910 d[i].size = (size+1)/2;
2911 break;
2912
2913 case SIZE_GET_STR:
2914 {
2915 mp_limb_t ff = GMP_NUMB_MAX;
2916 MPN_SIZEINBASE (d[i].size, &ff - (size-1), size, base);
2917 }
2918 break;
2919
2920 default:
2921 printf ("Unrecognised dst_size type %d\n", tr->dst_size[i]);
2922 abort ();
2923 }
2924 }
2925
2926 /* establish e->d[].p destinations */
2927 for (i = 0; i < NUM_DESTS; i++)
2928 {
2929 mp_size_t offset = 0;
2930
2931 /* possible room for overlapping sources */
2932 for (j = 0; j < numberof (overlap->s); j++)
2933 if (overlap->s[j] == i)
2934 offset = MAX (offset, s[j].align);
2935
2936 if (d[i].high)
2937 {
2938 if (tr->dst_bytes[i])
2939 {
2940 e->d[i].p = (mp_ptr)
2941 ((char *) (e->d[i].region.ptr + e->d[i].region.size)
2942 - d[i].size - d[i].align);
2943 }
2944 else
2945 {
2946 e->d[i].p = e->d[i].region.ptr + e->d[i].region.size
2947 - d[i].size - d[i].align;
2948 if (tr->overlap == OVERLAP_LOW_TO_HIGH)
2949 e->d[i].p -= offset;
2950 }
2951 }
2952 else
2953 {
2954 if (tr->dst_bytes[i])
2955 {
2956 e->d[i].p = (mp_ptr) ((char *) e->d[i].region.ptr + d[i].align);
2957 }
2958 else
2959 {
2960 e->d[i].p = e->d[i].region.ptr + d[i].align;
2961 if (tr->overlap == OVERLAP_HIGH_TO_LOW)
2962 e->d[i].p += offset;
2963 }
2964 }
2965 }
2966
2967 /* establish e->s[].p sources */
2968 for (i = 0; i < NUM_SOURCES; i++)
2969 {
2970 int o = overlap->s[i];
2971 switch (o) {
2972 case -1:
2973 /* no overlap */
2974 e->s[i].p = s[i].p;
2975 break;
2976 case 0:
2977 case 1:
2978 /* overlap with d[o] */
2979 if (tr->overlap == OVERLAP_HIGH_TO_LOW)
2980 e->s[i].p = e->d[o].p - s[i].align;
2981 else if (tr->overlap == OVERLAP_LOW_TO_HIGH)
2982 e->s[i].p = e->d[o].p + s[i].align;
2983 else if (tr->size2 == SIZE_FRACTION)
2984 e->s[i].p = e->d[o].p + size2;
2985 else
2986 e->s[i].p = e->d[o].p;
2987 break;
2988 default:
2989 abort();
2990 break;
2991 }
2992 }
2993 }
2994
2995
2996 void
validate_fail(void)2997 validate_fail (void)
2998 {
2999 if (tr->reference)
3000 {
3001 trap_location = TRAP_REF;
3002 call (&ref, tr->reference);
3003 trap_location = TRAP_NOWHERE;
3004 }
3005
3006 print_all();
3007 abort();
3008 }
3009
3010
3011 void
try_one(void)3012 try_one (void)
3013 {
3014 int i;
3015
3016 if (option_spinner)
3017 spinner();
3018 spinner_count++;
3019
3020 trap_location = TRAP_SETUPS;
3021
3022 if (tr->divisor == DIVISOR_NORM)
3023 divisor |= GMP_NUMB_HIGHBIT;
3024 if (tr->divisor == DIVISOR_ODD)
3025 divisor |= 1;
3026
3027 for (i = 0; i < NUM_SOURCES; i++)
3028 {
3029 if (s[i].high)
3030 s[i].p = s[i].region.ptr + s[i].region.size - SRC_SIZE(i) - s[i].align;
3031 else
3032 s[i].p = s[i].region.ptr + s[i].align;
3033 }
3034
3035 pointer_setup (&ref);
3036 pointer_setup (&fun);
3037
3038 ref.retval = 0x04152637;
3039 fun.retval = 0x8C9DAEBF;
3040
3041 t_random (multiplier_N, tr->msize);
3042
3043 for (i = 0; i < NUM_SOURCES; i++)
3044 {
3045 if (! tr->src[i])
3046 continue;
3047
3048 mprotect_region (&s[i].region, PROT_READ|PROT_WRITE);
3049 t_random (s[i].p, SRC_SIZE(i));
3050
3051 switch (tr->data) {
3052 case DATA_NON_ZERO:
3053 if (refmpn_zero_p (s[i].p, SRC_SIZE(i)))
3054 s[i].p[0] = 1;
3055 break;
3056
3057 case DATA_MULTIPLE_DIVISOR:
3058 /* same number of low zero bits as divisor */
3059 s[i].p[0] &= ~ LOW_ZEROS_MASK (divisor);
3060 refmpn_sub_1 (s[i].p, s[i].p, size,
3061 refmpn_mod_1 (s[i].p, size, divisor));
3062 break;
3063
3064 case DATA_GCD:
3065 /* s[1] no more bits than s[0] */
3066 if (i == 1 && size2 == size)
3067 s[1].p[size-1] &= refmpn_msbone_mask (s[0].p[size-1]);
3068
3069 /* high limb non-zero */
3070 s[i].p[SRC_SIZE(i)-1] += (s[i].p[SRC_SIZE(i)-1] == 0);
3071
3072 /* odd */
3073 s[i].p[0] |= 1;
3074 break;
3075
3076 case DATA_SRC0_ODD:
3077 if (i == 0)
3078 s[i].p[0] |= 1;
3079 break;
3080
3081 case DATA_SRC1_ODD:
3082 if (i == 1)
3083 s[i].p[0] |= 1;
3084 break;
3085
3086 case DATA_SRC1_ODD_PRIME:
3087 if (i == 1)
3088 {
3089 if (refmpn_zero_p (s[i].p+1, SRC_SIZE(i)-1)
3090 && s[i].p[0] <=3)
3091 s[i].p[0] = 3;
3092 else
3093 {
3094 mpz_t p;
3095 mpz_init (p);
3096 for (;;)
3097 {
3098 _mpz_realloc (p, SRC_SIZE(i));
3099 MPN_COPY (PTR(p), s[i].p, SRC_SIZE(i));
3100 SIZ(p) = SRC_SIZE(i);
3101 MPN_NORMALIZE (PTR(p), SIZ(p));
3102 mpz_nextprime (p, p);
3103 if (mpz_size (p) <= SRC_SIZE(i))
3104 break;
3105
3106 t_random (s[i].p, SRC_SIZE(i));
3107 }
3108 MPN_COPY (s[i].p, PTR(p), SIZ(p));
3109 if (SIZ(p) < SRC_SIZE(i))
3110 MPN_ZERO (s[i].p + SIZ(p), SRC_SIZE(i) - SIZ(p));
3111 mpz_clear (p);
3112 }
3113 }
3114 break;
3115
3116 case DATA_SRC1_HIGHBIT:
3117 if (i == 1)
3118 {
3119 if (tr->size2)
3120 s[i].p[size2-1] |= GMP_NUMB_HIGHBIT;
3121 else
3122 s[i].p[size-1] |= GMP_NUMB_HIGHBIT;
3123 }
3124 break;
3125
3126 case DATA_SRC0_HIGHBIT:
3127 if (i == 0)
3128 {
3129 s[i].p[size-1] |= GMP_NUMB_HIGHBIT;
3130 }
3131 break;
3132
3133 case DATA_UDIV_QRNND:
3134 s[i].p[1] %= divisor;
3135 break;
3136 case DATA_DIV_QR_1:
3137 if (i == 1)
3138 s[i].p[0] %= divisor;
3139 break;
3140 }
3141
3142 mprotect_region (&s[i].region, PROT_READ);
3143 }
3144
3145 for (i = 0; i < NUM_DESTS; i++)
3146 {
3147 if (! tr->dst[i])
3148 continue;
3149
3150 if (tr->dst0_from_src1 && i==0)
3151 {
3152 mp_size_t copy = MIN (d[0].size, SRC_SIZE(1));
3153 mp_size_t fill = MAX (0, d[0].size - copy);
3154 MPN_COPY (fun.d[0].p, s[1].region.ptr, copy);
3155 MPN_COPY (ref.d[0].p, s[1].region.ptr, copy);
3156 refmpn_fill (fun.d[0].p + copy, fill, DEADVAL);
3157 refmpn_fill (ref.d[0].p + copy, fill, DEADVAL);
3158 }
3159 else if (tr->dst_bytes[i])
3160 {
3161 memset (ref.d[i].p, 0xBA, d[i].size);
3162 memset (fun.d[i].p, 0xBA, d[i].size);
3163 }
3164 else
3165 {
3166 refmpn_fill (ref.d[i].p, d[i].size, DEADVAL);
3167 refmpn_fill (fun.d[i].p, d[i].size, DEADVAL);
3168 }
3169 }
3170
3171 for (i = 0; i < NUM_SOURCES; i++)
3172 {
3173 if (! tr->src[i])
3174 continue;
3175
3176 if (ref.s[i].p != s[i].p)
3177 {
3178 refmpn_copyi (ref.s[i].p, s[i].p, SRC_SIZE(i));
3179 refmpn_copyi (fun.s[i].p, s[i].p, SRC_SIZE(i));
3180 }
3181 }
3182
3183 if (option_print)
3184 print_all();
3185
3186 if (tr->validate != NULL)
3187 {
3188 trap_location = TRAP_FUN;
3189 call (&fun, choice->function);
3190 trap_location = TRAP_NOWHERE;
3191
3192 if (! CALLING_CONVENTIONS_CHECK ())
3193 {
3194 print_all();
3195 abort();
3196 }
3197
3198 (*tr->validate) ();
3199 }
3200 else
3201 {
3202 trap_location = TRAP_REF;
3203 call (&ref, tr->reference);
3204 trap_location = TRAP_FUN;
3205 call (&fun, choice->function);
3206 trap_location = TRAP_NOWHERE;
3207
3208 if (! CALLING_CONVENTIONS_CHECK ())
3209 {
3210 print_all();
3211 abort();
3212 }
3213
3214 compare ();
3215 }
3216 }
3217
3218
3219 #define SIZE_ITERATION \
3220 for (size = MAX3 (option_firstsize, \
3221 choice->minsize, \
3222 (tr->size == SIZE_ALLOW_ZERO) ? 0 : 1), \
3223 size += (tr->size == SIZE_ODD) && !(size & 1); \
3224 size <= option_lastsize; \
3225 size += (tr->size == SIZE_ODD) ? 2 : 1)
3226
3227 #define SIZE2_FIRST \
3228 (tr->size2 == SIZE_2 ? 2 \
3229 : tr->size2 == SIZE_FRACTION ? option_firstsize2 \
3230 : tr->size2 == SIZE_CEIL_HALF ? ((size + 1) / 2) \
3231 : tr->size2 ? \
3232 MAX (choice->minsize, (option_firstsize2 != 0 \
3233 ? option_firstsize2 : 1)) \
3234 : 0)
3235
3236 #define SIZE2_LAST \
3237 (tr->size2 == SIZE_2 ? 2 \
3238 : tr->size2 == SIZE_FRACTION ? FRACTION_COUNT-1 \
3239 : tr->size2 == SIZE_CEIL_HALF ? ((size + 1) / 2) \
3240 : tr->size2 ? size \
3241 : 0)
3242
3243 #define SIZE2_ITERATION \
3244 for (size2 = SIZE2_FIRST; size2 <= SIZE2_LAST; size2++)
3245
3246 #define ALIGN_COUNT(cond) ((cond) ? ALIGNMENTS : 1)
3247 #define ALIGN_ITERATION(w,n,cond) \
3248 for (w[n].align = 0; w[n].align < ALIGN_COUNT(cond); w[n].align++)
3249
3250 #define HIGH_LIMIT(cond) ((cond) != 0)
3251 #define HIGH_COUNT(cond) (HIGH_LIMIT (cond) + 1)
3252 #define HIGH_ITERATION(w,n,cond) \
3253 for (w[n].high = 0; w[n].high <= HIGH_LIMIT(cond); w[n].high++)
3254
3255 #define SHIFT_LIMIT \
3256 ((unsigned long) (tr->shift ? GMP_NUMB_BITS -1 : 1))
3257
3258 #define SHIFT_ITERATION \
3259 for (shift = 1; shift <= SHIFT_LIMIT; shift++)
3260
3261
3262 void
try_many(void)3263 try_many (void)
3264 {
3265 int i;
3266
3267 {
3268 unsigned long total = 1;
3269
3270 total *= option_repetitions;
3271 total *= option_lastsize;
3272 if (tr->size2 == SIZE_FRACTION) total *= FRACTION_COUNT;
3273 else if (tr->size2) total *= (option_lastsize+1)/2;
3274
3275 total *= SHIFT_LIMIT;
3276 total *= MULTIPLIER_COUNT;
3277 total *= DIVISOR_COUNT;
3278 total *= CARRY_COUNT;
3279 total *= T_RAND_COUNT;
3280
3281 total *= HIGH_COUNT (tr->dst[0]);
3282 total *= HIGH_COUNT (tr->dst[1]);
3283 total *= HIGH_COUNT (tr->src[0]);
3284 total *= HIGH_COUNT (tr->src[1]);
3285
3286 total *= ALIGN_COUNT (tr->dst[0]);
3287 total *= ALIGN_COUNT (tr->dst[1]);
3288 total *= ALIGN_COUNT (tr->src[0]);
3289 total *= ALIGN_COUNT (tr->src[1]);
3290
3291 total *= OVERLAP_COUNT;
3292
3293 printf ("%s %lu\n", choice->name, total);
3294 }
3295
3296 spinner_count = 0;
3297
3298 for (i = 0; i < option_repetitions; i++)
3299 SIZE_ITERATION
3300 SIZE2_ITERATION
3301
3302 SHIFT_ITERATION
3303 MULTIPLIER_ITERATION
3304 DIVISOR_ITERATION
3305 CARRY_ITERATION /* must be after divisor */
3306 T_RAND_ITERATION
3307
3308 HIGH_ITERATION(d,0, tr->dst[0])
3309 HIGH_ITERATION(d,1, tr->dst[1])
3310 HIGH_ITERATION(s,0, tr->src[0])
3311 HIGH_ITERATION(s,1, tr->src[1])
3312
3313 ALIGN_ITERATION(d,0, tr->dst[0])
3314 ALIGN_ITERATION(d,1, tr->dst[1])
3315 ALIGN_ITERATION(s,0, tr->src[0])
3316 ALIGN_ITERATION(s,1, tr->src[1])
3317
3318 OVERLAP_ITERATION
3319 try_one();
3320
3321 printf("\n");
3322 }
3323
3324
3325 /* Usually print_all() doesn't show much, but it might give a hint as to
3326 where the function was up to when it died. */
3327 void
trap(int sig)3328 trap (int sig)
3329 {
3330 const char *name = "noname";
3331
3332 switch (sig) {
3333 case SIGILL: name = "SIGILL"; break;
3334 #ifdef SIGBUS
3335 case SIGBUS: name = "SIGBUS"; break;
3336 #endif
3337 case SIGSEGV: name = "SIGSEGV"; break;
3338 case SIGFPE: name = "SIGFPE"; break;
3339 }
3340
3341 printf ("\n\nSIGNAL TRAP: %s\n", name);
3342
3343 switch (trap_location) {
3344 case TRAP_REF:
3345 printf (" in reference function: %s\n", tr->reference_name);
3346 break;
3347 case TRAP_FUN:
3348 printf (" in test function: %s\n", choice->name);
3349 print_all ();
3350 break;
3351 case TRAP_SETUPS:
3352 printf (" in parameter setups\n");
3353 print_all ();
3354 break;
3355 default:
3356 printf (" somewhere unknown\n");
3357 break;
3358 }
3359 exit (1);
3360 }
3361
3362
3363 void
try_init(void)3364 try_init (void)
3365 {
3366 #if HAVE_GETPAGESIZE
3367 /* Prefer getpagesize() over sysconf(), since on SunOS 4 sysconf() doesn't
3368 know _SC_PAGESIZE. */
3369 pagesize = getpagesize ();
3370 #else
3371 #if HAVE_SYSCONF
3372 if ((pagesize = sysconf (_SC_PAGESIZE)) == -1)
3373 {
3374 /* According to the linux man page, sysconf doesn't set errno */
3375 fprintf (stderr, "Cannot get sysconf _SC_PAGESIZE\n");
3376 exit (1);
3377 }
3378 #else
3379 Error, error, cannot get page size
3380 #endif
3381 #endif
3382
3383 printf ("pagesize is 0x%lX bytes\n", pagesize);
3384
3385 signal (SIGILL, trap);
3386 #ifdef SIGBUS
3387 signal (SIGBUS, trap);
3388 #endif
3389 signal (SIGSEGV, trap);
3390 signal (SIGFPE, trap);
3391
3392 {
3393 int i;
3394
3395 for (i = 0; i < NUM_SOURCES; i++)
3396 {
3397 malloc_region (&s[i].region, 2*option_lastsize+ALIGNMENTS-1);
3398 printf ("s[%d] %p to %p (0x%lX bytes)\n",
3399 i, (void *) (s[i].region.ptr),
3400 (void *) (s[i].region.ptr + s[i].region.size),
3401 (long) s[i].region.size * GMP_LIMB_BYTES);
3402 }
3403
3404 #define INIT_EACH(e,es) \
3405 for (i = 0; i < NUM_DESTS; i++) \
3406 { \
3407 malloc_region (&e.d[i].region, 2*option_lastsize+ALIGNMENTS-1); \
3408 printf ("%s d[%d] %p to %p (0x%lX bytes)\n", \
3409 es, i, (void *) (e.d[i].region.ptr), \
3410 (void *) (e.d[i].region.ptr + e.d[i].region.size), \
3411 (long) e.d[i].region.size * GMP_LIMB_BYTES); \
3412 }
3413
3414 INIT_EACH(ref, "ref");
3415 INIT_EACH(fun, "fun");
3416 }
3417 }
3418
3419 int
strmatch_wild(const char * pattern,const char * str)3420 strmatch_wild (const char *pattern, const char *str)
3421 {
3422 size_t plen, slen;
3423
3424 /* wildcard at start */
3425 if (pattern[0] == '*')
3426 {
3427 pattern++;
3428 plen = strlen (pattern);
3429 slen = strlen (str);
3430 return (plen == 0
3431 || (slen >= plen && memcmp (pattern, str+slen-plen, plen) == 0));
3432 }
3433
3434 /* wildcard at end */
3435 plen = strlen (pattern);
3436 if (plen >= 1 && pattern[plen-1] == '*')
3437 return (memcmp (pattern, str, plen-1) == 0);
3438
3439 /* no wildcards */
3440 return (strcmp (pattern, str) == 0);
3441 }
3442
3443 void
try_name(const char * name)3444 try_name (const char *name)
3445 {
3446 int found = 0;
3447 int i;
3448
3449 for (i = 0; i < numberof (choice_array); i++)
3450 {
3451 if (strmatch_wild (name, choice_array[i].name))
3452 {
3453 choice = &choice_array[i];
3454 tr = ¶m[choice->type];
3455 try_many ();
3456 found = 1;
3457 }
3458 }
3459
3460 if (!found)
3461 {
3462 printf ("%s unknown\n", name);
3463 /* exit (1); */
3464 }
3465 }
3466
3467
3468 void
usage(const char * prog)3469 usage (const char *prog)
3470 {
3471 int col = 0;
3472 int i;
3473
3474 printf ("Usage: %s [options] function...\n", prog);
3475 printf (" -1 use limb data 1,2,3,etc\n");
3476 printf (" -9 use limb data all 0xFF..FFs\n");
3477 printf (" -a zeros use limb data all zeros\n");
3478 printf (" -a ffs use limb data all 0xFF..FFs (same as -9)\n");
3479 printf (" -a 2fd use data 0x2FFF...FFFD\n");
3480 printf (" -p print each case tried (try this if seg faulting)\n");
3481 printf (" -R seed random numbers from time()\n");
3482 printf (" -r reps set repetitions (default %d)\n", DEFAULT_REPETITIONS);
3483 printf (" -s size starting size to test\n");
3484 printf (" -S size2 starting size2 to test\n");
3485 printf (" -s s1-s2 range of sizes to test\n");
3486 printf (" -W don't show the spinner (use this in gdb)\n");
3487 printf (" -z disable mprotect() redzones\n");
3488 printf ("Default data is refmpn_random() and refmpn_random2().\n");
3489 printf ("\n");
3490 printf ("Functions that can be tested:\n");
3491
3492 for (i = 0; i < numberof (choice_array); i++)
3493 {
3494 if (col + 1 + strlen (choice_array[i].name) > 79)
3495 {
3496 printf ("\n");
3497 col = 0;
3498 }
3499 printf (" %s", choice_array[i].name);
3500 col += 1 + strlen (choice_array[i].name);
3501 }
3502 printf ("\n");
3503
3504 exit(1);
3505 }
3506
3507
3508 int
main(int argc,char * argv[])3509 main (int argc, char *argv[])
3510 {
3511 int i;
3512
3513 /* unbuffered output */
3514 setbuf (stdout, NULL);
3515 setbuf (stderr, NULL);
3516
3517 /* default trace in hex, and in upper-case so can paste into bc */
3518 mp_trace_base = -16;
3519
3520 param_init ();
3521
3522 {
3523 unsigned long seed = 123;
3524 int opt;
3525
3526 while ((opt = getopt(argc, argv, "19a:b:E:pRr:S:s:Wz")) != EOF)
3527 {
3528 switch (opt) {
3529 case '1':
3530 /* use limb data values 1, 2, 3, ... etc */
3531 option_data = DATA_SEQ;
3532 break;
3533 case '9':
3534 /* use limb data values 0xFFF...FFF always */
3535 option_data = DATA_FFS;
3536 break;
3537 case 'a':
3538 if (strcmp (optarg, "zeros") == 0) option_data = DATA_ZEROS;
3539 else if (strcmp (optarg, "seq") == 0) option_data = DATA_SEQ;
3540 else if (strcmp (optarg, "ffs") == 0) option_data = DATA_FFS;
3541 else if (strcmp (optarg, "2fd") == 0) option_data = DATA_2FD;
3542 else
3543 {
3544 fprintf (stderr, "unrecognised data option: %s\n", optarg);
3545 exit (1);
3546 }
3547 break;
3548 case 'b':
3549 mp_trace_base = atoi (optarg);
3550 break;
3551 case 'E':
3552 /* re-seed */
3553 sscanf (optarg, "%lu", &seed);
3554 printf ("Re-seeding with %lu\n", seed);
3555 break;
3556 case 'p':
3557 option_print = 1;
3558 break;
3559 case 'R':
3560 /* randomize */
3561 seed = time (NULL);
3562 printf ("Seeding with %lu, re-run using \"-E %lu\"\n", seed, seed);
3563 break;
3564 case 'r':
3565 option_repetitions = atoi (optarg);
3566 break;
3567 case 's':
3568 {
3569 char *p;
3570 option_firstsize = strtol (optarg, 0, 0);
3571 if ((p = strchr (optarg, '-')) != NULL)
3572 option_lastsize = strtol (p+1, 0, 0);
3573 }
3574 break;
3575 case 'S':
3576 /* -S <size> sets the starting size for the second of a two size
3577 routine (like mpn_mul_basecase) */
3578 option_firstsize2 = strtol (optarg, 0, 0);
3579 break;
3580 case 'W':
3581 /* use this when running in the debugger */
3582 option_spinner = 0;
3583 break;
3584 case 'z':
3585 /* disable redzones */
3586 option_redzones = 0;
3587 break;
3588 case '?':
3589 usage (argv[0]);
3590 break;
3591 }
3592 }
3593
3594 gmp_randinit_default (__gmp_rands);
3595 __gmp_rands_initialized = 1;
3596 gmp_randseed_ui (__gmp_rands, seed);
3597 }
3598
3599 try_init();
3600
3601 if (argc <= optind)
3602 usage (argv[0]);
3603
3604 for (i = optind; i < argc; i++)
3605 try_name (argv[i]);
3606
3607 return 0;
3608 }
3609