src/sn-count-cuts.c

   1 /**
   2  * libsortnetwork - src/sn-count-cuts.c
   3  * Copyright (C) 2008-2011  Florian octo Forster
   4  *
   5  * This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License as published by the
   7  * Free Software Foundation; only version 2 of the License is applicable.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License along
  15  * with this program; if not, write to the Free Software Foundation, Inc.,
  16  * 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
  17  *
  18  * Authors:
  19  *   Florian octo Forster <ff at octo.it>
  20  **/
  21
  22 #include "config.h"
  23
  24 #include <stdlib.h>
  25 #include <stdio.h>
  26 #include <string.h>
  27 #include <unistd.h>
  28 #include <errno.h>
  29 #include <assert.h>
  30 #include <math.h>
  31
  32 #include "sn_network.h"
  33 #include "sn_random.h"
  34 #include "sn_hashtable.h"
  35
  36 static int cuts_num = 0;
  37 static uint64_t iterations_num = 1000000;
  38 static char *input_file = NULL;
  39
  40 static _Bool exit_after_collision = 0;
  41
  42 static sn_hashtable_t *hashtable;
  43
  44 static double possible_cuts (int inputs_num) /* {{{ */
  45 {
  46   double n = (double) inputs_num;
  47   double k = (double) cuts_num;
  48
  49   double tmp = lgamma (1.0 + n)
  50     - (lgamma (1.0 + k) + lgamma (1.0 + n - k));
  51
  52   return (pow (2.0, k) * exp (tmp));
  53 } /* }}} double possible_cuts */
  54
  55 static double estimate_reachable_networks (sn_network_t *n) /* {{{ */
  56 {
  57   double cuts = possible_cuts (SN_NETWORK_INPUT_NUM (n));
  58   double pct = sn_hashtable_get_networks_pct (hashtable) / 100.0;
  59
  60   return (cuts * pct);
  61 } /* }}} double estimate_reachable_networks */
  62
  63 static void exit_usage (void) /* {{{ */
  64 {
  65   printf ("sn-count-cuts [options] <file0> <file1>\n"
  66       "\n"
  67       "Options:\n"
  68       "  -1        Exit after the first collision has been detected.\n"
  69       "  -c        Number of cuts to perform.\n"
  70       "  -n        Maximum number of cuts to perform.\n"
  71       "  -h        Display this help and exit.\n"
  72       "\n");
  73   exit (EXIT_FAILURE);
  74 } /* }}} void exit_usage */
  75
  76 static int read_options (int argc, char **argv) /* {{{ */
  77 {
  78   int option;
  79
  80   while ((option = getopt (argc, argv, "1c:n:h")) != -1)
  81   {
  82     switch (option)
  83     {
  84       case '1':
  85         exit_after_collision = 1;
  86         break;
  87
  88       case 'c':
  89       {
  90         int tmp = atoi (optarg);
  91         if (tmp <= 0)
  92         {
  93           fprintf (stderr, "Not a valid number of cuts: %s\n", optarg);
  94           exit_usage ();
  95         }
  96         cuts_num = tmp;
  97       }
  98       break;
  99
 100       case 'n':
 101       {
 102         uint64_t tmp = (uint64_t) strtoull (optarg, /* endptr = */ NULL, /* base = */ 10);
 103         if (tmp <= 0)
 104         {
 105           fprintf (stderr, "Not a valid number of iterations: %s\n", optarg);
 106           exit_usage ();
 107         }
 108         iterations_num = tmp;
 109       }
 110       break;
 111
 112       case 'h':
 113       default:
 114         exit_usage ();
 115     }
 116   }
 117
 118   if ((argc - optind) >= 1)
 119     input_file = argv[optind];
 120
 121   return (0);
 122 } /* }}} int read_options */
 123
 124 static int create_random_cut (const sn_network_t *n) /* {{{ */
 125 {
 126   sn_network_t *n_copy;
 127   int mask[SN_NETWORK_INPUT_NUM (n)];
 128   int cuts_left = cuts_num;
 129   int status;
 130
 131   memset (mask, 0, sizeof (mask));
 132   while (cuts_left > 0)
 133   {
 134     int input = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (n));
 135
 136     if (mask[input] != 0)
 137       continue;
 138
 139     mask[input] = (2 * sn_bounded_random (0, 1)) - 1;
 140     cuts_left--;
 141   }
 142
 143   n_copy = sn_network_clone (n);
 144   if (n_copy == NULL)
 145     return (ENOMEM);
 146
 147   status = sn_network_cut (n_copy, mask);
 148   if (status != 0)
 149   {
 150     sn_network_destroy (n_copy);
 151     return (status);
 152   }
 153
 154   sn_network_unify (n_copy);
 155
 156   sn_hashtable_account (hashtable, n_copy);
 157
 158   sn_network_destroy (n_copy);
 159   return (0);
 160 } /* }}} int create_random_cut */
 161
 162 static int print_stats (sn_network_t *n) /* {{{ */
 163 {
 164   static _Bool first_call = 1;
 165
 166   if (first_call)
 167   {
 168     printf ("# iterations unique collisions estimate\n");
 169     first_call = 0;
 170   }
 171
 172   printf ("%"PRIu64" %"PRIu64" %"PRIu64" %.0f\n",
 173       sn_hashtable_get_total (hashtable),
 174       sn_hashtable_get_networks (hashtable),
 175       sn_hashtable_get_collisions (hashtable),
 176       estimate_reachable_networks (n));
 177
 178   return (0);
 179 } /* }}} int print_stats */
 180
 181 int main (int argc, char **argv) /* {{{ */
 182 {
 183   sn_network_t *n;
 184   uint64_t i;
 185
 186   read_options (argc, argv);
 187
 188   if ((input_file == NULL)
 189       || (strcmp ("-", input_file) == 0))
 190     n = sn_network_read (stdin);
 191   else
 192     n = sn_network_read_file (input_file);
 193   if (n == NULL)
 194   {
 195     fprintf (stderr, "Unable to read network.\n");
 196     exit (EXIT_FAILURE);
 197   }
 198
 199   if (cuts_num <= 0)
 200     cuts_num = SN_NETWORK_INPUT_NUM (n) / 2;
 201
 202   hashtable = sn_hashtable_create ();
 203   if (hashtable == NULL)
 204     exit (EXIT_FAILURE);
 205
 206   for (i = 0; i < iterations_num; i++)
 207   {
 208     create_random_cut (n);
 209
 210     if (exit_after_collision)
 211       if (sn_hashtable_get_collisions (hashtable) > 0)
 212         break;
 213
 214     if ((i < 100)
 215         || ((i < 1000) && (((i + 1) % 10) == 0))
 216         || ((i < 10000) && (((i + 1) % 100) == 0))
 217         || ((i < 100000) && (((i + 1) % 1000) == 0))
 218         || ((i < 1000000) && (((i + 1) % 10000) == 0))
 219         || ((i < 10000000) && (((i + 1) % 100000) == 0)))
 220       print_stats (n);
 221   }
 222
 223   if (((i - 1) < 100)
 224       || (((i - 1) < 1000) && ((i % 10) == 0))
 225       || (((i - 1) < 10000) && ((i % 100) == 0))
 226       || (((i - 1) < 100000) && ((i % 1000) == 0))
 227       || (((i - 1) < 1000000) && ((i % 10000) == 0))
 228       || (((i - 1) < 10000000) && ((i % 100000) == 0)))
 229   {
 230     /* do nothing */
 231   }
 232   else
 233   {
 234     print_stats (n);
 235   }
 236
 237   return (0);
 238 } /* }}} int main */
 239
 240 /* vim: set shiftwidth=2 softtabstop=2 fdm=marker : */