gd_topal.c

下载来的一个看图软件的源代码

	  if (x <= centerc0)
	    {
	      tdist = (x - maxc0) * C0_SCALE;
	      max_dist = tdist * tdist;
	    }
	  else
	    {
	      tdist = (x - minc0) * C0_SCALE;
	      max_dist = tdist * tdist;
	    }
	}

      x = im->green[i];
      if (x < minc1)
	{
	  tdist = (x - minc1) * C1_SCALE;
	  min_dist += tdist * tdist;
	  tdist = (x - maxc1) * C1_SCALE;
	  max_dist += tdist * tdist;
	}
      else if (x > maxc1)
	{
	  tdist = (x - maxc1) * C1_SCALE;
	  min_dist += tdist * tdist;
	  tdist = (x - minc1) * C1_SCALE;
	  max_dist += tdist * tdist;
	}
      else
	{
	  /* within cell range so no contribution to min_dist */
	  if (x <= centerc1)
	    {
	      tdist = (x - maxc1) * C1_SCALE;
	      max_dist += tdist * tdist;
	    }
	  else
	    {
	      tdist = (x - minc1) * C1_SCALE;
	      max_dist += tdist * tdist;
	    }
	}

      x = im->blue[i];
      if (x < minc2)
	{
	  tdist = (x - minc2) * C2_SCALE;
	  min_dist += tdist * tdist;
	  tdist = (x - maxc2) * C2_SCALE;
	  max_dist += tdist * tdist;
	}
      else if (x > maxc2)
	{
	  tdist = (x - maxc2) * C2_SCALE;
	  min_dist += tdist * tdist;
	  tdist = (x - minc2) * C2_SCALE;
	  max_dist += tdist * tdist;
	}
      else
	{
	  /* within cell range so no contribution to min_dist */
	  if (x <= centerc2)
	    {
	      tdist = (x - maxc2) * C2_SCALE;
	      max_dist += tdist * tdist;
	    }
	  else
	    {
	      tdist = (x - minc2) * C2_SCALE;
	      max_dist += tdist * tdist;
	    }
	}

      x = im->alpha[i];
      if (x < minc3)
	{
	  tdist = (x - minc3) * C3_SCALE;
	  min_dist += tdist * tdist;
	  tdist = (x - maxc3) * C3_SCALE;
	  max_dist += tdist * tdist;
	}
      else if (x > maxc3)
	{
	  tdist = (x - maxc3) * C3_SCALE;
	  min_dist += tdist * tdist;
	  tdist = (x - minc3) * C3_SCALE;
	  max_dist += tdist * tdist;
	}
      else
	{
	  /* within cell range so no contribution to min_dist */
	  if (x <= centerc3)
	    {
	      tdist = (x - maxc3) * C3_SCALE;
	      max_dist += tdist * tdist;
	    }
	  else
	    {
	      tdist = (x - minc3) * C3_SCALE;
	      max_dist += tdist * tdist;
	    }
	}

      mindist[i] = min_dist;	/* save away the results */
      if (max_dist < minmaxdist)
	minmaxdist = max_dist;
    }

  /* Now we know that no cell in the update box is more than minmaxdist
   * away from some colormap entry.  Therefore, only colors that are
   * within minmaxdist of some part of the box need be considered.
   */
  ncolors = 0;
  for (i = 0; i < numcolors; i++)
    {
      if (mindist[i] <= minmaxdist)
	colorlist[ncolors++] = i;
    }
  return ncolors;
}


static void
find_best_colors (gdImagePtr im, my_cquantize_ptr cquantize,
		  int minc0, int minc1, int minc2, int minc3,
		  int numcolors, int colorlist[], int bestcolor[])
