uzairkhan - Final 350 project

Users » shoaib_ahmed » Code » uzairkhan

Shoaib Ahmed / Mbed 2 deprecated uzairkhan

Final 350 project

Dependencies: uzair Camera_LS_Y201 F7_Ethernet LCD_DISCO_F746NG NetworkAPI SDFileSystem mbed

includes/jquant2.c@0:791a779d6220, 2017-07-31 (annotated)

Committer:: shoaib_ahmed
Date:: Mon Jul 31 09:16:35 2017 +0000
Revision:: 0:791a779d6220

final project;

Who changed what in which revision?

User	Revision	Line number	New contents of line
shoaib_ahmed	0:791a779d6220	1	/*
shoaib_ahmed	0:791a779d6220	2	* jquant2.c
shoaib_ahmed	0:791a779d6220	3	*
shoaib_ahmed	0:791a779d6220	4	* Copyright (C) 1991-1996, Thomas G. Lane.
shoaib_ahmed	0:791a779d6220	5	* Modified 2011 by Guido Vollbeding.
shoaib_ahmed	0:791a779d6220	6	* This file is part of the Independent JPEG Group's software.
shoaib_ahmed	0:791a779d6220	7	* For conditions of distribution and use, see the accompanying README file.
shoaib_ahmed	0:791a779d6220	8	*
shoaib_ahmed	0:791a779d6220	9	* This file contains 2-pass color quantization (color mapping) routines.
shoaib_ahmed	0:791a779d6220	10	* These routines provide selection of a custom color map for an image,
shoaib_ahmed	0:791a779d6220	11	* followed by mapping of the image to that color map, with optional
shoaib_ahmed	0:791a779d6220	12	* Floyd-Steinberg dithering.
shoaib_ahmed	0:791a779d6220	13	* It is also possible to use just the second pass to map to an arbitrary
shoaib_ahmed	0:791a779d6220	14	* externally-given color map.
shoaib_ahmed	0:791a779d6220	15	*
shoaib_ahmed	0:791a779d6220	16	* Note: ordered dithering is not supported, since there isn't any fast
shoaib_ahmed	0:791a779d6220	17	* way to compute intercolor distances; it's unclear that ordered dither's
shoaib_ahmed	0:791a779d6220	18	* fundamental assumptions even hold with an irregularly spaced color map.
shoaib_ahmed	0:791a779d6220	19	*/
shoaib_ahmed	0:791a779d6220	20
shoaib_ahmed	0:791a779d6220	21	#define JPEG_INTERNALS
shoaib_ahmed	0:791a779d6220	22	#include "jinclude.h"
shoaib_ahmed	0:791a779d6220	23	#include "jpeglib.h"
shoaib_ahmed	0:791a779d6220	24
shoaib_ahmed	0:791a779d6220	25	#ifdef QUANT_2PASS_SUPPORTED
shoaib_ahmed	0:791a779d6220	26
shoaib_ahmed	0:791a779d6220	27
shoaib_ahmed	0:791a779d6220	28	/*
shoaib_ahmed	0:791a779d6220	29	* This module implements the well-known Heckbert paradigm for color
shoaib_ahmed	0:791a779d6220	30	* quantization. Most of the ideas used here can be traced back to
shoaib_ahmed	0:791a779d6220	31	* Heckbert's seminal paper
shoaib_ahmed	0:791a779d6220	32	* Heckbert, Paul. "Color Image Quantization for Frame Buffer Display",
shoaib_ahmed	0:791a779d6220	33	* Proc. SIGGRAPH '82, Computer Graphics v.16 #3 (July 1982), pp 297-304.
shoaib_ahmed	0:791a779d6220	34	*
shoaib_ahmed	0:791a779d6220	35	* In the first pass over the image, we accumulate a histogram showing the
shoaib_ahmed	0:791a779d6220	36	* usage count of each possible color. To keep the histogram to a reasonable
shoaib_ahmed	0:791a779d6220	37	* size, we reduce the precision of the input; typical practice is to retain
shoaib_ahmed	0:791a779d6220	38	* 5 or 6 bits per color, so that 8 or 4 different input values are counted
shoaib_ahmed	0:791a779d6220	39	* in the same histogram cell.
shoaib_ahmed	0:791a779d6220	40	*
shoaib_ahmed	0:791a779d6220	41	* Next, the color-selection step begins with a box representing the whole
shoaib_ahmed	0:791a779d6220	42	* color space, and repeatedly splits the "largest" remaining box until we
shoaib_ahmed	0:791a779d6220	43	* have as many boxes as desired colors. Then the mean color in each
shoaib_ahmed	0:791a779d6220	44	* remaining box becomes one of the possible output colors.
shoaib_ahmed	0:791a779d6220	45	*
shoaib_ahmed	0:791a779d6220	46	* The second pass over the image maps each input pixel to the closest output
shoaib_ahmed	0:791a779d6220	47	* color (optionally after applying a Floyd-Steinberg dithering correction).
shoaib_ahmed	0:791a779d6220	48	* This mapping is logically trivial, but making it go fast enough requires
shoaib_ahmed	0:791a779d6220	49	* considerable care.
shoaib_ahmed	0:791a779d6220	50	*
shoaib_ahmed	0:791a779d6220	51	* Heckbert-style quantizers vary a good deal in their policies for choosing
shoaib_ahmed	0:791a779d6220	52	* the "largest" box and deciding where to cut it. The particular policies
shoaib_ahmed	0:791a779d6220	53	* used here have proved out well in experimental comparisons, but better ones
shoaib_ahmed	0:791a779d6220	54	* may yet be found.
shoaib_ahmed	0:791a779d6220	55	*
shoaib_ahmed	0:791a779d6220	56	* In earlier versions of the IJG code, this module quantized in YCbCr color
shoaib_ahmed	0:791a779d6220	57	* space, processing the raw upsampled data without a color conversion step.
shoaib_ahmed	0:791a779d6220	58	* This allowed the color conversion math to be done only once per colormap
shoaib_ahmed	0:791a779d6220	59	* entry, not once per pixel. However, that optimization precluded other
shoaib_ahmed	0:791a779d6220	60	* useful optimizations (such as merging color conversion with upsampling)
shoaib_ahmed	0:791a779d6220	61	* and it also interfered with desired capabilities such as quantizing to an
shoaib_ahmed	0:791a779d6220	62	* externally-supplied colormap. We have therefore abandoned that approach.
shoaib_ahmed	0:791a779d6220	63	* The present code works in the post-conversion color space, typically RGB.
shoaib_ahmed	0:791a779d6220	64	*
shoaib_ahmed	0:791a779d6220	65	* To improve the visual quality of the results, we actually work in scaled
shoaib_ahmed	0:791a779d6220	66	* RGB space, giving G distances more weight than R, and R in turn more than
shoaib_ahmed	0:791a779d6220	67	* B. To do everything in integer math, we must use integer scale factors.
shoaib_ahmed	0:791a779d6220	68	* The 2/3/1 scale factors used here correspond loosely to the relative
shoaib_ahmed	0:791a779d6220	69	* weights of the colors in the NTSC grayscale equation.
shoaib_ahmed	0:791a779d6220	70	* If you want to use this code to quantize a non-RGB color space, you'll
shoaib_ahmed	0:791a779d6220	71	* probably need to change these scale factors.
shoaib_ahmed	0:791a779d6220	72	*/
shoaib_ahmed	0:791a779d6220	73
shoaib_ahmed	0:791a779d6220	74	#define R_SCALE 2 /* scale R distances by this much */
shoaib_ahmed	0:791a779d6220	75	#define G_SCALE 3 /* scale G distances by this much */
shoaib_ahmed	0:791a779d6220	76	#define B_SCALE 1 /* and B by this much */
shoaib_ahmed	0:791a779d6220	77
shoaib_ahmed	0:791a779d6220	78	/* Relabel R/G/B as components 0/1/2, respecting the RGB ordering defined
shoaib_ahmed	0:791a779d6220	79	* in jmorecfg.h. As the code stands, it will do the right thing for R,G,B
shoaib_ahmed	0:791a779d6220	80	* and B,G,R orders. If you define some other weird order in jmorecfg.h,
shoaib_ahmed	0:791a779d6220	81	* you'll get compile errors until you extend this logic. In that case
shoaib_ahmed	0:791a779d6220	82	* you'll probably want to tweak the histogram sizes too.
shoaib_ahmed	0:791a779d6220	83	*/
shoaib_ahmed	0:791a779d6220	84
shoaib_ahmed	0:791a779d6220	85	#if RGB_RED == 0
shoaib_ahmed	0:791a779d6220	86	#define C0_SCALE R_SCALE
shoaib_ahmed	0:791a779d6220	87	#endif
shoaib_ahmed	0:791a779d6220	88	#if RGB_BLUE == 0
shoaib_ahmed	0:791a779d6220	89	#define C0_SCALE B_SCALE
shoaib_ahmed	0:791a779d6220	90	#endif
shoaib_ahmed	0:791a779d6220	91	#if RGB_GREEN == 1
shoaib_ahmed	0:791a779d6220	92	#define C1_SCALE G_SCALE
shoaib_ahmed	0:791a779d6220	93	#endif
shoaib_ahmed	0:791a779d6220	94	#if RGB_RED == 2
shoaib_ahmed	0:791a779d6220	95	#define C2_SCALE R_SCALE
shoaib_ahmed	0:791a779d6220	96	#endif
shoaib_ahmed	0:791a779d6220	97	#if RGB_BLUE == 2
shoaib_ahmed	0:791a779d6220	98	#define C2_SCALE B_SCALE
shoaib_ahmed	0:791a779d6220	99	#endif
shoaib_ahmed	0:791a779d6220	100
shoaib_ahmed	0:791a779d6220	101
shoaib_ahmed	0:791a779d6220	102	/*
shoaib_ahmed	0:791a779d6220	103	* First we have the histogram data structure and routines for creating it.
shoaib_ahmed	0:791a779d6220	104	*
shoaib_ahmed	0:791a779d6220	105	* The number of bits of precision can be adjusted by changing these symbols.
shoaib_ahmed	0:791a779d6220	106	* We recommend keeping 6 bits for G and 5 each for R and B.
shoaib_ahmed	0:791a779d6220	107	* If you have plenty of memory and cycles, 6 bits all around gives marginally
shoaib_ahmed	0:791a779d6220	108	* better results; if you are short of memory, 5 bits all around will save
shoaib_ahmed	0:791a779d6220	109	* some space but degrade the results.
shoaib_ahmed	0:791a779d6220	110	* To maintain a fully accurate histogram, we'd need to allocate a "long"
shoaib_ahmed	0:791a779d6220	111	* (preferably unsigned long) for each cell. In practice this is overkill;
shoaib_ahmed	0:791a779d6220	112	* we can get by with 16 bits per cell. Few of the cell counts will overflow,
shoaib_ahmed	0:791a779d6220	113	* and clamping those that do overflow to the maximum value will give close-
shoaib_ahmed	0:791a779d6220	114	* enough results. This reduces the recommended histogram size from 256Kb
shoaib_ahmed	0:791a779d6220	115	* to 128Kb, which is a useful savings on PC-class machines.
shoaib_ahmed	0:791a779d6220	116	* (In the second pass the histogram space is re-used for pixel mapping data;
shoaib_ahmed	0:791a779d6220	117	* in that capacity, each cell must be able to store zero to the number of
shoaib_ahmed	0:791a779d6220	118	* desired colors. 16 bits/cell is plenty for that too.)
shoaib_ahmed	0:791a779d6220	119	* Since the JPEG code is intended to run in small memory model on 80x86
shoaib_ahmed	0:791a779d6220	120	* machines, we can't just allocate the histogram in one chunk. Instead
shoaib_ahmed	0:791a779d6220	121	* of a true 3-D array, we use a row of pointers to 2-D arrays. Each
shoaib_ahmed	0:791a779d6220	122	* pointer corresponds to a C0 value (typically 2^5 = 32 pointers) and
shoaib_ahmed	0:791a779d6220	123	* each 2-D array has 2^62^5 = 2048 or 2^62^6 = 4096 entries. Note that
shoaib_ahmed	0:791a779d6220	124	* on 80x86 machines, the pointer row is in near memory but the actual
shoaib_ahmed	0:791a779d6220	125	* arrays are in far memory (same arrangement as we use for image arrays).
shoaib_ahmed	0:791a779d6220	126	*/
shoaib_ahmed	0:791a779d6220	127
shoaib_ahmed	0:791a779d6220	128	#define MAXNUMCOLORS (MAXJSAMPLE+1) /* maximum size of colormap */
shoaib_ahmed	0:791a779d6220	129
shoaib_ahmed	0:791a779d6220	130	/* These will do the right thing for either R,G,B or B,G,R color order,
shoaib_ahmed	0:791a779d6220	131	* but you may not like the results for other color orders.
shoaib_ahmed	0:791a779d6220	132	*/
shoaib_ahmed	0:791a779d6220	133	#define HIST_C0_BITS 5 /* bits of precision in R/B histogram */
shoaib_ahmed	0:791a779d6220	134	#define HIST_C1_BITS 6 /* bits of precision in G histogram */
shoaib_ahmed	0:791a779d6220	135	#define HIST_C2_BITS 5 /* bits of precision in B/R histogram */
shoaib_ahmed	0:791a779d6220	136
shoaib_ahmed	0:791a779d6220	137	/* Number of elements along histogram axes. */
shoaib_ahmed	0:791a779d6220	138	#define HIST_C0_ELEMS (1<<HIST_C0_BITS)
shoaib_ahmed	0:791a779d6220	139	#define HIST_C1_ELEMS (1<<HIST_C1_BITS)
shoaib_ahmed	0:791a779d6220	140	#define HIST_C2_ELEMS (1<<HIST_C2_BITS)
shoaib_ahmed	0:791a779d6220	141
shoaib_ahmed	0:791a779d6220	142	/* These are the amounts to shift an input value to get a histogram index. */
shoaib_ahmed	0:791a779d6220	143	#define C0_SHIFT (BITS_IN_JSAMPLE-HIST_C0_BITS)
shoaib_ahmed	0:791a779d6220	144	#define C1_SHIFT (BITS_IN_JSAMPLE-HIST_C1_BITS)
shoaib_ahmed	0:791a779d6220	145	#define C2_SHIFT (BITS_IN_JSAMPLE-HIST_C2_BITS)
shoaib_ahmed	0:791a779d6220	146
shoaib_ahmed	0:791a779d6220	147
shoaib_ahmed	0:791a779d6220	148	typedef UINT16 histcell; /* histogram cell; prefer an unsigned type */
shoaib_ahmed	0:791a779d6220	149
shoaib_ahmed	0:791a779d6220	150	typedef histcell FAR * histptr; /* for pointers to histogram cells */
shoaib_ahmed	0:791a779d6220	151
shoaib_ahmed	0:791a779d6220	152	typedef histcell hist1d[HIST_C2_ELEMS]; /* typedefs for the array */
shoaib_ahmed	0:791a779d6220	153	typedef hist1d FAR * hist2d; /* type for the 2nd-level pointers */
shoaib_ahmed	0:791a779d6220	154	typedef hist2d * hist3d; /* type for top-level pointer */
shoaib_ahmed	0:791a779d6220	155
shoaib_ahmed	0:791a779d6220	156
shoaib_ahmed	0:791a779d6220	157	/* Declarations for Floyd-Steinberg dithering.
shoaib_ahmed	0:791a779d6220	158	*
shoaib_ahmed	0:791a779d6220	159	* Errors are accumulated into the array fserrors[], at a resolution of
shoaib_ahmed	0:791a779d6220	160	* 1/16th of a pixel count. The error at a given pixel is propagated
shoaib_ahmed	0:791a779d6220	161	* to its not-yet-processed neighbors using the standard F-S fractions,
shoaib_ahmed	0:791a779d6220	162	* ... (here) 7/16
shoaib_ahmed	0:791a779d6220	163	* 3/16 5/16 1/16
shoaib_ahmed	0:791a779d6220	164	* We work left-to-right on even rows, right-to-left on odd rows.
shoaib_ahmed	0:791a779d6220	165	*
shoaib_ahmed	0:791a779d6220	166	* We can get away with a single array (holding one row's worth of errors)
shoaib_ahmed	0:791a779d6220	167	* by using it to store the current row's errors at pixel columns not yet
shoaib_ahmed	0:791a779d6220	168	* processed, but the next row's errors at columns already processed. We
shoaib_ahmed	0:791a779d6220	169	* need only a few extra variables to hold the errors immediately around the
shoaib_ahmed	0:791a779d6220	170	* current column. (If we are lucky, those variables are in registers, but
shoaib_ahmed	0:791a779d6220	171	* even if not, they're probably cheaper to access than array elements are.)
shoaib_ahmed	0:791a779d6220	172	*
shoaib_ahmed	0:791a779d6220	173	* The fserrors[] array has (#columns + 2) entries; the extra entry at
shoaib_ahmed	0:791a779d6220	174	* each end saves us from special-casing the first and last pixels.
shoaib_ahmed	0:791a779d6220	175	* Each entry is three values long, one value for each color component.
shoaib_ahmed	0:791a779d6220	176	*
shoaib_ahmed	0:791a779d6220	177	* Note: on a wide image, we might not have enough room in a PC's near data
shoaib_ahmed	0:791a779d6220	178	* segment to hold the error array; so it is allocated with alloc_large.
shoaib_ahmed	0:791a779d6220	179	*/
shoaib_ahmed	0:791a779d6220	180
shoaib_ahmed	0:791a779d6220	181	#if BITS_IN_JSAMPLE == 8
shoaib_ahmed	0:791a779d6220	182	typedef INT16 FSERROR; /* 16 bits should be enough */
shoaib_ahmed	0:791a779d6220	183	typedef int LOCFSERROR; /* use 'int' for calculation temps */
shoaib_ahmed	0:791a779d6220	184	#else
shoaib_ahmed	0:791a779d6220	185	typedef INT32 FSERROR; /* may need more than 16 bits */
shoaib_ahmed	0:791a779d6220	186	typedef INT32 LOCFSERROR; /* be sure calculation temps are big enough */
shoaib_ahmed	0:791a779d6220	187	#endif
shoaib_ahmed	0:791a779d6220	188
shoaib_ahmed	0:791a779d6220	189	typedef FSERROR FAR FSERRPTR; / pointer to error array (in FAR storage!) */
shoaib_ahmed	0:791a779d6220	190
shoaib_ahmed	0:791a779d6220	191
shoaib_ahmed	0:791a779d6220	192	/* Private subobject */
shoaib_ahmed	0:791a779d6220	193
shoaib_ahmed	0:791a779d6220	194	typedef struct {
shoaib_ahmed	0:791a779d6220	195	struct jpeg_color_quantizer pub; /* public fields */
shoaib_ahmed	0:791a779d6220	196
shoaib_ahmed	0:791a779d6220	197	/* Space for the eventually created colormap is stashed here */
shoaib_ahmed	0:791a779d6220	198	JSAMPARRAY sv_colormap; /* colormap allocated at init time */
shoaib_ahmed	0:791a779d6220	199	int desired; /* desired # of colors = size of colormap */
shoaib_ahmed	0:791a779d6220	200
shoaib_ahmed	0:791a779d6220	201	/* Variables for accumulating image statistics */
shoaib_ahmed	0:791a779d6220	202	hist3d histogram; /* pointer to the histogram */
shoaib_ahmed	0:791a779d6220	203
shoaib_ahmed	0:791a779d6220	204	boolean needs_zeroed; /* TRUE if next pass must zero histogram */
shoaib_ahmed	0:791a779d6220	205
shoaib_ahmed	0:791a779d6220	206	/* Variables for Floyd-Steinberg dithering */
shoaib_ahmed	0:791a779d6220	207	FSERRPTR fserrors; /* accumulated errors */
shoaib_ahmed	0:791a779d6220	208	boolean on_odd_row; /* flag to remember which row we are on */
shoaib_ahmed	0:791a779d6220	209	int * error_limiter; /* table for clamping the applied error */
shoaib_ahmed	0:791a779d6220	210	} my_cquantizer;
shoaib_ahmed	0:791a779d6220	211
shoaib_ahmed	0:791a779d6220	212	typedef my_cquantizer * my_cquantize_ptr;
shoaib_ahmed	0:791a779d6220	213
shoaib_ahmed	0:791a779d6220	214
shoaib_ahmed	0:791a779d6220	215	/*
shoaib_ahmed	0:791a779d6220	216	* Prescan some rows of pixels.
shoaib_ahmed	0:791a779d6220	217	* In this module the prescan simply updates the histogram, which has been
shoaib_ahmed	0:791a779d6220	218	* initialized to zeroes by start_pass.
shoaib_ahmed	0:791a779d6220	219	* An output_buf parameter is required by the method signature, but no data
shoaib_ahmed	0:791a779d6220	220	* is actually output (in fact the buffer controller is probably passing a
shoaib_ahmed	0:791a779d6220	221	* NULL pointer).
shoaib_ahmed	0:791a779d6220	222	*/
shoaib_ahmed	0:791a779d6220	223
shoaib_ahmed	0:791a779d6220	224	METHODDEF(void)
shoaib_ahmed	0:791a779d6220	225	prescan_quantize (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
shoaib_ahmed	0:791a779d6220	226	JSAMPARRAY output_buf, int num_rows)
shoaib_ahmed	0:791a779d6220	227	{
shoaib_ahmed	0:791a779d6220	228	my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
shoaib_ahmed	0:791a779d6220	229	register JSAMPROW ptr;
shoaib_ahmed	0:791a779d6220	230	register histptr histp;
shoaib_ahmed	0:791a779d6220	231	register hist3d histogram = cquantize->histogram;
shoaib_ahmed	0:791a779d6220	232	int row;
shoaib_ahmed	0:791a779d6220	233	JDIMENSION col;
shoaib_ahmed	0:791a779d6220	234	JDIMENSION width = cinfo->output_width;
shoaib_ahmed	0:791a779d6220	235
shoaib_ahmed	0:791a779d6220	236	for (row = 0; row < num_rows; row++) {
shoaib_ahmed	0:791a779d6220	237	ptr = input_buf[row];
shoaib_ahmed	0:791a779d6220	238	for (col = width; col > 0; col--) {
shoaib_ahmed	0:791a779d6220	239	/* get pixel value and index into the histogram */
shoaib_ahmed	0:791a779d6220	240	histp = & histogram[GETJSAMPLE(ptr[0]) >> C0_SHIFT]
shoaib_ahmed	0:791a779d6220	241	[GETJSAMPLE(ptr[1]) >> C1_SHIFT]
shoaib_ahmed	0:791a779d6220	242	[GETJSAMPLE(ptr[2]) >> C2_SHIFT];
shoaib_ahmed	0:791a779d6220	243	/* increment, check for overflow and undo increment if so. */
shoaib_ahmed	0:791a779d6220	244	if (++(*histp) <= 0)
shoaib_ahmed	0:791a779d6220	245	(*histp)--;
shoaib_ahmed	0:791a779d6220	246	ptr += 3;
shoaib_ahmed	0:791a779d6220	247	}
shoaib_ahmed	0:791a779d6220	248	}
shoaib_ahmed	0:791a779d6220	249	}
shoaib_ahmed	0:791a779d6220	250
shoaib_ahmed	0:791a779d6220	251
shoaib_ahmed	0:791a779d6220	252	/*
shoaib_ahmed	0:791a779d6220	253	* Next we have the really interesting routines: selection of a colormap
shoaib_ahmed	0:791a779d6220	254	* given the completed histogram.
shoaib_ahmed	0:791a779d6220	255	* These routines work with a list of "boxes", each representing a rectangular
shoaib_ahmed	0:791a779d6220	256	* subset of the input color space (to histogram precision).
shoaib_ahmed	0:791a779d6220	257	*/
shoaib_ahmed	0:791a779d6220	258
shoaib_ahmed	0:791a779d6220	259	typedef struct {
shoaib_ahmed	0:791a779d6220	260	/* The bounds of the box (inclusive); expressed as histogram indexes */
shoaib_ahmed	0:791a779d6220	261	int c0min, c0max;
shoaib_ahmed	0:791a779d6220	262	int c1min, c1max;
shoaib_ahmed	0:791a779d6220	263	int c2min, c2max;
shoaib_ahmed	0:791a779d6220	264	/* The volume (actually 2-norm) of the box */
shoaib_ahmed	0:791a779d6220	265	INT32 volume;
shoaib_ahmed	0:791a779d6220	266	/* The number of nonzero histogram cells within this box */
shoaib_ahmed	0:791a779d6220	267	long colorcount;
shoaib_ahmed	0:791a779d6220	268	} box;
shoaib_ahmed	0:791a779d6220	269
shoaib_ahmed	0:791a779d6220	270	typedef box * boxptr;
shoaib_ahmed	0:791a779d6220	271
shoaib_ahmed	0:791a779d6220	272
shoaib_ahmed	0:791a779d6220	273	LOCAL(boxptr)
shoaib_ahmed	0:791a779d6220	274	find_biggest_color_pop (boxptr boxlist, int numboxes)
shoaib_ahmed	0:791a779d6220	275	/* Find the splittable box with the largest color population */
shoaib_ahmed	0:791a779d6220	276	/* Returns NULL if no splittable boxes remain */
shoaib_ahmed	0:791a779d6220	277	{
shoaib_ahmed	0:791a779d6220	278	register boxptr boxp;
shoaib_ahmed	0:791a779d6220	279	register int i;
shoaib_ahmed	0:791a779d6220	280	register long maxc = 0;
shoaib_ahmed	0:791a779d6220	281	boxptr which = NULL;
shoaib_ahmed	0:791a779d6220	282
shoaib_ahmed	0:791a779d6220	283	for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) {
shoaib_ahmed	0:791a779d6220	284	if (boxp->colorcount > maxc && boxp->volume > 0) {
shoaib_ahmed	0:791a779d6220	285	which = boxp;
shoaib_ahmed	0:791a779d6220	286	maxc = boxp->colorcount;
shoaib_ahmed	0:791a779d6220	287	}
shoaib_ahmed	0:791a779d6220	288	}
shoaib_ahmed	0:791a779d6220	289	return which;
shoaib_ahmed	0:791a779d6220	290	}
shoaib_ahmed	0:791a779d6220	291
shoaib_ahmed	0:791a779d6220	292
shoaib_ahmed	0:791a779d6220	293	LOCAL(boxptr)
shoaib_ahmed	0:791a779d6220	294	find_biggest_volume (boxptr boxlist, int numboxes)
shoaib_ahmed	0:791a779d6220	295	/* Find the splittable box with the largest (scaled) volume */
shoaib_ahmed	0:791a779d6220	296	/* Returns NULL if no splittable boxes remain */
shoaib_ahmed	0:791a779d6220	297	{
shoaib_ahmed	0:791a779d6220	298	register boxptr boxp;
shoaib_ahmed	0:791a779d6220	299	register int i;
shoaib_ahmed	0:791a779d6220	300	register INT32 maxv = 0;
shoaib_ahmed	0:791a779d6220	301	boxptr which = NULL;
shoaib_ahmed	0:791a779d6220	302
shoaib_ahmed	0:791a779d6220	303	for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) {
shoaib_ahmed	0:791a779d6220	304	if (boxp->volume > maxv) {
shoaib_ahmed	0:791a779d6220	305	which = boxp;
shoaib_ahmed	0:791a779d6220	306	maxv = boxp->volume;
shoaib_ahmed	0:791a779d6220	307	}
shoaib_ahmed	0:791a779d6220	308	}
shoaib_ahmed	0:791a779d6220	309	return which;
shoaib_ahmed	0:791a779d6220	310	}
shoaib_ahmed	0:791a779d6220	311
shoaib_ahmed	0:791a779d6220	312
shoaib_ahmed	0:791a779d6220	313	LOCAL(void)
shoaib_ahmed	0:791a779d6220	314	update_box (j_decompress_ptr cinfo, boxptr boxp)
shoaib_ahmed	0:791a779d6220	315	/* Shrink the min/max bounds of a box to enclose only nonzero elements, */
shoaib_ahmed	0:791a779d6220	316	/* and recompute its volume and population */
shoaib_ahmed	0:791a779d6220	317	{
shoaib_ahmed	0:791a779d6220	318	my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
shoaib_ahmed	0:791a779d6220	319	hist3d histogram = cquantize->histogram;
shoaib_ahmed	0:791a779d6220	320	histptr histp;
shoaib_ahmed	0:791a779d6220	321	int c0,c1,c2;
shoaib_ahmed	0:791a779d6220	322	int c0min,c0max,c1min,c1max,c2min,c2max;
shoaib_ahmed	0:791a779d6220	323	INT32 dist0,dist1,dist2;
shoaib_ahmed	0:791a779d6220	324	long ccount;
shoaib_ahmed	0:791a779d6220	325
shoaib_ahmed	0:791a779d6220	326	c0min = boxp->c0min; c0max = boxp->c0max;
shoaib_ahmed	0:791a779d6220	327	c1min = boxp->c1min; c1max = boxp->c1max;
shoaib_ahmed	0:791a779d6220	328	c2min = boxp->c2min; c2max = boxp->c2max;
shoaib_ahmed	0:791a779d6220	329
shoaib_ahmed	0:791a779d6220	330	if (c0max > c0min)
shoaib_ahmed	0:791a779d6220	331	for (c0 = c0min; c0 <= c0max; c0++)
shoaib_ahmed	0:791a779d6220	332	for (c1 = c1min; c1 <= c1max; c1++) {
shoaib_ahmed	0:791a779d6220	333	histp = & histogram[c0][c1][c2min];
shoaib_ahmed	0:791a779d6220	334	for (c2 = c2min; c2 <= c2max; c2++)
shoaib_ahmed	0:791a779d6220	335	if (*histp++ != 0) {
shoaib_ahmed	0:791a779d6220	336	boxp->c0min = c0min = c0;
shoaib_ahmed	0:791a779d6220	337	goto have_c0min;
shoaib_ahmed	0:791a779d6220	338	}
shoaib_ahmed	0:791a779d6220	339	}
shoaib_ahmed	0:791a779d6220	340	have_c0min:
shoaib_ahmed	0:791a779d6220	341	if (c0max > c0min)
shoaib_ahmed	0:791a779d6220	342	for (c0 = c0max; c0 >= c0min; c0--)
shoaib_ahmed	0:791a779d6220	343	for (c1 = c1min; c1 <= c1max; c1++) {
shoaib_ahmed	0:791a779d6220	344	histp = & histogram[c0][c1][c2min];
shoaib_ahmed	0:791a779d6220	345	for (c2 = c2min; c2 <= c2max; c2++)
shoaib_ahmed	0:791a779d6220	346	if (*histp++ != 0) {
shoaib_ahmed	0:791a779d6220	347	boxp->c0max = c0max = c0;
shoaib_ahmed	0:791a779d6220	348	goto have_c0max;
shoaib_ahmed	0:791a779d6220	349	}
shoaib_ahmed	0:791a779d6220	350	}
shoaib_ahmed	0:791a779d6220	351	have_c0max:
shoaib_ahmed	0:791a779d6220	352	if (c1max > c1min)
shoaib_ahmed	0:791a779d6220	353	for (c1 = c1min; c1 <= c1max; c1++)
shoaib_ahmed	0:791a779d6220	354	for (c0 = c0min; c0 <= c0max; c0++) {
shoaib_ahmed	0:791a779d6220	355	histp = & histogram[c0][c1][c2min];
shoaib_ahmed	0:791a779d6220	356	for (c2 = c2min; c2 <= c2max; c2++)
shoaib_ahmed	0:791a779d6220	357	if (*histp++ != 0) {
shoaib_ahmed	0:791a779d6220	358	boxp->c1min = c1min = c1;
shoaib_ahmed	0:791a779d6220	359	goto have_c1min;
shoaib_ahmed	0:791a779d6220	360	}
shoaib_ahmed	0:791a779d6220	361	}
shoaib_ahmed	0:791a779d6220	362	have_c1min:
shoaib_ahmed	0:791a779d6220	363	if (c1max > c1min)
shoaib_ahmed	0:791a779d6220	364	for (c1 = c1max; c1 >= c1min; c1--)
shoaib_ahmed	0:791a779d6220	365	for (c0 = c0min; c0 <= c0max; c0++) {
shoaib_ahmed	0:791a779d6220	366	histp = & histogram[c0][c1][c2min];
shoaib_ahmed	0:791a779d6220	367	for (c2 = c2min; c2 <= c2max; c2++)
shoaib_ahmed	0:791a779d6220	368	if (*histp++ != 0) {
shoaib_ahmed	0:791a779d6220	369	boxp->c1max = c1max = c1;
shoaib_ahmed	0:791a779d6220	370	goto have_c1max;
shoaib_ahmed	0:791a779d6220	371	}
shoaib_ahmed	0:791a779d6220	372	}
shoaib_ahmed	0:791a779d6220	373	have_c1max:
shoaib_ahmed	0:791a779d6220	374	if (c2max > c2min)
shoaib_ahmed	0:791a779d6220	375	for (c2 = c2min; c2 <= c2max; c2++)
shoaib_ahmed	0:791a779d6220	376	for (c0 = c0min; c0 <= c0max; c0++) {
shoaib_ahmed	0:791a779d6220	377	histp = & histogram[c0][c1min][c2];
shoaib_ahmed	0:791a779d6220	378	for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS)
shoaib_ahmed	0:791a779d6220	379	if (*histp != 0) {
shoaib_ahmed	0:791a779d6220	380	boxp->c2min = c2min = c2;
shoaib_ahmed	0:791a779d6220	381	goto have_c2min;
shoaib_ahmed	0:791a779d6220	382	}
shoaib_ahmed	0:791a779d6220	383	}
shoaib_ahmed	0:791a779d6220	384	have_c2min:
shoaib_ahmed	0:791a779d6220	385	if (c2max > c2min)
shoaib_ahmed	0:791a779d6220	386	for (c2 = c2max; c2 >= c2min; c2--)
shoaib_ahmed	0:791a779d6220	387	for (c0 = c0min; c0 <= c0max; c0++) {
shoaib_ahmed	0:791a779d6220	388	histp = & histogram[c0][c1min][c2];
shoaib_ahmed	0:791a779d6220	389	for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS)
shoaib_ahmed	0:791a779d6220	390	if (*histp != 0) {
shoaib_ahmed	0:791a779d6220	391	boxp->c2max = c2max = c2;
shoaib_ahmed	0:791a779d6220	392	goto have_c2max;
shoaib_ahmed	0:791a779d6220	393	}
shoaib_ahmed	0:791a779d6220	394	}
shoaib_ahmed	0:791a779d6220	395	have_c2max:
shoaib_ahmed	0:791a779d6220	396
shoaib_ahmed	0:791a779d6220	397	/* Update box volume.
shoaib_ahmed	0:791a779d6220	398	* We use 2-norm rather than real volume here; this biases the method
shoaib_ahmed	0:791a779d6220	399	* against making long narrow boxes, and it has the side benefit that
shoaib_ahmed	0:791a779d6220	400	* a box is splittable iff norm > 0.
shoaib_ahmed	0:791a779d6220	401	* Since the differences are expressed in histogram-cell units,
shoaib_ahmed	0:791a779d6220	402	* we have to shift back to JSAMPLE units to get consistent distances;
shoaib_ahmed	0:791a779d6220	403	* after which, we scale according to the selected distance scale factors.
shoaib_ahmed	0:791a779d6220	404	*/
shoaib_ahmed	0:791a779d6220	405	dist0 = ((c0max - c0min) << C0_SHIFT) * C0_SCALE;
shoaib_ahmed	0:791a779d6220	406	dist1 = ((c1max - c1min) << C1_SHIFT) * C1_SCALE;
shoaib_ahmed	0:791a779d6220	407	dist2 = ((c2max - c2min) << C2_SHIFT) * C2_SCALE;
shoaib_ahmed	0:791a779d6220	408	boxp->volume = dist0dist0 + dist1dist1 + dist2*dist2;
shoaib_ahmed	0:791a779d6220	409
shoaib_ahmed	0:791a779d6220	410	/* Now scan remaining volume of box and compute population */
shoaib_ahmed	0:791a779d6220	411	ccount = 0;
shoaib_ahmed	0:791a779d6220	412	for (c0 = c0min; c0 <= c0max; c0++)
shoaib_ahmed	0:791a779d6220	413	for (c1 = c1min; c1 <= c1max; c1++) {
shoaib_ahmed	0:791a779d6220	414	histp = & histogram[c0][c1][c2min];
shoaib_ahmed	0:791a779d6220	415	for (c2 = c2min; c2 <= c2max; c2++, histp++)
shoaib_ahmed	0:791a779d6220	416	if (*histp != 0) {
shoaib_ahmed	0:791a779d6220	417	ccount++;
shoaib_ahmed	0:791a779d6220	418	}
shoaib_ahmed	0:791a779d6220	419	}
shoaib_ahmed	0:791a779d6220	420	boxp->colorcount = ccount;
shoaib_ahmed	0:791a779d6220	421	}
shoaib_ahmed	0:791a779d6220	422
shoaib_ahmed	0:791a779d6220	423
shoaib_ahmed	0:791a779d6220	424	LOCAL(int)
shoaib_ahmed	0:791a779d6220	425	median_cut (j_decompress_ptr cinfo, boxptr boxlist, int numboxes,
shoaib_ahmed	0:791a779d6220	426	int desired_colors)
shoaib_ahmed	0:791a779d6220	427	/* Repeatedly select and split the largest box until we have enough boxes */
shoaib_ahmed	0:791a779d6220	428	{
shoaib_ahmed	0:791a779d6220	429	int n,lb;
shoaib_ahmed	0:791a779d6220	430	int c0,c1,c2,cmax;
shoaib_ahmed	0:791a779d6220	431	register boxptr b1,b2;
shoaib_ahmed	0:791a779d6220	432
shoaib_ahmed	0:791a779d6220	433	while (numboxes < desired_colors) {
shoaib_ahmed	0:791a779d6220	434	/* Select box to split.
shoaib_ahmed	0:791a779d6220	435	* Current algorithm: by population for first half, then by volume.
shoaib_ahmed	0:791a779d6220	436	*/
shoaib_ahmed	0:791a779d6220	437	if (numboxes*2 <= desired_colors) {
shoaib_ahmed	0:791a779d6220	438	b1 = find_biggest_color_pop(boxlist, numboxes);
shoaib_ahmed	0:791a779d6220	439	} else {
shoaib_ahmed	0:791a779d6220	440	b1 = find_biggest_volume(boxlist, numboxes);
shoaib_ahmed	0:791a779d6220	441	}
shoaib_ahmed	0:791a779d6220	442	if (b1 == NULL) /* no splittable boxes left! */
shoaib_ahmed	0:791a779d6220	443	break;
shoaib_ahmed	0:791a779d6220	444	b2 = &boxlist[numboxes]; /* where new box will go */
shoaib_ahmed	0:791a779d6220	445	/* Copy the color bounds to the new box. */
shoaib_ahmed	0:791a779d6220	446	b2->c0max = b1->c0max; b2->c1max = b1->c1max; b2->c2max = b1->c2max;
shoaib_ahmed	0:791a779d6220	447	b2->c0min = b1->c0min; b2->c1min = b1->c1min; b2->c2min = b1->c2min;
shoaib_ahmed	0:791a779d6220	448	/* Choose which axis to split the box on.
shoaib_ahmed	0:791a779d6220	449	* Current algorithm: longest scaled axis.
shoaib_ahmed	0:791a779d6220	450	* See notes in update_box about scaling distances.
shoaib_ahmed	0:791a779d6220	451	*/
shoaib_ahmed	0:791a779d6220	452	c0 = ((b1->c0max - b1->c0min) << C0_SHIFT) * C0_SCALE;
shoaib_ahmed	0:791a779d6220	453	c1 = ((b1->c1max - b1->c1min) << C1_SHIFT) * C1_SCALE;
shoaib_ahmed	0:791a779d6220	454	c2 = ((b1->c2max - b1->c2min) << C2_SHIFT) * C2_SCALE;
shoaib_ahmed	0:791a779d6220	455	/* We want to break any ties in favor of green, then red, blue last.
shoaib_ahmed	0:791a779d6220	456	* This code does the right thing for R,G,B or B,G,R color orders only.
shoaib_ahmed	0:791a779d6220	457	*/
shoaib_ahmed	0:791a779d6220	458	#if RGB_RED == 0
shoaib_ahmed	0:791a779d6220	459	cmax = c1; n = 1;
shoaib_ahmed	0:791a779d6220	460	if (c0 > cmax) { cmax = c0; n = 0; }
shoaib_ahmed	0:791a779d6220	461	if (c2 > cmax) { n = 2; }
shoaib_ahmed	0:791a779d6220	462	#else
shoaib_ahmed	0:791a779d6220	463	cmax = c1; n = 1;
shoaib_ahmed	0:791a779d6220	464	if (c2 > cmax) { cmax = c2; n = 2; }
shoaib_ahmed	0:791a779d6220	465	if (c0 > cmax) { n = 0; }
shoaib_ahmed	0:791a779d6220	466	#endif
shoaib_ahmed	0:791a779d6220	467	/* Choose split point along selected axis, and update box bounds.
shoaib_ahmed	0:791a779d6220	468	* Current algorithm: split at halfway point.
shoaib_ahmed	0:791a779d6220	469	* (Since the box has been shrunk to minimum volume,
shoaib_ahmed	0:791a779d6220	470	* any split will produce two nonempty subboxes.)
shoaib_ahmed	0:791a779d6220	471	* Note that lb value is max for lower box, so must be < old max.
shoaib_ahmed	0:791a779d6220	472	*/
shoaib_ahmed	0:791a779d6220	473	switch (n) {
shoaib_ahmed	0:791a779d6220	474	case 0:
shoaib_ahmed	0:791a779d6220	475	lb = (b1->c0max + b1->c0min) / 2;
shoaib_ahmed	0:791a779d6220	476	b1->c0max = lb;
shoaib_ahmed	0:791a779d6220	477	b2->c0min = lb+1;
shoaib_ahmed	0:791a779d6220	478	break;
shoaib_ahmed	0:791a779d6220	479	case 1:
shoaib_ahmed	0:791a779d6220	480	lb = (b1->c1max + b1->c1min) / 2;
shoaib_ahmed	0:791a779d6220	481	b1->c1max = lb;
shoaib_ahmed	0:791a779d6220	482	b2->c1min = lb+1;
shoaib_ahmed	0:791a779d6220	483	break;
shoaib_ahmed	0:791a779d6220	484	case 2:
shoaib_ahmed	0:791a779d6220	485	lb = (b1->c2max + b1->c2min) / 2;
shoaib_ahmed	0:791a779d6220	486	b1->c2max = lb;
shoaib_ahmed	0:791a779d6220	487	b2->c2min = lb+1;
shoaib_ahmed	0:791a779d6220	488	break;
shoaib_ahmed	0:791a779d6220	489	}
shoaib_ahmed	0:791a779d6220	490	/* Update stats for boxes */
shoaib_ahmed	0:791a779d6220	491	update_box(cinfo, b1);
shoaib_ahmed	0:791a779d6220	492	update_box(cinfo, b2);
shoaib_ahmed	0:791a779d6220	493	numboxes++;
shoaib_ahmed	0:791a779d6220	494	}
shoaib_ahmed	0:791a779d6220	495	return numboxes;
shoaib_ahmed	0:791a779d6220	496	}
shoaib_ahmed	0:791a779d6220	497
shoaib_ahmed	0:791a779d6220	498
shoaib_ahmed	0:791a779d6220	499	LOCAL(void)
shoaib_ahmed	0:791a779d6220	500	compute_color (j_decompress_ptr cinfo, boxptr boxp, int icolor)
shoaib_ahmed	0:791a779d6220	501	/* Compute representative color for a box, put it in colormap[icolor] */
shoaib_ahmed	0:791a779d6220	502	{
shoaib_ahmed	0:791a779d6220	503	/* Current algorithm: mean weighted by pixels (not colors) */
shoaib_ahmed	0:791a779d6220	504	/* Note it is important to get the rounding correct! */
shoaib_ahmed	0:791a779d6220	505	my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
shoaib_ahmed	0:791a779d6220	506	hist3d histogram = cquantize->histogram;
shoaib_ahmed	0:791a779d6220	507	histptr histp;
shoaib_ahmed	0:791a779d6220	508	int c0,c1,c2;
shoaib_ahmed	0:791a779d6220	509	int c0min,c0max,c1min,c1max,c2min,c2max;
shoaib_ahmed	0:791a779d6220	510	long count;
shoaib_ahmed	0:791a779d6220	511	long total = 0;
shoaib_ahmed	0:791a779d6220	512	long c0total = 0;
shoaib_ahmed	0:791a779d6220	513	long c1total = 0;
shoaib_ahmed	0:791a779d6220	514	long c2total = 0;
shoaib_ahmed	0:791a779d6220	515
shoaib_ahmed	0:791a779d6220	516	c0min = boxp->c0min; c0max = boxp->c0max;
shoaib_ahmed	0:791a779d6220	517	c1min = boxp->c1min; c1max = boxp->c1max;
shoaib_ahmed	0:791a779d6220	518	c2min = boxp->c2min; c2max = boxp->c2max;
shoaib_ahmed	0:791a779d6220	519
shoaib_ahmed	0:791a779d6220	520	for (c0 = c0min; c0 <= c0max; c0++)
shoaib_ahmed	0:791a779d6220	521	for (c1 = c1min; c1 <= c1max; c1++) {
shoaib_ahmed	0:791a779d6220	522	histp = & histogram[c0][c1][c2min];
shoaib_ahmed	0:791a779d6220	523	for (c2 = c2min; c2 <= c2max; c2++) {
shoaib_ahmed	0:791a779d6220	524	if ((count = *histp++) != 0) {
shoaib_ahmed	0:791a779d6220	525	total += count;
shoaib_ahmed	0:791a779d6220	526	c0total += ((c0 << C0_SHIFT) + ((1<<C0_SHIFT)>>1)) * count;
shoaib_ahmed	0:791a779d6220	527	c1total += ((c1 << C1_SHIFT) + ((1<<C1_SHIFT)>>1)) * count;
shoaib_ahmed	0:791a779d6220	528	c2total += ((c2 << C2_SHIFT) + ((1<<C2_SHIFT)>>1)) * count;
shoaib_ahmed	0:791a779d6220	529	}
shoaib_ahmed	0:791a779d6220	530	}
shoaib_ahmed	0:791a779d6220	531	}
shoaib_ahmed	0:791a779d6220	532
shoaib_ahmed	0:791a779d6220	533	cinfo->colormap[0][icolor] = (JSAMPLE) ((c0total + (total>>1)) / total);
shoaib_ahmed	0:791a779d6220	534	cinfo->colormap[1][icolor] = (JSAMPLE) ((c1total + (total>>1)) / total);
shoaib_ahmed	0:791a779d6220	535	cinfo->colormap[2][icolor] = (JSAMPLE) ((c2total + (total>>1)) / total);
shoaib_ahmed	0:791a779d6220	536	}
shoaib_ahmed	0:791a779d6220	537
shoaib_ahmed	0:791a779d6220	538
shoaib_ahmed	0:791a779d6220	539	LOCAL(void)
shoaib_ahmed	0:791a779d6220	540	select_colors (j_decompress_ptr cinfo, int desired_colors)
shoaib_ahmed	0:791a779d6220	541	/* Master routine for color selection */
shoaib_ahmed	0:791a779d6220	542	{
shoaib_ahmed	0:791a779d6220	543	boxptr boxlist;
shoaib_ahmed	0:791a779d6220	544	int numboxes;
shoaib_ahmed	0:791a779d6220	545	int i;
shoaib_ahmed	0:791a779d6220	546
shoaib_ahmed	0:791a779d6220	547	/* Allocate workspace for box list */
shoaib_ahmed	0:791a779d6220	548	boxlist = (boxptr) (*cinfo->mem->alloc_small)
shoaib_ahmed	0:791a779d6220	549	((j_common_ptr) cinfo, JPOOL_IMAGE, desired_colors * SIZEOF(box));
shoaib_ahmed	0:791a779d6220	550	/* Initialize one box containing whole space */
shoaib_ahmed	0:791a779d6220	551	numboxes = 1;
shoaib_ahmed	0:791a779d6220	552	boxlist[0].c0min = 0;
shoaib_ahmed	0:791a779d6220	553	boxlist[0].c0max = MAXJSAMPLE >> C0_SHIFT;
shoaib_ahmed	0:791a779d6220	554	boxlist[0].c1min = 0;
shoaib_ahmed	0:791a779d6220	555	boxlist[0].c1max = MAXJSAMPLE >> C1_SHIFT;
shoaib_ahmed	0:791a779d6220	556	boxlist[0].c2min = 0;
shoaib_ahmed	0:791a779d6220	557	boxlist[0].c2max = MAXJSAMPLE >> C2_SHIFT;
shoaib_ahmed	0:791a779d6220	558	/* Shrink it to actually-used volume and set its statistics */
shoaib_ahmed	0:791a779d6220	559	update_box(cinfo, & boxlist[0]);
shoaib_ahmed	0:791a779d6220	560	/* Perform median-cut to produce final box list */
shoaib_ahmed	0:791a779d6220	561	numboxes = median_cut(cinfo, boxlist, numboxes, desired_colors);
shoaib_ahmed	0:791a779d6220	562	/* Compute the representative color for each box, fill colormap */
shoaib_ahmed	0:791a779d6220	563	for (i = 0; i < numboxes; i++)
shoaib_ahmed	0:791a779d6220	564	compute_color(cinfo, & boxlist[i], i);
shoaib_ahmed	0:791a779d6220	565	cinfo->actual_number_of_colors = numboxes;
shoaib_ahmed	0:791a779d6220	566	TRACEMS1(cinfo, 1, JTRC_QUANT_SELECTED, numboxes);
shoaib_ahmed	0:791a779d6220	567	}
shoaib_ahmed	0:791a779d6220	568
shoaib_ahmed	0:791a779d6220	569
shoaib_ahmed	0:791a779d6220	570	/*
shoaib_ahmed	0:791a779d6220	571	* These routines are concerned with the time-critical task of mapping input
shoaib_ahmed	0:791a779d6220	572	* colors to the nearest color in the selected colormap.
shoaib_ahmed	0:791a779d6220	573	*
shoaib_ahmed	0:791a779d6220	574	* We re-use the histogram space as an "inverse color map", essentially a
shoaib_ahmed	0:791a779d6220	575	* cache for the results of nearest-color searches. All colors within a
shoaib_ahmed	0:791a779d6220	576	* histogram cell will be mapped to the same colormap entry, namely the one
shoaib_ahmed	0:791a779d6220	577	* closest to the cell's center. This may not be quite the closest entry to
shoaib_ahmed	0:791a779d6220	578	* the actual input color, but it's almost as good. A zero in the cache
shoaib_ahmed	0:791a779d6220	579	* indicates we haven't found the nearest color for that cell yet; the array
shoaib_ahmed	0:791a779d6220	580	* is cleared to zeroes before starting the mapping pass. When we find the
shoaib_ahmed	0:791a779d6220	581	* nearest color for a cell, its colormap index plus one is recorded in the
shoaib_ahmed	0:791a779d6220	582	* cache for future use. The pass2 scanning routines call fill_inverse_cmap
shoaib_ahmed	0:791a779d6220	583	* when they need to use an unfilled entry in the cache.
shoaib_ahmed	0:791a779d6220	584	*
shoaib_ahmed	0:791a779d6220	585	* Our method of efficiently finding nearest colors is based on the "locally
shoaib_ahmed	0:791a779d6220	586	* sorted search" idea described by Heckbert and on the incremental distance
shoaib_ahmed	0:791a779d6220	587	* calculation described by Spencer W. Thomas in chapter III.1 of Graphics
shoaib_ahmed	0:791a779d6220	588	* Gems II (James Arvo, ed. Academic Press, 1991). Thomas points out that
shoaib_ahmed	0:791a779d6220	589	* the distances from a given colormap entry to each cell of the histogram can
shoaib_ahmed	0:791a779d6220	590	* be computed quickly using an incremental method: the differences between
shoaib_ahmed	0:791a779d6220	591	* distances to adjacent cells themselves differ by a constant. This allows a
shoaib_ahmed	0:791a779d6220	592	* fairly fast implementation of the "brute force" approach of computing the
shoaib_ahmed	0:791a779d6220	593	* distance from every colormap entry to every histogram cell. Unfortunately,
shoaib_ahmed	0:791a779d6220	594	* it needs a work array to hold the best-distance-so-far for each histogram
shoaib_ahmed	0:791a779d6220	595	* cell (because the inner loop has to be over cells, not colormap entries).
shoaib_ahmed	0:791a779d6220	596	* The work array elements have to be INT32s, so the work array would need
shoaib_ahmed	0:791a779d6220	597	* 256Kb at our recommended precision. This is not feasible in DOS machines.
shoaib_ahmed	0:791a779d6220	598	*
shoaib_ahmed	0:791a779d6220	599	* To get around these problems, we apply Thomas' method to compute the
shoaib_ahmed	0:791a779d6220	600	* nearest colors for only the cells within a small subbox of the histogram.
shoaib_ahmed	0:791a779d6220	601	* The work array need be only as big as the subbox, so the memory usage
shoaib_ahmed	0:791a779d6220	602	* problem is solved. Furthermore, we need not fill subboxes that are never
shoaib_ahmed	0:791a779d6220	603	* referenced in pass2; many images use only part of the color gamut, so a
shoaib_ahmed	0:791a779d6220	604	* fair amount of work is saved. An additional advantage of this
shoaib_ahmed	0:791a779d6220	605	* approach is that we can apply Heckbert's locality criterion to quickly
shoaib_ahmed	0:791a779d6220	606	* eliminate colormap entries that are far away from the subbox; typically
shoaib_ahmed	0:791a779d6220	607	* three-fourths of the colormap entries are rejected by Heckbert's criterion,
shoaib_ahmed	0:791a779d6220	608	* and we need not compute their distances to individual cells in the subbox.
shoaib_ahmed	0:791a779d6220	609	* The speed of this approach is heavily influenced by the subbox size: too
shoaib_ahmed	0:791a779d6220	610	* small means too much overhead, too big loses because Heckbert's criterion
shoaib_ahmed	0:791a779d6220	611	* can't eliminate as many colormap entries. Empirically the best subbox
shoaib_ahmed	0:791a779d6220	612	* size seems to be about 1/512th of the histogram (1/8th in each direction).
shoaib_ahmed	0:791a779d6220	613	*
shoaib_ahmed	0:791a779d6220	614	* Thomas' article also describes a refined method which is asymptotically
shoaib_ahmed	0:791a779d6220	615	* faster than the brute-force method, but it is also far more complex and
shoaib_ahmed	0:791a779d6220	616	* cannot efficiently be applied to small subboxes. It is therefore not
shoaib_ahmed	0:791a779d6220	617	* useful for programs intended to be portable to DOS machines. On machines
shoaib_ahmed	0:791a779d6220	618	* with plenty of memory, filling the whole histogram in one shot with Thomas'
shoaib_ahmed	0:791a779d6220	619	* refined method might be faster than the present code --- but then again,
shoaib_ahmed	0:791a779d6220	620	* it might not be any faster, and it's certainly more complicated.
shoaib_ahmed	0:791a779d6220	621	*/
shoaib_ahmed	0:791a779d6220	622
shoaib_ahmed	0:791a779d6220	623
shoaib_ahmed	0:791a779d6220	624	/* log2(histogram cells in update box) for each axis; this can be adjusted */
shoaib_ahmed	0:791a779d6220	625	#define BOX_C0_LOG (HIST_C0_BITS-3)
shoaib_ahmed	0:791a779d6220	626	#define BOX_C1_LOG (HIST_C1_BITS-3)
shoaib_ahmed	0:791a779d6220	627	#define BOX_C2_LOG (HIST_C2_BITS-3)
shoaib_ahmed	0:791a779d6220	628
shoaib_ahmed	0:791a779d6220	629	#define BOX_C0_ELEMS (1<<BOX_C0_LOG) /* # of hist cells in update box */
shoaib_ahmed	0:791a779d6220	630	#define BOX_C1_ELEMS (1<<BOX_C1_LOG)
shoaib_ahmed	0:791a779d6220	631	#define BOX_C2_ELEMS (1<<BOX_C2_LOG)
shoaib_ahmed	0:791a779d6220	632
shoaib_ahmed	0:791a779d6220	633	#define BOX_C0_SHIFT (C0_SHIFT + BOX_C0_LOG)
shoaib_ahmed	0:791a779d6220	634	#define BOX_C1_SHIFT (C1_SHIFT + BOX_C1_LOG)
shoaib_ahmed	0:791a779d6220	635	#define BOX_C2_SHIFT (C2_SHIFT + BOX_C2_LOG)
shoaib_ahmed	0:791a779d6220	636
shoaib_ahmed	0:791a779d6220	637
shoaib_ahmed	0:791a779d6220	638	/*
shoaib_ahmed	0:791a779d6220	639	* The next three routines implement inverse colormap filling. They could
shoaib_ahmed	0:791a779d6220	640	* all be folded into one big routine, but splitting them up this way saves
shoaib_ahmed	0:791a779d6220	641	* some stack space (the mindist[] and bestdist[] arrays need not coexist)
shoaib_ahmed	0:791a779d6220	642	* and may allow some compilers to produce better code by registerizing more
shoaib_ahmed	0:791a779d6220	643	* inner-loop variables.
shoaib_ahmed	0:791a779d6220	644	*/
shoaib_ahmed	0:791a779d6220	645
shoaib_ahmed	0:791a779d6220	646	LOCAL(int)
shoaib_ahmed	0:791a779d6220	647	find_nearby_colors (j_decompress_ptr cinfo, int minc0, int minc1, int minc2,
shoaib_ahmed	0:791a779d6220	648	JSAMPLE colorlist[])
shoaib_ahmed	0:791a779d6220	649	/* Locate the colormap entries close enough to an update box to be candidates
shoaib_ahmed	0:791a779d6220	650	* for the nearest entry to some cell(s) in the update box. The update box
shoaib_ahmed	0:791a779d6220	651	* is specified by the center coordinates of its first cell. The number of
shoaib_ahmed	0:791a779d6220	652	* candidate colormap entries is returned, and their colormap indexes are
shoaib_ahmed	0:791a779d6220	653	* placed in colorlist[].
shoaib_ahmed	0:791a779d6220	654	* This routine uses Heckbert's "locally sorted search" criterion to select
shoaib_ahmed	0:791a779d6220	655	* the colors that need further consideration.
shoaib_ahmed	0:791a779d6220	656	*/
shoaib_ahmed	0:791a779d6220	657	{
shoaib_ahmed	0:791a779d6220	658	int numcolors = cinfo->actual_number_of_colors;
shoaib_ahmed	0:791a779d6220	659	int maxc0, maxc1, maxc2;
shoaib_ahmed	0:791a779d6220	660	int centerc0, centerc1, centerc2;
shoaib_ahmed	0:791a779d6220	661	int i, x, ncolors;
shoaib_ahmed	0:791a779d6220	662	INT32 minmaxdist, min_dist, max_dist, tdist;
shoaib_ahmed	0:791a779d6220	663	INT32 mindist[MAXNUMCOLORS]; /* min distance to colormap entry i */
shoaib_ahmed	0:791a779d6220	664
shoaib_ahmed	0:791a779d6220	665	/* Compute true coordinates of update box's upper corner and center.
shoaib_ahmed	0:791a779d6220	666	* Actually we compute the coordinates of the center of the upper-corner
shoaib_ahmed	0:791a779d6220	667	* histogram cell, which are the upper bounds of the volume we care about.
shoaib_ahmed	0:791a779d6220	668	* Note that since ">>" rounds down, the "center" values may be closer to
shoaib_ahmed	0:791a779d6220	669	* min than to max; hence comparisons to them must be "<=", not "<".
shoaib_ahmed	0:791a779d6220	670	*/
shoaib_ahmed	0:791a779d6220	671	maxc0 = minc0 + ((1 << BOX_C0_SHIFT) - (1 << C0_SHIFT));
shoaib_ahmed	0:791a779d6220	672	centerc0 = (minc0 + maxc0) >> 1;
shoaib_ahmed	0:791a779d6220	673	maxc1 = minc1 + ((1 << BOX_C1_SHIFT) - (1 << C1_SHIFT));
shoaib_ahmed	0:791a779d6220	674	centerc1 = (minc1 + maxc1) >> 1;
shoaib_ahmed	0:791a779d6220	675	maxc2 = minc2 + ((1 << BOX_C2_SHIFT) - (1 << C2_SHIFT));
shoaib_ahmed	0:791a779d6220	676	centerc2 = (minc2 + maxc2) >> 1;
shoaib_ahmed	0:791a779d6220	677
shoaib_ahmed	0:791a779d6220	678	/* For each color in colormap, find:
shoaib_ahmed	0:791a779d6220	679	* 1. its minimum squared-distance to any point in the update box
shoaib_ahmed	0:791a779d6220	680	* (zero if color is within update box);
shoaib_ahmed	0:791a779d6220	681	* 2. its maximum squared-distance to any point in the update box.
shoaib_ahmed	0:791a779d6220	682	* Both of these can be found by considering only the corners of the box.
shoaib_ahmed	0:791a779d6220	683	* We save the minimum distance for each color in mindist[];
shoaib_ahmed	0:791a779d6220	684	* only the smallest maximum distance is of interest.
shoaib_ahmed	0:791a779d6220	685	*/
shoaib_ahmed	0:791a779d6220	686	minmaxdist = 0x7FFFFFFFL;
shoaib_ahmed	0:791a779d6220	687
shoaib_ahmed	0:791a779d6220	688	for (i = 0; i < numcolors; i++) {
shoaib_ahmed	0:791a779d6220	689	/* We compute the squared-c0-distance term, then add in the other two. */
shoaib_ahmed	0:791a779d6220	690	x = GETJSAMPLE(cinfo->colormap[0][i]);
shoaib_ahmed	0:791a779d6220	691	if (x < minc0) {
shoaib_ahmed	0:791a779d6220	692	tdist = (x - minc0) * C0_SCALE;
shoaib_ahmed	0:791a779d6220	693	min_dist = tdist*tdist;
shoaib_ahmed	0:791a779d6220	694	tdist = (x - maxc0) * C0_SCALE;
shoaib_ahmed	0:791a779d6220	695	max_dist = tdist*tdist;
shoaib_ahmed	0:791a779d6220	696	} else if (x > maxc0) {
shoaib_ahmed	0:791a779d6220	697	tdist = (x - maxc0) * C0_SCALE;
shoaib_ahmed	0:791a779d6220	698	min_dist = tdist*tdist;
shoaib_ahmed	0:791a779d6220	699	tdist = (x - minc0) * C0_SCALE;
shoaib_ahmed	0:791a779d6220	700	max_dist = tdist*tdist;
shoaib_ahmed	0:791a779d6220	701	} else {
shoaib_ahmed	0:791a779d6220	702	/* within cell range so no contribution to min_dist */
shoaib_ahmed	0:791a779d6220	703	min_dist = 0;
shoaib_ahmed	0:791a779d6220	704	if (x <= centerc0) {
shoaib_ahmed	0:791a779d6220	705	tdist = (x - maxc0) * C0_SCALE;
shoaib_ahmed	0:791a779d6220	706	max_dist = tdist*tdist;
shoaib_ahmed	0:791a779d6220	707	} else {
shoaib_ahmed	0:791a779d6220	708	tdist = (x - minc0) * C0_SCALE;
shoaib_ahmed	0:791a779d6220	709	max_dist = tdist*tdist;
shoaib_ahmed	0:791a779d6220	710	}
shoaib_ahmed	0:791a779d6220	711	}
shoaib_ahmed	0:791a779d6220	712
shoaib_ahmed	0:791a779d6220	713	x = GETJSAMPLE(cinfo->colormap[1][i]);
shoaib_ahmed	0:791a779d6220	714	if (x < minc1) {
shoaib_ahmed	0:791a779d6220	715	tdist = (x - minc1) * C1_SCALE;
shoaib_ahmed	0:791a779d6220	716	min_dist += tdist*tdist;
shoaib_ahmed	0:791a779d6220	717	tdist = (x - maxc1) * C1_SCALE;
shoaib_ahmed	0:791a779d6220	718	max_dist += tdist*tdist;
shoaib_ahmed	0:791a779d6220	719	} else if (x > maxc1) {
shoaib_ahmed	0:791a779d6220	720	tdist = (x - maxc1) * C1_SCALE;
shoaib_ahmed	0:791a779d6220	721	min_dist += tdist*tdist;
shoaib_ahmed	0:791a779d6220	722	tdist = (x - minc1) * C1_SCALE;
shoaib_ahmed	0:791a779d6220	723	max_dist += tdist*tdist;
shoaib_ahmed	0:791a779d6220	724	} else {
shoaib_ahmed	0:791a779d6220	725	/* within cell range so no contribution to min_dist */
shoaib_ahmed	0:791a779d6220	726	if (x <= centerc1) {
shoaib_ahmed	0:791a779d6220	727	tdist = (x - maxc1) * C1_SCALE;
shoaib_ahmed	0:791a779d6220	728	max_dist += tdist*tdist;
shoaib_ahmed	0:791a779d6220	729	} else {
shoaib_ahmed	0:791a779d6220	730	tdist = (x - minc1) * C1_SCALE;
shoaib_ahmed	0:791a779d6220	731	max_dist += tdist*tdist;
shoaib_ahmed	0:791a779d6220	732	}
shoaib_ahmed	0:791a779d6220	733	}
shoaib_ahmed	0:791a779d6220	734
shoaib_ahmed	0:791a779d6220	735	x = GETJSAMPLE(cinfo->colormap[2][i]);
shoaib_ahmed	0:791a779d6220	736	if (x < minc2) {
shoaib_ahmed	0:791a779d6220	737	tdist = (x - minc2) * C2_SCALE;
shoaib_ahmed	0:791a779d6220	738	min_dist += tdist*tdist;
shoaib_ahmed	0:791a779d6220	739	tdist = (x - maxc2) * C2_SCALE;
shoaib_ahmed	0:791a779d6220	740	max_dist += tdist*tdist;
shoaib_ahmed	0:791a779d6220	741	} else if (x > maxc2) {
shoaib_ahmed	0:791a779d6220	742	tdist = (x - maxc2) * C2_SCALE;
shoaib_ahmed	0:791a779d6220	743	min_dist += tdist*tdist;
shoaib_ahmed	0:791a779d6220	744	tdist = (x - minc2) * C2_SCALE;
shoaib_ahmed	0:791a779d6220	745	max_dist += tdist*tdist;
shoaib_ahmed	0:791a779d6220	746	} else {
shoaib_ahmed	0:791a779d6220	747	/* within cell range so no contribution to min_dist */
shoaib_ahmed	0:791a779d6220	748	if (x <= centerc2) {
shoaib_ahmed	0:791a779d6220	749	tdist = (x - maxc2) * C2_SCALE;
shoaib_ahmed	0:791a779d6220	750	max_dist += tdist*tdist;
shoaib_ahmed	0:791a779d6220	751	} else {
shoaib_ahmed	0:791a779d6220	752	tdist = (x - minc2) * C2_SCALE;
shoaib_ahmed	0:791a779d6220	753	max_dist += tdist*tdist;
shoaib_ahmed	0:791a779d6220	754	}
shoaib_ahmed	0:791a779d6220	755	}
shoaib_ahmed	0:791a779d6220	756
shoaib_ahmed	0:791a779d6220	757	mindist[i] = min_dist; /* save away the results */
shoaib_ahmed	0:791a779d6220	758	if (max_dist < minmaxdist)
shoaib_ahmed	0:791a779d6220	759	minmaxdist = max_dist;
shoaib_ahmed	0:791a779d6220	760	}
shoaib_ahmed	0:791a779d6220	761
shoaib_ahmed	0:791a779d6220	762	/* Now we know that no cell in the update box is more than minmaxdist
shoaib_ahmed	0:791a779d6220	763	* away from some colormap entry. Therefore, only colors that are
shoaib_ahmed	0:791a779d6220	764	* within minmaxdist of some part of the box need be considered.
shoaib_ahmed	0:791a779d6220	765	*/
shoaib_ahmed	0:791a779d6220	766	ncolors = 0;
shoaib_ahmed	0:791a779d6220	767	for (i = 0; i < numcolors; i++) {
shoaib_ahmed	0:791a779d6220	768	if (mindist[i] <= minmaxdist)
shoaib_ahmed	0:791a779d6220	769	colorlist[ncolors++] = (JSAMPLE) i;
shoaib_ahmed	0:791a779d6220	770	}
shoaib_ahmed	0:791a779d6220	771	return ncolors;
shoaib_ahmed	0:791a779d6220	772	}
shoaib_ahmed	0:791a779d6220	773
shoaib_ahmed	0:791a779d6220	774
shoaib_ahmed	0:791a779d6220	775	LOCAL(void)
shoaib_ahmed	0:791a779d6220	776	find_best_colors (j_decompress_ptr cinfo, int minc0, int minc1, int minc2,
shoaib_ahmed	0:791a779d6220	777	int numcolors, JSAMPLE colorlist[], JSAMPLE bestcolor[])
shoaib_ahmed	0:791a779d6220	778	/* Find the closest colormap entry for each cell in the update box,
shoaib_ahmed	0:791a779d6220	779	* given the list of candidate colors prepared by find_nearby_colors.
shoaib_ahmed	0:791a779d6220	780	* Return the indexes of the closest entries in the bestcolor[] array.
shoaib_ahmed	0:791a779d6220	781	* This routine uses Thomas' incremental distance calculation method to
shoaib_ahmed	0:791a779d6220	782	* find the distance from a colormap entry to successive cells in the box.
shoaib_ahmed	0:791a779d6220	783	*/
shoaib_ahmed	0:791a779d6220	784	{
shoaib_ahmed	0:791a779d6220	785	int ic0, ic1, ic2;
shoaib_ahmed	0:791a779d6220	786	int i, icolor;
shoaib_ahmed	0:791a779d6220	787	register INT32 * bptr; /* pointer into bestdist[] array */
shoaib_ahmed	0:791a779d6220	788	JSAMPLE * cptr; /* pointer into bestcolor[] array */
shoaib_ahmed	0:791a779d6220	789	INT32 dist0, dist1; /* initial distance values */
shoaib_ahmed	0:791a779d6220	790	register INT32 dist2; /* current distance in inner loop */
shoaib_ahmed	0:791a779d6220	791	INT32 xx0, xx1; /* distance increments */
shoaib_ahmed	0:791a779d6220	792	register INT32 xx2;
shoaib_ahmed	0:791a779d6220	793	INT32 inc0, inc1, inc2; /* initial values for increments */
shoaib_ahmed	0:791a779d6220	794	/* This array holds the distance to the nearest-so-far color for each cell */
shoaib_ahmed	0:791a779d6220	795	INT32 bestdist[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS];
shoaib_ahmed	0:791a779d6220	796
shoaib_ahmed	0:791a779d6220	797	/* Initialize best-distance for each cell of the update box */
shoaib_ahmed	0:791a779d6220	798	bptr = bestdist;
shoaib_ahmed	0:791a779d6220	799	for (i = BOX_C0_ELEMSBOX_C1_ELEMSBOX_C2_ELEMS-1; i >= 0; i--)
shoaib_ahmed	0:791a779d6220	800	*bptr++ = 0x7FFFFFFFL;
shoaib_ahmed	0:791a779d6220	801
shoaib_ahmed	0:791a779d6220	802	/* For each color selected by find_nearby_colors,
shoaib_ahmed	0:791a779d6220	803	* compute its distance to the center of each cell in the box.
shoaib_ahmed	0:791a779d6220	804	* If that's less than best-so-far, update best distance and color number.
shoaib_ahmed	0:791a779d6220	805	*/
shoaib_ahmed	0:791a779d6220	806
shoaib_ahmed	0:791a779d6220	807	/* Nominal steps between cell centers ("x" in Thomas article) */
shoaib_ahmed	0:791a779d6220	808	#define STEP_C0 ((1 << C0_SHIFT) * C0_SCALE)
shoaib_ahmed	0:791a779d6220	809	#define STEP_C1 ((1 << C1_SHIFT) * C1_SCALE)
shoaib_ahmed	0:791a779d6220	810	#define STEP_C2 ((1 << C2_SHIFT) * C2_SCALE)
shoaib_ahmed	0:791a779d6220	811
shoaib_ahmed	0:791a779d6220	812	for (i = 0; i < numcolors; i++) {
shoaib_ahmed	0:791a779d6220	813	icolor = GETJSAMPLE(colorlist[i]);
shoaib_ahmed	0:791a779d6220	814	/* Compute (square of) distance from minc0/c1/c2 to this color */
shoaib_ahmed	0:791a779d6220	815	inc0 = (minc0 - GETJSAMPLE(cinfo->colormap[0][icolor])) * C0_SCALE;
shoaib_ahmed	0:791a779d6220	816	dist0 = inc0*inc0;
shoaib_ahmed	0:791a779d6220	817	inc1 = (minc1 - GETJSAMPLE(cinfo->colormap[1][icolor])) * C1_SCALE;
shoaib_ahmed	0:791a779d6220	818	dist0 += inc1*inc1;
shoaib_ahmed	0:791a779d6220	819	inc2 = (minc2 - GETJSAMPLE(cinfo->colormap[2][icolor])) * C2_SCALE;
shoaib_ahmed	0:791a779d6220	820	dist0 += inc2*inc2;
shoaib_ahmed	0:791a779d6220	821	/* Form the initial difference increments */
shoaib_ahmed	0:791a779d6220	822	inc0 = inc0 * (2 * STEP_C0) + STEP_C0 * STEP_C0;
shoaib_ahmed	0:791a779d6220	823	inc1 = inc1 * (2 * STEP_C1) + STEP_C1 * STEP_C1;
shoaib_ahmed	0:791a779d6220	824	inc2 = inc2 * (2 * STEP_C2) + STEP_C2 * STEP_C2;
shoaib_ahmed	0:791a779d6220	825	/* Now loop over all cells in box, updating distance per Thomas method */
shoaib_ahmed	0:791a779d6220	826	bptr = bestdist;
shoaib_ahmed	0:791a779d6220	827	cptr = bestcolor;
shoaib_ahmed	0:791a779d6220	828	xx0 = inc0;
shoaib_ahmed	0:791a779d6220	829	for (ic0 = BOX_C0_ELEMS-1; ic0 >= 0; ic0--) {
shoaib_ahmed	0:791a779d6220	830	dist1 = dist0;
shoaib_ahmed	0:791a779d6220	831	xx1 = inc1;
shoaib_ahmed	0:791a779d6220	832	for (ic1 = BOX_C1_ELEMS-1; ic1 >= 0; ic1--) {
shoaib_ahmed	0:791a779d6220	833	dist2 = dist1;
shoaib_ahmed	0:791a779d6220	834	xx2 = inc2;
shoaib_ahmed	0:791a779d6220	835	for (ic2 = BOX_C2_ELEMS-1; ic2 >= 0; ic2--) {
shoaib_ahmed	0:791a779d6220	836	if (dist2 < *bptr) {
shoaib_ahmed	0:791a779d6220	837	*bptr = dist2;
shoaib_ahmed	0:791a779d6220	838	*cptr = (JSAMPLE) icolor;
shoaib_ahmed	0:791a779d6220	839	}
shoaib_ahmed	0:791a779d6220	840	dist2 += xx2;
shoaib_ahmed	0:791a779d6220	841	xx2 += 2 * STEP_C2 * STEP_C2;
shoaib_ahmed	0:791a779d6220	842	bptr++;
shoaib_ahmed	0:791a779d6220	843	cptr++;
shoaib_ahmed	0:791a779d6220	844	}
shoaib_ahmed	0:791a779d6220	845	dist1 += xx1;
shoaib_ahmed	0:791a779d6220	846	xx1 += 2 * STEP_C1 * STEP_C1;
shoaib_ahmed	0:791a779d6220	847	}
shoaib_ahmed	0:791a779d6220	848	dist0 += xx0;
shoaib_ahmed	0:791a779d6220	849	xx0 += 2 * STEP_C0 * STEP_C0;
shoaib_ahmed	0:791a779d6220	850	}
shoaib_ahmed	0:791a779d6220	851	}
shoaib_ahmed	0:791a779d6220	852	}
shoaib_ahmed	0:791a779d6220	853
shoaib_ahmed	0:791a779d6220	854
shoaib_ahmed	0:791a779d6220	855	LOCAL(void)
shoaib_ahmed	0:791a779d6220	856	fill_inverse_cmap (j_decompress_ptr cinfo, int c0, int c1, int c2)
shoaib_ahmed	0:791a779d6220	857	/* Fill the inverse-colormap entries in the update box that contains */
shoaib_ahmed	0:791a779d6220	858	/* histogram cell c0/c1/c2. (Only that one cell MUST be filled, but */
shoaib_ahmed	0:791a779d6220	859	/* we can fill as many others as we wish.) */
shoaib_ahmed	0:791a779d6220	860	{
shoaib_ahmed	0:791a779d6220	861	my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
shoaib_ahmed	0:791a779d6220	862	hist3d histogram = cquantize->histogram;
shoaib_ahmed	0:791a779d6220	863	int minc0, minc1, minc2; /* lower left corner of update box */
shoaib_ahmed	0:791a779d6220	864	int ic0, ic1, ic2;
shoaib_ahmed	0:791a779d6220	865	register JSAMPLE * cptr; /* pointer into bestcolor[] array */
shoaib_ahmed	0:791a779d6220	866	register histptr cachep; /* pointer into main cache array */
shoaib_ahmed	0:791a779d6220	867	/* This array lists the candidate colormap indexes. */
shoaib_ahmed	0:791a779d6220	868	JSAMPLE colorlist[MAXNUMCOLORS];
shoaib_ahmed	0:791a779d6220	869	int numcolors; /* number of candidate colors */
shoaib_ahmed	0:791a779d6220	870	/* This array holds the actually closest colormap index for each cell. */
shoaib_ahmed	0:791a779d6220	871	JSAMPLE bestcolor[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS];
shoaib_ahmed	0:791a779d6220	872
shoaib_ahmed	0:791a779d6220	873	/* Convert cell coordinates to update box ID */
shoaib_ahmed	0:791a779d6220	874	c0 >>= BOX_C0_LOG;
shoaib_ahmed	0:791a779d6220	875	c1 >>= BOX_C1_LOG;
shoaib_ahmed	0:791a779d6220	876	c2 >>= BOX_C2_LOG;
shoaib_ahmed	0:791a779d6220	877
shoaib_ahmed	0:791a779d6220	878	/* Compute true coordinates of update box's origin corner.
shoaib_ahmed	0:791a779d6220	879	* Actually we compute the coordinates of the center of the corner
shoaib_ahmed	0:791a779d6220	880	* histogram cell, which are the lower bounds of the volume we care about.
shoaib_ahmed	0:791a779d6220	881	*/
shoaib_ahmed	0:791a779d6220	882	minc0 = (c0 << BOX_C0_SHIFT) + ((1 << C0_SHIFT) >> 1);
shoaib_ahmed	0:791a779d6220	883	minc1 = (c1 << BOX_C1_SHIFT) + ((1 << C1_SHIFT) >> 1);
shoaib_ahmed	0:791a779d6220	884	minc2 = (c2 << BOX_C2_SHIFT) + ((1 << C2_SHIFT) >> 1);
shoaib_ahmed	0:791a779d6220	885
shoaib_ahmed	0:791a779d6220	886	/* Determine which colormap entries are close enough to be candidates
shoaib_ahmed	0:791a779d6220	887	* for the nearest entry to some cell in the update box.
shoaib_ahmed	0:791a779d6220	888	*/
shoaib_ahmed	0:791a779d6220	889	numcolors = find_nearby_colors(cinfo, minc0, minc1, minc2, colorlist);
shoaib_ahmed	0:791a779d6220	890
shoaib_ahmed	0:791a779d6220	891	/* Determine the actually nearest colors. */
shoaib_ahmed	0:791a779d6220	892	find_best_colors(cinfo, minc0, minc1, minc2, numcolors, colorlist,
shoaib_ahmed	0:791a779d6220	893	bestcolor);
shoaib_ahmed	0:791a779d6220	894
shoaib_ahmed	0:791a779d6220	895	/* Save the best color numbers (plus 1) in the main cache array */
shoaib_ahmed	0:791a779d6220	896	c0 <<= BOX_C0_LOG; /* convert ID back to base cell indexes */
shoaib_ahmed	0:791a779d6220	897	c1 <<= BOX_C1_LOG;
shoaib_ahmed	0:791a779d6220	898	c2 <<= BOX_C2_LOG;
shoaib_ahmed	0:791a779d6220	899	cptr = bestcolor;
shoaib_ahmed	0:791a779d6220	900	for (ic0 = 0; ic0 < BOX_C0_ELEMS; ic0++) {
shoaib_ahmed	0:791a779d6220	901	for (ic1 = 0; ic1 < BOX_C1_ELEMS; ic1++) {
shoaib_ahmed	0:791a779d6220	902	cachep = & histogram[c0+ic0][c1+ic1][c2];
shoaib_ahmed	0:791a779d6220	903	for (ic2 = 0; ic2 < BOX_C2_ELEMS; ic2++) {
shoaib_ahmed	0:791a779d6220	904	cachep++ = (histcell) (GETJSAMPLE(cptr++) + 1);
shoaib_ahmed	0:791a779d6220	905	}
shoaib_ahmed	0:791a779d6220	906	}
shoaib_ahmed	0:791a779d6220	907	}
shoaib_ahmed	0:791a779d6220	908	}
shoaib_ahmed	0:791a779d6220	909
shoaib_ahmed	0:791a779d6220	910
shoaib_ahmed	0:791a779d6220	911	/*
shoaib_ahmed	0:791a779d6220	912	* Map some rows of pixels to the output colormapped representation.
shoaib_ahmed	0:791a779d6220	913	*/
shoaib_ahmed	0:791a779d6220	914
shoaib_ahmed	0:791a779d6220	915	METHODDEF(void)
shoaib_ahmed	0:791a779d6220	916	pass2_no_dither (j_decompress_ptr cinfo,
shoaib_ahmed	0:791a779d6220	917	JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows)
shoaib_ahmed	0:791a779d6220	918	/* This version performs no dithering */
shoaib_ahmed	0:791a779d6220	919	{
shoaib_ahmed	0:791a779d6220	920	my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
shoaib_ahmed	0:791a779d6220	921	hist3d histogram = cquantize->histogram;
shoaib_ahmed	0:791a779d6220	922	register JSAMPROW inptr, outptr;
shoaib_ahmed	0:791a779d6220	923	register histptr cachep;
shoaib_ahmed	0:791a779d6220	924	register int c0, c1, c2;
shoaib_ahmed	0:791a779d6220	925	int row;
shoaib_ahmed	0:791a779d6220	926	JDIMENSION col;
shoaib_ahmed	0:791a779d6220	927	JDIMENSION width = cinfo->output_width;
shoaib_ahmed	0:791a779d6220	928
shoaib_ahmed	0:791a779d6220	929	for (row = 0; row < num_rows; row++) {
shoaib_ahmed	0:791a779d6220	930	inptr = input_buf[row];
shoaib_ahmed	0:791a779d6220	931	outptr = output_buf[row];
shoaib_ahmed	0:791a779d6220	932	for (col = width; col > 0; col--) {
shoaib_ahmed	0:791a779d6220	933	/* get pixel value and index into the cache */
shoaib_ahmed	0:791a779d6220	934	c0 = GETJSAMPLE(*inptr++) >> C0_SHIFT;
shoaib_ahmed	0:791a779d6220	935	c1 = GETJSAMPLE(*inptr++) >> C1_SHIFT;
shoaib_ahmed	0:791a779d6220	936	c2 = GETJSAMPLE(*inptr++) >> C2_SHIFT;
shoaib_ahmed	0:791a779d6220	937	cachep = & histogram[c0][c1][c2];
shoaib_ahmed	0:791a779d6220	938	/* If we have not seen this color before, find nearest colormap entry */
shoaib_ahmed	0:791a779d6220	939	/* and update the cache */
shoaib_ahmed	0:791a779d6220	940	if (*cachep == 0)
shoaib_ahmed	0:791a779d6220	941	fill_inverse_cmap(cinfo, c0,c1,c2);
shoaib_ahmed	0:791a779d6220	942	/* Now emit the colormap index for this cell */
shoaib_ahmed	0:791a779d6220	943	outptr++ = (JSAMPLE) (cachep - 1);
shoaib_ahmed	0:791a779d6220	944	}
shoaib_ahmed	0:791a779d6220	945	}
shoaib_ahmed	0:791a779d6220	946	}
shoaib_ahmed	0:791a779d6220	947
shoaib_ahmed	0:791a779d6220	948
shoaib_ahmed	0:791a779d6220	949	METHODDEF(void)
shoaib_ahmed	0:791a779d6220	950	pass2_fs_dither (j_decompress_ptr cinfo,
shoaib_ahmed	0:791a779d6220	951	JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows)
shoaib_ahmed	0:791a779d6220	952	/* This version performs Floyd-Steinberg dithering */
shoaib_ahmed	0:791a779d6220	953	{
shoaib_ahmed	0:791a779d6220	954	my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
shoaib_ahmed	0:791a779d6220	955	hist3d histogram = cquantize->histogram;
shoaib_ahmed	0:791a779d6220	956	register LOCFSERROR cur0, cur1, cur2; /* current error or pixel value */
shoaib_ahmed	0:791a779d6220	957	LOCFSERROR belowerr0, belowerr1, belowerr2; /* error for pixel below cur */
shoaib_ahmed	0:791a779d6220	958	LOCFSERROR bpreverr0, bpreverr1, bpreverr2; /* error for below/prev col */
shoaib_ahmed	0:791a779d6220	959	register FSERRPTR errorptr; /* => fserrors[] at column before current */
shoaib_ahmed	0:791a779d6220	960	JSAMPROW inptr; /* => current input pixel */
shoaib_ahmed	0:791a779d6220	961	JSAMPROW outptr; /* => current output pixel */
shoaib_ahmed	0:791a779d6220	962	histptr cachep;
shoaib_ahmed	0:791a779d6220	963	int dir; /* +1 or -1 depending on direction */
shoaib_ahmed	0:791a779d6220	964	int dir3; /* 3dir, for advancing inptr & errorptr /
shoaib_ahmed	0:791a779d6220	965	int row;
shoaib_ahmed	0:791a779d6220	966	JDIMENSION col;
shoaib_ahmed	0:791a779d6220	967	JDIMENSION width = cinfo->output_width;
shoaib_ahmed	0:791a779d6220	968	JSAMPLE *range_limit = cinfo->sample_range_limit;
shoaib_ahmed	0:791a779d6220	969	int *error_limit = cquantize->error_limiter;
shoaib_ahmed	0:791a779d6220	970	JSAMPROW colormap0 = cinfo->colormap[0];
shoaib_ahmed	0:791a779d6220	971	JSAMPROW colormap1 = cinfo->colormap[1];
shoaib_ahmed	0:791a779d6220	972	JSAMPROW colormap2 = cinfo->colormap[2];
shoaib_ahmed	0:791a779d6220	973	SHIFT_TEMPS
shoaib_ahmed	0:791a779d6220	974
shoaib_ahmed	0:791a779d6220	975	for (row = 0; row < num_rows; row++) {
shoaib_ahmed	0:791a779d6220	976	inptr = input_buf[row];
shoaib_ahmed	0:791a779d6220	977	outptr = output_buf[row];
shoaib_ahmed	0:791a779d6220	978	if (cquantize->on_odd_row) {
shoaib_ahmed	0:791a779d6220	979	/* work right to left in this row */
shoaib_ahmed	0:791a779d6220	980	inptr += (width-1) * 3; /* so point to rightmost pixel */
shoaib_ahmed	0:791a779d6220	981	outptr += width-1;
shoaib_ahmed	0:791a779d6220	982	dir = -1;
shoaib_ahmed	0:791a779d6220	983	dir3 = -3;
shoaib_ahmed	0:791a779d6220	984	errorptr = cquantize->fserrors + (width+1)3; / => entry after last column */
shoaib_ahmed	0:791a779d6220	985	cquantize->on_odd_row = FALSE; /* flip for next time */
shoaib_ahmed	0:791a779d6220	986	} else {
shoaib_ahmed	0:791a779d6220	987	/* work left to right in this row */
shoaib_ahmed	0:791a779d6220	988	dir = 1;
shoaib_ahmed	0:791a779d6220	989	dir3 = 3;
shoaib_ahmed	0:791a779d6220	990	errorptr = cquantize->fserrors; /* => entry before first real column */
shoaib_ahmed	0:791a779d6220	991	cquantize->on_odd_row = TRUE; /* flip for next time */
shoaib_ahmed	0:791a779d6220	992	}
shoaib_ahmed	0:791a779d6220	993	/* Preset error values: no error propagated to first pixel from left */
shoaib_ahmed	0:791a779d6220	994	cur0 = cur1 = cur2 = 0;
shoaib_ahmed	0:791a779d6220	995	/* and no error propagated to row below yet */
shoaib_ahmed	0:791a779d6220	996	belowerr0 = belowerr1 = belowerr2 = 0;
shoaib_ahmed	0:791a779d6220	997	bpreverr0 = bpreverr1 = bpreverr2 = 0;
shoaib_ahmed	0:791a779d6220	998
shoaib_ahmed	0:791a779d6220	999	for (col = width; col > 0; col--) {
shoaib_ahmed	0:791a779d6220	1000	/* curN holds the error propagated from the previous pixel on the
shoaib_ahmed	0:791a779d6220	1001	* current line. Add the error propagated from the previous line
shoaib_ahmed	0:791a779d6220	1002	* to form the complete error correction term for this pixel, and
shoaib_ahmed	0:791a779d6220	1003	* round the error term (which is expressed * 16) to an integer.
shoaib_ahmed	0:791a779d6220	1004	* RIGHT_SHIFT rounds towards minus infinity, so adding 8 is correct
shoaib_ahmed	0:791a779d6220	1005	* for either sign of the error value.
shoaib_ahmed	0:791a779d6220	1006	* Note: errorptr points to previous column's array entry.
shoaib_ahmed	0:791a779d6220	1007	*/
shoaib_ahmed	0:791a779d6220	1008	cur0 = RIGHT_SHIFT(cur0 + errorptr[dir3+0] + 8, 4);
shoaib_ahmed	0:791a779d6220	1009	cur1 = RIGHT_SHIFT(cur1 + errorptr[dir3+1] + 8, 4);
shoaib_ahmed	0:791a779d6220	1010	cur2 = RIGHT_SHIFT(cur2 + errorptr[dir3+2] + 8, 4);
shoaib_ahmed	0:791a779d6220	1011	/* Limit the error using transfer function set by init_error_limit.
shoaib_ahmed	0:791a779d6220	1012	* See comments with init_error_limit for rationale.
shoaib_ahmed	0:791a779d6220	1013	*/
shoaib_ahmed	0:791a779d6220	1014	cur0 = error_limit[cur0];
shoaib_ahmed	0:791a779d6220	1015	cur1 = error_limit[cur1];
shoaib_ahmed	0:791a779d6220	1016	cur2 = error_limit[cur2];
shoaib_ahmed	0:791a779d6220	1017	/* Form pixel value + error, and range-limit to 0..MAXJSAMPLE.
shoaib_ahmed	0:791a779d6220	1018	* The maximum error is +- MAXJSAMPLE (or less with error limiting);
shoaib_ahmed	0:791a779d6220	1019	* this sets the required size of the range_limit array.
shoaib_ahmed	0:791a779d6220	1020	*/
shoaib_ahmed	0:791a779d6220	1021	cur0 += GETJSAMPLE(inptr[0]);
shoaib_ahmed	0:791a779d6220	1022	cur1 += GETJSAMPLE(inptr[1]);
shoaib_ahmed	0:791a779d6220	1023	cur2 += GETJSAMPLE(inptr[2]);
shoaib_ahmed	0:791a779d6220	1024	cur0 = GETJSAMPLE(range_limit[cur0]);
shoaib_ahmed	0:791a779d6220	1025	cur1 = GETJSAMPLE(range_limit[cur1]);
shoaib_ahmed	0:791a779d6220	1026	cur2 = GETJSAMPLE(range_limit[cur2]);
shoaib_ahmed	0:791a779d6220	1027	/* Index into the cache with adjusted pixel value */
shoaib_ahmed	0:791a779d6220	1028	cachep = & histogram[cur0>>C0_SHIFT][cur1>>C1_SHIFT][cur2>>C2_SHIFT];
shoaib_ahmed	0:791a779d6220	1029	/* If we have not seen this color before, find nearest colormap */
shoaib_ahmed	0:791a779d6220	1030	/* entry and update the cache */
shoaib_ahmed	0:791a779d6220	1031	if (*cachep == 0)
shoaib_ahmed	0:791a779d6220	1032	fill_inverse_cmap(cinfo, cur0>>C0_SHIFT,cur1>>C1_SHIFT,cur2>>C2_SHIFT);
shoaib_ahmed	0:791a779d6220	1033	/* Now emit the colormap index for this cell */
shoaib_ahmed	0:791a779d6220	1034	{ register int pixcode = *cachep - 1;
shoaib_ahmed	0:791a779d6220	1035	*outptr = (JSAMPLE) pixcode;
shoaib_ahmed	0:791a779d6220	1036	/* Compute representation error for this pixel */
shoaib_ahmed	0:791a779d6220	1037	cur0 -= GETJSAMPLE(colormap0[pixcode]);
shoaib_ahmed	0:791a779d6220	1038	cur1 -= GETJSAMPLE(colormap1[pixcode]);
shoaib_ahmed	0:791a779d6220	1039	cur2 -= GETJSAMPLE(colormap2[pixcode]);
shoaib_ahmed	0:791a779d6220	1040	}
shoaib_ahmed	0:791a779d6220	1041	/* Compute error fractions to be propagated to adjacent pixels.
shoaib_ahmed	0:791a779d6220	1042	* Add these into the running sums, and simultaneously shift the
shoaib_ahmed	0:791a779d6220	1043	* next-line error sums left by 1 column.
shoaib_ahmed	0:791a779d6220	1044	*/
shoaib_ahmed	0:791a779d6220	1045	{ register LOCFSERROR bnexterr, delta;
shoaib_ahmed	0:791a779d6220	1046
shoaib_ahmed	0:791a779d6220	1047	bnexterr = cur0; /* Process component 0 */
shoaib_ahmed	0:791a779d6220	1048	delta = cur0 * 2;
shoaib_ahmed	0:791a779d6220	1049	cur0 += delta; /* form error * 3 */
shoaib_ahmed	0:791a779d6220	1050	errorptr[0] = (FSERROR) (bpreverr0 + cur0);
shoaib_ahmed	0:791a779d6220	1051	cur0 += delta; /* form error * 5 */
shoaib_ahmed	0:791a779d6220	1052	bpreverr0 = belowerr0 + cur0;
shoaib_ahmed	0:791a779d6220	1053	belowerr0 = bnexterr;
shoaib_ahmed	0:791a779d6220	1054	cur0 += delta; /* form error * 7 */
shoaib_ahmed	0:791a779d6220	1055	bnexterr = cur1; /* Process component 1 */
shoaib_ahmed	0:791a779d6220	1056	delta = cur1 * 2;
shoaib_ahmed	0:791a779d6220	1057	cur1 += delta; /* form error * 3 */
shoaib_ahmed	0:791a779d6220	1058	errorptr[1] = (FSERROR) (bpreverr1 + cur1);
shoaib_ahmed	0:791a779d6220	1059	cur1 += delta; /* form error * 5 */
shoaib_ahmed	0:791a779d6220	1060	bpreverr1 = belowerr1 + cur1;
shoaib_ahmed	0:791a779d6220	1061	belowerr1 = bnexterr;
shoaib_ahmed	0:791a779d6220	1062	cur1 += delta; /* form error * 7 */
shoaib_ahmed	0:791a779d6220	1063	bnexterr = cur2; /* Process component 2 */
shoaib_ahmed	0:791a779d6220	1064	delta = cur2 * 2;
shoaib_ahmed	0:791a779d6220	1065	cur2 += delta; /* form error * 3 */
shoaib_ahmed	0:791a779d6220	1066	errorptr[2] = (FSERROR) (bpreverr2 + cur2);
shoaib_ahmed	0:791a779d6220	1067	cur2 += delta; /* form error * 5 */
shoaib_ahmed	0:791a779d6220	1068	bpreverr2 = belowerr2 + cur2;
shoaib_ahmed	0:791a779d6220	1069	belowerr2 = bnexterr;
shoaib_ahmed	0:791a779d6220	1070	cur2 += delta; /* form error * 7 */
shoaib_ahmed	0:791a779d6220	1071	}
shoaib_ahmed	0:791a779d6220	1072	/* At this point curN contains the 7/16 error value to be propagated
shoaib_ahmed	0:791a779d6220	1073	* to the next pixel on the current line, and all the errors for the
shoaib_ahmed	0:791a779d6220	1074	* next line have been shifted over. We are therefore ready to move on.
shoaib_ahmed	0:791a779d6220	1075	*/
shoaib_ahmed	0:791a779d6220	1076	inptr += dir3; /* Advance pixel pointers to next column */
shoaib_ahmed	0:791a779d6220	1077	outptr += dir;
shoaib_ahmed	0:791a779d6220	1078	errorptr += dir3; /* advance errorptr to current column */
shoaib_ahmed	0:791a779d6220	1079	}
shoaib_ahmed	0:791a779d6220	1080	/* Post-loop cleanup: we must unload the final error values into the
shoaib_ahmed	0:791a779d6220	1081	* final fserrors[] entry. Note we need not unload belowerrN because
shoaib_ahmed	0:791a779d6220	1082	* it is for the dummy column before or after the actual array.
shoaib_ahmed	0:791a779d6220	1083	*/
shoaib_ahmed	0:791a779d6220	1084	errorptr[0] = (FSERROR) bpreverr0; /* unload prev errs into array */
shoaib_ahmed	0:791a779d6220	1085	errorptr[1] = (FSERROR) bpreverr1;
shoaib_ahmed	0:791a779d6220	1086	errorptr[2] = (FSERROR) bpreverr2;
shoaib_ahmed	0:791a779d6220	1087	}
shoaib_ahmed	0:791a779d6220	1088	}
shoaib_ahmed	0:791a779d6220	1089
shoaib_ahmed	0:791a779d6220	1090
shoaib_ahmed	0:791a779d6220	1091	/*
shoaib_ahmed	0:791a779d6220	1092	* Initialize the error-limiting transfer function (lookup table).
shoaib_ahmed	0:791a779d6220	1093	* The raw F-S error computation can potentially compute error values of up to
shoaib_ahmed	0:791a779d6220	1094	* +- MAXJSAMPLE. But we want the maximum correction applied to a pixel to be
shoaib_ahmed	0:791a779d6220	1095	* much less, otherwise obviously wrong pixels will be created. (Typical
shoaib_ahmed	0:791a779d6220	1096	* effects include weird fringes at color-area boundaries, isolated bright
shoaib_ahmed	0:791a779d6220	1097	* pixels in a dark area, etc.) The standard advice for avoiding this problem
shoaib_ahmed	0:791a779d6220	1098	* is to ensure that the "corners" of the color cube are allocated as output
shoaib_ahmed	0:791a779d6220	1099	* colors; then repeated errors in the same direction cannot cause cascading
shoaib_ahmed	0:791a779d6220	1100	* error buildup. However, that only prevents the error from getting
shoaib_ahmed	0:791a779d6220	1101	* completely out of hand; Aaron Giles reports that error limiting improves
shoaib_ahmed	0:791a779d6220	1102	* the results even with corner colors allocated.
shoaib_ahmed	0:791a779d6220	1103	* A simple clamping of the error values to about +- MAXJSAMPLE/8 works pretty
shoaib_ahmed	0:791a779d6220	1104	* well, but the smoother transfer function used below is even better. Thanks
shoaib_ahmed	0:791a779d6220	1105	* to Aaron Giles for this idea.
shoaib_ahmed	0:791a779d6220	1106	*/
shoaib_ahmed	0:791a779d6220	1107
shoaib_ahmed	0:791a779d6220	1108	LOCAL(void)
shoaib_ahmed	0:791a779d6220	1109	init_error_limit (j_decompress_ptr cinfo)
shoaib_ahmed	0:791a779d6220	1110	/* Allocate and fill in the error_limiter table */
shoaib_ahmed	0:791a779d6220	1111	{
shoaib_ahmed	0:791a779d6220	1112	my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
shoaib_ahmed	0:791a779d6220	1113	int * table;
shoaib_ahmed	0:791a779d6220	1114	int in, out;
shoaib_ahmed	0:791a779d6220	1115
shoaib_ahmed	0:791a779d6220	1116	table = (int ) (cinfo->mem->alloc_small)
shoaib_ahmed	0:791a779d6220	1117	((j_common_ptr) cinfo, JPOOL_IMAGE, (MAXJSAMPLE2+1) SIZEOF(int));
shoaib_ahmed	0:791a779d6220	1118	table += MAXJSAMPLE; /* so can index -MAXJSAMPLE .. +MAXJSAMPLE */
shoaib_ahmed	0:791a779d6220	1119	cquantize->error_limiter = table;
shoaib_ahmed	0:791a779d6220	1120
shoaib_ahmed	0:791a779d6220	1121	#define STEPSIZE ((MAXJSAMPLE+1)/16)
shoaib_ahmed	0:791a779d6220	1122	/* Map errors 1:1 up to +- MAXJSAMPLE/16 */
shoaib_ahmed	0:791a779d6220	1123	out = 0;
shoaib_ahmed	0:791a779d6220	1124	for (in = 0; in < STEPSIZE; in++, out++) {
shoaib_ahmed	0:791a779d6220	1125	table[in] = out; table[-in] = -out;
shoaib_ahmed	0:791a779d6220	1126	}
shoaib_ahmed	0:791a779d6220	1127	/* Map errors 1:2 up to +- 3MAXJSAMPLE/16 /
shoaib_ahmed	0:791a779d6220	1128	for (; in < STEPSIZE*3; in++, out += (in&1) ? 0 : 1) {
shoaib_ahmed	0:791a779d6220	1129	table[in] = out; table[-in] = -out;
shoaib_ahmed	0:791a779d6220	1130	}
shoaib_ahmed	0:791a779d6220	1131	/* Clamp the rest to final out value (which is (MAXJSAMPLE+1)/8) */
shoaib_ahmed	0:791a779d6220	1132	for (; in <= MAXJSAMPLE; in++) {
shoaib_ahmed	0:791a779d6220	1133	table[in] = out; table[-in] = -out;
shoaib_ahmed	0:791a779d6220	1134	}
shoaib_ahmed	0:791a779d6220	1135	#undef STEPSIZE
shoaib_ahmed	0:791a779d6220	1136	}
shoaib_ahmed	0:791a779d6220	1137
shoaib_ahmed	0:791a779d6220	1138
shoaib_ahmed	0:791a779d6220	1139	/*
shoaib_ahmed	0:791a779d6220	1140	* Finish up at the end of each pass.
shoaib_ahmed	0:791a779d6220	1141	*/
shoaib_ahmed	0:791a779d6220	1142
shoaib_ahmed	0:791a779d6220	1143	METHODDEF(void)
shoaib_ahmed	0:791a779d6220	1144	finish_pass1 (j_decompress_ptr cinfo)
shoaib_ahmed	0:791a779d6220	1145	{
shoaib_ahmed	0:791a779d6220	1146	my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
shoaib_ahmed	0:791a779d6220	1147
shoaib_ahmed	0:791a779d6220	1148	/* Select the representative colors and fill in cinfo->colormap */
shoaib_ahmed	0:791a779d6220	1149	cinfo->colormap = cquantize->sv_colormap;
shoaib_ahmed	0:791a779d6220	1150	select_colors(cinfo, cquantize->desired);
shoaib_ahmed	0:791a779d6220	1151	/* Force next pass to zero the color index table */
shoaib_ahmed	0:791a779d6220	1152	cquantize->needs_zeroed = TRUE;
shoaib_ahmed	0:791a779d6220	1153	}
shoaib_ahmed	0:791a779d6220	1154
shoaib_ahmed	0:791a779d6220	1155
shoaib_ahmed	0:791a779d6220	1156	METHODDEF(void)
shoaib_ahmed	0:791a779d6220	1157	finish_pass2 (j_decompress_ptr cinfo)
shoaib_ahmed	0:791a779d6220	1158	{
shoaib_ahmed	0:791a779d6220	1159	/* no work */
shoaib_ahmed	0:791a779d6220	1160	}
shoaib_ahmed	0:791a779d6220	1161
shoaib_ahmed	0:791a779d6220	1162
shoaib_ahmed	0:791a779d6220	1163	/*
shoaib_ahmed	0:791a779d6220	1164	* Initialize for each processing pass.
shoaib_ahmed	0:791a779d6220	1165	*/
shoaib_ahmed	0:791a779d6220	1166
shoaib_ahmed	0:791a779d6220	1167	METHODDEF(void)
shoaib_ahmed	0:791a779d6220	1168	start_pass_2_quant (j_decompress_ptr cinfo, boolean is_pre_scan)
shoaib_ahmed	0:791a779d6220	1169	{
shoaib_ahmed	0:791a779d6220	1170	my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
shoaib_ahmed	0:791a779d6220	1171	hist3d histogram = cquantize->histogram;
shoaib_ahmed	0:791a779d6220	1172	int i;
shoaib_ahmed	0:791a779d6220	1173
shoaib_ahmed	0:791a779d6220	1174	/* Only F-S dithering or no dithering is supported. */
shoaib_ahmed	0:791a779d6220	1175	/* If user asks for ordered dither, give him F-S. */
shoaib_ahmed	0:791a779d6220	1176	if (cinfo->dither_mode != JDITHER_NONE)
shoaib_ahmed	0:791a779d6220	1177	cinfo->dither_mode = JDITHER_FS;
shoaib_ahmed	0:791a779d6220	1178
shoaib_ahmed	0:791a779d6220	1179	if (is_pre_scan) {
shoaib_ahmed	0:791a779d6220	1180	/* Set up method pointers */
shoaib_ahmed	0:791a779d6220	1181	cquantize->pub.color_quantize = prescan_quantize;
shoaib_ahmed	0:791a779d6220	1182	cquantize->pub.finish_pass = finish_pass1;
shoaib_ahmed	0:791a779d6220	1183	cquantize->needs_zeroed = TRUE; /* Always zero histogram */
shoaib_ahmed	0:791a779d6220	1184	} else {
shoaib_ahmed	0:791a779d6220	1185	/* Set up method pointers */
shoaib_ahmed	0:791a779d6220	1186	if (cinfo->dither_mode == JDITHER_FS)
shoaib_ahmed	0:791a779d6220	1187	cquantize->pub.color_quantize = pass2_fs_dither;
shoaib_ahmed	0:791a779d6220	1188	else
shoaib_ahmed	0:791a779d6220	1189	cquantize->pub.color_quantize = pass2_no_dither;
shoaib_ahmed	0:791a779d6220	1190	cquantize->pub.finish_pass = finish_pass2;
shoaib_ahmed	0:791a779d6220	1191
shoaib_ahmed	0:791a779d6220	1192	/* Make sure color count is acceptable */
shoaib_ahmed	0:791a779d6220	1193	i = cinfo->actual_number_of_colors;
shoaib_ahmed	0:791a779d6220	1194	if (i < 1)
shoaib_ahmed	0:791a779d6220	1195	ERREXIT1(cinfo, JERR_QUANT_FEW_COLORS, 1);
shoaib_ahmed	0:791a779d6220	1196	if (i > MAXNUMCOLORS)
shoaib_ahmed	0:791a779d6220	1197	ERREXIT1(cinfo, JERR_QUANT_MANY_COLORS, MAXNUMCOLORS);
shoaib_ahmed	0:791a779d6220	1198
shoaib_ahmed	0:791a779d6220	1199	if (cinfo->dither_mode == JDITHER_FS) {
shoaib_ahmed	0:791a779d6220	1200	size_t arraysize = (size_t) ((cinfo->output_width + 2) *
shoaib_ahmed	0:791a779d6220	1201	(3 * SIZEOF(FSERROR)));
shoaib_ahmed	0:791a779d6220	1202	/* Allocate Floyd-Steinberg workspace if we didn't already. */
shoaib_ahmed	0:791a779d6220	1203	if (cquantize->fserrors == NULL)
shoaib_ahmed	0:791a779d6220	1204	cquantize->fserrors = (FSERRPTR) (*cinfo->mem->alloc_large)
shoaib_ahmed	0:791a779d6220	1205	((j_common_ptr) cinfo, JPOOL_IMAGE, arraysize);
shoaib_ahmed	0:791a779d6220	1206	/* Initialize the propagated errors to zero. */
shoaib_ahmed	0:791a779d6220	1207	FMEMZERO((void FAR *) cquantize->fserrors, arraysize);
shoaib_ahmed	0:791a779d6220	1208	/* Make the error-limit table if we didn't already. */
shoaib_ahmed	0:791a779d6220	1209	if (cquantize->error_limiter == NULL)
shoaib_ahmed	0:791a779d6220	1210	init_error_limit(cinfo);
shoaib_ahmed	0:791a779d6220	1211	cquantize->on_odd_row = FALSE;
shoaib_ahmed	0:791a779d6220	1212	}
shoaib_ahmed	0:791a779d6220	1213
shoaib_ahmed	0:791a779d6220	1214	}
shoaib_ahmed	0:791a779d6220	1215	/* Zero the histogram or inverse color map, if necessary */
shoaib_ahmed	0:791a779d6220	1216	if (cquantize->needs_zeroed) {
shoaib_ahmed	0:791a779d6220	1217	for (i = 0; i < HIST_C0_ELEMS; i++) {
shoaib_ahmed	0:791a779d6220	1218	FMEMZERO((void FAR *) histogram[i],
shoaib_ahmed	0:791a779d6220	1219	HIST_C1_ELEMSHIST_C2_ELEMS SIZEOF(histcell));
shoaib_ahmed	0:791a779d6220	1220	}
shoaib_ahmed	0:791a779d6220	1221	cquantize->needs_zeroed = FALSE;
shoaib_ahmed	0:791a779d6220	1222	}
shoaib_ahmed	0:791a779d6220	1223	}
shoaib_ahmed	0:791a779d6220	1224
shoaib_ahmed	0:791a779d6220	1225
shoaib_ahmed	0:791a779d6220	1226	/*
shoaib_ahmed	0:791a779d6220	1227	* Switch to a new external colormap between output passes.
shoaib_ahmed	0:791a779d6220	1228	*/
shoaib_ahmed	0:791a779d6220	1229
shoaib_ahmed	0:791a779d6220	1230	METHODDEF(void)
shoaib_ahmed	0:791a779d6220	1231	new_color_map_2_quant (j_decompress_ptr cinfo)
shoaib_ahmed	0:791a779d6220	1232	{
shoaib_ahmed	0:791a779d6220	1233	my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
shoaib_ahmed	0:791a779d6220	1234
shoaib_ahmed	0:791a779d6220	1235	/* Reset the inverse color map */
shoaib_ahmed	0:791a779d6220	1236	cquantize->needs_zeroed = TRUE;
shoaib_ahmed	0:791a779d6220	1237	}
shoaib_ahmed	0:791a779d6220	1238
shoaib_ahmed	0:791a779d6220	1239
shoaib_ahmed	0:791a779d6220	1240	/*
shoaib_ahmed	0:791a779d6220	1241	* Module initialization routine for 2-pass color quantization.
shoaib_ahmed	0:791a779d6220	1242	*/
shoaib_ahmed	0:791a779d6220	1243
shoaib_ahmed	0:791a779d6220	1244	GLOBAL(void)
shoaib_ahmed	0:791a779d6220	1245	jinit_2pass_quantizer (j_decompress_ptr cinfo)
shoaib_ahmed	0:791a779d6220	1246	{
shoaib_ahmed	0:791a779d6220	1247	my_cquantize_ptr cquantize;
shoaib_ahmed	0:791a779d6220	1248	int i;
shoaib_ahmed	0:791a779d6220	1249
shoaib_ahmed	0:791a779d6220	1250	cquantize = (my_cquantize_ptr)
shoaib_ahmed	0:791a779d6220	1251	(*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
shoaib_ahmed	0:791a779d6220	1252	SIZEOF(my_cquantizer));
shoaib_ahmed	0:791a779d6220	1253	cinfo->cquantize = (struct jpeg_color_quantizer *) cquantize;
shoaib_ahmed	0:791a779d6220	1254	cquantize->pub.start_pass = start_pass_2_quant;
shoaib_ahmed	0:791a779d6220	1255	cquantize->pub.new_color_map = new_color_map_2_quant;
shoaib_ahmed	0:791a779d6220	1256	cquantize->fserrors = NULL; /* flag optional arrays not allocated */
shoaib_ahmed	0:791a779d6220	1257	cquantize->error_limiter = NULL;
shoaib_ahmed	0:791a779d6220	1258
shoaib_ahmed	0:791a779d6220	1259	/* Make sure jdmaster didn't give me a case I can't handle */
shoaib_ahmed	0:791a779d6220	1260	if (cinfo->out_color_components != 3)
shoaib_ahmed	0:791a779d6220	1261	ERREXIT(cinfo, JERR_NOTIMPL);
shoaib_ahmed	0:791a779d6220	1262
shoaib_ahmed	0:791a779d6220	1263	/* Allocate the histogram/inverse colormap storage */
shoaib_ahmed	0:791a779d6220	1264	cquantize->histogram = (hist3d) (*cinfo->mem->alloc_small)
shoaib_ahmed	0:791a779d6220	1265	((j_common_ptr) cinfo, JPOOL_IMAGE, HIST_C0_ELEMS * SIZEOF(hist2d));
shoaib_ahmed	0:791a779d6220	1266	for (i = 0; i < HIST_C0_ELEMS; i++) {
shoaib_ahmed	0:791a779d6220	1267	cquantize->histogram[i] = (hist2d) (*cinfo->mem->alloc_large)
shoaib_ahmed	0:791a779d6220	1268	((j_common_ptr) cinfo, JPOOL_IMAGE,
shoaib_ahmed	0:791a779d6220	1269	HIST_C1_ELEMSHIST_C2_ELEMS SIZEOF(histcell));
shoaib_ahmed	0:791a779d6220	1270	}
shoaib_ahmed	0:791a779d6220	1271	cquantize->needs_zeroed = TRUE; /* histogram is garbage now */
shoaib_ahmed	0:791a779d6220	1272
shoaib_ahmed	0:791a779d6220	1273	/* Allocate storage for the completed colormap, if required.
shoaib_ahmed	0:791a779d6220	1274	* We do this now since it is FAR storage and may affect
shoaib_ahmed	0:791a779d6220	1275	* the memory manager's space calculations.
shoaib_ahmed	0:791a779d6220	1276	*/
shoaib_ahmed	0:791a779d6220	1277	if (cinfo->enable_2pass_quant) {
shoaib_ahmed	0:791a779d6220	1278	/* Make sure color count is acceptable */
shoaib_ahmed	0:791a779d6220	1279	int desired = cinfo->desired_number_of_colors;
shoaib_ahmed	0:791a779d6220	1280	/* Lower bound on # of colors ... somewhat arbitrary as long as > 0 */
shoaib_ahmed	0:791a779d6220	1281	if (desired < 8)
shoaib_ahmed	0:791a779d6220	1282	ERREXIT1(cinfo, JERR_QUANT_FEW_COLORS, 8);
shoaib_ahmed	0:791a779d6220	1283	/* Make sure colormap indexes can be represented by JSAMPLEs */
shoaib_ahmed	0:791a779d6220	1284	if (desired > MAXNUMCOLORS)
shoaib_ahmed	0:791a779d6220	1285	ERREXIT1(cinfo, JERR_QUANT_MANY_COLORS, MAXNUMCOLORS);
shoaib_ahmed	0:791a779d6220	1286	cquantize->sv_colormap = (*cinfo->mem->alloc_sarray)
shoaib_ahmed	0:791a779d6220	1287	((j_common_ptr) cinfo,JPOOL_IMAGE, (JDIMENSION) desired, (JDIMENSION) 3);
shoaib_ahmed	0:791a779d6220	1288	cquantize->desired = desired;
shoaib_ahmed	0:791a779d6220	1289	} else
shoaib_ahmed	0:791a779d6220	1290	cquantize->sv_colormap = NULL;
shoaib_ahmed	0:791a779d6220	1291
shoaib_ahmed	0:791a779d6220	1292	/* Only F-S dithering or no dithering is supported. */
shoaib_ahmed	0:791a779d6220	1293	/* If user asks for ordered dither, give him F-S. */
shoaib_ahmed	0:791a779d6220	1294	if (cinfo->dither_mode != JDITHER_NONE)
shoaib_ahmed	0:791a779d6220	1295	cinfo->dither_mode = JDITHER_FS;
shoaib_ahmed	0:791a779d6220	1296
shoaib_ahmed	0:791a779d6220	1297	/* Allocate Floyd-Steinberg workspace if necessary.
shoaib_ahmed	0:791a779d6220	1298	* This isn't really needed until pass 2, but again it is FAR storage.
shoaib_ahmed	0:791a779d6220	1299	* Although we will cope with a later change in dither_mode,
shoaib_ahmed	0:791a779d6220	1300	* we do not promise to honor max_memory_to_use if dither_mode changes.
shoaib_ahmed	0:791a779d6220	1301	*/
shoaib_ahmed	0:791a779d6220	1302	if (cinfo->dither_mode == JDITHER_FS) {
shoaib_ahmed	0:791a779d6220	1303	cquantize->fserrors = (FSERRPTR) (*cinfo->mem->alloc_large)
shoaib_ahmed	0:791a779d6220	1304	((j_common_ptr) cinfo, JPOOL_IMAGE,
shoaib_ahmed	0:791a779d6220	1305	(size_t) ((cinfo->output_width + 2) * (3 * SIZEOF(FSERROR))));
shoaib_ahmed	0:791a779d6220	1306	/* Might as well create the error-limiting table too. */
shoaib_ahmed	0:791a779d6220	1307	init_error_limit(cinfo);
shoaib_ahmed	0:791a779d6220	1308	}
shoaib_ahmed	0:791a779d6220	1309	}
shoaib_ahmed	0:791a779d6220	1310
shoaib_ahmed	0:791a779d6220	1311	#endif /* QUANT_2PASS_SUPPORTED */

Repository toolbox

Export to desktop IDE

Build repository

Repository details

Type:	Program
Mbed OS support:	Mbed 2 deprecated
Created:	31 Jul 2017
Imports:	1
Forks:	0
Commits:	1
Dependents:	0
Dependencies:	7
Followers:	1

includes/jquant2.c@0:791a779d6220, 2017-07-31 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning