jquant1.cpp (35108B)
1 /* 2 * jquant1.c 3 * 4 * Copyright (C) 1991-1995, 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 provide mapping to a fixed color map using equally spaced 10 * color values. Optional Floyd-Steinberg or ordered dithering is available. 11 */ 12 13 #define JPEG_INTERNALS 14 #include "jinclude.h" 15 #include "jpeglib.h" 16 17 #ifdef QUANT_1PASS_SUPPORTED 18 19 20 /* 21 * The main purpose of 1-pass quantization is to provide a fast, if not very 22 * high quality, colormapped output capability. A 2-pass quantizer usually 23 * gives better visual quality; however, for quantized grayscale output this 24 * quantizer is perfectly adequate. Dithering is highly recommended with this 25 * quantizer, though you can turn it off if you really want to. 26 * 27 * In 1-pass quantization the colormap must be chosen in advance of seeing the 28 * image. We use a map consisting of all combinations of Ncolors[i] color 29 * values for the i'th component. The Ncolors[] values are chosen so that 30 * their product, the total number of colors, is no more than that requested. 31 * (In most cases, the product will be somewhat less.) 32 * 33 * Since the colormap is orthogonal, the representative value for each color 34 * component can be determined without considering the other components; 35 * then these indexes can be combined into a colormap index by a standard 36 * N-dimensional-array-subscript calculation. Most of the arithmetic involved 37 * can be precalculated and stored in the lookup table colorindex[]. 38 * colorindex[i][j] maps pixel value j in component i to the nearest 39 * representative value (grid plane) for that component; this index is 40 * multiplied by the array stride for component i, so that the 41 * index of the colormap entry closest to a given pixel value is just 42 * sum( colorindex[component-number][pixel-component-value] ) 43 * Aside from being fast, this scheme allows for variable spacing between 44 * representative values with no additional lookup cost. 45 * 46 * If gamma correction has been applied in color conversion, it might be wise 47 * to adjust the color grid spacing so that the representative colors are 48 * equidistant in linear space. At this writing, gamma correction is not 49 * implemented by jdcolor, so nothing is done here. 50 */ 51 52 53 /* Declarations for ordered dithering. 54 * 55 * We use a standard 16x16 ordered dither array. The basic concept of ordered 56 * dithering is described in many references, for instance Dale Schumacher's 57 * chapter II.2 of Graphics Gems II (James Arvo, ed. Academic Press, 1991). 58 * In place of Schumacher's comparisons against a "threshold" value, we add a 59 * "dither" value to the input pixel and then round the result to the nearest 60 * output value. The dither value is equivalent to (0.5 - threshold) times 61 * the distance between output values. For ordered dithering, we assume that 62 * the output colors are equally spaced; if not, results will probably be 63 * worse, since the dither may be too much or too little at a given point. 64 * 65 * The normal calculation would be to form pixel value + dither, range-limit 66 * this to 0..MAXJSAMPLE, and then index into the colorindex table as usual. 67 * We can skip the separate range-limiting step by extending the colorindex 68 * table in both directions. 69 */ 70 71 #define ODITHER_SIZE 16 /* dimension of dither matrix */ 72 /* NB: if ODITHER_SIZE is not a power of 2, ODITHER_MASK uses will break */ 73 #define ODITHER_CELLS ( ODITHER_SIZE * ODITHER_SIZE ) /* # cells in matrix */ 74 #define ODITHER_MASK ( ODITHER_SIZE - 1 ) /* mask for wrapping around counters */ 75 76 typedef int ODITHER_MATRIX[ODITHER_SIZE][ODITHER_SIZE]; 77 typedef int ( *ODITHER_MATRIX_PTR )[ODITHER_SIZE]; 78 79 static const UINT8 base_dither_matrix[ODITHER_SIZE][ODITHER_SIZE] = { 80 /* Bayer's order-4 dither array. Generated by the code given in 81 * Stephen Hawley's article "Ordered Dithering" in Graphics Gems I. 82 * The values in this array must range from 0 to ODITHER_CELLS-1. 83 */ 84 { 0, 192, 48, 240, 12, 204, 60, 252, 3, 195, 51, 243, 15, 207, 63, 255 }, 85 { 128, 64, 176, 112, 140, 76, 188, 124, 131, 67, 179, 115, 143, 79, 191, 127 }, 86 { 32, 224, 16, 208, 44, 236, 28, 220, 35, 227, 19, 211, 47, 239, 31, 223 }, 87 { 160, 96, 144, 80, 172, 108, 156, 92, 163, 99, 147, 83, 175, 111, 159, 95 }, 88 { 8, 200, 56, 248, 4, 196, 52, 244, 11, 203, 59, 251, 7, 199, 55, 247 }, 89 { 136, 72, 184, 120, 132, 68, 180, 116, 139, 75, 187, 123, 135, 71, 183, 119 }, 90 { 40, 232, 24, 216, 36, 228, 20, 212, 43, 235, 27, 219, 39, 231, 23, 215 }, 91 { 168, 104, 152, 88, 164, 100, 148, 84, 171, 107, 155, 91, 167, 103, 151, 87 }, 92 { 2, 194, 50, 242, 14, 206, 62, 254, 1, 193, 49, 241, 13, 205, 61, 253 }, 93 { 130, 66, 178, 114, 142, 78, 190, 126, 129, 65, 177, 113, 141, 77, 189, 125 }, 94 { 34, 226, 18, 210, 46, 238, 30, 222, 33, 225, 17, 209, 45, 237, 29, 221 }, 95 { 162, 98, 146, 82, 174, 110, 158, 94, 161, 97, 145, 81, 173, 109, 157, 93 }, 96 { 10, 202, 58, 250, 6, 198, 54, 246, 9, 201, 57, 249, 5, 197, 53, 245 }, 97 { 138, 74, 186, 122, 134, 70, 182, 118, 137, 73, 185, 121, 133, 69, 181, 117 }, 98 { 42, 234, 26, 218, 38, 230, 22, 214, 41, 233, 25, 217, 37, 229, 21, 213 }, 99 { 170, 106, 154, 90, 166, 102, 150, 86, 169, 105, 153, 89, 165, 101, 149, 85 } 100 }; 101 102 103 /* Declarations for Floyd-Steinberg dithering. 104 * 105 * Errors are accumulated into the array fserrors[], at a resolution of 106 * 1/16th of a pixel count. The error at a given pixel is propagated 107 * to its not-yet-processed neighbors using the standard F-S fractions, 108 * ... (here) 7/16 109 * 3/16 5/16 1/16 110 * We work left-to-right on even rows, right-to-left on odd rows. 111 * 112 * We can get away with a single array (holding one row's worth of errors) 113 * by using it to store the current row's errors at pixel columns not yet 114 * processed, but the next row's errors at columns already processed. We 115 * need only a few extra variables to hold the errors immediately around the 116 * current column. (If we are lucky, those variables are in registers, but 117 * even if not, they're probably cheaper to access than array elements are.) 118 * 119 * The fserrors[] array is indexed [component#][position]. 120 * We provide (#columns + 2) entries per component; the extra entry at each 121 * end saves us from special-casing the first and last pixels. 122 * 123 * Note: on a wide image, we might not have enough room in a PC's near data 124 * segment to hold the error array; so it is allocated with alloc_large. 125 */ 126 127 #if BITS_IN_JSAMPLE == 8 128 typedef INT16 FSERROR; /* 16 bits should be enough */ 129 typedef int LOCFSERROR; /* use 'int' for calculation temps */ 130 #else 131 typedef INT32 FSERROR; /* may need more than 16 bits */ 132 typedef INT32 LOCFSERROR; /* be sure calculation temps are big enough */ 133 #endif 134 135 typedef FSERROR FAR * FSERRPTR; /* pointer to error array (in FAR storage!) */ 136 137 138 /* Private subobject */ 139 140 #define MAX_Q_COMPS 4 /* max components I can handle */ 141 142 typedef struct { 143 struct jpeg_color_quantizer pub;/* public fields */ 144 145 /* Initially allocated colormap is saved here */ 146 JSAMPARRAY sv_colormap; /* The color map as a 2-D pixel array */ 147 int sv_actual; /* number of entries in use */ 148 149 JSAMPARRAY colorindex; /* Precomputed mapping for speed */ 150 /* colorindex[i][j] = index of color closest to pixel value j in component i, 151 * premultiplied as described above. Since colormap indexes must fit into 152 * JSAMPLEs, the entries of this array will too. 153 */ 154 boolean is_padded; /* is the colorindex padded for odither? */ 155 156 int Ncolors[MAX_Q_COMPS];/* # of values alloced to each component */ 157 158 /* Variables for ordered dithering */ 159 int row_index; /* cur row's vertical index in dither matrix */ 160 ODITHER_MATRIX_PTR odither[MAX_Q_COMPS];/* one dither array per component */ 161 162 /* Variables for Floyd-Steinberg dithering */ 163 FSERRPTR fserrors[MAX_Q_COMPS];/* accumulated errors */ 164 boolean on_odd_row; /* flag to remember which row we are on */ 165 } my_cquantizer; 166 167 typedef my_cquantizer * my_cquantize_ptr; 168 169 170 /* 171 * Policy-making subroutines for create_colormap and create_colorindex. 172 * These routines determine the colormap to be used. The rest of the module 173 * only assumes that the colormap is orthogonal. 174 * 175 * * select_ncolors decides how to divvy up the available colors 176 * among the components. 177 * * output_value defines the set of representative values for a component. 178 * * largest_input_value defines the mapping from input values to 179 * representative values for a component. 180 * Note that the latter two routines may impose different policies for 181 * different components, though this is not currently done. 182 */ 183 184 185 LOCAL int 186 select_ncolors( j_decompress_ptr cinfo, int Ncolors[] ) { 187 /* Determine allocation of desired colors to components, */ 188 /* and fill in Ncolors[] array to indicate choice. */ 189 /* Return value is total number of colors (product of Ncolors[] values). */ 190 int nc = cinfo->out_color_components;/* number of color components */ 191 int max_colors = cinfo->desired_number_of_colors; 192 int total_colors, iroot, i, j; 193 boolean changed; 194 long temp; 195 static const int RGB_order[3] = { RGB_GREEN, RGB_RED, RGB_BLUE }; 196 197 /* We can allocate at least the nc'th root of max_colors per component. */ 198 /* Compute floor(nc'th root of max_colors). */ 199 iroot = 1; 200 do { 201 iroot++; 202 temp = iroot; /* set temp = iroot ** nc */ 203 for ( i = 1; i < nc; i++ ) { 204 temp *= iroot; 205 } 206 } while ( temp <= (long) max_colors );/* repeat till iroot exceeds root */ 207 iroot--; /* now iroot = floor(root) */ 208 209 /* Must have at least 2 color values per component */ 210 if ( iroot < 2 ) { 211 ERREXIT1( cinfo, JERR_QUANT_FEW_COLORS, (int) temp ); 212 } 213 214 /* Initialize to iroot color values for each component */ 215 total_colors = 1; 216 for ( i = 0; i < nc; i++ ) { 217 Ncolors[i] = iroot; 218 total_colors *= iroot; 219 } 220 /* We may be able to increment the count for one or more components without 221 * exceeding max_colors, though we know not all can be incremented. 222 * Sometimes, the first component can be incremented more than once! 223 * (Example: for 16 colors, we start at 2*2*2, go to 3*2*2, then 4*2*2.) 224 * In RGB colorspace, try to increment G first, then R, then B. 225 */ 226 do { 227 changed = FALSE; 228 for ( i = 0; i < nc; i++ ) { 229 j = ( cinfo->out_color_space == JCS_RGB ? RGB_order[i] : i ); 230 /* calculate new total_colors if Ncolors[j] is incremented */ 231 temp = total_colors / Ncolors[j]; 232 temp *= Ncolors[j] + 1;/* done in long arith to avoid oflo */ 233 if ( temp > (long) max_colors ) { 234 break; 235 } /* won't fit, done with this pass */ 236 Ncolors[j]++; /* OK, apply the increment */ 237 total_colors = (int) temp; 238 changed = TRUE; 239 } 240 } while ( changed ); 241 242 return total_colors; 243 } 244 245 246 LOCAL int 247 output_value( j_decompress_ptr cinfo, int ci, int j, int maxj ) { 248 /* Return j'th output value, where j will range from 0 to maxj */ 249 /* The output values must fall in 0..MAXJSAMPLE in increasing order */ 250 /* We always provide values 0 and MAXJSAMPLE for each component; 251 * any additional values are equally spaced between these limits. 252 * (Forcing the upper and lower values to the limits ensures that 253 * dithering can't produce a color outside the selected gamut.) 254 */ 255 return (int) ( ( (INT32) j * MAXJSAMPLE + maxj / 2 ) / maxj ); 256 } 257 258 259 LOCAL int 260 largest_input_value( j_decompress_ptr cinfo, int ci, int j, int maxj ) { 261 /* Return largest input value that should map to j'th output value */ 262 /* Must have largest(j=0) >= 0, and largest(j=maxj) >= MAXJSAMPLE */ 263 /* Breakpoints are halfway between values returned by output_value */ 264 return (int) ( ( (INT32) ( 2 * j + 1 ) * MAXJSAMPLE + maxj ) / ( 2 * maxj ) ); 265 } 266 267 268 /* 269 * Create the colormap. 270 */ 271 272 LOCAL void 273 create_colormap( j_decompress_ptr cinfo ) { 274 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 275 JSAMPARRAY colormap; /* Created colormap */ 276 int total_colors; /* Number of distinct output colors */ 277 int i, j, k, nci, blksize, blkdist, ptr, val; 278 279 /* Select number of colors for each component */ 280 total_colors = select_ncolors( cinfo, cquantize->Ncolors ); 281 282 /* Report selected color counts */ 283 if ( cinfo->out_color_components == 3 ) { 284 TRACEMS4( cinfo, 1, JTRC_QUANT_3_NCOLORS, 285 total_colors, cquantize->Ncolors[0], 286 cquantize->Ncolors[1], cquantize->Ncolors[2] ); 287 } else { 288 TRACEMS1( cinfo, 1, JTRC_QUANT_NCOLORS, total_colors ); 289 } 290 291 /* Allocate and fill in the colormap. */ 292 /* The colors are ordered in the map in standard row-major order, */ 293 /* i.e. rightmost (highest-indexed) color changes most rapidly. */ 294 295 colormap = ( *cinfo->mem->alloc_sarray ) 296 ( (j_common_ptr) cinfo, JPOOL_IMAGE, 297 (JDIMENSION) total_colors, (JDIMENSION) cinfo->out_color_components ); 298 299 /* blksize is number of adjacent repeated entries for a component */ 300 /* blkdist is distance between groups of identical entries for a component */ 301 blkdist = total_colors; 302 303 for ( i = 0; i < cinfo->out_color_components; i++ ) { 304 /* fill in colormap entries for i'th color component */ 305 nci = cquantize->Ncolors[i];/* # of distinct values for this color */ 306 blksize = blkdist / nci; 307 for ( j = 0; j < nci; j++ ) { 308 /* Compute j'th output value (out of nci) for component */ 309 val = output_value( cinfo, i, j, nci - 1 ); 310 /* Fill in all colormap entries that have this value of this component */ 311 for ( ptr = j * blksize; ptr < total_colors; ptr += blkdist ) { 312 /* fill in blksize entries beginning at ptr */ 313 for ( k = 0; k < blksize; k++ ) { 314 colormap[i][ptr + k] = (JSAMPLE) val; 315 } 316 } 317 } 318 blkdist = blksize; /* blksize of this color is blkdist of next */ 319 } 320 321 /* Save the colormap in private storage, 322 * where it will survive color quantization mode changes. 323 */ 324 cquantize->sv_colormap = colormap; 325 cquantize->sv_actual = total_colors; 326 } 327 328 329 /* 330 * Create the color index table. 331 */ 332 333 LOCAL void 334 create_colorindex( j_decompress_ptr cinfo ) { 335 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 336 JSAMPROW indexptr; 337 int i, j, k, nci, blksize, val, pad; 338 339 /* For ordered dither, we pad the color index tables by MAXJSAMPLE in 340 * each direction (input index values can be -MAXJSAMPLE .. 2*MAXJSAMPLE). 341 * This is not necessary in the other dithering modes. However, we 342 * flag whether it was done in case user changes dithering mode. 343 */ 344 if ( cinfo->dither_mode == JDITHER_ORDERED ) { 345 pad = MAXJSAMPLE * 2; 346 cquantize->is_padded = TRUE; 347 } else { 348 pad = 0; 349 cquantize->is_padded = FALSE; 350 } 351 352 cquantize->colorindex = ( *cinfo->mem->alloc_sarray ) 353 ( (j_common_ptr) cinfo, JPOOL_IMAGE, 354 (JDIMENSION) ( MAXJSAMPLE + 1 + pad ), 355 (JDIMENSION) cinfo->out_color_components ); 356 357 /* blksize is number of adjacent repeated entries for a component */ 358 blksize = cquantize->sv_actual; 359 360 for ( i = 0; i < cinfo->out_color_components; i++ ) { 361 /* fill in colorindex entries for i'th color component */ 362 nci = cquantize->Ncolors[i];/* # of distinct values for this color */ 363 blksize = blksize / nci; 364 365 /* adjust colorindex pointers to provide padding at negative indexes. */ 366 if ( pad ) { 367 cquantize->colorindex[i] += MAXJSAMPLE; 368 } 369 370 /* in loop, val = index of current output value, */ 371 /* and k = largest j that maps to current val */ 372 indexptr = cquantize->colorindex[i]; 373 val = 0; 374 k = largest_input_value( cinfo, i, 0, nci - 1 ); 375 for ( j = 0; j <= MAXJSAMPLE; j++ ) { 376 while ( j > k ) {/* advance val if past boundary */ 377 k = largest_input_value( cinfo, i, ++val, nci - 1 ); 378 } 379 /* premultiply so that no multiplication needed in main processing */ 380 indexptr[j] = (JSAMPLE) ( val * blksize ); 381 } 382 /* Pad at both ends if necessary */ 383 if ( pad ) { 384 for ( j = 1; j <= MAXJSAMPLE; j++ ) { 385 indexptr[-j] = indexptr[0]; 386 indexptr[MAXJSAMPLE + j] = indexptr[MAXJSAMPLE]; 387 } 388 } 389 } 390 } 391 392 393 /* 394 * Create an ordered-dither array for a component having ncolors 395 * distinct output values. 396 */ 397 398 LOCAL ODITHER_MATRIX_PTR 399 make_odither_array( j_decompress_ptr cinfo, int ncolors ) { 400 ODITHER_MATRIX_PTR odither; 401 int j, k; 402 INT32 num, den; 403 404 odither = (ODITHER_MATRIX_PTR) 405 ( *cinfo->mem->alloc_small )( (j_common_ptr) cinfo, JPOOL_IMAGE, 406 SIZEOF( ODITHER_MATRIX ) ); 407 /* The inter-value distance for this color is MAXJSAMPLE/(ncolors-1). 408 * Hence the dither value for the matrix cell with fill order f 409 * (f=0..N-1) should be (N-1-2*f)/(2*N) * MAXJSAMPLE/(ncolors-1). 410 * On 16-bit-int machine, be careful to avoid overflow. 411 */ 412 den = 2 * ODITHER_CELLS * ( (INT32) ( ncolors - 1 ) ); 413 for ( j = 0; j < ODITHER_SIZE; j++ ) { 414 for ( k = 0; k < ODITHER_SIZE; k++ ) { 415 num = ( (INT32) ( ODITHER_CELLS - 1 - 2 * ( (int)base_dither_matrix[j][k] ) ) ) 416 * MAXJSAMPLE; 417 /* Ensure round towards zero despite C's lack of consistency 418 * about rounding negative values in integer division... 419 */ 420 odither[j][k] = (int) ( num < 0 ? -( ( -num ) / den ) : num / den ); 421 } 422 } 423 return odither; 424 } 425 426 427 /* 428 * Create the ordered-dither tables. 429 * Components having the same number of representative colors may 430 * share a dither table. 431 */ 432 433 LOCAL void 434 create_odither_tables( j_decompress_ptr cinfo ) { 435 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 436 ODITHER_MATRIX_PTR odither; 437 int i, j, nci; 438 439 for ( i = 0; i < cinfo->out_color_components; i++ ) { 440 nci = cquantize->Ncolors[i];/* # of distinct values for this color */ 441 odither = NULL; /* search for matching prior component */ 442 for ( j = 0; j < i; j++ ) { 443 if ( nci == cquantize->Ncolors[j] ) { 444 odither = cquantize->odither[j]; 445 break; 446 } 447 } 448 if ( odither == NULL ) {/* need a new table? */ 449 odither = make_odither_array( cinfo, nci ); 450 } 451 cquantize->odither[i] = odither; 452 } 453 } 454 455 456 /* 457 * Map some rows of pixels to the output colormapped representation. 458 */ 459 460 METHODDEF void 461 color_quantize( j_decompress_ptr cinfo, JSAMPARRAY input_buf, 462 JSAMPARRAY output_buf, int num_rows ) { 463 /* General case, no dithering */ 464 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 465 JSAMPARRAY colorindex = cquantize->colorindex; 466 register int pixcode, ci; 467 register JSAMPROW ptrin, ptrout; 468 int row; 469 JDIMENSION col; 470 JDIMENSION width = cinfo->output_width; 471 register int nc = cinfo->out_color_components; 472 473 for ( row = 0; row < num_rows; row++ ) { 474 ptrin = input_buf[row]; 475 ptrout = output_buf[row]; 476 for ( col = width; col > 0; col-- ) { 477 pixcode = 0; 478 for ( ci = 0; ci < nc; ci++ ) { 479 pixcode += GETJSAMPLE( colorindex[ci][GETJSAMPLE( *ptrin++ )] ); 480 } 481 *ptrout++ = (JSAMPLE) pixcode; 482 } 483 } 484 } 485 486 487 METHODDEF void 488 color_quantize3( j_decompress_ptr cinfo, JSAMPARRAY input_buf, 489 JSAMPARRAY output_buf, int num_rows ) { 490 /* Fast path for out_color_components==3, no dithering */ 491 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 492 register int pixcode; 493 register JSAMPROW ptrin, ptrout; 494 JSAMPROW colorindex0 = cquantize->colorindex[0]; 495 JSAMPROW colorindex1 = cquantize->colorindex[1]; 496 JSAMPROW colorindex2 = cquantize->colorindex[2]; 497 int row; 498 JDIMENSION col; 499 JDIMENSION width = cinfo->output_width; 500 501 for ( row = 0; row < num_rows; row++ ) { 502 ptrin = input_buf[row]; 503 ptrout = output_buf[row]; 504 for ( col = width; col > 0; col-- ) { 505 pixcode = GETJSAMPLE( colorindex0[GETJSAMPLE( *ptrin++ )] ); 506 pixcode += GETJSAMPLE( colorindex1[GETJSAMPLE( *ptrin++ )] ); 507 pixcode += GETJSAMPLE( colorindex2[GETJSAMPLE( *ptrin++ )] ); 508 *ptrout++ = (JSAMPLE) pixcode; 509 } 510 } 511 } 512 513 514 METHODDEF void 515 quantize_ord_dither( j_decompress_ptr cinfo, JSAMPARRAY input_buf, 516 JSAMPARRAY output_buf, int num_rows ) { 517 /* General case, with ordered dithering */ 518 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 519 register JSAMPROW input_ptr; 520 register JSAMPROW output_ptr; 521 JSAMPROW colorindex_ci; 522 int * dither; /* points to active row of dither matrix */ 523 int row_index, col_index;/* current indexes into dither matrix */ 524 int nc = cinfo->out_color_components; 525 int ci; 526 int row; 527 JDIMENSION col; 528 JDIMENSION width = cinfo->output_width; 529 530 for ( row = 0; row < num_rows; row++ ) { 531 /* Initialize output values to 0 so can process components separately */ 532 jzero_far( (void FAR *) output_buf[row], 533 (size_t) ( width * SIZEOF( JSAMPLE ) ) ); 534 row_index = cquantize->row_index; 535 for ( ci = 0; ci < nc; ci++ ) { 536 input_ptr = input_buf[row] + ci; 537 output_ptr = output_buf[row]; 538 colorindex_ci = cquantize->colorindex[ci]; 539 dither = cquantize->odither[ci][row_index]; 540 col_index = 0; 541 542 for ( col = width; col > 0; col-- ) { 543 /* Form pixel value + dither, range-limit to 0..MAXJSAMPLE, 544 * select output value, accumulate into output code for this pixel. 545 * Range-limiting need not be done explicitly, as we have extended 546 * the colorindex table to produce the right answers for out-of-range 547 * inputs. The maximum dither is +- MAXJSAMPLE; this sets the 548 * required amount of padding. 549 */ 550 *output_ptr += colorindex_ci[GETJSAMPLE( *input_ptr ) + dither[col_index]]; 551 input_ptr += nc; 552 output_ptr++; 553 col_index = ( col_index + 1 ) & ODITHER_MASK; 554 } 555 } 556 /* Advance row index for next row */ 557 row_index = ( row_index + 1 ) & ODITHER_MASK; 558 cquantize->row_index = row_index; 559 } 560 } 561 562 563 METHODDEF void 564 quantize3_ord_dither( j_decompress_ptr cinfo, JSAMPARRAY input_buf, 565 JSAMPARRAY output_buf, int num_rows ) { 566 /* Fast path for out_color_components==3, with ordered dithering */ 567 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 568 register int pixcode; 569 register JSAMPROW input_ptr; 570 register JSAMPROW output_ptr; 571 JSAMPROW colorindex0 = cquantize->colorindex[0]; 572 JSAMPROW colorindex1 = cquantize->colorindex[1]; 573 JSAMPROW colorindex2 = cquantize->colorindex[2]; 574 int * dither0; /* points to active row of dither matrix */ 575 int * dither1; 576 int * dither2; 577 int row_index, col_index;/* current indexes into dither matrix */ 578 int row; 579 JDIMENSION col; 580 JDIMENSION width = cinfo->output_width; 581 582 for ( row = 0; row < num_rows; row++ ) { 583 row_index = cquantize->row_index; 584 input_ptr = input_buf[row]; 585 output_ptr = output_buf[row]; 586 dither0 = cquantize->odither[0][row_index]; 587 dither1 = cquantize->odither[1][row_index]; 588 dither2 = cquantize->odither[2][row_index]; 589 col_index = 0; 590 591 for ( col = width; col > 0; col-- ) { 592 pixcode = GETJSAMPLE( colorindex0[GETJSAMPLE( *input_ptr++ ) + 593 dither0[col_index]] ); 594 pixcode += GETJSAMPLE( colorindex1[GETJSAMPLE( *input_ptr++ ) + 595 dither1[col_index]] ); 596 pixcode += GETJSAMPLE( colorindex2[GETJSAMPLE( *input_ptr++ ) + 597 dither2[col_index]] ); 598 *output_ptr++ = (JSAMPLE) pixcode; 599 col_index = ( col_index + 1 ) & ODITHER_MASK; 600 } 601 row_index = ( row_index + 1 ) & ODITHER_MASK; 602 cquantize->row_index = row_index; 603 } 604 } 605 606 607 METHODDEF void 608 quantize_fs_dither( j_decompress_ptr cinfo, JSAMPARRAY input_buf, 609 JSAMPARRAY output_buf, int num_rows ) { 610 /* General case, with Floyd-Steinberg dithering */ 611 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 612 register LOCFSERROR cur;/* current error or pixel value */ 613 LOCFSERROR belowerr; /* error for pixel below cur */ 614 LOCFSERROR bpreverr; /* error for below/prev col */ 615 LOCFSERROR bnexterr; /* error for below/next col */ 616 LOCFSERROR delta; 617 register FSERRPTR errorptr; /* => fserrors[] at column before current */ 618 register JSAMPROW input_ptr; 619 register JSAMPROW output_ptr; 620 JSAMPROW colorindex_ci; 621 JSAMPROW colormap_ci; 622 int pixcode; 623 int nc = cinfo->out_color_components; 624 int dir; /* 1 for left-to-right, -1 for right-to-left */ 625 int dirnc; /* dir * nc */ 626 int ci; 627 int row; 628 JDIMENSION col; 629 JDIMENSION width = cinfo->output_width; 630 JSAMPLE * range_limit = cinfo->sample_range_limit; 631 SHIFT_TEMPS 632 633 for ( row = 0; row < num_rows; row++ ) { 634 /* Initialize output values to 0 so can process components separately */ 635 jzero_far( (void FAR *) output_buf[row], 636 (size_t) ( width * SIZEOF( JSAMPLE ) ) ); 637 for ( ci = 0; ci < nc; ci++ ) { 638 input_ptr = input_buf[row] + ci; 639 output_ptr = output_buf[row]; 640 if ( cquantize->on_odd_row ) { 641 /* work right to left in this row */ 642 input_ptr += ( width - 1 ) * nc;/* so point to rightmost pixel */ 643 output_ptr += width - 1; 644 dir = -1; 645 dirnc = -nc; 646 errorptr = cquantize->fserrors[ci] + ( width + 1 );/* => entry after last column */ 647 } else { 648 /* work left to right in this row */ 649 dir = 1; 650 dirnc = nc; 651 errorptr = cquantize->fserrors[ci];/* => entry before first column */ 652 } 653 colorindex_ci = cquantize->colorindex[ci]; 654 colormap_ci = cquantize->sv_colormap[ci]; 655 /* Preset error values: no error propagated to first pixel from left */ 656 cur = 0; 657 /* and no error propagated to row below yet */ 658 belowerr = bpreverr = 0; 659 660 for ( col = width; col > 0; col-- ) { 661 /* cur holds the error propagated from the previous pixel on the 662 * current line. Add the error propagated from the previous line 663 * to form the complete error correction term for this pixel, and 664 * round the error term (which is expressed * 16) to an integer. 665 * RIGHT_SHIFT rounds towards minus infinity, so adding 8 is correct 666 * for either sign of the error value. 667 * Note: errorptr points to *previous* column's array entry. 668 */ 669 cur = RIGHT_SHIFT( cur + errorptr[dir] + 8, 4 ); 670 /* Form pixel value + error, and range-limit to 0..MAXJSAMPLE. 671 * The maximum error is +- MAXJSAMPLE; this sets the required size 672 * of the range_limit array. 673 */ 674 cur += GETJSAMPLE( *input_ptr ); 675 cur = GETJSAMPLE( range_limit[cur] ); 676 /* Select output value, accumulate into output code for this pixel */ 677 pixcode = GETJSAMPLE( colorindex_ci[cur] ); 678 *output_ptr += (JSAMPLE) pixcode; 679 /* Compute actual representation error at this pixel */ 680 /* Note: we can do this even though we don't have the final */ 681 /* pixel code, because the colormap is orthogonal. */ 682 cur -= GETJSAMPLE( colormap_ci[pixcode] ); 683 /* Compute error fractions to be propagated to adjacent pixels. 684 * Add these into the running sums, and simultaneously shift the 685 * next-line error sums left by 1 column. 686 */ 687 bnexterr = cur; 688 delta = cur * 2; 689 cur += delta;/* form error * 3 */ 690 errorptr[0] = (FSERROR) ( bpreverr + cur ); 691 cur += delta;/* form error * 5 */ 692 bpreverr = belowerr + cur; 693 belowerr = bnexterr; 694 cur += delta;/* form error * 7 */ 695 /* At this point cur contains the 7/16 error value to be propagated 696 * to the next pixel on the current line, and all the errors for the 697 * next line have been shifted over. We are therefore ready to move on. 698 */ 699 input_ptr += dirnc;/* advance input ptr to next column */ 700 output_ptr += dir;/* advance output ptr to next column */ 701 errorptr += dir;/* advance errorptr to current column */ 702 } 703 /* Post-loop cleanup: we must unload the final error value into the 704 * final fserrors[] entry. Note we need not unload belowerr because 705 * it is for the dummy column before or after the actual array. 706 */ 707 errorptr[0] = (FSERROR) bpreverr;/* unload prev err into array */ 708 } 709 cquantize->on_odd_row = ( cquantize->on_odd_row ? FALSE : TRUE ); 710 } 711 } 712 713 714 /* 715 * Allocate workspace for Floyd-Steinberg errors. 716 */ 717 718 LOCAL void 719 alloc_fs_workspace( j_decompress_ptr cinfo ) { 720 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 721 size_t arraysize; 722 int i; 723 724 arraysize = (size_t) ( ( cinfo->output_width + 2 ) * SIZEOF( FSERROR ) ); 725 for ( i = 0; i < cinfo->out_color_components; i++ ) { 726 cquantize->fserrors[i] = (FSERRPTR) 727 ( *cinfo->mem->alloc_large )( (j_common_ptr) cinfo, JPOOL_IMAGE, arraysize ); 728 } 729 } 730 731 732 /* 733 * Initialize for one-pass color quantization. 734 */ 735 736 METHODDEF void 737 start_pass_1_quant( j_decompress_ptr cinfo, boolean is_pre_scan ) { 738 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 739 size_t arraysize; 740 int i; 741 742 /* Install my colormap. */ 743 cinfo->colormap = cquantize->sv_colormap; 744 cinfo->actual_number_of_colors = cquantize->sv_actual; 745 746 /* Initialize for desired dithering mode. */ 747 switch ( cinfo->dither_mode ) { 748 case JDITHER_NONE: 749 if ( cinfo->out_color_components == 3 ) { 750 cquantize->pub.color_quantize = color_quantize3; 751 } else { 752 cquantize->pub.color_quantize = color_quantize; 753 } 754 break; 755 case JDITHER_ORDERED: 756 if ( cinfo->out_color_components == 3 ) { 757 cquantize->pub.color_quantize = quantize3_ord_dither; 758 } else { 759 cquantize->pub.color_quantize = quantize_ord_dither; 760 } 761 cquantize->row_index = 0;/* initialize state for ordered dither */ 762 /* If user changed to ordered dither from another mode, 763 * we must recreate the color index table with padding. 764 * This will cost extra space, but probably isn't very likely. 765 */ 766 if ( !cquantize->is_padded ) { 767 create_colorindex( cinfo ); 768 } 769 /* Create ordered-dither tables if we didn't already. */ 770 if ( cquantize->odither[0] == NULL ) { 771 create_odither_tables( cinfo ); 772 } 773 break; 774 case JDITHER_FS: 775 cquantize->pub.color_quantize = quantize_fs_dither; 776 cquantize->on_odd_row = FALSE;/* initialize state for F-S dither */ 777 /* Allocate Floyd-Steinberg workspace if didn't already. */ 778 if ( cquantize->fserrors[0] == NULL ) { 779 alloc_fs_workspace( cinfo ); 780 } 781 /* Initialize the propagated errors to zero. */ 782 arraysize = (size_t) ( ( cinfo->output_width + 2 ) * SIZEOF( FSERROR ) ); 783 for ( i = 0; i < cinfo->out_color_components; i++ ) { 784 jzero_far( (void FAR *) cquantize->fserrors[i], arraysize ); 785 } 786 break; 787 default: 788 ERREXIT( cinfo, JERR_NOT_COMPILED ); 789 break; 790 } 791 } 792 793 794 /* 795 * Finish up at the end of the pass. 796 */ 797 798 METHODDEF void 799 finish_pass_1_quant( j_decompress_ptr cinfo ) { 800 /* no work in 1-pass case */ 801 } 802 803 804 /* 805 * Switch to a new external colormap between output passes. 806 * Shouldn't get to this module! 807 */ 808 809 METHODDEF void 810 new_color_map_1_quant( j_decompress_ptr cinfo ) { 811 ERREXIT( cinfo, JERR_MODE_CHANGE ); 812 } 813 814 815 /* 816 * Module initialization routine for 1-pass color quantization. 817 */ 818 819 GLOBAL void 820 jinit_1pass_quantizer( j_decompress_ptr cinfo ) { 821 my_cquantize_ptr cquantize; 822 823 cquantize = (my_cquantize_ptr) 824 ( *cinfo->mem->alloc_small )( (j_common_ptr) cinfo, JPOOL_IMAGE, 825 SIZEOF( my_cquantizer ) ); 826 cinfo->cquantize = (struct jpeg_color_quantizer *) cquantize; 827 cquantize->pub.start_pass = start_pass_1_quant; 828 cquantize->pub.finish_pass = finish_pass_1_quant; 829 cquantize->pub.new_color_map = new_color_map_1_quant; 830 cquantize->fserrors[0] = NULL;/* Flag FS workspace not allocated */ 831 cquantize->odither[0] = NULL;/* Also flag odither arrays not allocated */ 832 833 /* Make sure my internal arrays won't overflow */ 834 if ( cinfo->out_color_components > MAX_Q_COMPS ) { 835 ERREXIT1( cinfo, JERR_QUANT_COMPONENTS, MAX_Q_COMPS ); 836 } 837 /* Make sure colormap indexes can be represented by JSAMPLEs */ 838 if ( cinfo->desired_number_of_colors > ( MAXJSAMPLE + 1 ) ) { 839 ERREXIT1( cinfo, JERR_QUANT_MANY_COLORS, MAXJSAMPLE + 1 ); 840 } 841 842 /* Create the colormap and color index table. */ 843 create_colormap( cinfo ); 844 create_colorindex( cinfo ); 845 846 /* Allocate Floyd-Steinberg workspace now if requested. 847 * We do this now since it is FAR storage and may affect the memory 848 * manager's space calculations. If the user changes to FS dither 849 * mode in a later pass, we will allocate the space then, and will 850 * possibly overrun the max_memory_to_use setting. 851 */ 852 if ( cinfo->dither_mode == JDITHER_FS ) { 853 alloc_fs_workspace( cinfo ); 854 } 855 } 856 857 #endif /* QUANT_1PASS_SUPPORTED */