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