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
      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
      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
      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
     107  main (void)
     108  {
     109    tests_start ();
     110  
     111    check_mod ();
     112    check_pp ();
     113  
     114    tests_end ();
     115    exit (0);
     116  }