gd_topal.c

Linux/Unix下的绘图函数库（Graphic Drawing Library）

  long colorcount;
}
box;

typedef box *boxptr;


LOCAL (boxptr) find_biggest_color_pop (boxptr boxlist, int numboxes)
/* Find the splittable box with the largest color population */
/* Returns NULL if no splittable boxes remain */
{
  register boxptr boxp;
  register int i;
  register long maxc = 0;
  boxptr which = NULL;

  for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++)
    {
      if (boxp->colorcount > maxc && boxp->volume > 0)
	{
	  which = boxp;
	  maxc = boxp->colorcount;
	}
    }
  return which;
}


LOCAL (boxptr) find_biggest_volume (boxptr boxlist, int numboxes)
/* Find the splittable box with the largest (scaled) volume */
/* Returns NULL if no splittable boxes remain */
{
  register boxptr boxp;
  register int i;
  register INT32 maxv = 0;
  boxptr which = NULL;

  for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++)
    {
      if (boxp->volume > maxv)
	{
	  which = boxp;
	  maxv = boxp->volume;
	}
    }
  return which;
}


LOCAL (void)
#ifndef ORIGINAL_LIB_JPEG
  update_box (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize, boxptr boxp)
{
#else
  update_box (j_decompress_ptr cinfo, boxptr boxp)
/* Shrink the min/max bounds of a box to enclose only nonzero elements, */
/* and recompute its volume and population */
{
  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
#endif
  hist3d histogram = cquantize->histogram;
  histptr histp;
  int c0, c1, c2;
  int c0min, c0max, c1min, c1max, c2min, c2max;
  INT32 dist0, dist1, dist2;
  long ccount;

  c0min = boxp->c0min;
  c0max = boxp->c0max;
  c1min = boxp->c1min;
  c1max = boxp->c1max;
  c2min = boxp->c2min;
  c2max = boxp->c2max;

  if (c0max > c0min)
    for (c0 = c0min; c0 <= c0max; c0++)
      for (c1 = c1min; c1 <= c1max; c1++)
	{
	  histp = &histogram[c0][c1][c2min];
	  for (c2 = c2min; c2 <= c2max; c2++)
	    if (*histp++ != 0)
	      {
		boxp->c0min = c0min = c0;
		goto have_c0min;
	      }
	}
have_c0min:
  if (c0max > c0min)
    for (c0 = c0max; c0 >= c0min; c0--)
      for (c1 = c1min; c1 <= c1max; c1++)
	{
	  histp = &histogram[c0][c1][c2min];
	  for (c2 = c2min; c2 <= c2max; c2++)
	    if (*histp++ != 0)
	      {
		boxp->c0max = c0max = c0;
		goto have_c0max;
	      }
	}
have_c0max:
  if (c1max > c1min)
    for (c1 = c1min; c1 <= c1max; c1++)
      for (c0 = c0min; c0 <= c0max; c0++)
	{
	  histp = &histogram[c0][c1][c2min];
	  for (c2 = c2min; c2 <= c2max; c2++)
	    if (*histp++ != 0)
	      {
		boxp->c1min = c1min = c1;
		goto have_c1min;
	      }
	}
have_c1min:
  if (c1max > c1min)
    for (c1 = c1max; c1 >= c1min; c1--)
      for (c0 = c0min; c0 <= c0max; c0++)
	{
	  histp = &histogram[c0][c1][c2min];
	  for (c2 = c2min; c2 <= c2max; c2++)
	    if (*histp++ != 0)
	      {
		boxp->c1max = c1max = c1;
		goto have_c1max;
	      }
	}
have_c1max:
  if (c2max > c2min)
    for (c2 = c2min; c2 <= c2max; c2++)
      for (c0 = c0min; c0 <= c0max; c0++)
	{
	  histp = &histogram[c0][c1min][c2];
	  for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS)
	    if (*histp != 0)
	      {
		boxp->c2min = c2min = c2;
		goto have_c2min;
	      }
	}
have_c2min:
  if (c2max > c2min)
    for (c2 = c2max; c2 >= c2min; c2--)
      for (c0 = c0min; c0 <= c0max; c0++)
	{
	  histp = &histogram[c0][c1min][c2];
	  for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS)
	    if (*histp != 0)
	      {
		boxp->c2max = c2max = c2;
		goto have_c2max;
	      }
	}
