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