src/texsourc/lib/libpng/contrib/tools/scale.c

   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:
   3  *
   4  *    (number * mult + add)>>16
   5  *
   6  * The command arguments are:
   7  *
   8  *    scale target source
   9  *
  10  * and the program works out a pair of numbers, mult and add, that evaluate:
  11  *
  12  *          number * target
  13  *   round( --------------- )
  14  *              source
  15  *
  16  * exactly for number in the range 0..source
  17  */
  18 #define _ISOC99_SOURCE 1
  19
  20 #include <stdlib.h>
  21 #include <string.h>
  22 #include <stdio.h>
  23 #include <math.h>
  24
  25 static double minerr;
  26 static unsigned long minmult, minadd, minshift;
  27 static long mindelta;
  28
  29 static int
  30 test(unsigned long target, unsigned long source, unsigned long mult,
  31    long add, unsigned long shift, long delta)
  32 {
  33    unsigned long i;
  34    double maxerr = 0;
  35    double rs = (double)target/source;
  36
  37    for (i=0; i<=source; ++i)
  38    {
  39       unsigned long t = i*mult+add;
  40       double err = fabs((t >> shift) - i*rs);
  41
  42       if (err > minerr)
  43          return 0;
  44
  45       if (err > maxerr)
  46          maxerr = err;
  47    }
  48
  49    if (maxerr < minerr)
  50    {
  51       minerr = maxerr;
  52       minmult = mult;
  53       minadd = add;
  54       minshift = shift;
  55       mindelta = delta;
  56    }
  57
  58    return maxerr < .5;
  59 }
  60
  61 static int
  62 dotest(unsigned long target, unsigned long source, unsigned long mult,
  63    long add, unsigned long shift, long delta, int print)
  64 {
  65    if (test(target, source, mult, add, shift, delta))
  66    {
  67       if (print & 4)
  68          printf("      {%11lu,%6ld /* >>%lu */ }, /* %lu/%lu */\n",
  69             mult, add, shift, target, source);
  70
  71       else if (print & 2)
  72          printf("      {%11lu,%6ld,%3lu }, /* %lu/%lu */\n",
  73             mult, add, shift, target, source);
  74
  75       else if (print)
  76          printf("number * %lu/%lu = (number * %lu + %ld) >> %lu [delta %ld]\n",
  77             target, source, mult, add, shift, delta);
  78
  79       return 1;
  80    }
  81
  82    return 0;
  83 }
  84
  85 static int
  86 find(unsigned long target, unsigned long source, int print, int fixshift)
  87 {
  88    unsigned long shift = 0;
  89    unsigned long shiftlim = 0;
  90
  91    /* In the final math the sum is at most (source*mult+add) >> shift, so:
  92     *
  93     *    source*mult+add < 1<<32
  94     *    mult < (1<<32)/source
  95     *
  96     * but:
  97     *
  98     *    mult = (target<<shift)/source
  99     *
 100     * so:
 101     *
 102     *    (target<<shift) < (1<<32)
 103     */
 104    if (fixshift < 0)
 105       while ((target<<shiftlim) < 0x80000000U) ++shiftlim;
 106
 107    else
 108       shift = shiftlim = (unsigned long)fixshift;
 109
 110    minerr = 1E8;
 111
 112    for (; shift<=shiftlim; ++shift)
 113    {
 114       unsigned long mult = ((target<<shift) + (source>>1)) / source;
 115       long delta;
 116       long limit = 1; /* seems to be sufficient */
 117       long add, start, end;
 118
 119       end = 1<<shift;
 120       start = -end;
 121
 122       for (add=start; add<=end; ++add)
 123          if (dotest(target,source,mult,add,shift,0,print))
 124             return 1;
 125
 126       for (delta=1; delta<=limit; ++delta)
 127       {
 128 #        if 0
 129             fprintf(stderr, "%lu/%lu: shift %lu, delta %lu\n", target, source,
 130                shift, delta);
 131 #        endif
 132
 133          for (add=start; add<=end; ++add)
 134          {
 135             if (dotest(target, source, mult-delta, add, shift, -delta, print))
 136                return 1;
 137
 138             if (dotest(target, source, mult+delta, add, shift, delta, print))
 139                return 1;
 140          }
 141       }
 142    }
 143
 144    if (print & 4)
 145       printf("      {%11lu,%6ld /* >>%lu */ }, /* %lu/%lu ERROR: .5+%g*/\n",
 146          minmult, minadd, minshift, target, source, minerr-.5);
 147
 148    else if (print & 2)
 149       printf("      {%11lu,%6ld,%3lu }, /* %lu/%lu ERROR: .5+%g*/\n",
 150          minmult, minadd, minshift, target, source, minerr-.5);
 151
 152    else if (print)
 153       printf(
 154          "number * %lu/%lu ~= (number * %lu + %ld) >> %lu +/-.5+%g [delta %ld]\n",
 155          target, source, minmult, minadd, minshift, minerr-.5, mindelta);
 156
 157    return 0;
 158 }
 159
 160 static void
 161 usage(const char *prog)
 162 {
 163    fprintf(stderr,
 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",
 173       prog);
 174    exit(1);
 175 }
 176
 177 int
 178 main(int argc, const char **argv)
 179 {
 180    int i, err = 0, maxshift = 0, firstsrc = 1, code = 0, denominator = 0;
 181    unsigned long target, shift = 0;
 182
 183    while (argc > 1)
 184    {
 185       if (strcmp(argv[firstsrc], "--maxshift") == 0)
 186       {
 187          maxshift = 1;
 188          ++firstsrc;
 189       }
 190
 191       else if (strcmp(argv[firstsrc], "--code") == 0)
 192       {
 193          code = 1;
 194          ++firstsrc;
 195       }
 196
 197       else if (strcmp(argv[firstsrc], "--denominator") == 0)
 198       {
 199          denominator = 1;
 200          ++firstsrc;
 201       }
 202
 203       else
 204          break;
 205    }
 206
 207
 208    if (argc < 2+firstsrc)
 209       usage(argv[0]);
 210
 211    target = strtoul(argv[firstsrc++], 0, 0);
 212    if (target == 0) usage(argv[0]);
 213
 214    for (i=firstsrc; i<argc; ++i)
 215    {
 216       unsigned long source = strtoul(argv[i], 0, 0);
 217
 218       if (source == 0) usage(argv[0]);
 219
 220       if (!find(denominator ? source : target, denominator ? target : source,
 221          maxshift ? 0 : 1+code, -1))
 222          err = 1;
 223
 224       if (minshift > shift) shift = minshift;
 225    }
 226
 227    if (maxshift) for (i=firstsrc; i<argc; ++i)
 228    {
 229       unsigned long source = strtoul(argv[i], 0, 0);
 230
 231       if (!find(denominator ? source : target, denominator ? target : source,
 232          code ? 4 : 1, shift))
 233          err = 1;
 234    }
 235
 236    /* Just an exit code - the printout above lists the problem */
 237    return err;
 238 }