Back to index

php5  5.3.10
Classes | Defines | Typedefs | Functions
gd_topal.c File Reference
#include <string.h>
#include "gd.h"
#include "gdhelpers.h"

Go to the source code of this file.

Classes

struct  my_cquantizer
struct  box

Defines

#define QUANT_2PASS_SUPPORTED
#define RGB_RED   0
#define RGB_GREEN   1
#define RGB_BLUE   2
#define JSAMPLE   unsigned char
#define MAXJSAMPLE   (gdMaxColors-1)
#define BITS_IN_JSAMPLE   8
#define JSAMPROW   int*
#define JDIMENSION   int
#define METHODDEF(type)   static type
#define LOCAL(type)   static type
#define SHIFT_TEMPS
#define RIGHT_SHIFT(x, shft)   ((x) >> (shft))
#define range_limit(x)   { if(x<0) x=0; if (x>255) x=255; }
#define INT16   short
#define UINT16   unsigned short
#define INT32   int
#define FAR
#define boolean   int
#define TRUE   1
#define FALSE   0
#define input_buf   (oim->tpixels)
#define output_buf   (nim->pixels)
#define R_SCALE   2 /* scale R distances by this much */
#define G_SCALE   3 /* scale G distances by this much */
#define B_SCALE   1 /* and B by this much */
#define C0_SCALE   R_SCALE
#define C1_SCALE   G_SCALE
#define C2_SCALE   B_SCALE
#define MAXNUMCOLORS   (MAXJSAMPLE+1) /* maximum size of colormap */
#define HIST_C0_BITS   5 /* bits of precision in R/B histogram */
#define HIST_C1_BITS   6 /* bits of precision in G histogram */
#define HIST_C2_BITS   5 /* bits of precision in B/R histogram */
#define HIST_C0_ELEMS   (1<<HIST_C0_BITS)
#define HIST_C1_ELEMS   (1<<HIST_C1_BITS)
#define HIST_C2_ELEMS   (1<<HIST_C2_BITS)
#define C0_SHIFT   (BITS_IN_JSAMPLE-HIST_C0_BITS)
#define C1_SHIFT   (BITS_IN_JSAMPLE-HIST_C1_BITS)
#define C2_SHIFT   (BITS_IN_JSAMPLE-HIST_C2_BITS)
#define BOX_C0_LOG   (HIST_C0_BITS-3)
#define BOX_C1_LOG   (HIST_C1_BITS-3)
#define BOX_C2_LOG   (HIST_C2_BITS-3)
#define BOX_C0_ELEMS   (1<<BOX_C0_LOG) /* # of hist cells in update box */
#define BOX_C1_ELEMS   (1<<BOX_C1_LOG)
#define BOX_C2_ELEMS   (1<<BOX_C2_LOG)
#define BOX_C0_SHIFT   (C0_SHIFT + BOX_C0_LOG)
#define BOX_C1_SHIFT   (C1_SHIFT + BOX_C1_LOG)
#define BOX_C2_SHIFT   (C2_SHIFT + BOX_C2_LOG)
#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 GETJSAMPLE
#define STEPSIZE   ((MAXJSAMPLE+1)/16)

Typedefs

typedef UINT16 histcell
typedef histcell FARhistptr
typedef histcell hist1d [HIST_C2_ELEMS]
typedef hist1d FARhist2d
typedef hist2dhist3d
typedef INT16 FSERROR
typedef int LOCFSERROR
typedef FSERROR FARFSERRPTR
typedef my_cquantizermy_cquantize_ptr
typedef boxboxptr

Functions

 prescan_quantize (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize)
 LOCAL (boxptr)
 update_box (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize, boxptr boxp)
 median_cut (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize, boxptr boxlist, int numboxes, int desired_colors)
 compute_color (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize, boxptr boxp, int icolor)
 select_colors (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize, int desired_colors)
 find_nearby_colors (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize, int minc0, int minc1, int minc2, JSAMPLE colorlist[])
 LOCAL (void)
 fill_inverse_cmap (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize, int c0, int c1, int c2)
 pass2_no_dither (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize)
 pass2_fs_dither (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize)
 init_error_limit (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize)
static void zeroHistogram (hist3d histogram)
static void gdImageTrueColorToPaletteBody (gdImagePtr oim, int dither, int colorsWanted, gdImagePtr *cimP)
gdImagePtr gdImageCreatePaletteFromTrueColor (gdImagePtr im, int dither, int colorsWanted)
void gdImageTrueColorToPalette (gdImagePtr im, int dither, int colorsWanted)

Class Documentation

struct my_cquantizer

Definition at line 304 of file gd_topal.c.

Class Members
int * error_limiter
int * error_limiter_storage
FSERRPTR fserrors
hist3d histogram
boolean on_odd_row
struct box

Definition at line 407 of file gd_topal.c.

Class Members
int c0max
int c0min
int c1max
int c1min
int c2max
int c2min
long colorcount
INT32 volume

Define Documentation

#define B_SCALE   1 /* and B by this much */

Definition at line 186 of file gd_topal.c.

#define BITS_IN_JSAMPLE   8

Definition at line 65 of file gd_topal.c.

#define boolean   int

Definition at line 118 of file gd_topal.c.

