source: trunk/poppler/mypoppler/poppler/CairoRescaleBox.cc @ 461

Last change on this file since 461 was 461, checked in by Silvan Scherrer, 11 years ago

poppler update to 0.14.2

File size: 11.0 KB
Line 
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/* This implements a box filter that supports non-integer box sizes */
27
28#ifdef HAVE_CONFIG_H
29#include <config.h>
30#endif
31
32#include <stdint.h>
33#include <stdio.h>
34#include <assert.h>
35#include <stdlib.h>
36#include <math.h>
37#include "goo/gmem.h"
38#include "CairoRescaleBox.h"
39
40typedef unsigned short int      uint16_t;
41typedef unsigned int            uint32_t;
42
43/* we work in fixed point where 1. == 1 << 24 */
44#define FIXED_SHIFT 24
45
46static void downsample_row_box_filter (
47        int start, int width,
48        uint32_t *src, uint32_t *dest,
49        int coverage[], int pixel_coverage)
50{
51    /* we need an array of the pixel contribution of each destination pixel on the boundaries.
52     * we invert the value to get the value on the other size of the box */
53    /*
54
55       value  = a * contribution * 1/box_size
56       value += a * 1/box_size
57       value += a * 1/box_size
58       value += a * 1/box_size
59       value += a * (1 - contribution) * 1/box_size
60                a * (1/box_size - contribution * 1/box_size)
61
62        box size is constant
63
64
65       value = a * contribtion_a * 1/box_size + b * contribution_b * 1/box_size
66               contribution_b = (1 - contribution_a)
67                              = (1 - contribution_a_next)
68    */
69
70    /* box size = ceil(src_width/dest_width) */
71    int x = 0;
72
73    /* skip to start */
74    /* XXX: it might be possible to do this directly instead of iteratively, however
75     * the iterative solution is simple */
76    while (x < start)
77    {
78        int box = 1 << FIXED_SHIFT;
79        int start_coverage = coverage[x];
80        box -= start_coverage;
81        src++;
82        while (box >= pixel_coverage)
83        {
84            src++;
85            box -= pixel_coverage;
86        }
87        x++;
88    }
89
90    while (x < start + width)
91    {
92        uint32_t a = 0;
93        uint32_t r = 0;
94        uint32_t g = 0;
95        uint32_t b = 0;
96        int box = 1 << FIXED_SHIFT;
97        int start_coverage = coverage[x];
98
99        a = ((*src >> 24) & 0xff) * start_coverage;
100        r = ((*src >> 16) & 0xff) * start_coverage;
101        g = ((*src >>  8) & 0xff) * start_coverage;
102        b = ((*src >>  0) & 0xff) * start_coverage;
103        src++;
104        x++;
105        box -= start_coverage;
106
107        while (box >= pixel_coverage)
108        {
109            a += ((*src >> 24) & 0xff) * pixel_coverage;
110            r += ((*src >> 16) & 0xff) * pixel_coverage;
111            g += ((*src >>  8) & 0xff) * pixel_coverage;
112            b += ((*src >>  0) & 0xff) * pixel_coverage;
113            src++;
114
115            box -= pixel_coverage;
116        }
117
118        /* multiply by whatever is leftover
119         * this ensures that we don't bias down.
120         * i.e. start_coverage + n*pixel_coverage + box == 1 << 24 */
121        if (box > 0)
122        {
123            a += ((*src >> 24) & 0xff) * box;
124            r += ((*src >> 16) & 0xff) * box;
125            g += ((*src >>  8) & 0xff) * box;
126            b += ((*src >>  0) & 0xff) * box;
127        }
128
129        a >>= FIXED_SHIFT;
130        r >>= FIXED_SHIFT;
131        g >>= FIXED_SHIFT;
132        b >>= FIXED_SHIFT;
133
134        *dest = (a << 24) | (r << 16) | (g << 8) | b;
135        dest++;
136    }
137}
138
139static void downsample_columns_box_filter (
140        int n,
141        int start_coverage,
142        int pixel_coverage,
143        uint32_t *src, uint32_t *dest)
144{
145    int stride = n;
146    while (n--) {
147        uint32_t a = 0;
148        uint32_t r = 0;
149        uint32_t g = 0;
150        uint32_t b = 0;
151        uint32_t *column_src = src;
152        int box = 1 << FIXED_SHIFT;
153
154        a = ((*column_src >> 24) & 0xff) * start_coverage;
155        r = ((*column_src >> 16) & 0xff) * start_coverage;
156        g = ((*column_src >>  8) & 0xff) * start_coverage;
157        b = ((*column_src >>  0) & 0xff) * start_coverage;
158        column_src += stride;
159        box -= start_coverage;
160
161        while (box >= pixel_coverage)
162        {
163            a += ((*column_src >> 24) & 0xff) * pixel_coverage;
164            r += ((*column_src >> 16) & 0xff) * pixel_coverage;
165            g += ((*column_src >>  8) & 0xff) * pixel_coverage;
166            b += ((*column_src >>  0) & 0xff) * pixel_coverage;
167            column_src += stride;
168            box -= pixel_coverage;
169        }
170
171        if (box > 0) {
172            a += ((*column_src >> 24) & 0xff) * box;
173            r += ((*column_src >> 16) & 0xff) * box;
174            g += ((*column_src >>  8) & 0xff) * box;
175            b += ((*column_src >>  0) & 0xff) * box;
176        }
177
178        a >>= FIXED_SHIFT;
179        r >>= FIXED_SHIFT;
180        g >>= FIXED_SHIFT;
181        b >>= FIXED_SHIFT;
182
183        *dest = (a << 24) | (r << 16) | (g << 8) | b;
184        dest++;
185        src++;
186    }
187}
188
189static int compute_coverage (int coverage[], int src_length, int dest_length)
190{
191    int i;
192    /* num = src_length/dest_length
193       total = sum(pixel) / num
194
195       pixel * 1/num == pixel * dest_length / src_length
196    */
197    /* the average contribution of each source pixel */
198    int ratio = ((1 << 24)*(long long int)dest_length)/src_length;
199    /* because ((1 << 24)*(long long int)dest_length) won't always be divisible by src_length
200     * we'll need someplace to put the other bits.
201     *
202     * We want to ensure a + n*ratio < 1<<24
203     *
204     * 1<<24
205     * */
206
207    double scale = (double)src_length/dest_length;
208
209    /* for each destination pixel compute the coverage of the left most pixel included in the box */
210    /* I have a proof of this, which this margin is too narrow to contain */
211    for (i=0; i<dest_length; i++)
212    {
213        float left_side = i*scale;
214        float right_side = (i+1)*scale;
215        float right_fract = right_side - floor (right_side);
216        float left_fract = ceil (left_side) - left_side;
217        int overage;
218        /* find out how many source pixels will be used to fill the box */
219        int count = floor (right_side) - ceil (left_side);
220        /* what's the maximum value this expression can become?
221           floor((i+1)*scale) - ceil(i*scale)
222
223           (i+1)*scale - i*scale == scale
224
225           since floor((i+1)*scale) <= (i+1)*scale
226           and   ceil(i*scale)      >= i*scale
227
228           floor((i+1)*scale) - ceil(i*scale) <= scale
229
230           further since: floor((i+1)*scale) - ceil(i*scale) is an integer
231
232           therefore:
233           floor((i+1)*scale) - ceil(i*scale) <= floor(scale)
234        */
235
236        if (left_fract == 0.)
237            count--;
238
239        /* compute how much the right-most pixel contributes */
240        overage = ratio*(right_fract);
241
242        /* the remainder is the the amount that the left-most pixel
243         * contributes */
244        coverage[i] = (1<<24) - (count * ratio + overage);
245    }
246
247    return ratio;
248}
249
250GBool downscale_box_filter(uint32_t *orig, int orig_stride, unsigned orig_width, unsigned orig_height,
251                           signed scaled_width, signed scaled_height,
252                           uint16_t start_column, uint16_t start_row,
253                           uint16_t width, uint16_t height,
254                           uint32_t *dest, int dst_stride)
255{
256    int pixel_coverage_x, pixel_coverage_y;
257    int dest_y;
258    int src_y = 0;
259    uint32_t *scanline = orig;
260    int *x_coverage = NULL;
261    int *y_coverage = NULL;
262    uint32_t *temp_buf = NULL;
263    GBool retval = gFalse;
264
265    x_coverage = (int *)gmallocn3 (orig_width, 1, sizeof(int));
266    y_coverage = (int *)gmallocn3 (orig_height, 1, sizeof(int));
267
268    /* we need to allocate enough room for ceil(src_height/dest_height)+1
269      Example:
270      src_height = 140
271      dest_height = 50
272      src_height/dest_height = 2.8
273
274      |-------------|       2.8 pixels
275      |----|----|----|----| 4 pixels
276      need to sample 3 pixels
277
278         |-------------|       2.8 pixels
279      |----|----|----|----| 4 pixels
280      need to sample 4 pixels
281    */
282
283    temp_buf = (uint32_t *)gmallocn3 ((orig_height + scaled_height-1)/scaled_height+1, scaled_width, sizeof(uint32_t));
284
285    if (!x_coverage || !y_coverage || !scanline || !temp_buf)
286        goto cleanup;
287
288    pixel_coverage_x = compute_coverage (x_coverage, orig_width, scaled_width);
289    pixel_coverage_y = compute_coverage (y_coverage, orig_height, scaled_height);
290
291    assert (width + start_column <= scaled_width);
292
293    /* skip the rows at the beginning */
294    for (dest_y = 0; dest_y < start_row; dest_y++)
295    {
296        int box = 1 << FIXED_SHIFT;
297        int start_coverage_y = y_coverage[dest_y];
298        box -= start_coverage_y;
299        src_y++;
300        while (box >= pixel_coverage_y)
301        {
302            box -= pixel_coverage_y;
303            src_y++;
304        }
305    }
306
307    for (; dest_y < start_row + height; dest_y++)
308    {
309        int columns = 0;
310        int box = 1 << FIXED_SHIFT;
311        int start_coverage_y = y_coverage[dest_y];
312
313        scanline = orig + src_y * orig_stride / 4;
314        downsample_row_box_filter (start_column, width, scanline, temp_buf + width * columns, x_coverage, pixel_coverage_x);
315        columns++;
316        src_y++;
317        box -= start_coverage_y;
318
319        while (box >= pixel_coverage_y)
320        {
321            scanline = orig + src_y * orig_stride / 4;
322            downsample_row_box_filter (start_column, width, scanline, temp_buf + width * columns, x_coverage, pixel_coverage_x);
323            columns++;
324            src_y++;
325            box -= pixel_coverage_y;
326        }
327
328        /* downsample any leftovers */
329        if (box > 0)
330        {
331            scanline = orig + src_y * orig_stride / 4;
332            downsample_row_box_filter (start_column, width, scanline, temp_buf + width * columns, x_coverage, pixel_coverage_x);
333            columns++;
334        }
335
336        /* now scale the rows we just downsampled in the y direction */
337        downsample_columns_box_filter (width, start_coverage_y, pixel_coverage_y, temp_buf, dest);
338        dest += dst_stride / 4;
339
340//        assert(width*columns <= ((orig_height + scaled_height-1)/scaled_height+1) * width);
341    }
342//    assert (src_y<=orig_height);
343
344    retval = gTrue;
345
346cleanup:
347    free (x_coverage);
348    free (y_coverage);
349    free (temp_buf);
350
351    return gTrue;
352}
Note: See TracBrowser for help on using the repository browser.