have_c2max:

  /* Update box volume.
   * We use 2-norm rather than real volume here; this biases the method
   * against making long narrow boxes, and it has the side benefit that
   * a box is splittable iff norm > 0.
   * Since the differences are expressed in histogram-cell units,
   * we have to shift back to JSAMPLE units to get consistent distances;
   * after which, we scale according to the selected distance scale factors.
   */
  dist0 = ((c0max - c0min) << C0_SHIFT) * C0_SCALE;
  dist1 = ((c1max - c1min) << C1_SHIFT) * C1_SCALE;
  dist2 = ((c2max - c2min) << C2_SHIFT) * C2_SCALE;
  boxp->volume = dist0 * dist0 + dist1 * dist1 + dist2 * dist2;

  /* Now scan remaining volume of box and compute population */
  ccount = 0;
  for (c0 = c0min; c0 <= c0max; c0++)
    for (c1 = c1min; c1 <= c1max; c1++)
      {
	histp = &histogram[c0][c1][c2min];
	for (c2 = c2min; c2 <= c2max; c2++, histp++)
	  if (*histp != 0)
	    {
	      ccount++;
	    }
      }
  boxp->colorcount = ccount;
}


LOCAL (int)
#ifdef ORIGINAL_LIB_JPEG
median_cut (j_decompress_ptr cinfo, boxptr boxlist, int numboxes,
	    int desired_colors)
#else
median_cut (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize,
	    boxptr boxlist, int numboxes, int desired_colors)
#endif
/* Repeatedly select and split the largest box until we have enough boxes */
{
  int n, lb;
  int c0, c1, c2, cmax;
  register boxptr b1, b2;

  while (numboxes < desired_colors)
    {
      /* Select box to split.
       * Current algorithm: by population for first half, then by volume.
       */
      if (numboxes * 2 <= desired_colors)
	{
	  b1 = find_biggest_color_pop (boxlist, numboxes);
	}
      else
	{
	  b1 = find_biggest_volume (boxlist, numboxes);
	}
      if (b1 == NULL)		/* no splittable boxes left! */
	break;
      b2 = &boxlist[numboxes];	/* where new box will go */
      /* Copy the color bounds to the new box. */
      b2->c0max = b1->c0max;
      b2->c1max = b1->c1max;
      b2->c2max = b1->c2max;
      b2->c0min = b1->c0min;
      b2->c1min = b1->c1min;
      b2->c2min = b1->c2min;
      /* Choose which axis to split the box on.
       * Current algorithm: longest scaled axis.
       * See notes in update_box about scaling distances.
       */
      c0 = ((b1->c0max - b1->c0min) << C0_SHIFT) * C0_SCALE;
      c1 = ((b1->c1max - b1->c1min) << C1_SHIFT) * C1_SCALE;
      c2 = ((b1->c2max - b1->c2min) << C2_SHIFT) * C2_SCALE;
      /* We want to break any ties in favor of green, then red, blue last.
       * This code does the right thing for R,G,B or B,G,R color orders only.
       */
#if RGB_RED == 0
      cmax = c1;
      n = 1;
      if (c0 > cmax)
	{
	  cmax = c0;
	  n = 0;
	}
      if (c2 > cmax)
	{
	  n = 2;
	}
#else
      cmax = c1;
      n = 1;
      if (c2 > cmax)
	{
	  cmax = c2;
	  n = 2;
	}
      if (c0 > cmax)
	{
	  n = 0;
	}
#endif
      /* Choose split point along selected axis, and update box bounds.
       * Current algorithm: split at halfway point.
       * (Since the box has been shrunk to minimum volume,
       * any split will produce two nonempty subboxes.)
       * Note that lb value is max for lower box, so must be < old max.
       */
      switch (n)
	{
	case 0:
	  lb = (b1->c0max + b1->c0min) / 2;
	  b1->c0max = lb;
	  b2->c0min = lb + 1;
	  break;
	case 1:
	  lb = (b1->c1max + b1->c1min) / 2;
	  b1->c1max = lb;
	  b2->c1min = lb + 1;
	  break;
	case 2:
	  lb = (b1->c2max + b1->c2min) / 2;
	  b1->c2max = lb;
	  b2->c2min = lb + 1;
	  break;
	}
      /* Update stats for boxes */
#ifdef ORIGINAL_LIB_JPEG
      update_box (cinfo, b1);
      update_box (cinfo, b2);
#else
      update_box (oim, nim, cquantize, b1);
      update_box (oim, nim, cquantize, b2);
#endif
      numboxes++;
    }
  return numboxes;
}


