inv_cmap.c File Reference

#include <math.h>
#include <stdio.h>

Include dependency graph for inv_cmap.c:

Go to the source code of this file.

Functions
static void	maxfill ()
static int	redloop ()
static int	greenloop ()
static int	blueloop ()
void	inv_cmap (int colors, colormap, int bits, unsigned long *dist_buf,*rgbmap)
static int	greenloop (int restart)
static int	blueloop (int restart)
static void	maxfill (unsigned long *buffer, long side)

Variables
static int	bcenter
static int	gcenter
static int	rcenter
static long	gdist
static long	rdist
static long	cdist
static long	cbinc
static long	cginc
static long	crinc
static unsigned long *	gdp
static unsigned long *	rdp
static unsigned long *	cdp
static unsigned char *	grgbp
static unsigned char *	rrgbp
static unsigned char *	crgbp
static long	gstride
static long	rstride
static long	x
static long	xsqr
static long	colormax
static int	cindex

Function Documentation

static int blueloop ( )

static

static int blueloop ( int  restart )

static

Definition at line 480 of file inv_cmap.c.

{
    int detect;
    register unsigned long *dp;
    register unsigned char *rgbp;
    register long bdist, bxx;
    register int b, i = cindex;
    register long txsqr = xsqr + xsqr;
    register int lim;
    static int here, min, max;
#ifdef MINMAX_TRACK
    static int prevmin, prevmax;
    int thismin, thismax;
#ifdef DMIN_DMAX_TRACK
    static int dmin, dmax;
#endif /* DMIN_DMAX_TRACK */
#endif /* MINMAX_TRACK */
    static long binc;
#ifdef DEBUG
    long dist, tdist;
#endif

    if ( restart )
    {
    here = bcenter;
    min = 0;
    max = colormax - 1;
    binc = cbinc;
#ifdef MINMAX_TRACK
    prevmin = colormax;
    prevmax = 0;
#ifdef DMIN_DMAX_TRACK
    dmin = 0;
    dmax = 0;
#endif /* DMIN_DMAX_TRACK */
#endif /* MINMAX_TRACK */
    }

    detect = 0;
#ifdef MINMAX_TRACK
    thismin = min;
    thismax = max;
#endif
#ifdef DEBUG
    tdist = cred - red * x - x/2;
    dist = tdist*tdist;
    tdist = cgreen - green * x - x/2;
    dist += tdist*tdist;
    tdist = cblue - here * x - x/2;
    dist += tdist*tdist;
    if ( gdist != dist )
    fprintf( stderr, "*** At %d,%d,%d; dist = %ld != gdist = %ld\n",
         red, green, here, dist, gdist );
    if ( grgbp != zrgbp + red*rstride + green*gstride + here )
    fprintf( stderr, "*** At %d,%d,%d: buffer pointer is at %d,%d,%d\n",
         red, green, here,
         (grgbp - zrgbp) / rstride,
         ((grgbp - zrgbp) % rstride) / gstride,
         (grgbp - zrgbp) % gstride );
#endif /* DEBUG */

    /* Basic loop up. */
    /* First loop just finds first applicable cell. */
    for ( b = here, bdist = gdist, bxx = binc, dp = gdp, rgbp = grgbp, lim = max;
      b <= lim;
      b++, dp++, rgbp++,
      bdist += bxx, bxx += txsqr )
    {
#ifdef INSTRUMENT_IT
    outercount++;
#endif
    if ( *dp > bdist )
    {
        /* Remember new 'here' and associated data! */
        if ( b > here )
        {
        here = b;
        gdp = dp;
        grgbp = rgbp;
        gdist = bdist;
        binc = bxx;
#ifdef MINMAX_TRACK
        thismin = here;
#endif
#ifdef DEBUG
        fprintf( stderr, "===Adjusting blue here up at %d,%d,%d\n",
             red, green, here );

        tdist = cred - red * x - x/2;
        dist = tdist*tdist;
        tdist = cgreen - green * x - x/2;
        dist += tdist*tdist;
        tdist = cblue - here * x - x/2;
        dist += tdist*tdist;
        if ( gdist != dist )
            fprintf( stderr,
         "*** Adjusting here up at %d,%d,%d; dist = %ld != gdist = %ld\n",
                 red, green, here, dist, gdist );
#endif /* DEBUG */
        }
        detect = 1;
#ifdef INSTRUMENT_IT
        outercount--;
#endif
        break;
    }
    }
    /* Second loop fills in a run of closer cells. */
    for ( ;
      b <= lim;
      b++, dp++, rgbp++,
      bdist += bxx, bxx += txsqr )
    {
#ifdef INSTRUMENT_IT
    outercount++;
#endif
    if ( *dp > bdist )
    {
#ifdef INSTRUMENT_IT
        innercount++;
#endif
        *dp = bdist;
        *rgbp = i;
    }
    else
    {
#ifdef MINMAX_TRACK
        thismax = b - 1;
#endif
        break;
    }
    }
#ifdef DEBUG
    tdist = cred - red * x - x/2;
    dist = tdist*tdist;
    tdist = cgreen - green * x - x/2;
    dist += tdist*tdist;
    tdist = cblue - b * x - x/2;
    dist += tdist*tdist;
    if ( bdist != dist )
    fprintf( stderr,
         "*** After up loop at %d,%d,%d; dist = %ld != bdist = %ld\n",
         red, green, b, dist, bdist );
#endif /* DEBUG */
    
    /* Basic loop down. */
    /* Do initializations here, since the 'find' loop might not get
     * executed. 
     */
    lim = min;
    b = here - 1;
    bxx = binc - txsqr;
    bdist = gdist - bxx;
    dp = gdp - 1;
    rgbp = grgbp - 1;
    /* The 'find' loop is executed only if we didn't already find
     * something.
     */
    if ( !detect )
    for ( ;
          b >= lim;
          b--, dp--, rgbp--,
          bxx -= txsqr, bdist -= bxx )
    {
#ifdef INSTRUMENT_IT
        outercount++;
#endif
        if ( *dp > bdist )
        {
        /* Remember here! */
        /* No test for b against here necessary because b <
         * here by definition.
         */
        here = b;
        gdp = dp;
        grgbp = rgbp;
        gdist = bdist;
        binc = bxx;
#ifdef MINMAX_TRACK
        thismax = here;
#endif
        detect = 1;
#ifdef DEBUG
        fprintf( stderr, "===Adjusting blue here down at %d,%d,%d\n",
             red, green, here );
        tdist = cred - red * x - x/2;
        dist = tdist*tdist;
        tdist = cgreen - green * x - x/2;
        dist += tdist*tdist;
        tdist = cblue - here * x - x/2;
        dist += tdist*tdist;
        if ( gdist != dist )
            fprintf( stderr,
         "*** Adjusting here down at %d,%d,%d; dist = %ld != gdist = %ld\n",
                 red, green, here, dist, gdist );
#endif /* DEBUG */
#ifdef INSTRUMENT_IT
        outercount--;
#endif
        break;
        }
    }
    /* The 'update' loop. */
    for ( ;
      b >= lim;
      b--, dp--, rgbp--,
      bxx -= txsqr, bdist -= bxx )
    {
#ifdef INSTRUMENT_IT
    outercount++;
#endif
    if ( *dp > bdist )
    {
#ifdef INSTRUMENT_IT
        innercount++;
#endif
        *dp = bdist;
        *rgbp = i;
    }
    else
    {
#ifdef MINMAX_TRACK
        thismin = b + 1;
#endif
        break;
    }
    }

#ifdef DEBUG
    tdist = cred - red * x - x/2;
    dist = tdist*tdist;
    tdist = cgreen - green * x - x/2;
    dist += tdist*tdist;
    tdist = cblue - b * x - x/2;
    dist += tdist*tdist;
    if ( bdist != dist )
    fprintf( stderr,
         "*** After down loop at %d,%d,%d; dist = %ld != bdist = %ld\n",
         red, green, b, dist, bdist );
#endif /* DEBUG */

    /* If we saw something, update the edge trackers. */
#ifdef MINMAX_TRACK
    if ( detect )
    {
#ifdef DMIN_DMAX_TRACK
    /* Predictively track.  Not clear this is a win. */
    /* If there was a previous line, update the dmin/dmax values. */
    if ( prevmax >= prevmin )
    {
        if ( thismin > 0 )
        dmin = thismin - prevmin - 1;
        else
        dmin = 0;
        if ( thismax < colormax - 1 )
        dmax = thismax - prevmax + 1;
        else
        dmax = 0;
        /* Update the min and max values by the differences. */
        max = thismax + dmax;
        if ( max >= colormax )
        max = colormax - 1;
        min = thismin + dmin;
        if ( min < 0 )
        min = 0;
    }
#else /* !DMIN_DMAX_TRACK */
    /* Only tracks edges that are "shrinking" (min increasing, max
     * decreasing.
     */
    if ( thismax < prevmax )
        max = thismax;

    if ( thismin > prevmin )
        min = thismin;
#endif /* DMIN_DMAX_TRACK */
    
    /* Remember the min and max values. */
    prevmax = thismax;
    prevmin = thismin;
    }
#endif /* MINMAX_TRACK */

    return detect;
}

