jquant1.c revision bd543f030e7e435c2c6a6a7d52ad927ae97cd927
1/* 2 * jquant1.c 3 * 4 * Copyright (C) 1991, Thomas G. Lane. 5 * This file is part of the Independent JPEG Group's software. 6 * For conditions of distribution and use, see the accompanying README file. 7 * 8 * This file contains 1-pass color quantization (color mapping) routines. 9 * These routines are invoked via the methods color_quantize 10 * and color_quant_init/term. 11 */ 12 13#include "jinclude.h" 14 15#ifdef QUANT_1PASS_SUPPORTED 16 17 18/* 19 * This implementation is a fairly dumb, quick-and-dirty quantizer; 20 * it's here mostly so that we can start working on colormapped output formats. 21 * 22 * We quantize to a color map that is selected in advance of seeing the image; 23 * the map depends only on the requested number of colors (at least 8). 24 * The map consists of all combinations of Ncolors[j] color values for each 25 * component j; we choose Ncolors[] based on the requested # of colors. 26 * We always use 0 and MAXJSAMPLE in each color (hence the minimum 8 colors). 27 * Any additional color values are equally spaced between these limits. 28 * 29 * The result almost always needs dithering to look decent. 30 */ 31 32#define MAX_COMPONENTS 4 /* max components I can handle */ 33 34static int total_colors; /* Number of distinct output colors */ 35static int Ncolors[MAX_COMPONENTS]; /* # of values alloced to each component */ 36/* total_colors is the product of the Ncolors[] values */ 37 38static JSAMPARRAY colormap; /* The actual color map */ 39/* colormap[i][j] = value of i'th color component for output pixel value j */ 40 41static JSAMPARRAY colorindex; /* Precomputed mapping for speed */ 42/* colorindex[i][j] = index of color closest to pixel value j in component i, 43 * premultiplied so that the correct mapped value for a pixel (r,g,b) is: 44 * colorindex[0][r] + colorindex[1][g] + colorindex[2][b] 45 */ 46 47 48/* Declarations for Floyd-Steinberg dithering. 49 * Errors are accumulated into the arrays evenrowerrs[] and oddrowerrs[], 50 * each of which have #colors * (#columns + 2) entries (so that first/last 51 * pixels need not be special cases). These have resolutions of 1/16th of 52 * a pixel count. The error at a given pixel is propagated to its unprocessed 53 * neighbors using the standard F-S fractions, 54 * ... (here) 7/16 55 * 3/16 5/16 1/16 56 * We work left-to-right on even rows, right-to-left on odd rows. 57 * 58 * Note: on a wide image, we might not have enough room in a PC's near data 59 * segment to hold the error arrays; so they are allocated with alloc_medium. 60 */ 61 62#ifdef EIGHT_BIT_SAMPLES 63typedef INT16 FSERROR; /* 16 bits should be enough */ 64#else 65typedef INT32 FSERROR; /* may need more than 16 bits? */ 66#endif 67 68typedef FSERROR FAR *FSERRPTR; /* pointer to error array (in FAR storage!) */ 69 70static FSERRPTR evenrowerrs, oddrowerrs; /* current-row and next-row errors */ 71static boolean on_odd_row; /* flag to remember which row we are on */ 72 73 74/* 75 * Initialize for one-pass color quantization. 76 */ 77 78METHODDEF void 79color_quant_init (decompress_info_ptr cinfo) 80{ 81 int max_colors = cinfo->desired_number_of_colors; 82 int i,j,k, ntc, nci, blksize, blkdist, ptr, val; 83 84 if (cinfo->color_out_comps > MAX_COMPONENTS) 85 ERREXIT1(cinfo->emethods, "Cannot quantize more than %d color components", 86 MAX_COMPONENTS); 87 if (max_colors > (MAXJSAMPLE+1)) 88 ERREXIT1(cinfo->emethods, "Cannot request more than %d quantized colors", 89 MAXJSAMPLE+1); 90 91 /* Initialize to 2 color values for each component */ 92 total_colors = 1; 93 for (i = 0; i < cinfo->color_out_comps; i++) { 94 Ncolors[i] = 2; 95 total_colors *= 2; 96 } 97 if (total_colors > max_colors) 98 ERREXIT1(cinfo->emethods, "Cannot quantize to fewer than %d colors", 99 total_colors); 100 101 /* Increase the number of color values until requested limit is reached. */ 102 /* Note that for standard RGB color space, we will have at least as many */ 103 /* red values as green, and at least as many green values as blue. */ 104 i = 0; /* component index to increase next */ 105 /* test calculates ntc = new total_colors if Ncolors[i] is incremented */ 106 while ((ntc = (total_colors / Ncolors[i]) * (Ncolors[i]+1)) <= max_colors) { 107 Ncolors[i]++; /* OK, apply the increment */ 108 total_colors = ntc; 109 i++; /* advance to next component */ 110 if (i >= cinfo->color_out_comps) i = 0; 111 } 112 113 /* Report selected color counts */ 114 if (cinfo->color_out_comps == 3) 115 TRACEMS4(cinfo->emethods, 1, "Quantizing to %d = %d*%d*%d colors", 116 total_colors, Ncolors[0], Ncolors[1], Ncolors[2]); 117 else 118 TRACEMS1(cinfo->emethods, 1, "Quantizing to %d colors", total_colors); 119 120 /* Allocate and fill in the colormap and color index. */ 121 /* The colors are ordered in the map in standard row-major order, */ 122 /* i.e. rightmost (highest-indexed) color changes most rapidly. */ 123 124 colormap = (*cinfo->emethods->alloc_small_sarray) 125 ((long) total_colors, (long) cinfo->color_out_comps); 126 colorindex = (*cinfo->emethods->alloc_small_sarray) 127 ((long) (MAXJSAMPLE+1), (long) cinfo->color_out_comps); 128 129 /* blksize is number of adjacent repeated entries for a component */ 130 /* blkdist is distance between groups of identical entries for a component */ 131 blkdist = total_colors; 132 133 for (i = 0; i < cinfo->color_out_comps; i++) { 134 /* fill in colormap entries for i'th color component */ 135 nci = Ncolors[i]; /* # of distinct values for this color */ 136 blksize = blkdist / nci; 137 for (j = 0; j < nci; j++) { 138 /* Compute j'th output value (out of nci) for component */ 139 val = (j * MAXJSAMPLE + (nci-1)/2) / (nci-1); 140 /* Fill in all colormap entries that have this value of this component */ 141 for (ptr = j * blksize; ptr < total_colors; ptr += blkdist) { 142 /* fill in blksize entries beginning at ptr */ 143 for (k = 0; k < blksize; k++) 144 colormap[i][ptr+k] = (JSAMPLE) val; 145 } 146 } 147 blkdist = blksize; /* blksize of this color is blkdist of next */ 148 149 /* fill in colorindex entries for i'th color component */ 150 for (j = 0; j <= MAXJSAMPLE; j++) { 151 /* compute index of color closest to pixel value j */ 152 val = (j * (nci-1) + CENTERJSAMPLE) / MAXJSAMPLE; 153 /* premultiply so that no multiplication needed in main processing */ 154 colorindex[i][j] = (JSAMPLE) (val * blksize); 155 } 156 } 157 158 /* Pass the colormap to the output module. Note that the output */ 159 /* module is allowed to save this pointer and use the map during */ 160 /* any put_pixel_rows call! */ 161 (*cinfo->methods->put_color_map) (cinfo, total_colors, colormap); 162 163 /* Allocate Floyd-Steinberg workspace if necessary */ 164 if (cinfo->use_dithering) { 165 size_t arraysize = (cinfo->image_width + 2L) * cinfo->color_out_comps 166 * SIZEOF(FSERROR); 167 168 evenrowerrs = (FSERRPTR) (*cinfo->emethods->alloc_medium) (arraysize); 169 oddrowerrs = (FSERRPTR) (*cinfo->emethods->alloc_medium) (arraysize); 170 /* we only need to zero the forward contribution for current row. */ 171 jzero_far((void FAR *) evenrowerrs, arraysize); 172 on_odd_row = FALSE; 173 } 174 175} 176 177 178/* 179 * Map some rows of pixels to the output colormapped representation. 180 */ 181 182METHODDEF void 183color_quantize (decompress_info_ptr cinfo, int num_rows, 184 JSAMPIMAGE input_data, JSAMPARRAY output_data) 185/* General case, no dithering */ 186{ 187 register int pixcode, ci; 188 register long col; 189 register int row; 190 register long widthm1 = cinfo->image_width - 1; 191 register int nc = cinfo->color_out_comps; 192 193 for (row = 0; row < num_rows; row++) { 194 for (col = widthm1; col >= 0; col--) { 195 pixcode = 0; 196 for (ci = 0; ci < nc; ci++) { 197 pixcode += GETJSAMPLE(colorindex[ci] 198 [GETJSAMPLE(input_data[ci][row][col])]); 199 } 200 output_data[row][col] = (JSAMPLE) pixcode; 201 } 202 } 203} 204 205 206METHODDEF void 207color_quantize3 (decompress_info_ptr cinfo, int num_rows, 208 JSAMPIMAGE input_data, JSAMPARRAY output_data) 209/* Fast path for color_out_comps==3, no dithering */ 210{ 211 register int pixcode; 212 register JSAMPROW ptr0, ptr1, ptr2, ptrout; 213 register long col; 214 register int row; 215 register long width = cinfo->image_width; 216 217 for (row = 0; row < num_rows; row++) { 218 ptr0 = input_data[0][row]; 219 ptr1 = input_data[1][row]; 220 ptr2 = input_data[2][row]; 221 ptrout = output_data[row]; 222 for (col = width; col > 0; col--) { 223 pixcode = GETJSAMPLE(colorindex[0][GETJSAMPLE(*ptr0++)]); 224 pixcode += GETJSAMPLE(colorindex[1][GETJSAMPLE(*ptr1++)]); 225 pixcode += GETJSAMPLE(colorindex[2][GETJSAMPLE(*ptr2++)]); 226 *ptrout++ = (JSAMPLE) pixcode; 227 } 228 } 229} 230 231 232METHODDEF void 233color_quantize_dither (decompress_info_ptr cinfo, int num_rows, 234 JSAMPIMAGE input_data, JSAMPARRAY output_data) 235/* General case, with Floyd-Steinberg dithering */ 236{ 237 register int pixcode, ci; 238 register FSERROR val; 239 register FSERRPTR thisrowerr, nextrowerr; 240 register long col; 241 register int row; 242 register long width = cinfo->image_width; 243 register int nc = cinfo->color_out_comps; 244 245 for (row = 0; row < num_rows; row++) { 246 if (on_odd_row) { 247 /* work right to left in this row */ 248 thisrowerr = oddrowerrs + width*nc; 249 nextrowerr = evenrowerrs + width*nc; 250 for (ci = 0; ci < nc; ci++) /* need only initialize this one entry */ 251 nextrowerr[ci] = 0; 252 for (col = width - 1; col >= 0; col--) { 253 /* select the output pixel value */ 254 pixcode = 0; 255 for (ci = 0; ci < nc; ci++) { 256 /* compute pixel value + accumulated error */ 257 val = (((FSERROR) GETJSAMPLE(input_data[ci][row][col])) << 4) 258 + thisrowerr[ci]; 259 if (val <= 0) val = 0; /* must watch for range overflow! */ 260 else { 261 val += 8; /* divide by 16 with proper rounding */ 262 val >>= 4; 263 if (val > MAXJSAMPLE) val = MAXJSAMPLE; 264 } 265 thisrowerr[ci] = val; /* save for error propagation */ 266 pixcode += GETJSAMPLE(colorindex[ci][val]); 267 } 268 output_data[row][col] = (JSAMPLE) pixcode; 269 /* propagate error to adjacent pixels */ 270 for (ci = 0; ci < nc; ci++) { 271 val = thisrowerr[ci] - (FSERROR) GETJSAMPLE(colormap[ci][pixcode]); 272 thisrowerr[ci-nc] += val * 7; 273 nextrowerr[ci+nc] += val * 3; 274 nextrowerr[ci ] += val * 5; 275 nextrowerr[ci-nc] = val; /* not +=, since not initialized yet */ 276 } 277 thisrowerr -= nc; /* advance error ptrs to next pixel entry */ 278 nextrowerr -= nc; 279 } 280 on_odd_row = FALSE; 281 } else { 282 /* work left to right in this row */ 283 thisrowerr = evenrowerrs + nc; 284 nextrowerr = oddrowerrs + nc; 285 for (ci = 0; ci < nc; ci++) /* need only initialize this one entry */ 286 nextrowerr[ci] = 0; 287 for (col = 0; col < width; col++) { 288 /* select the output pixel value */ 289 pixcode = 0; 290 for (ci = 0; ci < nc; ci++) { 291 /* compute pixel value + accumulated error */ 292 val = (((FSERROR) GETJSAMPLE(input_data[ci][row][col])) << 4) 293 + thisrowerr[ci]; 294 if (val <= 0) val = 0; /* must watch for range overflow! */ 295 else { 296 val += 8; /* divide by 16 with proper rounding */ 297 val >>= 4; 298 if (val > MAXJSAMPLE) val = MAXJSAMPLE; 299 } 300 thisrowerr[ci] = val; /* save for error propagation */ 301 pixcode += GETJSAMPLE(colorindex[ci][val]); 302 } 303 output_data[row][col] = (JSAMPLE) pixcode; 304 /* propagate error to adjacent pixels */ 305 for (ci = 0; ci < nc; ci++) { 306 val = thisrowerr[ci] - (FSERROR) GETJSAMPLE(colormap[ci][pixcode]); 307 thisrowerr[ci+nc] += val * 7; 308 nextrowerr[ci-nc] += val * 3; 309 nextrowerr[ci ] += val * 5; 310 nextrowerr[ci+nc] = val; /* not +=, since not initialized yet */ 311 } 312 thisrowerr += nc; /* advance error ptrs to next pixel entry */ 313 nextrowerr += nc; 314 } 315 on_odd_row = TRUE; 316 } 317 } 318} 319 320 321/* 322 * Finish up at the end of the file. 323 */ 324 325METHODDEF void 326color_quant_term (decompress_info_ptr cinfo) 327{ 328 /* We can't free the colormap until now, since output module may use it! */ 329 (*cinfo->emethods->free_small_sarray) 330 (colormap, (long) cinfo->color_out_comps); 331 (*cinfo->emethods->free_small_sarray) 332 (colorindex, (long) cinfo->color_out_comps); 333 if (cinfo->use_dithering) { 334 (*cinfo->emethods->free_medium) ((void FAR *) evenrowerrs); 335 (*cinfo->emethods->free_medium) ((void FAR *) oddrowerrs); 336 } 337} 338 339 340/* 341 * Prescan some rows of pixels. 342 * Not used in one-pass case. 343 */ 344 345METHODDEF void 346color_quant_prescan (decompress_info_ptr cinfo, int num_rows, 347 JSAMPIMAGE image_data) 348{ 349 ERREXIT(cinfo->emethods, "Should not get here!"); 350} 351 352 353/* 354 * Do two-pass quantization. 355 * Not used in one-pass case. 356 */ 357 358METHODDEF void 359color_quant_doit (decompress_info_ptr cinfo, quantize_caller_ptr source_method) 360{ 361 ERREXIT(cinfo->emethods, "Should not get here!"); 362} 363 364 365/* 366 * The method selection routine for 1-pass color quantization. 367 */ 368 369GLOBAL void 370jsel1quantize (decompress_info_ptr cinfo) 371{ 372 if (! cinfo->two_pass_quantize) { 373 cinfo->methods->color_quant_init = color_quant_init; 374 if (cinfo->use_dithering) { 375 cinfo->methods->color_quantize = color_quantize_dither; 376 } else { 377 if (cinfo->color_out_comps == 3) 378 cinfo->methods->color_quantize = color_quantize3; 379 else 380 cinfo->methods->color_quantize = color_quantize; 381 } 382 cinfo->methods->color_quant_prescan = color_quant_prescan; 383 cinfo->methods->color_quant_doit = color_quant_doit; 384 cinfo->methods->color_quant_term = color_quant_term; 385 } 386} 387 388#endif /* QUANT_1PASS_SUPPORTED */ 389