LOCAL (void)
#ifndef ORIGINAL_LIB_JPEG
  compute_color (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize,
	       boxptr boxp, int icolor)
{
#else
  compute_color (j_decompress_ptr cinfo, boxptr boxp, int icolor)
/* Compute representative color for a box, put it in colormap[icolor] */
{
  /* Current algorithm: mean weighted by pixels (not colors) */
  /* Note it is important to get the rounding correct! */
  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
#endif
  hist3d histogram = cquantize->histogram;
  histptr histp;
  int c0, c1, c2;
  int c0min, c0max, c1min, c1max, c2min, c2max;
  long count = 0; /* 2.0.28: = 0 */
  long total = 0;
  long c0total = 0;
  long c1total = 0;
  long c2total = 0;

  c0min = boxp->c0min;
  c0max = boxp->c0max;
  c1min = boxp->c1min;
  c1max = boxp->c1max;
  c2min = boxp->c2min;
  c2max = boxp->c2max;

  for (c0 = c0min; c0 <= c0max; c0++)
    for (c1 = c1min; c1 <= c1max; c1++)
      {
	histp = &histogram[c0][c1][c2min];
	for (c2 = c2min; c2 <= c2max; c2++)
	  {
	    if ((count = *histp++) != 0)
	      {
		total += count;
		c0total +=
		  ((c0 << C0_SHIFT) + ((1 << C0_SHIFT) >> 1)) * count;
		c1total +=
		  ((c1 << C1_SHIFT) + ((1 << C1_SHIFT) >> 1)) * count;
		c2total +=
		  ((c2 << C2_SHIFT) + ((1 << C2_SHIFT) >> 1)) * count;
	      }
	  }
      }

#ifdef ORIGINAL_LIB_JPEG
  cinfo->colormap[0][icolor] = (JSAMPLE) ((c0total + (total >> 1)) / total);
  cinfo->colormap[1][icolor] = (JSAMPLE) ((c1total + (total >> 1)) / total);
  cinfo->colormap[2][icolor] = (JSAMPLE) ((c2total + (total >> 1)) / total);
#else
  /* 2.0.16: Paul den Dulk found an occasion where total can be 0 */
  if (count)
    {
      nim->red[icolor] = (int) ((c0total + (total >> 1)) / total);
      nim->green[icolor] = (int) ((c1total + (total >> 1)) / total);
      nim->blue[icolor] = (int) ((c2total + (total >> 1)) / total);
    }
  else
    {
      nim->red[icolor] = 255;
      nim->green[icolor] = 255;
      nim->blue[icolor] = 255;
    }
#endif
}


LOCAL (void)
#ifdef ORIGINAL_LIB_JPEG
select_colors (j_decompress_ptr cinfo, int desired_colors)
#else
select_colors (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize, int desired_colors)
#endif
/* Master routine for color selection */
{
  boxptr boxlist;
  int numboxes;
  int i;

  /* Allocate workspace for box list */
#ifdef ORIGINAL_LIB_JPEG
  boxlist = (boxptr) (*cinfo->mem->alloc_small)
    ((j_common_ptr) cinfo, JPOOL_IMAGE, desired_colors * SIZEOF (box));
#else
  /* This can't happen because we clamp desired_colors at gdMaxColors, 
    but anyway */
  if (overflow2(desired_colors, sizeof (box))) {
    return;
   }
  boxlist = (boxptr) gdMalloc (desired_colors * sizeof (box));
#endif
  /* Initialize one box containing whole space */
  numboxes = 1;
  boxlist[0].c0min = 0;
  boxlist[0].c0max = MAXJSAMPLE >> C0_SHIFT;
  boxlist[0].c1min = 0;
  boxlist[0].c1max = MAXJSAMPLE >> C1_SHIFT;
  boxlist[0].c2min = 0;
  boxlist[0].c2max = MAXJSAMPLE >> C2_SHIFT;
#ifdef ORIGINAL_LIB_JPEG
  /* Shrink it to actually-used volume and set its statistics */
  update_box (cinfo, &boxlist[0]);
  /* Perform median-cut to produce final box list */
  numboxes = median_cut (cinfo, boxlist, numboxes, desired_colors);
  /* Compute the representative color for each box, fill colormap */
  for (i = 0; i < numboxes; i++)
    compute_color (cinfo, &boxlist[i], i);
  cinfo->actual_number_of_colors = numboxes;
  TRACEMS1 (cinfo, 1, JTRC_QUANT_SELECTED, numboxes);
#else
  /* Shrink it to actually-used volume and set its statistics */
  update_box (oim, nim, cquantize, &boxlist[0]);
  /* Perform median-cut to produce final box list */
  numboxes = median_cut (oim, nim, cquantize, boxlist, numboxes, desired_colors);
  /* Compute the representative color for each box, fill colormap */
  for (i = 0; i < numboxes; i++)
    compute_color (oim, nim, cquantize, &boxlist[i], i);
  nim->colorsTotal = numboxes;