view Lib/fftw-3.2.1/support/addchain.c @ 1:e86e9c111b29

Updates stuff that potentially fixes the memory leak and also makes it work on Windows and Linux (Need to test). Still have to fix fftw include for linux in Jucer.

/* addition-chain optimizer */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

static int verbose;
static int mulcost = 18;
static int ldcost = 2;
static int sqcost = 10;
static int reflcost = 8;
#define INFTY 100000

static int *answer;
static int best_so_far;

static void print_answer(int n, int t)
{
     int i;
     printf("| (%d, %d) -> [", n, t);
     for (i = 0; i < t; ++i)
	  printf("%d;", answer[i]);
     printf("] (* %d *)\n", best_so_far);
}

#define DO(i, j, k, cst)			\
if (k < n) {					\
     int c = A[i] + A[j] + cst;			\
     if (c < A[k]) {				\
	  A[k] = c;				\
	  changed = 1;				\
     }						\
}

#define DO3(i, j, l, k, cst)			\
if (k < n) {					\
     int c = A[i] + A[j] + A[l] + cst;		\
     if (c < A[k]) {				\
	  A[k] = c;				\
	  changed = 1;				\
     }						\
}

static int optimize(int n, int *A)
{
     int i, j, k, changed, cst, cstmax;

     do {
	  changed = 0;
	  for (i = 0; i < n; ++i) {
	       k = i + i;
	       DO(i, i, k, sqcost);
	  }

	  for (i = 0; i < n; ++i) {
	       for (j = 0; j <= i; ++j) {
		    k = i + j;
		    DO(i, j, k, mulcost);
		    k = i - j;
		    DO(i, j, k, mulcost);

		    k = i + j;
		    DO3(i, j, i - j, k, reflcost);
	       }
	  }

     } while (changed);

     cst = cstmax = 0;
     for (i = 0; i < n; ++i) {
	  cst += A[i];
	  if (A[i] > cstmax) cstmax = A[i];
     }
/*     return cstmax; */
     return cst;
}

static void search(int n, int t, int *A, int *B, int depth)
{
     if (depth == 0) {
	  int i, tc;
	  for (i = 0; i < n; ++i)
	       A[i] = INFTY;
	  A[0] = 0;		/* always free */
	  for (i = 1; i <= t; ++i)
	       A[B[-i]] = ldcost;

	  tc = optimize(n, A);
	  if (tc < best_so_far) {
	       best_so_far = tc;
	       for (i = 1; i <= t; ++i)
		    answer[t - i] = B[-i];
	       if (verbose)
		    print_answer(n, t);
	  }
     } else {
	  for (B[0] = B[-1] + 1; B[0] < n; ++B[0])
	       search(n, t, A, B + 1, depth - 1);
     }
}

static void doit(int n, int t)
{
     int *A;
     int *B;

     A = malloc(n * sizeof(int));
     B = malloc((t + 1) * sizeof(int));
     answer = malloc(t * sizeof(int));

     B[0] = 0;
     best_so_far = INFTY;
     search(n, t, A, B + 1, t);

     print_answer(n, t);

     free(A); free(B); free(answer);
}

int main(int argc, char *argv[])
{
     int n = 32;
     int t = 3;
     int all;
     int ch;

     verbose = 0;
     all = 0;
     while ((ch = getopt(argc, argv, "n:t:m:l:r:s:va")) != -1) {
	  switch (ch) {
	  case 'n':
	       n = atoi(optarg);
	       break;
	  case 't':
	       t = atoi(optarg);
	       break;
	  case 'm':
	       mulcost = atoi(optarg);
	       break;
	  case 'l':
	       ldcost = atoi(optarg);
	       break;
	  case 's':
	       sqcost = atoi(optarg);
	       break;
	  case 'r':
	       reflcost = atoi(optarg);
	       break;
	  case 'v':
	       ++verbose;
	       break;
	  case 'a':
	       ++all;
	       break;
	  case '?':
	       fprintf(stderr, "use the source\n");
	       exit(1);
	  }
     }

     if (all) {
	  for (n = 4; n <= 64; n *= 2) {
	       int n1 = n - 1; if (n1 > 7) n1 = 7;
	       for (t = 1; t <= n1; ++t)
		    doit(n, t);
	  }
     } else {
	  doit(n, t);
     }

     return 0;
}