1 /* Copyright (C) 1995, 1996, 1997, 1998 Aladdin Enterprises. All rights reserved.
2
3 This software is provided AS-IS with no warranty, either express or
4 implied.
5
6 This software is distributed under license and may not be copied,
7 modified or distributed except as expressly authorized under the terms
8 of the license contained in the file LICENSE in this distribution.
9
10 For more information about licensing, please refer to
11 http://www.ghostscript.com/licensing/. For information on
12 commercial licensing, go to http://www.artifex.com/licensing/ or
13 contact Artifex Software, Inc., 101 Lucas Valley Road #110,
14 San Rafael, CA 94903, U.S.A., +1(415)492-9861.
15 */
16
17 /* $Id: srle.c,v 1.4 2002/02/21 22:24:54 giles Exp $ */
18 /* RunLengthEncode filter */
19 #include "stdio_.h" /* includes std.h */
20 #include "memory_.h"
21 #include "strimpl.h"
22 #include "srlx.h"
23
24 /* ------ RunLengthEncode ------ */
25
26 private_st_RLE_state();
27
28 /* Set defaults */
29 private void
s_RLE_set_defaults(stream_state * st)30 s_RLE_set_defaults(stream_state * st)
31 {
32 stream_RLE_state *const ss = (stream_RLE_state *) st;
33
34 s_RLE_set_defaults_inline(ss);
35 }
36
37 /* Initialize */
38 private int
s_RLE_init(stream_state * st)39 s_RLE_init(stream_state * st)
40 {
41 stream_RLE_state *const ss = (stream_RLE_state *) st;
42
43 return s_RLE_init_inline(ss);
44 }
45
46 /* Process a buffer */
47 private int
s_RLE_process(stream_state * st,stream_cursor_read * pr,stream_cursor_write * pw,bool last)48 s_RLE_process(stream_state * st, stream_cursor_read * pr,
49 stream_cursor_write * pw, bool last)
50 {
51 stream_RLE_state *const ss = (stream_RLE_state *) st;
52 register const byte *p = pr->ptr;
53 register byte *q = pw->ptr;
54 const byte *rlimit = pr->limit;
55 byte *wlimit = pw->limit;
56 int status = 0;
57 ulong rleft = ss->record_left;
58
59 /*
60 * We thought that the Genoa CET demands that the output from this
61 * filter be not just legal, but optimal, so we went to the trouble
62 * of ensuring this. It turned out that this wasn't actually
63 * necessary, but we didn't want to change the code back.
64 *
65 * For optimal output, we can't just break runs at buffer
66 * boundaries: unless we hit a record boundary or the end of the
67 * input, we have to look ahead far enough to know that we aren't
68 * breaking a run prematurely.
69 */
70
71 /* Check for leftover output. */
72 copy:
73 if (ss->copy_left) {
74 uint rcount = rlimit - p;
75 uint wcount = wlimit - q;
76 uint count = ss->copy_left;
77
78 if (rcount < count)
79 count = rcount;
80 if (wcount < count)
81 count = wcount;
82 if (rleft < count)
83 count = rleft;
84 memcpy(q + 1, p + 1, count);
85 pr->ptr = p += count;
86 pw->ptr = q += count;
87 if ((ss->record_left = rleft -= count) == 0)
88 ss->record_left = rleft = ss->record_size;
89 if ((ss->copy_left -= count) != 0)
90 return (rcount == 0 ? 0 : 1);
91 }
92 while (p < rlimit) {
93 const byte *beg = p;
94 const byte *p1;
95 uint count = rlimit - p;
96 bool end = last;
97 byte next;
98
99 if (count > rleft)
100 count = rleft, end = true;
101 if (count > 128)
102 count = 128, end = true;
103 p1 = p + count - 1;
104 if (count < 3) {
105 if (!end || count == 0)
106 break; /* can't look ahead far enough */
107 if (count == 1) {
108 if (wlimit - q < 2) {
109 status = 1;
110 break;
111 }
112 *++q = 0;
113 } else { /* count == 2 */
114 if (p[1] == p[2]) {
115 if (wlimit - q < 2) {
116 status = 1;
117 break;
118 }
119 *++q = 255;
120 } else {
121 if (wlimit - q < 3) {
122 status = 1;
123 break;
124 }
125 *++q = 1;
126 *++q = p[1];
127 }
128 }
129 *++q = p1[1];
130 p = p1 + 1;
131 } else if ((next = p[1]) == p[2] && next == p[3]) {
132 if (wlimit - q < 2) {
133 status = 1;
134 break;
135 }
136 /* Recognize leading repeated byte */
137 do {
138 p++;
139 }
140 while (p < p1 && p[2] == next);
141 if (p == p1 && !end) {
142 p = beg; /* need to look ahead further */
143 break;
144 }
145 p++;
146 *++q = (byte) (257 - (p - beg));
147 *++q = next;
148 } else {
149 p1--;
150 while (p < p1 && (p[2] != p[1] || p[3] != p[1]))
151 p++;
152 if (p == p1) {
153 if (!end) {
154 p = beg; /* need to look ahead further */
155 break;
156 }
157 p += 2;
158 }
159 count = p - beg;
160 if (wlimit - q < count + 1) {
161 p = beg;
162 if (q >= wlimit) {
163 status = 1;
164 break;
165 }
166 /* Copy some now and some later. */
167 *++q = count - 1;
168 ss->copy_left = count;
169 goto copy;
170 }
171 *++q = count - 1;
172 memcpy(q + 1, beg + 1, count);
173 q += count;
174 }
175 rleft -= p - beg;
176 if (rleft == 0)
177 rleft = ss->record_size;
178 }
179 if (last && status == 0 && ss->EndOfData) {
180 if (q < wlimit)
181 *++q = 128;
182 else
183 status = 1;
184 }
185 pr->ptr = p;
186 pw->ptr = q;
187 ss->record_left = rleft;
188 return status;
189 }
190
191 /* Stream template */
192 const stream_template s_RLE_template = {
193 &st_RLE_state, s_RLE_init, s_RLE_process, 129, 2, NULL,
194 s_RLE_set_defaults, s_RLE_init
195 };
196