From 0f2d6e79cfef8b0db5372f832a301fee124039cb Mon Sep 17 00:00:00 2001
From: Florian Forster <octo@leeloo.home.verplant.org>
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