try.c

a very popular packet of cryptography tools,it encloses the most common used algorithm and protocols

/* Run some tests on various mpn routines.

   THIS IS A TEST PROGRAM USED ONLY FOR DEVELOPMENT.  IT'S ALMOST CERTAIN TO
   BE SUBJECT TO INCOMPATIBLE CHANGES IN FUTURE VERSIONS OF GMP.

Copyright 2000, 2001, 2002, 2003 Free Software Foundation, Inc.

This file is part of the GNU MP Library.

The GNU MP Library is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or (at your
option) any later version.

The GNU MP Library is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
License for more details.

You should have received a copy of the GNU Lesser General Public License
along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
MA 02111-1307, USA. */


/* Usage: try [options] <function>...

   For example, "./try mpn_add_n" to run tests of that function.

   Combinations of alignments and overlaps are tested, with redzones above
   or below the destinations, and with the sources write-protected.

   The number of tests performed becomes ridiculously large with all the
   combinations, and for that reason this can't be a part of a "make check",
   it's meant only for development.  The code isn't very pretty either.

   During development it can help to disable the redzones, since seeing the
   rest of the destination written can show where the wrong part is, or if
   the dst pointers are off by 1 or whatever.  The magic DEADVAL initial
   fill (see below) will show locations never written.

   The -s option can be used to test only certain size operands, which is
   useful if some new code doesn't yet support say sizes less than the
   unrolling, or whatever.

   When a problem occurs it'll of course be necessary to run the program
   under gdb to find out quite where, how and why it's going wrong.  Disable
   the spinner with the -W option when doing this, or single stepping won't
   work.  Using the "-1" option to run with simple data can be useful.

   New functions to test can be added in try_array[].  If a new TYPE is
   required then add it to the existing constants, set up its parameters in
   param_init(), and add it to the call() function.  Extra parameter fields
   can be added if necessary, or further interpretations given to existing
   fields.


   Bugs:

   umul_ppmm support is not very good, lots of source data is generated
   whereas only two limbs are needed.


   Future:

   Make a little scheme for interpreting the "SIZE" selections uniformly.

   Make tr->size==SIZE_2 work, for the benefit of find_a which wants just 2
   source limbs.  Possibly increase the default repetitions in that case.

   Automatically detect gdb and disable the spinner (use -W for now).

   Make a way to re-run a failing case in the debugger.  Have an option to
   snapshot each test case before it's run so the data is available if a
   segv occurs.  (This should be more reliable than the current print_all()
   in the signal handler.)

   When alignment means a dst isn't hard against the redzone, check the
   space in between remains unchanged.

   See if the 80x86 debug registers can do redzones on byte boundaries.

   When a source overlaps a destination, don't run both s[i].high 0 and 1,
   as s[i].high has no effect.  Maybe encode s[i].high into overlap->s[i].

   When partial overlaps aren't done, don't loop over source alignments
   during overlaps.

   Try to make the looping code a bit less horrible.  Right now it's pretty
   hard to see what iterations are actually done.

   When there's no overlap, run with both src>dst and src<dst.  A subtle
   calling-conventions violation occured in a P6 copy which depended on the
   relative location of src and dst.

*/


/* always do assertion checking */
#define WANT_ASSERT 1

#include "config.h"

#include <errno.h>
#include <limits.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#if HAVE_UNISTD_H
#include <unistd.h>
#endif

#if HAVE_SYS_MMAN_H
#include <sys/mman.h>
#endif

#include "gmp.h"
#include "gmp-impl.h"
#include "longlong.h"
#include "tests.h"


#if WANT_ASSERT
#define ASSERT_CARRY(expr)   ASSERT_ALWAYS ((expr) != 0)
#else
#define ASSERT_CARRY(expr)   (expr)
#endif


#if !HAVE_DECL_OPTARG
extern char *optarg;
extern int optind, opterr;
#endif

/* Rumour has it some systems lack a define of PROT_NONE. */
#ifndef PROT_NONE
#define PROT_NONE   0
#endif

/* Dummy defines for when mprotect doesn't exist. */
#ifndef PROT_READ
#define PROT_READ   0
#endif
#ifndef PROT_WRITE
#define PROT_WRITE  0
#endif

/* _SC_PAGESIZE is standard, but hpux 9 and possibly other systems have
   _SC_PAGE_SIZE instead. */
#if defined (_SC_PAGE_SIZE) && ! defined (_SC_PAGESIZE)
#define _SC_PAGESIZE  _SC_PAGE_SIZE
#endif


#ifdef EXTRA_PROTOS
EXTRA_PROTOS
#endif
#ifdef EXTRA_PROTOS2
EXTRA_PROTOS2
#endif


#define DEFAULT_REPETITIONS  10

int  option_repetitions = DEFAULT_REPETITIONS;
int  option_spinner = 1;
int  option_redzones = 1;
int  option_firstsize = 0;
int  option_lastsize = 500;
int  option_firstsize2 = 0;

