1 /* Copyright (C) 2001-2019 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,
8 modified or distributed except as expressly authorized under the terms
9 of the license contained in the file LICENSE in this distribution.
10
11 Refer to licensing information at http://www.artifex.com or contact
12 Artifex Software, Inc., 1305 Grant Avenue - Suite 200, Novato,
13 CA 94945, U.S.A., +1(415)492-9861, for further information.
14 */
15
16
17 /* CCITTFax encoding filter */
18 #include "stdio_.h" /* includes std.h */
19 #include "memory_.h"
20 #include "gdebug.h"
21 #include "strimpl.h"
22 #include "scf.h"
23 #include "scfx.h"
24
25 /* ------ Macros and support routines ------ */
26
27 /* Statistics */
28
29 #if defined(DEBUG) && !defined(GS_THREADSAFE)
30
31 typedef struct stats_runs_s {
32 ulong termination[64];
33 ulong make_up[41];
34 } stats_runs_t;
35 static stats_runs_t stats_white_runs, stats_black_runs;
36
37 #define COUNT_RUN(tab, i) (tab)[i]++;
38
39 static void
print_run_stats(const gs_memory_t * mem,const stats_runs_t * stats)40 print_run_stats(const gs_memory_t *mem, const stats_runs_t * stats)
41 {
42 int i;
43 ulong total;
44
45 for (i = 0, total = 0; i < 41; i++)
46 dmprintf1(mem, " %lu", stats->make_up[i]),
47 total += stats->make_up[i];
48 dmprintf1(mem, " total=%lu\n\t", total);
49 for (i = 0, total = 0; i < 64; i++)
50 dmprintf1(mem, " %lu", stats->termination[i]),
51 total += stats->termination[i];
52 dmprintf1(mem, " total=%lu\n", total);
53 }
54
55 #else /* !DEBUG || defined(GS_THREADSAFE) */
56
57 #define COUNT_RUN(cnt, i) DO_NOTHING
58
59 #endif /* DEBUG */
60
61 /* Put a run onto the output stream. */
62 /* Free variables: q, bits, bits_left. */
63
64 #define CF_PUT_RUN(ss, lenv, rt, stats)\
65 BEGIN\
66 cfe_run rr;\
67 \
68 if ( lenv >= 64 ) {\
69 hce_store_state();\
70 q = cf_put_long_run(ss, q, lenv, &rt);\
71 hce_load_state();\
72 lenv &= 63;\
73 }\
74 rr = rt.termination[lenv];\
75 COUNT_RUN(stats.termination, lenv);\
76 hc_put_value(ss, q, rr.code, rr.code_length);\
77 END
78
79 static byte *
cf_put_long_run(stream_CFE_state * ss,byte * q,int lenv,const cf_runs * prt)80 cf_put_long_run(stream_CFE_state * ss, byte * q, int lenv, const cf_runs * prt)
81 {
82 hce_declare_state;
83 cfe_run rr;
84
85 #if defined(DEBUG) && !defined(GS_THREADSAFE)
86 stats_runs_t *pstats =
87 (prt == &cf_white_runs ? &stats_white_runs : &stats_black_runs);
88
89 #endif
90
91 hce_load_state();
92 while (lenv >= 2560 + 64) {
93 rr = prt->make_up[40];
94 COUNT_RUN(pstats->make_up, 40);
95 hc_put_value(ss, q, rr.code, rr.code_length);
96 lenv -= 2560;
97 }
98 rr = prt->make_up[lenv >> 6];
99 COUNT_RUN(pstats->make_up, lenv >> 6);
100 hc_put_value(ss, q, rr.code, rr.code_length);
101 hce_store_state();
102 return q;
103 }
104
105 #define CF_PUT_WHITE_RUN(ss, lenv)\
106 CF_PUT_RUN(ss, lenv, cf_white_runs, stats_white_runs)
107
108 #define CF_PUT_BLACK_RUN(ss, lenv)\
109 CF_PUT_RUN(ss, lenv, cf_black_runs, stats_black_runs)
110
111 /* ------ CCITTFaxEncode ------ */
112
113 private_st_CFE_state();
114
115 static void s_CFE_release(stream_state *);
116
117 /* Set default parameter values. */
118 static void
s_CFE_set_defaults(register stream_state * st)119 s_CFE_set_defaults(register stream_state * st)
120 {
121 stream_CFE_state *const ss = (stream_CFE_state *) st;
122
123 s_CFE_set_defaults_inline(ss);
124 }
125
126 /* Initialize CCITTFaxEncode filter */
127 static int
s_CFE_init(register stream_state * st)128 s_CFE_init(register stream_state * st)
129 {
130 stream_CFE_state *const ss = (stream_CFE_state *) st;
131 int columns = ss->Columns;
132
133 /*
134 * The worst case for encoding is alternating white and black pixels.
135 * For 1-D encoding, the worst case is 9 bits per 2 pixels; for 2-D
136 * (horizontal), 12 bits per 2 pixels. However, for 2D vertical encoding
137 * an offset 3 vertically encoded requires 7 bits of encoding. So we need
138 * to allow 14 bits for this, not 12 (see bug 696413). To fill out a scan line,
139 * we may add up to 6 12-bit EOL codes.
140 */
141 int code_bytes =
142 (((columns * (ss->K == 0 ? 9 : 14)) + 15) >> 4) + 20; /* add slop */
143 int raster = ss->raster =
144 ROUND_UP((columns + 7) >> 3, ss->DecodedByteAlign);
145
146 s_hce_init_inline(ss);
147 ss->lbuf = ss->lprev = ss->lcode = 0; /* in case we have to release */
148 if (columns > cfe_max_width)
149 return ERRC;
150 /****** WRONG ******/
151 /* Because skip_white_pixels can look as many as 4 bytes ahead, */
152 /* we need to allow 4 extra bytes at the end of the row buffers. */
153 ss->lbuf = gs_alloc_bytes(st->memory, raster + 4, "CFE lbuf");
154 ss->lcode = gs_alloc_bytes(st->memory, code_bytes, "CFE lcode");
155 if (ss->lbuf == 0 || ss->lcode == 0) {
156 s_CFE_release(st);
157 return ERRC;
158 /****** WRONG ******/
159 }
160 memset(ss->lbuf + raster, 0, 4); /* to pacify Valgrind */
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 + 4); /* +4 to pacify Valgrind */
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 static 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 static void cf_encode_1d(stream_CFE_state *, const byte *,
196 stream_cursor_write *);
197 static void cf_encode_2d(stream_CFE_state *, const byte *,
198 stream_cursor_write *, const byte *);
199 static 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_debug2m('w', ss->memory, "[w]CFE: read_count = %d, write_count=%d,\n",
214 ss->read_count, ss->write_count);
215 if_debug6m('w', ss->memory, " 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_debug2m('w', ss->memory, "[w2]new %d-D row, k_left=%d\n",
274 (ss->k_left == 1 ? 1 : 2), ss->k_left);
275 } else {
276 if_debug1m('w', ss->memory, "[w%d]new row\n", (ss->K < 0 ? 2 : 1));
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_debug9m('w', ss->memory, "[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 #if defined(DEBUG) && !defined(GS_THREADSAFE)
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 dmlputs(ss->memory, "[w]white runs:");
374 print_run_stats(ss->memory, &stats_white_runs);
375 dmlputs(ss->memory, "[w]black runs:");
376 print_run_stats(ss->memory, &stats_black_runs);
377 }
378 #endif
379 return status;
380 }
381
382 /* Encode a 1-D scan line. */
383 /* Attempt to stop coverity thinking skip_white_pixels() taints lbuf:*/
384 /* coverity[ -tainted_data_argument : arg-1 ] */
385 static void
cf_encode_1d(stream_CFE_state * ss,const byte * lbuf,stream_cursor_write * pw)386 cf_encode_1d(stream_CFE_state * ss, const byte * lbuf, stream_cursor_write * pw)
387 {
388 uint count = ss->raster << 3;
389 byte *q = pw->ptr;
390 int end_count = -ss->Columns & 7;
391 int rlen;
392
393 hce_declare_state;
394 const byte *p = lbuf;
395 byte invert = (ss->BlackIs1 ? 0 : 0xff);
396
397 /* Invariant: data = p[-1] ^ invert. */
398 uint data = *p++ ^ invert;
399
400 hce_load_state();
401 while (count != end_count) {
402 /* Parse a white run. */
403 skip_white_pixels(data, p, count, invert, rlen);
404 CF_PUT_WHITE_RUN(ss, rlen);
405 if (count == end_count)
406 break;
407 /* Parse a black run. */
408 skip_black_pixels(data, p, count, invert, rlen);
409 CF_PUT_BLACK_RUN(ss, rlen);
410 }
411 hce_store_state();
412 pw->ptr = q;
413 }
414
415 /* Encode a 2-D scan line. */
416 /* coverity[ -tainted_data_argument : arg-1 ] */
417 static void
cf_encode_2d(stream_CFE_state * ss,const byte * lbuf,stream_cursor_write * pw,const byte * lprev)418 cf_encode_2d(stream_CFE_state * ss, const byte * lbuf, stream_cursor_write * pw,
419 const byte * lprev)
420 {
421 byte invert_white = (ss->BlackIs1 ? 0 : 0xff);
422 byte invert = invert_white;
423 uint count = ss->raster << 3;
424 int end_count = -ss->Columns & 7;
425 const byte *p = lbuf;
426 byte *q = pw->ptr;
427 uint data = *p++ ^ invert;
428
429 hce_declare_state;
430 /*
431 * In order to handle the nominal 'changing white' at the beginning of
432 * each scan line, we need to suppress the test for an initial black bit
433 * in the reference line when we are at the very beginning of the scan
434 * line. To avoid an extra test, we use two different mask tables.
435 */
436 static const byte initial_count_bit[8] =
437 {
438 0, 1, 2, 4, 8, 0x10, 0x20, 0x40
439 };
440 static const byte further_count_bit[8] =
441 {
442 0x80, 1, 2, 4, 8, 0x10, 0x20, 0x40
443 };
444 const byte *count_bit = initial_count_bit;
445
446 hce_load_state();
447 while (count != end_count) {
448 /*
449 * If invert == invert_white, white and black have their
450 * correct meanings; if invert == ~invert_white,
451 * black and white are interchanged.
452 */
453 uint a0 = count;
454 uint a1;
455
456 #define b1 (a1 - diff) /* only for printing */
457 int diff;
458 uint prev_count = count;
459 const byte *prev_p = p - lbuf + lprev;
460 byte prev_data = prev_p[-1] ^ invert;
461 int rlen;
462
463 /* Find the a1 and b1 transitions. */
464 skip_white_pixels(data, p, count, invert, rlen);
465 a1 = count;
466 if ((prev_data & count_bit[prev_count & 7])) {
467 /* Look for changing white first. */
468 skip_black_pixels(prev_data, prev_p, prev_count, invert, rlen);
469 }
470 count_bit = further_count_bit; /* no longer at beginning */
471 pass:
472 if (prev_count != end_count)
473 skip_white_pixels(prev_data, prev_p, prev_count, invert, rlen);
474 diff = a1 - prev_count; /* i.e., logical b1 - a1 */
475 /* In all the comparisons below, remember that count */
476 /* runs downward, not upward, so the comparisons are */
477 /* reversed. */
478 if (diff <= -2) {
479 /* Could be a pass mode. Find b2. */
480 if (prev_count != end_count)
481 skip_black_pixels(prev_data, prev_p,
482 prev_count, invert, rlen);
483 if (prev_count > a1) {
484 /* Use pass mode. */
485 if_debug4m('W', ss->memory, "[W]pass: count = %d, a1 = %d, b1 = %d, new count = %d\n",
486 a0, a1, b1, prev_count);
487 hc_put_value(ss, q, cf2_run_pass_value, cf2_run_pass_length);
488 a0 = prev_count;
489 goto pass;
490 }
491 }
492 /* Check for vertical coding. */
493 if (diff <= 3 && diff >= -3) {
494 /* Use vertical coding. */
495 const cfe_run *cp = &cf2_run_vertical[diff + 3];
496
497 if_debug5m('W', ss->memory, "[W]vertical %d: count = %d, a1 = %d, b1 = %d, new count = %d\n",
498 diff, a0, a1, b1, count);
499 hc_put_code(ss, q, cp);
500 invert = ~invert; /* a1 polarity changes */
501 data ^= 0xff;
502 continue;
503 }
504 /* No luck, use horizontal coding. */
505 if (count != end_count)
506 skip_black_pixels(data, p, count, invert, rlen); /* find a2 */
507 hc_put_value(ss, q, cf2_run_horizontal_value,
508 cf2_run_horizontal_length);
509 a0 -= a1;
510 a1 -= count;
511 if (invert == invert_white) {
512 if_debug3m('W', ss->memory, "[W]horizontal: white = %d, black = %d, new count = %d\n",
513 a0, a1, count);
514 CF_PUT_WHITE_RUN(ss, a0);
515 CF_PUT_BLACK_RUN(ss, a1);
516 } else {
517 if_debug3m('W', ss->memory, "[W]horizontal: black = %d, white = %d, new count = %d\n",
518 a0, a1, count);
519 CF_PUT_BLACK_RUN(ss, a0);
520 CF_PUT_WHITE_RUN(ss, a1);
521 #undef b1
522 }
523 }
524 hce_store_state();
525 pw->ptr = q;
526 }
527
528 /* Stream template */
529 const stream_template s_CFE_template =
530 {
531 &st_CFE_state, s_CFE_init, s_CFE_process, 1, 1,
532 s_CFE_release, s_CFE_set_defaults
533 };
534