1 /* -*- Mode: c; c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t; -*- */
2 /*
3 * Copyright © 2009 Mozilla Corporation
4 *
5 * Permission to use, copy, modify, distribute, and sell this software and its
6 * documentation for any purpose is hereby granted without fee, provided that
7 * the above copyright notice appear in all copies and that both that
8 * copyright notice and this permission notice appear in supporting
9 * documentation, and that the name of Mozilla Corporation not be used in
10 * advertising or publicity pertaining to distribution of the software without
11 * specific, written prior permission. Mozilla Corporation makes no
12 * representations about the suitability of this software for any purpose. It
13 * is provided "as is" without express or implied warranty.
14 *
15 * MOZILLA CORPORATION DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
16 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT
17 * SHALL MOZILLA CORPORATION BE LIABLE FOR ANY SPECIAL, INDIRECT OR
18 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
19 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
20 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
21 * OF THIS SOFTWARE.
22 *
23 * Author: Jeff Muizelaar, Mozilla Corp.
24 */
25
26 //========================================================================
27 //
28 // Modified under the Poppler project - http://poppler.freedesktop.org
29 //
30 // All changes made under the Poppler project to this file are licensed
31 // under GPL version 2 or later
32 //
33 // Copyright (C) 2012 Hib Eris <hib@hiberis.nl>
34 // Copyright (C) 2012 Adrian Johnson <ajohnson@redneon.com>
35 //
36 // To see a description of the changes please see the Changelog file that
37 // came with your tarball or type make ChangeLog if you are building from git
38 //
39 //========================================================================
40
41
42 /* This implements a box filter that supports non-integer box sizes */
43
44 #ifdef HAVE_CONFIG_H
45 #include <config.h>
46 #endif
47
48 #include <stdint.h>
49 #include <stdio.h>
50 #include <assert.h>
51 #include <stdlib.h>
52 #include <math.h>
53 #include "goo/gmem.h"
54 #include "goo/gtypes_p.h"
55 #include "CairoRescaleBox.h"
56
57
58 /* we work in fixed point where 1. == 1 << 24 */
59 #define FIXED_SHIFT 24
60
61
downsample_row_box_filter(int start,int width,uint32_t * src,uint32_t * dest,int coverage[],int pixel_coverage)62 static void downsample_row_box_filter (
63 int start, int width,
64 uint32_t *src, uint32_t *dest,
65 int coverage[], int pixel_coverage)
66 {
67 /* we need an array of the pixel contribution of each destination pixel on the boundaries.
68 * we invert the value to get the value on the other size of the box */
69 /*
70
71 value = a * contribution * 1/box_size
72 value += a * 1/box_size
73 value += a * 1/box_size
74 value += a * 1/box_size
75 value += a * (1 - contribution) * 1/box_size
76 a * (1/box_size - contribution * 1/box_size)
77
78 box size is constant
79
80
81 value = a * contribtion_a * 1/box_size + b * contribution_b * 1/box_size
82 contribution_b = (1 - contribution_a)
83 = (1 - contribution_a_next)
84 */
85
86 /* box size = ceil(src_width/dest_width) */
87 int x = 0;
88
89 /* skip to start */
90 /* XXX: it might be possible to do this directly instead of iteratively, however
91 * the iterative solution is simple */
92 while (x < start)
93 {
94 int box = 1 << FIXED_SHIFT;
95 int start_coverage = coverage[x];
96 box -= start_coverage;
97 src++;
98 while (box >= pixel_coverage)
99 {
100 src++;
101 box -= pixel_coverage;
102 }
103 x++;
104 }
105
106 while (x < start + width)
107 {
108 uint32_t a = 0;
109 uint32_t r = 0;
110 uint32_t g = 0;
111 uint32_t b = 0;
112 int box = 1 << FIXED_SHIFT;
113 int start_coverage = coverage[x];
114
115 a = ((*src >> 24) & 0xff) * start_coverage;
116 r = ((*src >> 16) & 0xff) * start_coverage;
117 g = ((*src >> 8) & 0xff) * start_coverage;
118 b = ((*src >> 0) & 0xff) * start_coverage;
119 src++;
120 x++;
121 box -= start_coverage;
122
123 while (box >= pixel_coverage)
124 {
125 a += ((*src >> 24) & 0xff) * pixel_coverage;
126 r += ((*src >> 16) & 0xff) * pixel_coverage;
127 g += ((*src >> 8) & 0xff) * pixel_coverage;
128 b += ((*src >> 0) & 0xff) * pixel_coverage;
129 src++;
130
131 box -= pixel_coverage;
132 }
133
134 /* multiply by whatever is leftover
135 * this ensures that we don't bias down.
136 * i.e. start_coverage + n*pixel_coverage + box == 1 << 24 */
137 if (box > 0)
138 {
139 a += ((*src >> 24) & 0xff) * box;
140 r += ((*src >> 16) & 0xff) * box;
141 g += ((*src >> 8) & 0xff) * box;
142 b += ((*src >> 0) & 0xff) * box;
143 }
144
145 a >>= FIXED_SHIFT;
146 r >>= FIXED_SHIFT;
147 g >>= FIXED_SHIFT;
148 b >>= FIXED_SHIFT;
149
150 *dest = (a << 24) | (r << 16) | (g << 8) | b;
151 dest++;
152 }
153 }
154
downsample_columns_box_filter(int n,int start_coverage,int pixel_coverage,uint32_t * src,uint32_t * dest)155 static void downsample_columns_box_filter (
156 int n,
157 int start_coverage,
158 int pixel_coverage,
159 uint32_t *src, uint32_t *dest)
160 {
161 int stride = n;
162 while (n--) {
163 uint32_t a = 0;
164 uint32_t r = 0;
165 uint32_t g = 0;
166 uint32_t b = 0;
167 uint32_t *column_src = src;
168 int box = 1 << FIXED_SHIFT;
169
170 a = ((*column_src >> 24) & 0xff) * start_coverage;
171 r = ((*column_src >> 16) & 0xff) * start_coverage;
172 g = ((*column_src >> 8) & 0xff) * start_coverage;
173 b = ((*column_src >> 0) & 0xff) * start_coverage;
174 column_src += stride;
175 box -= start_coverage;
176
177 while (box >= pixel_coverage)
178 {
179 a += ((*column_src >> 24) & 0xff) * pixel_coverage;
180 r += ((*column_src >> 16) & 0xff) * pixel_coverage;
181 g += ((*column_src >> 8) & 0xff) * pixel_coverage;
182 b += ((*column_src >> 0) & 0xff) * pixel_coverage;
183 column_src += stride;
184 box -= pixel_coverage;
185 }
186
187 if (box > 0) {
188 a += ((*column_src >> 24) & 0xff) * box;
189 r += ((*column_src >> 16) & 0xff) * box;
190 g += ((*column_src >> 8) & 0xff) * box;
191 b += ((*column_src >> 0) & 0xff) * box;
192 }
193
194 a >>= FIXED_SHIFT;
195 r >>= FIXED_SHIFT;
196 g >>= FIXED_SHIFT;
197 b >>= FIXED_SHIFT;
198
199 *dest = (a << 24) | (r << 16) | (g << 8) | b;
200 dest++;
201 src++;
202 }
203 }
204
compute_coverage(int coverage[],int src_length,int dest_length)205 static int compute_coverage (int coverage[], int src_length, int dest_length)
206 {
207 int i;
208 /* num = src_length/dest_length
209 total = sum(pixel) / num
210
211 pixel * 1/num == pixel * dest_length / src_length
212 */
213 /* the average contribution of each source pixel */
214 int ratio = ((1 << 24)*(long long int)dest_length)/src_length;
215 /* because ((1 << 24)*(long long int)dest_length) won't always be divisible by src_length
216 * we'll need someplace to put the other bits.
217 *
218 * We want to ensure a + n*ratio < 1<<24
219 *
220 * 1<<24
221 * */
222
223 double scale = (double)src_length/dest_length;
224
225 /* for each destination pixel compute the coverage of the left most pixel included in the box */
226 /* I have a proof of this, which this margin is too narrow to contain */
227 for (i=0; i<dest_length; i++)
228 {
229 float left_side = i*scale;
230 float right_side = (i+1)*scale;
231 float right_fract = right_side - floor (right_side);
232 float left_fract = ceil (left_side) - left_side;
233 int overage;
234 /* find out how many source pixels will be used to fill the box */
235 int count = floor (right_side) - ceil (left_side);
236 /* what's the maximum value this expression can become?
237 floor((i+1)*scale) - ceil(i*scale)
238
239 (i+1)*scale - i*scale == scale
240
241 since floor((i+1)*scale) <= (i+1)*scale
242 and ceil(i*scale) >= i*scale
243
244 floor((i+1)*scale) - ceil(i*scale) <= scale
245
246 further since: floor((i+1)*scale) - ceil(i*scale) is an integer
247
248 therefore:
249 floor((i+1)*scale) - ceil(i*scale) <= floor(scale)
250 */
251
252 if (left_fract == 0.)
253 count--;
254
255 /* compute how much the right-most pixel contributes */
256 overage = ratio*(right_fract);
257
258 /* the remainder is the the amount that the left-most pixel
259 * contributes */
260 coverage[i] = (1<<24) - (count * ratio + overage);
261 }
262
263 return ratio;
264 }
265
266
downScaleImage(unsigned orig_width,unsigned orig_height,signed scaled_width,signed scaled_height,unsigned short int start_column,unsigned short int start_row,unsigned short int width,unsigned short int height,cairo_surface_t * dest_surface)267 GBool CairoRescaleBox::downScaleImage(unsigned orig_width, unsigned orig_height,
268 signed scaled_width, signed scaled_height,
269 unsigned short int start_column, unsigned short int start_row,
270 unsigned short int width, unsigned short int height,
271 cairo_surface_t *dest_surface) {
272 int pixel_coverage_x, pixel_coverage_y;
273 int dest_y;
274 int src_y = 0;
275 uint32_t *scanline;
276 int *x_coverage = NULL;
277 int *y_coverage = NULL;
278 uint32_t *temp_buf = NULL;
279 GBool retval = gFalse;
280 unsigned int *dest;
281 int dst_stride;
282
283 dest = (unsigned int *)cairo_image_surface_get_data (dest_surface);
284 dst_stride = cairo_image_surface_get_stride (dest_surface);
285
286 scanline = (uint32_t*)gmallocn3 (orig_width, 1, sizeof(int));
287
288 x_coverage = (int *)gmallocn3 (orig_width, 1, sizeof(int));
289 y_coverage = (int *)gmallocn3 (orig_height, 1, sizeof(int));
290
291 /* we need to allocate enough room for ceil(src_height/dest_height)+1
292 Example:
293 src_height = 140
294 dest_height = 50
295 src_height/dest_height = 2.8
296
297 |-------------| 2.8 pixels
298 |----|----|----|----| 4 pixels
299 need to sample 3 pixels
300
301 |-------------| 2.8 pixels
302 |----|----|----|----| 4 pixels
303 need to sample 4 pixels
304 */
305
306 temp_buf = (uint32_t *)gmallocn3 ((orig_height + scaled_height-1)/scaled_height+1, scaled_width, sizeof(uint32_t));
307
308 if (!x_coverage || !y_coverage || !scanline || !temp_buf)
309 goto cleanup;
310
311 pixel_coverage_x = compute_coverage (x_coverage, orig_width, scaled_width);
312 pixel_coverage_y = compute_coverage (y_coverage, orig_height, scaled_height);
313
314 assert (width + start_column <= scaled_width);
315
316
317
318 /* skip the rows at the beginning */
319 for (dest_y = 0; dest_y < start_row; dest_y++)
320 {
321 int box = 1 << FIXED_SHIFT;
322 int start_coverage_y = y_coverage[dest_y];
323 box -= start_coverage_y;
324 src_y++;
325 while (box >= pixel_coverage_y)
326 {
327 box -= pixel_coverage_y;
328 src_y++;
329 }
330 }
331
332 for (; dest_y < start_row + height; dest_y++)
333 {
334 int columns = 0;
335 int box = 1 << FIXED_SHIFT;
336 int start_coverage_y = y_coverage[dest_y];
337
338 getRow(src_y, scanline);
339 downsample_row_box_filter (start_column, width, scanline, temp_buf + width * columns, x_coverage, pixel_coverage_x);
340 columns++;
341 src_y++;
342 box -= start_coverage_y;
343
344 while (box >= pixel_coverage_y)
345 {
346 getRow(src_y, scanline);
347 downsample_row_box_filter (start_column, width, scanline, temp_buf + width * columns, x_coverage, pixel_coverage_x);
348 columns++;
349 src_y++;
350 box -= pixel_coverage_y;
351 }
352
353 /* downsample any leftovers */
354 if (box > 0)
355 {
356 getRow(src_y, scanline);
357 downsample_row_box_filter (start_column, width, scanline, temp_buf + width * columns, x_coverage, pixel_coverage_x);
358 columns++;
359 }
360
361 /* now scale the rows we just downsampled in the y direction */
362 downsample_columns_box_filter (width, start_coverage_y, pixel_coverage_y, temp_buf, dest);
363 dest += dst_stride / 4;
364
365 // assert(width*columns <= ((orig_height + scaled_height-1)/scaled_height+1) * width);
366 }
367 // assert (src_y<=orig_height);
368
369 retval = gTrue;
370
371 cleanup:
372 free (x_coverage);
373 free (y_coverage);
374 free (temp_buf);
375 free (scanline);
376
377 return retval;
378 }
379