1 /* Copyright (C) 1992, 1995, 1997, 1998, 1999 artofcode LLC. All rights reserved.
2
3 This program is free software; you can redistribute it and/or modify it
4 under the terms of the GNU General Public License as published by the
5 Free Software Foundation; either version 2 of the License, or (at your
6 option) any later version.
7
8 This program is distributed in the hope that it will be useful, but
9 WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 General Public License for more details.
12
13 You should have received a copy of the GNU General Public License along
14 with this program; if not, write to the Free Software Foundation, Inc.,
15 59 Temple Place, Suite 330, Boston, MA, 02111-1307.
16
17 */
18
19 /*$Id: scfe.c,v 1.2.6.1.2.1 2003/01/17 00:49:05 giles Exp $ */
20 /* CCITTFax encoding filter */
21 #include "stdio_.h" /* includes std.h */
22 #include "memory_.h"
23 #include "gdebug.h"
24 #include "strimpl.h"
25 #include "scf.h"
26 #include "scfx.h"
27
28 /* ------ Macros and support routines ------ */
29
30 /* Statistics */
31
32 #ifdef DEBUG
33
34 typedef struct stats_runs_s {
35 ulong termination[64];
36 ulong make_up[41];
37 } stats_runs_t;
38 private stats_runs_t stats_white_runs, stats_black_runs;
39
40 #define COUNT_RUN(tab, i) (tab)[i]++;
41
42 private void
print_run_stats(const stats_runs_t * stats)43 print_run_stats(const stats_runs_t * stats)
44 {
45 int i;
46 ulong total;
47
48 for (i = 0, total = 0; i < 41; i++)
49 dprintf1(" %lu", stats->make_up[i]),
50 total += stats->make_up[i];
51 dprintf1(" total=%lu\n\t", total);
52 for (i = 0, total = 0; i < 64; i++)
53 dprintf1(" %lu", stats->termination[i]),
54 total += stats->termination[i];
55 dprintf1(" total=%lu\n", total);
56 }
57
58 #else /* !DEBUG */
59
60 #define COUNT_RUN(cnt, i) DO_NOTHING
61
62 #endif /* DEBUG */
63
64 /* Put a run onto the output stream. */
65 /* Free variables: q, bits, bits_left. */
66
67 #define CF_PUT_RUN(ss, lenv, rt, stats)\
68 BEGIN\
69 cfe_run rr;\
70 \
71 if ( lenv >= 64 ) {\
72 hce_store_state();\
73 q = cf_put_long_run(ss, q, lenv, &rt);\
74 hce_load_state();\
75 lenv &= 63;\
76 }\
77 rr = rt.termination[lenv];\
78 COUNT_RUN(stats.termination, lenv);\
79 hc_put_value(ss, q, rr.code, rr.code_length);\
80 END
81
82 private byte *
cf_put_long_run(stream_CFE_state * ss,byte * q,int lenv,const cf_runs * prt)83 cf_put_long_run(stream_CFE_state * ss, byte * q, int lenv, const cf_runs * prt)
84 {
85 hce_declare_state;
86 cfe_run rr;
87
88 #ifdef DEBUG
89 stats_runs_t *pstats =
90 (prt == &cf_white_runs ? &stats_white_runs : &stats_black_runs);
91
92 #endif
93
94 hce_load_state();
95 while (lenv >= 2560 + 64) {
96 rr = prt->make_up[40];
97 COUNT_RUN(pstats->make_up, 40);
98 hc_put_value(ss, q, rr.code, rr.code_length);
99 lenv -= 2560;
100 }
101 rr = prt->make_up[lenv >> 6];
102 COUNT_RUN(pstats->make_up, lenv >> 6);
103 hc_put_value(ss, q, rr.code, rr.code_length);
104 hce_store_state();
105 return q;
106 }
107
108 #define CF_PUT_WHITE_RUN(ss, lenv)\
109 CF_PUT_RUN(ss, lenv, cf_white_runs, stats_white_runs)
110
111 #define CF_PUT_BLACK_RUN(ss, lenv)\
112 CF_PUT_RUN(ss, lenv, cf_black_runs, stats_black_runs)
113
114 /* ------ CCITTFaxEncode ------ */
115
116 private_st_CFE_state();
117
118 private void s_CFE_release(P1(stream_state *));
119
120 /* Set default parameter values. */
121 private void
s_CFE_set_defaults(register stream_state * st)122 s_CFE_set_defaults(register stream_state * st)
123 {
124 stream_CFE_state *const ss = (stream_CFE_state *) st;
125
126 s_CFE_set_defaults_inline(ss);
127 }
128
129 /* Initialize CCITTFaxEncode filter */
130 private int
s_CFE_init(register stream_state * st)131 s_CFE_init(register stream_state * st)
132 {
133 stream_CFE_state *const ss = (stream_CFE_state *) st;
134 int columns = ss->Columns;
135
136 /*
137 * The worst case for encoding is alternating white and black pixels.
138 * For 1-D encoding, the worst case is 9 bits per 2 pixels; for 2-D
139 * (horizontal), 12 bits per 2 pixels. To fill out a scan line,
140 * we may add up to 6 12-bit EOL codes.
141 */
142 int code_bytes =
143 ((columns * (ss->K == 0 ? 9 : 12)) >> 4) + 20; /* add slop */
144 int raster = ss->raster =
145 ROUND_UP((columns + 7) >> 3, ss->DecodedByteAlign);
146
147 s_hce_init_inline(ss);
148 ss->lbuf = ss->lprev = ss->lcode = 0; /* in case we have to release */
149 if (columns > cfe_max_width)
150 return ERRC;
151 /****** WRONG ******/
152 /* Because skip_white_pixels can look as many as 4 bytes ahead, */
153 /* we need to allow 4 extra bytes at the end of the row buffers. */
154 ss->lbuf = gs_alloc_bytes(st->memory, raster + 4, "CFE lbuf");
155 ss->lcode = gs_alloc_bytes(st->memory, code_bytes, "CFE lcode");
156 if (ss->lbuf == 0 || ss->lcode == 0) {
157 s_CFE_release(st);
158 return ERRC;
159 /****** WRONG ******/
160 }
161 if (ss->K != 0) {
162 ss->lprev = gs_alloc_bytes(st->memory, raster + 4, "CFE lprev");
163 if (ss->lprev == 0) {
164 s_CFE_release(st);
165 return ERRC;
166 /****** WRONG ******/
167 }
168 /* Clear the initial reference line for 2-D encoding. */
169 /* Make sure it is terminated properly. */
170 memset(ss->lprev, (ss->BlackIs1 ? 0 : 0xff), raster);
171 if (columns & 7)
172 ss->lprev[raster - 1] ^= 0x80 >> (columns & 7);
173 else
174 ss->lprev[raster] = ~ss->lprev[0];
175 }
176 ss->read_count = raster;
177 ss->write_count = 0;
178 ss->k_left = (ss->K > 0 ? 1 : ss->K);
179 ss->max_code_bytes = code_bytes;
180 return 0;
181 }
182
183 /* Release the filter. */
184 private void
s_CFE_release(stream_state * st)185 s_CFE_release(stream_state * st)
186 {
187 stream_CFE_state *const ss = (stream_CFE_state *) st;
188
189 gs_free_object(st->memory, ss->lprev, "CFE lprev(close)");
190 gs_free_object(st->memory, ss->lcode, "CFE lcode(close)");
191 gs_free_object(st->memory, ss->lbuf, "CFE lbuf(close)");
192 }
193
194 /* Flush the buffer */
195 private void cf_encode_1d(P3(stream_CFE_state *, const byte *,
196 stream_cursor_write *));
197 private void cf_encode_2d(P4(stream_CFE_state *, const byte *,
198 stream_cursor_write *, const byte *));
199 private int
s_CFE_process(stream_state * st,stream_cursor_read * pr,stream_cursor_write * pw,bool last)200 s_CFE_process(stream_state * st, stream_cursor_read * pr,
201 stream_cursor_write * pw, bool last)
202 {
203 stream_CFE_state *const ss = (stream_CFE_state *) st;
204 const byte *rlimit = pr->limit;
205 byte *wlimit = pw->limit;
206 int raster = ss->raster;
207 byte end_mask = 1 << (-ss->Columns & 7);
208 int status = 0;
209
210 for (;;) {
211 stream_cursor_write w;
212
213 if_debug2('w', "[w]CFE: read_count = %d, write_count=%d,\n",
214 ss->read_count, ss->write_count);
215 if_debug6('w', " pr = 0x%lx(%d)0x%lx, pw = 0x%lx(%d)0x%lx\n",
216 (ulong) pr->ptr, (int)(rlimit - pr->ptr), (ulong) rlimit,
217 (ulong) pw->ptr, (int)(wlimit - pw->ptr), (ulong) wlimit);
218 if (ss->write_count) {
219 /* Copy more of an encoded line to the caller. */
220 int wcount = wlimit - pw->ptr;
221 int ccount = min(wcount, ss->write_count);
222
223 memcpy(pw->ptr + 1, ss->lcode + ss->code_bytes - ss->write_count,
224 ccount);
225 pw->ptr += ccount;
226 if ((ss->write_count -= ccount) > 0) {
227 status = 1;
228 break;
229 }
230 }
231 if (ss->read_count) {
232 /* Copy more of an unencoded line from the caller. */
233 int rcount = rlimit - pr->ptr;
234 int ccount = min(rcount, ss->read_count);
235
236 if (rcount == 0 && last)
237 break;
238 memcpy(ss->lbuf + raster - ss->read_count,
239 pr->ptr + 1, ccount);
240 pr->ptr += ccount;
241 if ((ss->read_count -= ccount) != 0)
242 break;
243 }
244 /*
245 * We have a full scan line in lbuf. Ensure that it ends with
246 * two polarity changes.
247 */
248 {
249 byte *end = ss->lbuf + raster - 1;
250 byte end_bit = *end & end_mask;
251 byte not_bit = end_bit ^ end_mask;
252
253 *end &= -end_mask;
254 if (end_mask == 1)
255 end[1] = (end_bit ? 0x40 : 0x80);
256 else if (end_mask == 2)
257 *end |= not_bit >> 1, end[1] = end_bit << 7;
258 else
259 *end |= (not_bit >> 1) | (end_bit >> 2);
260 }
261 /*
262 * Write the output directly to the caller's buffer if it's large
263 * enough, otherwise to our own buffer.
264 */
265 if (wlimit - pw->ptr >= ss->max_code_bytes) {
266 w = *pw;
267 } else {
268 w.ptr = ss->lcode - 1;
269 w.limit = w.ptr + ss->max_code_bytes;
270 }
271 #ifdef DEBUG
272 if (ss->K > 0) {
273 if_debug1('w', "[w]new row, k_left=%d\n",
274 ss->k_left);
275 } else {
276 if_debug0('w', "[w]new row\n");
277 }
278 #endif
279 /*
280 * Write an EOL (actually a "beginning of line") if requested.
281 */
282 if (ss->EndOfLine) {
283 const cfe_run *rp =
284 (ss->K <= 0 ? &cf_run_eol :
285 ss->k_left > 1 ? &cf2_run_eol_2d :
286 &cf2_run_eol_1d);
287 cfe_run run;
288
289 hce_declare_state;
290
291 hce_load_state();
292 if (ss->EncodedByteAlign) {
293 run = *rp;
294 /* Pad the run on the left */
295 /* so it winds up byte-aligned. */
296 run.code_length +=
297 (bits_left - run_eol_code_length) & 7;
298 if (run.code_length > 16) /* <= 23 */
299 bits_left -= run.code_length & 7,
300 run.code_length = 16;
301 rp = &run;
302 }
303 hc_put_code(ss, w.ptr, rp);
304 hce_store_state();
305 } else if (ss->EncodedByteAlign)
306 ss->bits_left &= ~7;
307 /* Encode the line. */
308 if (ss->K == 0)
309 cf_encode_1d(ss, ss->lbuf, &w); /* pure 1-D */
310 else if (ss->K < 0)
311 cf_encode_2d(ss, ss->lbuf, &w, ss->lprev); /* pure 2-D */
312 else if (--(ss->k_left)) /* mixed, use 2-D */
313 cf_encode_2d(ss, ss->lbuf, &w, ss->lprev);
314 else { /* mixed, use 1-D */
315 cf_encode_1d(ss, ss->lbuf, &w);
316 ss->k_left = ss->K;
317 }
318 /*
319 * If we didn't write directly to the client's buffer, schedule
320 * the output data to be written.
321 */
322 if (w.limit == wlimit)
323 pw->ptr = w.ptr;
324 else
325 ss->write_count = ss->code_bytes = w.ptr - (ss->lcode - 1);
326 if (ss->K != 0) {
327 /* In 2-D modes, swap the current and previous scan lines. */
328 byte *temp = ss->lbuf;
329
330 ss->lbuf = ss->lprev;
331 ss->lprev = temp;
332 }
333 /* Note that the input buffer needs refilling. */
334 ss->read_count = raster;
335 }
336 /*
337 * When we exit from the loop, we know that write_count = 0, and
338 * there is no line waiting to be processed in the input buffer.
339 */
340 if (last && status == 0) {
341 const cfe_run *rp =
342 (ss->K > 0 ? &cf2_run_eol_1d : &cf_run_eol);
343 int i = (!ss->EndOfBlock ? 0 : ss->K < 0 ? 2 : 6);
344 uint bits_to_write =
345 hc_bits_size - ss->bits_left + i * rp->code_length;
346 byte *q = pw->ptr;
347
348 hce_declare_state;
349
350 if (wlimit - q < (bits_to_write + 7) >> 3) {
351 status = 1;
352 goto out;
353 }
354 hce_load_state();
355 if (ss->EncodedByteAlign)
356 bits_left &= ~7;
357 while (--i >= 0)
358 hc_put_code(ss, q, rp);
359 /* Force out the last byte or bytes. */
360 pw->ptr = hc_put_last_bits((stream_hc_state *) ss, q);
361 }
362 out:
363 if_debug9('w', "[w]CFE exit %d: read_count = %d, write_count = %d,\n pr = 0x%lx(%d)0x%lx; pw = 0x%lx(%d)0x%lx\n",
364 status, ss->read_count, ss->write_count,
365 (ulong) pr->ptr, (int)(rlimit - pr->ptr), (ulong) rlimit,
366 (ulong) pw->ptr, (int)(wlimit - pw->ptr), (ulong) wlimit);
367 #ifdef DEBUG
368 if (pr->ptr > rlimit || pw->ptr > wlimit) {
369 lprintf("Pointer overrun!\n");
370 status = ERRC;
371 }
372 if (gs_debug_c('w') && status == 1) {
373 dlputs("[w]white runs:");
374 print_run_stats(&stats_white_runs);
375 dlputs("[w]black runs:");
376 print_run_stats(&stats_black_runs);
377 }
378 #endif
379 return status;
380 }
381
382 /* Encode a 1-D scan line. */
383 private void
cf_encode_1d(stream_CFE_state * ss,const byte * lbuf,stream_cursor_write * pw)384 cf_encode_1d(stream_CFE_state * ss, const byte * lbuf, stream_cursor_write * pw)
385 {
386 uint count = ss->raster << 3;
387 byte *q = pw->ptr;
388 int end_count = -ss->Columns & 7;
389 int rlen;
390
391 hce_declare_state;
392 const byte *p = lbuf;
393 byte invert = (ss->BlackIs1 ? 0 : 0xff);
394
395 /* Invariant: data = p[-1] ^ invert. */
396 uint data = *p++ ^ invert;
397
398 hce_load_state();
399 while (count != end_count) {
400 /* Parse a white run. */
401 skip_white_pixels(data, p, count, invert, rlen);
402 CF_PUT_WHITE_RUN(ss, rlen);
403 if (count == end_count)
404 break;
405 /* Parse a black run. */
406 skip_black_pixels(data, p, count, invert, rlen);
407 CF_PUT_BLACK_RUN(ss, rlen);
408 }
409 hce_store_state();
410 pw->ptr = q;
411 }
412
413 /* Encode a 2-D scan line. */
414 private void
cf_encode_2d(stream_CFE_state * ss,const byte * lbuf,stream_cursor_write * pw,const byte * lprev)415 cf_encode_2d(stream_CFE_state * ss, const byte * lbuf, stream_cursor_write * pw,
416 const byte * lprev)
417 {
418 byte invert_white = (ss->BlackIs1 ? 0 : 0xff);
419 byte invert = invert_white;
420 uint count = ss->raster << 3;
421 int end_count = -ss->Columns & 7;
422 const byte *p = lbuf;
423 byte *q = pw->ptr;
424 uint data = *p++ ^ invert;
425
426 hce_declare_state;
427 /*
428 * In order to handle the nominal 'changing white' at the beginning of
429 * each scan line, we need to suppress the test for an initial black bit
430 * in the reference line when we are at the very beginning of the scan
431 * line. To avoid an extra test, we use two different mask tables.
432 */
433 static const byte initial_count_bit[8] =
434 {
435 0, 1, 2, 4, 8, 0x10, 0x20, 0x40
436 };
437 static const byte further_count_bit[8] =
438 {
439 0x80, 1, 2, 4, 8, 0x10, 0x20, 0x40
440 };
441 const byte *count_bit = initial_count_bit;
442
443 hce_load_state();
444 while (count != end_count) {
445 /*
446 * If invert == invert_white, white and black have their
447 * correct meanings; if invert == ~invert_white,
448 * black and white are interchanged.
449 */
450 uint a0 = count;
451 uint a1;
452
453 #define b1 (a1 - diff) /* only for printing */
454 int diff;
455 uint prev_count = count;
456 const byte *prev_p = p - lbuf + lprev;
457 byte prev_data = prev_p[-1] ^ invert;
458 int rlen;
459
460 /* Find the a1 and b1 transitions. */
461 skip_white_pixels(data, p, count, invert, rlen);
462 a1 = count;
463 if ((prev_data & count_bit[prev_count & 7])) {
464 /* Look for changing white first. */
465 skip_black_pixels(prev_data, prev_p, prev_count, invert, rlen);
466 }
467 count_bit = further_count_bit; /* no longer at beginning */
468 pass:
469 if (prev_count != end_count)
470 skip_white_pixels(prev_data, prev_p, prev_count, invert, rlen);
471 diff = a1 - prev_count; /* i.e., logical b1 - a1 */
472 /* In all the comparisons below, remember that count */
473 /* runs downward, not upward, so the comparisons are */
474 /* reversed. */
475 if (diff <= -2) {
476 /* Could be a pass mode. Find b2. */
477 if (prev_count != end_count)
478 skip_black_pixels(prev_data, prev_p,
479 prev_count, invert, rlen);
480 if (prev_count > a1) {
481 /* Use pass mode. */
482 if_debug4('W', "[W]pass: count = %d, a1 = %d, b1 = %d, new count = %d\n",
483 a0, a1, b1, prev_count);
484 hc_put_value(ss, q, cf2_run_pass_value, cf2_run_pass_length);
485 a0 = prev_count;
486 goto pass;
487 }
488 }
489 /* Check for vertical coding. */
490 if (diff <= 3 && diff >= -3) {
491 /* Use vertical coding. */
492 const cfe_run *cp = &cf2_run_vertical[diff + 3];
493
494 if_debug5('W', "[W]vertical %d: count = %d, a1 = %d, b1 = %d, new count = %d\n",
495 diff, a0, a1, b1, count);
496 hc_put_code(ss, q, cp);
497 invert = ~invert; /* a1 polarity changes */
498 data ^= 0xff;
499 continue;
500 }
501 /* No luck, use horizontal coding. */
502 if (count != end_count)
503 skip_black_pixels(data, p, count, invert, rlen); /* find a2 */
504 hc_put_value(ss, q, cf2_run_horizontal_value,
505 cf2_run_horizontal_length);
506 a0 -= a1;
507 a1 -= count;
508 if (invert == invert_white) {
509 if_debug3('W', "[W]horizontal: white = %d, black = %d, new count = %d\n",
510 a0, a1, count);
511 CF_PUT_WHITE_RUN(ss, a0);
512 CF_PUT_BLACK_RUN(ss, a1);
513 } else {
514 if_debug3('W', "[W]horizontal: black = %d, white = %d, new count = %d\n",
515 a0, a1, count);
516 CF_PUT_BLACK_RUN(ss, a0);
517 CF_PUT_WHITE_RUN(ss, a1);
518 #undef b1
519 }
520 }
521 hce_store_state();
522 pw->ptr = q;
523 }
524
525 /* Stream template */
526 const stream_template s_CFE_template =
527 {
528 &st_CFE_state, s_CFE_init, s_CFE_process, 1, 1,
529 s_CFE_release, s_CFE_set_defaults
530 };
531