/* Find the closest colormap entry for each cell in the update box,
 * given the list of candidate colors prepared by find_nearby_colors.
 * Return the indexes of the closest entries in the bestcolor[] array.
 * This routine uses Thomas' incremental distance calculation method to
 * find the distance from a colormap entry to successive cells in the box.
 */
{
  int ic0, ic1, ic2, ic3;
  int i, icolor;
  register int *bptr;		/* pointer into bestdist[] array */
  int *cptr;			/* pointer into bestcolor[] array */
  int dist0, dist1, dist2;	/* initial distance values */
  register int dist3;		/* current distance in inner loop */
  int xx0, xx1, xx2;		/* distance increments */
  register int xx3;
  int inc0, inc1, inc2, inc3;	/* initial values for increments */
  /* This array holds the distance to the nearest-so-far color for each cell */
  int bestdist[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS * BOX_C3_ELEMS];

  /* Initialize best-distance for each cell of the update box */
  bptr = bestdist;
  for (i = BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS * BOX_C3_ELEMS - 1; i >= 0; i--)
    *bptr++ = 0x7FFFFFFFL;

  /* For each color selected by find_nearby_colors,
   * compute its distance to the center of each cell in the box.
   * If that's less than best-so-far, update best distance and color number.
   */

  /* Nominal steps between cell centers ("x" in Thomas article) */
#define STEP_C0  ((1 << C0_SHIFT) * C0_SCALE)
#define STEP_C1  ((1 << C1_SHIFT) * C1_SCALE)
#define STEP_C2  ((1 << C2_SHIFT) * C2_SCALE)
#define STEP_C3  ((1 << C3_SHIFT) * C3_SCALE)

  for (i = 0; i < numcolors; i++)
    {
      icolor = colorlist[i];
      /* Compute (square of) distance from minc0/c1/c2 to this color */
      inc0 = (minc0 - (im->red[icolor])) * C0_SCALE;
      dist0 = inc0 * inc0;
      inc1 = (minc1 - (im->green[icolor])) * C1_SCALE;
      dist0 += inc1 * inc1;
      inc2 = (minc2 - (im->blue[icolor])) * C2_SCALE;
      dist0 += inc2 * inc2;
      inc3 = (minc3 - (im->alpha[icolor])) * C3_SCALE;
      dist0 += inc3 * inc3;
      /* Form the initial difference increments */
      inc0 = inc0 * (2 * STEP_C0) + STEP_C0 * STEP_C0;
      inc1 = inc1 * (2 * STEP_C1) + STEP_C1 * STEP_C1;
      inc2 = inc2 * (2 * STEP_C2) + STEP_C2 * STEP_C2;
      inc3 = inc3 * (2 * STEP_C3) + STEP_C3 * STEP_C3;
      /* Now loop over all cells in box, updating distance per Thomas method */
      bptr = bestdist;
      cptr = bestcolor;
      xx0 = inc0;
      for (ic0 = BOX_C0_ELEMS - 1; ic0 >= 0; ic0--)
	{
	  dist1 = dist0;
	  xx1 = inc1;
	  for (ic1 = BOX_C1_ELEMS - 1; ic1 >= 0; ic1--)
	    {
	      dist2 = dist1;
	      xx2 = inc2;
	      for (ic2 = BOX_C2_ELEMS - 1; ic2 >= 0; ic2--)
		{
		  for (ic3 = BOX_C3_ELEMS - 1; ic3 >= 0; ic3--)
		    {
		      if (dist3 < *bptr)
			{
			  *bptr = dist3;
			  *cptr = icolor;
			}
		      dist3 += xx3;
		      xx3 += 2 * STEP_C3 * STEP_C3;
		      bptr++;
		      cptr++;
		    }
		  dist2 += xx2;
		  xx2 += 2 * STEP_C2 * STEP_C2;
		}
	      dist1 += xx1;
	      xx1 += 2 * STEP_C1 * STEP_C1;
	    }
	  dist0 += xx0;
	  xx0 += 2 * STEP_C0 * STEP_C0;
	}
    }
}


static void
fill_inverse_cmap (gdImagePtr im, my_cquantize_ptr cquantize,
		   int c0, int c1, int c2, int c3)
