/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-24 07:01

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	871k	{
31	871k	stream_RLE_state const ss = (stream_RLE_state ) st;
32
33	871k	s_RLE_set_defaults_inline(ss);
34	871k	}
35
36		/* Initialize */
37		static int
38		s_RLE_init(stream_state * st)
39	871k	{
40	871k	stream_RLE_state const ss = (stream_RLE_state ) st;
41
42	871k	return s_RLE_init_inline(ss);
43	871k	}
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	47.6M	#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	47.6M	{
121	47.6M	stream_RLE_state const ss = (stream_RLE_state ) st;
122	47.6M	register const byte *p = pr->ptr;
123	47.6M	register byte *q = pw->ptr;
124	47.6M	const byte *plimit = pr->limit;
125	47.6M	byte *wlimit = pw->limit;
126	47.6M	ulong rleft = ss->record_left;
127	47.6M	int run_len = ss->run_len, ret = 0;
128	47.6M	byte n0 = ss->n0;
129	47.6M	byte n1 = ss->n1;
130	47.6M	byte n2 = ss->n2;
131	47.6M	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	47.6M	switch (ss->state) {
143	0	default:
144	0	dlprintf("Inconsistent state in s_RLE_process!\n");
145		/* fall through */
146	37.4M	case state_0:
147	22.1G	while (p != plimit) {
148	22.1G	if (run_len == 0) {
149		/* About to start a new run */
150	159M	n0 = *++p;
151	164M	case state_eq_0:
152	324M	run_len_0_n0_read:
153	324M	if (p == rlimit \|\| (p == plimit && last)) {
154		/* flush the record here, and restart */
155	13.1k	if (wlimit - q < 2){
156	133	ss->state = state_eq_0;
157		/* no_output_room_n0_read */
158	133	goto no_output_room;
159	133	}
160	12.9k	++q = 0; / Single literal */
161	12.9k	*++q = n0;
162	12.9k	rlimit = p + ss->record_size;
163	12.9k	continue;
164	13.1k	}
165	324M	if (p == plimit) {
166	5.26M	ss->state = state_eq_0;
167		/* no_more_data_n0_read */
168	5.26M	goto no_more_data;
169	5.26M	}
170	319M	n1 = *++p;
171	319M	case state_eq_01:
172	319M	if (p == rlimit \|\| (p == plimit && last)) {
173		/* flush the record here, and restart */
174	372k	if (wlimit - q < 3 - (n0 == n1)) {
175	2.24k	ss->state = state_eq_01;
176		/* no_output_room_n0n1_read */
177	2.24k	goto no_output_room;
178	2.24k	}
179	369k	if (n0 == n1) {
180	8.29k	++q = 0xff; / Repeat 2 */
181	8.29k	*++q = n0;
182	361k	} else {
183	361k	++q = 1; / Two literals */
184	361k	*++q = n0;
185	361k	*++q = n1;
186	361k	}
187	369k	run_len = 0;
188	369k	rlimit = p + ss->record_size;
189	369k	continue;
190	372k	}
191	318M	if (n0 == n1) {
192		/* Start of a repeated run */
193	282M	run_len = -2;
194	282M	} else {
195		/* A literal run of at least 1. */
196	36.7M	run_len = 1;
197	36.7M	ss->literals[0] = n0;
198	36.7M	n0 = n1;
199	36.7M	}
200	318M	if (p == plimit) {
201	3.63M	ss->state = state_0;
202	3.63M	goto no_more_data;
203	3.63M	}
204	22.0G	} else if (run_len > 0) {
205		/* We are in the middle of a run of literals */
206	1.50G	n1 = *++p;
207	1.51G	case state_gt_01:
208	1.51G	if (p == rlimit \|\| run_len == 126 \|\|
209	1.51G	(n0 == n1 && p == plimit && last)) {
210		/* flush the record here, and restart */
211		/* <len> <queue> n0 n1 */
212	9.67M	if (wlimit - q < run_len+3) {
213	269k	ss->state = state_gt_01;
214		/* no_output_room_gt_n0n1_read */
215	269k	goto no_output_room;
216	269k	}
217	9.40M	*++q = run_len+1;
218	9.40M	memcpy(q+1, ss->literals, run_len);
219	9.40M	q += run_len;
220	9.40M	*++q = n0;
221	9.40M	*++q = n1;
222	9.40M	run_len = 0;
223	9.40M	if (p == rlimit)
224	0	rlimit = p + ss->record_size;
225	9.40M	continue;
226	9.67M	}
227	1.50G	if (n0 == n1) {
228	167M	if (p == plimit) {
229	4.99M	ss->state = state_gt_01;
230		/* no_more_data_n0n1_read */
231	4.99M	goto no_more_data;
232	4.99M	}
233	162M	n2 = *++p;
234	162M	case state_gt_012:
235	162M	if (p == rlimit \|\| run_len == 125) {
236		/* flush the record here, and restart */
237		/* <len> <queue> n0 n1 n2 */
238	1.21M	if (wlimit - q < run_len+4) {
239	3.60k	ss->state = state_gt_012;
240		/* no_output_room_n0n1n2_read */
241	3.60k	goto no_output_room;
242	3.60k	}
243	1.20M	*++q = run_len+2;
244	1.20M	memcpy(q+1, ss->literals, run_len);
245	1.20M	q += run_len;
246	1.20M	*++q = n0;
247	1.20M	*++q = n1;
248	1.20M	*++q = n2;
249	1.20M	run_len = 0;
250	1.20M	if (p == rlimit)
251	0	rlimit = p + ss->record_size;
252	1.20M	continue;
253	1.21M	}
254	161M	if (n0 != n2) {
255		/* Stick with a literal run */
256	135M	ss->literals[run_len++] = n0;
257	135M	ss->literals[run_len++] = n1;
258	135M	n0 = n2;
259	135M	} else {
260		/* Flush current run, start a repeated run */
261		/* <len> <queue> */
262	25.8M	if (wlimit - q < run_len+1) {
263	110k	ss->state = state_gt_012;
264		/* no_output_room_n0n1n2_read */
265	110k	goto no_output_room;
266	110k	}
267	25.7M	*++q = run_len-1;
268	25.7M	memcpy(q+1, ss->literals, run_len);
269	25.7M	q += run_len;
270	25.7M	run_len = -3; /* Repeated run of length 3 */
271	25.7M	}
272	1.33G	} else {
273		/* Continue literal run */
274	1.33G	ss->literals[run_len++] = n0;
275	1.33G	n0 = n1;
276	1.33G	}
277	20.4G	} else {
278		/* We are in the middle of a repeated run */
279		/* <n0 repeated -run_len times> */
280	20.4G	n1 = *++p;
281	20.4G	if (n0 == n1)
282	20.3G	run_len--; /* Repeated run got longer */
283	20.4G	case state_lt_01:
284	20.4G	if (n0 != n1 \|\| p == rlimit \|\| run_len == -128) {
285		/* flush the record here, and restart */
286	307M	if (wlimit - q < 2) {
287	36.5k	ss->state = state_lt_01;
288		/* no_output_room_lt_n0n1_read */
289	36.5k	goto no_output_room;
290	36.5k	}
291	307M	++q = 257+run_len; / Repeated run */
292	307M	*++q = n0;
293	307M	run_len = 0;
294	307M	if (p == rlimit)
295	0	rlimit = p + ss->record_size;
296	307M	if (n0 != n1) {
297	159M	n0 = n1;
298	159M	goto run_len_0_n0_read;
299	159M	}
300	307M	}
301	20.4G	}
302	22.1G	}
303		/* n1 is never valid here */
304
305	33.3M	if (last) {
306	604k	if (run_len == 0) {
307		/* EOD */
308	387k	if (wlimit - q < 1) {
309	868	ss->state = state_0;
310	868	goto no_output_room;
311	868	}
312	387k	} else if (run_len > 0) {
313		/* Flush literal run + EOD */
314	58.2k	if (wlimit - q < run_len+2) {
315	49.4k	ss->state = state_0;
316	49.4k	goto no_output_room;
317	49.4k	}
318	8.86k	*++q = run_len;
319	8.86k	memcpy(q+1, ss->literals, run_len);
320	8.86k	q += run_len;
321	8.86k	*++q = n0;
322	158k	} else if (run_len < 0) {
323		/* Flush repeated run + EOD */
324	158k	if (wlimit - q < 3) {
325	3.84k	ss->state = state_0;
326	3.84k	goto no_output_room;
327	3.84k	}
328	154k	++q = 257+run_len; / Repeated run */
329	154k	*++q = n0;
330	154k	}
331	550k	case state_eod_unmarked:
332	550k	if (!ss->omitEOD) {
333	455k	if (wlimit - q < 1) {
334	33	ss->state = state_eod_unmarked;
335	33	goto no_output_room;
336	33	}
337	455k	++q = 128; / EOD */
338	455k	}
339	550k	case state_eod:
340	550k	ss->run_len = 0;
341	550k	ss->state = state_0;
342	550k	pr->ptr = p;
343	550k	pw->ptr = q;
344	550k	ss->record_left = rlimit - p;
345	550k	debug_ate(pinit, p, qinit, q, EOFC);
346	550k	return EOFC;
347	550k	}
348	47.6M	}
349
350		/* Normal exit */
351	32.7M	ss->run_len = run_len;
352	32.7M	ss->state = state_0;
353	32.7M	ss->n0 = n0;
354	32.7M	ss->n1 = n1;
355	32.7M	pr->ptr = p;
356	32.7M	pw->ptr = q;
357	32.7M	ss->record_left = rlimit - p;
358	32.7M	debug_ate(pinit, p, qinit, q, 0);
359	32.7M	return 0;
360
361	476k	no_output_room:
362	476k	ret = 1;
363	14.3M	no_more_data:
364	14.3M	ss->n0 = n0;
365	14.3M	ss->n1 = n1;
366	14.3M	ss->n2 = n2;
367	14.3M	ss->run_len = run_len;
368	14.3M	pr->ptr = p;
369	14.3M	pw->ptr = q;
370	14.3M	ss->record_left = rlimit - p;
371	14.3M	debug_ate(pinit, p, qinit, q, ret);
372	14.3M	return ret;
373	476k	}
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		};