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

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