src/sn_network.c

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <strings.h>
   5 #include <ctype.h>
   6 #include <assert.h>
   7
   8 #include "sn_network.h"
   9
  10 sn_network_t *sn_network_create (int inputs_num)
  11 {
  12   sn_network_t *n;
  13
  14   n = (sn_network_t *) malloc (sizeof (sn_network_t));
  15   if (n == NULL)
  16     return (NULL);
  17   memset (n, '\0', sizeof (sn_network_t));
  18
  19   n->inputs_num = inputs_num;
  20
  21   return (n);
  22 } /* sn_network_t *sn_network_create */
  23
  24 void sn_network_destroy (sn_network_t *n)
  25 {
  26   if (n == NULL)
  27     return;
  28
  29   if (n->stages != NULL)
  30   {
  31     int i;
  32     for (i = 0; i < n->stages_num; i++)
  33     {
  34       sn_stage_destroy (n->stages[i]);
  35       n->stages[i] = NULL;
  36     }
  37     n->stages = NULL;
  38   }
  39
  40   free (n);
  41 } /* void sn_network_destroy */
  42
  43 int sn_network_stage_add (sn_network_t *n, sn_stage_t *s)
  44 {
  45   sn_stage_t **temp;
  46
  47   temp = (sn_stage_t **) realloc (n->stages, (n->stages_num + 1)
  48       * sizeof (sn_stage_t *));
  49   if (temp == NULL)
  50     return (-1);
  51
  52   n->stages = temp;
  53   SN_STAGE_DEPTH (s) = n->stages_num;
  54   n->stages[n->stages_num] = s;
  55   n->stages_num++;
  56
  57   return (0);
  58 } /* int sn_network_stage_add */
  59
  60 int sn_network_stage_remove (sn_network_t *n, int s_num)
  61 {
  62   int nmemb = n->stages_num - (s_num + 1);
  63   sn_stage_t **temp;
  64
  65   assert (s_num < n->stages_num);
  66
  67   sn_stage_destroy (n->stages[s_num]);
  68   n->stages[s_num] = NULL;
  69
  70   if (nmemb > 0)
  71     memmove (n->stages + s_num, n->stages + (s_num + 1),
  72         nmemb * sizeof (sn_stage_t *));
  73   n->stages_num--;
  74
  75   /* Free the unused memory */
  76   temp = (sn_stage_t **) realloc (n->stages,
  77       n->stages_num * sizeof (sn_stage_t *));
  78   if (temp == NULL)
  79     return (-1);
  80   n->stages = temp;
  81
  82   return (0);
  83 } /* int sn_network_stage_remove */
  84
  85 int sn_network_show (sn_network_t *n)
  86 {
  87   int i;
  88
  89   for (i = 0; i < n->stages_num; i++)
  90     sn_stage_show (n->stages[i]);
  91
  92   return (0);
  93 } /* int sn_network_show */
  94
  95 int sn_network_invert (sn_network_t *n)
  96 {
  97   int i;
  98
  99   for (i = 0; i < n->stages_num; i++)
 100     sn_stage_invert (n->stages[i]);
 101
 102   return (0);
 103 } /* int sn_network_invert */
 104
 105 int sn_network_compress (sn_network_t *n)
 106 {
 107   int i;
 108   int j;
 109   int k;
 110
 111   for (i = 1; i < n->stages_num; i++)
 112   {
 113     sn_stage_t *s;
 114
 115     s = n->stages[i];
 116
 117     for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
 118     {
 119       sn_comparator_t *c = SN_STAGE_COMP_GET (s, j);
 120       int move_to = i;
 121
 122       for (k = i - 1; k >= 0; k--)
 123       {
 124         int conflict;
 125
 126         conflict = sn_stage_comparator_check_conflict (n->stages[k], c);
 127         if (conflict == 0)
 128         {
 129           move_to = k;
 130           continue;
 131         }
 132
 133         if (conflict == 2)
 134           move_to = -1;
 135         break;
 136       }
 137
 138       if (move_to < i)
 139       {
 140         if (move_to >= 0)
 141           sn_stage_comparator_add (n->stages[move_to], c);
 142         sn_stage_comparator_remove (s, j);
 143         j--;
 144       }
 145     }
 146   }
 147
 148   return (0);
 149 } /* int sn_network_compress */
 150
 151 int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir)
 152 {
 153   int i;
 154   int position = input;
 155
 156   for (i = 0; i < n->stages_num; i++)
 157   {
 158     sn_stage_t *s;
 159     int new_position;
 160
 161     s = n->stages[i];
 162     new_position = sn_stage_cut_at (s, position, dir);
 163
 164     if (position != new_position)
 165     {
 166       int j;
 167
 168       for (j = 0; j < i; j++)
 169         sn_stage_swap (n->stages[j], position, new_position);
 170     }
 171
 172     position = new_position;
 173   }
 174
 175   assert (((dir == DIR_MIN) && (position == 0))
 176       || ((dir == DIR_MAX) && (position == (n->inputs_num - 1))));
 177
 178
 179   for (i = 0; i < n->stages_num; i++)
 180     sn_stage_remove_input (n->stages[i], position);
 181
 182   n->inputs_num--;
 183
 184   return (0);
 185 } /* int sn_network_cut_at */
 186
 187 static int sn_network_add_bitonic_merger_recursive (sn_network_t *n,
 188     int low, int num)
 189 {
 190   sn_stage_t *s;
 191   int m;
 192   int i;
 193
 194   s = sn_stage_create (n->stages_num);
 195   if (s == NULL)
 196     return (-1);
 197
 198   if (num == 1)
 199     return (0);
 200
 201   m = num / 2;
 202
 203   for (i = low; i < (low + m); i++)
 204   {
 205     sn_comparator_t c;
 206
 207     c.min = i;
 208     c.max = i + m;
 209
 210     sn_stage_comparator_add (s, &c);
 211   }
 212
 213   sn_network_stage_add (n, s);
 214
 215   sn_network_add_bitonic_merger_recursive (n, low, m);
 216   sn_network_add_bitonic_merger_recursive (n, low + m, m);
 217
 218   return (0);
 219 } /* int sn_network_add_bitonic_merger_recursive */
 220
 221 static int sn_network_add_bitonic_merger (sn_network_t *n)
 222 {
 223   sn_stage_t *s;
 224   int m;
 225   int i;
 226
 227   s = sn_stage_create (n->stages_num);
 228   if (s == NULL)
 229     return (-1);
 230
 231   m = n->inputs_num / 2;
 232
 233   for (i = 0; i < m; i++)
 234   {
 235     sn_comparator_t c;
 236
 237     c.min = i;
 238     c.max = n->inputs_num - (i + 1);
 239
 240     sn_stage_comparator_add (s, &c);
 241   }
 242
 243   sn_network_stage_add (n, s);
 244
 245   sn_network_add_bitonic_merger_recursive (n, 0, m);
 246   sn_network_add_bitonic_merger_recursive (n, m, m);
 247
 248   return (0);
 249 } /* int sn_network_add_bitonic_merger */
 250
 251 sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1)
 252 {
 253   sn_network_t *n;
 254   int stages_num;
 255   int i;
 256   int j;
 257
 258   stages_num = (n0->stages_num > n1->stages_num)
 259     ? n0->stages_num
 260     : n1->stages_num;
 261
 262   n = sn_network_create (n0->inputs_num + n1->inputs_num);
 263   if (n == NULL)
 264     return (NULL);
 265
 266   for (i = 0; i < stages_num; i++)
 267   {
 268     sn_stage_t *s = sn_stage_create (i);
 269
 270     if (i < n0->stages_num)
 271       for (j = 0; j < SN_STAGE_COMP_NUM (n0->stages[i]); j++)
 272       {
 273         sn_comparator_t *c = SN_STAGE_COMP_GET (n0->stages[i], j);
 274         sn_stage_comparator_add (s, c);
 275       }
 276
 277     if (i < n1->stages_num)
 278       for (j = 0; j < SN_STAGE_COMP_NUM (n1->stages[i]); j++)
 279       {
 280         sn_comparator_t *c_orig = SN_STAGE_COMP_GET (n1->stages[i], j);
 281         sn_comparator_t  c_copy;
 282
 283         SN_COMP_MIN(&c_copy) = SN_COMP_MIN(c_orig) + n0->inputs_num;
 284         SN_COMP_MAX(&c_copy) = SN_COMP_MAX(c_orig) + n0->inputs_num;
 285
 286         sn_stage_comparator_add (s, &c_copy);
 287       }
 288
 289     sn_network_stage_add (n, s);
 290   }
 291
 292   sn_network_add_bitonic_merger (n);
 293   sn_network_compress (n);
 294
 295   return (n);
 296 } /* sn_network_t *sn_network_combine */
 297
 298 sn_network_t *sn_network_read (FILE *fh)
 299 {
 300   sn_network_t *n;
 301   char buffer[64];
 302
 303   int opt_inputs = 0;
 304
 305   while (fgets (buffer, sizeof (buffer), fh) != NULL)
 306   {
 307     char *str_key = buffer;
 308     char *str_value = NULL;
 309     int   buffer_len = strlen (buffer);
 310
 311     while ((buffer_len > 0) && ((buffer[buffer_len - 1] == '\n')
 312           || (buffer[buffer_len - 1] == '\r')))
 313     {
 314       buffer_len--;
 315       buffer[buffer_len] = '\0';
 316     }
 317     if (buffer_len == 0)
 318       break;
 319
 320     str_value = strchr (buffer, ':');
 321     if (str_value == NULL)
 322     {
 323       printf ("Cannot parse line: %s\n", buffer);
 324       continue;
 325     }
 326
 327     *str_value = '\0'; str_value++;
 328     while ((*str_value != '\0') && (isspace (*str_value) != 0))
 329       str_value++;
 330
 331     if (strcasecmp ("Inputs", str_key) == 0)
 332       opt_inputs = atoi (str_value);
 333     else
 334       printf ("Unknown key: %s\n", str_key);
 335   } /* while (fgets) */
 336
 337   if (opt_inputs < 2)
 338     return (NULL);
 339
 340   n = sn_network_create (opt_inputs);
 341
 342   while (42)
 343   {
 344     sn_stage_t *s;
 345
 346     s = sn_stage_read (fh);
 347     if (s == NULL)
 348       break;
 349
 350     sn_network_stage_add (n, s);
 351   }
 352
 353   if (SN_NETWORK_STAGE_NUM (n) < 1)
 354   {
 355     sn_network_destroy (n);
 356     return (NULL);
 357   }
 358
 359   return (n);
 360 } /* sn_network_t *sn_network_read */
 361
 362 sn_network_t *sn_network_read_file (const char *file)
 363 {
 364   sn_network_t *n;
 365   FILE *fh;
 366
 367   fh = fopen (file, "r");
 368   if (fh == NULL)
 369     return (NULL);
 370
 371   n = sn_network_read (fh);
 372
 373   fclose (fh);
 374
 375   return (n);
 376 } /* sn_network_t *sn_network_read_file */
 377
 378 int sn_network_write (sn_network_t *n, FILE *fh)
 379 {
 380   int i;
 381
 382   fprintf (fh, "Inputs: %i\n", n->inputs_num);
 383   fprintf (fh, "\n");
 384
 385   for (i = 0; i < n->stages_num; i++)
 386     sn_stage_write (n->stages[i], fh);
 387
 388   return (0);
 389 } /* int sn_network_write */
 390
 391 /* vim: set shiftwidth=2 softtabstop=2 : */