src/sn-shmoo.c

   1 /**
   2  * libsortnetwork - src/sn-normalize.c
   3  * Copyright (C) 2008-2010  Florian octo Forster
   4  *
   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.
   8  *
   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.
  13  *
  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
  17  *
  18  * Authors:
  19  *   Florian octo Forster <ff at octo.it>
  20  **/
  21
  22 #ifndef _ISOC99_SOURCE
  23 # define _ISOC99_SOURCE
  24 #endif
  25 #ifndef _POSIX_C_SOURCE
  26 # define _POSIX_C_SOURCE 200112L
  27 #endif
  28
  29 #include <stdlib.h>
  30 #include <stdio.h>
  31 #include <string.h>
  32
  33 #include "sn_network.h"
  34 #include "sn_stage.h"
  35 #include "sn_comparator.h"
  36
  37 struct shmoo_line_info_s
  38 {
  39   int line_num;
  40   int zeros_num;
  41   int ones_num;
  42 };
  43 typedef struct shmoo_line_info_s shmoo_line_info_t;
  44
  45 struct shmoo_chart_s
  46 {
  47   int inputs_num;
  48   int stages_num;
  49   char *state;
  50 };
  51 typedef struct shmoo_chart_s shmoo_chart_t;
  52 #define STATE(sc, i, s, z) \
  53   (sc)->state[((z) * (sc)->inputs_num * (sc)->stages_num) \
  54     + ((s) * (sc)->inputs_num) \
  55     + (i)]
  56
  57 static int account_values (shmoo_chart_t *sc, /* {{{ */
  58     int stage_num, int zeros_num, int *values)
  59 {
  60   int i;
  61
  62   for (i = 0; i < sc->inputs_num; i++)
  63   {
  64     char state;
  65
  66     state = STATE (sc, i, stage_num, zeros_num);
  67     if (values[i] == 0)
  68     {
  69       if (state == '-')
  70         continue;
  71       else if (state == '1')
  72         state = '-';
  73       else /* if ((state == '0') || (state == '?')) */
  74         state = '0';
  75     }
  76     else /* if (values[i] == 1) */
  77     {
  78       if (state == '-')
  79         continue;
  80       else if (state == '0')
  81         state = '-';
  82       else /* if ((state == '1') || (state == '?')) */
  83         state = '1';
  84     }
  85
  86     STATE (sc, i, stage_num, zeros_num) = state;
  87   }
  88
  89   return (0);
  90 } /* }}} int account_values */
  91
  92 static int try_all_stages (const sn_network_t *n, /* {{{ */
  93     shmoo_chart_t *sc, int *pattern)
  94 {
  95   int values[n->inputs_num];
  96   int zeros_num;
  97   int i;
  98
  99   /* Copy the test pattern */
 100   memcpy (values, pattern, sizeof (values));
 101
 102   /* Count the zeros.. */
 103   zeros_num = 0;
 104   for (i = 0; i < n->inputs_num; i++)
 105     if (values[i] == 0)
 106       zeros_num++;
 107
 108   for (i = 0; i < n->stages_num; i++)
 109   {
 110     sn_stage_t *s;
 111
 112     s = n->stages[i];
 113     sn_stage_sort (s, values);
 114     account_values (sc, i, zeros_num, values);
 115   }
 116
 117   return (0);
 118 } /* }}} int try_all_stages */
 119
 120 static int try_all_patterns (const sn_network_t *n, /* {{{ */
 121     shmoo_chart_t *sc)
 122 {
 123   int test_pattern[n->inputs_num];
 124
 125   /* Initialize the pattern */
 126   memset (test_pattern, 0, sizeof (test_pattern));
 127
 128   while (42)
 129   {
 130     int overflow;
 131     int i;
 132
 133     try_all_stages (n, sc, test_pattern);
 134
 135     /* Generate the next test pattern */
 136     overflow = 1;
 137     for (i = 0; i < n->inputs_num; i++)
 138     {
 139       if (test_pattern[i] == 0)
 140       {
 141         test_pattern[i] = 1;
 142         overflow = 0;
 143         break;
 144       }
 145       else
 146       {
 147         test_pattern[i] = 0;
 148         overflow = 1;
 149       }
 150     }
 151
 152     /* Break out of the while loop if we tested all possible patterns */
 153     if (overflow == 1)
 154       break;
 155   } /* while (42) */
 156
 157   /* All tests successfull */
 158   return (0);
 159 } /* }}} int try_all_patterns */
 160
 161 static shmoo_chart_t *shmoo_chart_create (const sn_network_t *n)
 162 {
 163   shmoo_chart_t *sc;
 164   int state_size;
 165
 166   sc = malloc (sizeof (*sc));
 167   memset (sc, 0, sizeof (*sc));
 168
 169   sc->inputs_num = SN_NETWORK_INPUT_NUM (n);
 170   sc->stages_num = SN_NETWORK_STAGE_NUM (n);
 171
 172   state_size = sc->inputs_num * (sc->inputs_num + 1) * sc->stages_num;
 173   sc->state = calloc (state_size, sizeof (*sc->state));
 174
 175   memset (sc->state, (int) '?', state_size);
 176
 177   try_all_patterns (n, sc);
 178
 179   return (sc);
 180 } /* shmoo_chart_t *shmoo_chart_create */
 181
 182 static int compare_line_info (const void *av, const void *bv) /* {{{ */
 183 {
 184   const shmoo_line_info_t *al;
 185   const shmoo_line_info_t *bl;
 186
 187   al = av;
 188   bl = bv;
 189
 190   if (al->zeros_num > bl->zeros_num)
 191     return (-1);
 192   else if (al->zeros_num < bl->zeros_num)
 193     return (1);
 194   else if (al->ones_num > bl->ones_num)
 195     return (1);
 196   else if (al->ones_num < bl->ones_num)
 197     return (-1);
 198   else if (al->line_num < bl->line_num)
 199     return (-1);
 200   else if (al->line_num > bl->line_num)
 201     return (1);
 202   else
 203     return (0);
 204 } /* }}} int compare_line_info */
 205
 206 /*
 207  *
 208  *       11111110000000000
 209  *       65432109876543210
 210  *
 211  *  123: 00000000--------1
 212  *  111: 000000--------111
 213  *   23: 0000--------11111
 214  *  101: 0---------1111111
 215  */
 216 static void print_shmoo_stage (shmoo_chart_t *sc, int stage_num) /* {{{ */
 217 {
 218   shmoo_line_info_t line_info[sc->inputs_num];
 219   char buffer[sc->inputs_num + 2];
 220   int i;
 221
 222   for (i = 0; i < sc->inputs_num; i++)
 223   {
 224     int j;
 225
 226     line_info[i].line_num = i;
 227     line_info[i].zeros_num = 0;
 228     line_info[i].ones_num = 0;
 229
 230     for (j = 0; j < sc->inputs_num; j++)
 231       if (STATE(sc, i, stage_num, j) == '0')
 232         line_info[i].zeros_num++;
 233       else if (STATE(sc, i, stage_num, j) == '1')
 234         line_info[i].ones_num++;
 235   }
 236
 237   if (stage_num == -1)
 238   qsort (line_info, sc->inputs_num, sizeof (line_info[0]),
 239       compare_line_info);
 240
 241   printf ("=== After applying stage %i ===\n\n", stage_num);
 242
 243   if (sc->inputs_num > 9)
 244   {
 245     for (i = 0; i < (sc->inputs_num + 1); i++)
 246     {
 247       int j;
 248
 249       j = (sc->inputs_num - i) / 10;
 250
 251       buffer[i] = '0' + j;
 252     }
 253     buffer[sizeof (buffer) - 1] = 0;
 254     printf ("      %s\n", buffer);
 255   }
 256
 257   for (i = 0; i < (sc->inputs_num + 1); i++)
 258   {
 259     int j;
 260
 261     j = (sc->inputs_num - i) % 10;
 262
 263     buffer[i] = '0' + j;
 264   }
 265   buffer[sizeof (buffer) - 1] = 0;
 266   printf ("      %s\n\n", buffer);
 267
 268   for (i = 0; i < sc->inputs_num; i++)
 269   {
 270     int j;
 271     int line_num;
 272
 273     line_num = line_info[i].line_num;
 274
 275     for (j = 0; j < (sc->inputs_num + 1); j++)
 276     {
 277       int zeros_num;
 278
 279       zeros_num = sc->inputs_num - j;
 280
 281       buffer[j] = STATE(sc, line_num, stage_num, zeros_num);
 282     }
 283     buffer[sizeof (buffer) - 1] = 0;
 284
 285     printf (" %3i: %s\n", line_num, buffer);
 286   }
 287
 288   printf ("\n\n");
 289 } /* }}} void print_shmoo_stage */
 290
 291 static void print_shmoo (shmoo_chart_t *sc) /* {{{ */
 292 {
 293   int i;
 294
 295   for (i = 0; i < sc->stages_num; i++)
 296     print_shmoo_stage (sc, i);
 297 } /* }}} void print_shmoo */
 298
 299 static void exit_usage (const char *name)
 300 {
 301   printf ("%s [file]\n", name);
 302   exit (1);
 303 }
 304
 305 int main (int argc, char **argv)
 306 {
 307   sn_network_t *n;
 308   shmoo_chart_t *sc;
 309
 310   if (argc > 2)
 311   {
 312     exit_usage (argv[0]);
 313   }
 314   else if (argc == 2)
 315   {
 316     if ((strcmp ("-h", argv[1]) == 0)
 317         || (strcmp ("--help", argv[1]) == 0)
 318         || (strcmp ("-help", argv[1]) == 0))
 319       exit_usage (argv[0]);
 320
 321     n = sn_network_read_file (argv[1]);
 322   }
 323   else
 324   {
 325     n = sn_network_read (stdin);
 326   }
 327
 328   if (n == NULL)
 329   {
 330     printf ("n == NULL!\n");
 331     return (1);
 332   }
 333
 334   sc = shmoo_chart_create (n);
 335   print_shmoo (sc);
 336
 337   return (EXIT_SUCCESS);
 338 } /* }}} main */
 339
 340 /* vim: set sw=2 sts=2 et fdm=marker : */