static int greenloop ( )

static

static int greenloop ( int  restart )

static

Definition at line 339 of file inv_cmap.c.

Referenced by redloop().

{
    int detect;
    int g;
    int first;
    long txsqr = xsqr + xsqr;
    static int here, min, max;
#ifdef MINMAX_TRACK
    static int prevmax, prevmin;
    int thismax, thismin;
#endif
    static long ginc, gxx, gcdist;  /* "gc" variables maintain correct */
    static unsigned long *gcdp;     /*  values for bcenter position, */
    static unsigned char *gcrgbp;   /*  despite modifications by blueloop */
                    /*  to gdist, gdp, grgbp. */

    if ( restart )
    {
    here = gcenter;
    min = 0;
    max = colormax - 1;
    ginc = cginc;
#ifdef MINMAX_TRACK
    prevmax = 0;
    prevmin = colormax;
#endif
    }

#ifdef MINMAX_TRACK
    thismin = min;
    thismax = max;
#endif
    detect = 0;

    /* Basic loop up. */
    for ( g = here, gcdist = gdist = rdist, gxx = ginc,
      gcdp = gdp = rdp, gcrgbp = grgbp = rrgbp, first = 1;
      g <= max;
      g++, gdp += gstride, gcdp += gstride, grgbp += gstride, gcrgbp += gstride,
      gdist += gxx, gcdist += gxx, gxx += txsqr, first = 0 )
    {
#ifdef DEBUG
    green = g;
#endif
    if ( blueloop( first ) )
    {
        if ( !detect )
        {
        /* Remember here and associated data! */
        if ( g > here )
        {
            here = g;
            rdp = gcdp;
            rrgbp = gcrgbp;
            rdist = gcdist;
            ginc = gxx;
#ifdef MINMAX_TRACK
            thismin = here;
#endif
#ifdef DEBUG
            fprintf( stderr, "===Adjusting green here up at %d,%d\n",
                 red, here );
#endif
        }
        detect = 1;
        }
    }
    else if ( detect )
    {
#ifdef MINMAX_TRACK
        thismax = g - 1;
#endif
        break;
    }
    }
    
    /* Basic loop down. */
    for ( g = here - 1, gxx = ginc - txsqr, gcdist = gdist = rdist - gxx,
      gcdp = gdp = rdp - gstride, gcrgbp = grgbp = rrgbp - gstride,
      first = 1;
      g >= min;
      g--, gdp -= gstride, gcdp -= gstride, grgbp -= gstride, gcrgbp -= gstride,
      gxx -= txsqr, gdist -= gxx, gcdist -= gxx, first = 0 )
    {
#ifdef DEBUG
    green = g;
#endif
    if ( blueloop( first ) )
    {
        if ( !detect )
        {
        /* Remember here! */
        here = g;
        rdp = gcdp;
        rrgbp = gcrgbp;
        rdist = gcdist;
        ginc = gxx;
#ifdef MINMAX_TRACK
        thismax = here;
#endif
#ifdef DEBUG
        fprintf( stderr, "===Adjusting green here down at %d,%d\n",
             red, here );
#endif
        detect = 1;
        }
    }
    else if ( detect )
    {
#ifdef MINMAX_TRACK
        thismin = g + 1;
#endif
        break;
    }
    }
    
#ifdef MINMAX_TRACK
    /* If we saw something, update the edge trackers.  For now, only
     * tracks edges that are "shrinking" (min increasing, max
     * decreasing.
     */
    if ( detect )
    {
    if ( thismax < prevmax )
        max = thismax;

    prevmax = thismax;

    if ( thismin > prevmin )
        min = thismin;

    prevmin = thismin;
    }
#endif

    return detect;
}

