/src/ghostpdl/base/srle.c

Source
/* 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-11-16 07:40

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