3 more benchmarks

git-svn-id: https://yquem.inria.fr/compcert/svn/compcert/trunk@1252 fca1b0fc-160b-0410-b1d3-a4f43f01ea2e

7 files changed, 863 insertions, 1 deletions

diff --git a/test/c/Makefile b/test/c/Makefile
index bff6211..060c8fc 100644
--- a/test/c/Makefile
+++ b/test/c/Makefile
@@ -12,7 +12,8 @@ TIME=xtime -o /dev/null -mintime 1.0     # Xavier's hack
 
 BENCHS=fib integr qsort fft sha1 aes almabench lists \
   binarytrees fannkuch knucleotide mandelbrot nbody \
-  nsieve nsievebits spectral vmach
+  nsieve nsievebits spectral vmach \
+  bisect chomp perlin
 
 PROGS=$(BENCHS) initializers
 
diff --git a/test/c/Results/bisect b/test/c/Results/bisect
new file mode 100644
index 0000000..de52da1
--- /dev/null
+++ b/test/c/Results/bisect
@@ -0,0 +1,20 @@
+    2 1.60051e+01
+    3 8.10101e+01
+    4 2.56008e+02
+    5 6.25006e+02
+    6 1.29600e+03
+    7 2.40100e+03
+    8 4.09600e+03
+    9 6.56100e+03
+   10 1.00000e+04
+   11 1.46410e+04
+   12 2.07360e+04
+   13 2.85610e+04
+   14 3.84160e+04
+   15 5.06250e+04
+   16 6.55360e+04
+   17 8.35210e+04
+   18 1.04976e+05
+   19 1.30321e+05
+   20 1.60000e+05
+eps2 = 9.71445e-05,  k = 22965
diff --git a/test/c/Results/chomp b/test/c/Results/chomp
new file mode 100644
index 0000000..c215420
--- /dev/null
+++ b/test/c/Results/chomp
@@ -0,0 +1,19 @@
+player 0 plays at (2,2)
+player 1 plays at (7,1)
+player 0 plays at (0,2)
+player 1 plays at (7,0)
+player 0 plays at (6,1)
+player 1 plays at (6,0)
+player 0 plays at (5,1)
+player 1 plays at (5,0)
+player 0 plays at (4,1)
+player 1 plays at (4,0)
+player 0 plays at (3,1)
+player 1 plays at (3,0)
+player 0 plays at (2,1)
+player 1 plays at (2,0)
+player 0 plays at (1,1)
+player 1 plays at (1,0)
+player 0 plays at (0,1)
+player 1 plays at (0,0)
+player 1 loses
diff --git a/test/c/Results/perlin b/test/c/Results/perlin
new file mode 100644
index 0000000..74e5655
--- /dev/null
+++ b/test/c/Results/perlin
@@ -0,0 +1 @@
+1.7556e+02
diff --git a/test/c/bisect.c b/test/c/bisect.c
new file mode 100644
index 0000000..759f997
--- /dev/null
+++ b/test/c/bisect.c
@@ -0,0 +1,376 @@
+/****
+    Copyright (C) 1996 McGill University.
+    Copyright (C) 1996 McCAT System Group.
+    Copyright (C) 1996 ACAPS Benchmark Administrator
+                       benadmin@acaps.cs.mcgill.ca
+
+    This program is free software; you can redistribute it and/or modify
+    it provided this copyright notice is maintained.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
+****/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <math.h>
+#include <float.h>
+
+void  *allocvector(size_t size) 
+{
+  void *V;
+
+  if ( (V = (void *) malloc((size_t) size)) == NULL ) {
+    fprintf(stderr, "Error: couldn't allocate V in allocvector.\n");
+    exit(2);
+  }
+  memset(V,0,size);
+  return V;
+}
+
+void dallocvector(int n, double **V)
+{
+  *V = (double *) allocvector((size_t) n*sizeof(double));
+}
+
+
+#define FUDGE  (double) 1.01
+
+
+
+int sturm(int n, double c[], double b[], double beta[], double x)
+
+/**************************************************************************
+
+Purpose:
+------------
+  Calculates the sturm sequence given by
+
+    q_1(x)  =  c[1] - x
+
+    q_i(x)  =  (c[i] - x) - b[i]*b[i] / q_{i-1}(x)
+
+  and returns a(x) = the number of negative q_i. a(x) gives the number
+  of eigenvalues smaller than x of the symmetric tridiagonal matrix
+  with diagonal c[0],c[1],...,c[n-1] and off-diagonal elements
+  b[1],b[2],...,b[n-1].
+
+
+Input parameters:
+------------------------
+  n :
+         The order of the matrix.
+
+  c[0]..c[n-1] : 
+        An n x 1 array giving the diagonal elements of the tridiagonal matrix.
+
+  b[1]..b[n-1] :   
+        An n x 1 array giving the sub-diagonal elements. b[0] may be 
+        arbitrary but is replaced by zero in the procedure.
+
+  beta[1]..beta[n-1] :
+         An n x 1 array giving the square of the  sub-diagonal elements, 
+         i.e. beta[i] = b[i]*b[i]. beta[0] may be arbitrary but is replaced by
+         zero in the procedure.
+
+  x :
+         Argument for the Sturm sequence.
+
+
+Returns:
+------------------------
+  integer a = Number of eigenvalues of the matrix smaller than x.
+
+
+Notes:
+------------------------
+On SGI PowerChallenge this function should be compiled with option
+"-O3 -OPT:IEEE_arithmetic=3" in order to activate the optimization 
+mentioned in the code below.
+
+
+**********************************************************************/
+
+{
+  int i;
+  int a;
+  double q;
+  
+  a = 0;
+  q = 1.0;
+
+  for(i=0; i<n; i++) {
+
+#ifndef TESTFIRST
+
+    if (q != 0.0) {
+
+#ifndef RECIPROCAL
+      q =  (c[i] - x) - beta[i]/q; 
+#else 
+  /* A potentially NUMERICALLY DANGEROUS optimizations is used here.
+   * The previous statement should read:
+   *         q = (c[i] - x) - beta[i]/q 
+   * But computing the reciprocal might help on some architectures
+   * that have multiply-add and/or reciprocal instuctions.
+   */
+     iq = 1.0/q;  
+      q =  (c[i] - x) - beta[i]*iq; 
+#endif
+
+    }
+    else {
+      q = (c[i] - x) - fabs(b[i])/DBL_EPSILON;  
+    }
+
+    if (q < 0)
+      a = a + 1;    
+  }
+
+#else
+    
+    if (q < 0) {
+      a = a + 1;    
+      
+#ifndef RECIPROCAL
+      q =  (c[i] - x) - beta[i]/q; 
+#else 
+      /* A potentially NUMERICALLY DANGEROUS optimizations is used here.
+       * The previous statement should read:
+       *         q = (c[i] - x) - beta[i]/q 
+       * But computing the reciprocal might help on some architectures
+       * that have multiply-add and/or reciprocal instuctions.
+       */
+      iq = 1.0/q;  
+      q =  (c[i] - x) - beta[i]*iq; 
+#endif
+      
+    }
+    else if (q > 0.0) {
+#ifndef RECIPROCAL
+      q =  (c[i] - x) - beta[i]/q; 
+#else 
+      /* A potentially NUMERICALLY DANGEROUS optimizations is used here.
+       * The previous statement should read:
+       *         q = (c[i] - x) - beta[i]/q 
+       * But computing the reciprocal might help on some architectures
+       * that have multiply-add and/or reciprocal instuctions.
+       */
+      iq = 1.0/q;  
+      q =  (c[i] - x) - beta[i]*iq; 
+#endif
+    }
+    else {
+      q = (c[i] - x) - fabs(b[i])/DBL_EPSILON;  
+    }
+    
+  }
+  if (q < 0)
+    a = a + 1;    
+#endif
+
+  return a;
+}
+  
+
+
+
+void dbisect(double c[], double b[], double beta[], 
+	     int n, int m1, int m2, double eps1, double *eps2, int *z,  
+	     double x[])
+
+
+/**************************************************************************
+
+Purpose:
+------------
+ 
+  Calculates eigenvalues lambda_{m1}, lambda_{m1+1},...,lambda_{m2} of
+  a symmetric tridiagonal matrix with diagonal c[0],c[1],...,c[n-1]
+  and off-diagonal elements b[1],b[2],...,b[n-1] by the method of
+  bisection, using Sturm sequences.
+
+
+  Input parameters:
+------------------------
+
+  c[0]..c[n-1] : 
+        An n x 1 array giving the diagonal elements of the tridiagonal matrix.
+
+  b[1]..b[n-1] :   
+        An n x 1 array giving the sub-diagonal elements. b[0] may be 
+        arbitrary but is replaced by zero in the procedure.
+
+  beta[1]..beta[n-1] :
+         An n x 1 array giving the square of the  sub-diagonal elements, 
+         i.e. beta[i] = b[i]*b[i]. beta[0] may be arbitrary but is replaced by
+         zero in the procedure.
+
+  n :
+         The order of the matrix.
+
+  m1, m2 : 
+         The eigenvalues lambda_{m1}, lambda_{m1+1},...,lambda_{m2} are 
+         calculated (NB! lambda_1 is the smallest eigenvalue).
+         m1 <= m2must hold otherwise no eigenvalues are computed.
+         returned in x[m1-1],x[m1],...,x[m2-1]
+ 
+  eps1 :
+         a quantity that affects the precision to which eigenvalues are 
+         computed. The bisection is continued as long as 
+         x_high - x_low >  2*DBL_EPSILON(|x_low|  + |x_high|) + eps1       (1)
+         When (1) is no longer satisfied, (x_high + x_low)/2  gives the
+         current eigenvalue lambda_k. Here DBL_EPSILON (constant) is
+         the machine accuracy, i.e. the smallest number such that
+         (1 + DBL_EPSILON) > 1.
+
+  Output parameters:
+------------------------
+
+  eps2 :
+        The overall bound  for the error in any eigenvalue.
+  z :
+        The total number of iterations to find all eigenvalues.
+  x : 
+        The array  x[m1],x[m1+1],...,x[m2] contains the computed eigenvalues.
+
+**********************************************************************/
+{
+  int i;
+  double h,xmin,xmax;
+  beta[0]  = b[0] = 0.0; 
+
+
+  /* calculate Gerschgorin interval */
+  xmin = c[n-1] - FUDGE*fabs(b[n-1]);
+  xmax = c[n-1] + FUDGE*fabs(b[n-1]);
+  for(i=n-2; i>=0; i--) { 
+    h = FUDGE*(fabs(b[i]) + fabs(b[i+1]));
+    if (c[i] + h > xmax)  xmax = c[i] + h;
+    if (c[i] - h < xmin)  xmin = c[i] - h;
+  }
+
+  /*  printf("xmax = %lf  xmin = %lf\n",xmax,xmin); */
+
+  /* estimate precision of calculated eigenvalues */  
+  *eps2 = DBL_EPSILON * (xmin + xmax > 0 ? xmax : -xmin);
+  if (eps1 <= 0)
+    eps1 = *eps2;
+  *eps2 = 0.5 * eps1 + 7 * *eps2;
+  { int a,k;
+    double x1,xu,x0;
+    double *wu; 
+
+    if( (wu = (double *) calloc(n+1,sizeof(double))) == NULL) {
+      fputs("bisect: Couldn't allocate memory for wu",stderr);
+      exit(1);
+    }
+
+    /* Start bisection process  */
+    x0 = xmax;
+    for(i=m2; i >= m1; i--) {
+      x[i] = xmax;
+      wu[i] = xmin;
+    }
+    *z = 0;
+    /* loop for the k-th eigenvalue */
+    for(k=m2; k>=m1; k--) {
+      xu = xmin;
+      for(i=k; i>=m1; i--) {
+	if(xu < wu[i]) {
+	  xu = wu[i];
+	  break;
+	}
+      }
+      if (x0 > x[k])
+	x0 = x[k];
+
+      x1 = (xu + x0)/2;
+      while ( x0-xu > 2*DBL_EPSILON*(fabs(xu)+fabs(x0))+eps1 ) {	
+	*z = *z + 1;
+	
+	/* Sturms Sequence  */
+
+       	a = sturm(n,c,b,beta,x1); 
+
+	/* Bisection step */
+	if (a < k) {
+	  if (a < m1) 
+	    xu = wu[m1] = x1;
+	  else {
+	    xu = wu[a+1] = x1;
+	    if (x[a] > x1) x[a] = x1;
+	  }
+	}
+	else {
+	  x0 = x1;
+	}	
+	x1 = (xu + x0)/2;	
+      }
+      x[k] = (xu + x0)/2;
+    }
+    free(wu);
+  }
+}     
+
+void test_matrix(int n, double *C, double *B)
+/* Symmetric tridiagonal matrix with diagonal
+
+     c_i = i^4,  i = (1,2,...,n)
+
+     and off-diagonal elements
+
+     b_i = i-1,    i = (2,3,...n).
+     It is possible to determine small eigenvalues of this matrix, with the
+     same relative error as for the large ones. 
+*/
+{
+  int i;
+    
+  for(i=0; i<n; i++) {
+    B[i] = (double) i;
+    C[i] = (double ) (i+1)*(i+1);
+    C[i] = C[i] * C[i];
+  }
+}
+
+
+int main(int argc,char *argv[])
+{
+  int rep,n,k,i,j;
+  double eps,eps2;
+  double *D,*E,*beta,*S;
+
+  rep = 50;
+  n = 500;
+  eps = 2.2204460492503131E-16;
+
+  dallocvector(n,&D);
+  dallocvector(n,&E);
+  dallocvector(n,&beta);
+  dallocvector(n,&S);  
+  
+  for (j=0; j<rep; j++) {
+    test_matrix(n,D,E);
+    
+    for (i=0; i<n; i++) {
+      beta[i] = E[i] * E[i];
+      S[i] = 0.0;
+    }
+    
+    E[0] = beta[0] = 0;  
+    dbisect(D,E,beta,n,1,n,eps,&eps2,&k,&S[-1]);    
+    
+  }
+  
+  for(i=1; i<20; i++)
+    printf("%5d %.5e\n",i+1,S[i]); 
+
+  printf("eps2 = %.5e,  k = %d\n",eps2,k);
+
+  return 0;
+}
+
+
diff --git a/test/c/chomp.c b/test/c/chomp.c
new file mode 100644
index 0000000..042877d
--- /dev/null
+++ b/test/c/chomp.c
@@ -0,0 +1,370 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#define NDATA (int *)malloc(ncol * sizeof(int))
+#define NLIST (struct _list *)malloc(sizeof(struct _list))
+#define NPLAY (struct _play *)malloc(sizeof(struct _play))
+
+struct _list
+{
+  int *data;
+  struct _list *next;
+} *wanted;
+
+struct _play
+{
+  int value;
+  int *state;
+  struct _list *first;
+  struct _play *next;
+} *game_tree;
+
+int nrow,ncol;      /* global so as to avoid passing them all over the place */
+
+int *copy_data(data) /* creates a duplicate of a given -data list */
+int *data;
+{
+  int *new = NDATA;
+  int counter = ncol;
+  while (counter --)
+      new[counter] = data[counter];
+  return new;
+}
+
+int next_data(int *data)  /* gives the next logical setup to the one passed */
+                          /* new setup replaces the old. Returns 0 if no valid */
+{                         /* setup exists after the one passed */
+  int counter = 0;
+  int valid = 0;     /* default to none */
+  while ((counter != ncol) && (! valid)) /* until its done */
+    {
+      if (data[counter] == nrow) /* if we hit a border */
+        {
+	  data[counter] = 0;     /* reset it to zero     */
+	  counter ++;      /* and take next column */
+	}
+       else
+        {
+	  data[counter] ++;      /* otherwise, just increment row number */
+	  valid = 1;                /* and set valid to true. */
+	}
+    }
+  return valid;                     /* return whether or not */
+}                                   /* a next could be found */
+
+void melt_data(int *data1,int *data2) /* melts 2 _data's into the first one. */
+{
+  int counter = ncol;
+  while (counter --)     /* do every column */
+    {
+      if (data1[counter] > data2[counter]) /* take the lowest one */
+          data1[counter] = data2[counter]; /* and put in first _data */
+    }
+}
+
+int equal_data(int *data1,int *data2) /* check if both _data's are equal */
+{
+  int counter = ncol;
+  while ((counter --) && (data1[counter] == data2[counter]));
+  return (counter < 0);
+}
+
+int valid_data(int *data) /* checks if the play could ever be achieved. */
+{
+  int low;      /* var to hold the current height */
+  int counter = 0;
+  low = nrow;   /* default to top of board */
+  while (counter != ncol) /* for every column */
+    {
+      if (data[counter] > low) break;  /* if you get something higher */
+      low = data[counter];             /* set this as current height */
+      counter ++;
+    }
+  return (counter == ncol);
+}
+
+void dump_list(struct _list *list) /* same for a _list structure */
+{
+  if (list != NULL)
+    {
+      dump_list(list -> next); /* dump the rest of it */
+      free(list -> data); /* and its _data structure */
+      free(list);
+    }
+}
+
+void dump_play(play) /* and for the entire game tree */
+struct _play *play;
+{
+  if (play != NULL)
+    {
+      dump_play(play -> next);  /* dump the rest of the _play */
+      dump_list(play -> first); /* its _list */
+      free(play -> state); /* and its _data */
+      free(play);
+    }
+}
+
+int get_value(int *data) /* get the value (0 or 1) for a specific _data */
+{
+  struct _play *search;
+  search = game_tree; /* start at the begginig */
+  while (! equal_data(search -> state,data)) /* until you find a match */
+      search = search -> next; /* take next element */
+  return search -> value; /* return its value */
+}
+
+void show_data(int *data) /* little display routine to give off results */
+{
+  int counter = 0;
+  while (counter != ncol)
+    {
+      printf("%d",data[counter ++]);
+      if (counter != ncol) putchar(',');
+    }
+}
+
+void show_move(int *data) /* puts in the "(" and ")" for show_data() */
+{
+  putchar('(');
+  show_data(data);
+  printf(")\n");
+}
+
+void show_list(struct _list *list) /* show the entire list of moves */
+{
+  while (list != NULL)
+    {
+      show_move(list -> data);
+      list = list -> next;
+    }
+}
+
+void show_play(struct _play *play) /* to diplay the whole tree */
+{
+  while (play != NULL)
+    {
+      printf("For state :\n");
+      show_data(play -> state);
+      printf("  value = %d\n",play -> value);
+      printf("We get, in order :\n");
+      show_list(play -> first);
+      play = play -> next;
+    }
+}
+
+int in_wanted(int *data) /* checks if the current _data is in the wanted list */
+{
+  struct _list *current;
+  current = wanted; /* start at the begginig */
+  while (current != NULL) /* unitl the last one */
+    {
+      if (equal_data(current -> data,data)) break; /* break if found */
+      current = current -> next; /* take next element */
+    }
+  if (current == NULL) return 0; /* if at the end, not found */
+  return 1;
+}
+
+int *make_data(int row,int col) /* creates a new _data with the correct */
+                                /* contents for the specified row & col */
+{
+  int count;
+  int *new = NDATA;
+  for (count = 0;count != col;count ++) /* creates col-1 cells with nrow */
+      new[count] = nrow;
+  for (;count != ncol;count ++) /* and the rest with row as value */
+      new[count] = row;
+  return new;         /* and return pointer to first element */
+}
+
+struct _list *make_list(int *data,int *value,int *all) /* create the whole _list of moves */
+                                                          /* for the _data structure data */
+{
+  int row,col;
+  int *temp;
+  struct _list *head,*current;
+  *value = 1; /* set to not good to give */
+  head = NLIST; /* create dummy header */
+  head -> next = NULL; /* set NULL as next element */
+  current = head;      /* start from here */
+  for (row = 0;row != nrow;row ++) /* for every row */
+    {
+      for (col = 0;col != ncol;col ++) /* for every column */
+        {
+	  temp = make_data(row,col); /* create _data for this play */
+	  melt_data(temp,data);      /* melt it with the current one */
+	  if (! equal_data(temp,data)) /* if they are different, it good */
+	    {
+	      current -> next = NLIST; /* create new element in list */
+	      current -> next -> data = copy_data(temp); /* copy data, and place in list */
+	      current -> next -> next = NULL; /* NULL the next element */
+	      current = current -> next; /* advance pointer */
+	      if (*value == 1) /* if still not found a good one */
+	          *value = get_value(temp); /* look at this value */
+	      if ((! *all) && (*value == 0))
+	        {  /* if we found it, and all is not set */
+		  col = ncol - 1; /* do what it take sto break out now */
+		  row = nrow - 1;
+	          if (in_wanted(temp)) /* if in the wanted list */
+		      *all = 2; /* flag it */
+		}
+	    }
+	   else /* if its not a valid move */
+	    {
+	      if (col == 0) row = nrow - 1; /* break out if at first column */
+	      col = ncol - 1;               /* but make sure you break out */
+	    }                               /* of the col for-loop anyway */
+	  free(temp); /* dump this unneeded space */
+	}
+    }
+  current = head -> next; /* skip first element */
+  free(head); /* dump it */
+  if (current != NULL) *value = 1 - *value; /* invert value if its */
+  return current;                           /* not the empty board */
+}
+
+struct _play *make_play(int all) /* make up the entire tree-like stuff */
+{
+  int val;
+  int *temp;
+  struct _play *head,*current;
+  head = NPLAY; /* dummy header again */
+  current = head; /* start here */
+  game_tree = NULL; /* no elements yet */
+  temp = make_data(0,0); /* new data, for empty board */
+  temp[0] --;   /* set it up at (-1,xx) so that next_data() returns (0,xx) */
+  while (next_data(temp)) /* take next one, and break if none */
+    {
+      if (valid_data(temp)) /* if board position is possible */
+        {
+	  current -> next = NPLAY; /* create a new _play cell */
+	  if (game_tree == NULL) game_tree = current -> next;
+	      /* set up game_tree if it was previously NULL */
+	  current -> next -> state = copy_data(temp); /* make a copy of temp */
+	  current -> next -> first = make_list(temp,&val,&all);
+	      /* make up its whole list of possible moves */
+	  current -> next -> value = val; /* place its value */
+	  current -> next -> next = NULL; /* no next element */
+	  current = current -> next;      /* advance pointer */
+	  if (all == 2)                   /* if found flag is on */
+	    {
+	      free(temp);            /* dump current temp */
+	      temp = make_data(nrow,ncol); /* and create one that will break */
+	    }
+	}
+    }
+  current = head -> next; /* skip first element */
+  free(head);             /* dump it */
+  return current;         /* and return pointer to start of list */
+}
+
+void make_wanted(int *data) /* makes up the list of positions from the full board */
+{
+         /* everything here is almost like in the previous function. */
+	 /* The reason its here, is that it does not do as much as   */
+	 /* the one before, and thus goes faster. Also, it saves the */
+	 /* results directly in wanted, which is a global variable.  */
+
+  int row,col;
+  int *temp;
+  struct _list *head,*current;
+  head = NLIST;
+  head -> next = NULL;
+  current = head;
+  for (row = 0;row != nrow;row ++)
+    {
+      for (col = 0;col != ncol;col ++)
+        {
+	  temp = make_data(row,col);
+	  melt_data(temp,data);
+	  if (! equal_data(temp,data))
+	    {
+	      current -> next = NLIST;
+	      current -> next -> data = copy_data(temp);
+	      current -> next -> next = NULL;
+	      current = current -> next;
+	    }
+	   else
+	    {
+	      if (col == 0) row = nrow - 1;
+	      col = ncol - 1;
+	    }
+	  free(temp);
+	}
+    }
+  current = head -> next;
+  free(head);
+  wanted = current;
+}
+
+int *get_good_move(struct _list *list) /* gets the first good move from a _list */
+{
+  if (list == NULL) return NULL; /* if list is NULL, say so */
+      /* until end-of-list or a good one is found */
+      /* a good move is one that gives off a zero value */
+  while ((list -> next != NULL) && (get_value(list -> data)))
+      list = list -> next;
+  return copy_data(list -> data); /* return the value */
+}
+
+int *get_winning_move(struct _play *play) /* just scans for the first good move */
+                                          /* in the last _list of a _play. This */
+{                                         /* is the full board */
+  int *temp;
+  while (play -> next != NULL) play = play -> next; /* go to end of _play */
+  temp = get_good_move(play -> first); /* get good move */
+  return temp;                         /* return it */
+}
+
+struct _list *where(int *data,struct _play *play)
+{
+  while (! equal_data(play -> state,data)) /* search for given _data */
+      play = play -> next;
+  return play -> first;  /* return the pointer */
+}
+
+void get_real_move(int *data1,int *data2,int *row,int *col) /* returns row & col of the move */
+                                                           /* which created data1 from data2 */
+{
+  *col = 0;
+  while (data1[*col] == data2[*col]) /* until there is a change */
+      (*col) ++;             /* and increment col number */
+  *row = data1[*col];  /* row is given by the content of the structure */
+}
+
+int main(void)
+{
+  int row,col,player;
+  int *current,*temp;
+  struct _play *tree;
+
+
+  ncol = 7;
+#ifdef SMALL_PROBLEM_SIZE
+  nrow = 7;
+#else
+  nrow = 8;
+#endif
+  tree = make_play(1); /* create entire tree structure, not just the */
+  player = 0;          /* needed part for first move */
+  current = make_data(nrow,ncol); /* start play at full board */
+  while (current != NULL)
+    {
+      temp = get_good_move(where(current,tree)); /* get best move */
+      if (temp != NULL)  /* temp = NULL when the poison pill is taken */
+        {
+          get_real_move(temp,current,&row,&col); /* calculate coordinates */
+          /* print it out nicely */
+          printf("player %d plays at (%d,%d)\n",player,row,col);
+          player = 1 - player; /* next player to do the same */
+          free(current);  /* dump for memory management */
+        }
+      current = temp; /* update board */
+    }
+  dump_play(tree); /* dump unneeded tree */
+  printf("player %d loses\n",1 - player); /* display winning player */
+  return 0;
+}
+
+/*****************************************************************************/
diff --git a/test/c/perlin.c b/test/c/perlin.c
new file mode 100644
index 0000000..1559c1c
--- /dev/null
+++ b/test/c/perlin.c
@@ -0,0 +1,75 @@
+// perlin noise, derived from the Java reference implementation at 
+// http://mrl.nyu.edu/~perlin/noise/
+
+#include <math.h>
+#include <stdio.h>
+
+static int p[512];
+
+static int permutation[256] = { 151,160,137,91,90,15,
+   131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
+   190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
+   88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,134,139,48,27,166,
+   77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
+   102,143,54, 65,25,63,161, 1,216,80,73,209,76,132,187,208, 89,18,169,200,196,
+   135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,250,124,123,
+   5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
+   223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167, 43,172,9,
+   129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,
+   251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,107,
+   49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
+   138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180
+   };
+
+static double fade(double t) { return t * t * t * (t * (t * 6 - 15) + 10); }
+
+static double lerp(double t, double a, double b) { return a + t * (b - a); }
+
+static double grad(int hash, double x, double y, double z) {
+  int h = hash & 15;                      // CONVERT LO 4 BITS OF HASH CODE
+  double u = h<8 ? x : y,                 // INTO 12 GRADIENT DIRECTIONS.
+         v = h<4 ? y : h==12||h==14 ? x : z;
+  return ((h&1) == 0 ? u : -u) + ((h&2) == 0 ? v : -v);
+}
+
+static double noise(double x, double y, double z) {
+  int X = (int)floor(x) & 255,                  // FIND UNIT CUBE THAT
+      Y = (int)floor(y) & 255,                  // CONTAINS POINT.
+      Z = (int)floor(z) & 255;
+  x -= floor(x);                                // FIND RELATIVE X,Y,Z
+  y -= floor(y);                                // OF POINT IN CUBE.
+  z -= floor(z);
+  double u = fade(x),                                // COMPUTE FADE CURVES
+         v = fade(y),                                // FOR EACH OF X,Y,Z.
+        w = fade(z);
+  int A = p[X  ]+Y, AA = p[A]+Z, AB = p[A+1]+Z,      // HASH COORDINATES OF
+      B = p[X+1]+Y, BA = p[B]+Z, BB = p[B+1]+Z;      // THE 8 CUBE CORNERS,
+
+  return lerp(w, lerp(v, lerp(u, grad(p[AA  ], x  , y  , z   ),  // AND ADD
+                                 grad(p[BA  ], x-1, y  , z   )), // BLENDED
+                         lerp(u, grad(p[AB  ], x  , y-1, z   ),  // RESULTS
+                                 grad(p[BB  ], x-1, y-1, z   ))),// FROM  8
+                 lerp(v, lerp(u, grad(p[AA+1], x  , y  , z-1 ),  // CORNERS
+                                 grad(p[BA+1], x-1, y  , z-1 )), // OF CUBE
+                         lerp(u, grad(p[AB+1], x  , y-1, z-1 ),
+                                 grad(p[BB+1], x-1, y-1, z-1 ))));
+}
+
+static void init() { 
+  int i = 0;
+  for (i=0; i < 256 ; i++)
+    p[256+i] = p[i] = permutation[i];
+}
+
+int main() {
+  init();
+  
+  double x, y, z, sum = 0.0;
+  for (x = -11352.57; x < 23561.57; x += .1235)
+    for (y = -346.1235; y < 124.124; y += 1.4325)
+      for (z = -156.235; y < 23.2345; y += 2.45)
+        sum += noise(x, y, z);
+  
+  printf("%.4e\n", sum);
+  return 0;
+}