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 (sn_network_t *n) /* {{{ */
 427 {
 428   int i;
 429
 430   for (i = 0; i < n->stages_num; i++)
 431     sn_stage_show (n->stages[i]);
 432
 433   return (0);
 434 } /* }}} int sn_network_show */
 435
 436 int sn_network_invert (sn_network_t *n) /* {{{ */
 437 {
 438   int i;
 439
 440   if (n == NULL)
 441     return (EINVAL);
 442
 443   for (i = 0; i < n->stages_num; i++)
 444     sn_stage_invert (n->stages[i]);
 445
 446   return (0);
 447 } /* }}} int sn_network_invert */
 448
 449 int sn_network_shift (sn_network_t *n, int sw) /* {{{ */
 450 {
 451   int i;
 452
 453   if ((n == NULL) || (sw < 0))
 454     return (EINVAL);
 455
 456   if (sw == 0)
 457     return (0);
 458
 459   for (i = 0; i < n->stages_num; i++)
 460     sn_stage_shift (n->stages[i], sw, SN_NETWORK_INPUT_NUM (n));
 461
 462   return (0);
 463 } /* }}} int sn_network_shift */
 464
 465 int sn_network_compress (sn_network_t *n) /* {{{ */
 466 {
 467   int i;
 468   int j;
 469   int k;
 470
 471   for (i = 1; i < n->stages_num; i++)
 472   {
 473     sn_stage_t *s;
 474
 475     s = n->stages[i];
 476
 477     for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
 478     {
 479       sn_comparator_t *c = SN_STAGE_COMP_GET (s, j);
 480       int move_to = i;
 481
 482       for (k = i - 1; k >= 0; k--)
 483       {
 484         int conflict;
 485
 486         conflict = sn_stage_comparator_check_conflict (n->stages[k], c);
 487         if (conflict == 0)
 488         {
 489           move_to = k;
 490           continue;
 491         }
 492
 493         if (conflict == 2)
 494           move_to = -1;
 495         break;
 496       }
 497
 498       if (move_to < i)
 499       {
 500         if (move_to >= 0)
 501           sn_stage_comparator_add (n->stages[move_to], c);
 502         sn_stage_comparator_remove (s, j);
 503         j--;
 504       }
 505     }
 506   }
 507
 508   while ((n->stages_num > 0)
 509       && (SN_STAGE_COMP_NUM (n->stages[n->stages_num - 1]) == 0))
 510     sn_network_stage_remove (n, n->stages_num - 1);
 511
 512   return (0);
 513 } /* }}} int sn_network_compress */
 514
 515 int sn_network_normalize (sn_network_t *n) /* {{{ */
 516 {
 517   int i;
 518
 519   for (i = 0; i < n->stages_num; i++)
 520   {
 521     sn_stage_t *s;
 522     int j;
 523
 524     s = n->stages[i];
 525
 526     for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
 527     {
 528       sn_comparator_t *c;
 529       int min;
 530       int max;
 531
 532       c = SN_STAGE_COMP_GET (s, j);
 533
 534       min = c->min;
 535       max = c->max;
 536
 537       if (min > max)
 538       {
 539         int k;
 540
 541         for (k = i; k < n->stages_num; k++)
 542           sn_stage_swap (n->stages[k], min, max);
 543
 544         i = -1;
 545         break; /* for (j) */
 546       }
 547     } /* for (j = 0 .. #comparators) */
 548   } /* for (i = n->stages_num - 1 .. 0) */
 549
 550   return (0);
 551 } /* }}} int sn_network_normalize */
 552
 553 int sn_network_remove_input (sn_network_t *n, int input) /* {{{ */
 554 {
 555   int i;
 556
 557   if ((n == NULL) || (input < 0) || (input >= n->inputs_num))
 558     return (EINVAL);
 559
 560   for (i = 0; i < n->stages_num; i++)
 561     sn_stage_remove_input (n->stages[i], input);
 562
 563   n->inputs_num--;
 564
 565   return (0);
 566 } /* }}} int sn_network_remove_input */
 567
 568 int sn_network_cut_at (sn_network_t *n, int input, /* {{{ */
 569     enum sn_network_cut_dir_e dir)
 570 {
 571   int i;
 572   int position = input;
 573
 574   for (i = 0; i < n->stages_num; i++)
 575   {
 576     sn_stage_t *s;
 577     int new_position;
 578
 579     s = n->stages[i];
 580     new_position = sn_stage_cut_at (s, position, dir);
 581
 582     if (position != new_position)
 583     {
 584       int j;
 585
 586       for (j = 0; j < i; j++)
 587         sn_stage_swap (n->stages[j], position, new_position);
 588     }
 589
 590     position = new_position;
 591   }
 592
 593   assert (((dir == DIR_MIN) && (position == 0))
 594       || ((dir == DIR_MAX) && (position == (n->inputs_num - 1))));
 595
 596   sn_network_remove_input (n, position);
 597
 598   return (0);
 599 } /* }}} int sn_network_cut_at */
 600
 601 int sn_network_cut (sn_network_t *n, int *mask) /* {{{ */
 602 {
 603   int inputs_num;
 604   int i;
 605
 606   for (i = 0; i < n->stages_num; i++)
 607   {
 608     sn_stage_t *s = n->stages[i];
 609
 610     sn_stage_cut (s, mask, n->stages);
 611   }
 612
 613   /* Use a copy of this member since it will be updated by
 614    * sn_network_remove_input(). */
 615   inputs_num = n->inputs_num;
 616   for (i = 0; i < inputs_num; i++)
 617   {
 618     if (mask[i] < 0)
 619       sn_network_remove_input (n, 0);
 620     else if (mask[i] > 0)
 621       sn_network_remove_input (n, n->inputs_num - 1);
 622   }
 623
 624   return (0);
 625 } /* }}} int sn_network_cut */
 626
 627 /* sn_network_concatenate
 628  *
 629  * `Glues' two networks together, resulting in a comparator network with twice
 630  * as many inputs but one that doesn't really sort anymore. It produces a
 631  * bitonic sequence, though, that can be used by the mergers below. */
 632 static sn_network_t *sn_network_concatenate (sn_network_t *n0, /* {{{ */
 633     sn_network_t *n1)
 634 {
 635   sn_network_t *n;
 636   int stages_num;
 637   int i;
 638   int j;
 639
 640   stages_num = (n0->stages_num > n1->stages_num)
 641     ? n0->stages_num
 642     : n1->stages_num;
 643
 644   n = sn_network_create (n0->inputs_num + n1->inputs_num);
 645   if (n == NULL)
 646     return (NULL);
 647
 648   for (i = 0; i < stages_num; i++)
 649   {
 650     sn_stage_t *s = sn_stage_create (i);
 651
 652     if (i < n0->stages_num)
 653       for (j = 0; j < SN_STAGE_COMP_NUM (n0->stages[i]); j++)
 654       {
 655         sn_comparator_t *c = SN_STAGE_COMP_GET (n0->stages[i], j);
 656         sn_stage_comparator_add (s, c);
 657       }
 658
 659     if (i < n1->stages_num)
 660       for (j = 0; j < SN_STAGE_COMP_NUM (n1->stages[i]); j++)
 661       {
 662         sn_comparator_t *c_orig = SN_STAGE_COMP_GET (n1->stages[i], j);
 663         sn_comparator_t  c_copy;
 664
 665         SN_COMP_MIN(&c_copy) = SN_COMP_MIN(c_orig) + n0->inputs_num;
 666         SN_COMP_MAX(&c_copy) = SN_COMP_MAX(c_orig) + n0->inputs_num;
 667
 668         sn_stage_comparator_add (s, &c_copy);
 669       }
 670
 671     sn_network_stage_add (n, s);
 672   }
 673
 674   return (n);
 675 } /* }}} sn_network_t *sn_network_concatenate */
 676
 677 static int sn_network_add_bitonic_merger (sn_network_t *n, /* {{{ */
 678     int *indizes, int indizes_num)
 679 {
 680   int i;
 681
 682   if (indizes_num <= 1)
 683     return (0);
 684
 685   if (indizes_num > 2)
 686   {
 687     int even_indizes[indizes_num];
 688     int even_indizes_num;
 689     int odd_indizes[indizes_num];
 690     int odd_indizes_num;
 691
 692     even_indizes_num = (indizes_num + 1) / 2;
 693     odd_indizes_num = indizes_num / 2;
 694
 695     for (i = 0; i < even_indizes_num; i++)
 696       even_indizes[i] = indizes[2 * i];
 697     for (i = 0; i < odd_indizes_num; i++)
 698       odd_indizes[i] = indizes[(2 * i) + 1];
 699
 700     sn_network_add_bitonic_merger (n, even_indizes, even_indizes_num);
 701     sn_network_add_bitonic_merger (n, odd_indizes, odd_indizes_num);
 702   }
 703
 704   for (i = 1; i < indizes_num; i += 2)
 705   {
 706     sn_comparator_t c;
 707
 708     memset (&c, 0, sizeof (c));
 709     c.min = indizes[i - 1];
 710     c.max = indizes[i];
 711
 712     sn_network_comparator_add (n, &c);
 713   }
 714
 715   return (0);
 716 } /* }}} int sn_network_add_bitonic_merger */
 717
 718 static int sn_network_add_odd_even_merger (sn_network_t *n, /* {{{ */
 719     int *indizes_left, int indizes_left_num,
 720     int *indizes_right, int indizes_right_num)
 721 {
 722   int tmp_left[indizes_left_num];
 723   int tmp_left_num;
 724   int tmp_right[indizes_left_num];
 725   int tmp_right_num;
 726   int max_index;
 727   sn_stage_t *s;
 728   int i;
 729
 730   if ((indizes_left_num == 0) || (indizes_right_num == 0))
 731   {
 732     return (0);
 733   }
 734   else if ((indizes_left_num == 1) && (indizes_right_num == 1))
 735   {
 736     sn_comparator_t c;
 737     sn_stage_t *s;
 738
 739     c.min = *indizes_left;
 740     c.max = *indizes_right;
 741
 742     s = sn_stage_create (n->stages_num);
 743     if (s == NULL)
 744       return (-1);
 745
 746     sn_stage_comparator_add (s, &c);
 747     sn_network_stage_add (n, s);
 748
 749     return (0);
 750   }
 751
 752   /* Merge odd sequences */
 753   tmp_left_num = (indizes_left_num + 1) / 2;
 754   for (i = 0; i < tmp_left_num; i++)
 755     tmp_left[i] = indizes_left[2 * i];
 756
 757   tmp_right_num = (indizes_right_num + 1) / 2;
 758   for (i = 0; i < tmp_right_num; i++)
 759     tmp_right[i] = indizes_right[2 * i];
 760
 761   sn_network_add_odd_even_merger (n,
 762       tmp_left, tmp_left_num,
 763       tmp_right, tmp_right_num);
 764
 765   /* Merge even sequences */
 766   tmp_left_num = indizes_left_num / 2;
 767   for (i = 0; i < tmp_left_num; i++)
 768     tmp_left[i] = indizes_left[(2 * i) + 1];
 769
 770   tmp_right_num = indizes_right_num / 2;
 771   for (i = 0; i < tmp_right_num; i++)
 772     tmp_right[i] = indizes_right[(2 * i) + 1];
 773
 774   sn_network_add_odd_even_merger (n,
 775       tmp_left, tmp_left_num,
 776       tmp_right, tmp_right_num);
 777
 778   /* Apply ``comparison-interchange'' operations. */
 779   s = sn_stage_create (n->stages_num);
 780
 781   max_index = indizes_left_num + indizes_right_num;
 782   if ((max_index % 2) == 0)
 783     max_index -= 3;
 784   else
 785     max_index -= 2;
 786
 787   for (i = 1; i <= max_index; i += 2)
 788   {
 789     sn_comparator_t c;
 790
 791     if (i < indizes_left_num)
 792       c.min = indizes_left[i];
 793     else
 794       c.min = indizes_right[i - indizes_left_num];
 795
 796     if ((i + 1) < indizes_left_num)
 797       c.max = indizes_left[i + 1];
 798     else
 799       c.max = indizes_right[i + 1 - indizes_left_num];
 800
 801     sn_stage_comparator_add (s, &c);
 802   }
 803
 804   sn_network_stage_add (n, s);
 805
 806   return (0);
 807 } /* }}} int sn_network_add_odd_even_merger */
 808
 809 sn_network_t *sn_network_combine_bitonic_merge (sn_network_t *n0, /* {{{ */
 810     sn_network_t *n1)
 811 {
 812   sn_network_t *n0_clone;
 813   sn_network_t *n;
 814   int indizes_num = SN_NETWORK_INPUT_NUM (n0) + SN_NETWORK_INPUT_NUM (n1);
 815   int indizes[indizes_num];
 816   int i;
 817
 818   /* We need to invert n0, because the sequence must be
 819    * z_1 >= z_2 >= ... >= z_k <= z_{k+1} <= ... <= z_p
 820    * and NOT the other way around! Otherwise the comparators added in
 821    * sn_network_add_bitonic_merger() from comparing (z_0,z_1), (z_2,z_3), ...
 822    * to comparing ...,  (z_{n-4},z_{n-3}), (z_{n-2},z_{n-1}), i.e. bound to the
 823    * end of the list, possibly leaving z_0 uncompared. */
 824   n0_clone = sn_network_clone (n0);
 825   if (n0_clone == NULL)
 826     return (NULL);
 827   sn_network_invert (n0_clone);
 828
 829   n = sn_network_concatenate (n0_clone, n1);
 830   if (n == NULL)
 831     return (NULL);
 832   sn_network_destroy (n0_clone);
 833
 834   for (i = 0; i < indizes_num; i++)
 835     indizes[i] = i;
 836
 837   sn_network_add_bitonic_merger (n, indizes, indizes_num);
 838
 839   return (n);
 840 } /* }}} sn_network_t *sn_network_combine_bitonic_merge */
 841
 842 sn_network_t *sn_network_combine_odd_even_merge (sn_network_t *n0, /* {{{ */
 843     sn_network_t *n1)
 844 {
 845   sn_network_t *n;
 846   int indizes_left[n0->inputs_num];
 847   int indizes_left_num;
 848   int indizes_right[n1->inputs_num];
 849   int indizes_right_num;
 850   int status;
 851   int i;
 852
 853   indizes_left_num = n0->inputs_num;
 854   indizes_right_num = n1->inputs_num;
 855   for (i = 0; i < indizes_left_num; i++)
 856     indizes_left[i] = i;
 857   for (i = 0; i < indizes_right_num; i++)
 858     indizes_right[i] = indizes_left_num + i;
 859
 860   n = sn_network_concatenate (n0, n1);
 861   if (n == NULL)
 862     return (NULL);
 863
 864   status = sn_network_add_odd_even_merger (n,
 865       indizes_left, indizes_left_num,
 866       indizes_right, indizes_right_num);
 867   if (status != 0)
 868   {
 869     sn_network_destroy (n);
 870     return (NULL);
 871   }
 872
 873   sn_network_compress (n);
 874   return (n);
 875 } /* }}} sn_network_t *sn_network_combine_odd_even_merge */
 876
 877 sn_network_t *sn_network_combine (sn_network_t *n0, /* {{{ */
 878     sn_network_t *n1)
 879 {
 880   return (sn_network_combine_odd_even_merge (n0, n1));
 881 } /* }}} sn_network_t *sn_network_combine */
 882
 883 int sn_network_sort (sn_network_t *n, int *values) /* {{{ */
 884 {
 885   int status;
 886   int i;
 887
 888   status = 0;
 889   for (i = 0; i < n->stages_num; i++)
 890   {
 891     status = sn_stage_sort (n->stages[i], values);
 892     if (status != 0)
 893       return (status);
 894   }
 895
 896   return (status);
 897 } /* }}} int sn_network_sort */
 898
 899 int sn_network_brute_force_check (sn_network_t *n) /* {{{ */
 900 {
 901   int test_pattern[n->inputs_num];
 902   int values[n->inputs_num];
 903   int status;
 904   int i;
 905
 906   memset (test_pattern, 0, sizeof (test_pattern));
 907   while (42)
 908   {
 909     int previous;
 910     int overflow;
 911
 912     /* Copy the current pattern and let the network sort it */
 913     memcpy (values, test_pattern, sizeof (values));
 914     status = sn_network_sort (n, values);
 915     if (status != 0)
 916       return (status);
 917
 918     /* Check if the array is now sorted. */
 919     previous = values[0];
 920     for (i = 1; i < n->inputs_num; i++)
 921     {
 922       if (previous > values[i])
 923         return (1);
 924       previous = values[i];
 925     }
 926
 927     /* Generate the next test pattern */
 928     overflow = 1;
 929     for (i = 0; i < n->inputs_num; i++)
 930     {
 931       if (test_pattern[i] == 0)
 932       {
 933         test_pattern[i] = 1;
 934         overflow = 0;
 935         break;
 936       }
 937       else
 938       {
 939         test_pattern[i] = 0;
 940         overflow = 1;
 941       }
 942     }
 943
 944     /* Break out of the while loop if we tested all possible patterns */
 945     if (overflow == 1)
 946       break;
 947   } /* while (42) */
 948
 949   /* All tests successfull */
 950   return (0);
 951 } /* }}} int sn_network_brute_force_check */
 952
 953 sn_network_t *sn_network_read (FILE *fh) /* {{{ */
 954 {
 955   sn_network_t *n;
 956   char buffer[64];
 957
 958   int opt_inputs = 0;
 959
 960   while (fgets (buffer, sizeof (buffer), fh) != NULL)
 961   {
 962     char *str_key = buffer;
 963     char *str_value = NULL;
 964     int   buffer_len = strlen (buffer);
 965
 966     while ((buffer_len > 0) && ((buffer[buffer_len - 1] == '\n')
 967           || (buffer[buffer_len - 1] == '\r')))
 968     {
 969       buffer_len--;
 970       buffer[buffer_len] = '\0';
 971     }
 972     if (buffer_len == 0)
 973       break;
 974
 975     str_value = strchr (buffer, ':');
 976     if (str_value == NULL)
 977     {
 978       printf ("Cannot parse line: %s\n", buffer);
 979       continue;
 980     }
 981
 982     *str_value = '\0'; str_value++;
 983     while ((*str_value != '\0') && (isspace (*str_value) != 0))
 984       str_value++;
 985
 986     if (strcasecmp ("Inputs", str_key) == 0)
 987       opt_inputs = atoi (str_value);
 988     else
 989       printf ("Unknown key: %s\n", str_key);
 990   } /* while (fgets) */
 991
 992   if (opt_inputs < 2)
 993     return (NULL);
 994
 995   n = sn_network_create (opt_inputs);
 996
 997   while (42)
 998   {
 999     sn_stage_t *s;
1000
1001     s = sn_stage_read (fh);
1002     if (s == NULL)
1003       break;
1004
1005     sn_network_stage_add (n, s);
1006   }
1007
1008   if (SN_NETWORK_STAGE_NUM (n) < 1)
1009   {
1010     sn_network_destroy (n);
1011     return (NULL);
1012   }
1013
1014   return (n);
1015 } /* }}} sn_network_t *sn_network_read */
1016
1017 sn_network_t *sn_network_read_file (const char *file) /* {{{ */
1018 {
1019   sn_network_t *n;
1020   FILE *fh;
1021
1022   fh = fopen (file, "r");
1023   if (fh == NULL)
1024     return (NULL);
1025
1026   n = sn_network_read (fh);
1027
1028   fclose (fh);
1029
1030   return (n);
1031 } /* }}} sn_network_t *sn_network_read_file */
1032
1033 int sn_network_write (sn_network_t *n, FILE *fh) /* {{{ */
1034 {
1035   int i;
1036
1037   fprintf (fh, "Inputs: %i\n", n->inputs_num);
1038   fprintf (fh, "\n");
1039
1040   for (i = 0; i < n->stages_num; i++)
1041     sn_stage_write (n->stages[i], fh);
1042
1043   return (0);
1044 } /* }}} int sn_network_write */
1045
1046 int sn_network_write_file (sn_network_t *n, const char *file) /* {{{ */
1047 {
1048   int status;
1049   FILE *fh;
1050
1051   fh = fopen (file, "w");
1052   if (fh == NULL)
1053     return (-1);
1054
1055   status = sn_network_write (n, fh);
1056
1057   fclose (fh);
1058
1059   return (status);
1060 } /* }}} int sn_network_write_file */
1061
1062 int sn_network_serialize (sn_network_t *n, char **ret_buffer, /* {{{ */
1063     size_t *ret_buffer_size)
1064 {
1065   char *buffer;
1066   size_t buffer_size;
1067   int status;
1068   int i;
1069
1070   buffer = *ret_buffer;
1071   buffer_size = *ret_buffer_size;
1072
1073 #define SNPRINTF_OR_FAIL(...) \
1074   status = snprintf (buffer, buffer_size, __VA_ARGS__); \
1075   if ((status < 1) || (((size_t) status) >= buffer_size)) \
1076     return (-1); \
1077   buffer += status; \
1078   buffer_size -= status;
1079
1080   SNPRINTF_OR_FAIL ("Inputs: %i\r\n\r\n", n->inputs_num);
1081
1082   for (i = 0; i < n->stages_num; i++)
1083   {
1084     status = sn_stage_serialize (n->stages[i], &buffer, &buffer_size);
1085     if (status != 0)
1086       return (status);
1087   }
1088
1089   *ret_buffer = buffer;
1090   *ret_buffer_size = buffer_size;
1091   return (0);
1092 } /* }}} int sn_network_serialize */
1093
1094 sn_network_t *sn_network_unserialize (char *buffer, /* {{{ */
1095     size_t buffer_size)
1096 {
1097   sn_network_t *n;
1098   int opt_inputs = 0;
1099
1100   if (buffer_size == 0)
1101     return (NULL);
1102
1103   /* Read options first */
1104   while (buffer_size > 0)
1105   {
1106     char *endptr;
1107     char *str_key;
1108     char *str_value;
1109     char *line;
1110     int   line_len;
1111
1112     line = buffer;
1113     endptr = strchr (buffer, '\n');
1114     if (endptr == NULL)
1115       return (NULL);
1116
1117     *endptr = 0;
1118     endptr++;
1119     buffer = endptr;
1120     line_len = strlen (line);
1121
1122     if ((line_len > 0) && (line[line_len - 1] == '\r'))
1123     {
1124       line[line_len - 1] = 0;
1125       line_len--;
1126     }
1127
1128     if (line_len == 0)
1129       break;
1130
1131     str_key = line;
1132     str_value = strchr (line, ':');
1133     if (str_value == NULL)
1134     {
1135       printf ("Cannot parse line: %s\n", line);
1136       continue;
1137     }
1138
1139     *str_value = '\0'; str_value++;
1140     while ((*str_value != '\0') && (isspace (*str_value) != 0))
1141       str_value++;
1142
1143     if (strcasecmp ("Inputs", str_key) == 0)
1144       opt_inputs = atoi (str_value);
1145     else
1146       printf ("Unknown key: %s\n", str_key);
1147   } /* while (fgets) */
1148
1149   if (opt_inputs < 2)
1150     return (NULL);
1151
1152   n = sn_network_create (opt_inputs);
1153
1154   while (42)
1155   {
1156     sn_stage_t *s;
1157
1158     s = sn_stage_unserialize (&buffer, &buffer_size);
1159     if (s == NULL)
1160       break;
1161
1162     sn_network_stage_add (n, s);
1163   }
1164
1165   if (SN_NETWORK_STAGE_NUM (n) < 1)
1166   {
1167     sn_network_destroy (n);
1168     return (NULL);
1169   }
1170
1171   return (n);
1172 } /* }}} sn_network_t *sn_network_unserialize */
1173
1174 /* vim: set sw=2 sts=2 et fdm=marker : */