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