#define BOX_C0_ELEMS   (1<<BOX_C0_LOG) /* # of hist cells in update box */

Definition at line 905 of file gd_topal.c.

#define BOX_C0_LOG   (HIST_C0_BITS-3)

Definition at line 901 of file gd_topal.c.

#define BOX_C0_SHIFT   (C0_SHIFT + BOX_C0_LOG)

Definition at line 909 of file gd_topal.c.

#define BOX_C1_ELEMS   (1<<BOX_C1_LOG)

Definition at line 906 of file gd_topal.c.

#define BOX_C1_LOG   (HIST_C1_BITS-3)

Definition at line 902 of file gd_topal.c.

#define BOX_C1_SHIFT   (C1_SHIFT + BOX_C1_LOG)

Definition at line 910 of file gd_topal.c.

#define BOX_C2_ELEMS   (1<<BOX_C2_LOG)

Definition at line 907 of file gd_topal.c.

#define BOX_C2_LOG   (HIST_C2_BITS-3)

Definition at line 903 of file gd_topal.c.

#define BOX_C2_SHIFT   (C2_SHIFT + BOX_C2_LOG)

Definition at line 911 of file gd_topal.c.

#define C0_SCALE   R_SCALE

Definition at line 196 of file gd_topal.c.

Definition at line 253 of file gd_topal.c.

#define C1_SCALE   G_SCALE

Definition at line 202 of file gd_topal.c.

Definition at line 254 of file gd_topal.c.

#define C2_SCALE   B_SCALE

Definition at line 208 of file gd_topal.c.

Definition at line 255 of file gd_topal.c.

#define FALSE   0

Definition at line 126 of file gd_topal.c.

#define FAR

Definition at line 112 of file gd_topal.c.

#define G_SCALE   3 /* scale G distances by this much */

Definition at line 185 of file gd_topal.c.

#define GETJSAMPLE
#define HIST_C0_BITS   5 /* bits of precision in R/B histogram */

Definition at line 243 of file gd_topal.c.

#define HIST_C0_ELEMS   (1<<HIST_C0_BITS)

Definition at line 248 of file gd_topal.c.

#define HIST_C1_BITS   6 /* bits of precision in G histogram */

Definition at line 244 of file gd_topal.c.

#define HIST_C1_ELEMS   (1<<HIST_C1_BITS)

Definition at line 249 of file gd_topal.c.

#define HIST_C2_BITS   5 /* bits of precision in B/R histogram */

Definition at line 245 of file gd_topal.c.

#define HIST_C2_ELEMS   (1<<HIST_C2_BITS)

Definition at line 250 of file gd_topal.c.

#define input_buf   (oim->tpixels)

Definition at line 130 of file gd_topal.c.

#define INT16   short

Definition at line 100 of file gd_topal.c.

#define INT32   int

Definition at line 108 of file gd_topal.c.

#define JDIMENSION   int

Definition at line 68 of file gd_topal.c.

#define JSAMPLE   unsigned char

Definition at line 63 of file gd_topal.c.

#define JSAMPROW   int*

Definition at line 67 of file gd_topal.c.

#define LOCAL (   type)    static type

Definition at line 71 of file gd_topal.c.

#define MAXJSAMPLE   (gdMaxColors-1)

Definition at line 64 of file gd_topal.c.

#define MAXNUMCOLORS   (MAXJSAMPLE+1) /* maximum size of colormap */

Definition at line 238 of file gd_topal.c.

#define METHODDEF (   type)    static type

Definition at line 70 of file gd_topal.c.

#define output_buf   (nim->pixels)

Definition at line 131 of file gd_topal.c.

Definition at line 57 of file gd_topal.c.

#define R_SCALE   2 /* scale R distances by this much */

Definition at line 184 of file gd_topal.c.

#define range_limit (   x)    { if(x<0) x=0; if (x>255) x=255; }

Definition at line 96 of file gd_topal.c.

#define RGB_BLUE   2

Definition at line 61 of file gd_topal.c.

#define RGB_GREEN   1

Definition at line 60 of file gd_topal.c.

#define RGB_RED   0

Definition at line 59 of file gd_topal.c.

#define RIGHT_SHIFT (   x,
  shft 
)    ((x) >> (shft))

Definition at line 92 of file gd_topal.c.

#define SHIFT_TEMPS

Definition at line 91 of file gd_topal.c.

#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 STEPSIZE   ((MAXJSAMPLE+1)/16)
#define TRUE   1

Definition at line 122 of file gd_topal.c.

#define UINT16   unsigned short

Definition at line 104 of file gd_topal.c.


Typedef Documentation

typedef box* boxptr

Definition at line 420 of file gd_topal.c.

typedef INT16 FSERROR

Definition at line 292 of file gd_topal.c.

typedef FSERROR FAR* FSERRPTR

Definition at line 299 of file gd_topal.c.

Definition at line 262 of file gd_topal.c.

typedef hist1d FAR* hist2d

Definition at line 263 of file gd_topal.c.

typedef hist2d* hist3d

Definition at line 264 of file gd_topal.c.

typedef UINT16 histcell

Definition at line 258 of file gd_topal.c.

typedef histcell FAR* histptr

Definition at line 260 of file gd_topal.c.

typedef int LOCFSERROR