Here is the caller graph for this function:

void inv_cmap	(	int	colors,
		colormap	,
		int	bits,
		unsigned long *	dist_buf,
		*	rgbmap
	)

Definition at line 214 of file inv_cmap.c.

{
    int nbits = 8 - bits;

    colormax = 1 << bits;
    x = 1 << nbits;
    xsqr = 1 << (2 * nbits);

    /* Compute "strides" for accessing the arrays. */
    gstride = colormax;
    rstride = colormax * colormax;

#ifdef INSTRUMENT_IT
    outercount = 0;
    innercount = 0;
#endif
    maxfill( dist_buf, colormax );

    for ( cindex = 0; cindex < colors; cindex++ )
    {
    /*
     * Distance formula is
     * (red - map[0])^2 + (green - map[1])^2 + (blue - map[2])^2
     *
     * Because of quantization, we will measure from the center of
     * each quantized "cube", so blue distance is
     *  (blue + x/2 - map[2])^2,
     * where x = 2^(8 - bits).
     * The step size is x, so the blue increment is
     *  2*x*blue - 2*x*map[2] + 2*x^2
     *
     * Now, b in the code below is actually blue/x, so our
     * increment will be 2*(b*x^2 + x^2 - x*map[2]).  For
     * efficiency, we will maintain this quantity in a separate variable
     * that will be updated incrementally by adding 2*x^2 each time.
     */
    /* The initial position is the cell containing the colormap
     * entry.  We get this by quantizing the colormap values.
     */
    rcenter = colormap[0][cindex] >> nbits;
    gcenter = colormap[1][cindex] >> nbits;
    bcenter = colormap[2][cindex] >> nbits;
#ifdef DEBUG
    cred = colormap[0][cindex];
    cgreen = colormap[1][cindex];
    cblue = colormap[2][cindex];
    fprintf( stderr, "---Starting %d: %d,%d,%d -> %d,%d,%d\n",
         cindex, cred, cgreen, cblue,
         rcenter, gcenter, bcenter );
    zrgbp = rgbmap;
#endif

    rdist = colormap[0][cindex] - (rcenter * x + x/2);
    gdist = colormap[1][cindex] - (gcenter * x + x/2);
    cdist = colormap[2][cindex] - (bcenter * x + x/2);
    cdist = rdist*rdist + gdist*gdist + cdist*cdist;

    crinc = 2 * ((rcenter + 1) * xsqr - (colormap[0][cindex] * x));
    cginc = 2 * ((gcenter + 1) * xsqr - (colormap[1][cindex] * x));
    cbinc = 2 * ((bcenter + 1) * xsqr - (colormap[2][cindex] * x));

    /* Array starting points. */
    cdp = dist_buf + rcenter * rstride + gcenter * gstride + bcenter;
    crgbp = rgbmap + rcenter * rstride + gcenter * gstride + bcenter;

    (void)redloop();
    }
#ifdef INSTRUMENT_IT
    fprintf( stderr, "K = %d, N = %d, outer count = %ld, inner count = %ld\n",
         colors, colormax, outercount, innercount );
#endif
}