#define ALIGNMENTS          4
#define OVERLAPS            4
#define CARRY_RANDOMS       5
#define MULTIPLIER_RANDOMS  5
#define DIVISOR_RANDOMS     5
#define FRACTION_COUNT      4

int  option_print = 0;

#define DATA_TRAND  0
#define DATA_ZEROS  1
#define DATA_SEQ    2
#define DATA_FFS    3
#define DATA_2FD    4
int  option_data = DATA_TRAND;


mp_size_t  pagesize;
#define PAGESIZE_LIMBS  (pagesize / BYTES_PER_MP_LIMB)

/* must be a multiple of the page size */
#define REDZONE_BYTES   (pagesize * 16)
#define REDZONE_LIMBS   (REDZONE_BYTES / BYTES_PER_MP_LIMB)


#define MAX3(x,y,z)   (MAX (x, MAX (y, z)))

#if BITS_PER_MP_LIMB == 32
#define DEADVAL  CNST_LIMB(0xDEADBEEF)
#else
#define DEADVAL  CNST_LIMB(0xDEADBEEFBADDCAFE)
#endif


struct region_t {
  mp_ptr     ptr;
  mp_size_t  size;
};


#define TRAP_NOWHERE 0
#define TRAP_REF     1
#define TRAP_FUN     2
#define TRAP_SETUPS  3
int trap_location = TRAP_NOWHERE;


#define NUM_SOURCES  2
#define NUM_DESTS    2

struct source_t {
  struct region_t  region;
  int        high;
  mp_size_t  align;
  mp_ptr     p;
};

struct source_t  s[NUM_SOURCES];

struct dest_t {
  int        high;
  mp_size_t  align;
  mp_size_t  size;
};

struct dest_t  d[NUM_DESTS];

struct source_each_t {
  mp_ptr     p;
};

struct dest_each_t {
  struct region_t  region;
  mp_ptr     p;
};

mp_size_t       size;
mp_size_t       size2;
unsigned long   shift;
mp_limb_t       carry;
mp_limb_t       divisor;
mp_limb_t       multiplier;

struct each_t {
  const char  *name;
  struct dest_each_t    d[NUM_DESTS];
  struct source_each_t  s[NUM_SOURCES];
  mp_limb_t  retval;
};

struct each_t  ref = { "Ref" };
struct each_t  fun = { "Fun" };

#define SRC_SIZE(n)  ((n) == 1 && tr->size2 ? size2 : size)

void validate_fail _PROTO ((void));


#if HAVE_TRY_NEW_C
#include "try-new.c"
#endif


typedef mp_limb_t (*tryfun_t) _PROTO ((ANYARGS));

struct try_t {
  char  retval;

  char  src[2];
  char  dst[2];

#define SIZE_YES          1
#define SIZE_ALLOW_ZERO   2
#define SIZE_1            3  /* 1 limb  */
#define SIZE_2            4  /* 2 limbs */
#define SIZE_3            5  /* 3 limbs */
#define SIZE_FRACTION     6  /* size2 is fraction for divrem etc */
#define SIZE_SIZE2        7
#define SIZE_PLUS_1       8
#define SIZE_SUM          9
#define SIZE_DIFF        10
#define SIZE_DIFF_PLUS_1 11
#define SIZE_RETVAL      12
#define SIZE_CEIL_HALF   13
#define SIZE_GET_STR     14
  char  size;
  char  size2;
  char  dst_size[2];

  char  dst_bytes[2];

  char  dst0_from_src1;

#define CARRY_BIT     1  /* single bit 0 or 1 */
#define CARRY_3       2  /* 0, 1, 2 */
#define CARRY_4       3  /* 0 to 3 */
#define CARRY_LIMB    4  /* any limb value */
#define CARRY_DIVISOR 5  /* carry<divisor */
  char  carry;

  /* a fudge to tell the output when to print negatives */
  char  carry_sign;

  char  multiplier;
  char  shift;

#define DIVISOR_LIMB  1
#define DIVISOR_NORM  2
#define DIVISOR_ODD   3
  char  divisor;

#define DATA_NON_ZERO         1
#define DATA_GCD              2
#define DATA_SRC1_ODD         3
#define DATA_SRC1_HIGHBIT     4
#define DATA_MULTIPLE_DIVISOR 5
#define DATA_UDIV_QRNND       6
  char  data;

/* Default is allow full overlap. */
#define OVERLAP_NONE         1
#define OVERLAP_LOW_TO_HIGH  2
#define OVERLAP_HIGH_TO_LOW  3
#define OVERLAP_NOT_SRCS     4
#define OVERLAP_NOT_SRC2     8
  char  overlap;

  tryfun_t    reference;
  const char  *reference_name;

  void        (*validate) _PROTO ((void));
  const char  *validate_name;
};

struct try_t  *tr;


