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