Mercurial > hg > sv-dependency-builds

annotate src/fftw-3.3.5/support/addchain.c @ 83:ae30d91d2ffe

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Replace these with versions built using an older toolset (so as to avoid ABI compatibilities when linking on Ubuntu 14.04 for packaging purposes)
author Chris Cannam
date Fri, 07 Feb 2020 11:51:13 +0000
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 }