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