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