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

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