Definition at line 293 of file gd_topal.c.

Definition at line 330 of file gd_topal.c.


Function Documentation

compute_color ( gdImagePtr  oim,
gdImagePtr  nim,
my_cquantize_ptr  cquantize,
boxptr  boxp,
int  icolor 
)

Definition at line 710 of file gd_topal.c.

{
#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;
    }
              nim->open[icolor] = 0;
#endif
}

Here is the call graph for this function:

Here is the caller graph for this function:

fill_inverse_cmap ( gdImagePtr  oim,
gdImagePtr  nim,
my_cquantize_ptr  cquantize,
int  c0,
int  c1,
int  c2 
)

Definition at line 1203 of file gd_topal.c.

{
#ifdef ORIGINAL_LIB_JPEG
  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
#endif
  hist3d histogram = cquantize->histogram;
  int minc0, minc1, minc2;  /* lower left corner of update box */
  int ic0, ic1, ic2;
  register JSAMPLE *cptr;   /* pointer into bestcolor[] array */
  register histptr cachep;  /* pointer into main cache array */
  /* This array lists the candidate colormap indexes. */
  JSAMPLE colorlist[MAXNUMCOLORS];
  int numcolors;            /* number of candidate colors */
  /* This array holds the actually closest colormap index for each cell. */
  JSAMPLE bestcolor[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS];

  /* Convert cell coordinates to update box ID */
  c0 >>= BOX_C0_LOG;
  c1 >>= BOX_C1_LOG;
  c2 >>= BOX_C2_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);

  /* Determine which colormap entries are close enough to be candidates
   * for the nearest entry to some cell in the update box.
   */
#ifdef ORIGINAL_LIB_JPEG
  numcolors = find_nearby_colors (cinfo, minc0, minc1, minc2, colorlist);

  /* Determine the actually nearest colors. */
  find_best_colors (cinfo, minc0, minc1, minc2, numcolors, colorlist,
                  bestcolor);
#else
  numcolors =
    find_nearby_colors (oim, nim, cquantize, minc0, minc1, minc2, colorlist);
  find_best_colors (oim, nim, cquantize, minc0, minc1, minc2, numcolors,
                  colorlist, bestcolor);
#endif

  /* 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;
  cptr = bestcolor;
  for (ic0 = 0; ic0 < BOX_C0_ELEMS; ic0++)
    {
      for (ic1 = 0; ic1 < BOX_C1_ELEMS; ic1++)
       {
         cachep = &histogram[c0 + ic0][c1 + ic1][c2];
         for (ic2 = 0; ic2 < BOX_C2_ELEMS; ic2++)
           {
#ifdef ORIGINAL_LIB_JPEG
             *cachep++ = (histcell) (GETJSAMPLE (*cptr++) + 1);
#else
             *cachep++ = (histcell) ((*cptr++) + 1);
#endif
           }
       }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

find_nearby_colors ( gdImagePtr  oim,
gdImagePtr  nim,
my_cquantize_ptr  cquantize,
int  minc0,
int  minc1,
int  minc2,
JSAMPLE  colorlist[] 
)

Definition at line 923 of file gd_topal.c.

{
#ifdef ORIGINAL_LIB_JPEG
  int numcolors = cinfo->actual_number_of_colors;
#else
  int numcolors = nim->colorsTotal;
#endif
  int maxc0, maxc1, maxc2;
  int centerc0, centerc1, centerc2;
  int i, x, ncolors;
  INT32 minmaxdist, min_dist, max_dist, tdist;
  INT32 mindist[MAXNUMCOLORS];     /* min distance to colormap entry i */

  /* Compute true coordinates of update box's upper corner and center.
   * Actually we compute the coordinates of the center of the upper-corner
   * histogram cell, which are the upper bounds of the volume we care about.
   * Note that since ">>" rounds down, the "center" values may be closer to
   * min than to max; hence comparisons to them must be "<=", not "<".
   */
  maxc0 = minc0 + ((1 << BOX_C0_SHIFT) - (1 << C0_SHIFT));
  centerc0 = (minc0 + maxc0) >> 1;
  maxc1 = minc1 + ((1 << BOX_C1_SHIFT) - (1 << C1_SHIFT));
  centerc1 = (minc1 + maxc1) >> 1;
  maxc2 = minc2 + ((1 << BOX_C2_SHIFT) - (1 << C2_SHIFT));
  centerc2 = (minc2 + maxc2) >> 1;

  /* For each color in colormap, find:
   *  1. its minimum squared-distance to any point in the update box
   *     (zero if color is within update box);
   *  2. its maximum squared-distance to any point in the update box.
   * Both of these can be found by considering only the corners of the box.
   * We save the minimum distance for each color in mindist[];
   * only the smallest maximum distance is of interest.
   */
  minmaxdist = 0x7FFFFFFFL;

  for (i = 0; i < numcolors; i++)
    {
      /* We compute the squared-c0-distance term, then add in the other two. */
#ifdef ORIGINAL_LIB_JPEG
      x = GETJSAMPLE (cinfo->colormap[0][i]);
#else
      x = nim->red[i];
#endif
      if (x < minc0)
       {
         tdist = (x - minc0) * C0_SCALE;
         min_dist = tdist * tdist;
         tdist = (x - maxc0) * C0_SCALE;
         max_dist = tdist * tdist;
       }
      else if (x > maxc0)
       {
         tdist = (x - maxc0) * C0_SCALE;
         min_dist = tdist * tdist;
         tdist = (x - minc0) * C0_SCALE;
         max_dist = tdist * tdist;
       }
      else
       {
         /* within cell range so no contribution to min_dist */
         min_dist = 0;
         if (x <= centerc0)
           {
             tdist = (x - maxc0) * C0_SCALE;
             max_dist = tdist * tdist;
           }
         else
           {
             tdist = (x - minc0) * C0_SCALE;
             max_dist = tdist * tdist;
           }
       }

#ifdef ORIGINAL_LIB_JPEG
      x = GETJSAMPLE (cinfo->colormap[1][i]);
#else
      x = nim->green[i];
#endif
      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;
           }
       }

