2 * libsortnetwork - src/sn-bb-merge.c
3 * Copyright (C) 2008-2010 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>
22 #ifndef _ISOC99_SOURCE
23 # define _ISOC99_SOURCE
25 #ifndef _POSIX_C_SOURCE
26 # define _POSIX_C_SOURCE 200809L
29 # define _XOPEN_SOURCE 700
37 #include <sys/types.h>
47 #include "sn_network.h"
48 #include "sn_random.h"
50 #if !defined(__GNUC__) || !__GNUC__
51 # define __attribute__(x) /**/
55 static int inputs_left = 0;
56 static int inputs_right = 0;
58 static int inputs_num = 0;
60 static int comparators_num = -1;
61 static int max_depth = -1;
62 static int max_stages = INT_MAX;
64 static char *initial_input_file = NULL;
66 static void exit_usage (const char *name) /* {{{ */
68 printf ("Usage: %s [options]\n"
70 "Valid options are:\n"
72 " -i <inputs>[:<inputs>] Number of inputs (left and right)\n"
74 " -i <inputs> Number of inputs\n"
76 " -c <comparators> Number of comparators\n"
77 " -s <stages> Maximum number of stages\n"
78 " -I <file> Initial input file\n"
82 } /* }}} void exit_usage */
84 int read_options (int argc, char **argv) /* {{{ */
88 while ((option = getopt (argc, argv, "i:c:I:o:p:P:s:t:h")) != -1)
100 tmp_str = strchr (optarg, ':');
105 tmp_right = atoi (tmp_str);
112 tmp_left = atoi (optarg);
115 exit_usage (argv[0]);
118 tmp_right = tmp_left;
120 inputs_left = tmp_left;
121 inputs_right = tmp_right;
141 comparators_num = tmp;
147 if (initial_input_file != NULL)
148 free (initial_input_file);
149 initial_input_file = strdup (optarg);
164 exit_usage (argv[0]);
169 } /* }}} int read_options */
172 static int rate_network (sn_network_t *n) /* {{{ */
174 int test_pattern[n->inputs_num];
175 int values[n->inputs_num];
177 int patterns_failed = 0;
184 assert (n->inputs_num == (inputs_left + inputs_right));
186 memset (test_pattern, 0, sizeof (test_pattern));
187 for (i = 0; i < inputs_left; i++)
190 for (zeros_left = 0; zeros_left <= inputs_left; zeros_left++)
196 test_pattern[zeros_left - 1] = 0;
198 for (i = 0; i < inputs_right; i++)
199 test_pattern[inputs_left + i] = 1;
201 for (zeros_right = 0; zeros_right <= inputs_right; zeros_right++)
204 test_pattern[inputs_left + zeros_right - 1] = 0;
206 /* Copy the current pattern and let the network sort it */
207 memcpy (values, test_pattern, sizeof (values));
208 status = sn_network_sort (n, values);
212 /* Check if the array is now sorted. */
213 previous = values[0];
215 for (i = 1; i < n->inputs_num; i++)
217 if (previous > values[i])
223 previous = values[i];
225 } /* for (zeros_right) */
226 } /* for (zeros_left) */
228 return (patterns_failed);
229 } /* }}} int rate_network */
231 static int rate_network (sn_network_t *n) /* {{{ */
233 int test_pattern[n->inputs_num];
234 int values[n->inputs_num];
236 int patterns_sorted = 0;
237 int patterns_failed = 0;
239 memset (test_pattern, 0, sizeof (test_pattern));
247 /* Copy the current pattern and let the network sort it */
248 memcpy (values, test_pattern, sizeof (values));
249 status = sn_network_sort (n, values);
253 /* Check if the array is now sorted. */
254 previous = values[0];
256 for (i = 1; i < n->inputs_num; i++)
258 if (previous > values[i])
264 previous = values[i];
270 /* Generate the next test pattern */
272 for (i = 0; i < n->inputs_num; i++)
274 if (test_pattern[i] == 0)
287 /* Break out of the while loop if we tested all possible patterns */
292 /* All tests successfull */
293 return (patterns_failed);
294 } /* }}} int rate_network */
297 static _Bool sn_bound (sn_network_t *n, int depth, int rating) /* {{{ */
299 static int least_failed = INT_MAX;
303 assert (depth <= max_depth);
305 if (SN_NETWORK_STAGE_NUM (n) > max_stages)
308 /* Minimum number of comparisons requires */
309 lower_bound = (int) (ceil (log ((double) rating) / log (2.0)));
311 if (lower_bound > (max_depth - depth))
314 if (least_failed >= rating)
316 printf ("New optimum: %i\n", rating);
320 least_failed = rating;
328 } /* }}} _Bool sn_bound */
330 static int sn_branch (sn_network_t *n, int depth, int rating) /* {{{ */
336 if (depth >= max_depth)
340 rating = rate_network (n);
342 left_num = SN_NETWORK_INPUT_NUM (n) - 1;
343 left_rnd = sn_bounded_random (0, left_num - 1);
345 for (i = 0; i < left_num; i++)
352 left_input = left_rnd + i;
353 if (left_input >= left_num)
354 left_input -= left_num;
355 assert (left_input < left_num);
356 assert (left_input >= 0);
358 right_num = SN_NETWORK_INPUT_NUM (n) - (left_input + 1);
362 right_rnd = sn_bounded_random (0, right_num - 1);
364 for (j = 0; j < right_num; j++)
366 sn_network_t *n_copy;
371 right_input = (left_input + 1) + right_rnd + j;
372 if (right_input >= SN_NETWORK_INPUT_NUM (n))
373 right_input -= right_num;
374 assert (right_input < SN_NETWORK_INPUT_NUM (n));
375 assert (right_input > left_input);
377 n_copy = sn_network_clone (n);
378 c = sn_comparator_create (left_input, right_input);
380 sn_network_comparator_add (n_copy, c);
382 /* Make sure the new comparator is improving the network */
383 n_copy_rating = rate_network (n_copy);
384 if (n_copy_rating >= rating)
386 sn_comparator_destroy (c);
387 sn_network_destroy (n_copy);
391 if (!sn_bound (n_copy, depth + 1, n_copy_rating))
392 sn_branch (n_copy, depth + 1, n_copy_rating);
394 sn_comparator_destroy (c);
395 sn_network_destroy (n_copy);
396 } /* for (right_input) */
397 } /* for (left_input) */
400 } /* }}} int sn_branch */
402 int main (int argc, char **argv) /* {{{ */
410 read_options (argc, argv);
413 if ((inputs_left <= 0) || (inputs_right <= 0) || (comparators_num <= 0))
414 exit_usage (argv[0]);
415 inputs_num = inputs_left + inputs_right;
417 if ((inputs_num <= 0) || (comparators_num <= 0))
418 exit_usage (argv[0]);
421 if (initial_input_file != NULL)
423 n = sn_network_read_file (initial_input_file);
426 fprintf (stderr, "Cannot read network from `%s'.\n",
431 if (n->inputs_num != inputs_num)
433 fprintf (stderr, "Network `%s' has %i inputs, but %i were configured "
434 "on the command line.\n",
435 initial_input_file, n->inputs_num, inputs_num);
440 if (SN_NETWORK_STAGE_NUM (n) > max_stages)
442 fprintf (stderr, "The maximum number of stages allowed (%i) is smaller "
443 "than the number of stages of the input file (%i).\n",
444 max_stages, SN_NETWORK_STAGE_NUM (n));
448 else /* if (initial_input_file == NULL) */
450 n = sn_network_create (inputs_num);
453 c_num = sn_network_get_comparator_num (n);
454 if (c_num >= comparators_num)
456 fprintf (stderr, "The initial network has already %i comparators, "
457 "which conflicts with the -c option (%i)!\n",
458 c_num, comparators_num);
461 max_depth = comparators_num - c_num;
463 printf ("Current configuration:\n"
464 " Number of inputs: %3i\n"
465 " Number of comparators: %3i\n"
466 " Search depth: %3i\n"
467 "=======================\n",
468 inputs_num, comparators_num, max_depth);
470 sn_branch (n, /* depth = */ 0, /* rating = */ -1);
475 /* vim: set sw=2 sts=2 et fdm=marker : */