Commit | Line | Data |
---|---|---|
0c52bae1 WJ |
1 | /* Copyright (C) 1989, 1992 Aladdin Enterprises. All rights reserved. |
2 | Distributed by Free Software Foundation, Inc. | |
3 | ||
4 | This file is part of Ghostscript. | |
5 | ||
6 | Ghostscript is distributed in the hope that it will be useful, but | |
7 | WITHOUT ANY WARRANTY. No author or distributor accepts responsibility | |
8 | to anyone for the consequences of using it or for whether it serves any | |
9 | particular purpose or works at all, unless he says so in writing. Refer | |
10 | to the Ghostscript General Public License for full details. | |
11 | ||
12 | Everyone is granted permission to copy, modify and redistribute | |
13 | Ghostscript, but only under the conditions described in the Ghostscript | |
14 | General Public License. A copy of this license is supposed to have been | |
15 | given to you along with Ghostscript so you can know your rights and | |
16 | responsibilities. It should be in a file named COPYING. Among other | |
17 | things, the copyright notice and this notice must be preserved on all | |
18 | copies. */ | |
19 | ||
20 | /* gxdither.c */ | |
21 | #include "gx.h" | |
22 | #include "gxfixed.h" | |
23 | #include "gxlum.h" | |
24 | #include "gxmatrix.h" | |
25 | #include "gzstate.h" | |
26 | #include "gzdevice.h" | |
27 | #include "gzcolor.h" | |
28 | #include "gzht.h" | |
29 | ||
30 | /* | |
31 | * Improved dithering for Ghostscript. The underlying device imaging | |
32 | * model supports dithering between two colors to generate intermediate | |
33 | * shades. | |
34 | * | |
35 | * The strategy is to first see if the color is either pure white or | |
36 | * pure black. In this case the problem is trivial. | |
37 | * | |
38 | * Next, if the device has high quality colors (at least 256 values | |
39 | * per axis), we ask it to map the color directly. | |
40 | * | |
41 | * Next, if the device is black and white, or the color happens | |
42 | * to be achromatic, we perform simple B/W dithering. | |
43 | * | |
44 | * Otherwise, things are a bit more complicated. If the device | |
45 | * supports N shades of each R, G and B independently, there are a total | |
46 | * of N*N*N colors. These colors form a 3-D grid in a cubical color | |
47 | * space. The following dithering technique works by locating the | |
48 | * color we want in this 3-D color grid and finding the eight colors | |
49 | * that surround it. In the case of dithering into 8 colors with 1 | |
50 | * bit for each red, green and blue, these eight colors will always | |
51 | * be the same. | |
52 | * | |
53 | * Now we consider all possible diagonal paths between the eight colors | |
54 | * and chose the path that runs closest to our desired color in 3-D | |
55 | * color space. There are 28 such paths. Then we find the position | |
56 | * on the path that is closest to our color. | |
57 | * | |
58 | * The search is made faster by always reflecting our color into | |
59 | * the bottom octant of the cube and comparing it to 7 paths. | |
60 | * After the best path and the best position on that path are found, | |
61 | * the results are reflected back into the original color space. | |
62 | * | |
63 | * NOTE: This code has been tested for B/W and Color imaging with | |
64 | * 1, 2, 3 and 8 bits per component. | |
65 | * | |
66 | * --- original code by Paul Haeberli @ Silicon Graphics - 1990 | |
67 | * --- extensively revised by L. Peter Deutsch, Aladdin Enterprises | |
68 | */ | |
69 | ||
70 | void gx_color_load(P2(gx_device_color *, gs_state *)); | |
71 | ||
72 | #define WEIGHT1 (unsigned long)(100) /* 1.0 */ | |
73 | #define WEIGHT2 (unsigned long)(71) /* 1/sqrt(2.0) */ | |
74 | #define WEIGHT3 (unsigned long)(62) /* 1/sqrt(3.0)+tad */ | |
75 | ||
76 | #define DIAG_R (0x1) | |
77 | #define DIAG_G (0x2) | |
78 | #define DIAG_B (0x4) | |
79 | #define DIAG_RG (0x3) | |
80 | #define DIAG_GB (0x6) | |
81 | #define DIAG_BR (0x5) | |
82 | #define DIAG_RGB (0x7) | |
83 | ||
84 | static unsigned short lum[8] = { | |
85 | (0*lum_blue_weight+0*lum_green_weight+0*lum_red_weight), | |
86 | (0*lum_blue_weight+0*lum_green_weight+1*lum_red_weight), | |
87 | (0*lum_blue_weight+1*lum_green_weight+0*lum_red_weight), | |
88 | (0*lum_blue_weight+1*lum_green_weight+1*lum_red_weight), | |
89 | (1*lum_blue_weight+0*lum_green_weight+0*lum_red_weight), | |
90 | (1*lum_blue_weight+0*lum_green_weight+1*lum_red_weight), | |
91 | (1*lum_blue_weight+1*lum_green_weight+0*lum_red_weight), | |
92 | (1*lum_blue_weight+1*lum_green_weight+1*lum_red_weight), | |
93 | }; | |
94 | ||
95 | /* Compute a fractional color, the correctly rounded quotient of */ | |
96 | /* f * max_color_param / maxv. */ | |
97 | #define _fc(f, maxv)\ | |
98 | (gx_color_value)(((f) * (max_color_param_long * 2) + maxv) / (maxv * 2)) | |
99 | /* We have to split up the following because of a bug in the IBM AIX 3.2 */ | |
100 | /* C compiler. */ | |
101 | private gx_color_value | |
102 | q0[] = { 0 }; | |
103 | private gx_color_value | |
104 | q1[] = { 0, 0xffff }; | |
105 | private gx_color_value | |
106 | q2[] = { 0, _fc(1,2), 0xffff }; | |
107 | private gx_color_value | |
108 | q3[] = { 0, _fc(1,3), _fc(2,3), 0xffff }; | |
109 | private gx_color_value | |
110 | q4[] = { 0, _fc(1,4), _fc(2,4), _fc(3,4), 0xffff }; | |
111 | private gx_color_value | |
112 | q5[] = { 0, _fc(1,5), _fc(2,5), _fc(3,5), _fc(4,5), 0xffff }; | |
113 | private gx_color_value | |
114 | q6[] = { 0, _fc(1,6), _fc(2,6), _fc(3,6), _fc(4,6), _fc(5,6), 0xffff }; | |
115 | private gx_color_value | |
116 | q7[] = { 0, _fc(1,7), _fc(2,7), _fc(3,7), _fc(4,7), _fc(5,7), _fc(6,7), 0xffff }; | |
117 | private gx_color_value _ds *color_quo[8] = { q0, q1, q2, q3, q4, q5, q6, q7 }; | |
118 | #define fractional_color(f, maxv)\ | |
119 | ((maxv) <= 7 ? color_quo[maxv][f] : _fc(f, maxv)) | |
120 | ||
121 | /* Note that this routine assumes that the incoming color */ | |
122 | /* has already been mapped through the transfer functions. */ | |
123 | void | |
124 | gx_color_render(gs_color *pcolor, gx_device_color *pdevc, gs_state *pgs) | |
125 | { device *pdev = pgs->device; | |
126 | uint max_value; | |
127 | unsigned long hsize; | |
128 | gx_device *dev; | |
129 | gx_color_index (*map_rgb_color)(P4(gx_device *, gx_color_value, | |
130 | gx_color_value, gx_color_value)); | |
131 | ||
132 | /* Make a special check for black and white. */ | |
133 | if ( pcolor->is_gray ) | |
134 | { if ( pcolor->luminance == 0 ) | |
135 | { pdevc->color2 = pdevc->color1 = pdev->black; | |
136 | pdevc->halftone_level = 0; /* pure color */ | |
137 | return; | |
138 | } | |
139 | else if ( pcolor->luminance == max_color_param ) | |
140 | { pdevc->color2 = pdevc->color1 = pdev->white; | |
141 | pdevc->halftone_level = 0; /* pure color */ | |
142 | return; | |
143 | } | |
144 | } | |
145 | ||
146 | /* get a few handy values */ | |
147 | dev = pdev->info; | |
148 | map_rgb_color = dev->procs->map_rgb_color; | |
149 | hsize = (unsigned)pgs->halftone->order_size; | |
150 | ||
151 | /* See if we should do it in black and white. */ | |
152 | if ( !gx_device_has_color(dev) || pcolor->is_gray ) | |
153 | { color_param lum = color_luminance(pcolor); | |
154 | if ( dev->color_info.max_gray >= 31 ) | |
155 | { /* Give the device a chance first. */ | |
156 | gx_color_index cx = | |
157 | (*map_rgb_color)(dev, lum, lum, lum); | |
158 | if ( cx != gx_no_color_index ) | |
159 | { pdevc->color2 = pdevc->color1 = cx; | |
160 | pdevc->halftone_level = 0; | |
161 | return; | |
162 | } | |
163 | } | |
164 | /* No luck, must dither. */ | |
165 | max_value = dev->color_info.dither_gray - 1; | |
166 | { unsigned long nshades = hsize * max_value + 1; | |
167 | unsigned long lx = | |
168 | (nshades * lum) / (max_color_param_long+1); | |
169 | color_param l = lx / hsize; | |
170 | pdevc->halftone_level = lx % hsize; | |
171 | lum = fractional_color(l, max_value); | |
172 | pdevc->color1 = (*map_rgb_color)(dev, lum, lum, lum); | |
173 | if ( pdevc->halftone_level == 0 ) | |
174 | { /* Close enough to a pure color, */ | |
175 | /* no dithering needed. */ | |
176 | pdevc->color2 = pdevc->color1; | |
177 | } | |
178 | else | |
179 | { lum = fractional_color(l+1, max_value); | |
180 | pdevc->color2 = | |
181 | (*map_rgb_color)(dev, lum, lum, lum); | |
182 | } | |
183 | gx_color_load(pdevc, pgs); | |
184 | } | |
185 | return; | |
186 | } | |
187 | ||
188 | /* If we are on a high quality RGB display, try not dithering first. */ | |
189 | if ( dev->color_info.max_rgb >= 31 ) | |
190 | { gx_color_index cx = (*map_rgb_color)(dev, pcolor->red, | |
191 | pcolor->green, | |
192 | pcolor->blue); | |
193 | if ( cx != gx_no_color_index ) | |
194 | { pdevc->color2 = pdevc->color1 = cx; | |
195 | pdevc->halftone_level = 0; /* pure color */ | |
196 | return; | |
197 | } | |
198 | } | |
199 | max_value = dev->color_info.dither_rgb - 1; | |
200 | ||
201 | /* must do real color dithering */ | |
202 | { color_param r, g, b; | |
203 | color_param rem_r = pcolor->red; | |
204 | color_param rem_g = pcolor->green; | |
205 | color_param rem_b = pcolor->blue; | |
206 | int adjust_r, adjust_b, adjust_g; | |
207 | unsigned short amax; | |
208 | unsigned long dmax; | |
209 | int axisc, diagc; | |
210 | unsigned short lum_invert; | |
211 | unsigned long dot1, dot2, dot3; | |
212 | int level; | |
213 | ||
214 | /* Compute the quotient and remainder of each color component */ | |
215 | /* with the actual number of available colors. Avoid */ | |
216 | /* multiplies and divides for the common values. */ | |
217 | /* Note that max_color_param is all 1s, so when only a short */ | |
218 | /* result is needed, subtracting x*max_color_param is equivalent to */ | |
219 | /* just adding x. rem_{r,g,b} are short, so we can get away */ | |
220 | /* with short arithmetic. */ | |
221 | switch ( max_value ) | |
222 | { | |
223 | case 1: /* 8 colors */ | |
224 | if ( rem_r == max_color_param ) rem_r = 0, r = 1; | |
225 | else r = 0; | |
226 | if ( rem_g == max_color_param ) rem_g = 0, g = 1; | |
227 | else g = 0; | |
228 | if ( rem_b == max_color_param ) rem_b = 0, b = 1; | |
229 | else b = 0; | |
230 | break; | |
231 | /* When max_color_param % max_value = 0, */ | |
232 | /* we can do some short arithmetic. */ | |
233 | /* Don't bother if ints are 32 bits. */ | |
234 | #if arch_ints_are_short | |
235 | case 3: /* 64 colors */ | |
236 | case 15: /* 4096 colors */ | |
237 | { const color_param q = max_color_param / max_value; | |
238 | r = rem_r / q; | |
239 | rem_r = rem_r * max_value + r; | |
240 | g = rem_g / q; | |
241 | rem_g = rem_g * max_value + g; | |
242 | b = rem_b / q; | |
243 | rem_b = rem_b * max_value + b; | |
244 | } break; | |
245 | #endif | |
246 | default: | |
247 | { unsigned long want_r = (ulong)max_value * rem_r; | |
248 | unsigned long want_g = (ulong)max_value * rem_g; | |
249 | unsigned long want_b = (ulong)max_value * rem_b; | |
250 | r = want_r / max_color_param_long; | |
251 | g = want_g / max_color_param_long; | |
252 | b = want_b / max_color_param_long; | |
253 | rem_r = (color_param)want_r + r; | |
254 | rem_g = (color_param)want_g + g; | |
255 | rem_b = (color_param)want_b + b; | |
256 | } | |
257 | } | |
258 | ||
259 | /* Check for no dithering required */ | |
260 | if ( !(rem_r | rem_g | rem_b) ) | |
261 | { pdevc->color2 = pdevc->color1 = | |
262 | (*map_rgb_color)(dev, fractional_color(r, max_value), | |
263 | fractional_color(g, max_value), | |
264 | fractional_color(b, max_value)); | |
265 | pdevc->halftone_level = 0; | |
266 | return; | |
267 | } | |
268 | #ifdef DEBUG | |
269 | if ( gs_debug['c'] ) | |
270 | { dprintf3("[c]rgb=%x,%x,%x -->\n", | |
271 | (unsigned)pcolor->red, (unsigned)pcolor->green, | |
272 | (unsigned)pcolor->blue); | |
273 | dprintf6(" %x+%x,%x+%x,%x+%x -->\n", | |
274 | (unsigned)r, (unsigned)rem_r, (unsigned)g, (unsigned)rem_g, | |
275 | (unsigned)b, (unsigned)rem_b); | |
276 | } | |
277 | #endif | |
278 | ||
279 | /* flip the remainder color into the 0, 0, 0 octant */ | |
280 | lum_invert = 0; | |
281 | #define half ((color_param)(max_color_param_long>>1)) | |
282 | if ( rem_r > half ) | |
283 | rem_r = max_color_param - rem_r, | |
284 | adjust_r = -1, r++, lum_invert += lum_red_weight; | |
285 | else | |
286 | adjust_r = 1; | |
287 | if ( rem_g > half) | |
288 | rem_g = max_color_param - rem_g, | |
289 | adjust_g = -1, g++, lum_invert += lum_green_weight; | |
290 | else | |
291 | adjust_g = 1; | |
292 | if ( rem_b > half ) | |
293 | rem_b = max_color_param - rem_b, | |
294 | adjust_b = -1, b++, lum_invert += lum_blue_weight; | |
295 | else | |
296 | adjust_b = 1; | |
297 | pdevc->color1 = (*map_rgb_color)(dev, fractional_color(r, max_value), | |
298 | fractional_color(g, max_value), | |
299 | fractional_color(b, max_value)); | |
300 | /* | |
301 | * Dot the color with each axis to find the best one of 7; | |
302 | * find the color at the end of the axis chosen. | |
303 | */ | |
304 | if ( rem_g > rem_r ) | |
305 | { if ( rem_b > rem_g ) | |
306 | amax = rem_b, axisc = DIAG_B; | |
307 | else | |
308 | amax = rem_g, axisc = DIAG_G; | |
309 | if ( rem_b > rem_r ) | |
310 | dmax = (unsigned long)rem_g+rem_b, diagc = DIAG_GB; | |
311 | else | |
312 | dmax = (unsigned long)rem_r+rem_g, diagc = DIAG_RG; | |
313 | } | |
314 | else | |
315 | { if ( rem_b > rem_r ) | |
316 | amax = rem_b, axisc = DIAG_B; | |
317 | else | |
318 | amax = rem_r, axisc = DIAG_R; | |
319 | if ( rem_b > rem_g ) | |
320 | dmax = (unsigned long)rem_b+rem_r, diagc = DIAG_BR; | |
321 | else | |
322 | dmax = (unsigned long)rem_r+rem_g, diagc = DIAG_RG; | |
323 | } | |
324 | ||
325 | dot1 = amax*WEIGHT1; | |
326 | dot2 = dmax*WEIGHT2; | |
327 | dot3 = (ulong)rem_r+rem_g+rem_b; /* rgb axis */ | |
328 | if ( dot1 > dot2 ) | |
329 | { if ( dot3*WEIGHT3 > dot1 ) | |
330 | diagc = DIAG_RGB, | |
331 | level = (hsize * dot3) / (3 * max_color_param_long); | |
332 | else | |
333 | diagc = axisc, | |
334 | level = (hsize * amax) / max_color_param_long; | |
335 | } | |
336 | else | |
337 | { if ( dot3*WEIGHT3 > dot2 ) | |
338 | diagc = DIAG_RGB, | |
339 | level = (hsize * dot3) / (3 * max_color_param_long); | |
340 | else | |
341 | level = (hsize * dmax) / (2 * max_color_param_long); | |
342 | }; | |
343 | #ifdef DEBUG | |
344 | if ( gs_debug['c'] ) | |
345 | { dprintf6(" %x+%x,%x+%x,%x+%x;", | |
346 | (unsigned)r, (unsigned)rem_r, (unsigned)g, (unsigned)rem_g, | |
347 | (unsigned)b, (unsigned)rem_b); | |
348 | dprintf3(" adjust=%d,%d,%d;\n", | |
349 | adjust_r, adjust_g, adjust_b); | |
350 | } | |
351 | #endif | |
352 | ||
353 | if ( (pdevc->halftone_level = level) == 0 ) | |
354 | pdevc->color2 = pdevc->color1; | |
355 | else | |
356 | { gx_color_index color2; | |
357 | /* construct the second color, inverting back to original space if needed */ | |
358 | if (diagc & DIAG_R) r += adjust_r; | |
359 | if (diagc & DIAG_G) g += adjust_g; | |
360 | if (diagc & DIAG_B) b += adjust_b; | |
361 | /* get the second device color, sorting by luminance */ | |
362 | color2 = (*map_rgb_color)(dev, fractional_color(r, max_value), | |
363 | fractional_color(g, max_value), | |
364 | fractional_color(b, max_value)); | |
365 | /****** THIS IS A BAD IDEA ******/ | |
366 | #if 0 | |
367 | if ( lum[diagc] < lum_invert ) | |
368 | { pdevc->color2 = pdevc->color1; | |
369 | pdevc->color1 = color2; | |
370 | pdevc->halftone_level = level = hsize - level; | |
371 | } | |
372 | else | |
373 | #endif | |
374 | pdevc->color2 = color2; | |
375 | gx_color_load(pdevc, pgs); | |
376 | } | |
377 | ||
378 | #ifdef DEBUG | |
379 | if ( gs_debug['c'] ) | |
380 | { dprintf5("[c]diagc=%d; color1=%lx, color2=%lx, level=%d/%d\n", | |
381 | diagc, (ulong)pdevc->color1, (ulong)pdevc->color2, | |
382 | level, (unsigned)hsize); | |
383 | } | |
384 | #endif | |
385 | ||
386 | } | |
387 | } |