dither2.c

ucOS 模拟环境

{
   boxptr boxlist;
   int numboxes;
   int i;
   /* Allocate workspace for box list */
   boxlist = (boxptr) (gif_alloc_buf)(desired_colors * SIZEOF(box));
   if(boxlist == NULL)
   	   return FALSE;
   /* 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;
   /* Shrink it to actually-used volume and set its statistics */
   gif_update_box(cinfo, & boxlist[0]);
   /* Perform median-cut to produce final box list */
   numboxes = gif_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;
   return TRUE;
}

//====================================================================================
// Function Name:	static void gif_find_best_colors (decompress_info_ptr  cinfo, int minc0, int minc1, int minc2,
//                   		  int numcolors, JSAMPLE colorlist[], JSAMPLE bestcolor[])

// Purpose      :	 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. 
// Parameter    :	
// Return       :	
// Remarks      :	
// Change Log   :	
//                Author       Date       Description	
//              -----------------------------------------------	
//=====================================================================================

static void gif_find_best_colors (decompress_info_ptr  cinfo, int minc0, int minc1, int minc2,
		  int numcolors, JSAMPLE colorlist[], JSAMPLE bestcolor[])
{
   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++) 
   {
      icolor = GETJSAMPLE(colorlist[i]);
      /* Compute (square of) distance from minc0/c1/c2 to this color */
      inc0 = (minc0 - GETJSAMPLE(cinfo->colormap[0][icolor])) * C0_SCALE;
      dist0 = inc0*inc0;
      inc1 = (minc1 - GETJSAMPLE(cinfo->colormap[1][icolor])) * C1_SCALE;
      dist0 += inc1*inc1;
      inc2 = (minc2 - GETJSAMPLE(cinfo->colormap[2][icolor])) * 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;
       }
   }
}
//====================================================================================
// Function Name:	static void  gif_fill_inverse_cmap (decompress_info_ptr cinfo, int c0, int c1, int c2)
// Purpose      :	Fill the inverse-colormap entries in the update box that contains
//                 histogram cell c0/c1/c2.  (Only that one cell MUST be filled, but
// Parameter    :	
// Return       :	
// Remarks      :	
// Change Log   :	
//                Author       Date       Description	
//              -----------------------------------------------	
//=====================================================================================
static void  gif_fill_inverse_cmap (decompress_info_ptr cinfo, int c0, int c1, int c2)
{
   my_cquantize_ptr2 cquantize = (my_cquantize_ptr2) cinfo->cquantize;
   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.
    */
   numcolors = find_nearby_colors(cinfo, minc0, minc1, minc2, colorlist);

   /* Determine the actually nearest colors. */
   gif_find_best_colors(cinfo, minc0, minc1, minc2, 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;
   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++) 
         {
	         *cachep++ = (histcell) (GETJSAMPLE(*cptr++) + 1);
         }
      }
   }
}
//====================================================================================
// Function Name:	void gif_pass2_fs_dither (decompress_info_ptr cinfo, uchar* input_buf, uchar* output_buf, int num_rows)
// Purpose      :	 This version performs Floyd-Steinberg dithering
// Parameter    :	
// Return       :	
// Remarks      :	
// Change Log   :	
//                Author       Date       Description	
//              -----------------------------------------------	
//=====================================================================================
void gif_pass2_fs_dither (decompress_info_ptr cinfo,
		 uchar* input_buf, uchar* output_buf, int num_rows)
{
   my_cquantize_ptr2 cquantize = (my_cquantize_ptr2) cinfo->cquantize;
   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 */
   JSAMPROW inptr;		/* => current input pixel */
   JSAMPROW outptr;		/* => current output pixel */
   histptr cachep;
   int dir;			/* +1 or -1 depending on direction */
   int dir3;			/* 3*dir, for advancing inptr & errorptr */
   int row;
   JDIMENSION col;

   JDIMENSION width = cinfo->output_width;
   JSAMPLE *range_limit = cinfo->sample_range_limit;
   int *error_limit = cquantize->error_limiter;
   JSAMPROW colormap0 = cinfo->colormap[0];
   JSAMPROW colormap1 = cinfo->colormap[1];
   JSAMPROW colormap2 = cinfo->colormap[2];
   //SHIFT_TEMPS

  

   for (row = 0; row < num_rows; row++) 
   {
      inptr = input_buf + row * 3 * width ;
      outptr = output_buf + row * width;
    
      /* work left to right in this row */
      dir = 1;
      dir3 = 3;
      errorptr = cquantize->fserrors; /* => entry before first real column */
      /* 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--) 
      {
         /* 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.
         */
         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]);
         /* 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)
         {
            gif_fill_inverse_cmap(cinfo, cur0>>C0_SHIFT,cur1>>C1_SHIFT,cur2>>C2_SHIFT);
         }
         /* Now emit the colormap index for this cell */
         { 
            register int pixcode = *cachep - 1;
	      
            *outptr = (JSAMPLE) pixcode;
	         /* Compute representation error for this pixel */
	         cur0 -= GETJSAMPLE(colormap0[pixcode]);
	         cur1 -= GETJSAMPLE(colormap1[pixcode]);
	         cur2 -= GETJSAMPLE(colormap2[pixcode]);
         }
         /* 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.
          */
         inptr += dir3;		/* Advance pixel pointers to next column */
         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;
   }
}

//====================================================================================
// Function Name:	Bool  gif_init_2pass_quantizer (decompress_info_ptr cinfo, uchar *gram)
// Purpose      :	 
// Parameter    :	
// Return       :	
// Remarks      :	
// Change Log   :	
//                Author       Date       Description	
//              -----------------------------------------------	
//=====================================================================================
Bool  gif_init_2pass_quantizer (decompress_info_ptr cinfo, uchar *gram)
{
   my_cquantize_ptr2 cquantize;
   int i;
   
   cquantize = (my_cquantize_ptr2) gif_alloc_buf (SIZEOF(my_cquantizer2));
   
   if(cquantize == NULL)
   {
      return FALSE;
   }
   cinfo->cquantize = (struct jpeg_color_quantizer *) cquantize;
   cquantize->fserrors = NULL;	/* flag optional arrays not allocated */
   cquantize->error_limiter = NULL;
   cinfo->enable_2pass_quant = TRUE;
   /* Make sure jdmaster didn't give me a case I can't handle */
   if (cinfo->out_color_components != 3)
   { 
#ifdef PCVER