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 #include "sn_random.h"
  10
  11 sn_network_t *sn_network_create (int inputs_num)
  12 {
  13   sn_network_t *n;
  14
  15   n = (sn_network_t *) malloc (sizeof (sn_network_t));
  16   if (n == NULL)
  17     return (NULL);
  18   memset (n, '\0', sizeof (sn_network_t));
  19
  20   n->inputs_num = inputs_num;
  21
  22   return (n);
  23 } /* sn_network_t *sn_network_create */
  24
  25 void sn_network_destroy (sn_network_t *n)
  26 {
  27   if (n == NULL)
  28     return;
  29
  30   if (n->stages != NULL)
  31   {
  32     int i;
  33     for (i = 0; i < n->stages_num; i++)
  34     {
  35       sn_stage_destroy (n->stages[i]);
  36       n->stages[i] = NULL;
  37     }
  38     free (n->stages);
  39     n->stages = NULL;
  40   }
  41
  42   free (n);
  43 } /* void sn_network_destroy */
  44
  45 int sn_network_stage_add (sn_network_t *n, sn_stage_t *s)
  46 {
  47   sn_stage_t **temp;
  48
  49   temp = (sn_stage_t **) realloc (n->stages, (n->stages_num + 1)
  50       * sizeof (sn_stage_t *));
  51   if (temp == NULL)
  52     return (-1);
  53
  54   n->stages = temp;
  55   SN_STAGE_DEPTH (s) = n->stages_num;
  56   n->stages[n->stages_num] = s;
  57   n->stages_num++;
  58
  59   return (0);
  60 } /* int sn_network_stage_add */
  61
  62 int sn_network_stage_remove (sn_network_t *n, int s_num)
  63 {
  64   int nmemb = n->stages_num - (s_num + 1);
  65   sn_stage_t **temp;
  66
  67   assert (s_num < n->stages_num);
  68
  69   sn_stage_destroy (n->stages[s_num]);
  70   n->stages[s_num] = NULL;
  71
  72   if (nmemb > 0)
  73   {
  74     memmove (n->stages + s_num, n->stages + (s_num + 1),
  75         nmemb * sizeof (sn_stage_t *));
  76     n->stages[n->stages_num - 1] = NULL;
  77   }
  78   n->stages_num--;
  79
  80   /* Free the unused memory */
  81   if (n->stages_num == 0)
  82   {
  83     free (n->stages);
  84     n->stages = NULL;
  85   }
  86   else
  87   {
  88     temp = (sn_stage_t **) realloc (n->stages,
  89         n->stages_num * sizeof (sn_stage_t *));
  90     if (temp == NULL)
  91       return (-1);
  92     n->stages = temp;
  93   }
  94
  95   return (0);
  96 } /* int sn_network_stage_remove */
  97
  98 sn_network_t *sn_network_clone (const sn_network_t *n)
  99 {
 100   sn_network_t *n_copy;
 101   int i;
 102
 103   n_copy = sn_network_create (n->inputs_num);
 104   if (n_copy == NULL)
 105     return (NULL);
 106
 107   for (i = 0; i < n->stages_num; i++)
 108   {
 109     sn_stage_t *s;
 110     int status;
 111
 112     s = sn_stage_clone (n->stages[i]);
 113     if (s == NULL)
 114       break;
 115
 116     status = sn_network_stage_add (n_copy, s);
 117     if (status != 0)
 118       break;
 119   }
 120
 121   if (i < n->stages_num)
 122   {
 123     sn_network_destroy (n_copy);
 124     return (NULL);
 125   }
 126
 127   return (n_copy);
 128 } /* sn_network_t *sn_network_clone */
 129
 130 int sn_network_show (sn_network_t *n)
 131 {
 132   int i;
 133
 134   for (i = 0; i < n->stages_num; i++)
 135     sn_stage_show (n->stages[i]);
 136
 137   return (0);
 138 } /* int sn_network_show */
 139
 140 int sn_network_invert (sn_network_t *n)
 141 {
 142   int i;
 143
 144   for (i = 0; i < n->stages_num; i++)
 145     sn_stage_invert (n->stages[i]);
 146
 147   return (0);
 148 } /* int sn_network_invert */
 149
 150 int sn_network_compress (sn_network_t *n)
 151 {
 152   int i;
 153   int j;
 154   int k;
 155
 156   for (i = 1; i < n->stages_num; i++)
 157   {
 158     sn_stage_t *s;
 159
 160     s = n->stages[i];
 161
 162     for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
 163     {
 164       sn_comparator_t *c = SN_STAGE_COMP_GET (s, j);
 165       int move_to = i;
 166
 167       for (k = i - 1; k >= 0; k--)
 168       {
 169         int conflict;
 170
 171         conflict = sn_stage_comparator_check_conflict (n->stages[k], c);
 172         if (conflict == 0)
 173         {
 174           move_to = k;
 175           continue;
 176         }
 177
 178         if (conflict == 2)
 179           move_to = -1;
 180         break;
 181       }
 182
 183       if (move_to < i)
 184       {
 185         if (move_to >= 0)
 186           sn_stage_comparator_add (n->stages[move_to], c);
 187         sn_stage_comparator_remove (s, j);
 188         j--;
 189       }
 190     }
 191   }
 192
 193   while ((n->stages_num > 0)
 194       && (SN_STAGE_COMP_NUM (n->stages[n->stages_num - 1]) == 0))
 195     sn_network_stage_remove (n, n->stages_num - 1);
 196
 197   return (0);
 198 } /* int sn_network_compress */
 199
 200 int sn_network_normalize (sn_network_t *n)
 201 {
 202   int i;
 203
 204   for (i = n->stages_num - 1; i >= 0; i--)
 205   {
 206     sn_stage_t *s;
 207     int j;
 208
 209     s = n->stages[i];
 210
 211     for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
 212     {
 213       sn_comparator_t *c;
 214       int min;
 215       int max;
 216
 217       c = SN_STAGE_COMP_GET (s, j);
 218
 219       min = c->min;
 220       max = c->max;
 221
 222       if (min > max)
 223       {
 224         int k;
 225
 226         for (k = i; k >= 0; k--)
 227           sn_stage_swap (n->stages[k], min, max);
 228       }
 229     } /* for (j = 0 .. #comparators) */
 230   } /* for (i = n->stages_num - 1 .. 0) */
 231
 232   return (0);
 233 } /* int sn_network_normalize */
 234
 235 int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir)
 236 {
 237   int i;
 238   int position = input;
 239
 240   for (i = 0; i < n->stages_num; i++)
 241   {
 242     sn_stage_t *s;
 243     int new_position;
 244
 245     s = n->stages[i];
 246     new_position = sn_stage_cut_at (s, position, dir);
 247
 248     if (position != new_position)
 249     {
 250       int j;
 251
 252       for (j = 0; j < i; j++)
 253         sn_stage_swap (n->stages[j], position, new_position);
 254     }
 255
 256     position = new_position;
 257   }
 258
 259   assert (((dir == DIR_MIN) && (position == 0))
 260       || ((dir == DIR_MAX) && (position == (n->inputs_num - 1))));
 261
 262   for (i = 0; i < n->stages_num; i++)
 263     sn_stage_remove_input (n->stages[i], position);
 264
 265   n->inputs_num--;
 266
 267   return (0);
 268 } /* int sn_network_cut_at */
 269
 270 static int sn_network_add_bitonic_merger_recursive (sn_network_t *n,
 271     int low, int num)
 272 {
 273   sn_stage_t *s;
 274   int m;
 275   int i;
 276
 277   if (num == 1)
 278     return (0);
 279
 280   s = sn_stage_create (n->stages_num);
 281   if (s == NULL)
 282     return (-1);
 283
 284   m = num / 2;
 285
 286   for (i = low; i < (low + m); i++)
 287   {
 288     sn_comparator_t c;
 289
 290     c.min = i;
 291     c.max = i + m;
 292
 293     sn_stage_comparator_add (s, &c);
 294   }
 295
 296   sn_network_stage_add (n, s);
 297
 298   sn_network_add_bitonic_merger_recursive (n, low, m);
 299   sn_network_add_bitonic_merger_recursive (n, low + m, m);
 300
 301   return (0);
 302 } /* int sn_network_add_bitonic_merger_recursive */
 303
 304 static int sn_network_add_bitonic_merger (sn_network_t *n)
 305 {
 306   sn_stage_t *s;
 307   int m;
 308   int i;
 309
 310   s = sn_stage_create (n->stages_num);
 311   if (s == NULL)
 312     return (-1);
 313
 314   m = n->inputs_num / 2;
 315
 316   for (i = 0; i < m; i++)
 317   {
 318     sn_comparator_t c;
 319
 320     c.min = i;
 321     c.max = n->inputs_num - (i + 1);
 322
 323     sn_stage_comparator_add (s, &c);
 324   }
 325
 326   sn_network_stage_add (n, s);
 327
 328   sn_network_add_bitonic_merger_recursive (n, 0, m);
 329   sn_network_add_bitonic_merger_recursive (n, m, m);
 330
 331   return (0);
 332 } /* int sn_network_add_bitonic_merger */
 333
 334 static int sn_network_add_odd_even_merger_recursive (sn_network_t *n,
 335     int *indizes, int indizes_num)
 336 {
 337   if (indizes_num > 2)
 338   {
 339     sn_comparator_t c;
 340     sn_stage_t *s;
 341     int indizes_half_num;
 342     int *indizes_half;
 343     int status;
 344     int i;
 345
 346     indizes_half_num = indizes_num / 2;
 347     indizes_half = (int *) malloc (indizes_num * sizeof (int));
 348     if (indizes_half == NULL)
 349       return (-1);
 350
 351     for (i = 0; i < indizes_half_num; i++)
 352     {
 353       indizes_half[i] = indizes[2 * i];
 354       indizes_half[indizes_half_num + i] = indizes[(2 * i) + 1];
 355     }
 356
 357     status = sn_network_add_odd_even_merger_recursive (n,
 358         indizes_half, indizes_half_num);
 359     if (status != 0)
 360     {
 361       free (indizes_half);
 362       return (status);
 363     }
 364
 365     status = sn_network_add_odd_even_merger_recursive (n,
 366         indizes_half + indizes_half_num, indizes_half_num);
 367     if (status != 0)
 368     {
 369       free (indizes_half);
 370       return (status);
 371     }
 372
 373     free (indizes_half);
 374
 375     s = sn_stage_create (n->stages_num);
 376     if (s == NULL)
 377       return (-1);
 378
 379     for (i = 1; i < (indizes_num - 2); i += 2)
 380     {
 381       c.min = indizes[i];
 382       c.max = indizes[i + 1];
 383
 384       sn_stage_comparator_add (s, &c);
 385     }
 386
 387     sn_network_stage_add (n, s);
 388   }
 389   else
 390   {
 391     sn_comparator_t c;
 392     sn_stage_t *s;
 393
 394     assert (indizes_num == 2);
 395
 396     c.min = indizes[0];
 397     c.max = indizes[1];
 398
 399     s = sn_stage_create (n->stages_num);
 400     if (s == NULL)
 401       return (-1);
 402
 403     sn_stage_comparator_add (s, &c);
 404     sn_network_stage_add (n, s);
 405   }
 406
 407   return (0);
 408 } /* int sn_network_add_odd_even_merger_recursive */
 409
 410 static int sn_network_add_odd_even_merger (sn_network_t *n)
 411 {
 412   int *indizes;
 413   int indizes_num;
 414   int status;
 415   int i;
 416
 417   indizes_num = n->inputs_num;
 418   indizes = (int *) malloc (indizes_num * sizeof (int));
 419   if (indizes == NULL)
 420     return (-1);
 421
 422   for (i = 0; i < indizes_num; i++)
 423     indizes[i] = i;
 424
 425   status = sn_network_add_odd_even_merger_recursive (n,
 426       indizes, indizes_num);
 427
 428   free (indizes);
 429   return (status);
 430 } /* int sn_network_add_bitonic_merger */
 431
 432 sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1)
 433 {
 434   sn_network_t *n;
 435   int stages_num;
 436   int i;
 437   int j;
 438
 439   stages_num = (n0->stages_num > n1->stages_num)
 440     ? n0->stages_num
 441     : n1->stages_num;
 442
 443   n = sn_network_create (n0->inputs_num + n1->inputs_num);
 444   if (n == NULL)
 445     return (NULL);
 446
 447   for (i = 0; i < stages_num; i++)
 448   {
 449     sn_stage_t *s = sn_stage_create (i);
 450
 451     if (i < n0->stages_num)
 452       for (j = 0; j < SN_STAGE_COMP_NUM (n0->stages[i]); j++)
 453       {
 454         sn_comparator_t *c = SN_STAGE_COMP_GET (n0->stages[i], j);
 455         sn_stage_comparator_add (s, c);
 456       }
 457
 458     if (i < n1->stages_num)
 459       for (j = 0; j < SN_STAGE_COMP_NUM (n1->stages[i]); j++)
 460       {
 461         sn_comparator_t *c_orig = SN_STAGE_COMP_GET (n1->stages[i], j);
 462         sn_comparator_t  c_copy;
 463
 464         SN_COMP_MIN(&c_copy) = SN_COMP_MIN(c_orig) + n0->inputs_num;
 465         SN_COMP_MAX(&c_copy) = SN_COMP_MAX(c_orig) + n0->inputs_num;
 466
 467         sn_stage_comparator_add (s, &c_copy);
 468       }
 469
 470     sn_network_stage_add (n, s);
 471   }
 472
 473   if (sn_bounded_random (0, 1) == 0)
 474   {
 475     sn_network_add_bitonic_merger (n);
 476   }
 477   else
 478   {
 479     sn_network_add_odd_even_merger (n);
 480   }
 481
 482   sn_network_compress (n);
 483
 484   return (n);
 485 } /* sn_network_t *sn_network_combine */
 486
 487 sn_network_t *sn_network_read (FILE *fh)
 488 {
 489   sn_network_t *n;
 490   char buffer[64];
 491
 492   int opt_inputs = 0;
 493
 494   while (fgets (buffer, sizeof (buffer), fh) != NULL)
 495   {
 496     char *str_key = buffer;
 497     char *str_value = NULL;
 498     int   buffer_len = strlen (buffer);
 499
 500     while ((buffer_len > 0) && ((buffer[buffer_len - 1] == '\n')
 501           || (buffer[buffer_len - 1] == '\r')))
 502     {
 503       buffer_len--;
 504       buffer[buffer_len] = '\0';
 505     }
 506     if (buffer_len == 0)
 507       break;
 508
 509     str_value = strchr (buffer, ':');
 510     if (str_value == NULL)
 511     {
 512       printf ("Cannot parse line: %s\n", buffer);
 513       continue;
 514     }
 515
 516     *str_value = '\0'; str_value++;
 517     while ((*str_value != '\0') && (isspace (*str_value) != 0))
 518       str_value++;
 519
 520     if (strcasecmp ("Inputs", str_key) == 0)
 521       opt_inputs = atoi (str_value);
 522     else
 523       printf ("Unknown key: %s\n", str_key);
 524   } /* while (fgets) */
 525
 526   if (opt_inputs < 2)
 527     return (NULL);
 528
 529   n = sn_network_create (opt_inputs);
 530
 531   while (42)
 532   {
 533     sn_stage_t *s;
 534
 535     s = sn_stage_read (fh);
 536     if (s == NULL)
 537       break;
 538
 539     sn_network_stage_add (n, s);
 540   }
 541
 542   if (SN_NETWORK_STAGE_NUM (n) < 1)
 543   {
 544     sn_network_destroy (n);
 545     return (NULL);
 546   }
 547
 548   return (n);
 549 } /* sn_network_t *sn_network_read */
 550
 551 sn_network_t *sn_network_read_file (const char *file)
 552 {
 553   sn_network_t *n;
 554   FILE *fh;
 555
 556   fh = fopen (file, "r");
 557   if (fh == NULL)
 558     return (NULL);
 559
 560   n = sn_network_read (fh);
 561
 562   fclose (fh);
 563
 564   return (n);
 565 } /* sn_network_t *sn_network_read_file */
 566
 567 int sn_network_write (sn_network_t *n, FILE *fh)
 568 {
 569   int i;
 570
 571   fprintf (fh, "Inputs: %i\n", n->inputs_num);
 572   fprintf (fh, "\n");
 573
 574   for (i = 0; i < n->stages_num; i++)
 575     sn_stage_write (n->stages[i], fh);
 576
 577   return (0);
 578 } /* int sn_network_write */
 579
 580 int sn_network_write_file (sn_network_t *n, const char *file)
 581 {
 582   int status;
 583   FILE *fh;
 584
 585   fh = fopen (file, "w");
 586   if (fh == NULL)
 587     return (-1);
 588
 589   status = sn_network_write (n, fh);
 590
 591   fclose (fh);
 592
 593   return (status);
 594 } /* int sn_network_write_file */
 595
 596 /* vim: set shiftwidth=2 softtabstop=2 : */