add fannkuch test

1 files changed, 159 insertions, 0 deletions

diff --git a/test/fannkuch.cpp b/test/fannkuch.cpp
new file mode 100644
index 000000000..f615ba2f8
--- /dev/null
+++ b/test/fannkuch.cpp
@@ -0,0 +1,159 @@
+/*
+ * The Computer Language Benchmarks Game
+ * http://shootout.alioth.debian.org/
+ *
+ * Contributed by Eckehard Berns
+ * Based on code by Heiner Marxen
+ * and the ATS version by Hongwei Xi
+ *
+ * Modified for emscripten by azakai
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+
+struct worker_args {
+   int i, n;
+   struct worker_args *next;
+};
+
+int
+fannkuch_worker(void *_arg)
+{
+   struct worker_args *args = (worker_args*)_arg;
+   int *perm1, *count, *perm;
+   int maxflips, flips, i, n, r, j, k, tmp;
+
+   maxflips = 0;
+   n = args->n;
+   perm1 = (int*)malloc(n * sizeof(int));
+   perm = (int*)malloc(n * sizeof(int));
+   count = (int*)malloc(n * sizeof(int));
+   for (i = 0; i < n; i++)
+      perm1[i] = i;
+   perm1[args->i] = n - 1;
+   perm1[n - 1] = args->i;
+   r = n;
+
+   for (;;) {
+      for (; r > 1; r--)
+         count[r - 1] = r;
+      if (perm1[0] != 0 && perm1[n - 1] != n - 1) {
+         for (i = 0; i < n; i++)
+            perm[i] = perm1[i];
+         flips = 0;
+         k = perm[0];
+         do {
+            for (i = 1, j = k - 1; i < j; i++, j--) {
+               tmp = perm[i];
+               perm[i] = perm[j];
+               perm[j] = tmp;
+            }
+            flips++;
+            tmp = perm[k];
+            perm[k] = k;
+            k = tmp;
+         } while (k);
+         if (maxflips < flips)
+            maxflips = flips;
+      }
+      for (;;) {
+         if (r >= n - 1) {
+            free(perm1);
+            free(perm);
+            free(count);
+            return maxflips;
+         }
+
+         {
+            int p0 = perm1[0];
+            for (i = 0; i < r; i++)
+               perm1[i] = perm1[i + 1];
+            perm1[i] = p0;
+         }
+         if (--count[r] > 0)
+            break;
+         r++;
+      }
+   }
+}
+
+static int
+fannkuch(int n)
+{
+   struct worker_args *args, *targs;
+   int showmax = 30;
+   int *perm1, *count, i, r, maxflips, flips;
+
+   args = NULL;
+   for (i = 0; i < n - 1; i++) {
+      targs = (worker_args*)malloc(sizeof(struct worker_args));
+      targs->i = i;
+      targs->n = n;
+      targs->next = args;
+      args = targs;
+   }
+
+   perm1 = (int*)malloc(n * sizeof(int));
+   count = (int*)malloc(n * sizeof(int));
+
+   for (i = 0; i < n; i++)
+      perm1[i] = i;
+
+   r = n;
+   for (;;) {
+      if (showmax) {
+         for (i = 0; i < n; i++)
+            printf("%d", perm1[i] + 1);
+         printf("\n");
+         showmax--;
+      } else
+         goto cleanup;
+
+      for (; r > 1; r--)
+         count[r - 1] = r;
+
+      for (;;) {
+         if (r == n)
+            goto cleanup;
+         {
+            int p0 = perm1[0];
+            for (i = 0; i < r; i++)
+               perm1[i] = perm1[i + 1];
+            perm1[i] = p0;
+         }
+         if (--count[r] > 0)
+            break;
+
+         r++;
+      }
+   }
+
+    cleanup:
+   free(perm1);
+   free(count);
+   maxflips = 0;
+   while (args != NULL) {
+      flips = (int)fannkuch_worker(args);
+      if (maxflips < flips)
+         maxflips = flips;
+      targs = args;
+      args = args->next;
+      free(targs);
+   }
+   return maxflips;
+}
+
+int
+main(int argc, char **argv)
+{
+   int n = argc > 1 ? atoi(argv[1]) : 0;
+
+   if (n < 1) {
+      printf("Wrong argument.\n");
+      return 1;
+   }
+   printf("Pfannkuchen(%d) = %d.\n", n, fannkuch(n));
+   return 0;
+}
+