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