Mercurial > hg > sv-dependency-builds

annotate src/fftw-3.3.5/support/addchain.c @ 43:5ea0608b923f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Current zlib source
author Chris Cannam
date Tue, 18 Oct 2016 14:33:52 +0100
parents 2cd0e3b3e1fd
children
rev   line source
Chris@42 1 /* addition-chain optimizer */
Chris@42 2 #include <stdio.h>
Chris@42 3 #include <stdlib.h>
Chris@42 4 #include <unistd.h>
Chris@42 5
Chris@42 6 static int verbose;
Chris@42 7 static int mulcost = 18;
Chris@42 8 static int ldcost = 2;
Chris@42 9 static int sqcost = 10;
Chris@42 10 static int reflcost = 8;
Chris@42 11 #define INFTY 100000
Chris@42 12
Chris@42 13 static int *answer;
Chris@42 14 static int best_so_far;
Chris@42 15
Chris@42 16 static void print_answer(int n, int t)
Chris@42 17 {
Chris@42 18 int i;
Chris@42 19 printf("| (%d, %d) -> [", n, t);
Chris@42 20 for (i = 0; i < t; ++i)
Chris@42 21 printf("%d;", answer[i]);
Chris@42 22 printf("] (* %d *)\n", best_so_far);
Chris@42 23 }
Chris@42 24
Chris@42 25 #define DO(i, j, k, cst) \
Chris@42 26 if (k < n) { \
Chris@42 27 int c = A[i] + A[j] + cst; \
Chris@42 28 if (c < A[k]) { \
Chris@42 29 A[k] = c; \
Chris@42 30 changed = 1; \
Chris@42 31 } \
Chris@42 32 }
Chris@42 33
Chris@42 34 #define DO3(i, j, l, k, cst) \
Chris@42 35 if (k < n) { \
Chris@42 36 int c = A[i] + A[j] + A[l] + cst; \
Chris@42 37 if (c < A[k]) { \
Chris@42 38 A[k] = c; \
Chris@42 39 changed = 1; \
Chris@42 40 } \
Chris@42 41 }
Chris@42 42
Chris@42 43 static int optimize(int n, int *A)
Chris@42 44 {
Chris@42 45 int i, j, k, changed, cst, cstmax;
Chris@42 46
Chris@42 47 do {
Chris@42 48 changed = 0;
Chris@42 49 for (i = 0; i < n; ++i) {
Chris@42 50 k = i + i;
Chris@42 51 DO(i, i, k, sqcost);
Chris@42 52 }
Chris@42 53
Chris@42 54 for (i = 0; i < n; ++i) {
Chris@42 55 for (j = 0; j <= i; ++j) {
Chris@42 56 k = i + j;
Chris@42 57 DO(i, j, k, mulcost);
Chris@42 58 k = i - j;
Chris@42 59 DO(i, j, k, mulcost);
Chris@42 60
Chris@42 61 k = i + j;
Chris@42 62 DO3(i, j, i - j, k, reflcost);
Chris@42 63 }
Chris@42 64 }
Chris@42 65
Chris@42 66 } while (changed);
Chris@42 67
Chris@42 68 cst = cstmax = 0;
Chris@42 69 for (i = 0; i < n; ++i) {
Chris@42 70 cst += A[i];
Chris@42 71 if (A[i] > cstmax) cstmax = A[i];
Chris@42 72 }
Chris@42 73 /* return cstmax; */
Chris@42 74 return cst;
Chris@42 75 }
Chris@42 76
Chris@42 77 static void search(int n, int t, int *A, int *B, int depth)
Chris@42 78 {
Chris@42 79 if (depth == 0) {
Chris@42 80 int i, tc;
Chris@42 81 for (i = 0; i < n; ++i)
Chris@42 82 A[i] = INFTY;
Chris@42 83 A[0] = 0; /* always free */
Chris@42 84 for (i = 1; i <= t; ++i)
Chris@42 85 A[B[-i]] = ldcost;
Chris@42 86
Chris@42 87 tc = optimize(n, A);
Chris@42 88 if (tc < best_so_far) {
Chris@42 89 best_so_far = tc;
Chris@42 90 for (i = 1; i <= t; ++i)
Chris@42 91 answer[t - i] = B[-i];
Chris@42 92 if (verbose)
Chris@42 93 print_answer(n, t);
Chris@42 94 }
Chris@42 95 } else {
Chris@42 96 for (B[0] = B[-1] + 1; B[0] < n; ++B[0])
Chris@42 97 search(n, t, A, B + 1, depth - 1);
Chris@42 98 }
Chris@42 99 }
Chris@42 100
Chris@42 101 static void doit(int n, int t)
Chris@42 102 {
Chris@42 103 int *A;
Chris@42 104 int *B;
Chris@42 105
Chris@42 106 A = malloc(n * sizeof(int));
Chris@42 107 B = malloc((t + 1) * sizeof(int));
Chris@42 108 answer = malloc(t * sizeof(int));
Chris@42 109
Chris@42 110 B[0] = 0;
Chris@42 111 best_so_far = INFTY;
Chris@42 112 search(n, t, A, B + 1, t);
Chris@42 113
Chris@42 114 print_answer(n, t);
Chris@42 115
Chris@42 116 free(A); free(B); free(answer);
Chris@42 117 }
Chris@42 118
Chris@42 119 int main(int argc, char *argv[])
Chris@42 120 {
Chris@42 121 int n = 32;
Chris@42 122 int t = 3;
Chris@42 123 int all;
Chris@42 124 int ch;
Chris@42 125
Chris@42 126 verbose = 0;
Chris@42 127 all = 0;
Chris@42 128 while ((ch = getopt(argc, argv, "n:t:m:l:r:s:va")) != -1) {
Chris@42 129 switch (ch) {
Chris@42 130 case 'n':
Chris@42 131 n = atoi(optarg);
Chris@42 132 break;
Chris@42 133 case 't':
Chris@42 134 t = atoi(optarg);
Chris@42 135 break;
Chris@42 136 case 'm':
Chris@42 137 mulcost = atoi(optarg);
Chris@42 138 break;
Chris@42 139 case 'l':
Chris@42 140 ldcost = atoi(optarg);
Chris@42 141 break;
Chris@42 142 case 's':
Chris@42 143 sqcost = atoi(optarg);
Chris@42 144 break;
Chris@42 145 case 'r':
Chris@42 146 reflcost = atoi(optarg);
Chris@42 147 break;
Chris@42 148 case 'v':
Chris@42 149 ++verbose;
Chris@42 150 break;
Chris@42 151 case 'a':
Chris@42 152 ++all;
Chris@42 153 break;
Chris@42 154 case '?':
Chris@42 155 fprintf(stderr, "use the source\n");
Chris@42 156 exit(1);
Chris@42 157 }
Chris@42 158 }
Chris@42 159
Chris@42 160 if (all) {
Chris@42 161 for (n = 4; n <= 64; n *= 2) {
Chris@42 162 int n1 = n - 1; if (n1 > 7) n1 = 7;
Chris@42 163 for (t = 1; t <= n1; ++t)
Chris@42 164 doit(n, t);
Chris@42 165 }
Chris@42 166 } else {
Chris@42 167 doit(n, t);
Chris@42 168 }
Chris@42 169
Chris@42 170 return 0;
Chris@42 171 }