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