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