jquant2.c 48 KB

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