From 8d745e97bdb8371c42dff7304d55511fabfa6b6c Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Tue, 21 Dec 2010 11:35:12 +0100 Subject: [PATCH] Implement the bitonic sort in src/sn_network.c. The new implementation can handle input numbers which are not a power of two. Also sn-bitonicmerge has been added which works analogously to sn-oddevenmerge. --- README | 4 ++ src/Makefile.am | 7 +- src/sn-bitonicmerge.c | 70 ++++++++++++++++++++ src/sn-bitonicsort.c | 78 +++------------------- src/sn_network.c | 179 ++++++++++++++++++++++++++++---------------------- src/sn_network.h | 9 +++ 6 files changed, 201 insertions(+), 146 deletions(-) create mode 100644 src/sn-bitonicmerge.c diff --git a/README b/README index afac4ac..3278196 100644 --- a/README +++ b/README @@ -19,6 +19,10 @@ The distribution includes the following utility programs: Reads a list of values from STDIN and applies a given comparator network to the list. The resulting list of printed to STDOUT. + * sn-bitonicmerge + Create a bitonic merge network with a given number of left and right + inputs. The resulting network is printed to STDOUT. + * sn-bitonicsort Creates a bitonic mergesort network with a given number of inputs and prints the network to STDOUT. The number of inputs must be a power of two. diff --git a/src/Makefile.am b/src/Makefile.am index 8923b41..1924258 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -2,7 +2,9 @@ include_HEADERS = sn_network.h sn_stage.h sn_comparator.h lib_LTLIBRARIES = libsortnetwork.la -bin_PROGRAMS = sn-apply sn-bitonicsort sn-bb sn-bb-merge sn-check-bf sn-cut \ +bin_PROGRAMS = sn-apply \ + sn-bitonicmerge sn-bitonicsort \ + sn-bb sn-bb-merge sn-check-bf sn-cut \ sn-info sn-markov sn-merge sn-normalize \ sn-oddevenmerge sn-oddevensort sn-pairwisesort \ sn-shmoo sn-show sn-svg sn-tex @@ -23,6 +25,9 @@ sn_bb_merge_SOURCES = sn-bb.c sn_bb_merge_CPPFLAGS = $(AM_CPPFLAGS) -DBUILD_MERGE=1 sn_bb_merge_LDADD = libsortnetwork.la -lm +sn_bitonicmerge_SOURCES = sn-bitonicmerge.c +sn_bitonicmerge_LDADD = libsortnetwork.la + sn_bitonicsort_SOURCES = sn-bitonicsort.c sn_bitonicsort_LDADD = libsortnetwork.la diff --git a/src/sn-bitonicmerge.c b/src/sn-bitonicmerge.c new file mode 100644 index 0000000..5503e13 --- /dev/null +++ b/src/sn-bitonicmerge.c @@ -0,0 +1,70 @@ +/** + * libsortnetwork - src/sn-bitonicmerge.c + * Copyright (C) 2008-2010 Florian octo Forster + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation; only version 2 of the License is applicable. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + * Authors: + * Florian octo Forster + **/ + +#ifndef _ISOC99_SOURCE +# define _ISOC99_SOURCE +#endif +#ifndef _POSIX_C_SOURCE +# define _POSIX_C_SOURCE 200112L +#endif + +#include +#include + +#include "sn_network.h" + +int main (int argc, char **argv) +{ + sn_network_t *sn_left; + sn_network_t *sn_right; + sn_network_t *bm; + int inputs_left; + int inputs_right; + + if (argc != 3) + { + printf ("Usage: %s \n", argv[0]); + return (0); + } + + inputs_left = atoi (argv[1]); + inputs_right = atoi (argv[2]); + if ((inputs_left < 1) || (inputs_right < 1)) + { + fprintf (stderr, "Invalid number of inputs: %i/%i\n", + inputs_left, inputs_right); + return (1); + } + + sn_left = sn_network_create (inputs_left); + sn_right = sn_network_create (inputs_right); + bm = sn_network_combine_bitonic_merge (sn_left, sn_right); + + sn_network_write (bm, stdout); + + sn_network_destroy (sn_left); + sn_network_destroy (sn_right); + sn_network_destroy (bm); + + return (0); +} /* int main */ + +/* vim: set shiftwidth=2 softtabstop=2 : */ diff --git a/src/sn-bitonicsort.c b/src/sn-bitonicsort.c index 9a69dc2..3119123 100644 --- a/src/sn-bitonicsort.c +++ b/src/sn-bitonicsort.c @@ -31,88 +31,30 @@ #include "sn_network.h" -static sn_network_t *create_batcher_sort (size_t inputs_num) -{ - sn_network_t *n; - sn_network_t *n_small; - - if (inputs_num == 2) - { - sn_stage_t *s; - sn_comparator_t c; - - n = sn_network_create (2); - if (n == NULL) - { - fprintf (stderr, "create_batcher_sort: sn_network_create failed.\n"); - return (NULL); - } - - s = sn_stage_create (0); - if (s == NULL) - { - sn_network_destroy (n); - fprintf (stderr, "create_batcher_sort: sn_stage_create failed.\n"); - return (NULL); - } - - c.min = 0; - c.max = 1; - - sn_stage_comparator_add (s, &c); - sn_network_stage_add (n, s); - - return (n); - } - else if ((inputs_num < 2) || ((inputs_num % 2) != 0)) - { - fprintf (stderr, "create_batcher_sort: Inputs must be a power of two, " - "sorry.\n"); - return (NULL); - } - - n_small = create_batcher_sort (inputs_num / 2); - if (n_small == NULL) - return (NULL); - - n = sn_network_combine_bitonic_merge (n_small, n_small); - if (n == NULL) - { - sn_network_destroy (n_small); - fprintf (stderr, "create_batcher_sort: sn_network_combine_bitonic_merge " - "failed.\n"); - return (NULL); - } - - sn_network_destroy (n_small); - sn_network_compress (n); - - return (n); -} /* sn_network_t *create_batcher_sort */ - int main (int argc, char **argv) { sn_network_t *n; - size_t inputs_num; + int inputs_num; if (argc != 2) { - printf ("Usage: %s \n", argv[0]); - return (0); + printf ("Usage: sn-bitonicsort \n"); + exit (EXIT_SUCCESS); } - inputs_num = (size_t) atoi (argv[1]); + inputs_num = atoi (argv[1]); if (inputs_num < 2) { - fprintf (stderr, "Invalid number of inputs: %zu\n", inputs_num); - return (1); + fprintf (stderr, "Invalid number of inputs: %i\n", inputs_num); + exit (EXIT_FAILURE); } - n = create_batcher_sort (inputs_num); + n = sn_network_create_bitonic_mergesort (inputs_num); if (n == NULL) { - printf ("n == NULL!\n"); - return (1); + fprintf (stderr, "Creating bitonic mergesort network with %i inputs failed.\n", + inputs_num); + exit (EXIT_FAILURE); } sn_network_write (n, stdout); diff --git a/src/sn_network.c b/src/sn_network.c index ee4f79e..e7e3144 100644 --- a/src/sn_network.c +++ b/src/sn_network.c @@ -136,6 +136,66 @@ sn_network_t *sn_network_create_odd_even_mergesort (int inputs_num) /* {{{ */ } } /* }}} sn_network_t *sn_network_create_odd_even_mergesort */ +sn_network_t *sn_network_create_bitonic_mergesort (int inputs_num) /* {{{ */ +{ + sn_network_t *n; + + assert (inputs_num > 0); + if (inputs_num == 1) + { + return (sn_network_create (inputs_num)); + } + if (inputs_num == 2) + { + sn_comparator_t c; + + n = sn_network_create (inputs_num); + + memset (&c, 0, sizeof (c)); + c.min = 0; + c.max = 1; + + sn_network_comparator_add (n, &c); + + return (n); + } + else + { + sn_network_t *n_left; + sn_network_t *n_right; + int inputs_left; + int inputs_right; + + inputs_left = inputs_num / 2; + inputs_right = inputs_num - inputs_left; + + n_left = sn_network_create_bitonic_mergesort (inputs_left); + if (n_left == NULL) + return (NULL); + + if (inputs_left != inputs_right) + n_right = sn_network_create_bitonic_mergesort (inputs_right); + else + n_right = n_left; + if (n_right == NULL) + { + sn_network_destroy (n_left); + return (NULL); + } + + n = sn_network_combine_bitonic_merge (n_left, n_right); + + if (n_left != n_right) + sn_network_destroy (n_right); + sn_network_destroy (n_left); + + if (n != NULL) + sn_network_compress (n); + + return (n); + } +} /* }}} sn_network_t *sn_network_create_bitonic_mergesort */ + static int sn_network_create_pairwise_internal (sn_network_t *n, /* {{{ */ int *inputs, int inputs_num) { @@ -616,71 +676,44 @@ static sn_network_t *sn_network_concatenate (sn_network_t *n0, /* {{{ */ return (n); } /* }}} sn_network_t *sn_network_concatenate */ -static int sn_network_add_bitonic_merger_recursive (sn_network_t *n, /* {{{ */ - int low, int num) +static int sn_network_add_bitonic_merger (sn_network_t *n, /* {{{ */ + int *indizes, int indizes_num) { - sn_stage_t *s; - int m; int i; - if (num == 1) + if (indizes_num <= 1) return (0); - s = sn_stage_create (n->stages_num); - if (s == NULL) - return (-1); - - m = num / 2; - - for (i = low; i < (low + m); i++) + if (indizes_num > 2) { - sn_comparator_t c; + int even_indizes[indizes_num]; + int even_indizes_num; + int odd_indizes[indizes_num]; + int odd_indizes_num; - c.min = i; - c.max = i + m; + even_indizes_num = (indizes_num + 1) / 2; + odd_indizes_num = indizes_num / 2; - sn_stage_comparator_add (s, &c); - } + for (i = 0; i < even_indizes_num; i++) + even_indizes[i] = indizes[2 * i]; + for (i = 0; i < odd_indizes_num; i++) + odd_indizes[i] = indizes[(2 * i) + 1]; - sn_network_stage_add (n, s); - - sn_network_add_bitonic_merger_recursive (n, low, m); - sn_network_add_bitonic_merger_recursive (n, low + m, m); - - return (0); -} /* }}} int sn_network_add_bitonic_merger_recursive */ - -static int sn_network_add_bitonic_merger (sn_network_t *n) /* {{{ */ -{ -#if 0 - sn_stage_t *s; - int m; - int i; - - s = sn_stage_create (n->stages_num); - if (s == NULL) - return (-1); - - m = n->inputs_num / 2; + sn_network_add_bitonic_merger (n, even_indizes, even_indizes_num); + sn_network_add_bitonic_merger (n, odd_indizes, odd_indizes_num); + } - for (i = 0; i < m; i++) + for (i = 1; i < indizes_num; i += 2) { sn_comparator_t c; - c.min = i; - c.max = n->inputs_num - (i + 1); + memset (&c, 0, sizeof (c)); + c.min = indizes[i - 1]; + c.max = indizes[i]; - sn_stage_comparator_add (s, &c); + sn_network_comparator_add (n, &c); } - sn_network_stage_add (n, s); - - sn_network_add_bitonic_merger_recursive (n, 0, m); - sn_network_add_bitonic_merger_recursive (n, m, m); -#else - sn_network_add_bitonic_merger_recursive (n, 0, SN_NETWORK_INPUT_NUM (n)); -#endif - return (0); } /* }}} int sn_network_add_bitonic_merger */ @@ -775,45 +808,37 @@ static int sn_network_add_odd_even_merger (sn_network_t *n, /* {{{ */ return (0); } /* }}} int sn_network_add_odd_even_merger */ -static sn_network_t *sn_network_combine_bitonic_shift (sn_network_t *n0, /* {{{ */ - sn_network_t *n1, int do_shift) +sn_network_t *sn_network_combine_bitonic_merge (sn_network_t *n0, /* {{{ */ + sn_network_t *n1) { + sn_network_t *n0_clone; sn_network_t *n; - sn_network_t *n1_clone; - int shift; + int indizes_num = SN_NETWORK_INPUT_NUM (n0) + SN_NETWORK_INPUT_NUM (n1); + int indizes[indizes_num]; + int i; - n1_clone = sn_network_clone (n1); - if (n1_clone == NULL) + /* We need to invert n0, because the sequence must be + * z_1 >= z_2 >= ... >= z_k <= z_{k+1} <= ... <= z_p + * and NOT the other way around! Otherwise the comparators added in + * sn_network_add_bitonic_merger() from comparing (z_0,z_1), (z_2,z_3), ... + * to comparing ..., (z_{n-4},z_{n-3}), (z_{n-2},z_{n-1}), i.e. bound to the + * end of the list, possibly leaving z_0 uncompared. */ + n0_clone = sn_network_clone (n0); + if (n0_clone == NULL) return (NULL); + sn_network_invert (n0_clone); - sn_network_invert (n1_clone); - - n = sn_network_concatenate (n0, n1_clone); + n = sn_network_concatenate (n0_clone, n1); if (n == NULL) return (NULL); + sn_network_destroy (n0_clone); - sn_network_destroy (n1_clone); - - if (do_shift) - shift = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (n) - 1); - else - shift = 0; + for (i = 0; i < indizes_num; i++) + indizes[i] = i; - if (shift > 0) - { - DPRINTF ("sn_network_combine_bitonic_shift: Shifting by %i.\n", shift); - sn_network_shift (n, shift); - } - - sn_network_add_bitonic_merger (n); + sn_network_add_bitonic_merger (n, indizes, indizes_num); return (n); -} /* }}} sn_network_t *sn_network_combine_bitonic_shift */ - -sn_network_t *sn_network_combine_bitonic_merge (sn_network_t *n0, /* {{{ */ - sn_network_t *n1) -{ - return (sn_network_combine_bitonic_shift (n0, n1, /* do_shift = */ 0)); } /* }}} sn_network_t *sn_network_combine_bitonic_merge */ sn_network_t *sn_network_combine_odd_even_merge (sn_network_t *n0, /* {{{ */ diff --git a/src/sn_network.h b/src/sn_network.h index 328d0fe..eb5b2e9 100644 --- a/src/sn_network.h +++ b/src/sn_network.h @@ -87,6 +87,15 @@ void sn_network_destroy (sn_network_t *n); sn_network_t *sn_network_create_odd_even_mergesort (int inputs_num); /** + * Creates a new sort network using Batcher's Bitonic-Mergesort algorithm. + * + * \param inputs_num Number of inputs / outputs of the sorting network. + * \return A pointer to the newly allocated sorting network or \c NULL if an + * invalid number of inputs was given or allocation failed. + */ +sn_network_t *sn_network_create_bitonic_mergesort (int inputs_num); + +/** * Creates a new sorting network using the Pairwise sorting algorithm published * by Ian Parberry. * \param inputs_num Number of inputs / outputs of the sorting network. -- 2.11.0