1 /* Test mpn_perfect_square_p data.
2
3 Copyright 2002 Free Software Foundation, Inc.
4
5 This file is part of the GNU MP Library test suite.
6
7 The GNU MP Library test suite is free software; you can redistribute it
8 and/or modify it under the terms of the GNU General Public License as
9 published by the Free Software Foundation; either version 3 of the License,
10 or (at your option) any later version.
11
12 The GNU MP Library test suite is distributed in the hope that it will be
13 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
15 Public License for more details.
16
17 You should have received a copy of the GNU General Public License along with
18 the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */
19
20 #include <stdio.h>
21 #include <stdlib.h>
22
23 #include "gmp-impl.h"
24 #include "tests.h"
25
26 #include "mpn/perfsqr.h"
27
28
29 #define PERFSQR_MOD_MASK ((CNST_LIMB(1) << PERFSQR_MOD_BITS) - 1)
30
31 void
check_mod_2(mp_limb_t d,mp_limb_t inv,mp_limb_t got_hi,mp_limb_t got_lo)32 check_mod_2 (mp_limb_t d, mp_limb_t inv, mp_limb_t got_hi, mp_limb_t got_lo)
33 {
34 int want[2*GMP_LIMB_BITS], got;
35 unsigned r, idx;
36 mp_limb_t q;
37
38 ASSERT_ALWAYS (d <= numberof (want));
39 ASSERT_ALWAYS (((inv * d) & PERFSQR_MOD_MASK) == 1);
40 ASSERT_ALWAYS (MP_LIMB_T_MAX / d >= PERFSQR_MOD_MASK);
41
42 /* the squares mod d */
43 for (r = 0; r < d; r++)
44 want[r] = 0;
45 for (r = 0; r < d; r++)
46 want[(r*r)%d] = 1;
47
48 /* for each remainder mod d, expect the table data to correctly identify
49 it as a residue or non-residue */
50 for (r = 0; r < d; r++)
51 {
52 /* as per PERFSQR_MOD_IDX */
53 q = ((r) * (inv)) & PERFSQR_MOD_MASK;
54 idx = (q * (d)) >> PERFSQR_MOD_BITS;
55
56 if (idx >= GMP_LIMB_BITS)
57 got = (got_hi >> (idx - GMP_LIMB_BITS)) & 1;
58 else
59 got = (got_lo >> idx) & 1;
60
61 if (got != want[r])
62 {
63 printf ("Wrong generated data\n");
64 printf (" d=%u\n", (unsigned) d);
65 printf (" r=%u\n", r);
66 printf (" idx=%u\n", idx);
67 printf (" got %d\n", got);
68 printf (" want %d\n", want[r]);
69 abort ();
70 }
71 }
72 }
73
74 /* Check the generated data in perfsqr.h. */
75 void
check_mod(void)76 check_mod (void)
77 {
78 #define PERFSQR_MOD_34(r, up, usize) { r = 0; } /* so r isn't unused */
79 #define PERFSQR_MOD_PP(r, up, usize) { r = 0; }
80 #define PERFSQR_MOD_1(r, d, inv, mask) check_mod_2 (d, inv, CNST_LIMB(0), mask)
81 #define PERFSQR_MOD_2(r, d, inv, mhi, mlo) check_mod_2 (d, inv, mhi, mlo)
82
83 PERFSQR_MOD_TEST (dummy, dummy);
84 }
85
86 /* Check PERFSQR_PP, if in use. */
87 void
check_pp(void)88 check_pp (void)
89 {
90 #ifdef PERFSQR_PP
91 ASSERT_ALWAYS_LIMB (PERFSQR_PP);
92 ASSERT_ALWAYS_LIMB (PERFSQR_PP_NORM);
93 ASSERT_ALWAYS_LIMB (PERFSQR_PP_INVERTED);
94
95 /* preinv stuff only for nails==0 */
96 if (GMP_NAIL_BITS == 0)
97 {
98 ASSERT_ALWAYS (PERFSQR_PP_NORM
99 == PERFSQR_PP << refmpn_count_leading_zeros (PERFSQR_PP));
100 ASSERT_ALWAYS (PERFSQR_PP_INVERTED
101 == refmpn_invert_limb (PERFSQR_PP_NORM));
102 }
103 #endif
104 }
105
106 int
main(void)107 main (void)
108 {
109 tests_start ();
110
111 check_mod ();
112 check_pp ();
113
114 tests_end ();
115 exit (0);
116 }
117