dither2.c

ucOS 模拟环境

//----------------------------------------------------------------------
// File Name :		dither2.c
// Project   :		gif_jpeg
// Module    :
// Memo      :
//                Author       Date       Description
//              -----------------------------------------------
//				  dts			  2004.3.10
//               
//----------------------------------------------------------------------

#include "gif_dither2.h"
#include "gif_error.h"
#include "gif_gray.h"
#include "gif_interface.h"
#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 */

/* Relabel R/G/B as components 0/1/2, respecting the RGB ordering defined
 * in jmorecfg.h.  As the code stands, it will do the right thing for R,G,B
 * and B,G,R orders.  If you define some other weird order in jmorecfg.h,
 * you'll get compile errors until you extend this logic.  In that case
 * you'll probably want to tweak the histogram sizes too.
 */

#if RGB_RED == 0
#define C0_SCALE R_SCALE
#endif
#if RGB_BLUE == 0
#define C0_SCALE B_SCALE
#endif
#if RGB_GREEN == 1
#define C1_SCALE G_SCALE
#endif
#if RGB_RED == 2
#define C2_SCALE R_SCALE
#endif
#if RGB_BLUE == 2
#define C2_SCALE B_SCALE
#endif


/*
 * First we have the histogram data structure and routines for creating it.
 *
 * The number of bits of precision can be adjusted by changing these symbols.
 * We recommend keeping 6 bits for G and 5 each for R and B.
 * If you have plenty of memory and cycles, 6 bits all around gives marginally
 * better results; if you are short of memory, 5 bits all around will save
 * some space but degrade the results.
 * To maintain a fully accurate histogram, we'd need to allocate a "long"
 * (preferably unsigned long) for each cell.  In practice this is overkill;
 * we can get by with 16 bits per cell.  Few of the cell counts will overflow,
 * and clamping those that do overflow to the maximum value will give close-
 * enough results.  This reduces the recommended histogram size from 256Kb
 * to 128Kb, which is a useful savings on PC-class machines.
 * (In the second pass the histogram space is re-used for pixel mapping data;
 * in that capacity, each cell must be able to store zero to the number of
 * desired colors.  16 bits/cell is plenty for that too.)
 * Since the JPEG code is intended to run in small memory model on 80x86
 * machines, we can't just allocate the histogram in one chunk.  Instead
 * of a true 3-D array, we use a row of pointers to 2-D arrays.  Each
 * pointer corresponds to a C0 value (typically 2^5 = 32 pointers) and
 * each 2-D array has 2^6*2^5 = 2048 or 2^6*2^6 = 4096 entries.  Note that
 * on 80x86 machines, the pointer row is in near memory but the actual
 * arrays are in far memory (same arrangement as we use for image arrays).
 */

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

/* These will do the right thing for either R,G,B or B,G,R color order,
 * but you may not like the results for other color orders.
 */
#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 */

/* Number of elements along histogram axes. */
#define HIST_C0_ELEMS  (1<<HIST_C0_BITS)
#define HIST_C1_ELEMS  (1<<HIST_C1_BITS)
#define HIST_C2_ELEMS  (1<<HIST_C2_BITS)

/* These are the amounts to shift an input value to get a histogram index. */
#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)


typedef uchar histcell;	/* histogram cell; prefer an unsigned type */

typedef histcell FAR * histptr;	/* for pointers to histogram cells */

typedef histcell hist1d[HIST_C2_ELEMS]; /* typedefs for the array */
typedef hist1d FAR * hist2d;	/* type for the 2nd-level pointers */
typedef hist2d * hist3d;	/* type for top-level pointer */
#define BITS_IN_JSAMPLE  8	/* use 8 or 12 */

#if BITS_IN_JSAMPLE == 8
typedef INT16 FSERROR;		/* 16 bits should be enough */
typedef int LOCFSERROR;		/* use 'int' for calculation temps */
#else
typedef INT32 FSERROR;		/* may need more than 16 bits */
typedef INT32 LOCFSERROR;	/* be sure calculation temps are big enough */
#endif

typedef FSERROR FAR *FSERRPTR;	/* pointer to error array (in FAR storage!) */

