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