/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 06:56

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