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