gd_topal.c

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

      belowerr0 = belowerr1 = belowerr2 = belowerr3 = 0;
      bpreverr0 = bpreverr1 = bpreverr2 = bpreverr3 = 0;

      for (col = width; col > 0; col--)
	{
	  int a;
	  /* curN holds the error propagated from the previous pixel on the
	   * current line.  Add the error propagated from the previous line
	   * to form the complete error correction term for this pixel, and
	   * round the error term (which is expressed * 16) to an integer.
	   * RIGHT_SHIFT rounds towards minus infinity, so adding 8 is correct
	   * for either sign of the error value.
	   * Note: errorptr points to *previous* column's array entry.
	   */
	  cur0 = RIGHT_SHIFT (cur0 + errorptr[dir4 + 0] + 8, 4);
	  cur1 = RIGHT_SHIFT (cur1 + errorptr[dir4 + 1] + 8, 4);
	  cur2 = RIGHT_SHIFT (cur2 + errorptr[dir4 + 2] + 8, 4);
	  cur3 = RIGHT_SHIFT (cur3 + errorptr[dir4 + 3] + 8, 4);
	  /* Limit the error using transfer function set by init_error_limit.
	   * See comments with init_error_limit for rationale.
	   */
	  cur0 = error_limit[cur0];
	  cur1 = error_limit[cur1];
	  cur2 = error_limit[cur2];
	  cur3 = error_limit[cur3];
	  /* Form pixel value + error, and range-limit to 0..MAXJSAMPLE.
	   * The maximum error is +- MAXJSAMPLE (or less with error limiting);
	   * but we'll be lazy and just clamp this with an if test (TBB).
	   */
	  cur0 += gdTrueColorGetRed (*inptr);
	  cur1 += gdTrueColorGetGreen (*inptr);
	  cur2 += gdTrueColorGetBlue (*inptr);
	  /* Expand to 8 bits for consistency with dithering algorithm -- TBB */
	  a = gdTrueColorGetAlpha (*inptr);
	  cur3 += (a << 1) + (a >> 6);
	  if (cur0 < 0)
	    {
	      cur0 = 0;
	    }
	  if (cur0 > 255)
	    {
	      cur0 = 255;
	    }
	  if (cur1 < 0)
	    {
	      cur1 = 0;
	    }
	  if (cur1 > 255)
	    {
	      cur1 = 255;
	    }
	  if (cur2 < 0)
	    {
	      cur2 = 0;
	    }
	  if (cur2 > 255)
	    {
	      cur2 = 255;
	    }
	  if (cur3 < 0)
	    {
	      cur3 = 0;
	    }
	  if (cur3 > 255)
	    {
	      cur3 = 255;
	    }
	  /* Index into the cache with adjusted pixel value */
	  cachep = &histogram
	    [cur0 >> C0_SHIFT]
	    [cur1 >> C1_SHIFT]
	    [cur2 >> C2_SHIFT]
	    [cur3 >> (C3_SHIFT + 1)];
	  /* If we have not seen this color before, find nearest colormap */
	  /* entry and update the cache */
	  if (*cachep == 0)
	    fill_inverse_cmap (im, cquantize,
		       cur0 >> C0_SHIFT, cur1 >> C1_SHIFT, cur2 >> C2_SHIFT,
			       cur3 >> (C3_SHIFT + 1));
	  /* Now emit the colormap index for this cell */
	  {
	    register int pixcode = *cachep - 1;
	    *outptr = pixcode;
	    /* Compute representation error for this pixel */
	    cur0 -= colormap0[pixcode];
	    cur1 -= colormap1[pixcode];
	    cur2 -= colormap2[pixcode];
	    cur3 -= ((colormap3[pixcode] << 1) + (colormap3[pixcode] >> 6));
	  }
	  /* Compute error fractions to be propagated to adjacent pixels.
	   * Add these into the running sums, and simultaneously shift the
	   * next-line error sums left by 1 column.
	   */
	  {
	    register LOCFSERROR bnexterr, delta;

	    bnexterr = cur0;	/* Process component 0 */
	    delta = cur0 * 2;
	    cur0 += delta;	/* form error * 3 */
	    errorptr[0] = (FSERROR) (bpreverr0 + cur0);
	    cur0 += delta;	/* form error * 5 */
	    bpreverr0 = belowerr0 + cur0;
	    belowerr0 = bnexterr;
	    cur0 += delta;	/* form error * 7 */
	    bnexterr = cur1;	/* Process component 1 */
	    delta = cur1 * 2;
	    cur1 += delta;	/* form error * 3 */
	    errorptr[1] = (FSERROR) (bpreverr1 + cur1);
	    cur1 += delta;	/* form error * 5 */
	    bpreverr1 = belowerr1 + cur1;
	    belowerr1 = bnexterr;
	    cur1 += delta;	/* form error * 7 */
	    bnexterr = cur2;	/* Process component 2 */
	    delta = cur2 * 2;
	    cur2 += delta;	/* form error * 3 */
	    errorptr[2] = (FSERROR) (bpreverr2 + cur2);
	    cur2 += delta;	/* form error * 5 */
	    bpreverr2 = belowerr2 + cur2;
	    belowerr2 = bnexterr;
	    cur2 += delta;	/* form error * 7 */
	    bnexterr = cur3;	/* Process component 3 */
	    delta = cur3 * 2;
	    cur3 += delta;	/* form error * 3 */
	    errorptr[3] = (FSERROR) (bpreverr3 + cur3);
	    cur3 += delta;	/* form error * 5 */
	    bpreverr3 = belowerr3 + cur3;
	    belowerr3 = bnexterr;
	    cur3 += delta;	/* form error * 7 */
	  }
	  /* At this point curN contains the 7/16 error value to be propagated
	   * to the next pixel on the current line, and all the errors for the
	   * next line have been shifted over.  We are therefore ready to move on.
	   */
	  inptr += dir;		/* Advance pixel pointers to next column */
	  outptr += dir;
	  errorptr += dir4;	/* advance errorptr to current column */
	}
      /* Post-loop cleanup: we must unload the final error values into the
       * final fserrors[] entry.  Note we need not unload belowerrN because
       * it is for the dummy column before or after the actual array.
       */
      errorptr[0] = (FSERROR) bpreverr0;	/* unload prev errs into array */
      errorptr[1] = (FSERROR) bpreverr1;
      errorptr[2] = (FSERROR) bpreverr2;
      errorptr[3] = (FSERROR) bpreverr3;
    }
}