#ifdef ORIGINAL_LIB_JPEG
      x = GETJSAMPLE (cinfo->colormap[2][i]);
#else
      x = nim->blue[i];
#endif
      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;
           }
       }

      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++] = (JSAMPLE) i;
    }
  return ncolors;
}

Here is the caller graph for this function:

gdImagePtr gdImageCreatePaletteFromTrueColor ( gdImagePtr  im,
int  dither,
int  colorsWanted 
)

Definition at line 1759 of file gd_topal.c.

{
       gdImagePtr nim;
       gdImageTrueColorToPaletteBody(im, dither, colorsWanted, &nim);
       return nim;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void gdImageTrueColorToPalette ( gdImagePtr  im,
int  dither,
int  colorsWanted 
)

Definition at line 1766 of file gd_topal.c.

{
       gdImageTrueColorToPaletteBody(im, dither, colorsWanted, 0);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void gdImageTrueColorToPaletteBody ( gdImagePtr  oim,
int  dither,
int  colorsWanted,
gdImagePtr cimP 
) [static]

Definition at line 1779 of file gd_topal.c.

{
  my_cquantize_ptr cquantize = NULL;
  int i;

#ifndef ORIGINAL_LIB_JPEG
  /* Allocate the JPEG palette-storage */
  size_t arraysize;
  int maxColors = gdMaxColors;
  gdImagePtr nim;
  if (cimP) {
    nim = gdImageCreate(oim->sx, oim->sy);
    *cimP = nim;
    if (!nim) {
      return;
    }
  } else {
    nim = oim;
  }     
  if (!oim->trueColor)
    {
      /* (Almost) nothing to do! */
      if (cimP) {
        gdImageCopy(nim, oim, 0, 0, 0, 0, oim->sx, oim->sy);
        *cimP = nim;
      }
      return;
    }

  /* If we have a transparent color (the alphaless mode of transparency), we
   * must reserve a palette entry for it at the end of the palette. */
  if (oim->transparent >= 0)
    {
      maxColors--;
    }
  if (colorsWanted > maxColors)
    {
      colorsWanted = maxColors;
    }
  if (!cimP) {
    nim->pixels = gdCalloc (sizeof (unsigned char *), oim->sy);
    if (!nim->pixels)
      {
        /* No can do */
        goto outOfMemory;
      }
    for (i = 0; (i < nim->sy); i++)
      {
        nim->pixels[i] = gdCalloc (sizeof (unsigned char *), oim->sx);
        if (!nim->pixels[i])
       {
         goto outOfMemory;
       }
      }
  }
#endif

#ifdef ORIGINAL_LIB_JPEG
  cquantize = (my_cquantize_ptr)
    (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
                            SIZEOF (my_cquantizer));
  cinfo->cquantize = (struct jpeg_color_quantizer *) cquantize;
  cquantize->pub.start_pass = start_pass_2_quant;
  cquantize->pub.new_color_map = new_color_map_2_quant;
  /* Make sure jdmaster didn't give me a case I can't handle */
  if (cinfo->out_color_components != 3)
    ERREXIT (cinfo, JERR_NOTIMPL);
#else
  cquantize = (my_cquantize_ptr) gdCalloc (sizeof (my_cquantizer), 1);
  if (!cquantize)
    {
      /* No can do */
      goto outOfMemory;
    }
#endif
  cquantize->fserrors = NULL;      /* flag optional arrays not allocated */
  cquantize->error_limiter = NULL;


  /* Allocate the histogram/inverse colormap storage */
#ifdef ORIGINAL_LIB_JPEG
  cquantize->histogram = (hist3d) (*cinfo->mem->alloc_small)
    ((j_common_ptr) cinfo, JPOOL_IMAGE, HIST_C0_ELEMS * SIZEOF (hist2d));
  for (i = 0; i < HIST_C0_ELEMS; i++)
    {
      cquantize->histogram[i] = (hist2d) (*cinfo->mem->alloc_large)
       ((j_common_ptr) cinfo, JPOOL_IMAGE,
        HIST_C1_ELEMS * HIST_C2_ELEMS * SIZEOF (histcell));
    }
  cquantize->needs_zeroed = TRUE;  /* histogram is garbage now */
#else
  cquantize->histogram = (hist3d) safe_emalloc (HIST_C0_ELEMS, sizeof (hist2d), 0);
  for (i = 0; i < HIST_C0_ELEMS; i++)
    {
      cquantize->histogram[i] =
       (hist2d) safe_emalloc (HIST_C1_ELEMS * HIST_C2_ELEMS, sizeof (histcell), 0);
      if (!cquantize->histogram[i])
       {
         goto outOfMemory;
       }
    }
#endif

#ifdef ORIGINAL_LIB_JPEG
  /* Allocate storage for the completed colormap, if required.
   * We do this now since it is FAR storage and may affect
   * the memory manager's space calculations.
   */
  if (cinfo->enable_2pass_quant)
    {
      /* Make sure color count is acceptable */
      int desired = cinfo->desired_number_of_colors;
      /* Lower bound on # of colors ... somewhat arbitrary as long as > 0 */
      if (desired < 8)
       ERREXIT1 (cinfo, JERR_QUANT_FEW_COLORS, 8);
      /* Make sure colormap indexes can be represented by JSAMPLEs */
      if (desired > MAXNUMCOLORS)
       ERREXIT1 (cinfo, JERR_QUANT_MANY_COLORS, MAXNUMCOLORS);
      cquantize->sv_colormap = (*cinfo->mem->alloc_sarray)
       ((j_common_ptr) cinfo, JPOOL_IMAGE, (JDIMENSION) desired,
        (JDIMENSION) 3);
      cquantize->desired = desired;
    }
  else
    cquantize->sv_colormap = NULL;

  /* Only F-S dithering or no dithering is supported. */
  /* If user asks for ordered dither, give him F-S. */
  if (cinfo->dither_mode != JDITHER_NONE)
    cinfo->dither_mode = JDITHER_FS;

  /* Allocate Floyd-Steinberg workspace if necessary.
   * This isn't really needed until pass 2, but again it is FAR storage.
   * Although we will cope with a later change in dither_mode,
   * we do not promise to honor max_memory_to_use if dither_mode changes.
   */
  if (cinfo->dither_mode == JDITHER_FS)
    {
      cquantize->fserrors = (FSERRPTR) (*cinfo->mem->alloc_large)
       ((j_common_ptr) cinfo, JPOOL_IMAGE,
        (size_t) ((cinfo->output_width + 2) * (3 * SIZEOF (FSERROR))));
      /* Might as well create the error-limiting table too. */
      init_error_limit (cinfo);
    }
#else

  cquantize->fserrors = (FSERRPTR) safe_emalloc (3, sizeof (FSERROR), 0);
  init_error_limit (oim, nim, cquantize);
  arraysize = (size_t) ((nim->sx + 2) * (3 * sizeof (FSERROR)));
  /* Allocate Floyd-Steinberg workspace. */
  cquantize->fserrors = gdRealloc(cquantize->fserrors, arraysize);
  memset(cquantize->fserrors, 0, arraysize);
  if (!cquantize->fserrors)
    {
      goto outOfMemory;
    }
  cquantize->on_odd_row = FALSE;

  /* Do the work! */
  zeroHistogram (cquantize->histogram);
  prescan_quantize (oim, nim, cquantize);
  /* TBB 2.0.5: pass colorsWanted, not 256! */
  select_colors (oim, nim, cquantize, colorsWanted);
  zeroHistogram (cquantize->histogram);
  if (dither)
    {
      pass2_fs_dither (oim, nim, cquantize);
    }
  else
    {
      pass2_no_dither (oim, nim, cquantize);
    }
#if 0                       /* 2.0.12; we no longer attempt full alpha in palettes */
  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;
           }
       }
    }
