From 0f2d6e79cfef8b0db5372f832a301fee124039cb Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Sat, 10 May 2008 08:30:43 +0200 Subject: [PATCH] src/sn_{network,stage}.[ch]: Add a brute force checker. And the needed actual sorting code. --- src/sn_network.c | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/sn_network.h | 3 +++ src/sn_stage.c | 22 +++++++++++++++++- src/sn_stage.h | 2 ++ 4 files changed, 96 insertions(+), 1 deletion(-) diff --git a/src/sn_network.c b/src/sn_network.c index ba5fffb..1cc2d06 100644 --- a/src/sn_network.c +++ b/src/sn_network.c @@ -512,6 +512,76 @@ sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1) return (n); } /* sn_network_t *sn_network_combine */ +int sn_network_sort (sn_network_t *n, int *values) +{ + int status; + int i; + + status = 0; + for (i = 0; i < n->stages_num; i++) + { + status = sn_stage_sort (n->stages[i], values); + if (status != 0) + return (status); + } + + return (status); +} /* int sn_network_sort */ + +int sn_network_brute_force_check (sn_network_t *n) +{ + int test_pattern[n->inputs_num]; + int values[n->inputs_num]; + int status; + int i; + + memset (test_pattern, 0, sizeof (test_pattern)); + while (42) + { + int previous; + int overflow; + + /* Copy the current pattern and let the network sort it */ + memcpy (values, test_pattern, sizeof (values)); + status = sn_network_sort (n, values); + if (status != 0) + return (status); + + /* Check if the array is now sorted. */ + previous = values[0]; + for (i = 1; i < n->inputs_num; i++) + { + if (previous > values[i]) + return (1); + previous = values[i]; + } + + /* Generate the next test pattern */ + overflow = 1; + for (i = 0; i < n->inputs_num; i++) + { + if (test_pattern[i] == 0) + { + test_pattern[i] = 1; + overflow = 0; + break; + } + else + { + test_pattern[i] = 0; + overflow = 1; + } + } + + /* Break out of the while loop if we tested all possible patterns */ + if (overflow == 1) + break; + } /* while (42) */ + + /* All tests successfull */ + return (0); +} /* int sn_network_brute_force_check */ + sn_network_t *sn_network_read (FILE *fh) { sn_network_t *n; diff --git a/src/sn_network.h b/src/sn_network.h index 6aebf4a..4bcd586 100644 --- a/src/sn_network.h +++ b/src/sn_network.h @@ -46,6 +46,9 @@ void sn_network_destroy (sn_network_t *n); int sn_network_stage_add (sn_network_t *n, sn_stage_t *s); int sn_network_stage_remove (sn_network_t *n, int s_num); +int sn_network_sort (sn_network_t *n, int *values); +int sn_network_brute_force_check (sn_network_t *n); + int sn_network_show (sn_network_t *n); int sn_network_invert (sn_network_t *n); int sn_network_compress (sn_network_t *n); diff --git a/src/sn_stage.c b/src/sn_stage.c index dfd3fb5..bade6c4 100644 --- a/src/sn_stage.c +++ b/src/sn_stage.c @@ -56,6 +56,27 @@ void sn_stage_destroy (sn_stage_t *s) free (s); } /* void sn_stage_destroy */ +int sn_stage_sort (sn_stage_t *s, int *values) +{ + sn_comparator_t *c; + int i; + + for (i = 0; i < s->comparators_num; i++) + { + c = s->comparators + i; + if (values[c->min] > values[c->max]) + { + int temp; + + temp = values[c->min]; + values[c->min] = values[c->max]; + values[c->max] = temp; + } + } + + return (0); +} /* int sn_stage_sort */ + int sn_stage_comparator_add (sn_stage_t *s, const sn_comparator_t *c) { sn_comparator_t *temp; @@ -172,7 +193,6 @@ int sn_stage_show (sn_stage_t *s) int j; int k; - for (i = 0; i < s->comparators_num; i++) { lines[i] = -1; diff --git a/src/sn_stage.h b/src/sn_stage.h index 4a57f5e..e1cb898 100644 --- a/src/sn_stage.h +++ b/src/sn_stage.h @@ -48,6 +48,8 @@ sn_stage_t *sn_stage_create (int depth); sn_stage_t *sn_stage_clone (const sn_stage_t *s); void sn_stage_destroy (sn_stage_t *s); +int sn_stage_sort (sn_stage_t *s, int *values); + int sn_stage_comparator_add (sn_stage_t *s, const sn_comparator_t *c); int sn_stage_comparator_remove (sn_stage_t *s, int c_num); int sn_stage_comparator_check_conflict (sn_stage_t *s, const sn_comparator_t *c); -- 2.11.0