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 sn_network_t *sn_network_clone (const sn_network_t *n)
  98 {
  99   sn_network_t *n_copy;
 100   int i;
 101
 102   n_copy = sn_network_create (n->inputs_num);
 103   if (n_copy == NULL)
 104     return (NULL);
 105
 106   for (i = 0; i < n->stages_num; i++)
 107   {
 108     sn_stage_t *s;
 109     int status;
 110
 111     s = sn_stage_clone (n->stages[i]);
 112     if (s == NULL)
 113       break;
 114
 115     status = sn_network_stage_add (n_copy, s);
 116     if (status != 0)
 117       break;
 118   }
 119
 120   if (i < n->stages_num)
 121   {
 122     sn_network_destroy (n_copy);
 123     return (NULL);
 124   }
 125
 126   return (n_copy);
 127 } /* sn_network_t *sn_network_clone */
 128
 129 int sn_network_show (sn_network_t *n)
 130 {
 131   int i;
 132
 133   for (i = 0; i < n->stages_num; i++)
 134     sn_stage_show (n->stages[i]);
 135
 136   return (0);
 137 } /* int sn_network_show */
 138
 139 int sn_network_invert (sn_network_t *n)
 140 {
 141   int i;
 142
 143   for (i = 0; i < n->stages_num; i++)
 144     sn_stage_invert (n->stages[i]);
 145
 146   return (0);
 147 } /* int sn_network_invert */
 148
 149 int sn_network_compress (sn_network_t *n)
 150 {
 151   int i;
 152   int j;
 153   int k;
 154
 155   for (i = 1; i < n->stages_num; i++)
 156   {
 157     sn_stage_t *s;
 158
 159     s = n->stages[i];
 160
 161     for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
 162     {
 163       sn_comparator_t *c = SN_STAGE_COMP_GET (s, j);
 164       int move_to = i;
 165
 166       for (k = i - 1; k >= 0; k--)
 167       {
 168         int conflict;
 169
 170         conflict = sn_stage_comparator_check_conflict (n->stages[k], c);
 171         if (conflict == 0)
 172         {
 173           move_to = k;
 174           continue;
 175         }
 176
 177         if (conflict == 2)
 178           move_to = -1;
 179         break;
 180       }
 181
 182       if (move_to < i)
 183       {
 184         if (move_to >= 0)
 185           sn_stage_comparator_add (n->stages[move_to], c);
 186         sn_stage_comparator_remove (s, j);
 187         j--;
 188       }
 189     }
 190   }
 191
 192   while ((n->stages_num > 0)
 193       && (SN_STAGE_COMP_NUM (n->stages[n->stages_num - 1]) == 0))
 194     sn_network_stage_remove (n, n->stages_num - 1);
 195
 196   return (0);
 197 } /* int sn_network_compress */
 198
 199 int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir)
 200 {
 201   int i;
 202   int position = input;
 203
 204   for (i = 0; i < n->stages_num; i++)
 205   {
 206     sn_stage_t *s;
 207     int new_position;
 208
 209     s = n->stages[i];
 210     new_position = sn_stage_cut_at (s, position, dir);
 211
 212     if (position != new_position)
 213     {
 214       int j;
 215
 216       for (j = 0; j < i; j++)
 217         sn_stage_swap (n->stages[j], position, new_position);
 218     }
 219
 220     position = new_position;
 221   }
 222
 223   assert (((dir == DIR_MIN) && (position == 0))
 224       || ((dir == DIR_MAX) && (position == (n->inputs_num - 1))));
 225
 226   for (i = 0; i < n->stages_num; i++)
 227     sn_stage_remove_input (n->stages[i], position);
 228
 229   n->inputs_num--;
 230
 231   return (0);
 232 } /* int sn_network_cut_at */
 233
 234 static int sn_network_add_bitonic_merger_recursive (sn_network_t *n,
 235     int low, int num)
 236 {
 237   sn_stage_t *s;
 238   int m;
 239   int i;
 240
 241   if (num == 1)
 242     return (0);
 243
 244   s = sn_stage_create (n->stages_num);
 245   if (s == NULL)
 246     return (-1);
 247
 248   m = num / 2;
 249
 250   for (i = low; i < (low + m); i++)
 251   {
 252     sn_comparator_t c;
 253
 254     c.min = i;
 255     c.max = i + m;
 256
 257     sn_stage_comparator_add (s, &c);
 258   }
 259
 260   sn_network_stage_add (n, s);
 261
 262   sn_network_add_bitonic_merger_recursive (n, low, m);
 263   sn_network_add_bitonic_merger_recursive (n, low + m, m);
 264
 265   return (0);
 266 } /* int sn_network_add_bitonic_merger_recursive */
 267
 268 static int sn_network_add_bitonic_merger (sn_network_t *n)
 269 {
 270   sn_stage_t *s;
 271   int m;
 272   int i;
 273
 274   s = sn_stage_create (n->stages_num);
 275   if (s == NULL)
 276     return (-1);
 277
 278   m = n->inputs_num / 2;
 279
 280   for (i = 0; i < m; i++)
 281   {
 282     sn_comparator_t c;
 283
 284     c.min = i;
 285     c.max = n->inputs_num - (i + 1);
 286
 287     sn_stage_comparator_add (s, &c);
 288   }
 289
 290   sn_network_stage_add (n, s);
 291
 292   sn_network_add_bitonic_merger_recursive (n, 0, m);
 293   sn_network_add_bitonic_merger_recursive (n, m, m);
 294
 295   return (0);
 296 } /* int sn_network_add_bitonic_merger */
 297
 298 sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1)
 299 {
 300   sn_network_t *n;
 301   int stages_num;
 302   int i;
 303   int j;
 304
 305   stages_num = (n0->stages_num > n1->stages_num)
 306     ? n0->stages_num
 307     : n1->stages_num;
 308
 309   n = sn_network_create (n0->inputs_num + n1->inputs_num);
 310   if (n == NULL)
 311     return (NULL);
 312
 313   for (i = 0; i < stages_num; i++)
 314   {
 315     sn_stage_t *s = sn_stage_create (i);
 316
 317     if (i < n0->stages_num)
 318       for (j = 0; j < SN_STAGE_COMP_NUM (n0->stages[i]); j++)
 319       {
 320         sn_comparator_t *c = SN_STAGE_COMP_GET (n0->stages[i], j);
 321         sn_stage_comparator_add (s, c);
 322       }
 323
 324     if (i < n1->stages_num)
 325       for (j = 0; j < SN_STAGE_COMP_NUM (n1->stages[i]); j++)
 326       {
 327         sn_comparator_t *c_orig = SN_STAGE_COMP_GET (n1->stages[i], j);
 328         sn_comparator_t  c_copy;
 329
 330         SN_COMP_MIN(&c_copy) = SN_COMP_MIN(c_orig) + n0->inputs_num;
 331         SN_COMP_MAX(&c_copy) = SN_COMP_MAX(c_orig) + n0->inputs_num;
 332
 333         sn_stage_comparator_add (s, &c_copy);
 334       }
 335
 336     sn_network_stage_add (n, s);
 337   }
 338
 339   sn_network_add_bitonic_merger (n);
 340   sn_network_compress (n);
 341
 342   return (n);
 343 } /* sn_network_t *sn_network_combine */
 344
 345 sn_network_t *sn_network_read (FILE *fh)
 346 {
 347   sn_network_t *n;
 348   char buffer[64];
 349
 350   int opt_inputs = 0;
 351
 352   while (fgets (buffer, sizeof (buffer), fh) != NULL)
 353   {
 354     char *str_key = buffer;
 355     char *str_value = NULL;
 356     int   buffer_len = strlen (buffer);
 357
 358     while ((buffer_len > 0) && ((buffer[buffer_len - 1] == '\n')
 359           || (buffer[buffer_len - 1] == '\r')))
 360     {
 361       buffer_len--;
 362       buffer[buffer_len] = '\0';
 363     }
 364     if (buffer_len == 0)
 365       break;
 366
 367     str_value = strchr (buffer, ':');
 368     if (str_value == NULL)
 369     {
 370       printf ("Cannot parse line: %s\n", buffer);
 371       continue;
 372     }
 373
 374     *str_value = '\0'; str_value++;
 375     while ((*str_value != '\0') && (isspace (*str_value) != 0))
 376       str_value++;
 377
 378     if (strcasecmp ("Inputs", str_key) == 0)
 379       opt_inputs = atoi (str_value);
 380     else
 381       printf ("Unknown key: %s\n", str_key);
 382   } /* while (fgets) */
 383
 384   if (opt_inputs < 2)
 385     return (NULL);
 386
 387   n = sn_network_create (opt_inputs);
 388
 389   while (42)
 390   {
 391     sn_stage_t *s;
 392
 393     s = sn_stage_read (fh);
 394     if (s == NULL)
 395       break;
 396
 397     sn_network_stage_add (n, s);
 398   }
 399
 400   if (SN_NETWORK_STAGE_NUM (n) < 1)
 401   {
 402     sn_network_destroy (n);
 403     return (NULL);
 404   }
 405
 406   return (n);
 407 } /* sn_network_t *sn_network_read */
 408
 409 sn_network_t *sn_network_read_file (const char *file)
 410 {
 411   sn_network_t *n;
 412   FILE *fh;
 413
 414   fh = fopen (file, "r");
 415   if (fh == NULL)
 416     return (NULL);
 417
 418   n = sn_network_read (fh);
 419
 420   fclose (fh);
 421
 422   return (n);
 423 } /* sn_network_t *sn_network_read_file */
 424
 425 int sn_network_write (sn_network_t *n, FILE *fh)
 426 {
 427   int i;
 428
 429   fprintf (fh, "Inputs: %i\n", n->inputs_num);
 430   fprintf (fh, "\n");
 431
 432   for (i = 0; i < n->stages_num; i++)
 433     sn_stage_write (n->stages[i], fh);
 434
 435   return (0);
 436 } /* int sn_network_write */
 437
 438 int sn_network_write_file (sn_network_t *n, const char *file)
 439 {
 440   int status;
 441   FILE *fh;
 442
 443   fh = fopen (file, "w");
 444   if (fh == NULL)
 445     return (-1);
 446
 447   status = sn_network_write (n, fh);
 448
 449   fclose (fh);
 450
 451   return (status);
 452 } /* int sn_network_write_file */
 453
 454 /* vim: set shiftwidth=2 softtabstop=2 : */