/*
 * Initialize the error-limiting transfer function (lookup table).
 * The raw F-S error computation can potentially compute error values of up to
 * +- MAXJSAMPLE.  But we want the maximum correction applied to a pixel to be
 * much less, otherwise obviously wrong pixels will be created.  (Typical
 * effects include weird fringes at color-area boundaries, isolated bright
 * pixels in a dark area, etc.)  The standard advice for avoiding this problem
 * is to ensure that the "corners" of the color cube are allocated as output
 * colors; then repeated errors in the same direction cannot cause cascading
 * error buildup.  However, that only prevents the error from getting
 * completely out of hand; Aaron Giles reports that error limiting improves
 * the results even with corner colors allocated.
 * A simple clamping of the error values to about +- MAXJSAMPLE/8 works pretty
 * well, but the smoother transfer function used below is even better.  Thanks
 * to Aaron Giles for this idea.
 */

static int
init_error_limit (gdImagePtr im, my_cquantize_ptr cquantize)
/* Allocate and fill in the error_limiter table */
{
  int *table;
  int in, out;

  cquantize->error_limiter_storage = (int *) gdMalloc ((255 * 2 + 1) * sizeof (int));
  if (!cquantize->error_limiter_storage)
    {
      return 0;
    }
  /* so can index -MAXJSAMPLE .. +MAXJSAMPLE */
  cquantize->error_limiter = cquantize->error_limiter_storage + 255;
  table = cquantize->error_limiter;
#define STEPSIZE ((255+1)/16)
  /* Map errors 1:1 up to +- MAXJSAMPLE/16 */
  out = 0;
  for (in = 0; in < STEPSIZE; in++, out++)
    {
      table[in] = out;
      table[-in] = -out;
    }
  /* Map errors 1:2 up to +- 3*MAXJSAMPLE/16 */
  for (; in < STEPSIZE * 3; in++, out += (in & 1) ? 0 : 1)
    {
      table[in] = out;
      table[-in] = -out;
    }
  /* Clamp the rest to final out value (which is (MAXJSAMPLE+1)/8) */
  for (; in <= 255; in++)
    {
      table[in] = out;
      table[-in] = -out;
    }
#undef STEPSIZE
  return 1;
}

static void
zeroHistogram (hist4d histogram)
{
  int i;
  int j;
  /* Zero the histogram or inverse color map */
  for (i = 0; i < HIST_C0_ELEMS; i++)
    {
      for (j = 0; j < HIST_C1_ELEMS; j++)
	{
	  memset (histogram[i][j],
		  0,
		  HIST_C2_ELEMS * HIST_C3_ELEMS * sizeof (histcell));
	}
    }
}

