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