/src/ghostpdl/base/srle.c

Source (jump to first uncovered line)
/* Copyright (C) 2001-2023 Artifex Software, Inc.
   All Rights Reserved.

   This software is provided AS-IS with no warranty, either express or
   implied.

   This software is distributed under license and may not be copied,
   modified or distributed except as expressly authorized under the terms
   of the license contained in the file LICENSE in this distribution.

   Refer to licensing information at http://www.artifex.com or contact
   Artifex Software, Inc.,  39 Mesa Street, Suite 108A, San Francisco,
   CA 94129, USA, for further information.
*/


/* RunLengthEncode filter */
#include "stdio_.h"   /* includes std.h */
#include "memory_.h"
#include "strimpl.h"
#include "srlx.h"

/* ------ RunLengthEncode ------ */

private_st_RLE_state();

/* Set defaults */
static void
s_RLE_set_defaults(stream_state * st)
{
    stream_RLE_state *const ss = (stream_RLE_state *) st;

    s_RLE_set_defaults_inline(ss);
}

/* Initialize */
static int
s_RLE_init(stream_state * st)
{
    stream_RLE_state *const ss = (stream_RLE_state *) st;

    return s_RLE_init_inline(ss);
}

enum {
    /* Initial state - Nothing read (but may be mid run). */
    state_0,

    /* 0 bytes into a run, n0 read. */
    state_eq_0,

    /* 0 bytes into a run, n0 and n1 read. */
    state_eq_01,

    /* n bytes into a literal run, n0 and n1 read. */
    state_gt_01,

    /* n bytes into a literal run, n0,n1,n2 read. */
    state_gt_012,

    /* -n bytes into a repeated run, n0 and n1 read. */
    state_lt_01,

    /* We have reached the end of data, but not written the marker. */
    state_eod_unmarked,

    /* We have reached the end of data, and written the marker. */
    state_eod
};

#ifdef DEBUG_RLE
static void
debug_ate(const byte *p, const byte *plimit,
          const byte *q, const byte *qlimit,
          int ret)
{
    if (p != plimit) {
        dlprintf("CONSUMED");
        while (p != plimit) {
            dlprintf1(" %02x", *++p);
        }
        dlprintf("\n");
    }
    if (q != qlimit) {
        dlprintf("PRODUCED\n");
        while (q != qlimit) {
            int n = *++q;
            if (n == 128) {
                dlprintf1(" EOD(%02x)", n);
            } else if (n < 128) {
                dlprintf2(" %d(%02x)(", n+1, n);
                n++;
                while (n-- && q != qlimit) {
                    dlprintf1(" %02x", *++q);
                }
                if (n != -1) {
                    dlprintf1(" %d missing!", n+1);
                }
                dlprintf(" )\n");
            } else {
                dlprintf2(" %d(%02x) - ", 257-n, n);
                if (q == qlimit) {
                    dlprintf("WTF!");
                }
                dlprintf1("%02x\n", *++q);
            }
        }
        dlprintf("\n");
    }
    dlprintf1("RETURNED %d\n", ret);
}
#else
#define debug_ate(a,b,c,d,e) do { } while (0)
#endif

