8 #include "sn_network.h"
11 sn_network_t *sn_network_create (int inputs_num)
15 n = (sn_network_t *) malloc (sizeof (sn_network_t));
18 memset (n, '\0', sizeof (sn_network_t));
20 n->inputs_num = inputs_num;
23 } /* sn_network_t *sn_network_create */
25 void sn_network_destroy (sn_network_t *n)
30 if (n->stages != NULL)
33 for (i = 0; i < n->stages_num; i++)
35 sn_stage_destroy (n->stages[i]);
43 } /* void sn_network_destroy */
45 int sn_network_stage_add (sn_network_t *n, sn_stage_t *s)
49 temp = (sn_stage_t **) realloc (n->stages, (n->stages_num + 1)
50 * sizeof (sn_stage_t *));
55 SN_STAGE_DEPTH (s) = n->stages_num;
56 n->stages[n->stages_num] = s;
60 } /* int sn_network_stage_add */
62 int sn_network_stage_remove (sn_network_t *n, int s_num)
64 int nmemb = n->stages_num - (s_num + 1);
67 assert (s_num < n->stages_num);
69 sn_stage_destroy (n->stages[s_num]);
70 n->stages[s_num] = NULL;
74 memmove (n->stages + s_num, n->stages + (s_num + 1),
75 nmemb * sizeof (sn_stage_t *));
76 n->stages[n->stages_num - 1] = NULL;
80 /* Free the unused memory */
81 if (n->stages_num == 0)
88 temp = (sn_stage_t **) realloc (n->stages,
89 n->stages_num * sizeof (sn_stage_t *));
96 } /* int sn_network_stage_remove */
98 sn_network_t *sn_network_clone (const sn_network_t *n)
100 sn_network_t *n_copy;
103 n_copy = sn_network_create (n->inputs_num);
107 for (i = 0; i < n->stages_num; i++)
112 s = sn_stage_clone (n->stages[i]);
116 status = sn_network_stage_add (n_copy, s);
121 if (i < n->stages_num)
123 sn_network_destroy (n_copy);
128 } /* sn_network_t *sn_network_clone */
130 int sn_network_show (sn_network_t *n)
134 for (i = 0; i < n->stages_num; i++)
135 sn_stage_show (n->stages[i]);
138 } /* int sn_network_show */
140 int sn_network_invert (sn_network_t *n)
144 for (i = 0; i < n->stages_num; i++)
145 sn_stage_invert (n->stages[i]);
148 } /* int sn_network_invert */
150 int sn_network_compress (sn_network_t *n)
156 for (i = 1; i < n->stages_num; i++)
162 for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
164 sn_comparator_t *c = SN_STAGE_COMP_GET (s, j);
167 for (k = i - 1; k >= 0; k--)
171 conflict = sn_stage_comparator_check_conflict (n->stages[k], c);
186 sn_stage_comparator_add (n->stages[move_to], c);
187 sn_stage_comparator_remove (s, j);
193 while ((n->stages_num > 0)
194 && (SN_STAGE_COMP_NUM (n->stages[n->stages_num - 1]) == 0))
195 sn_network_stage_remove (n, n->stages_num - 1);
198 } /* int sn_network_compress */
200 int sn_network_normalize (sn_network_t *n)
204 for (i = n->stages_num - 1; i >= 0; i--)
211 for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
217 c = SN_STAGE_COMP_GET (s, j);
226 for (k = i; k >= 0; k--)
227 sn_stage_swap (n->stages[k], min, max);
229 } /* for (j = 0 .. #comparators) */
230 } /* for (i = n->stages_num - 1 .. 0) */
233 } /* int sn_network_normalize */
235 int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir)
238 int position = input;
240 for (i = 0; i < n->stages_num; i++)
246 new_position = sn_stage_cut_at (s, position, dir);
248 if (position != new_position)
252 for (j = 0; j < i; j++)
253 sn_stage_swap (n->stages[j], position, new_position);
256 position = new_position;
259 assert (((dir == DIR_MIN) && (position == 0))
260 || ((dir == DIR_MAX) && (position == (n->inputs_num - 1))));
262 for (i = 0; i < n->stages_num; i++)
263 sn_stage_remove_input (n->stages[i], position);
268 } /* int sn_network_cut_at */
270 static int sn_network_add_bitonic_merger_recursive (sn_network_t *n,
280 s = sn_stage_create (n->stages_num);
286 for (i = low; i < (low + m); i++)
293 sn_stage_comparator_add (s, &c);
296 sn_network_stage_add (n, s);
298 sn_network_add_bitonic_merger_recursive (n, low, m);
299 sn_network_add_bitonic_merger_recursive (n, low + m, m);
302 } /* int sn_network_add_bitonic_merger_recursive */
304 static int sn_network_add_bitonic_merger (sn_network_t *n)
310 s = sn_stage_create (n->stages_num);
314 m = n->inputs_num / 2;
316 for (i = 0; i < m; i++)
321 c.max = n->inputs_num - (i + 1);
323 sn_stage_comparator_add (s, &c);
326 sn_network_stage_add (n, s);
328 sn_network_add_bitonic_merger_recursive (n, 0, m);
329 sn_network_add_bitonic_merger_recursive (n, m, m);
332 } /* int sn_network_add_bitonic_merger */
334 static int sn_network_add_odd_even_merger_recursive (sn_network_t *n,
335 int *indizes, int indizes_num)
341 int indizes_half_num;
346 indizes_half_num = indizes_num / 2;
347 indizes_half = (int *) malloc (indizes_num * sizeof (int));
348 if (indizes_half == NULL)
351 for (i = 0; i < indizes_half_num; i++)
353 indizes_half[i] = indizes[2 * i];
354 indizes_half[indizes_half_num + i] = indizes[(2 * i) + 1];
357 status = sn_network_add_odd_even_merger_recursive (n,
358 indizes_half, indizes_half_num);
365 status = sn_network_add_odd_even_merger_recursive (n,
366 indizes_half + indizes_half_num, indizes_half_num);
375 s = sn_stage_create (n->stages_num);
379 for (i = 1; i < (indizes_num - 2); i += 2)
382 c.max = indizes[i + 1];
384 sn_stage_comparator_add (s, &c);
387 sn_network_stage_add (n, s);
394 assert (indizes_num == 2);
399 s = sn_stage_create (n->stages_num);
403 sn_stage_comparator_add (s, &c);
404 sn_network_stage_add (n, s);
408 } /* int sn_network_add_odd_even_merger_recursive */
410 static int sn_network_add_odd_even_merger (sn_network_t *n)
417 indizes_num = n->inputs_num;
418 indizes = (int *) malloc (indizes_num * sizeof (int));
422 for (i = 0; i < indizes_num; i++)
425 status = sn_network_add_odd_even_merger_recursive (n,
426 indizes, indizes_num);
430 } /* int sn_network_add_bitonic_merger */
432 sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1)
439 stages_num = (n0->stages_num > n1->stages_num)
443 n = sn_network_create (n0->inputs_num + n1->inputs_num);
447 for (i = 0; i < stages_num; i++)
449 sn_stage_t *s = sn_stage_create (i);
451 if (i < n0->stages_num)
452 for (j = 0; j < SN_STAGE_COMP_NUM (n0->stages[i]); j++)
454 sn_comparator_t *c = SN_STAGE_COMP_GET (n0->stages[i], j);
455 sn_stage_comparator_add (s, c);
458 if (i < n1->stages_num)
459 for (j = 0; j < SN_STAGE_COMP_NUM (n1->stages[i]); j++)
461 sn_comparator_t *c_orig = SN_STAGE_COMP_GET (n1->stages[i], j);
462 sn_comparator_t c_copy;
464 SN_COMP_MIN(&c_copy) = SN_COMP_MIN(c_orig) + n0->inputs_num;
465 SN_COMP_MAX(&c_copy) = SN_COMP_MAX(c_orig) + n0->inputs_num;
467 sn_stage_comparator_add (s, &c_copy);
470 sn_network_stage_add (n, s);
473 if (sn_bounded_random (0, 1) == 0)
475 sn_network_add_bitonic_merger (n);
479 sn_network_add_odd_even_merger (n);
482 sn_network_compress (n);
485 } /* sn_network_t *sn_network_combine */
487 sn_network_t *sn_network_read (FILE *fh)
494 while (fgets (buffer, sizeof (buffer), fh) != NULL)
496 char *str_key = buffer;
497 char *str_value = NULL;
498 int buffer_len = strlen (buffer);
500 while ((buffer_len > 0) && ((buffer[buffer_len - 1] == '\n')
501 || (buffer[buffer_len - 1] == '\r')))
504 buffer[buffer_len] = '\0';
509 str_value = strchr (buffer, ':');
510 if (str_value == NULL)
512 printf ("Cannot parse line: %s\n", buffer);
516 *str_value = '\0'; str_value++;
517 while ((*str_value != '\0') && (isspace (*str_value) != 0))
520 if (strcasecmp ("Inputs", str_key) == 0)
521 opt_inputs = atoi (str_value);
523 printf ("Unknown key: %s\n", str_key);
524 } /* while (fgets) */
529 n = sn_network_create (opt_inputs);
535 s = sn_stage_read (fh);
539 sn_network_stage_add (n, s);
542 if (SN_NETWORK_STAGE_NUM (n) < 1)
544 sn_network_destroy (n);
549 } /* sn_network_t *sn_network_read */
551 sn_network_t *sn_network_read_file (const char *file)
556 fh = fopen (file, "r");
560 n = sn_network_read (fh);
565 } /* sn_network_t *sn_network_read_file */
567 int sn_network_write (sn_network_t *n, FILE *fh)
571 fprintf (fh, "Inputs: %i\n", n->inputs_num);
574 for (i = 0; i < n->stages_num; i++)
575 sn_stage_write (n->stages[i], fh);
578 } /* int sn_network_write */
580 int sn_network_write_file (sn_network_t *n, const char *file)
585 fh = fopen (file, "w");
589 status = sn_network_write (n, fh);
594 } /* int sn_network_write_file */
596 /* vim: set shiftwidth=2 softtabstop=2 : */