static void maxfill ( )

static

static void maxfill ( unsigned long *  buffer, long  side  )

static

Definition at line 768 of file inv_cmap.c.

{
    register unsigned long maxv = ~0L;
    register long i;
    register unsigned long *bp;

    for ( i = colormax * colormax * colormax, bp = buffer;
      i > 0;
      i--, bp++ )
    *bp = maxv;
}

static int redloop ( )

static

Definition at line 292 of file inv_cmap.c.

References cdist, cdp, colormax, crgbp, crinc, greenloop(), rcenter, rdist, rdp, rrgbp, rstride, and xsqr.

{
    int detect;
    int r;
    int first;
    long txsqr = xsqr + xsqr;
    static long rxx;

    detect = 0;

    /* Basic loop up. */
    for ( r = rcenter, rdist = cdist, rxx = crinc,
      rdp = cdp, rrgbp = crgbp, first = 1;
      r < colormax;
      r++, rdp += rstride, rrgbp += rstride,
      rdist += rxx, rxx += txsqr, first = 0 )
    {
#ifdef DEBUG
    red = r;
#endif
    if ( greenloop( first ) )
        detect = 1;
    else if ( detect )
        break;
    }
    
    /* Basic loop down. */
    for ( r = rcenter - 1, rxx = crinc - txsqr, rdist = cdist - rxx,
      rdp = cdp - rstride, rrgbp = crgbp - rstride, first = 1;
      r >= 0;
      r--, rdp -= rstride, rrgbp -= rstride,
      rxx -= txsqr, rdist -= rxx, first = 0 )
    {
#ifdef DEBUG
    red = r;
#endif
    if ( greenloop( first ) )
        detect = 1;
    else if ( detect )
        break;
    }
    
    return detect;
}