/* Here we go at last. */
void
gdImageTrueColorToPalette (gdImagePtr im, int dither, int colorsWanted)
{
  my_cquantize_ptr cquantize = 0;
  int i;
  size_t arraysize;
  if (!im->trueColor)
    {
      /* Nothing to do! */
      return;
    }
  if (colorsWanted > gdMaxColors)
    {
      colorsWanted = gdMaxColors;
    }
  im->pixels = gdCalloc (sizeof (unsigned char *), im->sy);
  if (!im->pixels)
    {
      /* No can do */
      goto outOfMemory;
    }
  for (i = 0; (i < im->sy); i++)
    {
      im->pixels[i] = gdCalloc (sizeof (unsigned char *), im->sx);
      if (!im->pixels[i])
	{
	  goto outOfMemory;
	}
    }
  cquantize = (my_cquantize_ptr) gdCalloc (sizeof (my_cquantizer), 1);
  if (!cquantize)
    {
      /* No can do */
      goto outOfMemory;
    }
  /* Allocate the histogram/inverse colormap storage */
  cquantize->histogram = (hist4d) gdMalloc (HIST_C0_ELEMS * sizeof (hist3d));
  for (i = 0; i < HIST_C0_ELEMS; i++)
    {
      int j;
      cquantize->histogram[i] = (hist3d) gdCalloc (HIST_C1_ELEMS,
						   sizeof (hist2d));
      if (!cquantize->histogram[i])
	{
	  goto outOfMemory;
	}
      for (j = 0; (j < HIST_C1_ELEMS); j++)
	{
	  cquantize->histogram[i][j] = (hist2d) gdCalloc (HIST_C2_ELEMS * HIST_C3_ELEMS,
							  sizeof (histcell));
	  if (!cquantize->histogram[i][j])
	    {
	      goto outOfMemory;
	    }
	}
    }
  cquantize->fserrors = (FSERRPTR) gdMalloc (4 * sizeof (FSERROR));
  init_error_limit (im, cquantize);
  arraysize = (size_t) ((im->sx + 2) *
			(4 * sizeof (FSERROR)));
  /* Allocate Floyd-Steinberg workspace. */
  cquantize->fserrors = gdCalloc (arraysize, 1);
  if (!cquantize->fserrors)
    {
      goto outOfMemory;
    }
  cquantize->on_odd_row = FALSE;

  /* Do the work! */
  zeroHistogram (cquantize->histogram);
  prescan_quantize (im, cquantize);
  select_colors (im, cquantize, 256);
  /* TBB HACK REMOVE */
  {
    FILE *out = fopen ("palettemap.png", "wb");
    int i;
    gdImagePtr im2 = gdImageCreateTrueColor (256, 256);
    for (i = 0; (i < 256); i++)
      {
	gdImageFilledRectangle (im2, (i % 16) * 16, (i / 16) * 16,
				(i % 16) * 16 + 15, (i / 16) * 16 + 15,
				gdTrueColorAlpha (im->red[i], im->green[i],
						im->blue[i], im->alpha[i]));
      }
    gdImagePng (im2, out);
    fclose (out);
    gdImageDestroy (im2);
  }
  zeroHistogram (cquantize->histogram);
  if (dither)
    {
      pass2_fs_dither (im, cquantize);
    }
  else
    {
      pass2_no_dither (im, cquantize);
    }
  if (cquantize->transparentIsPresent)
    {
      int mt = -1;
      int mtIndex = -1;
      for (i = 0; (i < im->colorsTotal); i++)
	{
	  if (im->alpha[i] > mt)
	    {
	      mtIndex = i;
	      mt = im->alpha[i];
	    }
	}
      for (i = 0; (i < im->colorsTotal); i++)
	{
	  if (im->alpha[i] == mt)
	    {
	      im->alpha[i] = gdAlphaTransparent;
	    }
	}
    }
  if (cquantize->opaqueIsPresent)
    {
      int mo = 128;
      int moIndex = -1;
      for (i = 0; (i < im->colorsTotal); i++)
	{
	  if (im->alpha[i] < mo)
	    {
	      moIndex = i;
	      mo = im->alpha[i];
	    }
	}
      for (i = 0; (i < im->colorsTotal); i++)
	{
	  if (im->alpha[i] == mo)
	    {
	      im->alpha[i] = gdAlphaOpaque;
	    }
	}
    }
  /* Success! Get rid of the truecolor image data. */
  im->trueColor = 0;
  /* Junk the truecolor pixels */
  for (i = 0; i < im->sy; i++)
    {
      gdFree (im->tpixels[i]);
    }
  gdFree (im->tpixels);
  im->tpixels = 0;
  /* Tediously free stuff. */
outOfMemory:
  if (im->trueColor)
    {
      /* On failure only */
      for (i = 0; i < im->sy; i++)
	{
	  if (im->pixels[i])
	    {
	      gdFree (im->pixels[i]);
	    }
	}
      if (im->pixels)
	{
	  gdFree (im->pixels);
	}
      im->pixels = 0;
    }
  for (i = 0; i < HIST_C0_ELEMS; i++)
    {
      if (cquantize->histogram[i])
	{
	  int j;
	  for (j = 0; j < HIST_C1_ELEMS; j++)
	    {
	      if (cquantize->histogram[i][j])
		{
		  gdFree (cquantize->histogram[i][j]);
		}
	    }
	  gdFree (cquantize->histogram[i]);
	}
    }
  if (cquantize->histogram)
    {
      gdFree (cquantize->histogram);
    }
  if (cquantize->fserrors)
    {
      gdFree (cquantize->fserrors);
    }
  if (cquantize->error_limiter_storage)
    {
      gdFree (cquantize->error_limiter_storage);
    }
  if (cquantize)
    {
      gdFree (cquantize);
    }
}