src/vppinfra/test_random.c

   1 /*
   2  * Copyright (c) 2015 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 /*
  16   Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
  17
  18   Permission is hereby granted, free of charge, to any person obtaining
  19   a copy of this software and associated documentation files (the
  20   "Software"), to deal in the Software without restriction, including
  21   without limitation the rights to use, copy, modify, merge, publish,
  22   distribute, sublicense, and/or sell copies of the Software, and to
  23   permit persons to whom the Software is furnished to do so, subject to
  24   the following conditions:
  25
  26   The above copyright notice and this permission notice shall be
  27   included in all copies or substantial portions of the Software.
  28
  29   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  30   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  31   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  32   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  33   LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  34   OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  35   WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  36 */
  37
  38 #include <vppinfra/format.h>
  39 #include <vppinfra/bitmap.h>
  40
  41 static u32 outcome_frequencies[] = {
  42   8, 5, 9, 2, 7, 5,
  43 };
  44
  45
  46 int
  47 test_chisquare (void)
  48 {
  49   u64 *values = 0;
  50   int i;
  51   f64 d, delta_d;
  52
  53   vec_validate (values, 5);
  54
  55   for (i = 0; i < 6; i++)
  56     values[i] = (u64) outcome_frequencies[i];
  57
  58   d = clib_chisquare (values);
  59
  60   delta_d = d - 5.333;
  61
  62   if (delta_d < 0.0)
  63     delta_d = -delta_d;
  64
  65   if (delta_d < 0.001)
  66     {
  67       fformat (stdout, "chisquare OK...\n");
  68       return 0;
  69     }
  70   else
  71     {
  72       fformat (stdout, "chisquare BAD, d = %.3f\n", d);
  73       return -1;
  74     }
  75 }
  76
  77 static u32 known_random_sequence[] = {
  78   0x00000000, 0x3c6ef35f, 0x47502932, 0xd1ccf6e9,
  79   0xaaf95334, 0x6252e503, 0x9f2ec686, 0x57fe6c2d,
  80   0xa3d95fa8, 0x81fdbee7, 0x94f0af1a, 0xcbf633b1,
  81 };
  82
  83
  84 int
  85 test_random_main (unformat_input_t * input)
  86 {
  87   uword n_iterations;
  88   uword i, repeat_count;
  89   uword *bitmap = 0;
  90   uword print;
  91   u32 seed;
  92   u32 *seedp = &seed;
  93   u64 *counts = 0;
  94   f64 d;
  95
  96   /* first, check known sequence from Numerical Recipes in C, 2nd ed.
  97      page 284 */
  98   seed = known_random_sequence[0];
  99   for (i = 0; i < ARRAY_LEN (known_random_sequence) - 1; i++)
 100     {
 101       u32 rv;
 102       rv = random_u32 (seedp);
 103       if (rv != known_random_sequence[i + 1])
 104         {
 105           fformat (stderr, "known sequence check FAILS at index %d", i + 1);
 106           break;
 107         }
 108     }
 109
 110   clib_warning ("known sequence check passes");
 111
 112   n_iterations = 1000;
 113   seed = 0;
 114   print = 1 << 24;
 115
 116   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 117     {
 118       if (0 == unformat (input, "iter %d", &n_iterations)
 119           && 0 == unformat (input, "print %d", &print)
 120           && 0 == unformat (input, "seed %d", &seed))
 121         clib_error ("unknown input `%U'", format_unformat_error, input);
 122     }
 123
 124   if (!seed)
 125     seed = random_default_seed ();
 126
 127   if (n_iterations == 0)
 128     n_iterations = random_u32_max ();
 129
 130   clib_warning ("%d iterations, seed %d\n", n_iterations, seed);
 131
 132   repeat_count = 0;
 133   for (i = 0; i < n_iterations; i++)
 134     {
 135       uword r = random_u32 (&seed);
 136       uword b, ri, rj;
 137
 138       ri = r / BITS (bitmap[0]);
 139       rj = (uword) 1 << (r % BITS (bitmap[0]));
 140
 141       vec_validate (bitmap, ri);
 142       b = bitmap[ri];
 143
 144       if (b & rj)
 145         goto repeat;
 146       b |= rj;
 147       bitmap[ri] = b;
 148
 149       if (0 == (i & (print - 1)))
 150         fformat (stderr, "0x%08x iterations %d repeats\n", i, repeat_count);
 151       continue;
 152
 153     repeat:
 154       fformat (stderr, "repeat found at iteration  %d/%d\n", i, n_iterations);
 155       repeat_count++;
 156       continue;
 157     }
 158
 159   if (test_chisquare ())
 160     return (-1);
 161
 162   /* Simple randomness tests based on X2 stats */
 163   vec_validate (counts, 255);
 164
 165   for (i = 0; i < 1000000; i++)
 166     {
 167       u32 random_index;
 168       u32 r = random_u32 (&seed);
 169
 170       random_index = r & 0xFF;
 171
 172       counts[random_index]++;
 173     }
 174
 175   d = clib_chisquare (counts);
 176
 177   fformat (stdout, "%d random octets, chisquare stat d = %.3f\n", i, d);
 178
 179   vec_free (counts);
 180
 181   return 0;
 182 }
 183
 184 #ifdef CLIB_UNIX
 185 int
 186 main (int argc, char *argv[])
 187 {
 188   unformat_input_t i;
 189   int ret;
 190
 191   clib_mem_init (0, 3ULL << 30);
 192
 193   unformat_init_command_line (&i, argv);
 194   ret = test_random_main (&i);
 195   unformat_free (&i);
 196
 197   return ret;
 198 }
 199 #endif /* CLIB_UNIX */
 200
 201
 202 /*
 203  * fd.io coding-style-patch-verification: ON
 204  *
 205  * Local Variables:
 206  * eval: (c-set-style "gnu")
 207  * End:
 208  */