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

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