/* * jquant1.c * * This file was part of the Independent JPEG Group's software: * Copyright (C) 1991-1996, Thomas G. Lane. * libjpeg-turbo Modifications: * Copyright (C) 2009, 2015, D. R. Commander. * For conditions of distribution and use, see the accompanying README.ijg * file. * * This file contains 1-pass color quantization (color mapping) routines. * These routines provide mapping to a fixed color map using equally spaced * color values. Optional Floyd-Steinberg or ordered dithering is available. */ #define JPEG_INTERNALS #include "jinclude.h" #include "jpeglib.h" #ifdef QUANT_1PASS_SUPPORTED /* * The main purpose of 1-pass quantization is to provide a fast, if not very * high quality, colormapped output capability. A 2-pass quantizer usually * gives better visual quality; however, for quantized grayscale output this * quantizer is perfectly adequate. Dithering is highly recommended with this * quantizer, though you can turn it off if you really want to. * * In 1-pass quantization the colormap must be chosen in advance of seeing the * image. We use a map consisting of all combinations of Ncolors[i] color * values for the i'th component. The Ncolors[] values are chosen so that * their product, the total number of colors, is no more than that requested. * (In most cases, the product will be somewhat less.) * * Since the colormap is orthogonal, the representative value for each color * component can be determined without considering the other components; * then these indexes can be combined into a colormap index by a standard * N-dimensional-array-subscript calculation. Most of the arithmetic involved * can be precalculated and stored in the lookup table colorindex[]. * colorindex[i][j] maps pixel value j in component i to the nearest * representative value (grid plane) for that component; this index is * multiplied by the array stride for component i, so that the * index of the colormap entry closest to a given pixel value is just * sum( colorindex[component-number][pixel-component-value] ) * Aside from being fast, this scheme allows for variable spacing between * representative values with no additional lookup cost. * * If gamma correction has been applied in color conversion, it might be wise * to adjust the color grid spacing so that the representative colors are * equidistant in linear space. At this writing, gamma correction is not * implemented by jdcolor, so nothing is done here. */ /* Declarations for ordered dithering. * * We use a standard 16x16 ordered dither array. The basic concept of ordered * dithering is described in many references, for instance Dale Schumacher's * chapter II.2 of Graphics Gems II (James Arvo, ed. Academic Press, 1991). * In place of Schumacher's comparisons against a "threshold" value, we add a * "dither" value to the input pixel and then round the result to the nearest * output value. The dither value is equivalent to (0.5 - threshold) times * the distance between output values. For ordered dithering, we assume that * the output colors are equally spaced; if not, results will probably be * worse, since the dither may be too much or too little at a given point. * * The normal calculation would be to form pixel value + dither, range-limit * this to 0..MAXJSAMPLE, and then index into the colorindex table as usual. * We can skip the separate range-limiting step by extending the colorindex * table in both directions. */ #define ODITHER_SIZE … /* NB: if ODITHER_SIZE is not a power of 2, ODITHER_MASK uses will break */ #define ODITHER_CELLS … #define ODITHER_MASK … ODITHER_MATRIX; ODITHER_MATRIX_PTR; static const UINT8 base_dither_matrix[ODITHER_SIZE][ODITHER_SIZE] = …; /* Declarations for Floyd-Steinberg dithering. * * Errors are accumulated into the array fserrors[], at a resolution of * 1/16th of a pixel count. The error at a given pixel is propagated * to its not-yet-processed 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. * * We can get away with a single array (holding one row's worth of errors) * by using it to store the current row's errors at pixel columns not yet * processed, but the next row's errors at columns already processed. We * need only a few extra variables to hold the errors immediately around the * current column. (If we are lucky, those variables are in registers, but * even if not, they're probably cheaper to access than array elements are.) * * The fserrors[] array is indexed [component#][position]. * We provide (#columns + 2) entries per component; the extra entry at each * end saves us from special-casing the first and last pixels. */ #if BITS_IN_JSAMPLE == 8 FSERROR; /* 16 bits should be enough */ LOCFSERROR; /* use 'int' for calculation temps */ #else typedef JLONG FSERROR; /* may need more than 16 bits */ typedef JLONG LOCFSERROR; /* be sure calculation temps are big enough */ #endif FSERRPTR; /* pointer to error array */ /* Private subobject */ #define MAX_Q_COMPS … my_cquantizer; my_cquantize_ptr; /* * Policy-making subroutines for create_colormap and create_colorindex. * These routines determine the colormap to be used. The rest of the module * only assumes that the colormap is orthogonal. * * * select_ncolors decides how to divvy up the available colors * among the components. * * output_value defines the set of representative values for a component. * * largest_input_value defines the mapping from input values to * representative values for a component. * Note that the latter two routines may impose different policies for * different components, though this is not currently done. */ LOCAL(int) select_ncolors(j_decompress_ptr cinfo, int Ncolors[]) /* Determine allocation of desired colors to components, */ /* and fill in Ncolors[] array to indicate choice. */ /* Return value is total number of colors (product of Ncolors[] values). */ { … } LOCAL(int) output_value(j_decompress_ptr cinfo, int ci, int j, int maxj) /* Return j'th output value, where j will range from 0 to maxj */ /* The output values must fall in 0..MAXJSAMPLE in increasing order */ { … } LOCAL(int) largest_input_value(j_decompress_ptr cinfo, int ci, int j, int maxj) /* Return largest input value that should map to j'th output value */ /* Must have largest(j=0) >= 0, and largest(j=maxj) >= MAXJSAMPLE */ { … } /* * Create the colormap. */ LOCAL(void) create_colormap(j_decompress_ptr cinfo) { … } /* * Create the color index table. */ LOCAL(void) create_colorindex(j_decompress_ptr cinfo) { … } /* * Create an ordered-dither array for a component having ncolors * distinct output values. */ LOCAL(ODITHER_MATRIX_PTR) make_odither_array(j_decompress_ptr cinfo, int ncolors) { … } /* * Create the ordered-dither tables. * Components having the same number of representative colors may * share a dither table. */ LOCAL(void) create_odither_tables(j_decompress_ptr cinfo) { … } /* * Map some rows of pixels to the output colormapped representation. */ METHODDEF(void) color_quantize(j_decompress_ptr cinfo, JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows) /* General case, no dithering */ { … } METHODDEF(void) color_quantize3(j_decompress_ptr cinfo, JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows) /* Fast path for out_color_components==3, no dithering */ { … } METHODDEF(void) quantize_ord_dither(j_decompress_ptr cinfo, JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows) /* General case, with ordered dithering */ { … } METHODDEF(void) quantize3_ord_dither(j_decompress_ptr cinfo, JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows) /* Fast path for out_color_components==3, with ordered dithering */ { … } METHODDEF(void) quantize_fs_dither(j_decompress_ptr cinfo, JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows) /* General case, with Floyd-Steinberg dithering */ { … } /* * Allocate workspace for Floyd-Steinberg errors. */ LOCAL(void) alloc_fs_workspace(j_decompress_ptr cinfo) { … } /* * Initialize for one-pass color quantization. */ METHODDEF(void) start_pass_1_quant(j_decompress_ptr cinfo, boolean is_pre_scan) { … } /* * Finish up at the end of the pass. */ METHODDEF(void) finish_pass_1_quant(j_decompress_ptr cinfo) { … } /* * Switch to a new external colormap between output passes. * Shouldn't get to this module! */ METHODDEF(void) new_color_map_1_quant(j_decompress_ptr cinfo) { … } /* * Module initialization routine for 1-pass color quantization. */ GLOBAL(void) jinit_1pass_quantizer(j_decompress_ptr cinfo) { … } #endif /* QUANT_1PASS_SUPPORTED */
Codebase Browser
chromium