/* * This software is copyrighted as noted below. It may be freely copied, * modified, and redistributed, provided that the copyright notice is * preserved on all copies. * * There is no warranty or other guarantee of fitness for this software, * it is provided solely "as is". Bug reports or fixes may be sent * to the author, who may or may not act on them as he desires. * * You may not include this software in a program or other software product * without supplying the source, or without informing the end-user that the * source is available for no extra charge. * * If you modify this software, you should include a notice giving the * name of the person performing the modification, the date of modification, * and the reason for such modification. */ /* * inv_cmap.c - Compute an inverse colormap. * * Author: Spencer W. Thomas * EECS Dept. * University of Michigan * Date: Thu Sep 20 1990 * Copyright (c) 1990, University of Michigan * * $Id: inv_cmap.c,v 1.1.1.1 1993/10/05 08:51:53 ljo Exp $ */ #include #include #ifndef NO_INV_CMAP_TRACKING #ifdef DEBUG static int cred, cgreen, cblue; static int red, green; static unsigned char *zrgbp; #endif DEBUG static int bcenter, gcenter, rcenter; static long gdist, rdist, cdist; static long cbinc, cginc, crinc; static unsigned long *gdp, *rdp, *cdp; static unsigned char *grgbp, *rrgbp, *crgbp; static gstride, rstride; static long x, xsqr, colormax; static int cindex; #ifdef INSTRUMENT_IT static long outercount = 0, innercount = 0; #endif /***************************************************************** * TAG( inv_cmap ) * * Compute an inverse colormap efficiently. * Inputs: * colors: Number of colors in the forward colormap. * colormap: The forward colormap. * bits: Number of quantization bits. The inverse * colormap will have (2^bits)^3 entries. * dist_buf: An array of (2^bits)^3 long integers to be * used as scratch space. * Outputs: * rgbmap: The output inverse colormap. The entry * rgbmap[(r<<(2*bits)) + (g<> 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 } /* redloop -- loop up and down from red center. */ int redloop() { int detect; int r, i = cindex; int first; long txsqr = xsqr + xsqr; static int here, min, max; 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; } /* greenloop -- loop up and down from green center. */ int greenloop( restart ) { int detect; int g, i = cindex; 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; } /* blueloop -- loop up and down from blue center. */ int blueloop( restart ) { 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; } maxfill( buffer, side ) unsigned long *buffer; long side; { 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; } #else /* !NO_INV_CMAP_TRACKING */ /***************************************************************** * TAG( inv_cmap ) * * Compute an inverse colormap efficiently. * Inputs: * colors: Number of colors in the forward colormap. * colormap: The forward colormap. * bits: Number of quantization bits. The inverse * colormap will have (2^bits)^3 entries. * dist_buf: An array of (2^bits)^3 long integers to be * used as scratch space. * Outputs: * rgbmap: The output inverse colormap. The entry * rgbmap[(r<<(2*bits)) + (g< bdist ) { #ifdef INSTRUMENT_IT innercount++; #endif *dp = bdist; *rgbp = i; } } } #ifdef INSTRUMENT_IT fprintf( stderr, "K = %d, N = %d, outer count = %ld, inner count = %ld\n", colors, colormax, outercount, innercount ); #endif } #endif /* NO_INV_CMAP_TRACKING */