#endif

  /* If we had a 'transparent' color, increment the color count so it's
   * officially in the palette and convert the transparent variable to point to
   * an index rather than a color (Its data already exists and transparent
   * pixels have already been mapped to it by this point, it is done late as to
   * avoid color matching / dithering with it). */
  if (oim->transparent >= 0)
    {
      nim->transparent = nim->colorsTotal;
      nim->colorsTotal++;
    }

  /* Success! Get rid of the truecolor image data. */
  if (!cimP) { 
    oim->trueColor = 0;
    /* Junk the truecolor pixels */
    for (i = 0; i < oim->sy; i++)
      {
        gdFree (oim->tpixels[i]);
      }
    gdFree (oim->tpixels);
    oim->tpixels = 0;
  }
  goto success;
  /* Tediously free stuff. */
outOfMemory:
  if (oim->trueColor)
    {
      if (!cimP) {
        /* On failure only */
        for (i = 0; i < nim->sy; i++)
       {
         if (nim->pixels[i])
           {
             gdFree (nim->pixels[i]);
           }
       }
        if (nim->pixels)
       {
         gdFree (nim->pixels);
       }
        nim->pixels = 0;
      } else {
        gdImageDestroy(nim);
        *cimP = 0;
      }
    }
success:
  for (i = 0; i < HIST_C0_ELEMS; i++)
    {
      if (cquantize->histogram[i])
       {
         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);
    }

#endif
}

Here is the call graph for this function:

Here is the caller graph for this function:

init_error_limit ( gdImagePtr  oim,
gdImagePtr  nim,
my_cquantize_ptr  cquantize 
)

Definition at line 1591 of file gd_topal.c.

