jquant2.pas

用pascal寫的jpeg codec, 測試過的

  is specified by the center coordinates of its first cell.  The number of
  candidate colormap entries is returned, and their colormap indexes are
  placed in colorlist[].
  This routine uses Heckbert's "locally sorted search" criterion to select
  the colors that need further consideration. }

var
  numcolors : int;
  maxc0, maxc1, maxc2 : int;
  centerc0, centerc1, centerc2 : int;
  i, x, ncolors : int;
  minmaxdist, min_dist, max_dist, tdist : INT32;
  mindist : array[0..MAXNUMCOLORS-1] of INT32;
  	{ min distance to colormap entry i }
begin
  numcolors := cinfo^.actual_number_of_colors;

  { 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 shl BOX_C0_SHIFT) - (1 shl C0_SHIFT));
  centerc0 := (minc0 + maxc0) shr 1;
  maxc1 := minc1 + ((1 shl BOX_C1_SHIFT) - (1 shl C1_SHIFT));
  centerc1 := (minc1 + maxc1) shr 1;
  maxc2 := minc2 + ((1 shl BOX_C2_SHIFT) - (1 shl C2_SHIFT));
  centerc2 := (minc2 + maxc2) shr 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 := long($7FFFFFFF);

  for i := 0 to pred(numcolors) do
  begin
    { We compute the squared-c0-distance term, then add in the other two. }
    x := GETJSAMPLE(cinfo^.colormap^[0]^[i]);
    if (x < minc0) then
    begin
      tdist := (x - minc0) * C0_SCALE;
      min_dist := tdist*tdist;
      tdist := (x - maxc0) * C0_SCALE;
      max_dist := tdist*tdist;
    end
    else
      if (x > maxc0) then
      begin
        tdist := (x - maxc0) * C0_SCALE;
        min_dist := tdist*tdist;
        tdist := (x - minc0) * C0_SCALE;
        max_dist := tdist*tdist;
      end
      else
      begin
        { within cell range so no contribution to min_dist }
        min_dist := 0;
        if (x <= centerc0) then
        begin
          tdist := (x - maxc0) * C0_SCALE;
          max_dist := tdist*tdist;
        end
        else
        begin
          tdist := (x - minc0) * C0_SCALE;
          max_dist := tdist*tdist;
        end;
      end;

    x := GETJSAMPLE(cinfo^.colormap^[1]^[i]);
    if (x < minc1) then
    begin
      tdist := (x - minc1) * C1_SCALE;
      Inc(min_dist, tdist*tdist);
      tdist := (x - maxc1) * C1_SCALE;
      Inc(max_dist, tdist*tdist);
    end
    else
      if (x > maxc1) then
      begin
        tdist := (x - maxc1) * C1_SCALE;
        Inc(min_dist, tdist*tdist);
        tdist := (x - minc1) * C1_SCALE;
        Inc(max_dist, tdist*tdist);
      end
      else
      begin
        { within cell range so no contribution to min_dist }
        if (x <= centerc1) then
        begin
	  tdist := (x - maxc1) * C1_SCALE;
	  Inc(max_dist, tdist*tdist);
        end
        else
        begin
	  tdist := (x - minc1) * C1_SCALE;
	  Inc(max_dist, tdist*tdist);
        end
      end;

    x := GETJSAMPLE(cinfo^.colormap^[2]^[i]);
    if (x < minc2) then
    begin
      tdist := (x - minc2) * C2_SCALE;
      Inc(min_dist, tdist*tdist);
      tdist := (x - maxc2) * C2_SCALE;
      Inc(max_dist, tdist*tdist);
    end
    else
      if (x > maxc2) then
      begin
        tdist := (x - maxc2) * C2_SCALE;
        Inc(min_dist, tdist*tdist);
        tdist := (x - minc2) * C2_SCALE;
        Inc(max_dist, tdist*tdist);
      end
      else
      begin
        { within cell range so no contribution to min_dist }
        if (x <= centerc2) then
        begin
	  tdist := (x - maxc2) * C2_SCALE;
	  Inc(max_dist, tdist*tdist);
        end
        else
        begin
	  tdist := (x - minc2) * C2_SCALE;
	  Inc(max_dist, tdist*tdist);
        end;
      end;

    mindist[i] := min_dist;	{ save away the results }
    if (max_dist < minmaxdist) then
      minmaxdist := max_dist;
  end;

  { 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 to pred(numcolors) do
  begin
    if (mindist[i] <= minmaxdist) then
    begin
      colorlist[ncolors] := JSAMPLE(i);
      Inc(ncolors);
    end;
  end;
  find_nearby_colors := ncolors;
end;


{LOCAL}
procedure find_best_colors (cinfo : j_decompress_ptr;
                            minc0 : int; minc1 : int; minc2 : int;
                            numcolors : int;
                            var colorlist : array of JSAMPLE;
                            var bestcolor : array of JSAMPLE);
{ 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. }
const
  { Nominal steps between cell centers ("x" in Thomas article) }
  STEP_C0 = ((1 shl C0_SHIFT) * C0_SCALE);
  STEP_C1 = ((1 shl C1_SHIFT) * C1_SCALE);
  STEP_C2 = ((1 shl C2_SHIFT) * C2_SCALE);
var
  ic0, ic1, ic2 : int;
  i, icolor : int;
  {register} bptr : INT32PTR;     { pointer into bestdist[] array }
  cptr : JSAMPLE_PTR;              { pointer into bestcolor[] array }
  dist0, dist1 : INT32;         { initial distance values }
  {register} dist2 : INT32;	{ current distance in inner loop }
  xx0, xx1 : INT32;             { distance increments }
  {register} xx2 : INT32;
  inc0, inc1, inc2 : INT32;	{ initial values for increments }
  { This array holds the distance to the nearest-so-far color for each cell }
  bestdist : array[0..BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS-1] of INT32;
begin
  { Initialize best-distance for each cell of the update box }
  for i := BOX_C0_ELEMS*BOX_C1_ELEMS*BOX_C2_ELEMS-1 downto 0 do
    bestdist[i] := $7FFFFFFF;

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



  for i := 0 to pred(numcolors) do
  begin
    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;
    Inc(dist0, inc1*inc1);
    inc2 := (minc2 - GETJSAMPLE(cinfo^.colormap^[2]^[icolor])) * C2_SCALE;
    Inc(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[0];
    cptr := @bestcolor[0];
    xx0 := inc0;
    for ic0 := BOX_C0_ELEMS-1 downto 0 do
    begin
      dist1 := dist0;
      xx1 := inc1;
      for ic1 := BOX_C1_ELEMS-1 downto 0 do
      begin
	dist2 := dist1;
	xx2 := inc2;
	for ic2 := BOX_C2_ELEMS-1 downto 0 do
        begin
	  if (dist2 < bptr^) then
          begin
	    bptr^ := dist2;
	    cptr^ := JSAMPLE (icolor);
	  end;
	  Inc(dist2, xx2);
	  Inc(xx2, 2 * STEP_C2 * STEP_C2);
	  Inc(bptr);
	  Inc(cptr);
	end;
	Inc(dist1, xx1);
	Inc(xx1, 2 * STEP_C1 * STEP_C1);
      end;
      Inc(dist0, xx0);
      Inc(xx0, 2 * STEP_C0 * STEP_C0);
    end;
  end;
end;


{LOCAL}
procedure fill_inverse_cmap (cinfo : j_decompress_ptr;
                             c0 : int; c1 : int; c2 : int);
{ Fill the inverse-colormap entries in the update box that contains }
{ histogram cell c0/c1/c2.  (Only that one cell MUST be filled, but }
{ we can fill as many others as we wish.) }
var
  cquantize : my_cquantize_ptr;
  histogram : hist3d;
  minc0, minc1, minc2 : int;    { lower left corner of update box }
  ic0, ic1, ic2 : int;
  {register} cptr : JSAMPLE_PTR;	{ pointer into bestcolor[] array }
  {register} cachep : histptr;	{ pointer into main cache array }
  { This array lists the candidate colormap indexes. }
  colorlist : array[0..MAXNUMCOLORS-1] of JSAMPLE;
  numcolors : int;		{ number of candidate colors }
  { This array holds the actually closest colormap index for each cell. }
  bestcolor : array[0..BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS-1] of JSAMPLE;
begin
  cquantize := my_cquantize_ptr (cinfo^.cquantize);
  histogram := cquantize^.histogram;

  { Convert cell coordinates to update box ID }
  c0 := c0 shr BOX_C0_LOG;
  c1 := c1 shr BOX_C1_LOG;
  c2 := c2 shr 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 shl BOX_C0_SHIFT) + ((1 shl C0_SHIFT) shr 1);
  minc1 := (c1 shl BOX_C1_SHIFT) + ((1 shl C1_SHIFT) shr 1);
  minc2 := (c2 shl BOX_C2_SHIFT) + ((1 shl C2_SHIFT) shr 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. }
  find_best_colors(cinfo, minc0, minc1, minc2, numcolors, colorlist,
		   bestcolor);

  { Save the best color numbers (plus 1) in the main cache array }
  c0 := c0 shl BOX_C0_LOG;		{ convert ID back to base cell indexes }
  c1 := c1 shl BOX_C1_LOG;
  c2 := c2 shl BOX_C2_LOG;
  cptr := @(bestcolor[0]);
  for ic0 := 0 to pred(BOX_C0_ELEMS) do
    for ic1 := 0 to pred(BOX_C1_ELEMS) do
    begin
      cachep := @(histogram^[c0+ic0]^[c1+ic1][c2]);
      for ic2 := 0 to pred(BOX_C2_ELEMS) do
      begin
	cachep^ := histcell (GETJSAMPLE(cptr^) + 1);
        Inc(cachep);
        Inc(cptr);
      end;
    end;
end;


{ Map some rows of pixels to the output colormapped representation. }

{METHODDEF}
procedure pass2_no_dither (cinfo : j_decompress_ptr;
		           input_buf : JSAMPARRAY;
                           output_buf : JSAMPARRAY;
                           num_rows : int); far;
{ This version performs no dithering }
var
  cquantize : my_cquantize_ptr;
  histogram : hist3d;
  {register} inptr : RGBptr;
             outptr : JSAMPLE_PTR;
  {register} cachep : histptr;
  {register} c0, c1, c2 : int;
  row : int;
  col : JDIMENSION;
  width : JDIMENSION;
begin
  cquantize := my_cquantize_ptr (cinfo^.cquantize);
  histogram := cquantize^.histogram;
  width := cinfo^.output_width;

  for row := 0 to pred(num_rows) do
  begin
    inptr := RGBptr(input_buf^[row]);
    outptr := JSAMPLE_PTR(output_buf^[row]);
    for col := pred(width) downto 0 do
    begin
      { get pixel value and index into the cache }
      c0 := GETJSAMPLE(inptr^.r) shr C0_SHIFT;
      c1 := GETJSAMPLE(inptr^.g) shr C1_SHIFT;
      c2 := GETJSAMPLE(inptr^.b) shr C2_SHIFT;
      Inc(inptr);
      cachep := @(histogram^[c0]^[c1][c2]);
      { If we have not seen this color before, find nearest colormap entry }
      { and update the cache }
      if (cachep^ = 0) then
	fill_inverse_cmap(cinfo, c0,c1,c2);
      { Now emit the colormap index for this cell }
      outptr^ := JSAMPLE (cachep^ - 1);
      Inc(outptr);
    end;
  end;
end;


{METHODDEF}
procedure pass2_fs_dither (cinfo : j_decompress_ptr;
		           input_buf : JSAMPARRAY;
                           output_buf : JSAMPARRAY;
                           num_rows : int); far;
{ This version performs Floyd-Steinberg dithering }
var
  cquantize : my_cquantize_ptr;
  histogram : hist3d;
  {register} cur : LOCRGB_FSERROR;	{ current error or pixel value }
  belowerr : LOCRGB_FSERROR; { error for pixel below cur }
  bpreverr : LOCRGB_FSERROR; { error for below/prev col }
  prev_errorptr,
  {register} errorptr : RGB_FSERROR_PTR;	{ => fserrors[] at column before current }
  inptr : RGBptr;		{ => current input pixel }
  outptr : JSAMPLE_PTR;		{ => current output pixel }
  cachep : histptr;
  dir : int;			{ +1 or -1 depending on direction }
  row : int;
  col : JDIMENSION;
  width : JDIMENSION;
  range_limit : range_limit_table_ptr;
  error_limit : error_limit_ptr;
  colormap0 : JSAMPROW;
  colormap1 : JSAMPROW;
  colormap2 : JSAMPROW;
  {register} pixcode : int;
  {register} bnexterr, delta : LOCFSERROR;
begin
  cquantize := my_cquantize_ptr (cinfo^.cquantize);
  histogram := cquantize^.histogram;
  width := cinfo^.output_width;