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 http://www.gnu.org/licenses/. */ 19 20 #include <stdio.h> 21 #include <stdlib.h> 22 23 #include "gmp.h" 24 #include "gmp-impl.h" 25 #include "tests.h" 26 27 #include "mpn/perfsqr.h" 28 29 30 #define PERFSQR_MOD_MASK ((CNST_LIMB(1) << PERFSQR_MOD_BITS) - 1) 31 32 void 33 check_mod_2 (mp_limb_t d, mp_limb_t inv, mp_limb_t got_hi, mp_limb_t got_lo) 34 { 35 int want[2*GMP_LIMB_BITS], got; 36 unsigned r, idx; 37 mp_limb_t q; 38 39 ASSERT_ALWAYS (d <= numberof (want)); 40 ASSERT_ALWAYS (((inv * d) & PERFSQR_MOD_MASK) == 1); 41 ASSERT_ALWAYS (MP_LIMB_T_MAX / d >= PERFSQR_MOD_MASK); 42 43 /* the squares mod d */ 44 for (r = 0; r < d; r++) 45 want[r] = 0; 46 for (r = 0; r < d; r++) 47 want[(r*r)%d] = 1; 48 49 /* for each remainder mod d, expect the table data to correctly identify 50 it as a residue or non-residue */ 51 for (r = 0; r < d; r++) 52 { 53 /* as per PERFSQR_MOD_IDX */ 54 q = ((r) * (inv)) & PERFSQR_MOD_MASK; 55 idx = (q * (d)) >> PERFSQR_MOD_BITS; 56 57 if (idx >= GMP_LIMB_BITS) 58 got = (got_hi >> (idx - GMP_LIMB_BITS)) & 1; 59 else 60 got = (got_lo >> idx) & 1; 61 62 if (got != want[r]) 63 { 64 printf ("Wrong generated data\n"); 65 printf (" d=%u\n", (unsigned) d); 66 printf (" r=%u\n", r); 67 printf (" idx=%u\n", idx); 68 printf (" got %d\n", got); 69 printf (" want %d\n", want[r]); 70 abort (); 71 } 72 } 73 } 74 75 /* Check the generated data in perfsqr.h. */ 76 void 77 check_mod (void) 78 { 79 #define PERFSQR_MOD_34(r, up, usize) { r = 0; } /* so r isn't unused */ 80 #define PERFSQR_MOD_PP(r, up, usize) { r = 0; } 81 #define PERFSQR_MOD_1(r, d, inv, mask) check_mod_2 (d, inv, CNST_LIMB(0), mask) 82 #define PERFSQR_MOD_2(r, d, inv, mhi, mlo) check_mod_2 (d, inv, mhi, mlo) 83 84 PERFSQR_MOD_TEST (dummy, dummy); 85 } 86 87 /* Check PERFSQR_PP, if in use. */ 88 void 89 check_pp (void) 90 { 91 #ifdef PERFSQR_PP 92 ASSERT_ALWAYS_LIMB (PERFSQR_PP); 93 ASSERT_ALWAYS_LIMB (PERFSQR_PP_NORM); 94 ASSERT_ALWAYS_LIMB (PERFSQR_PP_INVERTED); 95 96 /* preinv stuff only for nails==0 */ 97 if (GMP_NAIL_BITS == 0) 98 { 99 ASSERT_ALWAYS (PERFSQR_PP_NORM 100 == PERFSQR_PP << refmpn_count_leading_zeros (PERFSQR_PP)); 101 ASSERT_ALWAYS (PERFSQR_PP_INVERTED 102 == refmpn_invert_limb (PERFSQR_PP_NORM)); 103 } 104 #endif 105 } 106 107 int 108 main (void) 109 { 110 tests_start (); 111 112 check_mod (); 113 check_pp (); 114 115 tests_end (); 116 exit (0); 117 } 118