jquant1.c 32 KB

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