2 * libsortnetwork - src/sn-count-cuts.c
3 * Copyright (C) 2008-2011 Florian octo Forster
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.
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.
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
19 * Florian octo Forster <ff at octo.it>
32 #include "sn_network.h"
33 #include "sn_random.h"
34 #include "sn_hashtable.h"
36 static int cuts_num = 0;
37 static uint64_t iterations_num = 1000000;
38 static char *input_file = NULL;
40 static _Bool exit_after_collision = 0;
42 static sn_hashtable_t *hashtable;
44 static double possible_cuts (int inputs_num) /* {{{ */
46 double n = (double) inputs_num;
47 double k = (double) cuts_num;
49 double tmp = lgamma (1.0 + n)
50 - (lgamma (1.0 + k) + lgamma (1.0 + n - k));
52 return (pow (2.0, k) * exp (tmp));
53 } /* }}} double possible_cuts */
55 static double estimate_reachable_networks (sn_network_t *n) /* {{{ */
57 double cuts = possible_cuts (SN_NETWORK_INPUT_NUM (n));
58 double pct = sn_hashtable_get_networks_pct (hashtable) / 100.0;
61 } /* }}} double estimate_reachable_networks */
63 static void exit_usage (void) /* {{{ */
65 printf ("sn-count-cuts [options] <file0> <file1>\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"
74 } /* }}} void exit_usage */
76 static int read_options (int argc, char **argv) /* {{{ */
80 while ((option = getopt (argc, argv, "1c:n:h")) != -1)
85 exit_after_collision = 1;
90 int tmp = atoi (optarg);
93 fprintf (stderr, "Not a valid number of cuts: %s\n", optarg);
102 uint64_t tmp = (uint64_t) strtoull (optarg, /* endptr = */ NULL, /* base = */ 10);
105 fprintf (stderr, "Not a valid number of iterations: %s\n", optarg);
108 iterations_num = tmp;
118 if ((argc - optind) >= 1)
119 input_file = argv[optind];
122 } /* }}} int read_options */
124 static int create_random_cut (const sn_network_t *n) /* {{{ */
126 sn_network_t *n_copy;
127 int mask[SN_NETWORK_INPUT_NUM (n)];
128 int cuts_left = cuts_num;
131 memset (mask, 0, sizeof (mask));
132 while (cuts_left > 0)
134 int input = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (n));
136 if (mask[input] != 0)
139 mask[input] = (2 * sn_bounded_random (0, 1)) - 1;
143 n_copy = sn_network_clone (n);
147 status = sn_network_cut (n_copy, mask);
150 sn_network_destroy (n_copy);
154 sn_network_unify (n_copy);
156 sn_hashtable_account (hashtable, n_copy);
158 sn_network_destroy (n_copy);
160 } /* }}} int create_random_cut */
162 static int print_stats (sn_network_t *n) /* {{{ */
164 static _Bool first_call = 1;
168 printf ("# iterations unique collisions estimate\n");
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));
179 } /* }}} int print_stats */
181 int main (int argc, char **argv) /* {{{ */
186 read_options (argc, argv);
188 if ((input_file == NULL)
189 || (strcmp ("-", input_file) == 0))
190 n = sn_network_read (stdin);
192 n = sn_network_read_file (input_file);
195 fprintf (stderr, "Unable to read network.\n");
200 cuts_num = SN_NETWORK_INPUT_NUM (n) / 2;
202 hashtable = sn_hashtable_create ();
203 if (hashtable == NULL)
206 for (i = 0; i < iterations_num; i++)
208 create_random_cut (n);
210 if (exit_after_collision)
211 if (sn_hashtable_get_collisions (hashtable) > 0)
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)))
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)))
240 /* vim: set shiftwidth=2 softtabstop=2 fdm=marker : */