1 /* Copyright (C) 1996, 1997, 1998, 1999 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: spngp.c,v 1.4 2002/02/21 22:24:54 giles Exp $ */
18 /* PNG pixel prediction filters */
19 #include "memory_.h"
20 #include "strimpl.h"
21 #include "spngpx.h"
22
23 /* ------ PNGPredictorEncode/Decode ------ */
24
25 private_st_PNGP_state();
26
27 /* Define values for case dispatch. */
28 #define cNone 10
29 #define cSub 11
30 #define cUp 12
31 #define cAverage 13
32 #define cPaeth 14
33 #define cOptimum 15
34 #define cEncode -10
35 #define cDecode -4
36 private const byte pngp_case_needs_prev[] = {
37 0, 0, 1, 1, 1, 1
38 };
39
40 /* Set defaults */
41 private void
s_PNGP_set_defaults(stream_state * st)42 s_PNGP_set_defaults(stream_state * st)
43 {
44 stream_PNGP_state *const ss = (stream_PNGP_state *) st;
45
46 s_PNGP_set_defaults_inline(ss);
47 }
48
49 /* Common (re)initialization. */
50 private int
s_PNGP_reinit(stream_state * st)51 s_PNGP_reinit(stream_state * st)
52 {
53 stream_PNGP_state *const ss = (stream_PNGP_state *) st;
54
55 if (ss->prev_row != 0)
56 memset(ss->prev_row + ss->bpp, 0, ss->row_count);
57 ss->row_left = 0;
58 return 0;
59 }
60
61 /* Common initialization. */
62 private int
s_pngp_init(stream_state * st,bool need_prev)63 s_pngp_init(stream_state * st, bool need_prev)
64 {
65 stream_PNGP_state *const ss = (stream_PNGP_state *) st;
66 int bits_per_pixel = ss->Colors * ss->BitsPerComponent;
67 long bits_per_row = (long)bits_per_pixel * ss->Columns;
68 byte *prev_row = 0;
69
70 #if arch_sizeof_long > arch_sizeof_int
71 if (bits_per_row > max_uint * 7L)
72 return ERRC; /****** WRONG ******/
73 #endif
74 ss->row_count = (uint) ((bits_per_row + 7) >> 3);
75 ss->end_mask = (1 << (-bits_per_row & 7)) - 1;
76 ss->bpp = (bits_per_pixel + 7) >> 3;
77 if (need_prev) {
78 prev_row = gs_alloc_bytes(st->memory, ss->bpp + ss->row_count,
79 "PNGPredictor prev row");
80 if (prev_row == 0)
81 return ERRC; /****** WRONG ******/
82 memset(prev_row, 0, ss->bpp);
83 }
84 ss->prev_row = prev_row;
85 /* case_index is only preset for encoding */
86 return s_PNGP_reinit(st);
87 }
88
89 /* Initialize PNGPredictorEncode filter. */
90 private int
s_PNGPE_init(stream_state * st)91 s_PNGPE_init(stream_state * st)
92 {
93 stream_PNGP_state *const ss = (stream_PNGP_state *) st;
94
95 return s_pngp_init(st, pngp_case_needs_prev[ss->Predictor - cNone]);
96 }
97
98 /* Initialize PNGPredictorDecode filter. */
99 private int
s_PNGPD_init(stream_state * st)100 s_PNGPD_init(stream_state * st)
101 {
102 return s_pngp_init(st, true);
103 }
104
105 /* Release a PNGPredictor filter. */
106 private void
s_PNGP_release(stream_state * st)107 s_PNGP_release(stream_state *st)
108 {
109 stream_PNGP_state *const ss = (stream_PNGP_state *) st;
110
111 if (ss->prev_row)
112 gs_free_object(st->memory, ss->prev_row, "PNGPredictor prev row");
113 }
114
115 /*
116 * Process a partial buffer. We pass in current and previous pointers
117 * to both the current and preceding scan line. Note that dprev is
118 * p - bpp for encoding, q - bpp for decoding; similarly, the 'up' row
119 * is the raw data for encoding, the filtered data for decoding.
120 * Note also that the case_index cannot be cOptimum.
121 */
122 private int
paeth_predictor(int a,int b,int c)123 paeth_predictor(int a, int b, int c)
124 {
125 /* The definitions of ac and bc are correct, not a typo. */
126 int ac = b - c, bc = a - c, abcc = ac + bc;
127 int pa = (ac < 0 ? -ac : ac), pb = (bc < 0 ? -bc : bc),
128 pc = (abcc < 0 ? -abcc : abcc);
129
130 return (pa <= pb && pa <= pc ? a : pb <= pc ? b : c);
131 }
132 private void
s_pngp_process(stream_state * st,stream_cursor_write * pw,const byte * dprev,stream_cursor_read * pr,const byte * upprev,const byte * up,uint count)133 s_pngp_process(stream_state * st, stream_cursor_write * pw,
134 const byte * dprev, stream_cursor_read * pr,
135 const byte * upprev, const byte * up, uint count)
136 {
137 stream_PNGP_state *const ss = (stream_PNGP_state *) st;
138 byte *q = pw->ptr + 1;
139 const byte *p = pr->ptr + 1;
140
141 pr->ptr += count;
142 pw->ptr += count;
143 ss->row_left -= count;
144 switch (ss->case_index) {
145 case cEncode + cNone:
146 case cDecode + cNone:
147 memcpy(q, p, count);
148 break;
149 case cEncode + cSub:
150 for (; count; ++q, ++dprev, ++p, --count)
151 *q = (byte) (*p - *dprev);
152 break;
153 case cDecode + cSub:
154 for (; count; ++q, ++dprev, ++p, --count)
155 *q = (byte) (*p + *dprev);
156 break;
157 case cEncode + cUp:
158 for (; count; ++q, ++up, ++p, --count)
159 *q = (byte) (*p - *up);
160 break;
161 case cDecode + cUp:
162 for (; count; ++q, ++up, ++p, --count)
163 *q = (byte) (*p + *up);
164 break;
165 case cEncode + cAverage:
166 for (; count; ++q, ++dprev, ++up, ++p, --count)
167 *q = (byte) (*p - arith_rshift_1((int)*dprev + (int)*up));
168 break;
169 case cDecode + cAverage:
170 for (; count; ++q, ++dprev, ++up, ++p, --count)
171 *q = (byte) (*p + arith_rshift_1((int)*dprev + (int)*up));
172 break;
173 case cEncode + cPaeth:
174 for (; count; ++q, ++dprev, ++up, ++upprev, ++p, --count)
175 *q = (byte) (*p - paeth_predictor(*dprev, *up, *upprev));
176 break;
177 case cDecode + cPaeth:
178 for (; count; ++q, ++dprev, ++up, ++upprev, ++p, --count)
179 *q = (byte) (*p + paeth_predictor(*dprev, *up, *upprev));
180 break;
181 }
182 }
183
184 /* Calculate the number of bytes for the next processing step, */
185 /* the min of (input data, output data, remaining row length). */
186 private uint
s_pngp_count(const stream_state * st_const,const stream_cursor_read * pr,const stream_cursor_write * pw)187 s_pngp_count(const stream_state * st_const, const stream_cursor_read * pr,
188 const stream_cursor_write * pw)
189 {
190 const stream_PNGP_state *const ss_const =
191 (const stream_PNGP_state *)st_const;
192 uint rcount = pr->limit - pr->ptr;
193 uint wcount = pw->limit - pw->ptr;
194 uint row_left = ss_const->row_left;
195
196 if (rcount < row_left)
197 row_left = rcount;
198 if (wcount < row_left)
199 row_left = wcount;
200 return row_left;
201 }
202
203 /*
204 * Encode a buffer. Let N = ss->row_count, P = N - ss->row_left,
205 * and B = ss->bpp. Consider that bytes [-B .. -1] of every row are zero.
206 * Then:
207 * prev_row[0 .. P - 1] contain bytes -B .. P - B - 1
208 * of the current input row.
209 * ss->prev[0 .. B - 1] contain bytes P - B .. P - 1
210 * of the current input row.
211 * prev_row[P .. N + B - 1] contain bytes P - B .. N - 1
212 * of the previous input row.
213 */
214 private int
optimum_predictor(const stream_state * st,const stream_cursor_read * pr)215 optimum_predictor(const stream_state * st, const stream_cursor_read * pr)
216 {
217 return cSub;
218 }
219 private int
s_PNGPE_process(stream_state * st,stream_cursor_read * pr,stream_cursor_write * pw,bool last)220 s_PNGPE_process(stream_state * st, stream_cursor_read * pr,
221 stream_cursor_write * pw, bool last)
222 {
223 stream_PNGP_state *const ss = (stream_PNGP_state *) st;
224 int bpp = ss->bpp;
225 int status = 0;
226
227 while (pr->ptr < pr->limit) {
228 uint count;
229
230 if (ss->row_left == 0) {
231 /* Beginning of row, write algorithm byte. */
232 int predictor;
233
234 if (pw->ptr >= pw->limit) {
235 status = 1;
236 break;
237 }
238 predictor =
239 (ss->Predictor == cOptimum ?
240 optimum_predictor(st, pr) :
241 ss->Predictor);
242 *++(pw->ptr) = (byte) predictor - cNone;
243 ss->case_index = predictor + cEncode;
244 ss->row_left = ss->row_count;
245 memset(ss->prev, 0, bpp);
246 continue;
247 }
248 count = s_pngp_count(st, pr, pw);
249 if (count == 0) {
250 /* We know we have input, so output must be full. */
251 status = 1;
252 break;
253 } {
254 byte *up = ss->prev_row + bpp + ss->row_count - ss->row_left;
255 uint n = min(count, bpp);
256
257 /* Process bytes whose predecessors are in prev. */
258 s_pngp_process(st, pw, ss->prev, pr, up - bpp, up, n);
259 if (ss->prev_row)
260 memcpy(up - bpp, ss->prev, n);
261 if (ss->row_left == 0)
262 continue;
263 if (n < bpp) {
264 /*
265 * We didn't have both enough input data and enough output
266 * space to use up all of prev. Shift more data into prev
267 * and exit.
268 */
269 int prev_left = bpp - n;
270
271 memmove(ss->prev, ss->prev + n, prev_left);
272 memcpy(ss->prev + prev_left, pr->ptr - (n - 1), n);
273 if (pw->ptr >= pw->limit && pr->ptr < pr->limit)
274 status = 1;
275 break;
276 }
277 /* Process bytes whose predecessors are in the input. */
278 /* We know we have at least bpp input and output bytes, */
279 /* and that n = bpp. */
280 count -= bpp;
281 s_pngp_process(st, pw, pr->ptr - (bpp - 1), pr,
282 up, up + bpp, count);
283 memcpy(ss->prev, pr->ptr - (bpp - 1), bpp);
284 if (ss->prev_row) {
285 memcpy(up, pr->ptr - (bpp + count - 1), count);
286 if (ss->row_left == 0)
287 memcpy(up + count, ss->prev, bpp);
288 }
289 }
290 }
291 return status;
292 }
293
294 /*
295 * Decode a buffer. Let N = ss->row_count, P = N - ss->row_left,
296 * and B = ss->bpp. Consider that bytes [-B .. -1] of every row are zero.
297 * Then:
298 * prev_row[0 .. P - 1] contain bytes -B .. P - B - 1
299 * of the current output row.
300 * ss->prev[0 .. B - 1] contain bytes P - B .. P - 1
301 * of the current output row.
302 * prev_row[P .. N + B - 1] contain bytes P - B .. N - 1
303 * of the previous output row.
304 */
305 private int
s_PNGPD_process(stream_state * st,stream_cursor_read * pr,stream_cursor_write * pw,bool last)306 s_PNGPD_process(stream_state * st, stream_cursor_read * pr,
307 stream_cursor_write * pw, bool last)
308 {
309 stream_PNGP_state *const ss = (stream_PNGP_state *) st;
310 int bpp = ss->bpp;
311 int status = 0;
312
313 while (pr->ptr < pr->limit) {
314 uint count;
315
316 if (ss->row_left == 0) {
317 /* Beginning of row, read algorithm byte. */
318 int predictor = pr->ptr[1];
319
320 if (predictor >= cOptimum - cNone) {
321 status = ERRC;
322 break;
323 }
324 pr->ptr++;
325 ss->case_index = predictor + cNone + cDecode;
326 ss->row_left = ss->row_count;
327 memset(ss->prev, 0, bpp);
328 continue;
329 }
330 count = s_pngp_count(st, pr, pw);
331 if (count == 0) {
332 /* We know we have input, so output must be full. */
333 status = 1;
334 break;
335 } {
336 byte *up = ss->prev_row + bpp + ss->row_count - ss->row_left;
337 uint n = min(count, bpp);
338
339 /* Process bytes whose predecessors are in prev. */
340 s_pngp_process(st, pw, ss->prev, pr, up - bpp, up, n);
341 if (ss->prev_row)
342 memcpy(up - bpp, ss->prev, n);
343 if (ss->row_left == 0)
344 continue;
345 if (n < bpp) {
346 /*
347 * We didn't have both enough input data and enough output
348 * space to use up all of prev. Shift more data into prev
349 * and exit.
350 */
351 int prev_left = bpp - n;
352
353 memmove(ss->prev, ss->prev + n, prev_left);
354 memcpy(ss->prev + prev_left, pw->ptr - (n - 1), n);
355 if (pw->ptr >= pw->limit && pr->ptr < pr->limit)
356 status = 1;
357 break;
358 }
359 /* Process bytes whose predecessors are in the output. */
360 /* We know we have at least bpp input and output bytes, */
361 /* and that n = bpp. */
362 count -= bpp;
363 s_pngp_process(st, pw, pw->ptr - (bpp - 1), pr,
364 up, up + bpp, count);
365 memcpy(ss->prev, pw->ptr - (bpp - 1), bpp);
366 if (ss->prev_row) {
367 memcpy(up, pw->ptr - (bpp + count - 1), count);
368 if (ss->row_left == 0)
369 memcpy(up + count, ss->prev, bpp);
370 }
371 }
372 }
373 return status;
374 }
375
376 /* Stream templates */
377 const stream_template s_PNGPE_template = {
378 &st_PNGP_state, s_PNGPE_init, s_PNGPE_process, 1, 1, s_PNGP_release,
379 s_PNGP_set_defaults, s_PNGP_reinit
380 };
381 const stream_template s_PNGPD_template = {
382 &st_PNGP_state, s_PNGPD_init, s_PNGPD_process, 1, 1, s_PNGP_release,
383 s_PNGP_set_defaults, s_PNGP_reinit
384 };
385