1/* Test for mpn_invert function. 2 3 Contributed to the GNU project by Marco Bodrato. 4 5Copyright 2009 Free Software Foundation, Inc. 6 7This file is part of the GNU MP Library. 8 9The GNU MP Library is free software; you can redistribute it and/or modify 10it under the terms of the GNU Lesser General Public License as published by 11the Free Software Foundation; either version 3 of the License, or (at your 12option) any later version. 13 14The GNU MP Library is distributed in the hope that it will be useful, but 15WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 16or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 17License for more details. 18 19You should have received a copy of the GNU Lesser General Public License 20along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */ 21 22 23#include "gmp.h" 24#include "gmp-impl.h" 25#include "tests.h" 26 27#include <stdlib.h> 28#include <stdio.h> 29 30/* Sizes are up to 2^SIZE_LOG limbs */ 31#ifndef SIZE_LOG 32#define SIZE_LOG 12 33#endif 34 35#ifndef COUNT 36#define COUNT 1000 37#endif 38 39#define MAX_N (1L << SIZE_LOG) 40#define MIN_N 1 41 42 43static int 44invert_valid (mp_srcptr ip, mp_srcptr dp, mp_size_t n) 45{ 46 mp_ptr tp; 47 int cy; 48 TMP_DECL; 49 50 TMP_MARK; 51 tp = TMP_ALLOC_LIMBS (2*n); 52 53 refmpn_mul (tp, ip, n, dp, n); 54 cy = refmpn_add_n (tp + n, tp + n, dp, n); /* This must not give a carry. */ 55 cy -= refmpn_add (tp, tp, 2*n, dp, n); /* This must give a carry. */ 56 TMP_FREE; 57 58 return (cy == -1); 59} 60 61/* 62 Chech the result of the mpn_invert function in the library. 63*/ 64 65int 66main (int argc, char **argv) 67{ 68 mp_ptr ip, dp, scratch; 69 int count = COUNT; 70 int test; 71 gmp_randstate_ptr rands; 72 TMP_DECL; 73 TMP_MARK; 74 75 if (argc > 1) 76 { 77 char *end; 78 count = strtol (argv[1], &end, 0); 79 if (*end || count <= 0) 80 { 81 fprintf (stderr, "Invalid test count: %s.\n", argv[1]); 82 return 1; 83 } 84 } 85 86 tests_start (); 87 rands = RANDS; 88 89 dp = TMP_ALLOC_LIMBS (MAX_N); 90 ip = 1+TMP_ALLOC_LIMBS (MAX_N + 2); 91 scratch 92 = 1+TMP_ALLOC_LIMBS (mpn_invert_itch (MAX_N) + 2); 93 94 for (test = 0; test < count; test++) 95 { 96 unsigned size_min; 97 unsigned size_range; 98 mp_size_t n; 99 mp_size_t itch; 100 mp_limb_t i_before, i_after, s_before, s_after; 101 102 for (size_min = 1; (1L << size_min) < MIN_N; size_min++) 103 ; 104 105 /* We generate an in the MIN_N <= n <= (1 << size_range). */ 106 size_range = size_min 107 + gmp_urandomm_ui (rands, SIZE_LOG + 1 - size_min); 108 109 n = MIN_N 110 + gmp_urandomm_ui (rands, (1L << size_range) + 1 - MIN_N); 111 112 mpn_random2 (dp, n); 113 114 mpn_random2 (ip-1, n + 2); 115 i_before = ip[-1]; 116 i_after = ip[n]; 117 118 itch = mpn_invert_itch (n); 119 ASSERT_ALWAYS (itch <= mpn_invert_itch (MAX_N)); 120 mpn_random2 (scratch-1, itch+2); 121 s_before = scratch[-1]; 122 s_after = scratch[itch]; 123 124 dp[n-1] |= GMP_NUMB_HIGHBIT; 125 mpn_invert (ip, dp, n, scratch); 126 if (ip[-1] != i_before || ip[n] != i_after 127 || scratch[-1] != s_before || scratch[itch] != s_after 128 || ! invert_valid(ip, dp, n)) 129 { 130 printf ("ERROR in test %d, n = %d\n", 131 test, (int) n); 132 if (ip[-1] != i_before) 133 { 134 printf ("before ip:"); mpn_dump (ip -1, 1); 135 printf ("keep: "); mpn_dump (&i_before, 1); 136 } 137 if (ip[n] != i_after) 138 { 139 printf ("after ip:"); mpn_dump (ip + n, 1); 140 printf ("keep: "); mpn_dump (&i_after, 1); 141 } 142 if (scratch[-1] != s_before) 143 { 144 printf ("before scratch:"); mpn_dump (scratch-1, 1); 145 printf ("keep: "); mpn_dump (&s_before, 1); 146 } 147 if (scratch[itch] != s_after) 148 { 149 printf ("after scratch:"); mpn_dump (scratch + itch, 1); 150 printf ("keep: "); mpn_dump (&s_after, 1); 151 } 152 mpn_dump (dp, n); 153 mpn_dump (ip, n); 154 155 abort(); 156 } 157 } 158 TMP_FREE; 159 tests_end (); 160 return 0; 161} 162