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