1 /* Given a target range and a source range work out an expression to scale from
2 * the source to the target of the form:
4 * (number * mult + add)>>16
6 * The command arguments are:
10 * and the program works out a pair of numbers, mult and add, that evaluate:
13 * round( --------------- )
16 * exactly for number in the range 0..source
18 #define _ISOC99_SOURCE 1
26 static unsigned long minmult, minadd, minshift;
30 test(unsigned long target, unsigned long source, unsigned long mult,
31 long add, unsigned long shift, long delta)
35 double rs = (double)target/source;
37 for (i=0; i<=source; ++i)
39 unsigned long t = i*mult+add;
40 double err = fabs((t >> shift) - i*rs);
62 dotest(unsigned long target, unsigned long source, unsigned long mult,
63 long add, unsigned long shift, long delta, int print)
65 if (test(target, source, mult, add, shift, delta))
68 printf(" {%11lu,%6ld /* >>%lu */ }, /* %lu/%lu */\n",
69 mult, add, shift, target, source);
72 printf(" {%11lu,%6ld,%3lu }, /* %lu/%lu */\n",
73 mult, add, shift, target, source);
76 printf("number * %lu/%lu = (number * %lu + %ld) >> %lu [delta %ld]\n",
77 target, source, mult, add, shift, delta);
86 find(unsigned long target, unsigned long source, int print, int fixshift)
88 unsigned long shift = 0;
89 unsigned long shiftlim = 0;
91 /* In the final math the sum is at most (source*mult+add) >> shift, so:
93 * source*mult+add < 1<<32
94 * mult < (1<<32)/source
98 * mult = (target<<shift)/source
102 * (target<<shift) < (1<<32)
105 while ((target<<shiftlim) < 0x80000000U) ++shiftlim;
108 shift = shiftlim = (unsigned long)fixshift;
112 for (; shift<=shiftlim; ++shift)
114 unsigned long mult = ((target<<shift) + (source>>1)) / source;
116 long limit = 1; /* seems to be sufficient */
117 long add, start, end;
122 for (add=start; add<=end; ++add)
123 if (dotest(target,source,mult,add,shift,0,print))
126 for (delta=1; delta<=limit; ++delta)
129 fprintf(stderr, "%lu/%lu: shift %lu, delta %lu\n", target, source,
133 for (add=start; add<=end; ++add)
135 if (dotest(target, source, mult-delta, add, shift, -delta, print))
138 if (dotest(target, source, mult+delta, add, shift, delta, print))
145 printf(" {%11lu,%6ld /* >>%lu */ }, /* %lu/%lu ERROR: .5+%g*/\n",
146 minmult, minadd, minshift, target, source, minerr-.5);
149 printf(" {%11lu,%6ld,%3lu }, /* %lu/%lu ERROR: .5+%g*/\n",
150 minmult, minadd, minshift, target, source, minerr-.5);
154 "number * %lu/%lu ~= (number * %lu + %ld) >> %lu +/-.5+%g [delta %ld]\n",
155 target, source, minmult, minadd, minshift, minerr-.5, mindelta);
161 usage(const char *prog)
164 "usage: %s {--denominator|--maxshift|--code} target {source}\n"
165 " For each 'source' prints 'mult' and 'add' such that:\n\n"
166 " (number * mult + add) >> 16 = round(number*target/source)\n\n"
167 " for all integer values of number in the range 0..source.\n\n"
168 " --denominator: swap target and source (specify a single source first\n"
169 " and follow with multiple targets.)\n"
170 " --maxshift: find the lowest shift value that works for all the\n"
171 " repeated 'source' values\n"
172 " --code: output C code for array/structure initialization\n",
178 main(int argc, const char **argv)
180 int i, err = 0, maxshift = 0, firstsrc = 1, code = 0, denominator = 0;
181 unsigned long target, shift = 0;
185 if (strcmp(argv[firstsrc], "--maxshift") == 0)
191 else if (strcmp(argv[firstsrc], "--code") == 0)
197 else if (strcmp(argv[firstsrc], "--denominator") == 0)
208 if (argc < 2+firstsrc)
211 target = strtoul(argv[firstsrc++], 0, 0);
212 if (target == 0) usage(argv[0]);
214 for (i=firstsrc; i<argc; ++i)
216 unsigned long source = strtoul(argv[i], 0, 0);
218 if (source == 0) usage(argv[0]);
220 if (!find(denominator ? source : target, denominator ? target : source,
221 maxshift ? 0 : 1+code, -1))
224 if (minshift > shift) shift = minshift;
227 if (maxshift) for (i=firstsrc; i<argc; ++i)
229 unsigned long source = strtoul(argv[i], 0, 0);
231 if (!find(denominator ? source : target, denominator ? target : source,
232 code ? 4 : 1, shift))
236 /* Just an exit code - the printout above lists the problem */