src/sn_network.c

   1 /**
   2  * libsortnetwork - src/sn_network.c
   3  * Copyright (C) 2008-2010  Florian octo Forster
   4  *
   5  * This library is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU Lesser General Public License as published by
   7  * the Free Software Foundation; either version 2.1 of the License, or (at
   8  * your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12  * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
  13  * for more details.
  14  *
  15  * You should have received a copy of the GNU Lesser General Public License
  16  * along with this library; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  18  *
  19  * Authors:
  20  *   Florian octo Forster <ff at octo.it>
  21  **/
  22
  23 #ifndef _ISOC99_SOURCE
  24 # define _ISOC99_SOURCE
  25 #endif
  26 #ifndef _POSIX_C_SOURCE
  27 # define _POSIX_C_SOURCE 200112L
  28 #endif
  29
  30 #if 0
  31 # define DPRINTF(...) fprintf (stderr, "sn_network: " __VA_ARGS__)
  32 #else
  33 # define DPRINTF(...) /**/
  34 #endif
  35
  36 #include <stdlib.h>
  37 #include <stdio.h>
  38 #include <string.h>
  39 #include <strings.h>
  40 #include <ctype.h>
  41 #include <assert.h>
  42 #include <errno.h>
  43
  44 #include "sn_network.h"
  45 #include "sn_random.h"
  46
  47 sn_network_t *sn_network_create (int inputs_num) /* {{{ */
  48 {
  49   sn_network_t *n;
  50
  51   n = (sn_network_t *) malloc (sizeof (sn_network_t));
  52   if (n == NULL)
  53     return (NULL);
  54   memset (n, '\0', sizeof (sn_network_t));
  55
  56   n->inputs_num = inputs_num;
  57
  58   return (n);
  59 } /* }}} sn_network_t *sn_network_create */
  60
  61 void sn_network_destroy (sn_network_t *n) /* {{{ */
  62 {
  63   if (n == NULL)
  64     return;
  65
  66   if (n->stages != NULL)
  67   {
  68     int i;
  69     for (i = 0; i < n->stages_num; i++)
  70     {
  71       sn_stage_destroy (n->stages[i]);
  72       n->stages[i] = NULL;
  73     }
  74     free (n->stages);
  75     n->stages = NULL;
  76   }
  77
  78   free (n);
  79 } /* }}} void sn_network_destroy */
  80
  81 sn_network_t *sn_network_create_odd_even_mergesort (int inputs_num) /* {{{ */
  82 {
  83   sn_network_t *n;
  84
  85   n = sn_network_create (inputs_num);
  86
  87   assert (inputs_num > 0);
  88   if (inputs_num == 1)
  89   {
  90     return (n);
  91   }
  92   if (inputs_num == 2)
  93   {
  94     sn_stage_t *s;
  95     sn_comparator_t c;
  96
  97     c.min = 0;
  98     c.max = 1;
  99
 100     s = sn_stage_create (/* depth = */ 0);
 101     sn_stage_comparator_add (s, &c);
 102     sn_network_stage_add (n, s);
 103
 104     return (n);
 105   }
 106   else
 107   {
 108     sn_network_t *n_left;
 109     sn_network_t *n_right;
 110     int inputs_left;
 111     int inputs_right;
 112
 113     inputs_left = inputs_num / 2;
 114     inputs_right = inputs_num - inputs_left;
 115
 116     n_left = sn_network_create_odd_even_mergesort (inputs_left);
 117     if (n_left == NULL)
 118       return (NULL);
 119
 120     n_right = sn_network_create_odd_even_mergesort (inputs_right);
 121     if (n_right == NULL)
 122     {
 123       sn_network_destroy (n_left);
 124       return (NULL);
 125     }
 126
 127     n = sn_network_combine_odd_even_merge (n_left, n_right);
 128
 129     sn_network_destroy (n_left);
 130     sn_network_destroy (n_right);
 131
 132     if (n != NULL)
 133       sn_network_compress (n);
 134
 135     return (n);
 136   }
 137 } /* }}} sn_network_t *sn_network_create_odd_even_mergesort */
 138
 139 static int sn_network_create_pairwise_internal (sn_network_t *n, /* {{{ */
 140     int *inputs, int inputs_num)
 141 {
 142   int i;
 143   int inputs_copy[inputs_num];
 144   int m;
 145
 146   for (i = 1; i < inputs_num; i += 2)
 147   {
 148     sn_comparator_t *c = sn_comparator_create (inputs[i-1], inputs[i]);
 149     sn_network_comparator_add (n, c);
 150     sn_comparator_destroy (c);
 151   }
 152
 153   if (inputs_num <= 2)
 154     return (0);
 155
 156   /* Sort "pairs" recursively. Like with odd-even mergesort, odd and even lines
 157    * are handled recursively and later reunited. */
 158   for (i = 0; i < inputs_num; i += 2)
 159     inputs_copy[(int) (i / 2)] = inputs[i];
 160   /* Recursive call #1 with first set of lines */
 161   sn_network_create_pairwise_internal (n, inputs_copy,
 162       (int) ((inputs_num + 1) / 2));
 163
 164   for (i = 1; i < inputs_num; i += 2)
 165     inputs_copy[(int) (i / 2)] = inputs[i];
 166   /* Recursive call #2 with second set of lines */
 167   sn_network_create_pairwise_internal (n, inputs_copy,
 168       (int) (inputs_num/ 2));
 169
 170   /* m is the "amplitude" of the sorted pairs. This is a bit tricky to read due
 171    * to different indices being used in the paper, unfortunately. */
 172   m = inputs_num / 2;
 173   while (m > 1)
 174   {
 175     for (i = 1; (i + (m - 1)) < inputs_num; i += 2)
 176     {
 177       int left = i;
 178       int right = i + (m - 1);
 179       sn_comparator_t *c;
 180
 181       assert (left < right);
 182       c = sn_comparator_create (inputs[left], inputs[right]);
 183       sn_network_comparator_add (n, c);
 184       sn_comparator_destroy (c);
 185     }
 186
 187     m = m / 2;
 188   } /* while (m > 1) */
 189
 190   return (0);
 191 } /* }}} int sn_network_create_pairwise_internal */
 192
 193 sn_network_t *sn_network_create_pairwise (int inputs_num) /* {{{ */
 194 {
 195   sn_network_t *n = sn_network_create (inputs_num);
 196   int inputs[inputs_num];
 197   int i;
 198
 199   if (n == NULL)
 200     return (NULL);
 201
 202   for (i = 0; i < inputs_num; i++)
 203     inputs[i] = i;
 204
 205   sn_network_create_pairwise_internal (n, inputs, inputs_num);
 206   sn_network_compress (n);
 207
 208   return (n);
 209 } /* }}} sn_network_t *sn_network_create_pairwise */
 210
 211 int sn_network_network_add (sn_network_t *n, sn_network_t *other) /* {{{ */
 212 {
 213   int stages_num;
 214   sn_stage_t **tmp;
 215
 216   if ((n == NULL) || (other == NULL))
 217     return (EINVAL);
 218
 219   stages_num = n->stages_num + other->stages_num;
 220   if (stages_num <= n->stages_num)
 221     return (EINVAL);
 222
 223   tmp = realloc (n->stages, sizeof (*n->stages) * stages_num);
 224   if (tmp == NULL)
 225     return (ENOMEM);
 226   n->stages = tmp;
 227
 228   memcpy (n->stages + n->stages_num, other->stages,
 229       sizeof (*other->stages) * other->stages_num);
 230   n->stages_num = stages_num;
 231
 232   free (other->stages);
 233   free (other);
 234
 235   return (0);
 236 } /* }}} int sn_network_network_add */
 237
 238 int sn_network_stage_add (sn_network_t *n, sn_stage_t *s) /* {{{ */
 239 {
 240   sn_stage_t **temp;
 241
 242   if ((n == NULL) || (s == NULL))
 243     return (EINVAL);
 244
 245   temp = (sn_stage_t **) realloc (n->stages, (n->stages_num + 1)
 246       * sizeof (sn_stage_t *));
 247   if (temp == NULL)
 248     return (-1);
 249
 250   n->stages = temp;
 251   SN_STAGE_DEPTH (s) = n->stages_num;
 252   n->stages[n->stages_num] = s;
 253   n->stages_num++;
 254
 255   return (0);
 256 } /* }}} int sn_network_stage_add */
 257
 258 int sn_network_stage_remove (sn_network_t *n, int s_num) /* {{{ */
 259 {
 260   int nmemb = n->stages_num - (s_num + 1);
 261   sn_stage_t **temp;
 262
 263   if ((n == NULL) || (s_num >= n->stages_num))
 264     return (EINVAL);
 265
 266   sn_stage_destroy (n->stages[s_num]);
 267   n->stages[s_num] = NULL;
 268
 269   if (nmemb > 0)
 270   {
 271     memmove (n->stages + s_num, n->stages + (s_num + 1),
 272         nmemb * sizeof (sn_stage_t *));
 273     n->stages[n->stages_num - 1] = NULL;
 274   }
 275   n->stages_num--;
 276
 277   /* Free the unused memory */
 278   if (n->stages_num == 0)
 279   {
 280     free (n->stages);
 281     n->stages = NULL;
 282   }
 283   else
 284   {
 285     temp = (sn_stage_t **) realloc (n->stages,
 286         n->stages_num * sizeof (sn_stage_t *));
 287     if (temp == NULL)
 288       return (-1);
 289     n->stages = temp;
 290   }
 291
 292   return (0);
 293 } /* }}} int sn_network_stage_remove */
 294
 295 sn_network_t *sn_network_clone (const sn_network_t *n) /* {{{ */
 296 {
 297   sn_network_t *n_copy;
 298   int i;
 299
 300   n_copy = sn_network_create (n->inputs_num);
 301   if (n_copy == NULL)
 302     return (NULL);
 303
 304   for (i = 0; i < n->stages_num; i++)
 305   {
 306     sn_stage_t *s;
 307     int status;
 308
 309     s = sn_stage_clone (n->stages[i]);
 310     if (s == NULL)
 311       break;
 312
 313     status = sn_network_stage_add (n_copy, s);
 314     if (status != 0)
 315       break;
 316   }
 317
 318   if (i < n->stages_num)
 319   {
 320     sn_network_destroy (n_copy);
 321     return (NULL);
 322   }
 323
 324   return (n_copy);
 325 } /* }}} sn_network_t *sn_network_clone */
 326
 327 int sn_network_comparator_add (sn_network_t *n, /* {{{ */
 328     const sn_comparator_t *c)
 329 {
 330   sn_stage_t *s;
 331
 332   if ((n == NULL) || (c == NULL))
 333     return (EINVAL);
 334
 335   if (n->stages_num > 0)
 336   {
 337     s = n->stages[n->stages_num - 1];
 338
 339     if (sn_stage_comparator_check_conflict (s, c) == 0)
 340     {
 341       sn_stage_comparator_add (s, c);
 342       return (0);
 343     }
 344   }
 345
 346   s = sn_stage_create (n->stages_num);
 347   sn_stage_comparator_add (s, c);
 348   sn_network_stage_add (n, s);
 349
 350   return (0);
 351 } /* }}} int sn_network_comparator_add */
 352
 353 int sn_network_get_comparator_num (const sn_network_t *n) /* {{{ */
 354 {
 355   int num;
 356   int i;
 357
 358   if (n == NULL)
 359     return (-1);
 360
 361   num = 0;
 362   for (i = 0; i < n->stages_num; i++)
 363     num += n->stages[i]->comparators_num;
 364
 365   return (num);
 366 } /* }}} int sn_network_get_comparator_num */
 367
 368 int sn_network_show (sn_network_t *n) /* {{{ */
 369 {
 370   int i;
 371
 372   for (i = 0; i < n->stages_num; i++)
 373     sn_stage_show (n->stages[i]);
 374
 375   return (0);
 376 } /* }}} int sn_network_show */
 377
 378 int sn_network_invert (sn_network_t *n) /* {{{ */
 379 {
 380   int i;
 381
 382   if (n == NULL)
 383     return (EINVAL);
 384
 385   for (i = 0; i < n->stages_num; i++)
 386     sn_stage_invert (n->stages[i]);
 387
 388   return (0);
 389 } /* }}} int sn_network_invert */
 390
 391 int sn_network_shift (sn_network_t *n, int sw) /* {{{ */
 392 {
 393   int i;
 394
 395   if ((n == NULL) || (sw < 0))
 396     return (EINVAL);
 397
 398   if (sw == 0)
 399     return (0);
 400
 401   for (i = 0; i < n->stages_num; i++)
 402     sn_stage_shift (n->stages[i], sw, SN_NETWORK_INPUT_NUM (n));
 403
 404   return (0);
 405 } /* }}} int sn_network_shift */
 406
 407 int sn_network_compress (sn_network_t *n) /* {{{ */
 408 {
 409   int i;
 410   int j;
 411   int k;
 412
 413   for (i = 1; i < n->stages_num; i++)
 414   {
 415     sn_stage_t *s;
 416
 417     s = n->stages[i];
 418
 419     for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
 420     {
 421       sn_comparator_t *c = SN_STAGE_COMP_GET (s, j);
 422       int move_to = i;
 423
 424       for (k = i - 1; k >= 0; k--)
 425       {
 426         int conflict;
 427
 428         conflict = sn_stage_comparator_check_conflict (n->stages[k], c);
 429         if (conflict == 0)
 430         {
 431           move_to = k;
 432           continue;
 433         }
 434
 435         if (conflict == 2)
 436           move_to = -1;
 437         break;
 438       }
 439
 440       if (move_to < i)
 441       {
 442         if (move_to >= 0)
 443           sn_stage_comparator_add (n->stages[move_to], c);
 444         sn_stage_comparator_remove (s, j);
 445         j--;
 446       }
 447     }
 448   }
 449
 450   while ((n->stages_num > 0)
 451       && (SN_STAGE_COMP_NUM (n->stages[n->stages_num - 1]) == 0))
 452     sn_network_stage_remove (n, n->stages_num - 1);
 453
 454   return (0);
 455 } /* }}} int sn_network_compress */
 456
 457 int sn_network_normalize (sn_network_t *n) /* {{{ */
 458 {
 459   int i;
 460
 461   for (i = 0; i < n->stages_num; i++)
 462   {
 463     sn_stage_t *s;
 464     int j;
 465
 466     s = n->stages[i];
 467
 468     for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
 469     {
 470       sn_comparator_t *c;
 471       int min;
 472       int max;
 473
 474       c = SN_STAGE_COMP_GET (s, j);
 475
 476       min = c->min;
 477       max = c->max;
 478
 479       if (min > max)
 480       {
 481         int k;
 482
 483         for (k = i; k < n->stages_num; k++)
 484           sn_stage_swap (n->stages[k], min, max);
 485
 486         i = -1;
 487         break; /* for (j) */
 488       }
 489     } /* for (j = 0 .. #comparators) */
 490   } /* for (i = n->stages_num - 1 .. 0) */
 491
 492   return (0);
 493 } /* }}} int sn_network_normalize */
 494
 495 int sn_network_remove_input (sn_network_t *n, int input) /* {{{ */
 496 {
 497   int i;
 498
 499   if ((n == NULL) || (input < 0) || (input >= n->inputs_num))
 500     return (EINVAL);
 501
 502   for (i = 0; i < n->stages_num; i++)
 503     sn_stage_remove_input (n->stages[i], input);
 504
 505   n->inputs_num--;
 506
 507   return (0);
 508 } /* }}} int sn_network_remove_input */
 509
 510 int sn_network_cut_at (sn_network_t *n, int input, /* {{{ */
 511     enum sn_network_cut_dir_e dir)
 512 {
 513   int i;
 514   int position = input;
 515
 516   for (i = 0; i < n->stages_num; i++)
 517   {
 518     sn_stage_t *s;
 519     int new_position;
 520
 521     s = n->stages[i];
 522     new_position = sn_stage_cut_at (s, position, dir);
 523
 524     if (position != new_position)
 525     {
 526       int j;
 527
 528       for (j = 0; j < i; j++)
 529         sn_stage_swap (n->stages[j], position, new_position);
 530     }
 531
 532     position = new_position;
 533   }
 534
 535   assert (((dir == DIR_MIN) && (position == 0))
 536       || ((dir == DIR_MAX) && (position == (n->inputs_num - 1))));
 537
 538   sn_network_remove_input (n, position);
 539
 540   return (0);
 541 } /* }}} int sn_network_cut_at */
 542
 543 int sn_network_cut (sn_network_t *n, int *mask) /* {{{ */
 544 {
 545   int inputs_num;
 546   int i;
 547
 548   for (i = 0; i < n->stages_num; i++)
 549   {
 550     sn_stage_t *s = n->stages[i];
 551
 552     sn_stage_cut (s, mask, n->stages);
 553   }
 554
 555   /* Use a copy of this member since it will be updated by
 556    * sn_network_remove_input(). */
 557   inputs_num = n->inputs_num;
 558   for (i = 0; i < inputs_num; i++)
 559   {
 560     if (mask[i] < 0)
 561       sn_network_remove_input (n, 0);
 562     else if (mask[i] > 0)
 563       sn_network_remove_input (n, n->inputs_num - 1);
 564   }
 565
 566   return (0);
 567 } /* }}} int sn_network_cut */
 568
 569 /* sn_network_concatenate
 570  *
 571  * `Glues' two networks together, resulting in a comparator network with twice
 572  * as many inputs but one that doesn't really sort anymore. It produces a
 573  * bitonic sequence, though, that can be used by the mergers below. */
 574 static sn_network_t *sn_network_concatenate (sn_network_t *n0, /* {{{ */
 575     sn_network_t *n1)
 576 {
 577   sn_network_t *n;
 578   int stages_num;
 579   int i;
 580   int j;
 581
 582   stages_num = (n0->stages_num > n1->stages_num)
 583     ? n0->stages_num
 584     : n1->stages_num;
 585
 586   n = sn_network_create (n0->inputs_num + n1->inputs_num);
 587   if (n == NULL)
 588     return (NULL);
 589
 590   for (i = 0; i < stages_num; i++)
 591   {
 592     sn_stage_t *s = sn_stage_create (i);
 593
 594     if (i < n0->stages_num)
 595       for (j = 0; j < SN_STAGE_COMP_NUM (n0->stages[i]); j++)
 596       {
 597         sn_comparator_t *c = SN_STAGE_COMP_GET (n0->stages[i], j);
 598         sn_stage_comparator_add (s, c);
 599       }
 600
 601     if (i < n1->stages_num)
 602       for (j = 0; j < SN_STAGE_COMP_NUM (n1->stages[i]); j++)
 603       {
 604         sn_comparator_t *c_orig = SN_STAGE_COMP_GET (n1->stages[i], j);
 605         sn_comparator_t  c_copy;
 606
 607         SN_COMP_MIN(&c_copy) = SN_COMP_MIN(c_orig) + n0->inputs_num;
 608         SN_COMP_MAX(&c_copy) = SN_COMP_MAX(c_orig) + n0->inputs_num;
 609
 610         sn_stage_comparator_add (s, &c_copy);
 611       }
 612
 613     sn_network_stage_add (n, s);
 614   }
 615
 616   return (n);
 617 } /* }}} sn_network_t *sn_network_concatenate */
 618
 619 static int sn_network_add_bitonic_merger_recursive (sn_network_t *n, /* {{{ */
 620     int low, int num)
 621 {
 622   sn_stage_t *s;
 623   int m;
 624   int i;
 625
 626   if (num == 1)
 627     return (0);
 628
 629   s = sn_stage_create (n->stages_num);
 630   if (s == NULL)
 631     return (-1);
 632
 633   m = num / 2;
 634
 635   for (i = low; i < (low + m); i++)
 636   {
 637     sn_comparator_t c;
 638
 639     c.min = i;
 640     c.max = i + m;
 641
 642     sn_stage_comparator_add (s, &c);
 643   }
 644
 645   sn_network_stage_add (n, s);
 646
 647   sn_network_add_bitonic_merger_recursive (n, low, m);
 648   sn_network_add_bitonic_merger_recursive (n, low + m, m);
 649
 650   return (0);
 651 } /* }}} int sn_network_add_bitonic_merger_recursive */
 652
 653 static int sn_network_add_bitonic_merger (sn_network_t *n) /* {{{ */
 654 {
 655 #if 0
 656   sn_stage_t *s;
 657   int m;
 658   int i;
 659
 660   s = sn_stage_create (n->stages_num);
 661   if (s == NULL)
 662     return (-1);
 663
 664   m = n->inputs_num / 2;
 665
 666   for (i = 0; i < m; i++)
 667   {
 668     sn_comparator_t c;
 669
 670     c.min = i;
 671     c.max = n->inputs_num - (i + 1);
 672
 673     sn_stage_comparator_add (s, &c);
 674   }
 675
 676   sn_network_stage_add (n, s);
 677
 678   sn_network_add_bitonic_merger_recursive (n, 0, m);
 679   sn_network_add_bitonic_merger_recursive (n, m, m);
 680 #else
 681   sn_network_add_bitonic_merger_recursive (n, 0, SN_NETWORK_INPUT_NUM (n));
 682 #endif
 683
 684   return (0);
 685 } /* }}} int sn_network_add_bitonic_merger */
 686
 687 static int sn_network_add_odd_even_merger (sn_network_t *n, /* {{{ */
 688     int *indizes_left, int indizes_left_num,
 689     int *indizes_right, int indizes_right_num)
 690 {
 691   int tmp_left[indizes_left_num];
 692   int tmp_left_num;
 693   int tmp_right[indizes_left_num];
 694   int tmp_right_num;
 695   int max_index;
 696   sn_stage_t *s;
 697   int i;
 698
 699   if ((indizes_left_num == 0) || (indizes_right_num == 0))
 700   {
 701     return (0);
 702   }
 703   else if ((indizes_left_num == 1) && (indizes_right_num == 1))
 704   {
 705     sn_comparator_t c;
 706     sn_stage_t *s;
 707
 708     c.min = *indizes_left;
 709     c.max = *indizes_right;
 710
 711     s = sn_stage_create (n->stages_num);
 712     if (s == NULL)
 713       return (-1);
 714
 715     sn_stage_comparator_add (s, &c);
 716     sn_network_stage_add (n, s);
 717
 718     return (0);
 719   }
 720
 721   /* Merge odd sequences */
 722   tmp_left_num = (indizes_left_num + 1) / 2;
 723   for (i = 0; i < tmp_left_num; i++)
 724     tmp_left[i] = indizes_left[2 * i];
 725
 726   tmp_right_num = (indizes_right_num + 1) / 2;
 727   for (i = 0; i < tmp_right_num; i++)
 728     tmp_right[i] = indizes_right[2 * i];
 729
 730   sn_network_add_odd_even_merger (n,
 731       tmp_left, tmp_left_num,
 732       tmp_right, tmp_right_num);
 733
 734   /* Merge even sequences */
 735   tmp_left_num = indizes_left_num / 2;
 736   for (i = 0; i < tmp_left_num; i++)
 737     tmp_left[i] = indizes_left[(2 * i) + 1];
 738
 739   tmp_right_num = indizes_right_num / 2;
 740   for (i = 0; i < tmp_right_num; i++)
 741     tmp_right[i] = indizes_right[(2 * i) + 1];
 742
 743   sn_network_add_odd_even_merger (n,
 744       tmp_left, tmp_left_num,
 745       tmp_right, tmp_right_num);
 746
 747   /* Apply ``comparison-interchange'' operations. */
 748   s = sn_stage_create (n->stages_num);
 749
 750   max_index = indizes_left_num + indizes_right_num;
 751   if ((max_index % 2) == 0)
 752     max_index -= 3;
 753   else
 754     max_index -= 2;
 755
 756   for (i = 1; i <= max_index; i += 2)
 757   {
 758     sn_comparator_t c;
 759
 760     if (i < indizes_left_num)
 761       c.min = indizes_left[i];
 762     else
 763       c.min = indizes_right[i - indizes_left_num];
 764
 765     if ((i + 1) < indizes_left_num)
 766       c.max = indizes_left[i + 1];
 767     else
 768       c.max = indizes_right[i + 1 - indizes_left_num];
 769
 770     sn_stage_comparator_add (s, &c);
 771   }
 772
 773   sn_network_stage_add (n, s);
 774
 775   return (0);
 776 } /* }}} int sn_network_add_odd_even_merger */
 777
 778 static sn_network_t *sn_network_combine_bitonic_shift (sn_network_t *n0, /* {{{ */
 779     sn_network_t *n1, int do_shift)
 780 {
 781   sn_network_t *n;
 782   sn_network_t *n1_clone;
 783   int shift;
 784
 785   n1_clone = sn_network_clone (n1);
 786   if (n1_clone == NULL)
 787     return (NULL);
 788
 789   sn_network_invert (n1_clone);
 790
 791   n = sn_network_concatenate (n0, n1_clone);
 792   if (n == NULL)
 793     return (NULL);
 794
 795   sn_network_destroy (n1_clone);
 796
 797   if (do_shift)
 798     shift = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (n) - 1);
 799   else
 800     shift = 0;
 801
 802   if (shift > 0)
 803   {
 804     DPRINTF ("sn_network_combine_bitonic_shift: Shifting by %i.\n", shift);
 805     sn_network_shift (n, shift);
 806   }
 807
 808   sn_network_add_bitonic_merger (n);
 809
 810   return (n);
 811 } /* }}} sn_network_t *sn_network_combine_bitonic_shift */
 812
 813 sn_network_t *sn_network_combine_bitonic_merge (sn_network_t *n0, /* {{{ */
 814     sn_network_t *n1)
 815 {
 816   return (sn_network_combine_bitonic_shift (n0, n1, /* do_shift = */ 0));
 817 } /* }}} sn_network_t *sn_network_combine_bitonic_merge */
 818
 819 sn_network_t *sn_network_combine_odd_even_merge (sn_network_t *n0, /* {{{ */
 820     sn_network_t *n1)
 821 {
 822   sn_network_t *n;
 823   int indizes_left[n0->inputs_num];
 824   int indizes_left_num;
 825   int indizes_right[n1->inputs_num];
 826   int indizes_right_num;
 827   int status;
 828   int i;
 829
 830   indizes_left_num = n0->inputs_num;
 831   indizes_right_num = n1->inputs_num;
 832   for (i = 0; i < indizes_left_num; i++)
 833     indizes_left[i] = i;
 834   for (i = 0; i < indizes_right_num; i++)
 835     indizes_right[i] = indizes_left_num + i;
 836
 837   n = sn_network_concatenate (n0, n1);
 838   if (n == NULL)
 839     return (NULL);
 840
 841   status = sn_network_add_odd_even_merger (n,
 842       indizes_left, indizes_left_num,
 843       indizes_right, indizes_right_num);
 844   if (status != 0)
 845   {
 846     sn_network_destroy (n);
 847     return (NULL);
 848   }
 849
 850   sn_network_compress (n);
 851   return (n);
 852 } /* }}} sn_network_t *sn_network_combine_odd_even_merge */
 853
 854 sn_network_t *sn_network_combine (sn_network_t *n0, /* {{{ */
 855     sn_network_t *n1)
 856 {
 857   return (sn_network_combine_odd_even_merge (n0, n1));
 858 } /* }}} sn_network_t *sn_network_combine */
 859
 860 int sn_network_sort (sn_network_t *n, int *values) /* {{{ */
 861 {
 862   int status;
 863   int i;
 864
 865   status = 0;
 866   for (i = 0; i < n->stages_num; i++)
 867   {
 868     status = sn_stage_sort (n->stages[i], values);
 869     if (status != 0)
 870       return (status);
 871   }
 872
 873   return (status);
 874 } /* }}} int sn_network_sort */
 875
 876 int sn_network_brute_force_check (sn_network_t *n) /* {{{ */
 877 {
 878   int test_pattern[n->inputs_num];
 879   int values[n->inputs_num];
 880   int status;
 881   int i;
 882
 883   memset (test_pattern, 0, sizeof (test_pattern));
 884   while (42)
 885   {
 886     int previous;
 887     int overflow;
 888
 889     /* Copy the current pattern and let the network sort it */
 890     memcpy (values, test_pattern, sizeof (values));
 891     status = sn_network_sort (n, values);
 892     if (status != 0)
 893       return (status);
 894
 895     /* Check if the array is now sorted. */
 896     previous = values[0];
 897     for (i = 1; i < n->inputs_num; i++)
 898     {
 899       if (previous > values[i])
 900         return (1);
 901       previous = values[i];
 902     }
 903
 904     /* Generate the next test pattern */
 905     overflow = 1;
 906     for (i = 0; i < n->inputs_num; i++)
 907     {
 908       if (test_pattern[i] == 0)
 909       {
 910         test_pattern[i] = 1;
 911         overflow = 0;
 912         break;
 913       }
 914       else
 915       {
 916         test_pattern[i] = 0;
 917         overflow = 1;
 918       }
 919     }
 920
 921     /* Break out of the while loop if we tested all possible patterns */
 922     if (overflow == 1)
 923       break;
 924   } /* while (42) */
 925
 926   /* All tests successfull */
 927   return (0);
 928 } /* }}} int sn_network_brute_force_check */
 929
 930 sn_network_t *sn_network_read (FILE *fh) /* {{{ */
 931 {
 932   sn_network_t *n;
 933   char buffer[64];
 934
 935   int opt_inputs = 0;
 936
 937   while (fgets (buffer, sizeof (buffer), fh) != NULL)
 938   {
 939     char *str_key = buffer;
 940     char *str_value = NULL;
 941     int   buffer_len = strlen (buffer);
 942
 943     while ((buffer_len > 0) && ((buffer[buffer_len - 1] == '\n')
 944           || (buffer[buffer_len - 1] == '\r')))
 945     {
 946       buffer_len--;
 947       buffer[buffer_len] = '\0';
 948     }
 949     if (buffer_len == 0)
 950       break;
 951
 952     str_value = strchr (buffer, ':');
 953     if (str_value == NULL)
 954     {
 955       printf ("Cannot parse line: %s\n", buffer);
 956       continue;
 957     }
 958
 959     *str_value = '\0'; str_value++;
 960     while ((*str_value != '\0') && (isspace (*str_value) != 0))
 961       str_value++;
 962
 963     if (strcasecmp ("Inputs", str_key) == 0)
 964       opt_inputs = atoi (str_value);
 965     else
 966       printf ("Unknown key: %s\n", str_key);
 967   } /* while (fgets) */
 968
 969   if (opt_inputs < 2)
 970     return (NULL);
 971
 972   n = sn_network_create (opt_inputs);
 973
 974   while (42)
 975   {
 976     sn_stage_t *s;
 977
 978     s = sn_stage_read (fh);
 979     if (s == NULL)
 980       break;
 981
 982     sn_network_stage_add (n, s);
 983   }
 984
 985   if (SN_NETWORK_STAGE_NUM (n) < 1)
 986   {
 987     sn_network_destroy (n);
 988     return (NULL);
 989   }
 990
 991   return (n);
 992 } /* }}} sn_network_t *sn_network_read */
 993
 994 sn_network_t *sn_network_read_file (const char *file) /* {{{ */
 995 {
 996   sn_network_t *n;
 997   FILE *fh;
 998
 999   fh = fopen (file, "r");
1000   if (fh == NULL)
1001     return (NULL);
1002
1003   n = sn_network_read (fh);
1004
1005   fclose (fh);
1006
1007   return (n);
1008 } /* }}} sn_network_t *sn_network_read_file */
1009
1010 int sn_network_write (sn_network_t *n, FILE *fh) /* {{{ */
1011 {
1012   int i;
1013
1014   fprintf (fh, "Inputs: %i\n", n->inputs_num);
1015   fprintf (fh, "\n");
1016
1017   for (i = 0; i < n->stages_num; i++)
1018     sn_stage_write (n->stages[i], fh);
1019
1020   return (0);
1021 } /* }}} int sn_network_write */
1022
1023 int sn_network_write_file (sn_network_t *n, const char *file) /* {{{ */
1024 {
1025   int status;
1026   FILE *fh;
1027
1028   fh = fopen (file, "w");
1029   if (fh == NULL)
1030     return (-1);
1031
1032   status = sn_network_write (n, fh);
1033
1034   fclose (fh);
1035
1036   return (status);
1037 } /* }}} int sn_network_write_file */
1038
1039 int sn_network_serialize (sn_network_t *n, char **ret_buffer, /* {{{ */
1040     size_t *ret_buffer_size)
1041 {
1042   char *buffer;
1043   size_t buffer_size;
1044   int status;
1045   int i;
1046
1047   buffer = *ret_buffer;
1048   buffer_size = *ret_buffer_size;
1049
1050 #define SNPRINTF_OR_FAIL(...) \
1051   status = snprintf (buffer, buffer_size, __VA_ARGS__); \
1052   if ((status < 1) || (((size_t) status) >= buffer_size)) \
1053     return (-1); \
1054   buffer += status; \
1055   buffer_size -= status;
1056
1057   SNPRINTF_OR_FAIL ("Inputs: %i\r\n\r\n", n->inputs_num);
1058
1059   for (i = 0; i < n->stages_num; i++)
1060   {
1061     status = sn_stage_serialize (n->stages[i], &buffer, &buffer_size);
1062     if (status != 0)
1063       return (status);
1064   }
1065
1066   *ret_buffer = buffer;
1067   *ret_buffer_size = buffer_size;
1068   return (0);
1069 } /* }}} int sn_network_serialize */
1070
1071 sn_network_t *sn_network_unserialize (char *buffer, /* {{{ */
1072     size_t buffer_size)
1073 {
1074   sn_network_t *n;
1075   int opt_inputs = 0;
1076
1077   if (buffer_size == 0)
1078     return (NULL);
1079
1080   /* Read options first */
1081   while (buffer_size > 0)
1082   {
1083     char *endptr;
1084     char *str_key;
1085     char *str_value;
1086     char *line;
1087     int   line_len;
1088
1089     line = buffer;
1090     endptr = strchr (buffer, '\n');
1091     if (endptr == NULL)
1092       return (NULL);
1093
1094     *endptr = 0;
1095     endptr++;
1096     buffer = endptr;
1097     line_len = strlen (line);
1098
1099     if ((line_len > 0) && (line[line_len - 1] == '\r'))
1100     {
1101       line[line_len - 1] = 0;
1102       line_len--;
1103     }
1104
1105     if (line_len == 0)
1106       break;
1107
1108     str_key = line;
1109     str_value = strchr (line, ':');
1110     if (str_value == NULL)
1111     {
1112       printf ("Cannot parse line: %s\n", line);
1113       continue;
1114     }
1115
1116     *str_value = '\0'; str_value++;
1117     while ((*str_value != '\0') && (isspace (*str_value) != 0))
1118       str_value++;
1119
1120     if (strcasecmp ("Inputs", str_key) == 0)
1121       opt_inputs = atoi (str_value);
1122     else
1123       printf ("Unknown key: %s\n", str_key);
1124   } /* while (fgets) */
1125
1126   if (opt_inputs < 2)
1127     return (NULL);
1128
1129   n = sn_network_create (opt_inputs);
1130
1131   while (42)
1132   {
1133     sn_stage_t *s;
1134
1135     s = sn_stage_unserialize (&buffer, &buffer_size);
1136     if (s == NULL)
1137       break;
1138
1139     sn_network_stage_add (n, s);
1140   }
1141
1142   if (SN_NETWORK_STAGE_NUM (n) < 1)
1143   {
1144     sn_network_destroy (n);
1145     return (NULL);
1146   }
1147
1148   return (n);
1149 } /* }}} sn_network_t *sn_network_unserialize */
1150
1151 /* vim: set sw=2 sts=2 et fdm=marker : */