/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:17

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