tests/mpn/t-perfsqr.c

   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.
   6
   7 The GNU MP Library is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU Lesser General Public License as published by
   9 the Free Software Foundation; either version 3 of the License, or (at your
  10 option) any later version.
  11
  12 The GNU MP Library is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  15 License for more details.
  16
  17 You should have received a copy of the GNU Lesser General Public License
  18 along with the GNU MP Library.  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 }