From 2b64b183834075911f9e53a6f0132d116bf45a76 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Fri, 17 Dec 2010 14:31:54 +0100 Subject: [PATCH] sn-pairwise: Implement the pairwise sorting network. --- README | 9 ++++++- src/Makefile.am | 5 +++- src/sn-pairwise.c | 64 +++++++++++++++++++++++++++++++++++++++++++++++++ src/sn_network.c | 72 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/sn_network.h | 9 +++++++ 5 files changed, 157 insertions(+), 2 deletions(-) create mode 100644 src/sn-pairwise.c diff --git a/README b/README index 86f7733..3778dde 100644 --- a/README +++ b/README @@ -45,9 +45,16 @@ The distribution includes the following utility programs: way. * sn-oddevenmerge - Creates a odd-even-merge-sort network with a given number of inputs and + Create an odd-even merge network with a given number of left and right + inputs. The resulting network is printed to STDOUT. + + * sn-oddevensort + Creates an odd-even mergesort network with a given number of inputs and prints the network to STDOUT. + * sn-pairwise + Create a pairwise sorting network based on the paper by Ian Parberry. + * sn-shmoo Prints a so-called "shmoo chart" of a comparator network to STDOUT. The running time of this tool is exponential, roughly O(m * 2^n) where m is the diff --git a/src/Makefile.am b/src/Makefile.am index fb28f66..e30ca07 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -4,7 +4,7 @@ lib_LTLIBRARIES = libsortnetwork.la bin_PROGRAMS = sn-apply sn-batcher sn-bb sn-bb-merge sn-check-bf sn-cut \ sn-info sn-markov sn-merge sn-normalize \ - sn-oddevenmerge sn-oddevensort \ + sn-oddevenmerge sn-oddevensort sn-pairwise \ sn-shmoo sn-show sn-svg sn-tex libsortnetwork_la_SOURCES = sn_network.c sn_network.h \ @@ -50,6 +50,9 @@ sn_oddevenmerge_LDADD = libsortnetwork.la sn_oddevensort_SOURCES = sn-oddevensort.c sn_oddevensort_LDADD = libsortnetwork.la +sn_pairwise_SOURCES = sn-pairwise.c +sn_pairwise_LDADD = libsortnetwork.la + sn_shmoo_SOURCES = sn-shmoo.c sn_shmoo_LDADD = libsortnetwork.la diff --git a/src/sn-pairwise.c b/src/sn-pairwise.c new file mode 100644 index 0000000..99079d5 --- /dev/null +++ b/src/sn-pairwise.c @@ -0,0 +1,64 @@ +/** + * libsortnetwork - src/sn-pairwise.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 *n; + size_t inputs_num; + + if (argc != 2) + { + printf ("Usage: %s \n", argv[0]); + return (0); + } + + inputs_num = (size_t) atoi (argv[1]); + if (inputs_num < 2) + { + fprintf (stderr, "Invalid number of inputs: %zu\n", inputs_num); + return (1); + } + + n = sn_network_create_pairwise (inputs_num); + if (n == NULL) + { + printf ("n == NULL!\n"); + return (1); + } + + sn_network_write (n, stdout); + + return (0); +} /* int main */ + +/* vim: set shiftwidth=2 softtabstop=2 : */ diff --git a/src/sn_network.c b/src/sn_network.c index b490de4..1b3dd36 100644 --- a/src/sn_network.c +++ b/src/sn_network.c @@ -135,6 +135,78 @@ sn_network_t *sn_network_create_odd_even_mergesort (int inputs_num) /* {{{ */ } } /* }}} sn_network_t *sn_network_create_odd_even_mergesort */ +static int sn_network_create_pairwise_internal (sn_network_t *n, /* {{{ */ + int *inputs, int inputs_num) +{ + int i; + int inputs_copy[inputs_num]; + int m; + + for (i = 1; i < inputs_num; i += 2) + { + sn_comparator_t *c = sn_comparator_create (inputs[i-1], inputs[i]); + sn_network_comparator_add (n, c); + sn_comparator_destroy (c); + } + + if (inputs_num <= 2) + return (0); + + /* Sort "pairs" recursively. Like with odd-even mergesort, odd and even lines + * are handled recursively and later reunited. */ + for (i = 0; i < inputs_num; i += 2) + inputs_copy[(int) (i / 2)] = inputs[i]; + /* Recursive call #1 with first set of lines */ + sn_network_create_pairwise_internal (n, inputs_copy, + (int) ((inputs_num + 1) / 2)); + + for (i = 1; i < inputs_num; i += 2) + inputs_copy[(int) (i / 2)] = inputs[i]; + /* Recursive call #2 with second set of lines */ + sn_network_create_pairwise_internal (n, inputs_copy, + (int) (inputs_num/ 2)); + + /* m is the "amplitude" of the sorted pairs. This is a bit tricky to read due + * to different indices being used in the paper, unfortunately. */ + m = inputs_num / 2; + while (m > 1) + { + for (i = 1; (i + (m - 1)) < inputs_num; i += 2) + { + int left = i; + int right = i + (m - 1); + sn_comparator_t *c; + + assert (left < right); + c = sn_comparator_create (inputs[left], inputs[right]); + sn_network_comparator_add (n, c); + sn_comparator_destroy (c); + } + + m = m / 2; + } /* while (m > 1) */ + + return (0); +} /* }}} int sn_network_create_pairwise_internal */ + +sn_network_t *sn_network_create_pairwise (int inputs_num) /* {{{ */ +{ + sn_network_t *n = sn_network_create (inputs_num); + int inputs[inputs_num]; + int i; + + if (n == NULL) + return (NULL); + + for (i = 0; i < inputs_num; i++) + inputs[i] = i; + + sn_network_create_pairwise_internal (n, inputs, inputs_num); + sn_network_compress (n); + + return (n); +} /* }}} sn_network_t *sn_network_create_pairwise */ + int sn_network_stage_add (sn_network_t *n, sn_stage_t *s) /* {{{ */ { sn_stage_t **temp; diff --git a/src/sn_network.h b/src/sn_network.h index d312c35..f56e3ca 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 sorting network using the Pairwise sorting algorithm published + * by Ian Parberry. + * \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_pairwise (int inputs_num); + +/** * Append a new stage to a comparator network. * * \param n The comparator network to which to add the stage. -- 2.11.0