/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: 2026-08-08 08:00

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