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

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