/* Process a buffer */
static int
s_RLE_process(stream_state * st, stream_cursor_read * pr,
              stream_cursor_write * pw, bool last)
{
    stream_RLE_state *const ss = (stream_RLE_state *) st;
    register const byte *p = pr->ptr;
    register byte *q = pw->ptr;
    const byte *plimit = pr->limit;
    byte *wlimit = pw->limit;
    ulong rleft = ss->record_left;
    int run_len = ss->run_len, ret = 0;
    byte n0 = ss->n0;
    byte n1 = ss->n1;
    byte n2 = ss->n2;
    const byte *rlimit = p + rleft;
#ifdef DEBUG_RLE
    const byte *pinit = p;
    const byte *qinit = q;
    static int entry = -1;

    entry++;
    dlprintf7("ENTERED(%d): avail_in=%d avail_out=%d run_len=%d n0=%02x n1=%02x n2=%02x\n",
              entry, plimit-p, wlimit-q, run_len, n0, n1, n2);
#endif

    switch (ss->state) {
    default:
        dlprintf("Inconsistent state in s_RLE_process!\n");
        /* fall through */
    case state_0:
        while (p != plimit) {
            if (run_len == 0) {
                /* About to start a new run */
                n0 = *++p;
    case state_eq_0:
run_len_0_n0_read:
                if (p == rlimit || (p == plimit && last)) {
                    /* flush the record here, and restart */
                    if (wlimit - q < 2){
                        ss->state = state_eq_0;
                        /* no_output_room_n0_read */
                        goto no_output_room;
                    }
                    *++q = 0; /* Single literal */
                    *++q = n0;
                    rlimit = p + ss->record_size;
                    continue;
                }
                if (p == plimit) {
                    ss->state = state_eq_0;
                    /* no_more_data_n0_read */
                    goto no_more_data;
                }
                n1 = *++p;
    case state_eq_01:
                if (p == rlimit || (p == plimit && last)) {
                    /* flush the record here, and restart */
                    if (wlimit - q < 3 - (n0 == n1)) {
                        ss->state = state_eq_01;
                        /* no_output_room_n0n1_read */
                        goto no_output_room;
                    }
                    if (n0 == n1) {
                        *++q = 0xff; /* Repeat 2 */
                        *++q = n0;
                    } else {
                        *++q = 1; /* Two literals */
                        *++q = n0;
                        *++q = n1;
                    }
                    run_len = 0;
                    rlimit = p + ss->record_size;
                    continue;
                }
                if (n0 == n1) {
                    /* Start of a repeated run */
                    run_len = -2;
                } else {
                    /* A literal run of at least 1. */
                    run_len = 1;
                    ss->literals[0] = n0;
                    n0 = n1;
                }
                if (p == plimit) {
                    ss->state = state_0;
                    goto no_more_data;
                }
            } else if (run_len > 0) {
                /* We are in the middle of a run of literals */
                n1 = *++p;
    case state_gt_01:
                if (p == rlimit || run_len == 126 ||
                    (n0 == n1 && p == plimit && last)) {
                    /* flush the record here, and restart */
                    /* <len> <queue> n0 n1 */
                        if (wlimit - q < run_len+3) {
                            ss->state = state_gt_01;
                            /* no_output_room_gt_n0n1_read */
                            goto no_output_room;
                        }
                    *++q = run_len+1;
                    memcpy(q+1, ss->literals, run_len);
                    q += run_len;
                    *++q = n0;
                    *++q = n1;
                    run_len = 0;
                    if (p == rlimit)
                        rlimit = p + ss->record_size;
                    continue;
                }
                if (n0 == n1) {
                    if (p == plimit) {
                        ss->state = state_gt_01;
                        /* no_more_data_n0n1_read */
                        goto no_more_data;
                    }
                    n2 = *++p;
    case state_gt_012:
                    if (p == rlimit || run_len == 125) {
                        /* flush the record here, and restart */
                        /* <len> <queue> n0 n1 n2 */
                        if (wlimit - q < run_len+4) {
                            ss->state = state_gt_012;
                            /* no_output_room_n0n1n2_read */
                            goto no_output_room;
                        }
                        *++q = run_len+2;
                        memcpy(q+1, ss->literals, run_len);
                        q += run_len;
                        *++q = n0;
                        *++q = n1;
                        *++q = n2;
                        run_len = 0;
                        if (p == rlimit)
                            rlimit = p + ss->record_size;
                        continue;
                    }
                    if (n0 != n2) {
                        /* Stick with a literal run */
                        ss->literals[run_len++] = n0;
                        ss->literals[run_len++] = n1;
                        n0 = n2;
                    } else {
                        /* Flush current run, start a repeated run */
                        /* <len> <queue> */
                        if (wlimit - q < run_len+1) {
                            ss->state = state_gt_012;
                            /* no_output_room_n0n1n2_read */
                            goto no_output_room;
                        }
                        *++q = run_len-1;
                        memcpy(q+1, ss->literals, run_len);
                        q += run_len;
                        run_len = -3; /* Repeated run of length 3 */
                    }
                } else {
                    /* Continue literal run */
                    ss->literals[run_len++] = n0;
                    n0 = n1;
                }
            } else {
                /* We are in the middle of a repeated run */
                /* <n0 repeated -run_len times> */
                n1 = *++p;
                if (n0 == n1)
                    run_len--; /* Repeated run got longer */
    case state_lt_01:
                if (n0 != n1 || p == rlimit || run_len == -128) {
                    /* flush the record here, and restart */
                    if (wlimit - q < 2) {
                        ss->state = state_lt_01;
                        /* no_output_room_lt_n0n1_read */
                        goto no_output_room;
                    }
                    *++q = 257+run_len; /* Repeated run */
                    *++q = n0;
                    run_len = 0;
                    if (p == rlimit)
                        rlimit = p + ss->record_size;
                    if (n0 != n1) {
                        n0 = n1;
                        goto run_len_0_n0_read;
                    }
                }
            }
        }
        /* n1 is never valid here */

        if (last) {
            if (run_len == 0) {
                /* EOD */
                if (wlimit - q < 1) {
                    ss->state = state_0;
                    goto no_output_room;
                }
            } else if (run_len > 0) {
                /* Flush literal run + EOD */
                if (wlimit - q < run_len+2) {
                    ss->state = state_0;
                    goto no_output_room;
                }
                *++q = run_len;
                memcpy(q+1, ss->literals, run_len);
                q += run_len;
                *++q = n0;
            } else if (run_len < 0) {
                /* Flush repeated run + EOD */
                if (wlimit - q < 3) {
                    ss->state = state_0;
                    goto no_output_room;
                }
                *++q = 257+run_len; /* Repeated run */
                *++q = n0;
            }
    case state_eod_unmarked:
            if (!ss->omitEOD) {
                if (wlimit - q < 1) {
                    ss->state = state_eod_unmarked;
                    goto no_output_room;
                }
                *++q = 128; /* EOD */
            }
    case state_eod:
            ss->run_len = 0;
            ss->state = state_0;
            pr->ptr = p;
            pw->ptr = q;
            ss->record_left = rlimit - p;
            debug_ate(pinit, p, qinit, q, EOFC);
            return EOFC;
        }
    }

    /* Normal exit */
    ss->run_len = run_len;
    ss->state = state_0;
    ss->n0 = n0;
    ss->n1 = n1;
    pr->ptr = p;
    pw->ptr = q;
    ss->record_left = rlimit - p;
    debug_ate(pinit, p, qinit, q, 0);
    return 0;

no_output_room:
    ret = 1;
no_more_data:
    ss->n0 = n0;
    ss->n1 = n1;
    ss->n2 = n2;
    ss->run_len = run_len;
    pr->ptr = p;
    pw->ptr = q;
    ss->record_left = rlimit - p;
    debug_ate(pinit, p, qinit, q, ret);
    return ret;
}

