1 /******************************************************************************
2 File: $Id: eprnfs.c,v 1.6 2001/05/01 07:02:01 Martin Rel $
3 Contents: Floyd-Steinberg error diffusion for eprn
4 Author: Martin Lottermoser, Greifswaldstrasse 28, 38124 Braunschweig,
5 Germany; e-mail: Martin.Lottermoser@t-online.de.
6
7 *******************************************************************************
8 * *
9 * Copyright (C) 2001 by Martin Lottermoser *
10 * All rights reserved *
11 * *
12 *******************************************************************************
13
14 Information about Floyd-Steinberg error diffusion should be available in a
15 number of places. I've used:
16
17 James D. Foley, Andries van Dam, Steven K. Feiner, John F. Hughes
18 "Computer Graphics"
19 Second edition in C
20 Reading/Massachusetts, etc.: Addison-Wesley, 1996
21 ISBN 0-201-84840-6
22
23 ******************************************************************************/
24
25 /*****************************************************************************/
26
27 #ifndef _XOPEN_SOURCE
28 #define _XOPEN_SOURCE 500
29 #endif
30
31 #include "gdeveprn.h"
32
33 /*****************************************************************************/
34
35 /* Here follow some macros for code sections used in several routines. */
36
37 #define fit_to_octet(value) ((value) < 0? 0: (value) > 255? 255: (value))
38
39 #define FS_assign() \
40 new_value = *to + correction; \
41 if (new_value < 0) { \
42 *to = 0; \
43 remaining_error += new_value; \
44 } \
45 else if (255 < new_value) { \
46 *to = 255; \
47 remaining_error += new_value - 255; \
48 } \
49 else *to = new_value;
50
51 #define error_propagation_Gray() \
52 if (error != 0) { \
53 remaining_error = error; \
54 \
55 /* 7/16 of the error goes to the right */ \
56 correction = (7*error)/16; \
57 remaining_error -= correction; \
58 if (pixel < max_pixel) { \
59 to = from + 1; \
60 FS_assign() \
61 if (pixel == pixels - 1 && *to > 0) { \
62 pixels++; \
63 line->length++; \
64 } \
65 } \
66 \
67 /* 3/16 of the error goes to the left and below */ \
68 correction = (3*error)/16; \
69 remaining_error -= correction; \
70 if (pixel > 0) { \
71 to = next_line->str + (pixel - 1); \
72 FS_assign() \
73 if (next_line->length < pixel && *to > 0) next_line->length = pixel; \
74 } \
75 \
76 /* 5/16 of the error goes below */ \
77 correction = (5*error)/16; \
78 remaining_error -= correction; \
79 to = next_line->str + pixel; \
80 FS_assign() \
81 if (next_line->length <= pixel && *to > 0) next_line->length = pixel + 1; \
82 \
83 /* The remainder (about 1/16 of the error) is added to the right and */ \
84 /* below. */ \
85 if (pixel < max_pixel) { \
86 to = next_line->str + (pixel+1); \
87 new_value = *to + remaining_error; \
88 *to = fit_to_octet(new_value); \
89 if (next_line->length < pixel + 2 && *to > 0) \
90 next_line->length = pixel + 2; \
91 } \
92 }
93
94 /* Number of octets per pixel for the non-monochrome cases */
95 #define OCTETS_PER_PIXEL 4
96
97 #define error_propagation_colour() \
98 if (error != 0) { \
99 remaining_error = error; \
100 \
101 /* 7/16 of the error goes to the right */ \
102 correction = (7*error)/16; \
103 remaining_error -= correction; \
104 if (pixel < max_pixel) { \
105 to = from + OCTETS_PER_PIXEL; \
106 FS_assign() \
107 if (pixel == pixels - 1 && *to > 0) { \
108 pixels++; \
109 line->length += OCTETS_PER_PIXEL; \
110 } \
111 } \
112 \
113 /* 3/16 of the error goes to the left and below */ \
114 correction = (3*error)/16; \
115 remaining_error -= correction; \
116 if (pixel > 0) { \
117 to = next_line->str + (pixel - 1)*OCTETS_PER_PIXEL + colorant; \
118 FS_assign() \
119 if (next_line->length < pixel*OCTETS_PER_PIXEL && *to > 0) \
120 next_line->length = pixel*OCTETS_PER_PIXEL; \
121 } \
122 \
123 /* 5/16 of the error goes below */ \
124 correction = (5*error)/16; \
125 remaining_error -= correction; \
126 to = next_line->str + pixel*OCTETS_PER_PIXEL + colorant; \
127 FS_assign() \
128 if (next_line->length <= pixel*OCTETS_PER_PIXEL && *to > 0) \
129 next_line->length = (pixel + 1)*OCTETS_PER_PIXEL; \
130 \
131 /* The remainder (about 1/16 of the error) is added to the right and */ \
132 /* below. */ \
133 if (pixel < max_pixel) { \
134 to = next_line->str + (pixel+1)*OCTETS_PER_PIXEL + colorant; \
135 new_value = *to + remaining_error; \
136 *to = fit_to_octet(new_value); \
137 if (next_line->length < (pixel + 2)*OCTETS_PER_PIXEL && *to > 0) \
138 next_line->length = (pixel + 2)*OCTETS_PER_PIXEL; \
139 } \
140 }
141
142 /******************************************************************************
143
144 Function: split_Gray_2
145
146 Floyd-Steinberg error diffusion for the process colour model Gray and
147 2 intensity levels.
148
149 ******************************************************************************/
150
split_Gray_2(eprn_OctetString * line,eprn_OctetString * next_line,int max_octets,eprn_OctetString bitplanes[])151 static void split_Gray_2(eprn_OctetString *line, eprn_OctetString *next_line,
152 int max_octets, eprn_OctetString bitplanes[])
153 {
154 const int
155 max_pixel = max_octets - 1;
156 int
157 correction,
158 error,
159 new_value,
160 pixel,
161 pixel_mod_8,
162 pixels = line->length,
163 remaining_error;
164 eprn_Octet
165 approx,
166 *from,
167 *ptr,
168 *to;
169
170 ptr = bitplanes[0].str;
171
172 /* Loop over pixels in the scan line. Note that 'pixels' may increase
173 within the loop. */
174 for (pixel = 0, pixel_mod_8 = 8; pixel < pixels; pixel++, pixel_mod_8++) {
175 if (pixel_mod_8 == 8) {
176 pixel_mod_8 = 0;
177 *ptr = 0;
178 }
179
180 /* Determine approximation and error for this pixel */
181 from = line->str + pixel;
182 approx = *from >> 7; /* take the most significant bit */
183 error = *from - 255*approx;
184 /* The sign of 'error' is chosen such that 'error' is positive if
185 colorant intensity has to be added to the picture. */
186
187 /* Insert the approximation into the output plane */
188 *ptr = (*ptr << 1) | approx;
189
190 error_propagation_Gray()
191
192 if (pixel_mod_8 == 7) ptr++;
193 }
194
195 eprn_finalize(false, 0, 1, bitplanes, &ptr, pixels);
196
197 return;
198 }
199
200 /******************************************************************************
201
202 Function: split_Gray()
203
204 Floyd-Steinberg error diffusion for the process colour model Gray and an
205 arbitrary number of intensity levels.
206
207 ******************************************************************************/
208
split_Gray(eprn_OctetString * line,eprn_OctetString * next_line,int max_octets,unsigned int black_levels,eprn_OctetString bitplanes[])209 static void split_Gray(eprn_OctetString *line, eprn_OctetString *next_line,
210 int max_octets, unsigned int black_levels, eprn_OctetString bitplanes[])
211 {
212 const int
213 max_pixel = max_octets - 1,
214 planes = eprn_bits_for_levels(black_levels);
215 int
216 correction,
217 error,
218 new_value,
219 pixel,
220 pixel_mod_8,
221 pixels = line->length,
222 plane,
223 remaining_error;
224 eprn_Octet
225 approx,
226 *from,
227 *ptr[8],
228 *to;
229 const unsigned int
230 divisor = 256/black_levels,
231 max_level = black_levels - 1;
232
233 for (plane = 0; plane < planes; plane++) ptr[plane] = bitplanes[plane].str;
234
235 /* Loop over pixels in the scan line. Note that 'pixels' may increase
236 within the loop. */
237 for (pixel = 0, pixel_mod_8 = 8; pixel < pixels; pixel++, pixel_mod_8++) {
238 if (pixel_mod_8 == 8) {
239 pixel_mod_8 = 0;
240 for (plane = 0; plane < planes; plane++) *ptr[plane] = 0;
241 }
242
243 /* Determine approximation and error for this pixel */
244 from = line->str + pixel;
245 approx = *from/divisor;
246 error = *from - (255*approx)/max_level;
247 /* The sign of 'error' is chosen such that 'error' is positive if
248 colorant intensity has to be added to the picture. */
249
250 /* Distribute the approximation over the bit planes */
251 for (plane = 0; plane < planes; plane++) {
252 *ptr[plane] = (*ptr[plane] << 1) | (approx & 0x01);
253 approx >>= 1;
254 }
255
256 error_propagation_Gray()
257
258 if (pixel_mod_8 == 7)
259 for (plane = 0; plane < planes; plane++) ptr[plane]++;
260 }
261
262 eprn_finalize(false, 0, planes, bitplanes, ptr, pixels);
263
264 return;
265 }
266
267 /*****************************************************************************/
268
269 /* Index of the black colorant in a pixel value (gx_color_index) for the
270 non-monochrome cases */
271 #define BLACK_INDEX 3
272
273 /******************************************************************************
274
275 Function: split_colour_CMYK_2()
276
277 Floyd-Steinberg error diffusion for the CMYK colour model using 2 intensity
278 levels for all colorants.
279
280 This function is about 14 % faster than split_colour_at_most_2(), and every
281 bit helps.
282
283 ******************************************************************************/
284
285 #define PLANES 4
286
split_colour_CMYK_2(eprn_OctetString * line,eprn_OctetString * next_line,int max_octets,eprn_OctetString bitplanes[])287 static void split_colour_CMYK_2(eprn_OctetString *line,
288 eprn_OctetString *next_line, int max_octets, eprn_OctetString bitplanes[])
289 {
290 const int
291 max_pixel = max_octets/OCTETS_PER_PIXEL - 1;
292 int
293 colorant,
294 correction,
295 error,
296 new_value,
297 pixel,
298 pixel_mod_8,
299 pixels = line->length/OCTETS_PER_PIXEL,
300 plane,
301 remaining_error;
302 eprn_Octet
303 approx,
304 *from,
305 *ptr[4],
306 *to;
307
308 for (plane = 0; plane < PLANES; plane++) ptr[plane] = bitplanes[plane].str;
309
310 /* Loop over pixels in the scan line. Note that 'pixels' may increase
311 within the loop. */
312 for (pixel = 0, pixel_mod_8 = 8; pixel < pixels; pixel++, pixel_mod_8++) {
313 if (pixel_mod_8 == 8) {
314 pixel_mod_8 = 0;
315 for (plane = 0; plane < PLANES; plane++) *ptr[plane] = 0;
316 }
317
318 /* Loop over colorants within a scan line. Remember that the order within
319 a pixel is YMCK. */
320 for (colorant = BLACK_INDEX; colorant >= 0; colorant--) {
321 from = line->str + pixel*OCTETS_PER_PIXEL + colorant;
322
323 /* Determine approximation and error for this pixel */
324 approx = *from >> 7;
325 error = *from - 255*approx;
326 /* The sign of 'error' is chosen such that 'error' is positive if
327 colorant intensity has to be added to the picture. */
328
329 /* Insert the approximation in the bit plane */
330 plane = BLACK_INDEX - colorant;
331 *ptr[plane] = (*ptr[plane] << 1) | approx;
332
333 error_propagation_colour()
334 }
335
336 if (pixel_mod_8 == 7)
337 for (plane = 0; plane < PLANES; plane++) ptr[plane]++;
338 }
339
340 eprn_finalize(false, 2, PLANES, bitplanes, ptr, pixels);
341
342 return;
343 }
344
345 /******************************************************************************
346
347 Function: split_colour_at_most_2()
348
349 Floyd-Steinberg error diffusion for the non-monochrome process colour models
350 using 2 intensity levels for the CMY colorants and at most 2 for the black
351 colorant.
352
353 ******************************************************************************/
354
split_colour_at_most_2(eprn_OctetString * line,eprn_OctetString * next_line,int max_octets,eprn_ColourModel colour_model,eprn_OctetString bitplanes[])355 static void split_colour_at_most_2(eprn_OctetString *line,
356 eprn_OctetString *next_line, int max_octets, eprn_ColourModel colour_model,
357 eprn_OctetString bitplanes[])
358 {
359 const int
360 last_colorant =
361 colour_model == eprn_DeviceCMY_plus_K || colour_model == eprn_DeviceCMYK?
362 BLACK_INDEX: 2,
363 max_pixel = max_octets/OCTETS_PER_PIXEL - 1,
364 planes =
365 colour_model == eprn_DeviceCMY_plus_K || colour_model == eprn_DeviceCMYK?
366 4: 3;
367 int
368 colorant,
369 correction,
370 error,
371 new_value,
372 pixel,
373 pixel_mod_8,
374 pixels = line->length/OCTETS_PER_PIXEL,
375 plane,
376 remaining_error;
377 eprn_Octet
378 approx[4],
379 *from,
380 *ptr[4],
381 *to;
382
383 for (plane = 0; plane < planes; plane++) ptr[plane] = bitplanes[plane].str;
384
385 /* Loop over pixels in the scan line. Note that 'pixels' may increase
386 within the loop. */
387 for (pixel = 0, pixel_mod_8 = 8; pixel < pixels; pixel++, pixel_mod_8++) {
388 if (pixel_mod_8 == 8) {
389 pixel_mod_8 = 0;
390 for (plane = 0; plane < planes; plane++) *ptr[plane] = 0;
391 }
392
393 /* Loop over colorants within a scan line. Remember that the order within
394 a pixel is YMCK or BGR-. */
395 for (colorant = last_colorant; colorant >= 0; colorant--) {
396 from = line->str + pixel*OCTETS_PER_PIXEL + colorant;
397
398 /* Determine approximation and error for this pixel */
399 approx[colorant] = *from >> 7;
400 error = *from - 255*approx[colorant];
401 /* The sign of 'error' is chosen such that 'error' is positive if
402 colorant intensity has to be added to the picture. */
403
404 error_propagation_colour()
405 }
406
407 /* Determine the black component for CMY+K */
408 if (colour_model == eprn_DeviceCMY_plus_K &&
409 approx[0] == approx[1] && approx[1] == approx[2] && approx[0] > 0) {
410 approx[BLACK_INDEX] = approx[0];
411 approx[0] = approx[1] = approx[2] = 0;
412 }
413
414 /* Distribute the approximation over the bit planes */
415 for (colorant = last_colorant, plane = 0; colorant >= 0;
416 colorant--, plane++) {
417 *ptr[plane] = (*ptr[plane] << 1) | approx[colorant];
418 }
419
420 if (pixel_mod_8 == 7)
421 for (plane = 0; plane < planes; plane++) ptr[plane]++;
422 }
423
424 eprn_finalize(colour_model == eprn_DeviceRGB, 2, planes, bitplanes, ptr,
425 pixels);
426
427 return;
428 }
429
430 /******************************************************************************
431
432 Function: split_colour()
433
434 Floyd-Steinberg error diffusion for the non-monochrome process colour models
435 and an arbitrary number of intensity levels.
436
437 ******************************************************************************/
438
split_colour(eprn_OctetString * line,eprn_OctetString * next_line,int max_octets,eprn_ColourModel colour_model,unsigned int black_levels,unsigned int non_black_levels,eprn_OctetString bitplanes[])439 static void split_colour(eprn_OctetString *line, eprn_OctetString *next_line,
440 int max_octets, eprn_ColourModel colour_model,
441 unsigned int black_levels, unsigned int non_black_levels,
442 eprn_OctetString bitplanes[])
443 {
444 const int
445 black_planes = eprn_bits_for_levels(black_levels),
446 last_colorant = black_levels > 0? BLACK_INDEX: 2,
447 max_pixel = max_octets/OCTETS_PER_PIXEL - 1,
448 non_black_planes = eprn_bits_for_levels(non_black_levels),
449 planes = black_planes + 3*non_black_planes;
450 int
451 colorant,
452 correction,
453 error,
454 new_value,
455 next_plane[4],
456 pixel,
457 pixel_mod_8,
458 pixels = line->length/OCTETS_PER_PIXEL,
459 plane,
460 remaining_error;
461 eprn_Octet
462 approx[4],
463 *from,
464 *ptr[32],
465 *to;
466 unsigned int
467 divisor[4],
468 max_level[4];
469
470 if (black_levels > 0) {
471 divisor[BLACK_INDEX] = 256/black_levels;
472 max_level[BLACK_INDEX] = black_levels - 1;
473 }
474 else {
475 divisor[BLACK_INDEX] = 0;
476 max_level[BLACK_INDEX] = 0;
477 }
478 next_plane[BLACK_INDEX] = black_planes;
479
480 for (colorant = 0; colorant < BLACK_INDEX; colorant++) {
481 divisor[colorant] = 256/non_black_levels;
482 max_level[colorant] = non_black_levels - 1;
483 next_plane[colorant] = (3 - colorant)*non_black_planes + black_planes;
484 }
485
486 for (plane = 0; plane < planes; plane++) ptr[plane] = bitplanes[plane].str;
487
488 /* Loop over pixels in the scan line. Note that 'pixels' may increase
489 within the loop. */
490 for (pixel = 0, pixel_mod_8 = 8; pixel < pixels; pixel++, pixel_mod_8++) {
491 if (pixel_mod_8 == 8) {
492 pixel_mod_8 = 0;
493 for (plane = 0; plane < planes; plane++) *ptr[plane] = 0;
494 }
495
496 /* Loop over colorants within a scan line */
497 for (colorant = last_colorant; colorant >= 0; colorant--) {
498 from = line->str + pixel*OCTETS_PER_PIXEL + colorant;
499
500 /* Determine approximation and error for this pixel */
501 approx[colorant] = *from/divisor[colorant];
502 error = *from - (255*approx[colorant])/max_level[colorant];
503 /* The sign of 'error' is chosen such that 'error' is positive if
504 colorant intensity has to be added to the picture. */
505
506 error_propagation_colour()
507 }
508
509 /* Determine the black component for CMY+K */
510 if (colour_model == eprn_DeviceCMY_plus_K &&
511 approx[0] == approx[1] && approx[1] == approx[2] && approx[0] > 0) {
512 int value = approx[0]*(black_levels - 1);
513 if (value % (non_black_levels - 1) == 0) {
514 /* Black does have a level at the same intensity as the CMY levels */
515 approx[BLACK_INDEX] = value/(non_black_levels - 1);
516 approx[0] = approx[1] = approx[2] = 0;
517 }
518 }
519
520 /* Distribute the approximation over the bit planes */
521 plane = 0;
522 for (colorant = last_colorant; colorant >= 0; colorant--) {
523 while (plane < next_plane[colorant]) {
524 *ptr[plane] = (*ptr[plane] << 1) | (approx[colorant] & 0x01);
525 approx[colorant] >>= 1;
526 plane++;
527 }
528 }
529
530 if (pixel_mod_8 == 7) {
531 int j;
532 for (j = 0; j < planes; j++) ptr[j]++;
533 }
534 }
535
536 eprn_finalize(colour_model == eprn_DeviceRGB, non_black_levels, planes,
537 bitplanes, ptr, pixels);
538
539 return;
540 }
541
542 /******************************************************************************
543
544 Function: eprn_split_FS
545
546 This function performs Floyd-Steinberg error diffusion on a scan line
547 and returns the result as bitplanes.
548
549 'line' points to the scan line to be split, 'next_line' to the following one.
550 Both lines will be modified by this process. This modification assumes that
551 the function is called successively for all lines, starting with the first.
552 All octets up to 'max_octets' must be available in the input lines and, as
553 far as they have not been included in the length fields, must be zero.
554 The parameter 'colour_model' specifies the process colour model used.
555 'black_levels' is the number of intensity levels for the black colorant,
556 'non_black_levels' the corresponding number for the other colorants.
557 'bitplanes' is an array of bitplanes into which the result will be stored
558 in the usual format.
559
560 ******************************************************************************/
561
eprn_split_FS(eprn_OctetString * line,eprn_OctetString * next_line,int max_octets,eprn_ColourModel colour_model,unsigned int black_levels,unsigned int non_black_levels,eprn_OctetString bitplanes[])562 void eprn_split_FS(eprn_OctetString *line, eprn_OctetString *next_line,
563 int max_octets, eprn_ColourModel colour_model,
564 unsigned int black_levels, unsigned int non_black_levels,
565 eprn_OctetString bitplanes[])
566 {
567 if (colour_model == eprn_DeviceGray) {
568 if (black_levels == 2)
569 split_Gray_2(line, next_line, max_octets, bitplanes);
570 else
571 split_Gray(line, next_line, max_octets, black_levels, bitplanes);
572 }
573 else if (colour_model == eprn_DeviceCMYK &&
574 black_levels == 2 && non_black_levels == 2)
575 split_colour_CMYK_2(line, next_line, max_octets, bitplanes);
576 else {
577 if (black_levels <= 2 && non_black_levels == 2)
578 split_colour_at_most_2(line, next_line, max_octets, colour_model,
579 bitplanes);
580 else
581 split_colour(line, next_line, max_octets, colour_model, black_levels,
582 non_black_levels, bitplanes);
583 }
584
585 return;
586 }
587