1 /*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 - This software is distributed in the hope that it will be
4 - useful, but with NO WARRANTY OF ANY KIND.
5 - No author or distributor accepts responsibility to anyone for the
6 - consequences of using this software, or for whether it serves any
7 - particular purpose or works at all, unless he or she says so in
8 - writing. Everyone is granted permission to copy, modify and
9 - redistribute this source code, for commercial or non-commercial
10 - purposes, with the following restrictions: (1) the origin of this
11 - source code must not be misrepresented; (2) modified versions must
12 - be plainly marked as such; and (3) this notice may not be removed
13 - or altered from any source or modified source distribution.
14 *====================================================================*/
15
16 /*
17 * grayquantlow.c
18 *
19 * Thresholding from 8 bpp to 1 bpp
20 *
21 * Floyd-Steinberg dithering to binary
22 * void ditherToBinaryLow()
23 * void ditherToBinaryLineLow()
24 *
25 * Simple (pixelwise) binarization
26 * void thresholdToBinaryLow()
27 * void thresholdToBinaryLineLow()
28 *
29 * A slower version of Floyd-Steinberg dithering that uses LUTs
30 * void ditherToBinaryLUTLow()
31 * void ditherToBinaryLineLUTLow()
32 * l_int32 make8To1DitherTables()
33 *
34 * Thresholding from 8 bpp to 2 bpp
35 *
36 * Floyd-Steinberg-like dithering to 2 bpp
37 * void ditherTo2bppLow()
38 * void ditherTo2bppLineLow()
39 * l_int32 make8To2DitherTables()
40 *
41 * Simple thresholding to 2 bpp
42 * void thresholdTo2bppLow()
43 *
44 * Thresholding from 8 bpp to 4 bpp
45 *
46 * Simple thresholding to 4 bpp
47 * void thresholdTo4bppLow()
48 */
49
50 #include <stdio.h>
51 #include <stdlib.h>
52 #include <string.h>
53 #include "allheaders.h"
54
55 #ifndef NO_CONSOLE_IO
56 #define DEBUG_UNROLLING 0
57 #endif /* ~NO_CONSOLE_IO */
58
59
60 /*------------------------------------------------------------------*
61 * Binarization by Floyd-Steinberg Dithering *
62 *------------------------------------------------------------------*/
63 /*
64 * ditherToBinaryLow()
65 *
66 * See comments in pixDitherToBinary() in binarize.c
67 */
68 void
ditherToBinaryLow(l_uint32 * datad,l_int32 w,l_int32 h,l_int32 wpld,l_uint32 * datas,l_int32 wpls,l_uint32 * bufs1,l_uint32 * bufs2,l_int32 lowerclip,l_int32 upperclip)69 ditherToBinaryLow(l_uint32 *datad,
70 l_int32 w,
71 l_int32 h,
72 l_int32 wpld,
73 l_uint32 *datas,
74 l_int32 wpls,
75 l_uint32 *bufs1,
76 l_uint32 *bufs2,
77 l_int32 lowerclip,
78 l_int32 upperclip)
79 {
80 l_int32 i;
81 l_uint32 *lined;
82
83 /* do all lines except last line */
84 memcpy(bufs2, datas, 4 * wpls); /* prime the buffer */
85 for (i = 0; i < h - 1; i++) {
86 memcpy(bufs1, bufs2, 4 * wpls);
87 memcpy(bufs2, datas + (i + 1) * wpls, 4 * wpls);
88 lined = datad + i * wpld;
89 ditherToBinaryLineLow(lined, w, bufs1, bufs2, lowerclip, upperclip, 0);
90 }
91
92 /* do last line */
93 memcpy(bufs1, bufs2, 4 * wpls);
94 lined = datad + (h - 1) * wpld;
95 ditherToBinaryLineLow(lined, w, bufs1, bufs2, lowerclip, upperclip, 1);
96 return;
97 }
98
99
100 /*
101 * ditherToBinaryLineLow()
102 *
103 * Input: lined (ptr to beginning of dest line
104 * w (width of image in pixels)
105 * bufs1 (buffer of current source line)
106 * bufs2 (buffer of next source line)
107 * lowerclip (lower clip distance to black)
108 * upperclip (upper clip distance to white)
109 * lastlineflag (0 if not last dest line, 1 if last dest line)
110 * Return: void
111 *
112 * Dispatches FS error diffusion dithering for
113 * a single line of the image. If lastlineflag == 0,
114 * both source buffers are used; otherwise, only bufs1
115 * is used. We use source buffers because the error
116 * is propagated into them, and we don't want to change
117 * the input src image.
118 *
119 * We break dithering out line by line to make it
120 * easier to combine functions like interpolative
121 * scaling and error diffusion dithering, as such a
122 * combination of operations obviates the need to
123 * generate a 2x grayscale image as an intermediary.
124 */
125 void
ditherToBinaryLineLow(l_uint32 * lined,l_int32 w,l_uint32 * bufs1,l_uint32 * bufs2,l_int32 lowerclip,l_int32 upperclip,l_int32 lastlineflag)126 ditherToBinaryLineLow(l_uint32 *lined,
127 l_int32 w,
128 l_uint32 *bufs1,
129 l_uint32 *bufs2,
130 l_int32 lowerclip,
131 l_int32 upperclip,
132 l_int32 lastlineflag)
133 {
134 l_int32 j;
135 l_int32 oval, eval;
136 l_uint8 fval1, fval2, rval, bval, dval;
137
138 if (lastlineflag == 0) {
139 for (j = 0; j < w - 1; j++) {
140 oval = GET_DATA_BYTE(bufs1, j);
141 if (oval > 127) { /* binarize to OFF */
142 if ((eval = 255 - oval) > upperclip) {
143 /* subtract from neighbors */
144 fval1 = (3 * eval) / 8;
145 fval2 = eval / 4;
146 rval = GET_DATA_BYTE(bufs1, j + 1);
147 rval = L_MAX(0, rval - fval1);
148 SET_DATA_BYTE(bufs1, j + 1, rval);
149 bval = GET_DATA_BYTE(bufs2, j);
150 bval = L_MAX(0, bval - fval1);
151 SET_DATA_BYTE(bufs2, j, bval);
152 dval = GET_DATA_BYTE(bufs2, j + 1);
153 dval = L_MAX(0, dval - fval2);
154 SET_DATA_BYTE(bufs2, j + 1, dval);
155 }
156 }
157 else { /* oval <= 127; binarize to ON */
158 SET_DATA_BIT(lined, j); /* ON pixel */
159 if (oval > lowerclip) {
160 /* add to neighbors */
161 fval1 = (3 * oval) / 8;
162 fval2 = oval / 4;
163 rval = GET_DATA_BYTE(bufs1, j + 1);
164 rval = L_MIN(255, rval + fval1);
165 SET_DATA_BYTE(bufs1, j + 1, rval);
166 bval = GET_DATA_BYTE(bufs2, j);
167 bval = L_MIN(255, bval + fval1);
168 SET_DATA_BYTE(bufs2, j, bval);
169 dval = GET_DATA_BYTE(bufs2, j + 1);
170 dval = L_MIN(255, dval + fval2);
171 SET_DATA_BYTE(bufs2, j + 1, dval);
172 }
173 }
174 }
175
176 /* do last column: j = w - 1 */
177 oval = GET_DATA_BYTE(bufs1, j);
178 if (oval > 127) { /* binarize to OFF */
179 if ((eval = 255 - oval) > upperclip) {
180 /* subtract from neighbors */
181 fval1 = (3 * eval) / 8;
182 bval = GET_DATA_BYTE(bufs2, j);
183 bval = L_MAX(0, bval - fval1);
184 SET_DATA_BYTE(bufs2, j, bval);
185 }
186 }
187 else { /*oval <= 127; binarize to ON */
188 SET_DATA_BIT(lined, j); /* ON pixel */
189 if (oval > lowerclip) {
190 /* add to neighbors */
191 fval1 = (3 * oval) / 8;
192 bval = GET_DATA_BYTE(bufs2, j);
193 bval = L_MIN(255, bval + fval1);
194 SET_DATA_BYTE(bufs2, j, bval);
195 }
196 }
197 }
198 else { /* lastlineflag == 1 */
199 for (j = 0; j < w - 1; j++) {
200 oval = GET_DATA_BYTE(bufs1, j);
201 if (oval > 127) { /* binarize to OFF */
202 if ((eval = 255 - oval) > upperclip) {
203 /* subtract from neighbors */
204 fval1 = (3 * eval) / 8;
205 rval = GET_DATA_BYTE(bufs1, j + 1);
206 rval = L_MAX(0, rval - fval1);
207 SET_DATA_BYTE(bufs1, j + 1, rval);
208 }
209 }
210 else { /* oval <= 127; binarize to ON */
211 SET_DATA_BIT(lined, j); /* ON pixel */
212 if (oval > lowerclip) {
213 /* add to neighbors */
214 fval1 = (3 * oval) / 8;
215 rval = GET_DATA_BYTE(bufs1, j + 1);
216 rval = L_MIN(255, rval + fval1);
217 SET_DATA_BYTE(bufs1, j + 1, rval);
218 }
219 }
220 }
221
222 /* do last pixel: (i, j) = (h - 1, w - 1) */
223 oval = GET_DATA_BYTE(bufs1, j);
224 if (oval < 128)
225 SET_DATA_BIT(lined, j); /* ON pixel */
226 }
227
228 return;
229 }
230
231
232
233 /*------------------------------------------------------------------*
234 * Simple binarization with fixed threshold *
235 *------------------------------------------------------------------*/
236 /*
237 * thresholdToBinaryLow()
238 *
239 * If the source pixel is less than thresh,
240 * the dest will be 1; otherwise, it will be 0
241 */
242 void
thresholdToBinaryLow(l_uint32 * datad,l_int32 w,l_int32 h,l_int32 wpld,l_uint32 * datas,l_int32 d,l_int32 wpls,l_int32 thresh)243 thresholdToBinaryLow(l_uint32 *datad,
244 l_int32 w,
245 l_int32 h,
246 l_int32 wpld,
247 l_uint32 *datas,
248 l_int32 d,
249 l_int32 wpls,
250 l_int32 thresh)
251 {
252 l_int32 i;
253 l_uint32 *lines, *lined;
254
255 for (i = 0; i < h; i++) {
256 lines = datas + i * wpls;
257 lined = datad + i * wpld;
258 thresholdToBinaryLineLow(lined, w, lines, d, thresh);
259 }
260 return;
261 }
262
263
264 /*
265 * thresholdToBinaryLineLow()
266 *
267 */
268 void
thresholdToBinaryLineLow(l_uint32 * lined,l_int32 w,l_uint32 * lines,l_int32 d,l_int32 thresh)269 thresholdToBinaryLineLow(l_uint32 *lined,
270 l_int32 w,
271 l_uint32 *lines,
272 l_int32 d,
273 l_int32 thresh)
274 {
275 l_int32 j, k, gval, scount, dcount;
276 l_uint32 sword, dword;
277
278 PROCNAME("thresholdToBinaryLineLow");
279
280 switch (d)
281 {
282 case 4:
283 /* Unrolled as 4 source words, 1 dest word */
284 for (j = 0, scount = 0, dcount = 0; j + 31 < w; j += 32) {
285 dword = 0;
286 for (k = 0; k < 4; k++) {
287 sword = lines[scount++];
288 dword <<= 8;
289 gval = (sword >> 28) & 0xf;
290 /* Trick used here and below: if gval < thresh then
291 * gval - thresh < 0, so its high-order bit is 1, and
292 * ((gval - thresh) >> 31) & 1 == 1; likewise, if
293 * gval >= thresh, then ((gval - thresh) >> 31) & 1 == 0
294 * Doing it this way avoids a random (and thus easily
295 * mispredicted) branch on each pixel. */
296 dword |= ((gval - thresh) >> 24) & 128;
297 gval = (sword >> 24) & 0xf;
298 dword |= ((gval - thresh) >> 25) & 64;
299 gval = (sword >> 20) & 0xf;
300 dword |= ((gval - thresh) >> 26) & 32;
301 gval = (sword >> 16) & 0xf;
302 dword |= ((gval - thresh) >> 27) & 16;
303 gval = (sword >> 12) & 0xf;
304 dword |= ((gval - thresh) >> 28) & 8;
305 gval = (sword >> 8) & 0xf;
306 dword |= ((gval - thresh) >> 29) & 4;
307 gval = (sword >> 4) & 0xf;
308 dword |= ((gval - thresh) >> 30) & 2;
309 gval = sword & 0xf;
310 dword |= ((gval - thresh) >> 31) & 1;
311 }
312 lined[dcount++] = dword;
313 }
314
315 if (j < w) {
316 dword = 0;
317 for (; j < w; j++) {
318 if ((j & 7) == 0) {
319 sword = lines[scount++];
320 }
321 gval = (sword >> 28) & 0xf;
322 sword <<= 4;
323 dword |= (((gval - thresh) >> 31) & 1) << (31 - (j & 31));
324 }
325 lined[dcount] = dword;
326 }
327 #if DEBUG_UNROLLING
328 #define CHECK_BIT(a, b, c) if (GET_DATA_BIT(a, b) != c) { \
329 fprintf(stderr, "Error: mismatch at %d/%d(%d), %d vs %d\n", \
330 j, w, d, GET_DATA_BIT(a, b), c); }
331 for (j = 0; j < w; j++) {
332 gval = GET_DATA_QBIT(lines, j);
333 CHECK_BIT(lined, j, gval < thresh ? 1 : 0);
334 }
335 #endif
336 break;
337 case 8:
338 /* Unrolled as 8 source words, 1 dest word */
339 for (j = 0, scount = 0, dcount = 0; j + 31 < w; j += 32) {
340 dword = 0;
341 for (k = 0; k < 8; k++) {
342 sword = lines[scount++];
343 dword <<= 4;
344 gval = (sword >> 24) & 0xff;
345 dword |= ((gval - thresh) >> 28) & 8;
346 gval = (sword >> 16) & 0xff;
347 dword |= ((gval - thresh) >> 29) & 4;
348 gval = (sword >> 8) & 0xff;
349 dword |= ((gval - thresh) >> 30) & 2;
350 gval = sword & 0xff;
351 dword |= ((gval - thresh) >> 31) & 1;
352 }
353 lined[dcount++] = dword;
354 }
355
356 if (j < w) {
357 dword = 0;
358 for (; j < w; j++) {
359 if ((j & 3) == 0) {
360 sword = lines[scount++];
361 }
362 gval = (sword >> 24) & 0xff;
363 sword <<= 8;
364 dword |= (((gval - thresh) >> 31) & 1) << (31 - (j & 31));
365 }
366 lined[dcount] = dword;
367 }
368 #if DEBUG_UNROLLING
369 for (j = 0; j < w; j++) {
370 gval = GET_DATA_BYTE(lines, j);
371 CHECK_BIT(lined, j, gval < thresh ? 1 : 0);
372 }
373 #undef CHECK_BIT
374 #endif
375 break;
376 default:
377 L_ERROR("src depth not 4 or 8 bpp", procName);
378 break;
379 }
380 return;
381 }
382
383
384 /*---------------------------------------------------------------------*
385 * Alternate implementation of dithering that uses lookup tables. *
386 * This is analogous to the method used in dithering to 2 bpp. *
387 *---------------------------------------------------------------------*/
388 /*!
389 * ditherToBinaryLUTLow()
390 *
391 * Low-level function for doing Floyd-Steinberg error diffusion
392 * dithering from 8 bpp (datas) to 1 bpp (datad). Two source
393 * line buffers, bufs1 and bufs2, are provided, along with three
394 * 256-entry lookup tables: tabval gives the output pixel value,
395 * tab38 gives the extra (plus or minus) transferred to the pixels
396 * directly to the left and below, and tab14 gives the extra
397 * transferred to the diagonal below. The choice of 3/8 and 1/4
398 * is traditional but arbitrary when you use a lookup table; the
399 * only constraint is that the sum is 1. See other comments below.
400 */
401 void
ditherToBinaryLUTLow(l_uint32 * datad,l_int32 w,l_int32 h,l_int32 wpld,l_uint32 * datas,l_int32 wpls,l_uint32 * bufs1,l_uint32 * bufs2,l_int32 * tabval,l_int32 * tab38,l_int32 * tab14)402 ditherToBinaryLUTLow(l_uint32 *datad,
403 l_int32 w,
404 l_int32 h,
405 l_int32 wpld,
406 l_uint32 *datas,
407 l_int32 wpls,
408 l_uint32 *bufs1,
409 l_uint32 *bufs2,
410 l_int32 *tabval,
411 l_int32 *tab38,
412 l_int32 *tab14)
413 {
414 l_int32 i;
415 l_uint32 *lined;
416
417 /* do all lines except last line */
418 memcpy(bufs2, datas, 4 * wpls); /* prime the buffer */
419 for (i = 0; i < h - 1; i++) {
420 memcpy(bufs1, bufs2, 4 * wpls);
421 memcpy(bufs2, datas + (i + 1) * wpls, 4 * wpls);
422 lined = datad + i * wpld;
423 ditherToBinaryLineLUTLow(lined, w, bufs1, bufs2,
424 tabval, tab38, tab14, 0);
425 }
426
427 /* do last line */
428 memcpy(bufs1, bufs2, 4 * wpls);
429 lined = datad + (h - 1) * wpld;
430 ditherToBinaryLineLUTLow(lined, w, bufs1, bufs2, tabval, tab38, tab14, 1);
431 return;
432 }
433
434
435 /*!
436 * ditherToBinaryLineLUTLow()
437 *
438 * Input: lined (ptr to beginning of dest line
439 * w (width of image in pixels)
440 * bufs1 (buffer of current source line)
441 * bufs2 (buffer of next source line)
442 * tabval (value to assign for current pixel)
443 * tab38 (excess value to give to neighboring 3/8 pixels)
444 * tab14 (excess value to give to neighboring 1/4 pixel)
445 * lastlineflag (0 if not last dest line, 1 if last dest line)
446 * Return: void
447 */
448 void
ditherToBinaryLineLUTLow(l_uint32 * lined,l_int32 w,l_uint32 * bufs1,l_uint32 * bufs2,l_int32 * tabval,l_int32 * tab38,l_int32 * tab14,l_int32 lastlineflag)449 ditherToBinaryLineLUTLow(l_uint32 *lined,
450 l_int32 w,
451 l_uint32 *bufs1,
452 l_uint32 *bufs2,
453 l_int32 *tabval,
454 l_int32 *tab38,
455 l_int32 *tab14,
456 l_int32 lastlineflag)
457 {
458 l_int32 j;
459 l_int32 oval, tab38val, tab14val;
460 l_uint8 rval, bval, dval;
461
462 if (lastlineflag == 0) {
463 for (j = 0; j < w - 1; j++) {
464 oval = GET_DATA_BYTE(bufs1, j);
465 if (tabval[oval])
466 SET_DATA_BIT(lined, j);
467 rval = GET_DATA_BYTE(bufs1, j + 1);
468 bval = GET_DATA_BYTE(bufs2, j);
469 dval = GET_DATA_BYTE(bufs2, j + 1);
470 tab38val = tab38[oval];
471 if (tab38val == 0)
472 continue;
473 tab14val = tab14[oval];
474 if (tab38val < 0) {
475 rval = L_MAX(0, rval + tab38val);
476 bval = L_MAX(0, bval + tab38val);
477 dval = L_MAX(0, dval + tab14val);
478 }
479 else {
480 rval = L_MIN(255, rval + tab38val);
481 bval = L_MIN(255, bval + tab38val);
482 dval = L_MIN(255, dval + tab14val);
483 }
484 SET_DATA_BYTE(bufs1, j + 1, rval);
485 SET_DATA_BYTE(bufs2, j, bval);
486 SET_DATA_BYTE(bufs2, j + 1, dval);
487 }
488
489 /* do last column: j = w - 1 */
490 oval = GET_DATA_BYTE(bufs1, j);
491 if (tabval[oval])
492 SET_DATA_BIT(lined, j);
493 bval = GET_DATA_BYTE(bufs2, j);
494 tab38val = tab38[oval];
495 if (tab38val < 0) {
496 bval = L_MAX(0, bval + tab38val);
497 SET_DATA_BYTE(bufs2, j, bval);
498 }
499 else if (tab38val > 0 ) {
500 bval = L_MIN(255, bval + tab38val);
501 SET_DATA_BYTE(bufs2, j, bval);
502 }
503 }
504 else { /* lastlineflag == 1 */
505 for (j = 0; j < w - 1; j++) {
506 oval = GET_DATA_BYTE(bufs1, j);
507 if (tabval[oval])
508 SET_DATA_BIT(lined, j);
509 rval = GET_DATA_BYTE(bufs1, j + 1);
510 tab38val = tab38[oval];
511 if (tab38val == 0)
512 continue;
513 if (tab38val < 0)
514 rval = L_MAX(0, rval + tab38val);
515 else
516 rval = L_MIN(255, rval + tab38val);
517 SET_DATA_BYTE(bufs1, j + 1, rval);
518 }
519
520 /* do last pixel: (i, j) = (h - 1, w - 1) */
521 oval = GET_DATA_BYTE(bufs1, j);
522 if (tabval[oval])
523 SET_DATA_BIT(lined, j);
524 }
525
526 return;
527 }
528
529
530 /*!
531 * make8To1DitherTables()
532 *
533 * Input: &tabval (value assigned to output pixel; 0 or 1)
534 * &tab38 (amount propagated to pixels left and below)
535 * &tab14 (amount propagated to pixel to left and down)
536 * lowerclip (values near 0 where the excess is not propagated)
537 * upperclip (values near 255 where the deficit is not propagated)
538 *
539 * Return: 0 if OK, 1 on error
540 */
541 l_int32
make8To1DitherTables(l_int32 ** ptabval,l_int32 ** ptab38,l_int32 ** ptab14,l_int32 lowerclip,l_int32 upperclip)542 make8To1DitherTables(l_int32 **ptabval,
543 l_int32 **ptab38,
544 l_int32 **ptab14,
545 l_int32 lowerclip,
546 l_int32 upperclip)
547 {
548 l_int32 i;
549 l_int32 *tabval, *tab38, *tab14;
550
551 PROCNAME("make8To1DitherTables");
552
553 if (!ptabval || !ptab38 || !ptab14)
554 return ERROR_INT("table ptrs not all defined", procName, 1);
555
556 /* 3 lookup tables: 1-bit value, (3/8)excess, and (1/4)excess */
557 if ((tabval = (l_int32 *)CALLOC(256, sizeof(l_int32))) == NULL)
558 return ERROR_INT("tabval not made", procName, 1);
559 if ((tab38 = (l_int32 *)CALLOC(256, sizeof(l_int32))) == NULL)
560 return ERROR_INT("tab38 not made", procName, 1);
561 if ((tab14 = (l_int32 *)CALLOC(256, sizeof(l_int32))) == NULL)
562 return ERROR_INT("tab14 not made", procName, 1);
563 *ptabval = tabval;
564 *ptab38 = tab38;
565 *ptab14 = tab14;
566
567 for (i = 0; i < 256; i++) {
568 if (i <= lowerclip) {
569 tabval[i] = 1;
570 tab38[i] = 0;
571 tab14[i] = 0;
572 }
573 else if (i < 128) {
574 tabval[i] = 1;
575 tab38[i] = (3 * i + 4) / 8;
576 tab14[i] = (i + 2) / 4;
577 }
578 else if (i < 255 - upperclip) {
579 tabval[i] = 0;
580 tab38[i] = (3 * (i - 255) + 4) / 8;
581 tab14[i] = ((i - 255) + 2) / 4;
582 }
583 else { /* i >= 255 - upperclip */
584 tabval[i] = 0;
585 tab38[i] = 0;
586 tab14[i] = 0;
587 }
588 }
589
590 return 0;
591 }
592
593
594 /*------------------------------------------------------------------*
595 * Dithering to 2 bpp *
596 *------------------------------------------------------------------*/
597 /*
598 * ditherTo2bppLow()
599 *
600 * Low-level function for doing Floyd-Steinberg error diffusion
601 * dithering from 8 bpp (datas) to 2 bpp (datad). Two source
602 * line buffers, bufs1 and bufs2, are provided, along with three
603 * 256-entry lookup tables: tabval gives the output pixel value,
604 * tab38 gives the extra (plus or minus) transferred to the pixels
605 * directly to the left and below, and tab14 gives the extra
606 * transferred to the diagonal below. The choice of 3/8 and 1/4
607 * is traditional but arbitrary when you use a lookup table; the
608 * only constraint is that the sum is 1. See other comments
609 * below and in grayquant.c.
610 */
611 void
ditherTo2bppLow(l_uint32 * datad,l_int32 w,l_int32 h,l_int32 wpld,l_uint32 * datas,l_int32 wpls,l_uint32 * bufs1,l_uint32 * bufs2,l_int32 * tabval,l_int32 * tab38,l_int32 * tab14)612 ditherTo2bppLow(l_uint32 *datad,
613 l_int32 w,
614 l_int32 h,
615 l_int32 wpld,
616 l_uint32 *datas,
617 l_int32 wpls,
618 l_uint32 *bufs1,
619 l_uint32 *bufs2,
620 l_int32 *tabval,
621 l_int32 *tab38,
622 l_int32 *tab14)
623 {
624 l_int32 i;
625 l_uint32 *lined;
626
627 /* do all lines except last line */
628 memcpy(bufs2, datas, 4 * wpls); /* prime the buffer */
629 for (i = 0; i < h - 1; i++) {
630 memcpy(bufs1, bufs2, 4 * wpls);
631 memcpy(bufs2, datas + (i + 1) * wpls, 4 * wpls);
632 lined = datad + i * wpld;
633 ditherTo2bppLineLow(lined, w, bufs1, bufs2, tabval, tab38, tab14, 0);
634 }
635
636 /* do last line */
637 memcpy(bufs1, bufs2, 4 * wpls);
638 lined = datad + (h - 1) * wpld;
639 ditherTo2bppLineLow(lined, w, bufs1, bufs2, tabval, tab38, tab14, 1);
640 return;
641 }
642
643
644 /*
645 * ditherTo2bppLineLow()
646 *
647 * Input: lined (ptr to beginning of dest line
648 * w (width of image in pixels)
649 * bufs1 (buffer of current source line)
650 * bufs2 (buffer of next source line)
651 * tabval (value to assign for current pixel)
652 * tab38 (excess value to give to neighboring 3/8 pixels)
653 * tab14 (excess value to give to neighboring 1/4 pixel)
654 * lastlineflag (0 if not last dest line, 1 if last dest line)
655 * Return: void
656 *
657 * Dispatches error diffusion dithering for
658 * a single line of the image. If lastlineflag == 0,
659 * both source buffers are used; otherwise, only bufs1
660 * is used. We use source buffers because the error
661 * is propagated into them, and we don't want to change
662 * the input src image.
663 *
664 * We break dithering out line by line to make it
665 * easier to combine functions like interpolative
666 * scaling and error diffusion dithering, as such a
667 * combination of operations obviates the need to
668 * generate a 2x grayscale image as an intermediary.
669 */
670 void
ditherTo2bppLineLow(l_uint32 * lined,l_int32 w,l_uint32 * bufs1,l_uint32 * bufs2,l_int32 * tabval,l_int32 * tab38,l_int32 * tab14,l_int32 lastlineflag)671 ditherTo2bppLineLow(l_uint32 *lined,
672 l_int32 w,
673 l_uint32 *bufs1,
674 l_uint32 *bufs2,
675 l_int32 *tabval,
676 l_int32 *tab38,
677 l_int32 *tab14,
678 l_int32 lastlineflag)
679 {
680 l_int32 j;
681 l_int32 oval, tab38val, tab14val;
682 l_uint8 rval, bval, dval;
683
684 if (lastlineflag == 0) {
685 for (j = 0; j < w - 1; j++) {
686 oval = GET_DATA_BYTE(bufs1, j);
687 SET_DATA_DIBIT(lined, j, tabval[oval]);
688 rval = GET_DATA_BYTE(bufs1, j + 1);
689 bval = GET_DATA_BYTE(bufs2, j);
690 dval = GET_DATA_BYTE(bufs2, j + 1);
691 tab38val = tab38[oval];
692 tab14val = tab14[oval];
693 if (tab38val < 0) {
694 rval = L_MAX(0, rval + tab38val);
695 bval = L_MAX(0, bval + tab38val);
696 dval = L_MAX(0, dval + tab14val);
697 }
698 else {
699 rval = L_MIN(255, rval + tab38val);
700 bval = L_MIN(255, bval + tab38val);
701 dval = L_MIN(255, dval + tab14val);
702 }
703 SET_DATA_BYTE(bufs1, j + 1, rval);
704 SET_DATA_BYTE(bufs2, j, bval);
705 SET_DATA_BYTE(bufs2, j + 1, dval);
706 }
707
708 /* do last column: j = w - 1 */
709 oval = GET_DATA_BYTE(bufs1, j);
710 SET_DATA_DIBIT(lined, j, tabval[oval]);
711 bval = GET_DATA_BYTE(bufs2, j);
712 tab38val = tab38[oval];
713 if (tab38val < 0)
714 bval = L_MAX(0, bval + tab38val);
715 else
716 bval = L_MIN(255, bval + tab38val);
717 SET_DATA_BYTE(bufs2, j, bval);
718 }
719 else { /* lastlineflag == 1 */
720 for (j = 0; j < w - 1; j++) {
721 oval = GET_DATA_BYTE(bufs1, j);
722 SET_DATA_DIBIT(lined, j, tabval[oval]);
723 rval = GET_DATA_BYTE(bufs1, j + 1);
724 tab38val = tab38[oval];
725 if (tab38val < 0)
726 rval = L_MAX(0, rval + tab38val);
727 else
728 rval = L_MIN(255, rval + tab38val);
729 SET_DATA_BYTE(bufs1, j + 1, rval);
730 }
731
732 /* do last pixel: (i, j) = (h - 1, w - 1) */
733 oval = GET_DATA_BYTE(bufs1, j);
734 SET_DATA_DIBIT(lined, j, tabval[oval]);
735 }
736
737 return;
738 }
739
740
741 /*!
742 * make8To2DitherTables()
743 *
744 * Input: &tabval (value assigned to output pixel; 0, 1, 2 or 3)
745 * &tab38 (amount propagated to pixels left and below)
746 * &tab14 (amount propagated to pixel to left and down)
747 * cliptoblack (values near 0 where the excess is not propagated)
748 * cliptowhite (values near 255 where the deficit is not propagated)
749 *
750 * Return: 0 if OK, 1 on error
751 */
752 l_int32
make8To2DitherTables(l_int32 ** ptabval,l_int32 ** ptab38,l_int32 ** ptab14,l_int32 cliptoblack,l_int32 cliptowhite)753 make8To2DitherTables(l_int32 **ptabval,
754 l_int32 **ptab38,
755 l_int32 **ptab14,
756 l_int32 cliptoblack,
757 l_int32 cliptowhite)
758 {
759 l_int32 i;
760 l_int32 *tabval, *tab38, *tab14;
761
762 PROCNAME("make8To2DitherTables");
763
764 /* 3 lookup tables: 2-bit value, (3/8)excess, and (1/4)excess */
765 if ((tabval = (l_int32 *)CALLOC(256, sizeof(l_int32))) == NULL)
766 return ERROR_INT("tabval not made", procName, 1);
767 if ((tab38 = (l_int32 *)CALLOC(256, sizeof(l_int32))) == NULL)
768 return ERROR_INT("tab38 not made", procName, 1);
769 if ((tab14 = (l_int32 *)CALLOC(256, sizeof(l_int32))) == NULL)
770 return ERROR_INT("tab14 not made", procName, 1);
771 *ptabval = tabval;
772 *ptab38 = tab38;
773 *ptab14 = tab14;
774
775 for (i = 0; i < 256; i++) {
776 if (i <= cliptoblack) {
777 tabval[i] = 0;
778 tab38[i] = 0;
779 tab14[i] = 0;
780 }
781 else if (i < 43) {
782 tabval[i] = 0;
783 tab38[i] = (3 * i + 4) / 8;
784 tab14[i] = (i + 2) / 4;
785 }
786 else if (i < 85) {
787 tabval[i] = 1;
788 tab38[i] = (3 * (i - 85) - 4) / 8;
789 tab14[i] = ((i - 85) - 2) / 4;
790 }
791 else if (i < 128) {
792 tabval[i] = 1;
793 tab38[i] = (3 * (i - 85) + 4) / 8;
794 tab14[i] = ((i - 85) + 2) / 4;
795 }
796 else if (i < 170) {
797 tabval[i] = 2;
798 tab38[i] = (3 * (i - 170) - 4) / 8;
799 tab14[i] = ((i - 170) - 2) / 4;
800 }
801 else if (i < 213) {
802 tabval[i] = 2;
803 tab38[i] = (3 * (i - 170) + 4) / 8;
804 tab14[i] = ((i - 170) + 2) / 4;
805 }
806 else if (i < 255 - cliptowhite) {
807 tabval[i] = 3;
808 tab38[i] = (3 * (i - 255) - 4) / 8;
809 tab14[i] = ((i - 255) - 2) / 4;
810 }
811 else { /* i >= 255 - cliptowhite */
812 tabval[i] = 3;
813 tab38[i] = 0;
814 tab14[i] = 0;
815 }
816 }
817
818 #if 0
819 for (i = 0; i < 256; i++)
820 fprintf(stderr, "tabval[%d] = %d, tab38[%d] = %d, tab14[%d] = %d\n",
821 i, tabval[i], i, tab38[i], i, tab14[i]);
822 #endif
823
824 return 0;
825 }
826
827
828 /*------------------------------------------------------------------*
829 * Simple thresholding to 2 bpp *
830 *------------------------------------------------------------------*/
831 /*
832 * thresholdTo2bppLow()
833 *
834 * Low-level function for thresholding from 8 bpp (datas) to
835 * 2 bpp (datad), using thresholds implicitly defined through @tab,
836 * a 256-entry lookup table that gives a 2-bit output value
837 * for each possible input.
838 *
839 * For each line, unroll the loop so that for each 32 bit src word,
840 * representing four consecutive 8-bit pixels, we compose one byte
841 * of output consisiting of four 2-bit pixels.
842 */
843 void
thresholdTo2bppLow(l_uint32 * datad,l_int32 h,l_int32 wpld,l_uint32 * datas,l_int32 wpls,l_int32 * tab)844 thresholdTo2bppLow(l_uint32 *datad,
845 l_int32 h,
846 l_int32 wpld,
847 l_uint32 *datas,
848 l_int32 wpls,
849 l_int32 *tab)
850 {
851 l_uint8 sval1, sval2, sval3, sval4, dval;
852 l_int32 i, j, k;
853 l_uint32 *lines, *lined;
854
855 for (i = 0; i < h; i++) {
856 lines = datas + i * wpls;
857 lined = datad + i * wpld;
858 for (j = 0; j < wpls; j++) {
859 k = 4 * j;
860 sval1 = GET_DATA_BYTE(lines, k);
861 sval2 = GET_DATA_BYTE(lines, k + 1);
862 sval3 = GET_DATA_BYTE(lines, k + 2);
863 sval4 = GET_DATA_BYTE(lines, k + 3);
864 dval = (tab[sval1] << 6) | (tab[sval2] << 4) |
865 (tab[sval3] << 2) | tab[sval4];
866 SET_DATA_BYTE(lined, j, dval);
867 }
868 }
869 return;
870 }
871
872
873 /*------------------------------------------------------------------*
874 * Simple thresholding to 4 bpp *
875 *------------------------------------------------------------------*/
876 /*
877 * thresholdTo4bppLow()
878 *
879 * Low-level function for thresholding from 8 bpp (datas) to
880 * 4 bpp (datad), using thresholds implicitly defined through @tab,
881 * a 256-entry lookup table that gives a 4-bit output value
882 * for each possible input.
883 *
884 * For each line, unroll the loop so that for each 32 bit src word,
885 * representing four consecutive 8-bit pixels, we compose two bytes
886 * of output consisiting of four 4-bit pixels.
887 */
888 void
thresholdTo4bppLow(l_uint32 * datad,l_int32 h,l_int32 wpld,l_uint32 * datas,l_int32 wpls,l_int32 * tab)889 thresholdTo4bppLow(l_uint32 *datad,
890 l_int32 h,
891 l_int32 wpld,
892 l_uint32 *datas,
893 l_int32 wpls,
894 l_int32 *tab)
895 {
896 l_uint8 sval1, sval2, sval3, sval4;
897 l_uint16 dval;
898 l_int32 i, j, k;
899 l_uint32 *lines, *lined;
900
901 for (i = 0; i < h; i++) {
902 lines = datas + i * wpls;
903 lined = datad + i * wpld;
904 for (j = 0; j < wpls; j++) {
905 k = 4 * j;
906 sval1 = GET_DATA_BYTE(lines, k);
907 sval2 = GET_DATA_BYTE(lines, k + 1);
908 sval3 = GET_DATA_BYTE(lines, k + 2);
909 sval4 = GET_DATA_BYTE(lines, k + 3);
910 dval = (tab[sval1] << 12) | (tab[sval2] << 8) |
911 (tab[sval3] << 4) | tab[sval4];
912 SET_DATA_TWO_BYTES(lined, j, dval);
913 }
914 }
915 return;
916 }
917
918
919