/* Fill the inverse-colormap entries in the update box that contains */
/* histogram cell c0/c1/c2/c3.  (Only that one cell MUST be filled, but */
/* we can fill as many others as we wish.) */
{
  hist4d histogram = cquantize->histogram;
  int minc0, minc1, minc2, minc3;	/* lower left corner of update box */
  int ic0, ic1, ic2, ic3;
  register int *cptr;		/* pointer into bestcolor[] array */
  register histptr cachep;	/* pointer into main cache array */
  /* This array lists the candidate colormap indexes. */
  int colorlist[MAXNUMCOLORS];
  int numcolors;		/* number of candidate colors */
  /* This array holds the actually closest colormap index for each cell. */
  int bestcolor[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS * BOX_C3_ELEMS];

  /* Convert cell coordinates to update box ID */
  c0 >>= BOX_C0_LOG;
  c1 >>= BOX_C1_LOG;
  c2 >>= BOX_C2_LOG;
  c3 >>= BOX_C3_LOG;

  /* Compute true coordinates of update box's origin corner.
   * Actually we compute the coordinates of the center of the corner
   * histogram cell, which are the lower bounds of the volume we care about.
   */
  minc0 = (c0 << BOX_C0_SHIFT) + ((1 << C0_SHIFT) >> 1);
  minc1 = (c1 << BOX_C1_SHIFT) + ((1 << C1_SHIFT) >> 1);
  minc2 = (c2 << BOX_C2_SHIFT) + ((1 << C2_SHIFT) >> 1);
  minc3 = (c3 << BOX_C3_SHIFT) + ((1 << C3_SHIFT) >> 1);
  /* Determine which colormap entries are close enough to be candidates
   * for the nearest entry to some cell in the update box.
   */
  numcolors = find_nearby_colors (im, cquantize, minc0, minc1, minc2, minc3, colorlist);

  /* Determine the actually nearest colors. */
  find_best_colors (im, cquantize, minc0, minc1, minc2, minc3, numcolors, colorlist,
		    bestcolor);

  /* Save the best color numbers (plus 1) in the main cache array */
  c0 <<= BOX_C0_LOG;		/* convert ID back to base cell indexes */
  c1 <<= BOX_C1_LOG;
  c2 <<= BOX_C2_LOG;
  c3 <<= BOX_C3_LOG;
  cptr = bestcolor;
  for (ic0 = 0; ic0 < BOX_C0_ELEMS; ic0++)
    {
      for (ic1 = 0; ic1 < BOX_C1_ELEMS; ic1++)
	{
	  for (ic2 = 0; ic2 < BOX_C2_ELEMS; ic2++)
	    {
	      cachep = &histogram[c0 + ic0][c1 + ic1][c2 + ic2][c3];
	      for (ic3 = 0; ic3 < BOX_C3_ELEMS; ic3++)
		{
		  *cachep++ = (histcell) ((*cptr++) + 1);
		}
	    }
	}
    }
}


/*
 * Map some rows of pixels to the output colormapped representation.
 */

void
pass2_no_dither (gdImagePtr im, my_cquantize_ptr cquantize)
/* This version performs no dithering */
{
  hist4d histogram = cquantize->histogram;
  register int *inptr;
  register unsigned char *outptr;
  register histptr cachep;
  register int c0, c1, c2, c3;
  int row;
  int col;
  int width = im->sx;
  int num_rows = im->sy;
  for (row = 0; row < num_rows; row++)
    {
      inptr = im->tpixels[row];
      outptr = im->pixels[row];
      for (col = 0; col < width; col++)
	{
	  int r, g, b, a;
	  /* get pixel value and index into the cache */
	  r = gdTrueColorGetRed (*inptr);
	  g = gdTrueColorGetGreen (*inptr);
	  b = gdTrueColorGetBlue (*inptr);
	  a = gdTrueColorGetAlpha (*inptr++);
	  c0 = r >> C0_SHIFT;
	  c1 = g >> C1_SHIFT;
	  c2 = b >> C2_SHIFT;
	  c3 = a >> C3_SHIFT;
	  cachep = &histogram[c0][c1][c2][c3];
	  /* If we have not seen this color before, find nearest colormap entry */
	  /* and update the cache */
	  if (*cachep == 0)
	    {
#if 0
	      /* TBB: quick and dirty approach for use when testing
	         fill_inverse_cmap for errors */
	      int i;
	      int best = -1;
	      int mindist = 0x7FFFFFFF;
	      for (i = 0; (i < im->colorsTotal); i++)
		{
		  int rdist = (im->red[i] >> C0_SHIFT) - c0;
		  int gdist = (im->green[i] >> C1_SHIFT) - c1;
		  int bdist = (im->blue[i] >> C2_SHIFT) - c2;
		  int adist = (im->alpha[i] >> C3_SHIFT) - c3;
		  int dist = (rdist * rdist) * R_SCALE +
		  (gdist * gdist) * G_SCALE +
		  (bdist * bdist) * B_SCALE +
		  (adist * adist) * A_SCALE;
		  if (dist < mindist)
		    {
		      best = i;
		      mindist = dist;
		    }
		}
	      *cachep = best + 1;
#endif
	      fill_inverse_cmap (im, cquantize, c0, c1, c2, c3);
	    }
	  /* Now emit the colormap index for this cell */
	  *outptr++ = (*cachep - 1);
	}
    }
}