typedef struct {

  /* Space for the eventually created colormap is stashed here */
  uchar** sv_colormap;	/* colormap allocated at init time */
  int desired;			/* desired # of colors = size of colormap */

  /* Variables for accumulating image statistics */
  hist3d histogram;		/* pointer to the histogram */

  boolean needs_zeroed;		/* TRUE if next pass must zero histogram */

  /* Variables for Floyd-Steinberg dithering */
  FSERRPTR fserrors;		/* accumulated errors */
  boolean on_odd_row;		/* flag to remember which row we are on */
  int * error_limiter;		/* table for clamping the applied error */
} my_cquantizer2;

typedef my_cquantizer2 * my_cquantize_ptr2;


#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)

typedef struct {
  /* The bounds of the box (inclusive); expressed as histogram indexes */
  int c0min, c0max;
  int c1min, c1max;
  int c2min, c2max;
  /* The volume (actually 2-norm) of the box */
  INT32 volume;
  /* The number of nonzero histogram cells within this box */
  long colorcount;
} box;

typedef box * boxptr;
/* static function define */


static void    gif_update_box (decompress_info_ptr cinfo, boxptr boxp);
static boxptr  gif_find_biggest_color_pop (boxptr boxlist, int numboxes);
static Bool  gif_init_error_limit (decompress_info_ptr cinfo);
static void gif_pass2_no_dither (decompress_info_ptr cinfo,
		 uchar* input_buf, uchar* output_buf, int num_rows);

static void gif_zero_far (void FAR * target, size_t bytestozero);
static Bool gif_prepare_range_limit_table (decompress_info_ptr cinfo);

static void  gif_fill_inverse_cmap (decompress_info_ptr cinfo, int c0, int c1, int c2);

/* end the static function define*/
//GLOABLE variable define 
#ifdef PCVER
	extern FILE *FileError; 
#endif
//end gloable variable define  


//====================================================================================
// Function Name:	static  boxptr  find_biggest_volume (boxptr boxlist, int numboxes)
// Purpose      :	Find the splittable box with the largest (scaled) volume
// Parameter    :	
// Return       :	Returns NULL if no splittable boxes remain 		
// Remarks      :	
// Change Log   :	
//                Author       Date       Description	
//              -----------------------------------------------	
//=====================================================================================
static  boxptr  find_biggest_volume (boxptr boxlist, int numboxes)
{
   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;
}

//====================================================================================
// Function Name:	static boxptr gif_find_biggest_color_pop  (boxptr boxlist, int numboxes)
// Purpose      :	Find the splittable box with the largest color population
// Parameter    :	
// Return       :	Returns NULL if no splittable boxes remain		
// Remarks      :	
// Change Log   :	
//                Author       Date       Description	
//              -----------------------------------------------	
//=====================================================================================
static boxptr gif_find_biggest_color_pop  (boxptr boxlist, int numboxes)
{
   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;
}

//====================================================================================
// Function Name:	static int gif_median_cut (decompress_info_ptr cinfo, boxptr boxlist, 
//                                           int numboxes, int desired_colors)
// Purpose      :	Repeatedly select and split the largest box until we have enough boxes
// Parameter    :	
// Return       :	
// Remarks      :	
// Change Log   :	
//                Author       Date       Description	
//              -----------------------------------------------	
//=====================================================================================
static int gif_median_cut (decompress_info_ptr cinfo, boxptr boxlist, int numboxes,
	    int desired_colors)
{
   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 = gif_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 */
      gif_update_box(cinfo, b1);
      gif_update_box(cinfo, b2);
      numboxes++;
   }
   return numboxes;
}
//====================================================================================
// Function Name:	static void gif_update_box (decompress_info_ptr cinfo, boxptr boxp)
// Purpose      :	Shrink the min/max bounds of a box to enclose only nonzero elements,
//                and recompute its volume and population
// Parameter    :	
// Return       :	
// Remarks      :	
// Change Log   :	
//                Author       Date       Description	
//              -----------------------------------------------	
//=====================================================================================
static void gif_update_box (decompress_info_ptr cinfo, boxptr boxp)
{
   my_cquantize_ptr2 cquantize = (my_cquantize_ptr2) cinfo->cquantize;
   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)