void
validate_mod_34lsub1 (void)
{
#define CNST_34LSUB1   ((CNST_LIMB(1) << (3 * (BITS_PER_MP_LIMB / 4))) - 1)
  
  mp_srcptr  ptr = s[0].p;
  int        error = 0;
  mp_limb_t  got, got_mod, want, want_mod;

  ASSERT (size >= 1);

  got = fun.retval;
  got_mod = got % CNST_34LSUB1;
  
  want = refmpn_mod_34lsub1 (ptr, size);
  want_mod = want % CNST_34LSUB1;

  if (got_mod != want_mod)
    {
      printf ("got   0x%lX reduced from 0x%lX\n", got_mod, got);
      printf ("want  0x%lX reduced from 0x%lX\n", want_mod, want);
      error = 1;
    }
  
  if (error)
    validate_fail ();
}

void
validate_divexact_1 (void)
{
  mp_srcptr  src = s[0].p;
  mp_srcptr  dst = fun.d[0].p;
  int  error = 0;

  ASSERT (size >= 1);

  {
    mp_ptr     tp = refmpn_malloc_limbs (size);
    mp_limb_t  rem;

    rem = refmpn_divrem_1 (tp, 0, src, size, divisor);
    if (rem != 0)
      {
        printf ("Remainder a%%d == 0x%lX, mpn_divexact_1 undefined\n", rem);
        error = 1;
      }
    if (! refmpn_equal_anynail (tp, dst, size))
      {
        printf ("Quotient a/d wrong\n");
        mpn_trace ("fun ", dst, size);
        mpn_trace ("want", tp, size);
        error = 1;
      }
    free (tp);
  }
  
  if (error)
    validate_fail ();
}


void
validate_modexact_1c_odd (void)
{
  mp_srcptr  ptr = s[0].p;
  mp_limb_t  r = fun.retval;
  int  error = 0;

  ASSERT (size >= 1);
  ASSERT (divisor & 1);

  if (carry < divisor)
    {
      if (! (r < divisor))
        {
          printf ("Don't have r < divisor\n");
          error = 1;
        }
    }
  else /* carry >= divisor */
    {
      if (! (r <= divisor))
        {
          printf ("Don't have r <= divisor\n");
          error = 1;
        }
    }

  {
    mp_limb_t  c = carry % divisor;
    mp_ptr     tp = refmpn_malloc_limbs (size+1);
    mp_size_t  k;

    for (k = size-1; k <= size; k++)
      {
        /* set {tp,size+1} to r*b^k + a - c */
        refmpn_copyi (tp, ptr, size);
        tp[size] = 0;
        ASSERT_NOCARRY (refmpn_add_1 (tp+k, tp+k, size+1-k, r));
        if (refmpn_sub_1 (tp, tp, size+1, c))
          ASSERT_CARRY (mpn_add_1 (tp, tp, size+1, divisor));
       
        if (refmpn_mod_1 (tp, size+1, divisor) == 0)
          goto good_remainder;
      }
    printf ("Remainder matches neither r*b^(size-1) nor r*b^size\n");
    error = 1;

  good_remainder:
    free (tp);
  }
  
  if (error)
    validate_fail ();
}

void
validate_modexact_1_odd (void)
{
  carry = 0;
  validate_modexact_1c_odd ();
}


void
validate_sqrtrem (void)
{
  mp_srcptr  orig_ptr = s[0].p;
  mp_size_t  orig_size = size;
  mp_size_t  root_size = (size+1)/2;
  mp_srcptr  root_ptr = fun.d[0].p;
  mp_size_t  rem_size = fun.retval;
  mp_srcptr  rem_ptr = fun.d[1].p;
  mp_size_t  prod_size = 2*root_size;
  mp_ptr     p;
  int  error = 0;

  if (rem_size < 0 || rem_size > size)
    {
      printf ("Bad remainder size retval %ld\n", rem_size);
      validate_fail ();
    }

  p = refmpn_malloc_limbs (prod_size);

  p[root_size] = refmpn_lshift (p, root_ptr, root_size, 1);
  if (refmpn_cmp_twosizes (p,root_size+1, rem_ptr,rem_size) < 0)
    {
      printf ("Remainder bigger than 2*root\n");
      error = 1;
    }

  refmpn_sqr (p, root_ptr, root_size);
  if (rem_size != 0)
    refmpn_add (p, p, prod_size, rem_ptr, rem_size);
  if (refmpn_cmp_twosizes (p,prod_size, orig_ptr,orig_size) != 0)
    {
      printf ("root^2+rem != original\n");
      mpn_trace ("prod", p, prod_size);
      error = 1;
    }
  free (p);

  if (error)
    validate_fail ();
}


/* These types are indexes into the param[] array and are arbitrary so long
   as they're all distinct and within the size of param[].  Renumber
   whenever necessary or desired.  */

#define TYPE_ADD               1
#define TYPE_ADD_N             2
#define TYPE_ADD_NC            3
#define TYPE_SUB               4
#define TYPE_SUB_N             5
#define TYPE_SUB_NC            6

#define TYPE_MUL_1             7