/* We assume that right shift corresponds to signed division by 2 with
 * rounding towards minus infinity.  This is correct for typical "arithmetic
 * shift" instructions that shift in copies of the sign bit.  But some
 * C compilers implement >> with an unsigned shift.  For these machines you
 * must define RIGHT_SHIFT_IS_UNSIGNED.
 * RIGHT_SHIFT provides a proper signed right shift of an INT32 quantity.
 * It is only applied with constant shift counts.  SHIFT_TEMPS must be
 * included in the variables of any routine using RIGHT_SHIFT.
 */

#ifdef RIGHT_SHIFT_IS_UNSIGNED
#define SHIFT_TEMPS	INT32 shift_temp;
#define RIGHT_SHIFT(x,shft)  \
	((shift_temp = (x)) < 0 ? \
	 (shift_temp >> (shft)) | ((~((INT32) 0)) << (32-(shft))) : \
	 (shift_temp >> (shft)))
#else
#define SHIFT_TEMPS
#define RIGHT_SHIFT(x,shft)	((x) >> (shft))
#endif


void
pass2_fs_dither (gdImagePtr im, my_cquantize_ptr cquantize)

/* This version performs Floyd-Steinberg dithering */
{
  hist4d histogram = cquantize->histogram;
  register LOCFSERROR cur0, cur1, cur2, cur3;	/* current error or pixel value */
  LOCFSERROR belowerr0, belowerr1, belowerr2, belowerr3;	/* error for pixel below cur */
  LOCFSERROR bpreverr0, bpreverr1, bpreverr2, bpreverr3;	/* error for below/prev col */
  register FSERRPTR errorptr;	/* => fserrors[] at column before current */
  int *inptr;			/* => current input pixel */
  unsigned char *outptr;	/* => current output pixel */
  histptr cachep;
  int dir;			/* +1 or -1 depending on direction */
  int dir4;			/* 4*dir, for advancing errorptr */
  int row;
  int col;
  int width = im->sx;
  int num_rows = im->sy;
  int *error_limit = cquantize->error_limiter;
  int *colormap0 = im->red;
  int *colormap1 = im->green;
  int *colormap2 = im->blue;
  int *colormap3 = im->alpha;
  SHIFT_TEMPS

    for (row = 0; row < num_rows; row++)
    {
      inptr = im->tpixels[row];
      outptr = im->pixels[row];
      if (cquantize->on_odd_row)
	{
	  /* work right to left in this row */
	  inptr += (width - 1);	/* so point to rightmost pixel */
	  outptr += width - 1;
	  dir = -1;
	  dir4 = -4;
	  errorptr = cquantize->fserrors + (width + 1) * 4;	/* => entry after last column */
	  cquantize->on_odd_row = FALSE;	/* flip for next time */
	}
      else
	{
	  /* work left to right in this row */
	  dir = 1;
	  dir4 = 4;
	  errorptr = cquantize->fserrors;	/* => entry before first real column */
	  cquantize->on_odd_row = TRUE;		/* flip for next time */
	}
      /* Preset error values: no error propagated to first pixel from left */
      cur0 = cur1 = cur2 = cur3 = 0;
      /* and no error propagated to row below yet */