/* Stream template */
const stream_template s_RLE_template = {
    &st_RLE_state, s_RLE_init, s_RLE_process, 1, 129, NULL,
    s_RLE_set_defaults, s_RLE_init
};

Coverage Report

Created: 2025-06-10 07:26

Line	Count	Source (jump to first uncovered line)
1		/* Copyright (C) 2001-2023 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., 39 Mesa Street, Suite 108A, San Francisco,
13		CA 94129, USA, for further information.
14		*/
15
16
17		/* RunLengthEncode filter */
18		#include "stdio_.h" /* includes std.h */
19		#include "memory_.h"
20		#include "strimpl.h"
21		#include "srlx.h"
22
23		/* ------ RunLengthEncode ------ */
24
25		private_st_RLE_state();
26
27		/* Set defaults */
28		static void
29		s_RLE_set_defaults(stream_state * st)
30	39.1k	{
31	39.1k	stream_RLE_state const ss = (stream_RLE_state ) st;
32
33	39.1k	s_RLE_set_defaults_inline(ss);
34	39.1k	}
35
36		/* Initialize */
37		static int
38		s_RLE_init(stream_state * st)
39	39.1k	{
40	39.1k	stream_RLE_state const ss = (stream_RLE_state ) st;
41
42	39.1k	return s_RLE_init_inline(ss);
43	39.1k	}
44
45		enum {
46		/* Initial state - Nothing read (but may be mid run). */
47		state_0,
48
49		/* 0 bytes into a run, n0 read. */
50		state_eq_0,
51
52		/* 0 bytes into a run, n0 and n1 read. */
53		state_eq_01,
54
55		/* n bytes into a literal run, n0 and n1 read. */
56		state_gt_01,
57
58		/* n bytes into a literal run, n0,n1,n2 read. */
59		state_gt_012,
60
61		/* -n bytes into a repeated run, n0 and n1 read. */
62		state_lt_01,
63
64		/* We have reached the end of data, but not written the marker. */
65		state_eod_unmarked,
66
67		/* We have reached the end of data, and written the marker. */
68		state_eod
69		};
70
71		#ifdef DEBUG_RLE
72		static void
73		debug_ate(const byte p, const byte plimit,
74		const byte q, const byte qlimit,
75		int ret)
76		{
77		if (p != plimit) {
78		dlprintf("CONSUMED");
79		while (p != plimit) {
80		dlprintf1(" %02x", *++p);
81		}
82		dlprintf("\n");
83		}
84		if (q != qlimit) {
85		dlprintf("PRODUCED\n");
86		while (q != qlimit) {
87		int n = *++q;
88		if (n == 128) {
89		dlprintf1(" EOD(%02x)", n);
90		} else if (n < 128) {
91		dlprintf2(" %d(%02x)(", n+1, n);
92		n++;
93		while (n-- && q != qlimit) {
94		dlprintf1(" %02x", *++q);
95		}
96		if (n != -1) {
97		dlprintf1(" %d missing!", n+1);
98		}
99		dlprintf(" )\n");
100		} else {
101		dlprintf2(" %d(%02x) - ", 257-n, n);
102		if (q == qlimit) {
103		dlprintf("WTF!");
104		}
105		dlprintf1("%02x\n", *++q);
106		}
107		}
108		dlprintf("\n");
109		}
110		dlprintf1("RETURNED %d\n", ret);
111		}
112		#else
113	650k	#define debug_ate(a,b,c,d,e) do { } while (0)
114		#endif
115
116		/* Process a buffer */
117		static int
118		s_RLE_process(stream_state * st, stream_cursor_read * pr,
119		stream_cursor_write * pw, bool last)
120	650k	{
121	650k	stream_RLE_state const ss = (stream_RLE_state ) st;
122	650k	register const byte *p = pr->ptr;
123	650k	register byte *q = pw->ptr;
124	650k	const byte *plimit = pr->limit;
125	650k	byte *wlimit = pw->limit;
126	650k	ulong rleft = ss->record_left;
127	650k	int run_len = ss->run_len, ret = 0;
128	650k	byte n0 = ss->n0;
129	650k	byte n1 = ss->n1;
130	650k	byte n2 = ss->n2;
131	650k	const byte *rlimit = p + rleft;
132		#ifdef DEBUG_RLE
133		const byte *pinit = p;
134		const byte *qinit = q;
135		static int entry = -1;
136
137		entry++;
138		dlprintf7("ENTERED(%d): avail_in=%d avail_out=%d run_len=%d n0=%02x n1=%02x n2=%02x\n",
139		entry, plimit-p, wlimit-q, run_len, n0, n1, n2);
140		#endif
141
142	650k	switch (ss->state) {
143	0	default:
144	0	dlprintf("Inconsistent state in s_RLE_process!\n");
145		/* fall through */
146	524k	case state_0:
147	10.1M	while (p != plimit) {
148	9.66M	if (run_len == 0) {
149		/* About to start a new run */
150	61.6k	n0 = *++p;
151	155k	case state_eq_0:
152	563k	run_len_0_n0_read:
153	563k	if (p == rlimit \|\| (p == plimit && last)) {
154		/* flush the record here, and restart */
155	6	if (wlimit - q < 2){
156	0	ss->state = state_eq_0;
157		/* no_output_room_n0_read */
158	0	goto no_output_room;
159	0	}
160	6	++q = 0; / Single literal */
161	6	*++q = n0;
162	6	rlimit = p + ss->record_size;
163	6	continue;
164	6	}
165	563k	if (p == plimit) {
166	93.4k	ss->state = state_eq_0;
167		/* no_more_data_n0_read */
168	93.4k	goto no_more_data;
169	93.4k	}
170	469k	n1 = *++p;
171	469k	case state_eq_01:
172	469k	if (p == rlimit \|\| (p == plimit && last)) {
173		/* flush the record here, and restart */
174	11.9k	if (wlimit - q < 3 - (n0 == n1)) {
175	74	ss->state = state_eq_01;
176		/* no_output_room_n0n1_read */
177	74	goto no_output_room;
178	74	}
179	11.8k	if (n0 == n1) {
180	3	++q = 0xff; / Repeat 2 */
181	3	*++q = n0;
182	11.8k	} else {
183	11.8k	++q = 1; / Two literals */
184	11.8k	*++q = n0;
185	11.8k	*++q = n1;
186	11.8k	}
187	11.8k	run_len = 0;
188	11.8k	rlimit = p + ss->record_size;
189	11.8k	continue;
190	11.9k	}
191	457k	if (n0 == n1) {
192		/* Start of a repeated run */
193	109k	run_len = -2;
194	348k	} else {
195		/* A literal run of at least 1. */
196	348k	run_len = 1;
197	348k	ss->literals[0] = n0;
198	348k	n0 = n1;
199	348k	}
200	457k	if (p == plimit) {
201	28.0k	ss->state = state_0;
202	28.0k	goto no_more_data;
203	28.0k	}
204	9.59M	} else if (run_len > 0) {
205		/* We are in the middle of a run of literals */
206	2.12M	n1 = *++p;
207	2.16M	case state_gt_01:
208	2.16M	if (p == rlimit \|\| run_len == 126 \|\|
209	2.16M	(n0 == n1 && p == plimit && last)) {
210		/* flush the record here, and restart */
211		/* <len> <queue> n0 n1 */
212	5.42k	if (wlimit - q < run_len+3) {
213	4.01k	ss->state = state_gt_01;
214		/* no_output_room_gt_n0n1_read */
215	4.01k	goto no_output_room;
216	4.01k	}
217	1.40k	*++q = run_len+1;
218	1.40k	memcpy(q+1, ss->literals, run_len);
219	1.40k	q += run_len;
220	1.40k	*++q = n0;
221	1.40k	*++q = n1;
222	1.40k	run_len = 0;
223	1.40k	if (p == rlimit)
224	0	rlimit = p + ss->record_size;
225	1.40k	continue;
226	5.42k	}
227	2.15M	if (n0 == n1) {
228	447k	if (p == plimit) {
229	33.2k	ss->state = state_gt_01;
230		/* no_more_data_n0n1_read */
231	33.2k	goto no_more_data;
232	33.2k	}
233	414k	n2 = *++p;
234	414k	case state_gt_012:
235	414k	if (p == rlimit \|\| run_len == 125) {
236		/* flush the record here, and restart */
237		/* <len> <queue> n0 n1 n2 */
238	78	if (wlimit - q < run_len+4) {
239	32	ss->state = state_gt_012;
240		/* no_output_room_n0n1n2_read */
241	32	goto no_output_room;
242	32	}
243	46	*++q = run_len+2;
244	46	memcpy(q+1, ss->literals, run_len);
245	46	q += run_len;
246	46	*++q = n0;
247	46	*++q = n1;
248	46	*++q = n2;
249	46	run_len = 0;
250	46	if (p == rlimit)
251	0	rlimit = p + ss->record_size;
252	46	continue;
253	78	}
254	414k	if (n0 != n2) {
255		/* Stick with a literal run */
256	74.1k	ss->literals[run_len++] = n0;
257	74.1k	ss->literals[run_len++] = n1;
258	74.1k	n0 = n2;
259	339k	} else {
260		/* Flush current run, start a repeated run */
261		/* <len> <queue> */
262	339k	if (wlimit - q < run_len+1) {
263	9.88k	ss->state = state_gt_012;
264		/* no_output_room_n0n1n2_read */
265	9.88k	goto no_output_room;
266	9.88k	}
267	329k	*++q = run_len-1;
268	329k	memcpy(q+1, ss->literals, run_len);
269	329k	q += run_len;
270	329k	run_len = -3; /* Repeated run of length 3 */
271	329k	}
272	1.71M	} else {
273		/* Continue literal run */
274	1.71M	ss->literals[run_len++] = n0;
275	1.71M	n0 = n1;
276	1.71M	}
277	7.46M	} else {
278		/* We are in the middle of a repeated run */
279		/* <n0 repeated -run_len times> */
280	7.46M	n1 = *++p;
281	7.46M	if (n0 == n1)
282	7.05M	run_len--; /* Repeated run got longer */
283	7.46M	case state_lt_01:
284	7.46M	if (n0 != n1 \|\| p == rlimit \|\| run_len == -128) {
285		/* flush the record here, and restart */
286	431k	if (wlimit - q < 2) {
287	2.57k	ss->state = state_lt_01;
288		/* no_output_room_lt_n0n1_read */
289	2.57k	goto no_output_room;
290	2.57k	}
291	429k	++q = 257+run_len; / Repeated run */
292	429k	*++q = n0;
293	429k	run_len = 0;
294	429k	if (p == rlimit)
295	0	rlimit = p + ss->record_size;
296	429k	if (n0 != n1) {
297	408k	n0 = n1;
298	408k	goto run_len_0_n0_read;
299	408k	}
300	429k	}
301	7.46M	}
302	9.66M	}
303		/* n1 is never valid here */
304
305	479k	if (last) {
306	22.5k	if (run_len == 0) {
307		/* EOD */
308	11.8k	if (wlimit - q < 1) {
309	30	ss->state = state_0;
310	30	goto no_output_room;
311	30	}
312	11.8k	} else if (run_len > 0) {
313		/* Flush literal run + EOD */
314	2.85k	if (wlimit - q < run_len+2) {
315	2.84k	ss->state = state_0;
316	2.84k	goto no_output_room;
317	2.84k	}
318	10	*++q = run_len;
319	10	memcpy(q+1, ss->literals, run_len);
320	10	q += run_len;
321	10	*++q = n0;
322	7.84k	} else if (run_len < 0) {
323		/* Flush repeated run + EOD */
324	7.84k	if (wlimit - q < 3) {
325	469	ss->state = state_0;
326	469	goto no_output_room;
327	469	}
328	7.37k	++q = 257+run_len; / Repeated run */
329	7.37k	*++q = n0;
330	7.37k	}
331	19.2k	case state_eod_unmarked:
332	19.2k	if (!ss->omitEOD) {
333	19.2k	if (wlimit - q < 1) {
334	0	ss->state = state_eod_unmarked;
335	0	goto no_output_room;
336	0	}
337	19.2k	++q = 128; / EOD */
338	19.2k	}
339	19.2k	case state_eod:
340	19.2k	ss->run_len = 0;
341	19.2k	ss->state = state_0;
342	19.2k	pr->ptr = p;
343	19.2k	pw->ptr = q;
344	19.2k	ss->record_left = rlimit - p;
345	19.2k	debug_ate(pinit, p, qinit, q, EOFC);
346	19.2k	return EOFC;
347	19.2k	}
348	650k	}
349
350		/* Normal exit */
351	457k	ss->run_len = run_len;
352	457k	ss->state = state_0;
353	457k	ss->n0 = n0;
354	457k	ss->n1 = n1;
355	457k	pr->ptr = p;
356	457k	pw->ptr = q;
357	457k	ss->record_left = rlimit - p;
358	457k	debug_ate(pinit, p, qinit, q, 0);
359	457k	return 0;
360
361	19.9k	no_output_room:
362	19.9k	ret = 1;
363	174k	no_more_data:
364	174k	ss->n0 = n0;
365	174k	ss->n1 = n1;
366	174k	ss->n2 = n2;
367	174k	ss->run_len = run_len;
368	174k	pr->ptr = p;
369	174k	pw->ptr = q;
370	174k	ss->record_left = rlimit - p;
371	174k	debug_ate(pinit, p, qinit, q, ret);
372	174k	return ret;
373	19.9k	}
374
375		/* Stream template */
376		const stream_template s_RLE_template = {
377		&st_RLE_state, s_RLE_init, s_RLE_process, 1, 129, NULL,
378		s_RLE_set_defaults, s_RLE_init
379		};