This is jquant1.c in view mode; [Download] [Up]
/*
* jquant1.c
*
* Copyright (C) 1991, Thomas G. Lane.
* This file is part of the Independent JPEG Group's software.
* For conditions of distribution and use, see the accompanying README file.
*
* This file contains 1-pass color quantization (color mapping) routines.
* These routines are invoked via the methods color_quantize
* and color_quant_init/term.
*/
#include "jinclude.h"
#ifdef QUANT_1PASS_SUPPORTED
/*
* This implementation is a fairly dumb, quick-and-dirty quantizer;
* it's here mostly so that we can start working on colormapped output formats.
*
* We quantize to a color map that is selected in advance of seeing the image;
* the map depends only on the requested number of colors (at least 8).
* The map consists of all combinations of Ncolors[j] color values for each
* component j; we choose Ncolors[] based on the requested # of colors.
* We always use 0 and MAXJSAMPLE in each color (hence the minimum 8 colors).
* Any additional color values are equally spaced between these limits.
*
* The result almost always needs dithering to look decent.
*/
#define MAX_COMPONENTS 4 /* max components I can handle */
static int total_colors; /* Number of distinct output colors */
static int Ncolors[MAX_COMPONENTS]; /* # of values alloced to each component */
/* total_colors is the product of the Ncolors[] values */
static JSAMPARRAY colormap; /* The actual color map */
/* colormap[i][j] = value of i'th color component for output pixel value j */
static JSAMPARRAY colorindex; /* Precomputed mapping for speed */
/* colorindex[i][j] = index of color closest to pixel value j in component i,
* premultiplied so that the correct mapped value for a pixel (r,g,b) is:
* colorindex[0][r] + colorindex[1][g] + colorindex[2][b]
*/
/* Declarations for Floyd-Steinberg dithering.
* Errors are accumulated into the arrays evenrowerrs[] and oddrowerrs[],
* each of which have #colors * (#columns + 2) entries (so that first/last
* pixels need not be special cases). These have resolutions of 1/16th of
* a pixel count. The error at a given pixel is propagated to its unprocessed
* neighbors using the standard F-S fractions,
* ... (here) 7/16
* 3/16 5/16 1/16
* We work left-to-right on even rows, right-to-left on odd rows.
*
* Note: on a wide image, we might not have enough room in a PC's near data
* segment to hold the error arrays; so they are allocated with alloc_medium.
*/
#ifdef EIGHT_BIT_SAMPLES
typedef short FSERROR; /* 16 bits should be enough */
#else
typedef INT32 FSERROR; /* may need more than 16 bits? */
#endif
typedef FSERROR FAR *FSERRPTR; /* pointer to error array (in FAR storage!) */
static FSERRPTR evenrowerrs, oddrowerrs; /* current-row and next-row errors */
static boolean on_odd_row; /* flag to remember which row we are on */
/*
* Initialize for one-pass color quantization.
*/
METHODDEF void
color_quant_init (decompress_info_ptr cinfo)
{
int max_colors = cinfo->desired_number_of_colors;
int i,j,k, ntc, nci, blksize, blkdist, ptr, val;
if (cinfo->color_out_comps > MAX_COMPONENTS)
ERREXIT1(cinfo->emethods, "Cannot quantize more than %d color components",
MAX_COMPONENTS);
if (max_colors > (MAXJSAMPLE+1))
ERREXIT1(cinfo->emethods, "Cannot request more than %d quantized colors",
MAXJSAMPLE+1);
/* Initialize to 2 color values for each component */
total_colors = 1;
for (i = 0; i < cinfo->color_out_comps; i++) {
Ncolors[i] = 2;
total_colors *= 2;
}
if (total_colors > max_colors)
ERREXIT1(cinfo->emethods, "Cannot quantize to fewer than %d colors",
total_colors);
/* Increase the number of color values until requested limit is reached. */
/* Note that for standard RGB color space, we will have at least as many */
/* red values as green, and at least as many green values as blue. */
i = 0; /* component index to increase next */
/* test calculates ntc = new total_colors if Ncolors[i] is incremented */
while ((ntc = (total_colors / Ncolors[i]) * (Ncolors[i]+1)) <= max_colors) {
Ncolors[i]++; /* OK, apply the increment */
total_colors = ntc;
i++; /* advance to next component */
if (i >= cinfo->color_out_comps) i = 0;
}
/* Report selected color counts */
if (cinfo->color_out_comps == 3)
TRACEMS4(cinfo->emethods, 1, "Quantizing to %d = %d*%d*%d colors",
total_colors, Ncolors[0], Ncolors[1], Ncolors[2]);
else
TRACEMS1(cinfo->emethods, 1, "Quantizing to %d colors", total_colors);
/* Allocate and fill in the colormap and color index. */
/* The colors are ordered in the map in standard row-major order, */
/* i.e. rightmost (highest-indexed) color changes most rapidly. */
colormap = (*cinfo->emethods->alloc_small_sarray)
((long) total_colors, (long) cinfo->color_out_comps);
colorindex = (*cinfo->emethods->alloc_small_sarray)
((long) (MAXJSAMPLE+1), (long) cinfo->color_out_comps);
/* blksize is number of adjacent repeated entries for a component */
/* blkdist is distance between groups of identical entries for a component */
blkdist = total_colors;
for (i = 0; i < cinfo->color_out_comps; i++) {
/* fill in colormap entries for i'th color component */
nci = Ncolors[i]; /* # of distinct values for this color */
blksize = blkdist / nci;
for (j = 0; j < nci; j++) {
val = (j * MAXJSAMPLE + (nci-1)/2) / (nci-1); /* j'th value of color */
for (ptr = j * blksize; ptr < total_colors; ptr += blkdist) {
/* fill in blksize entries beginning at ptr */
for (k = 0; k < blksize; k++)
colormap[i][ptr+k] = val;
}
}
blkdist = blksize; /* blksize of this color is blkdist of next */
/* fill in colorindex entries for i'th color component */
for (j = 0; j <= MAXJSAMPLE; j++) {
/* compute index of color closest to pixel value j */
val = (j * (nci-1) + CENTERJSAMPLE) / MAXJSAMPLE;
/* premultiply so that no multiplication needed in main processing */
val *= blksize;
colorindex[i][j] = val;
}
}
/* Pass the colormap to the output module. Note that the output */
/* module is allowed to save this pointer and use the map during */
/* any put_pixel_rows call! */
(*cinfo->methods->put_color_map) (cinfo, total_colors, colormap);
/* Allocate Floyd-Steinberg workspace if necessary */
if (cinfo->use_dithering) {
size_t arraysize = (cinfo->image_width + 2L) * cinfo->color_out_comps
* SIZEOF(FSERROR);
evenrowerrs = (FSERRPTR) (*cinfo->emethods->alloc_medium) (arraysize);
oddrowerrs = (FSERRPTR) (*cinfo->emethods->alloc_medium) (arraysize);
/* we only need to zero the forward contribution for current row. */
jzero_far((void FAR *) evenrowerrs, arraysize);
on_odd_row = FALSE;
}
}
/*
* Map some rows of pixels to the output colormapped representation.
*/
METHODDEF void
color_quantize (decompress_info_ptr cinfo, int num_rows,
JSAMPIMAGE input_data, JSAMPARRAY output_data)
/* General case, no dithering */
{
register int pixcode, ci;
register long col;
register int row;
register long widthm1 = cinfo->image_width - 1;
register int nc = cinfo->color_out_comps;
for (row = 0; row < num_rows; row++) {
for (col = widthm1; col >= 0; col--) {
pixcode = 0;
for (ci = 0; ci < nc; ci++) {
pixcode += GETJSAMPLE(colorindex[ci]
[GETJSAMPLE(input_data[ci][row][col])]);
}
output_data[row][col] = pixcode;
}
}
}
METHODDEF void
color_quantize3 (decompress_info_ptr cinfo, int num_rows,
JSAMPIMAGE input_data, JSAMPARRAY output_data)
/* Fast path for color_out_comps==3, no dithering */
{
register int pixcode;
register JSAMPROW ptr0, ptr1, ptr2, ptrout;
register long col;
register int row;
register long width = cinfo->image_width;
for (row = 0; row < num_rows; row++) {
ptr0 = input_data[0][row];
ptr1 = input_data[1][row];
ptr2 = input_data[2][row];
ptrout = output_data[row];
for (col = width; col > 0; col--) {
pixcode = GETJSAMPLE(colorindex[0][GETJSAMPLE(*ptr0++)]);
pixcode += GETJSAMPLE(colorindex[1][GETJSAMPLE(*ptr1++)]);
pixcode += GETJSAMPLE(colorindex[2][GETJSAMPLE(*ptr2++)]);
*ptrout++ = pixcode;
}
}
}
METHODDEF void
color_quantize_dither (decompress_info_ptr cinfo, int num_rows,
JSAMPIMAGE input_data, JSAMPARRAY output_data)
/* General case, with Floyd-Steinberg dithering */
{
register int pixcode, ci;
register FSERROR val;
register FSERRPTR thisrowerr, nextrowerr;
register long col;
register int row;
register long width = cinfo->image_width;
register int nc = cinfo->color_out_comps;
for (row = 0; row < num_rows; row++) {
if (on_odd_row) {
/* work right to left in this row */
thisrowerr = oddrowerrs + width*nc;
nextrowerr = evenrowerrs + width*nc;
for (ci = 0; ci < nc; ci++) /* need only initialize this one entry */
nextrowerr[ci] = 0;
for (col = width - 1; col >= 0; col--) {
/* select the output pixel value */
pixcode = 0;
for (ci = 0; ci < nc; ci++) {
/* compute pixel value + accumulated error */
val = (((FSERROR) GETJSAMPLE(input_data[ci][row][col])) << 4)
+ thisrowerr[ci];
if (val < 0) val = 0; /* must watch for range overflow! */
else {
val += 8; /* divide by 16 with proper rounding */
val >>= 4;
if (val > MAXJSAMPLE) val = MAXJSAMPLE;
}
thisrowerr[ci] = val; /* save for error propagation */
pixcode += GETJSAMPLE(colorindex[ci][val]);
}
output_data[row][col] = pixcode;
/* propagate error to adjacent pixels */
for (ci = 0; ci < nc; ci++) {
val = thisrowerr[ci] - GETJSAMPLE(colormap[ci][pixcode]);
thisrowerr[ci-nc] += val * 7;
nextrowerr[ci+nc] += val * 3;
nextrowerr[ci ] += val * 5;
nextrowerr[ci-nc] = val; /* not +=, since not initialized yet */
}
thisrowerr -= nc; /* advance error ptrs to next pixel entry */
nextrowerr -= nc;
}
on_odd_row = FALSE;
} else {
/* work left to right in this row */
thisrowerr = evenrowerrs + nc;
nextrowerr = oddrowerrs + nc;
for (ci = 0; ci < nc; ci++) /* need only initialize this one entry */
nextrowerr[ci] = 0;
for (col = 0; col < width; col++) {
/* select the output pixel value */
pixcode = 0;
for (ci = 0; ci < nc; ci++) {
/* compute pixel value + accumulated error */
val = (((FSERROR) GETJSAMPLE(input_data[ci][row][col])) << 4)
+ thisrowerr[ci];
if (val < 0) val = 0; /* must watch for range overflow! */
else {
val += 8; /* divide by 16 with proper rounding */
val >>= 4;
if (val > MAXJSAMPLE) val = MAXJSAMPLE;
}
thisrowerr[ci] = val; /* save for error propagation */
pixcode += GETJSAMPLE(colorindex[ci][val]);
}
output_data[row][col] = pixcode;
/* propagate error to adjacent pixels */
for (ci = 0; ci < nc; ci++) {
val = thisrowerr[ci] - GETJSAMPLE(colormap[ci][pixcode]);
thisrowerr[ci+nc] += val * 7;
nextrowerr[ci-nc] += val * 3;
nextrowerr[ci ] += val * 5;
nextrowerr[ci+nc] = val; /* not +=, since not initialized yet */
}
thisrowerr += nc; /* advance error ptrs to next pixel entry */
nextrowerr += nc;
}
on_odd_row = TRUE;
}
}
}
/*
* Finish up at the end of the file.
*/
METHODDEF void
color_quant_term (decompress_info_ptr cinfo)
{
/* We can't free the colormap until now, since output module may use it! */
(*cinfo->emethods->free_small_sarray)
(colormap, (long) cinfo->color_out_comps);
(*cinfo->emethods->free_small_sarray)
(colorindex, (long) cinfo->color_out_comps);
if (cinfo->use_dithering) {
(*cinfo->emethods->free_medium) ((void FAR *) evenrowerrs);
(*cinfo->emethods->free_medium) ((void FAR *) oddrowerrs);
}
}
/*
* Prescan some rows of pixels.
* Not used in one-pass case.
*/
METHODDEF void
color_quant_prescan (decompress_info_ptr cinfo, int num_rows,
JSAMPIMAGE image_data)
{
ERREXIT(cinfo->emethods, "Should not get here!");
}
/*
* Do two-pass quantization.
* Not used in one-pass case.
*/
METHODDEF void
color_quant_doit (decompress_info_ptr cinfo, quantize_caller_ptr source_method)
{
ERREXIT(cinfo->emethods, "Should not get here!");
}
/*
* The method selection routine for 1-pass color quantization.
*/
GLOBAL void
jsel1quantize (decompress_info_ptr cinfo)
{
if (! cinfo->two_pass_quantize) {
cinfo->methods->color_quant_init = color_quant_init;
if (cinfo->use_dithering) {
cinfo->methods->color_quantize = color_quantize_dither;
} else {
if (cinfo->color_out_comps == 3)
cinfo->methods->color_quantize = color_quantize3;
else
cinfo->methods->color_quantize = color_quantize;
}
cinfo->methods->color_quant_prescan = color_quant_prescan;
cinfo->methods->color_quant_doit = color_quant_doit;
cinfo->methods->color_quant_term = color_quant_term;
}
}
#endif /* QUANT_1PASS_SUPPORTED */
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.