Here is the call graph for this function:

Variable Documentation

int bcenter

static

Definition at line 40 of file inv_cmap.c.

long cbinc

static

Definition at line 42 of file inv_cmap.c.

long cdist

static

Definition at line 41 of file inv_cmap.c.

Referenced by redloop().

unsigned long * cdp

static

Definition at line 43 of file inv_cmap.c.

Referenced by redloop().

long cginc

static

Definition at line 42 of file inv_cmap.c.

int cindex

static

Definition at line 47 of file inv_cmap.c.

long colormax

static

Definition at line 46 of file inv_cmap.c.

Referenced by redloop().

unsigned char * crgbp

static

Definition at line 44 of file inv_cmap.c.

Referenced by redloop().

long crinc

static

Definition at line 42 of file inv_cmap.c.

Referenced by redloop().

int gcenter

static

Definition at line 40 of file inv_cmap.c.

long gdist

static

Definition at line 41 of file inv_cmap.c.

unsigned long* gdp

static

Definition at line 43 of file inv_cmap.c.

unsigned char* grgbp

static

Definition at line 44 of file inv_cmap.c.

long gstride

static

Definition at line 45 of file inv_cmap.c.

int rcenter

static

Definition at line 40 of file inv_cmap.c.

Referenced by redloop().

long rdist

static

Definition at line 41 of file inv_cmap.c.

Referenced by redloop().

unsigned long * rdp

static

Definition at line 43 of file inv_cmap.c.

Referenced by redloop().

unsigned char * rrgbp

static

Definition at line 44 of file inv_cmap.c.

Referenced by redloop().

long rstride

static

Definition at line 45 of file inv_cmap.c.

Referenced by redloop().

long x

static

Definition at line 46 of file inv_cmap.c.

long xsqr

static

Definition at line 46 of file inv_cmap.c.

Referenced by redloop().