home *** CD-ROM | disk | FTP | other *** search
/ CD Actual 3 / CD ACTUAL 3.iso / linux / incoming / libgr-2.000 / libgr-2 / libgr-2.0.3 / rle / inv_cmap.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-08-14  |  23.3 KB  |  898 lines
  1. /*
  2.  * This software is copyrighted as noted below.  It may be freely copied,
  3.  * modified, and redistributed, provided that the copyright notice is
  4.  * preserved on all copies.
  5.  *
  6.  * There is no warranty or other guarantee of fitness for this software,
  7.  * it is provided solely "as is".  Bug reports or fixes may be sent
  8.  * to the author, who may or may not act on them as he desires.
  9.  *
  10.  * You may not include this software in a program or other software product
  11.  * without supplying the source, or without informing the end-user that the
  12.  * source is available for no extra charge.
  13.  *
  14.  * If you modify this software, you should include a notice giving the
  15.  * name of the person performing the modification, the date of modification,
  16.  * and the reason for such modification.
  17.  */
  18. /*
  19.  * inv_cmap.c - Compute an inverse colormap.
  20.  *
  21.  * Author:    Spencer W. Thomas
  22.  *         EECS Dept.
  23.  *         University of Michigan
  24.  * Date:    Thu Sep 20 1990
  25.  * Copyright (c) 1990, University of Michigan
  26.  *
  27.  * inv_cmap.c,v 1.1.1.1 1995/08/15 02:46:22 neal Exp
  28.  */
  29.  
  30. #include <math.h>
  31. #include <stdio.h>
  32.  
  33. #ifndef NO_INV_CMAP_TRACKING
  34.  
  35. #ifdef DEBUG
  36. static int cred, cgreen, cblue;
  37. static int red, green;
  38. static unsigned char *zrgbp;
  39. #endif
  40. static int bcenter, gcenter, rcenter;
  41. static long gdist, rdist, cdist;
  42. static long cbinc, cginc, crinc;
  43. static unsigned long *gdp, *rdp, *cdp;
  44. static unsigned char *grgbp, *rrgbp, *crgbp;
  45. static gstride, rstride;
  46. static long x, xsqr, colormax;
  47. static int cindex;
  48. #ifdef INSTRUMENT_IT
  49. static long outercount = 0, innercount = 0;
  50. #endif
  51.  
  52. #ifdef USE_PROTOTYPES
  53. static void maxfill( unsigned long *, long );
  54. static int redloop( void );
  55. static int greenloop( int );
  56. static int blueloop( int );
  57. #else
  58. static void maxfill();
  59. static int redloop();
  60. static int greenloop();
  61. static int blueloop();
  62. #endif
  63.  
  64.  
  65. /*****************************************************************
  66.  * TAG( inv_cmap )
  67.  *
  68.  * Compute an inverse colormap efficiently.
  69.  * Inputs:
  70.  *     colors:        Number of colors in the forward colormap.
  71.  *     colormap:    The forward colormap.
  72.  *     bits:        Number of quantization bits.  The inverse
  73.  *             colormap will have (2^bits)^3 entries.
  74.  *     dist_buf:    An array of (2^bits)^3 long integers to be
  75.  *             used as scratch space.
  76.  * Outputs:
  77.  *     rgbmap:        The output inverse colormap.  The entry
  78.  *             rgbmap[(r<<(2*bits)) + (g<<bits) + b]
  79.  *             is the colormap entry that is closest to the
  80.  *             (quantized) color (r,g,b).
  81.  * Assumptions:
  82.  *     Quantization is performed by right shift (low order bits are
  83.  *     truncated).  Thus, the distance to a quantized color is
  84.  *     actually measured to the color at the center of the cell
  85.  *     (i.e., to r+.5, g+.5, b+.5, if (r,g,b) is a quantized color).
  86.  * Algorithm:
  87.  *     Uses a "distance buffer" algorithm:
  88.  *     The distance from each representative in the forward color map
  89.  *     to each point in the rgb space is computed.  If it is less
  90.  *     than the distance currently stored in dist_buf, then the
  91.  *     corresponding entry in rgbmap is replaced with the current
  92.  *     representative (and the dist_buf entry is replaced with the
  93.  *     new distance).
  94.  *
  95.  *     The distance computation uses an efficient incremental formulation.
  96.  *
  97.  *     Distances are computed "outward" from each color.  If the
  98.  *     colors are evenly distributed in color space, the expected
  99.  *     number of cells visited for color I is N^3/I.
  100.  *     Thus, the complexity of the algorithm is O(log(K) N^3),
  101.  *     where K = colors, and N = 2^bits.
  102.  */
  103.  
  104. /*
  105.  * Here's the idea:  scan from the "center" of each cell "out"
  106.  * until we hit the "edge" of the cell -- that is, the point
  107.  * at which some other color is closer -- and stop.  In 1-D,
  108.  * this is simple:
  109.  *     for i := here to max do
  110.  *         if closer then buffer[i] = this color
  111.  *         else break
  112.  *     repeat above loop with i := here-1 to min by -1
  113.  *
  114.  * In 2-D, it's trickier, because along a "scan-line", the
  115.  * region might start "after" the "center" point.  A picture
  116.  * might clarify:
  117.  *         |    ...
  118.  *               | ...    .
  119.  *              ...        .
  120.  *           ... |      .
  121.  *          .    +         .
  122.  *           .          .
  123.  *            .         .
  124.  *             .........
  125.  *
  126.  * The + marks the "center" of the above region.  On the top 2
  127.  * lines, the region "begins" to the right of the "center".
  128.  *
  129.  * Thus, we need a loop like this:
  130.  *     detect := false
  131.  *     for i := here to max do
  132.  *         if closer then
  133.  *             buffer[..., i] := this color
  134.  *             if !detect then
  135.  *                 here = i
  136.  *                 detect = true
  137.  *         else
  138.  *             if detect then
  139.  *                 break
  140.  *                 
  141.  * Repeat the above loop with i := here-1 to min by -1.  Note that
  142.  * the "detect" value should not be reinitialized.  If it was
  143.  * "true", and center is not inside the cell, then none of the
  144.  * cell lies to the left and this loop should exit
  145.  * immediately.
  146.  *
  147.  * The outer loops are similar, except that the "closer" test
  148.  * is replaced by a call to the "next in" loop; its "detect"
  149.  * value serves as the test.  (No assignment to the buffer is
  150.  * done, either.)
  151.  *
  152.  * Each time an outer loop starts, the "here", "min", and
  153.  * "max" values of the next inner loop should be
  154.  * re-initialized to the center of the cell, 0, and cube size,
  155.  * respectively.  Otherwise, these values will carry over from
  156.  * one "call" to the inner loop to the next.  This tracks the
  157.  * edges of the cell and minimizes the number of
  158.  * "unproductive" comparisons that must be made.
  159.  *
  160.  * Finally, the inner-most loop can have the "if !detect"
  161.  * optimized out of it by splitting it into two loops: one
  162.  * that finds the first color value on the scan line that is
  163.  * in this cell, and a second that fills the cell until
  164.  * another one is closer:
  165.  *      if !detect then        {needed for "down" loop}
  166.  *         for i := here to max do
  167.  *         if closer then
  168.  *             buffer[..., i] := this color
  169.  *             detect := true
  170.  *             break
  171.  *    for i := i+1 to max do
  172.  *        if closer then
  173.  *             buffer[..., i] := this color
  174.  *         else
  175.  *             break
  176.  *
  177.  * In this implementation, each level will require the
  178.  * following variables.  Variables labelled (l) are local to each
  179.  * procedure.  The ? should be replaced with r, g, or b:
  180.  *      cdist:            The distance at the starting point.
  181.  *     ?center:    The value of this component of the color
  182.  *      c?inc:            The initial increment at the ?center position.
  183.  *     ?stride:    The amount to add to the buffer
  184.  *             pointers (dp and rgbp) to get to the
  185.  *             "next row".
  186.  *     min(l):        The "low edge" of the cell, init to 0
  187.  *     max(l):        The "high edge" of the cell, init to
  188.  *             colormax-1
  189.  *     detect(l):        True if this row has changed some
  190.  *                     buffer entries.
  191.  *      i(l):             The index for this row.
  192.  *      ?xx:            The accumulated increment value.
  193.  *      
  194.  *      here(l):        The starting index for this color.  The
  195.  *                      following variables are associated with here,
  196.  *                      in the sense that they must be updated if here
  197.  *                      is changed.
  198.  *      ?dist:            The current distance for this level.  The
  199.  *                      value of dist from the previous level (g or r,
  200.  *                      for level b or g) initializes dist on this
  201.  *                      level.  Thus gdist is associated with here(b)).
  202.  *      ?inc:            The initial increment for the row.
  203.  *      ?dp:            Pointer into the distance buffer.  The value
  204.  *                      from the previous level initializes this level.
  205.  *      ?rgbp:            Pointer into the rgb buffer.  The value
  206.  *                      from the previous level initializes this level.
  207.  * 
  208.  * The blue and green levels modify 'here-associated' variables (dp,
  209.  * rgbp, dist) on the green and red levels, respectively, when here is
  210.  * changed.
  211.  */
  212.  
  213. void
  214. inv_cmap( colors, colormap, bits, dist_buf, rgbmap )
  215. int colors, bits;
  216. unsigned char *colormap[3], *rgbmap;
  217. unsigned long *dist_buf;
  218. {
  219.     int nbits = 8 - bits;
  220.  
  221.     colormax = 1 << bits;
  222.     x = 1 << nbits;
  223.     xsqr = 1 << (2 * nbits);
  224.  
  225.     /* Compute "strides" for accessing the arrays. */
  226.     gstride = colormax;
  227.     rstride = colormax * colormax;
  228.  
  229. #ifdef INSTRUMENT_IT
  230.     outercount = 0;
  231.     innercount = 0;
  232. #endif
  233.     maxfill( dist_buf, colormax );
  234.  
  235.     for ( cindex = 0; cindex < colors; cindex++ )
  236.     {
  237.     /*
  238.      * Distance formula is
  239.      * (red - map[0])^2 + (green - map[1])^2 + (blue - map[2])^2
  240.      *
  241.      * Because of quantization, we will measure from the center of
  242.      * each quantized "cube", so blue distance is
  243.      *     (blue + x/2 - map[2])^2,
  244.      * where x = 2^(8 - bits).
  245.      * The step size is x, so the blue increment is
  246.      *     2*x*blue - 2*x*map[2] + 2*x^2
  247.      *
  248.      * Now, b in the code below is actually blue/x, so our
  249.      * increment will be 2*(b*x^2 + x^2 - x*map[2]).  For
  250.      * efficiency, we will maintain this quantity in a separate variable
  251.      * that will be updated incrementally by adding 2*x^2 each time.
  252.      */
  253.     /* The initial position is the cell containing the colormap
  254.      * entry.  We get this by quantizing the colormap values.
  255.      */
  256.     rcenter = colormap[0][cindex] >> nbits;
  257.     gcenter = colormap[1][cindex] >> nbits;
  258.     bcenter = colormap[2][cindex] >> nbits;
  259. #ifdef DEBUG
  260.     cred = colormap[0][cindex];
  261.     cgreen = colormap[1][cindex];
  262.     cblue = colormap[2][cindex];
  263.     fprintf( stderr, "---Starting %d: %d,%d,%d -> %d,%d,%d\n",
  264.          cindex, cred, cgreen, cblue,
  265.          rcenter, gcenter, bcenter );
  266.     zrgbp = rgbmap;
  267. #endif
  268.  
  269.     rdist = colormap[0][cindex] - (rcenter * x + x/2);
  270.     gdist = colormap[1][cindex] - (gcenter * x + x/2);
  271.     cdist = colormap[2][cindex] - (bcenter * x + x/2);
  272.     cdist = rdist*rdist + gdist*gdist + cdist*cdist;
  273.  
  274.     crinc = 2 * ((rcenter + 1) * xsqr - (colormap[0][cindex] * x));
  275.     cginc = 2 * ((gcenter + 1) * xsqr - (colormap[1][cindex] * x));
  276.     cbinc = 2 * ((bcenter + 1) * xsqr - (colormap[2][cindex] * x));
  277.  
  278.     /* Array starting points. */
  279.     cdp = dist_buf + rcenter * rstride + gcenter * gstride + bcenter;
  280.     crgbp = rgbmap + rcenter * rstride + gcenter * gstride + bcenter;
  281.  
  282.     (void)redloop();
  283.     }
  284. #ifdef INSTRUMENT_IT
  285.     fprintf( stderr, "K = %d, N = %d, outer count = %ld, inner count = %ld\n",
  286.          colors, colormax, outercount, innercount );
  287. #endif
  288. }
  289.  
  290. /* redloop -- loop up and down from red center. */
  291. static int
  292. redloop()
  293. {
  294.     int detect;
  295.     int r;
  296.     int first;
  297.     long txsqr = xsqr + xsqr;
  298.     static long rxx;
  299.  
  300.     detect = 0;
  301.  
  302.     /* Basic loop up. */
  303.     for ( r = rcenter, rdist = cdist, rxx = crinc,
  304.       rdp = cdp, rrgbp = crgbp, first = 1;
  305.       r < colormax;
  306.       r++, rdp += rstride, rrgbp += rstride,
  307.       rdist += rxx, rxx += txsqr, first = 0 )
  308.     {
  309. #ifdef DEBUG
  310.     red = r;
  311. #endif
  312.     if ( greenloop( first ) )
  313.         detect = 1;
  314.     else if ( detect )
  315.         break;
  316.     }
  317.     
  318.     /* Basic loop down. */
  319.     for ( r = rcenter - 1, rxx = crinc - txsqr, rdist = cdist - rxx,
  320.       rdp = cdp - rstride, rrgbp = crgbp - rstride, first = 1;
  321.       r >= 0;
  322.       r--, rdp -= rstride, rrgbp -= rstride,
  323.       rxx -= txsqr, rdist -= rxx, first = 0 )
  324.     {
  325. #ifdef DEBUG
  326.     red = r;
  327. #endif
  328.     if ( greenloop( first ) )
  329.         detect = 1;
  330.     else if ( detect )
  331.         break;
  332.     }
  333.     
  334.     return detect;
  335. }
  336.  
  337. /* greenloop -- loop up and down from green center. */
  338. static int
  339. greenloop( restart )
  340. int restart;
  341. {
  342.     int detect;
  343.     int g;
  344.     int first;
  345.     long txsqr = xsqr + xsqr;
  346.     static int here, min, max;
  347. #ifdef MINMAX_TRACK
  348.     static int prevmax, prevmin;
  349.     int thismax, thismin;
  350. #endif
  351.     static long ginc, gxx, gcdist;    /* "gc" variables maintain correct */
  352.     static unsigned long *gcdp;        /*  values for bcenter position, */
  353.     static unsigned char *gcrgbp;    /*  despite modifications by blueloop */
  354.                     /*  to gdist, gdp, grgbp. */
  355.  
  356.     if ( restart )
  357.     {
  358.     here = gcenter;
  359.     min = 0;
  360.     max = colormax - 1;
  361.     ginc = cginc;
  362. #ifdef MINMAX_TRACK
  363.     prevmax = 0;
  364.     prevmin = colormax;
  365. #endif
  366.     }
  367.  
  368. #ifdef MINMAX_TRACK
  369.     thismin = min;
  370.     thismax = max;
  371. #endif
  372.     detect = 0;
  373.  
  374.     /* Basic loop up. */
  375.     for ( g = here, gcdist = gdist = rdist, gxx = ginc,
  376.       gcdp = gdp = rdp, gcrgbp = grgbp = rrgbp, first = 1;
  377.       g <= max;
  378.       g++, gdp += gstride, gcdp += gstride, grgbp += gstride, gcrgbp += gstride,
  379.       gdist += gxx, gcdist += gxx, gxx += txsqr, first = 0 )
  380.     {
  381. #ifdef DEBUG
  382.     green = g;
  383. #endif
  384.     if ( blueloop( first ) )
  385.     {
  386.         if ( !detect )
  387.         {
  388.         /* Remember here and associated data! */
  389.         if ( g > here )
  390.         {
  391.             here = g;
  392.             rdp = gcdp;
  393.             rrgbp = gcrgbp;
  394.             rdist = gcdist;
  395.             ginc = gxx;
  396. #ifdef MINMAX_TRACK
  397.             thismin = here;
  398. #endif
  399. #ifdef DEBUG
  400.             fprintf( stderr, "===Adjusting green here up at %d,%d\n",
  401.                  red, here );
  402. #endif
  403.         }
  404.         detect = 1;
  405.         }
  406.     }
  407.     else if ( detect )
  408.     {
  409. #ifdef MINMAX_TRACK
  410.         thismax = g - 1;
  411. #endif
  412.         break;
  413.     }
  414.     }
  415.     
  416.     /* Basic loop down. */
  417.     for ( g = here - 1, gxx = ginc - txsqr, gcdist = gdist = rdist - gxx,
  418.       gcdp = gdp = rdp - gstride, gcrgbp = grgbp = rrgbp - gstride,
  419.       first = 1;
  420.       g >= min;
  421.       g--, gdp -= gstride, gcdp -= gstride, grgbp -= gstride, gcrgbp -= gstride,
  422.       gxx -= txsqr, gdist -= gxx, gcdist -= gxx, first = 0 )
  423.     {
  424. #ifdef DEBUG
  425.     green = g;
  426. #endif
  427.     if ( blueloop( first ) )
  428.     {
  429.         if ( !detect )
  430.         {
  431.         /* Remember here! */
  432.         here = g;
  433.         rdp = gcdp;
  434.         rrgbp = gcrgbp;
  435.         rdist = gcdist;
  436.         ginc = gxx;
  437. #ifdef MINMAX_TRACK
  438.         thismax = here;
  439. #endif
  440. #ifdef DEBUG
  441.         fprintf( stderr, "===Adjusting green here down at %d,%d\n",
  442.              red, here );
  443. #endif
  444.         detect = 1;
  445.         }
  446.     }
  447.     else if ( detect )
  448.     {
  449. #ifdef MINMAX_TRACK
  450.         thismin = g + 1;
  451. #endif
  452.         break;
  453.     }
  454.     }
  455.     
  456. #ifdef MINMAX_TRACK
  457.     /* If we saw something, update the edge trackers.  For now, only
  458.      * tracks edges that are "shrinking" (min increasing, max
  459.      * decreasing.
  460.      */
  461.     if ( detect )
  462.     {
  463.     if ( thismax < prevmax )
  464.         max = thismax;
  465.  
  466.     prevmax = thismax;
  467.  
  468.     if ( thismin > prevmin )
  469.         min = thismin;
  470.  
  471.     prevmin = thismin;
  472.     }
  473. #endif
  474.  
  475.     return detect;
  476. }
  477.  
  478. /* blueloop -- loop up and down from blue center. */
  479. static int
  480. blueloop( restart )
  481. int restart;
  482. {
  483.     int detect;
  484.     register unsigned long *dp;
  485.     register unsigned char *rgbp;
  486.     register long bdist, bxx;
  487.     register int b, i = cindex;
  488.     register long txsqr = xsqr + xsqr;
  489.     register int lim;
  490.     static int here, min, max;
  491. #ifdef MINMAX_TRACK
  492.     static int prevmin, prevmax;
  493.     int thismin, thismax;
  494. #ifdef DMIN_DMAX_TRACK
  495.     static int dmin, dmax;
  496. #endif /* DMIN_DMAX_TRACK */
  497. #endif /* MINMAX_TRACK */
  498.     static long binc;
  499. #ifdef DEBUG
  500.     long dist, tdist;
  501. #endif
  502.  
  503.     if ( restart )
  504.     {
  505.     here = bcenter;
  506.     min = 0;
  507.     max = colormax - 1;
  508.     binc = cbinc;
  509. #ifdef MINMAX_TRACK
  510.     prevmin = colormax;
  511.     prevmax = 0;
  512. #ifdef DMIN_DMAX_TRACK
  513.     dmin = 0;
  514.     dmax = 0;
  515. #endif /* DMIN_DMAX_TRACK */
  516. #endif /* MINMAX_TRACK */
  517.     }
  518.  
  519.     detect = 0;
  520. #ifdef MINMAX_TRACK
  521.     thismin = min;
  522.     thismax = max;
  523. #endif
  524. #ifdef DEBUG
  525.     tdist = cred - red * x - x/2;
  526.     dist = tdist*tdist;
  527.     tdist = cgreen - green * x - x/2;
  528.     dist += tdist*tdist;
  529.     tdist = cblue - here * x - x/2;
  530.     dist += tdist*tdist;
  531.     if ( gdist != dist )
  532.     fprintf( stderr, "*** At %d,%d,%d; dist = %ld != gdist = %ld\n",
  533.          red, green, here, dist, gdist );
  534.     if ( grgbp != zrgbp + red*rstride + green*gstride + here )
  535.     fprintf( stderr, "*** At %d,%d,%d: buffer pointer is at %d,%d,%d\n",
  536.          red, green, here,
  537.          (grgbp - zrgbp) / rstride,
  538.          ((grgbp - zrgbp) % rstride) / gstride,
  539.          (grgbp - zrgbp) % gstride );
  540. #endif /* DEBUG */
  541.  
  542.     /* Basic loop up. */
  543.     /* First loop just finds first applicable cell. */
  544.     for ( b = here, bdist = gdist, bxx = binc, dp = gdp, rgbp = grgbp, lim = max;
  545.       b <= lim;
  546.       b++, dp++, rgbp++,
  547.       bdist += bxx, bxx += txsqr )
  548.     {
  549. #ifdef INSTRUMENT_IT
  550.     outercount++;
  551. #endif
  552.     if ( *dp > bdist )
  553.     {
  554.         /* Remember new 'here' and associated data! */
  555.         if ( b > here )
  556.         {
  557.         here = b;
  558.         gdp = dp;
  559.         grgbp = rgbp;
  560.         gdist = bdist;
  561.         binc = bxx;
  562. #ifdef MINMAX_TRACK
  563.         thismin = here;
  564. #endif
  565. #ifdef DEBUG
  566.         fprintf( stderr, "===Adjusting blue here up at %d,%d,%d\n",
  567.              red, green, here );
  568.  
  569.         tdist = cred - red * x - x/2;
  570.         dist = tdist*tdist;
  571.         tdist = cgreen - green * x - x/2;
  572.         dist += tdist*tdist;
  573.         tdist = cblue - here * x - x/2;
  574.         dist += tdist*tdist;
  575.         if ( gdist != dist )
  576.             fprintf( stderr,
  577.          "*** Adjusting here up at %d,%d,%d; dist = %ld != gdist = %ld\n",
  578.                  red, green, here, dist, gdist );
  579. #endif /* DEBUG */
  580.         }
  581.         detect = 1;
  582. #ifdef INSTRUMENT_IT
  583.         outercount--;
  584. #endif
  585.         break;
  586.     }
  587.     }
  588.     /* Second loop fills in a run of closer cells. */
  589.     for ( ;
  590.       b <= lim;
  591.       b++, dp++, rgbp++,
  592.       bdist += bxx, bxx += txsqr )
  593.     {
  594. #ifdef INSTRUMENT_IT
  595.     outercount++;
  596. #endif
  597.     if ( *dp > bdist )
  598.     {
  599. #ifdef INSTRUMENT_IT
  600.         innercount++;
  601. #endif
  602.         *dp = bdist;
  603.         *rgbp = i;
  604.     }
  605.     else
  606.     {
  607. #ifdef MINMAX_TRACK
  608.         thismax = b - 1;
  609. #endif
  610.         break;
  611.     }
  612.     }
  613. #ifdef DEBUG
  614.     tdist = cred - red * x - x/2;
  615.     dist = tdist*tdist;
  616.     tdist = cgreen - green * x - x/2;
  617.     dist += tdist*tdist;
  618.     tdist = cblue - b * x - x/2;
  619.     dist += tdist*tdist;
  620.     if ( bdist != dist )
  621.     fprintf( stderr,
  622.          "*** After up loop at %d,%d,%d; dist = %ld != bdist = %ld\n",
  623.          red, green, b, dist, bdist );
  624. #endif /* DEBUG */
  625.     
  626.     /* Basic loop down. */
  627.     /* Do initializations here, since the 'find' loop might not get
  628.      * executed. 
  629.      */
  630.     lim = min;
  631.     b = here - 1;
  632.     bxx = binc - txsqr;
  633.     bdist = gdist - bxx;
  634.     dp = gdp - 1;
  635.     rgbp = grgbp - 1;
  636.     /* The 'find' loop is executed only if we didn't already find
  637.      * something.
  638.      */
  639.     if ( !detect )
  640.     for ( ;
  641.           b >= lim;
  642.           b--, dp--, rgbp--,
  643.           bxx -= txsqr, bdist -= bxx )
  644.     {
  645. #ifdef INSTRUMENT_IT
  646.         outercount++;
  647. #endif
  648.         if ( *dp > bdist )
  649.         {
  650.         /* Remember here! */
  651.         /* No test for b against here necessary because b <
  652.          * here by definition.
  653.          */
  654.         here = b;
  655.         gdp = dp;
  656.         grgbp = rgbp;
  657.         gdist = bdist;
  658.         binc = bxx;
  659. #ifdef MINMAX_TRACK
  660.         thismax = here;
  661. #endif
  662.         detect = 1;
  663. #ifdef DEBUG
  664.         fprintf( stderr, "===Adjusting blue here down at %d,%d,%d\n",
  665.              red, green, here );
  666.         tdist = cred - red * x - x/2;
  667.         dist = tdist*tdist;
  668.         tdist = cgreen - green * x - x/2;
  669.         dist += tdist*tdist;
  670.         tdist = cblue - here * x - x/2;
  671.         dist += tdist*tdist;
  672.         if ( gdist != dist )
  673.             fprintf( stderr,
  674.          "*** Adjusting here down at %d,%d,%d; dist = %ld != gdist = %ld\n",
  675.                  red, green, here, dist, gdist );
  676. #endif /* DEBUG */
  677. #ifdef INSTRUMENT_IT
  678.         outercount--;
  679. #endif
  680.         break;
  681.         }
  682.     }
  683.     /* The 'update' loop. */
  684.     for ( ;
  685.       b >= lim;
  686.       b--, dp--, rgbp--,
  687.       bxx -= txsqr, bdist -= bxx )
  688.     {
  689. #ifdef INSTRUMENT_IT
  690.     outercount++;
  691. #endif
  692.     if ( *dp > bdist )
  693.     {
  694. #ifdef INSTRUMENT_IT
  695.         innercount++;
  696. #endif
  697.         *dp = bdist;
  698.         *rgbp = i;
  699.     }
  700.     else
  701.     {
  702. #ifdef MINMAX_TRACK
  703.         thismin = b + 1;
  704. #endif
  705.         break;
  706.     }
  707.     }
  708.  
  709. #ifdef DEBUG
  710.     tdist = cred - red * x - x/2;
  711.     dist = tdist*tdist;
  712.     tdist = cgreen - green * x - x/2;
  713.     dist += tdist*tdist;
  714.     tdist = cblue - b * x - x/2;
  715.     dist += tdist*tdist;
  716.     if ( bdist != dist )
  717.     fprintf( stderr,
  718.          "*** After down loop at %d,%d,%d; dist = %ld != bdist = %ld\n",
  719.          red, green, b, dist, bdist );
  720. #endif /* DEBUG */
  721.  
  722.     /* If we saw something, update the edge trackers. */
  723. #ifdef MINMAX_TRACK
  724.     if ( detect )
  725.     {
  726. #ifdef DMIN_DMAX_TRACK
  727.     /* Predictively track.  Not clear this is a win. */
  728.     /* If there was a previous line, update the dmin/dmax values. */
  729.     if ( prevmax >= prevmin )
  730.     {
  731.         if ( thismin > 0 )
  732.         dmin = thismin - prevmin - 1;
  733.         else
  734.         dmin = 0;
  735.         if ( thismax < colormax - 1 )
  736.         dmax = thismax - prevmax + 1;
  737.         else
  738.         dmax = 0;
  739.         /* Update the min and max values by the differences. */
  740.         max = thismax + dmax;
  741.         if ( max >= colormax )
  742.         max = colormax - 1;
  743.         min = thismin + dmin;
  744.         if ( min < 0 )
  745.         min = 0;
  746.     }
  747. #else /* !DMIN_DMAX_TRACK */
  748.     /* Only tracks edges that are "shrinking" (min increasing, max
  749.      * decreasing.
  750.      */
  751.     if ( thismax < prevmax )
  752.         max = thismax;
  753.  
  754.     if ( thismin > prevmin )
  755.         min = thismin;
  756. #endif /* DMIN_DMAX_TRACK */
  757.     
  758.     /* Remember the min and max values. */
  759.     prevmax = thismax;
  760.     prevmin = thismin;
  761.     }
  762. #endif /* MINMAX_TRACK */
  763.  
  764.     return detect;
  765. }
  766.  
  767. static void
  768. maxfill( buffer, side )
  769. unsigned long *buffer;
  770. long side;
  771. {
  772.     register unsigned long maxv = ~0L;
  773.     register long i;
  774.     register unsigned long *bp;
  775.  
  776.     for ( i = colormax * colormax * colormax, bp = buffer;
  777.       i > 0;
  778.       i--, bp++ )
  779.     *bp = maxv;
  780. }
  781.  
  782. #else /* !NO_INV_CMAP_TRACKING */
  783. /*****************************************************************
  784.  * TAG( inv_cmap )
  785.  *
  786.  * Compute an inverse colormap efficiently.
  787.  * Inputs:
  788.  *     colors:        Number of colors in the forward colormap.
  789.  *     colormap:    The forward colormap.
  790.  *     bits:        Number of quantization bits.  The inverse
  791.  *             colormap will have (2^bits)^3 entries.
  792.  *     dist_buf:    An array of (2^bits)^3 long integers to be
  793.  *             used as scratch space.
  794.  * Outputs:
  795.  *     rgbmap:        The output inverse colormap.  The entry
  796.  *             rgbmap[(r<<(2*bits)) + (g<<bits) + b]
  797.  *             is the colormap entry that is closest to the
  798.  *             (quantized) color (r,g,b).
  799.  * Assumptions:
  800.  *     Quantization is performed by right shift (low order bits are
  801.  *     truncated).  Thus, the distance to a quantized color is
  802.  *     actually measured to the color at the center of the cell
  803.  *     (i.e., to r+.5, g+.5, b+.5, if (r,g,b) is a quantized color).
  804.  * Algorithm:
  805.  *     Uses a "distance buffer" algorithm:
  806.  *     The distance from each representative in the forward color map
  807.  *     to each point in the rgb space is computed.  If it is less
  808.  *     than the distance currently stored in dist_buf, then the
  809.  *     corresponding entry in rgbmap is replaced with the current
  810.  *     representative (and the dist_buf entry is replaced with the
  811.  *     new distance).
  812.  *
  813.  *     The distance computation uses an efficient incremental formulation.
  814.  *
  815.  *     Right now, distances are computed for all entries in the rgb
  816.  *     space.  Thus, the complexity of the algorithm is O(K N^3),
  817.  *     where K = colors, and N = 2^bits.
  818.  */
  819. void
  820. inv_cmap( colors, colormap, bits, dist_buf, rgbmap )
  821. int colors, bits;
  822. unsigned char *colormap[3], *rgbmap;
  823. unsigned long *dist_buf;
  824. {
  825.     register unsigned long *dp;
  826.     register unsigned char *rgbp;
  827.     register long bdist, bxx;
  828.     register int b, i;
  829.     int nbits = 8 - bits;
  830.     register int colormax = 1 << bits;
  831.     register long xsqr = 1 << (2 * nbits);
  832.     int x = 1 << nbits;
  833.     int rinc, ginc, binc, r, g;
  834.     long rdist, gdist, rxx, gxx;
  835. #ifdef INSTRUMENT_IT
  836.     long outercount = 0, innercount = 0;
  837. #endif
  838.  
  839.     for ( i = 0; i < colors; i++ )
  840.     {
  841.     /*
  842.      * Distance formula is
  843.      * (red - map[0])^2 + (green - map[1])^2 + (blue - map[2])^2
  844.      *
  845.      * Because of quantization, we will measure from the center of
  846.      * each quantized "cube", so blue distance is
  847.      *     (blue + x/2 - map[2])^2,
  848.      * where x = 2^(8 - bits).
  849.      * The step size is x, so the blue increment is
  850.      *     2*x*blue - 2*x*map[2] + 2*x^2
  851.      *
  852.      * Now, b in the code below is actually blue/x, so our
  853.      * increment will be 2*x*x*b + (2*x^2 - 2*x*map[2]).  For
  854.      * efficiency, we will maintain this quantity in a separate variable
  855.      * that will be updated incrementally by adding 2*x^2 each time.
  856.      */
  857.     rdist = colormap[0][i] - x/2;
  858.     gdist = colormap[1][i] - x/2;
  859.     bdist = colormap[2][i] - x/2;
  860.     rdist = rdist*rdist + gdist*gdist + bdist*bdist;
  861.  
  862.     rinc = 2 * (xsqr - (colormap[0][i] << nbits));
  863.     ginc = 2 * (xsqr - (colormap[1][i] << nbits));
  864.     binc = 2 * (xsqr - (colormap[2][i] << nbits));
  865.     dp = dist_buf;
  866.     rgbp = rgbmap;
  867.     for ( r = 0, rxx = rinc;
  868.           r < colormax;
  869.           rdist += rxx, r++, rxx += xsqr + xsqr )
  870.         for ( g = 0, gdist = rdist, gxx = ginc;
  871.           g < colormax;
  872.           gdist += gxx, g++, gxx += xsqr + xsqr )
  873.         for ( b = 0, bdist = gdist, bxx = binc;
  874.               b < colormax;
  875.               bdist += bxx, b++, dp++, rgbp++,
  876.               bxx += xsqr + xsqr )
  877.         {
  878. #ifdef INSTRUMENT_IT
  879.             outercount++;
  880. #endif
  881.             if ( i == 0 || *dp > bdist )
  882.             {
  883. #ifdef INSTRUMENT_IT
  884.             innercount++;
  885. #endif
  886.             *dp = bdist;
  887.             *rgbp = i;
  888.             }
  889.         }
  890.     }
  891. #ifdef INSTRUMENT_IT
  892.     fprintf( stderr, "K = %d, N = %d, outer count = %ld, inner count = %ld\n",
  893.          colors, colormax, outercount, innercount );
  894. #endif
  895. }
  896.  
  897. #endif /* NO_INV_CMAP_TRACKING */
  898.