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