{
  int *table;
  int in, out;
#ifdef ORIGINAL_LIB_JPEG
  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
  table = (int *) (*cinfo->mem->alloc_small)
    ((j_common_ptr) cinfo, JPOOL_IMAGE, (MAXJSAMPLE * 2 + 1) * SIZEOF (int));
#else
  cquantize->error_limiter_storage =
    (int *) safe_emalloc ((MAXJSAMPLE * 2 + 1), sizeof (int), 0);
  if (!cquantize->error_limiter_storage)
    {
      return;
    }
  table = cquantize->error_limiter_storage;
#endif

  table += MAXJSAMPLE;             /* so can index -MAXJSAMPLE .. +MAXJSAMPLE */
  cquantize->error_limiter = table;

#define STEPSIZE ((MAXJSAMPLE+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 <= MAXJSAMPLE; in++)
    {
      table[in] = out;
      table[-in] = -out;
    }
#undef STEPSIZE
}

Here is the call graph for this function:

Here is the caller graph for this function:

LOCAL ( boxptr  )

Definition at line 423 of file gd_topal.c.

{
  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 ( void  )

Definition at line 1098 of file gd_topal.c.

{
  int ic0, ic1, ic2;
  int i, icolor;
  register INT32 *bptr;            /* pointer into bestdist[] array */
  JSAMPLE *cptr;            /* pointer into bestcolor[] array */
  INT32 dist0, dist1;              /* initial distance values */
  register INT32 dist2;            /* current distance in inner loop */
  INT32 xx0, xx1;           /* distance increments */
  register INT32 xx2;
  INT32 inc0, inc1, inc2;   /* initial values for increments */
  /* This array holds the distance to the nearest-so-far color for each cell */
  INT32 bestdist[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS];

  /* Initialize best-distance for each cell of the update box */
  bptr = bestdist;
  for (i = BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_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)

  for (i = 0; i < numcolors; i++)
    {
      int r, g, b;
#ifdef ORIGINAL_LIB_JPEG

      icolor = GETJSAMPLE (colorlist[i]);
      r = GETJSAMPLE (cinfo->colormap[0][icolor]);
      g = GETJSAMPLE (cinfo->colormap[1][icolor]);
      b = GETJSAMPLE (cinfo->colormap[2][icolor]);
#else
      icolor = colorlist[i];
      r = nim->red[icolor];
      g = nim->green[icolor];
      b = nim->blue[icolor];
#endif

      /* Compute (square of) distance from minc0/c1/c2 to this color */
      inc0 = (minc0 - r) * C0_SCALE;
      dist0 = inc0 * inc0;
      inc1 = (minc1 - g) * C1_SCALE;
      dist0 += inc1 * inc1;
      inc2 = (minc2 - b) * C2_SCALE;
      dist0 += inc2 * inc2;
      /* 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;
      /* 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--)
              {
                if (dist2 < *bptr)
                  {
                    *bptr = dist2;
                    *cptr = (JSAMPLE) icolor;
                  }
                dist2 += xx2;
                xx2 += 2 * STEP_C2 * STEP_C2;
                bptr++;
                cptr++;
              }
             dist1 += xx1;
             xx1 += 2 * STEP_C1 * STEP_C1;
           }
         dist0 += xx0;
         xx0 += 2 * STEP_C0 * STEP_C0;
       }
    }
}

Here is the call graph for this function:

median_cut ( gdImagePtr  oim,
gdImagePtr  nim,
my_cquantize_ptr  cquantize,
boxptr  boxlist,
int  numboxes,
int  desired_colors 
)

Definition at line 603 of file gd_topal.c.

{
  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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

pass2_fs_dither ( gdImagePtr  oim,
gdImagePtr  nim,
my_cquantize_ptr  cquantize 
)

Definition at line 1365 of file gd_topal.c.

{
#else
pass2_fs_dither (j_decompress_ptr cinfo,
               JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows)
/* This version performs Floyd-Steinberg dithering */
{
  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
  JSAMPROW inptr;           /* => current input pixel */
#endif
  hist3d histogram = cquantize->histogram;
  register LOCFSERROR cur0, cur1, cur2;   /* current error or pixel value */
  LOCFSERROR belowerr0, belowerr1, belowerr2;    /* error for pixel below cur */
  LOCFSERROR bpreverr0, bpreverr1, bpreverr2;    /* error for below/prev col */
  register FSERRPTR errorptr;      /* => fserrors[] at column before current */
  histptr cachep;
  int dir;                  /* +1 or -1 depending on direction */
  int dir3;                 /* 3*dir, for advancing inptr & errorptr */
  int row;
  JDIMENSION col;
#ifdef ORIGINAL_LIB_JPEG
  JSAMPROW outptr;          /* => current output pixel */
  JDIMENSION width = cinfo->output_width;
  JSAMPLE *range_limit = cinfo->sample_range_limit;
  JSAMPROW colormap0 = cinfo->colormap[0];
  JSAMPROW colormap1 = cinfo->colormap[1];
  JSAMPROW colormap2 = cinfo->colormap[2];
#else
  int *inptr;               /* => current input pixel */
  unsigned char *outptr;    /* => current output pixel */
  int width = oim->sx;
  int num_rows = oim->sy;
  int *colormap0 = nim->red;
  int *colormap1 = nim->green;
  int *colormap2 = nim->blue;
#endif
  int *error_limit = cquantize->error_limiter;


  SHIFT_TEMPS for (row = 0; row < num_rows; row++)
    {
      inptr = input_buf[row];
      outptr = output_buf[row];
      if (cquantize->on_odd_row)
       {
         /* work right to left in this row */
         inptr += (width - 1) * 3; /* so point to rightmost pixel */
         outptr += width - 1;
         dir = -1;
         dir3 = -3;
         errorptr = cquantize->fserrors + (width + 1) * 3;     /* => entry after last column */
#ifdef ORIGINAL_LIB_JPEG_REVERSE_ODD_ROWS
         cquantize->on_odd_row = FALSE;   /* flip for next time */
#endif
       }
      else
       {
         /* work left to right in this row */
         dir = 1;
         dir3 = 3;
         errorptr = cquantize->fserrors;  /* => entry before first real column */
#ifdef ORIGINAL_LIB_JPEG_REVERSE_ODD_ROWS
         cquantize->on_odd_row = TRUE;    /* flip for next time */
#endif
       }
      /* Preset error values: no error propagated to first pixel from left */
      cur0 = cur1 = cur2 = 0;
      /* and no error propagated to row below yet */
      belowerr0 = belowerr1 = belowerr2 = 0;
      bpreverr0 = bpreverr1 = bpreverr2 = 0;

      for (col = width; col > 0; col--)
       {

         /* If this pixel is transparent, we want to assign it to the special
          * transparency color index past the end of the palette rather than
          * go through matching / dithering. */
         if ((oim->transparent >= 0) && (*inptr == oim->transparent))
           {
             *outptr = nim->colorsTotal;
             errorptr[0] = 0;
             errorptr[1] = 0;
             errorptr[2] = 0;
             errorptr[3] = 0;
             inptr += dir;
             outptr += dir;
             errorptr += dir3;
             continue;
           }
         /* 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[dir3 + 0] + 8, 4);
         cur1 = RIGHT_SHIFT (cur1 + errorptr[dir3 + 1] + 8, 4);
         cur2 = RIGHT_SHIFT (cur2 + errorptr[dir3 + 2] + 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];
         /* Form pixel value + error, and range-limit to 0..MAXJSAMPLE.
          * The maximum error is +- MAXJSAMPLE (or less with error limiting);
          * this sets the required size of the range_limit array.
          */
#ifdef ORIGINAL_LIB_JPEG
         cur0 += GETJSAMPLE (inptr[0]);
         cur1 += GETJSAMPLE (inptr[1]);
         cur2 += GETJSAMPLE (inptr[2]);
         cur0 = GETJSAMPLE (range_limit[cur0]);
         cur1 = GETJSAMPLE (range_limit[cur1]);
         cur2 = GETJSAMPLE (range_limit[cur2]);
#else
         cur0 += gdTrueColorGetRed (*inptr);
         cur1 += gdTrueColorGetGreen (*inptr);
         cur2 += gdTrueColorGetBlue (*inptr);
         range_limit (cur0);
         range_limit (cur1);
         range_limit (cur2);
#endif

         /* Index into the cache with adjusted pixel value */
         cachep =
           &histogram[cur0 >> C0_SHIFT][cur1 >> C1_SHIFT][cur2 >> C2_SHIFT];
         /* If we have not seen this color before, find nearest colormap */
         /* entry and update the cache */
         if (*cachep == 0)
#ifdef ORIGINAL_LIB_JPEG
           fill_inverse_cmap (cinfo, cur0 >> C0_SHIFT, cur1 >> C1_SHIFT,
                            cur2 >> C2_SHIFT);
#else
           fill_inverse_cmap (oim, nim, cquantize, cur0 >> C0_SHIFT,
                            cur1 >> C1_SHIFT, cur2 >> C2_SHIFT);
#endif
         /* Now emit the colormap index for this cell */
         {
           register int pixcode = *cachep - 1;
           *outptr = (JSAMPLE) pixcode;
           /* Compute representation error for this pixel */
#define GETJSAMPLE
           cur0 -= GETJSAMPLE (colormap0[pixcode]);
           cur1 -= GETJSAMPLE (colormap1[pixcode]);
           cur2 -= GETJSAMPLE (colormap2[pixcode]);
#undef GETJSAMPLE
         }
         /* 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 */
         }
         /* 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.
          */
#ifdef ORIGINAL_LIB_JPEG
         inptr += dir3;     /* Advance pixel pointers to next column */
#else
         inptr += dir;             /* Advance pixel pointers to next column */
#endif
         outptr += dir;
         errorptr += dir3;  /* 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;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

pass2_no_dither ( gdImagePtr  oim,
gdImagePtr  nim,
my_cquantize_ptr  cquantize 
)

Definition at line 1286 of file gd_topal.c.

{
  register int *inptr;
  register unsigned char *outptr;
  int width = oim->sx;
  int num_rows = oim->sy;
#else
pass2_no_dither (j_decompress_ptr cinfo,
               JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows)
/* This version performs no dithering */
{
  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
  register JSAMPROW inptr, outptr;
  JDIMENSION width = cinfo->output_width;
#endif
  hist3d histogram = cquantize->histogram;
  register int c0, c1, c2;
  int row;
  JDIMENSION col;
  register histptr cachep;


  for (row = 0; row < num_rows; row++)
    {
      inptr = input_buf[row];
      outptr = output_buf[row];
      for (col = width; col > 0; col--)
       {
         /* get pixel value and index into the cache */
         int r, g, b;
#ifdef ORIGINAL_LIB_JPEG
         r = GETJSAMPLE (*inptr++);
         g = GETJSAMPLE (*inptr++);
         b = GETJSAMPLE (*inptr++);
#else
         r = gdTrueColorGetRed (*inptr);
         g = gdTrueColorGetGreen (*inptr);
         /* 
            2.0.24: inptr must not be incremented until after
            transparency check, if any. Thanks to "Super Pikeman." 
          */
         b = gdTrueColorGetBlue (*inptr);

         /* If the pixel is transparent, we assign it the palette index that
          * will later be added at the end of the palette as the transparent
          * index. */
         if ((oim->transparent >= 0) && (oim->transparent == *(inptr - 1)))
           {
             *outptr++ = nim->colorsTotal;
             inptr++;
             continue;
           }
         inptr++;
#endif
         c0 = r >> C0_SHIFT;
         c1 = g >> C1_SHIFT;
         c2 = b >> C2_SHIFT;
         cachep = &histogram[c0][c1][c2];
         /* If we have not seen this color before, find nearest colormap entry */
         /* and update the cache */
         if (*cachep == 0)
#ifdef ORIGINAL_LIB_JPEG
           fill_inverse_cmap (cinfo, c0, c1, c2);
#else
           fill_inverse_cmap (oim, nim, cquantize, c0, c1, c2);
#endif
         /* Now emit the colormap index for this cell */
#ifdef ORIGINAL_LIB_JPEG
         *outptr++ = (JSAMPLE) (*cachep - 1);
#else
         *outptr++ = (*cachep - 1);
#endif
       }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

prescan_quantize ( gdImagePtr  oim,
gdImagePtr  nim,
my_cquantize_ptr  cquantize 
)

Definition at line 344 of file gd_topal.c.

{
#else
prescan_quantize (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
                JSAMPARRAY output_buf, int num_rows)
{
  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
#endif
  register JSAMPROW ptr;
  register histptr histp;
  register hist3d histogram = cquantize->histogram;
  int row;
  JDIMENSION col;
#ifdef ORIGINAL_LIB_JPEG
  JDIMENSION width = cinfo->output_width;
#else
  int width = oim->sx;
  int num_rows = oim->sy;
#endif

  for (row = 0; row < num_rows; row++)
    {
      ptr = input_buf[row];
      for (col = width; col > 0; col--)
       {
#ifdef ORIGINAL_LIB_JPEG
         int r = GETJSAMPLE (ptr[0]) >> C0_SHIFT;
         int g = GETJSAMPLE (ptr[1]) >> C1_SHIFT;
         int b = GETJSAMPLE (ptr[2]) >> C2_SHIFT;
#else
         int r = gdTrueColorGetRed (*ptr) >> C0_SHIFT;
         int g = gdTrueColorGetGreen (*ptr) >> C1_SHIFT;
         int b = gdTrueColorGetBlue (*ptr) >> C2_SHIFT;
         /* 2.0.12: Steven Brown: support a single totally transparent
            color in the original. */
         if ((oim->transparent >= 0) && (*ptr == oim->transparent))
           {
             ptr++;
             continue;
           }
#endif
         /* get pixel value and index into the histogram */
         histp = &histogram[r][g][b];
         /* increment, check for overflow and undo increment if so. */
         if (++(*histp) == 0)
           (*histp)--;
#ifdef ORIGINAL_LIB_JPEG
         ptr += 3;
#else
         ptr++;
#endif
       }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

select_colors ( gdImagePtr  oim,
gdImagePtr  nim,
my_cquantize_ptr  cquantize,
int  desired_colors 
)

Definition at line 784 of file gd_topal.c.

{
  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
  boxlist = (boxptr) safe_emalloc(desired_colors, sizeof (box), 1);
#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;

  /* If we had a pure transparency color, add it as the last palette entry.
   * Skip incrementing the color count so that the dither / matching phase
   * won't use it on pixels that shouldn't have been transparent.  We'll
   * increment it after all that finishes. */
  if (oim->transparent >= 0)
    {
      /* Save the transparent color. */
      nim->red[nim->colorsTotal] = gdTrueColorGetRed (oim->transparent);
      nim->green[nim->colorsTotal] = gdTrueColorGetGreen (oim->transparent);
      nim->blue[nim->colorsTotal] = gdTrueColorGetBlue (oim->transparent);
      nim->alpha[nim->colorsTotal] = gdAlphaTransparent;
      nim->open[nim->colorsTotal] = 0;
    }

  gdFree (boxlist);
#endif
}

Here is the call graph for this function:

Here is the caller graph for this function:

update_box ( gdImagePtr  oim,
gdImagePtr  nim,
my_cquantize_ptr  cquantize,
boxptr  boxp 
)

Definition at line 467 of file gd_topal.c.

{
#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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void zeroHistogram ( hist3d  histogram) [static]

Definition at line 1745 of file gd_topal.c.

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

Here is the caller graph for this function: