[cairo] [PATCH] pixman: high qualtiy downscaling

Carlos Garcia Campos carlosgc at gnome.org
Tue Nov 17 03:04:06 PST 2009


Excerpts from Jeff Muizelaar's message of vie jul 31 22:56:13 +0200 2009:
> The following patch is a cleaned up version of my previous downscaling
> patches. It doesn't currently export any api, but I'd like to get it
> into the pixman repo to avoid any duplication of work while the proper
> api to expose it is worked out.

What's the status of this? any chance of getting this fixed in pixman
soon? Poppler has been affected by this bug[1] for a long time, and it's
the main reason why we still allow building poppler-glib frontend with
the splash backend. If there's anything I can do to help, please let
me know.

[1] http://bugs.freedesktop.org/show_bug.cgi?id=5589

Thanks, 

> -Jeff
> 
> 
> diff --git a/pixman/Makefile.am b/pixman/Makefile.am
> index e19fa6e..8292bfc 100644
> --- a/pixman/Makefile.am
> +++ b/pixman/Makefile.am
> @@ -33,6 +33,10 @@ libpixman_1_la_SOURCES =            \
>      pixman-edge-imp.h            \
>      pixman-trap.c                \
>      pixman-timer.c                \
> +    pixman-rescale.c            \
> +    pixman-rescale-box.c            \
> +    pixman-rescale-integer-box.c        \
> +    pixman-rescale-lanczos.c        \
>      pixman-matrix.c
>  
>  libpixmanincludedir = $(includedir)/pixman-1/
> diff --git a/pixman/pixman-rescale-box.c b/pixman/pixman-rescale-box.c
> new file mode 100644
> index 0000000..6d9a874
> --- /dev/null
> +++ b/pixman/pixman-rescale-box.c
> @@ -0,0 +1,439 @@
> +/* -*- Mode: c; c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t; -*- */
> +/*
> + * Copyright © 2009 Mozilla Corporation
> + *
> + * Permission to use, copy, modify, distribute, and sell this software and its
> + * documentation for any purpose is hereby granted without fee, provided that
> + * the above copyright notice appear in all copies and that both that
> + * copyright notice and this permission notice appear in supporting
> + * documentation, and that the name of Mozilla Corporation not be used in
> + * advertising or publicity pertaining to distribution of the software without
> + * specific, written prior permission.  Mozilla Corporation makes no
> + * representations about the suitability of this software for any purpose.  It
> + * is provided "as is" without express or implied warranty.
> + *
> + * MOZILLA CORPORATION DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
> + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT
> + * SHALL MOZILLA CORPORATION BE LIABLE FOR ANY SPECIAL, INDIRECT OR
> + * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
> + * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
> + * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
> + * OF THIS SOFTWARE.
> + *
> + * Author: Jeff Muizelaar, Mozilla Corp.
> + */
> +
> +/* This implements a box filter that supports non-integer box sizes */
> +
> +#ifdef HAVE_CONFIG_H
> +#include <config.h>
> +#endif
> +
> +#include <stdint.h>
> +#include <stdio.h>
> +#include <assert.h>
> +#include <stdlib.h>
> +#include <math.h>
> +#include "pixman-private.h"
> +#include "pixman-rescale.h"
> +
> +/* we work in fixed point where 1. == 1 << 24 */
> +#define FIXED_SHIFT 24
> +
> +#if 0
> +static void downsample_row_box_filter_sse2(
> +        int start,
> +        int width,
> +        uint32_t *src, uint32_t *dest,
> +                int coverage[], int pixel_coverage)
> +{
> +    /* we need an array of the pixel contribution of each destination pixel on
> the boundaries.
> +     * we invert the value to get the value on the other size of the box */
> +    /*
> +
> +       value  = a * contribution * 1/box_size
> +       value += a * 1/box_size
> +       value += a * 1/box_size
> +       value += a * 1/box_size
> +       value += a * (1 - contribution) * 1/box_size
> +                a * (1/box_size - contribution * 1/box_size)
> +
> +        box size is constant
> +
> +
> +       value = a * contribtion_a * 1/box_size + b * contribution_b * 1/box_size
> +               contribution_b = (1 - contribution_a)
> +                              = (1 - contribution_a_next)
> +    */
> +
> +    /* box size = ceil(src_width/dest_width) */
> +    int x = 0;
> +    while (x < start) {
> +        int box = 1 << FIXED_SHIFT;
> +        int start_coverage = coverage[x];
> +        box -= start_coverage;
> +        src++;
> +        while (box >= pixel_coverage) {
> +            src++;
> +            box -= pixel_coverage;
> +        }
> +        x++;
> +    }
> +    __m128i accum = _mm_setzero_si128();
> +    __m128i zero = _mm_setzero_si128();
> +    while (x < start + width) {
> +        uint32_t a = 0;
> +        uint32_t r = 0;
> +        uint32_t g = 0;
> +        uint32_t b = 0;
> +        int box = 1 << FIXED_SHIFT;
> +        int start_coverage = coverage[x];
> +        __m128i v_src = _mm_cvtsi32_si128(*src);
> +        v_src = _mm_unpacklo_epi16(_mm_unpacklo_epi8(v_src, zero), zero);
> +        __m128i coeff = _mm_cvtsi32_si128(start_coverage);
> +        /* duplicate the filter coefficient */
> +        coeff = _mm_shuffle_epi32(coeff, _MM_SHUFFLE(0, 0, 0, 0));
> +        /* multiply and accumulate the result:
> +         * 0000vvvv_0000vvvv_0000vvvv_0000vvvv *
> 000000aa_000000rr_000000gg_000000bb */
> +        accum = _mm_madd_epi16(v_src, coeff);
> +        // we can't use a 32 bit mulitply in sse2
> +        // sse4.1 gives us pmulld but it is apparenlty slow (6 clocks on
> Nehalem)
> +        src++;
> +        x++;
> +        box -= start_coverage;
> +        while (box >= pixel_coverage) {
> +            a += ((*src >> 24) & 0xff) * pixel_coverage;
> +            r += ((*src >> 16) & 0xff) * pixel_coverage;
> +            g += ((*src >>  8) & 0xff) * pixel_coverage;
> +            b += ((*src >>  0) & 0xff) * pixel_coverage;
> +            src++;
> +
> +            box -= pixel_coverage;
> +        }
> +        /* multiply by whatever is leftover
> +         * this ensures that we don't bias down.
> +         * i.e. start_coverage + n*pixel_coverage + box == 1 << 24 */
> +        if (box > 0) {
> +            a += ((*src >> 24) & 0xff) * box;
> +            r += ((*src >> 16) & 0xff) * box;
> +            g += ((*src >>  8) & 0xff) * box;
> +            b += ((*src >>  0) & 0xff) * box;
> +        }
> +
> +        a >>= FIXED_SHIFT;
> +        r >>= FIXED_SHIFT;
> +        g >>= FIXED_SHIFT;
> +        b >>= FIXED_SHIFT;
> +
> +        *dest = (a << 24) | (r << 16) | (g << 8) | b;
> +        dest++;
> +    }
> +}
> +#endif
> +
> +static void downsample_row_box_filter (
> +        int start, int width,
> +        uint32_t *src, uint32_t *dest,
> +        int coverage[], int pixel_coverage)
> +{
> +    /* we need an array of the pixel contribution of each destination pixel on
> the boundaries.
> +     * we invert the value to get the value on the other size of the box */
> +    /*
> +
> +       value  = a * contribution * 1/box_size
> +       value += a * 1/box_size
> +       value += a * 1/box_size
> +       value += a * 1/box_size
> +       value += a * (1 - contribution) * 1/box_size
> +                a * (1/box_size - contribution * 1/box_size)
> +
> +        box size is constant
> +
> +
> +       value = a * contribtion_a * 1/box_size + b * contribution_b * 1/box_size
> +               contribution_b = (1 - contribution_a)
> +                              = (1 - contribution_a_next)
> +    */
> +
> +    /* box size = ceil(src_width/dest_width) */
> +    int x = 0;
> +
> +    /* skip to start */
> +    /* XXX: it might be possible to do this directly instead of iteratively,
> however
> +     * the iterative solution is simple */
> +    while (x < start)
> +    {
> +        int box = 1 << FIXED_SHIFT;
> +        int start_coverage = coverage[x];
> +        box -= start_coverage;
> +        src++;
> +        while (box >= pixel_coverage)
> +        {
> +            src++;
> +            box -= pixel_coverage;
> +        }
> +        x++;
> +    }
> +
> +    while (x < start + width)
> +    {
> +        uint32_t a = 0;
> +        uint32_t r = 0;
> +        uint32_t g = 0;
> +        uint32_t b = 0;
> +        int box = 1 << FIXED_SHIFT;
> +        int start_coverage = coverage[x];
> +
> +        a = ((*src >> 24) & 0xff) * start_coverage;
> +        r = ((*src >> 16) & 0xff) * start_coverage;
> +        g = ((*src >>  8) & 0xff) * start_coverage;
> +        b = ((*src >>  0) & 0xff) * start_coverage;
> +        src++;
> +        x++;
> +        box -= start_coverage;
> +
> +        while (box >= pixel_coverage)
> +        {
> +            a += ((*src >> 24) & 0xff) * pixel_coverage;
> +            r += ((*src >> 16) & 0xff) * pixel_coverage;
> +            g += ((*src >>  8) & 0xff) * pixel_coverage;
> +            b += ((*src >>  0) & 0xff) * pixel_coverage;
> +            src++;
> +
> +            box -= pixel_coverage;
> +        }
> +
> +        /* multiply by whatever is leftover
> +         * this ensures that we don't bias down.
> +         * i.e. start_coverage + n*pixel_coverage + box == 1 << 24 */
> +        if (box > 0)
> +        {
> +            a += ((*src >> 24) & 0xff) * box;
> +            r += ((*src >> 16) & 0xff) * box;
> +            g += ((*src >>  8) & 0xff) * box;
> +            b += ((*src >>  0) & 0xff) * box;
> +        }
> +
> +        a >>= FIXED_SHIFT;
> +        r >>= FIXED_SHIFT;
> +        g >>= FIXED_SHIFT;
> +        b >>= FIXED_SHIFT;
> +
> +        *dest = (a << 24) | (r << 16) | (g << 8) | b;
> +        dest++;
> +    }
> +}
> +
> +static void downsample_columns_box_filter (
> +        int n,
> +        int start_coverage,
> +        int pixel_coverage,
> +        uint32_t *src, uint32_t *dest)
> +{
> +    int stride = n;
> +    while (n--) {
> +        uint32_t a = 0;
> +        uint32_t r = 0;
> +        uint32_t g = 0;
> +        uint32_t b = 0;
> +        uint32_t *column_src = src;
> +        int box = 1 << FIXED_SHIFT;
> +
> +        a = ((*column_src >> 24) & 0xff) * start_coverage;
> +        r = ((*column_src >> 16) & 0xff) * start_coverage;
> +        g = ((*column_src >>  8) & 0xff) * start_coverage;
> +        b = ((*column_src >>  0) & 0xff) * start_coverage;
> +        column_src += stride;
> +        box -= start_coverage;
> +
> +        while (box >= pixel_coverage)
> +        {
> +            a += ((*column_src >> 24) & 0xff) * pixel_coverage;
> +            r += ((*column_src >> 16) & 0xff) * pixel_coverage;
> +            g += ((*column_src >>  8) & 0xff) * pixel_coverage;
> +            b += ((*column_src >>  0) & 0xff) * pixel_coverage;
> +            column_src += stride;
> +            box -= pixel_coverage;
> +        }
> +
> +        if (box > 0) {
> +            a += ((*column_src >> 24) & 0xff) * box;
> +            r += ((*column_src >> 16) & 0xff) * box;
> +            g += ((*column_src >>  8) & 0xff) * box;
> +            b += ((*column_src >>  0) & 0xff) * box;
> +        }
> +
> +        a >>= FIXED_SHIFT;
> +        r >>= FIXED_SHIFT;
> +        g >>= FIXED_SHIFT;
> +        b >>= FIXED_SHIFT;
> +
> +        *dest = (a << 24) | (r << 16) | (g << 8) | b;
> +        dest++;
> +        src++;
> +    }
> +}
> +
> +static int compute_coverage (int coverage[], int src_length, int dest_length)
> +{
> +    int i;
> +    /* num = src_length/dest_length
> +       total = sum(pixel) / num
> +
> +       pixel * 1/num == pixel * dest_length / src_length
> +    */
> +    /* the average contribution of each source pixel */
> +    int ratio = ((1 << 24)*(long long int)dest_length)/src_length;
> +    /* because ((1 << 24)*(long long int)dest_length) won't always be
> divisible by src_length
> +     * we'll need someplace to put the other bits.
> +     *
> +     * We want to ensure a + n*ratio < 1<<24
> +     *
> +     * 1<<24
> +     * */
> +
> +    double scale = (double)src_length/dest_length;
> +
> +    /* for each destination pixel compute the coverage of the left most pixel
> included in the box */
> +    /* I have a proof of this, which this margin is too narrow to contain */
> +    for (i=0; i<dest_length; i++)
> +    {
> +        float left_side = i*scale;
> +        float right_side = (i+1)*scale;
> +        float right_fract = right_side - floor (right_side);
> +        float left_fract = ceil (left_side) - left_side;
> +        int overage;
> +        /* find out how many source pixels will be used to fill the box */
> +        int count = floor (right_side) - ceil (left_side);
> +        /* what's the maximum value this expression can become?
> +           floor((i+1)*scale) - ceil(i*scale)
> +
> +           (i+1)*scale - i*scale == scale
> +
> +           since floor((i+1)*scale) <= (i+1)*scale
> +           and   ceil(i*scale)      >= i*scale
> +
> +           floor((i+1)*scale) - ceil(i*scale) <= scale
> +
> +           further since: floor((i+1)*scale) - ceil(i*scale) is an integer
> +
> +           therefore:
> +           floor((i+1)*scale) - ceil(i*scale) <= floor(scale)
> +        */
> +
> +        if (left_fract == 0.)
> +            count--;
> +
> +        /* compute how much the right-most pixel contributes */
> +        overage = ratio*(right_fract);
> +
> +        /* the remainder is the the amount that the left-most pixel
> +         * contributes */
> +        coverage[i] = (1<<24) - (count * ratio + overage);
> +    }
> +
> +    return ratio;
> +}
> +
> +PIXMAN_EXPORT
> +int downscale_box_filter(const struct rescale_fetcher *fetcher, void *closure,
> unsigned orig_width, unsigned orig_height,
> +        signed scaled_width, signed scaled_height,
> +        uint16_t start_column, uint16_t start_row,
> +        uint16_t width, uint16_t height,
> +        uint32_t *dest, int dst_stride)
> +{
> +    int pixel_coverage_x, pixel_coverage_y;
> +    int dest_y;
> +    int src_y = 0;
> +
> +    void (*fetch_scanline)(void *closure, int y, uint32_t **scanline) =
> fetcher->fetch_scanline;
> +    uint32_t *scanline = fetcher->init(closure);
> +
> +    int *x_coverage = pixman_malloc_abc (orig_width, 1, sizeof(int));
> +    int *y_coverage = pixman_malloc_abc (orig_height, 1, sizeof(int));
> +
> +    /* we need to allocate enough room for ceil(src_height/dest_height)+1
> +      Example:
> +      src_height = 140
> +      dest_height = 50
> +      src_height/dest_height = 2.8
> +
> +      |-------------|       2.8 pixels
> +      |----|----|----|----| 4 pixels
> +      need to sample 3 pixels
> +
> +         |-------------|       2.8 pixels
> +      |----|----|----|----| 4 pixels
> +      need to sample 4 pixels
> +    */
> +
> +    uint32_t *temp_buf = pixman_malloc_abc ((orig_height +
> scaled_height-1)/scaled_height+1, scaled_width, sizeof(uint32_t));
> +
> +    if (!x_coverage || !y_coverage || !scanline || !temp_buf) {
> +        return -1;
> +    }
> +
> +    pixel_coverage_x = compute_coverage (x_coverage, orig_width, scaled_width);
> +    pixel_coverage_y = compute_coverage (y_coverage, orig_height,
> scaled_height);
> +
> +    assert (width + start_column <= scaled_width);
> +
> +    /* skip the rows at the beginning */
> +    for (dest_y = 0; dest_y < start_row; dest_y++)
> +    {
> +        int box = 1 << FIXED_SHIFT;
> +        int start_coverage_y = y_coverage[dest_y];
> +        box -= start_coverage_y;
> +        src_y++;
> +        while (box >= pixel_coverage_y)
> +        {
> +            box -= pixel_coverage_y;
> +            src_y++;
> +        }
> +    }
> +
> +    for (; dest_y < start_row + height; dest_y++)
> +    {
> +        int columns = 0;
> +        int box = 1 << FIXED_SHIFT;
> +        int start_coverage_y = y_coverage[dest_y];
> +
> +        fetch_scanline (closure, src_y, &scanline);
> +        downsample_row_box_filter (start_column, width, scanline, temp_buf +
> width * columns, x_coverage, pixel_coverage_x);
> +        columns++;
> +        src_y++;
> +        box -= start_coverage_y;
> +
> +        while (box >= pixel_coverage_y)
> +        {
> +            fetch_scanline (closure, src_y, &scanline);
> +            downsample_row_box_filter (start_column, width, scanline, temp_buf
> + width * columns, x_coverage, pixel_coverage_x);
> +            columns++;
> +            src_y++;
> +            box -= pixel_coverage_y;
> +        }
> +
> +        /* downsample any leftovers */
> +        if (box > 0)
> +        {
> +            fetch_scanline (closure, src_y, &scanline);
> +            downsample_row_box_filter (start_column, width, scanline, temp_buf
> + width * columns, x_coverage, pixel_coverage_x);
> +            columns++;
> +        }
> +
> +        /* now scale the rows we just downsampled in the y direction */
> +        downsample_columns_box_filter (width, start_coverage_y,
> pixel_coverage_y, temp_buf, dest);
> +        dest += dst_stride/4;
> +
> +        assert(width*columns <= ((orig_height +
> scaled_height-1)/scaled_height+1) * width);
> +    }
> +
> +    assert (src_y<=orig_height);
> +
> +    fetcher->fini (closure, scanline);
> +    free (x_coverage);
> +    free (y_coverage);
> +    free (temp_buf);
> +
> +    return 0;
> +}
> diff --git a/pixman/pixman-rescale-integer-box.c
> b/pixman/pixman-rescale-integer-box.c
> new file mode 100644
> index 0000000..5142705
> --- /dev/null
> +++ b/pixman/pixman-rescale-integer-box.c
> @@ -0,0 +1,271 @@
> +/* -*- Mode: c; c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t; -*- */
> +/*
> + * Copyright © 2009 Mozilla Corporation
> + *
> + * Permission to use, copy, modify, distribute, and sell this software and its
> + * documentation for any purpose is hereby granted without fee, provided that
> + * the above copyright notice appear in all copies and that both that
> + * copyright notice and this permission notice appear in supporting
> + * documentation, and that the name of Mozilla Corporation not be used in
> + * advertising or publicity pertaining to distribution of the software without
> + * specific, written prior permission.  Mozilla Corporation makes no
> + * representations about the suitability of this software for any purpose.  It
> + * is provided "as is" without express or implied warranty.
> + *
> + * MOZILLA CORPORATION DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
> + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT
> + * SHALL MOZILLA CORPORATION BE LIABLE FOR ANY SPECIAL, INDIRECT OR
> + * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
> + * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
> + * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
> + * OF THIS SOFTWARE.
> + *
> + * Author: Jeff Muizelaar, Mozilla Corp.
> + */
> +
> +#ifdef HAVE_CONFIG_H
> +#include <config.h>
> +#endif
> +
> +#include <stdio.h>
> +#include <assert.h>
> +#include <stdlib.h>
> +#include "pixman-private.h"
> +#include "pixman-rescale.h"
> +
> +/*
> +When box filtering with an integer sized box we only ever have two box sizes.
> +Proof:
> +    Assume w1 > w2.
> +    r = w1/w2
> +
> +    The size of the two boxes is
> +    r1 = ceil(r), r2 = floor(r)
> +
> +    we want to find non-negative integers p and q such that:
> +    w1 = p*r1 + q*r2
> +
> +    if r1 == r2 then
> +        r is an integer and thus w2 evenly divides w1
> +        therefor p = w2 and q = 0
> +    otherwise r1 != r2 and
> +        r1 = r2 + 1
> +        w1 = p*(r2 + 1) + q * r2
> +           = p*r2 + q*r2 + p
> +           = (p + q)*r2 + p
> +
> +        we then choose a value of p such that:
> +            w1 = r2*w2 + p
> +            thus p = w1 mod w2
> +            and  q = w2 - p which is > 0 because
> +                            p = w1 mod w2
> +
> +            subing into:
> +            (p + q)*r2 + p
> +            gives:
> +            w1 = (p + w2 - p)*r2 + p
> +            w1 = w2*r2 + w1 mod w2
> +
> +*/
> +#define AVOID_DIVIDE
> +
> +/* downsample_row_box_filter is a Digital Differential Analyzer (like
> Bresenham's line algorithm)
> + * 'e' is the current fraction or error
> + */
> +void downsample_row_box_filter(
> +        int n,
> +        uint32_t *src, uint32_t *dest,
> +                long dx2, long e, long src_dx)
> +{
> +    /* the filter sums only two different counts of samples.
> +     * we compute the inverses for these two different counts
> +     * so that we can do multiplications instead of divisions */
> +    int div_inv[2];
> +    int div = src_dx/dx2;
> +    /* we can index on the bottom bit of the divisor because the two different
> counts
> +     * are +1 */
> +    div_inv[div & 1] = (1<<24)/div;
> +    div += 1;
> +    div_inv[div & 1] = (1<<24)/div;
> +
> +    while (n--) {
> +        uint32_t a, r, g, b;
> +        int div;
> +        int count = 1;
> +
> +        /* we always have at least one source pixel per destination pixel
> +         * because we are downscaling */
> +        a = (*src >> 24) & 0xff;
> +        r = (*src >> 16) & 0xff;
> +        g = (*src >>  8) & 0xff;
> +        b = (*src >>  0) & 0xff;
> +        e -= dx2;
> +        src++;
> +
> +        /* accumulate the rest of the source pixels */
> +        while (e > 0) {
> +            e -= dx2;
> +            a += (*src >> 24) & 0xff;
> +            r += (*src >> 16) & 0xff;
> +            g += (*src >>  8) & 0xff;
> +            b += (*src >>  0) & 0xff;
> +            count++;
> +            src++;
> +        }
> +
> +#ifdef AVOID_DIVIDE
> +        div = div_inv[count & 1];
> +
> +        a = (a * div + 0x10000) >> 24;
> +        r = (r * div + 0x10000) >> 24;
> +        g = (g * div + 0x10000) >> 24;
> +        b = (b * div + 0x10000) >> 24;
> +#else
> +        a /= count;
> +        r /= count;
> +        g /= count;
> +        b /= count;
> +#endif
> +
> +        *dest = (a << 24) | (r << 16) | (g << 8) | b;
> +        dest++;
> +
> +        e += src_dx;
> +    }
> +}
> +
> +void downsample_columns_box_filter(
> +        int n,
> +        int columns,
> +        uint32_t *src, uint32_t *dest)
> +{
> +    int stride = n;
> +    int div = (1<<24)/columns;
> +    while (n--)
> +    {
> +        uint32_t a, r, g, b;
> +        uint32_t *column_src = src;
> +        int h;
> +
> +        a = (*column_src >> 24) & 0xff;
> +        r = (*column_src >> 16) & 0xff;
> +        g = (*column_src >>  8) & 0xff;
> +        b = (*column_src >>  0) & 0xff;
> +
> +        for (h = 1; h < columns; h++)
> +        {
> +            a += (*column_src >> 24) & 0xff;
> +            r += (*column_src >> 16) & 0xff;
> +            g += (*column_src >>  8) & 0xff;
> +            b += (*column_src >>  0) & 0xff;
> +            column_src += stride;
> +        }
> +
> +#ifdef AVOID_DIVIDE
> +        a = (a * div + 0x10000) >> 24;
> +        r = (r * div + 0x10000) >> 24;
> +        g = (g * div + 0x10000) >> 24;
> +        b = (b * div + 0x10000) >> 24;
> +#else
> +        a /= columns;
> +        r /= columns;
> +        g /= columns ;
> +        b /= columns;
> +#endif
> +        *dest = (a << 24) | (r << 16) | (g << 8) | b;
> +        dest++;
> +        src++;
> +    }
> +}
> +
> +#define ROUND
> +
> +PIXMAN_EXPORT
> +int downscale_integer_box_filter (const struct rescale_fetcher *fetcher, void
> *closure, unsigned orig_width, unsigned orig_height,
> +        signed scaled_width, signed scaled_height,
> +        uint16_t start_column, uint16_t start_row,
> +        uint16_t width, uint16_t height,
> +        uint32_t *dest, int dst_stride)
> +{
> +    uint32_t *temp_buf;
> +    uint32_t *scanline;
> +    int src_offset = 0;
> +    int src_dy, e, dx2;
> +    int dest_dx, src_dx, ex, dx2x;
> +    int y = 0;
> +    int d;
> +
> +    /* setup our parameters for runing our DDA in the y direction */
> +    /* multiplying by 2 is for rounding purposes. i.e. to move the center */
> +    src_dy = orig_height * 2; /* dy *= 2 */
> +    e = (orig_height*2) - scaled_height; /* e = dy*2 - dx */
> +    dx2 = scaled_height*2; /* dx2 = dx*2 */
> +
> +    /* setup our parameters for doing DDA in the x direction */
> +    dest_dx = scaled_width;
> +    src_dx = orig_width;
> +    ex = (src_dx*2) - dest_dx;
> +    dx2x = dest_dx*2;
> +    src_dx *= 2;
> +
> +    /* Compute the src_offset and associated error value:
> +     * There are two ways to do this: */
> +    /* 1. Directly
> +    int nsrc_offset = (src_dx*startColumn + dest_dx)/(dest_dx*2);
> +    long nex = (src_dx*startColumn + dest_dx)%(dest_dx*2) - dest_dx*2 +
> src_dx; */
> +    /* 2. Iteratively */
> +    for (d = 0; d < start_column; d++) {
> +        while (ex > 0) {
> +            src_offset++;
> +            ex -= dx2x;
> +        }
> +        ex += src_dx;
> +    }
> +
> +    /* seek to the begining */
> +    for (d = 0; d < start_row; d++) {
> +        while (e > 0) {
> +            e -= dx2;
> +            y++;
> +        }
> +        e += src_dy;
> +    }
> +
> +    /* we need to allocate enough room for ceil(src_height/dest_height)
> scanlines */
> +    temp_buf = pixman_malloc_abc ((orig_height +
> scaled_height-1)/scaled_height, scaled_width, sizeof(uint32_t));
> +
> +    scanline = fetcher->init (closure);
> +
> +    if (!scanline || !temp_buf) {
> +        return -1;
> +    }
> +
> +    for (d = start_row; d < start_row + height; d++)
> +    {
> +        int columns = 0;
> +        while (e > 0)
> +        {
> +            fetcher->fetch_scanline (closure, y, &scanline);
> +
> +            /* XXX: We could turn this multiplication into addition. It
> +             * probably doesn't matter though  */
> +            downsample_row_box_filter (width, scanline + src_offset, temp_buf
> + width * columns,
> +                                       dx2x, ex, src_dx);
> +
> +            e -= dx2;
> +            columns++;
> +            y++;
> +        }
> +
> +        downsample_columns_box_filter (width, columns, temp_buf, dest);
> +
> +        dest += dst_stride/4;
> +        e += src_dy;
> +    }
> +
> +    fetcher->fini (closure, scanline);
> +    free (temp_buf);
> +
> +    return 0;
> +}
> +
> diff --git a/pixman/pixman-rescale-lanczos.c b/pixman/pixman-rescale-lanczos.c
> new file mode 100644
> index 0000000..864fd6d
> --- /dev/null
> +++ b/pixman/pixman-rescale-lanczos.c
> @@ -0,0 +1,483 @@
> +/* -*- Mode: c; c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t; -*- */
> +/*
> + * Copyright © 2009 Mozilla Corporation
> + *
> + * Permission to use, copy, modify, distribute, and sell this software and its
> + * documentation for any purpose is hereby granted without fee, provided that
> + * the above copyright notice appear in all copies and that both that
> + * copyright notice and this permission notice appear in supporting
> + * documentation, and that the name of Mozilla Corporation not be used in
> + * advertising or publicity pertaining to distribution of the software without
> + * specific, written prior permission.  Mozilla Corporation makes no
> + * representations about the suitability of this software for any purpose.  It
> + * is provided "as is" without express or implied warranty.
> + *
> + * MOZILLA CORPORATION DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
> + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT
> + * SHALL MOZILLA CORPORATION BE LIABLE FOR ANY SPECIAL, INDIRECT OR
> + * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
> + * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
> + * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
> + * OF THIS SOFTWARE.
> + *
> + * Author: Jeff Muizelaar, Mozilla Corp.
> + *
> + * Portions derived from Chromium:
> + *
> + * Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
> + *
> + * Redistribution and use in source and binary forms, with or without
> + * modification, are permitted provided that the following conditions are
> + * met:
> + *
> + *    * Redistributions of source code must retain the above copyright
> + * notice, this list of conditions and the following disclaimer.
> + *    * Redistributions in binary form must reproduce the above
> + * copyright notice, this list of conditions and the following disclaimer
> + * in the documentation and/or other materials provided with the
> + * distribution.
> + *    * Neither the name of Google Inc. nor the names of its
> + * contributors may be used to endorse or promote products derived from
> + * this software without specific prior written permission.
> + *
> + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
> + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
> + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
> + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
> + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
> + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
> + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
> + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
> + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
> + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
> + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
> + */
> +
> +#ifdef HAVE_CONFIG_H
> +#include <config.h>
> +#endif
> +
> +#include <stdint.h>
> +#include <stdio.h>
> +#include <assert.h>
> +#include <stdlib.h>
> +#include <float.h>
> +#include <math.h>
> +#include "pixman-private.h"
> +#include "pixman-rescale.h"
> +
> +
> +#define FILTER_SHIFT 14
> +#define LANCZOS_LOBES 2
> +
> +/* contains the filter for each destination pixel */
> +struct filter {
> +    int count; /* filter size */
> +    int16_t *values; /* filter coefficients */
> +    int offset; /* filter start offset */
> +};
> +
> +static int clamp(int a)
> +{
> +    if (a > 255)
> +        return 255;
> +    if (a < 0)
> +        return 0;
> +    return a;
> +}
> +
> +/* from ffmpeg */
> +static inline uint8_t clip_uint8(int a)
> +{
> +    if (a&(~255)) /* check if any of the high bits are set */
> +        return (-a)>>31; /* clip to either 0 or 255 */
> +    else
> +        return a;
> +}
> +
> +#if 0
> +#include <pmmintrin.h>
> +#include <emmintrin.h>
> +static void
> +downsample_row_convolve_sse2(int n,
> +        uint32_t *src, uint32_t *dest,
> +                const struct filter *filter, int src_size)
> +{
> +    int pixel = 0;
> +    while (n--) {
> +        int i;
> +        __m128i accum = _mm_setzero_si128 ();
> +        __m128i zero  = _mm_setzero_si128 ();
> +        for (i=0; i<filter[pixel].count; i++) {
> +            __m128i v_src = _mm_cvtsi32_si128 (src[filter[pixel].offset + i]);
> +            v_src = _mm_unpacklo_epi16 (_mm_unpacklo_epi8 (v_src, zero), zero);
> +
> +            __m128i coeff = _mm_cvtsi32_si128 (filter[pixel].values[i]);
> +            /* duplicate the filter coefficient */
> +            coeff = _mm_shuffle_epi32 (coeff, _MM_SHUFFLE (0, 0, 0, 0));
> +
> +            /* multiply and accumulate the result:
> +             * 0000vvvv_0000vvvv_0000vvvv_0000vvvv *
> 000000aa_000000rr_000000gg_000000bb */
> +            __m128i result = _mm_madd_epi16 (v_src, coeff);
> +            accum = _mm_add_epi32 (accum, result);
> +        }
> +
> +        /* scale the accumulator down */
> +        accum = _mm_srai_epi32 (accum, FILTER_SHIFT);
> +
> +        /* pack 000000aa_000000rr_000000gg_000000bb ->
> 00000000_00000000_00000000_aarrggbb */
> +        accum = _mm_packs_epi32 (accum, accum);
> +
> +        //XXX: this should be need to saturate properly but doesn't seem to
> make a difference
> +        accum = _mm_max_epi16 (accum, zero);
> +
> +        accum = _mm_packus_epi16 (accum, accum);
> +
> +        *dest = _mm_cvtsi128_si32 (accum);
> +        dest++;
> +        pixel++;
> +    }
> +}
> +#endif
> +
> +static void
> +downsample_row_convolve(int n,
> +        uint32_t *src, uint32_t *dest,
> +                struct filter *filter, int src_size)
> +{
> +    int pixel = 0;
> +    while (n--)
> +    {
> +        int32_t a = 0;
> +        int32_t r = 0;
> +        int32_t g = 0;
> +        int32_t b = 0;
> +        int i;
> +
> +        for (i=0; i<filter[pixel].count; i++) {
> +            a += ((src[filter[pixel].offset + i] >> 24) & 0xff) *
> filter[pixel].values[i];
> +            r += ((src[filter[pixel].offset + i] >> 16) & 0xff) *
> filter[pixel].values[i];
> +            g += ((src[filter[pixel].offset + i] >>  8) & 0xff) *
> filter[pixel].values[i];
> +            b += ((src[filter[pixel].offset + i] >>  0) & 0xff) *
> filter[pixel].values[i];
> +        }
> +
> +        a >>= FILTER_SHIFT;
> +        r >>= FILTER_SHIFT;
> +        g >>= FILTER_SHIFT;
> +        b >>= FILTER_SHIFT;
> +
> +        a = clamp (a);
> +        r = clamp (r);
> +        g = clamp (g);
> +        b = clamp (b);
> +
> +        *dest = (a << 24) | (r << 16) | (g << 8) | b;
> +        dest++;
> +        pixel++;
> +    }
> +}
> +
> +/* src1 and src2 are two contiguous regions of samples. We need two to handle
> + * the ring buffer that is used by the caller
> + *
> + * instead of src1, src1_length, src2, filter_length we could pass:
> + * ring_buf, start_index, ring_buf_length, filter_length,
> + * this is implicitly coded in the parameters we do pass:
> + * src1 = ring_buf + start_index
> + * src1_length = min(ring_buf_length - start_index, filter_length)
> + * src2 = ring_buf */
> +static void
> +downsample_columns_convolve(int n,
> +        uint32_t *src1, int src1_length,
> +        uint32_t *src2,
> +        uint32_t *dest,
> +        int16_t *filter, int filter_length)
> +{
> +    int stride = n;
> +    while (n--)
> +    {
> +        int32_t a = 0;
> +        int32_t r = 0;
> +        int32_t g = 0;
> +        int32_t b = 0;
> +        int i;
> +        uint32_t *column_src;
> +
> +        /* we do the accumulation in two steps because the source lines are in
> a ring buffer
> +         * so won't be contiguous */
> +        column_src = src1;
> +        for (i=0; i<src1_length; i++) /* loop till the end of the ring buffer
> */
> +        {
> +            a += ((*column_src >> 24) & 0xff) * filter[i];
> +            r += ((*column_src >> 16) & 0xff) * filter[i];
> +            g += ((*column_src >>  8) & 0xff) * filter[i];
> +            b += ((*column_src >>  0) & 0xff) * filter[i];
> +            column_src += stride;
> +        }
> +
> +        /* accumulate the remaining samples starting at the begining of the
> ring buffer */
> +        column_src = src2;
> +        for (; i<filter_length; i++)
> +        {
> +            a += ((*column_src >> 24) & 0xff) * filter[i];
> +            r += ((*column_src >> 16) & 0xff) * filter[i];
> +            g += ((*column_src >>  8) & 0xff) * filter[i];
> +            b += ((*column_src >>  0) & 0xff) * filter[i];
> +            column_src += stride;
> +        }
> +
> +        a >>= FILTER_SHIFT;
> +        r >>= FILTER_SHIFT;
> +        g >>= FILTER_SHIFT;
> +        b >>= FILTER_SHIFT;
> +
> +        a = clamp (a);
> +        r = clamp (r);
> +        g = clamp (g);
> +        b = clamp (b);
> +
> +        *dest = (a << 24) | (r << 16) | (g << 8) | b;
> +        dest++;
> +        src1++;
> +        src2++;
> +    }
> +}
> +
> +
> +/* Evaluates the Lanczos filter of the given filter size window for the given
> + * position.
> + *
> + * |filter_size| is the width of the filter (the "window"), outside of which
> + * the value of the function is 0. Inside of the window, the value is the
> + * normalized sinc function:
> + *   lanczos(x) = sinc(x) * sinc(x / filter_size);
> + * where
> + *   sinc(x) = sin(pi*x) / (pi*x);
> + */
> +float eval_lanczos(int filter_size, float x)
> +{
> +  if (x <= -filter_size || x >= filter_size)
> +    return 0.0f;  /* Outside of the window. */
> +  if (x > -FLT_EPSILON &&
> +      x < FLT_EPSILON)
> +    return 1.0f;  /* Special case the discontinuity at the origin. */
> +  else {
> +      float xpi = x * (M_PI);
> +      return (sin(xpi) / xpi) *  /* sinc(x) */
> +          sin(xpi / filter_size) / (xpi / filter_size);  /*
> sinc(x/filter_size) */
> +  }
> +}
> +
> +/* dealing with the edges:
> +   some options:
> +   we could always have approximately the same number of samples in the filter
> and just pad the image out
> +   chromium seems to truncate the filter though...
> +   I don't really have a good reason to choose either approach...
> +   one way to get an idea is to see what other implementation do.
> +   - it looks like quartz pads
> +   - chromium truncates the filter
> +   - opera pads
> +*/
> +
> +int floor_int(float a)
> +{
> +    return floor(a);
> +}
> +
> +int ceil_int(float a)
> +{
> +    return ceil(a);
> +}
> +
> +int float_to_fixed(float a)
> +{
> +    return a * (1 << FILTER_SHIFT);
> +}
> +
> +/* this method does not do source clipping
> + * but will do dest clipping */
> +struct filter *compute_lanczos_filter(int dest_subset_lo, int
> dest_subset_size, int src_size, float scale)
> +{
> +    /* this is half the number of pixels that the filter uses in filter space
> */
> +    int dest_support = LANCZOS_LOBES;
> +    float src_support = dest_support / scale;
> +
> +    /* we need to compute a set of filters for each pixel */
> +    /* filter width */
> +    int i;
> +    struct filter *filter = malloc (dest_subset_size * sizeof(struct filter));
> +    int max_filter_size = ceil_int (src_support * 2) - floor_int (src_support
> * -2) + 1;
> +    float *filter_values = malloc (max_filter_size * sizeof(float)); /* this
> is a good candidate for stack allocation */
> +    int dest_subset_hi = dest_subset_lo + dest_subset_size; /* [lo, hi) */
> +
> +
> +    /* When we're doing a magnification, the scale will be larger than one.
> This
> +     * means the destination pixels are much smaller than the source pixels,
> and
> +     * that the range covered by the filter won't necessarily cover any source
> +     * pixel boundaries. Therefore, we use these clamped values (max of 1) for
> +     * some computations.
> +     */
> +    float clamped_scale = MIN (1., scale);
> +
> +    /* Speed up the divisions below by turning them into multiplies. */
> +    float inv_scale = 1. / scale;
> +
> +    /* Loop over all pixels in the output range. We will generate one set of
> +     * filter values for each one. Those values will tell us how to blend the
> +     * source pixels to compute the destination pixel.
> +     */
> +    int dest_subset_i;
> +    int pixel = 0;
> +    for (dest_subset_i = dest_subset_lo; dest_subset_i < dest_subset_hi;
> dest_subset_i++, pixel++) {
> +
> +        float src_pixel = dest_subset_i * inv_scale;
> +
> +        int src_begin = MAX (0, floor_int (src_pixel - src_support));
> +        int src_end = MIN (src_size - 1, ceil_int (src_pixel + src_support));
> +
> +        /* Compute the unnormalized filter value at each location of the source
> +         * it covers. */
> +        float filter_sum = 0.; /* sum of the filter values for normalizing */
> +        int filter_size = 0;
> +        int cur_filter_pixel;
> +        int j = 0;
> +
> +        assert(src_begin >= 0);
> +
> +        for (cur_filter_pixel = src_begin; cur_filter_pixel <= src_end;
> +                cur_filter_pixel++)
> +        {
> +            /* Distance from the center of the filter, this is the filter
> coordinate
> +             * in source space. */
> +            float src_filter_pos = cur_filter_pixel - src_pixel;
> +
> +            /* Since the filter really exists in dest space, map it there. */
> +            float dest_filter_pos = src_filter_pos * clamped_scale;
> +
> +            /* Compute the filter value at that location. */
> +            float filter_value = eval_lanczos(LANCZOS_LOBES, dest_filter_pos);
> +            filter_sum += filter_value;
> +            filter_values[j] = filter_value;
> +
> +            filter_size++;
> +            j++;
> +        }
> +
> +        assert(src_end >= src_begin);
> +        assert(filter_size <= max_filter_size);
> +
> +        {
> +            int16_t leftovers;
> +            /* XXX: eventually we should avoid doing malloc here and just
> malloc a big
> +             * chunk of max_filter_size * sizeof(int16_t) */
> +            int16_t *fixed_filter_values = malloc (filter_size *
> sizeof(int16_t));
> +
> +            /* the filter must be normalized so that we don't affect the
> brightness of
> +             * the image. Convert to normalized fixed point */
> +            /* XXX: It might be better if we didn't have to do this in a
> separate pass */
> +            int16_t fixed_sum = 0; /* XXX: should we use a regular int here? */
> +            for (i=0; i<filter_size; i++)
> +            {
> +                int16_t cur_fixed = float_to_fixed(filter_values[i] /
> filter_sum);
> +                fixed_sum += cur_fixed;
> +                fixed_filter_values[i] = cur_fixed;
> +            }
> +
> +            /* The conversion to fixed point will leave some rounding errors,
> which
> +             * we add back in to avoid affecting the brightness of the image.
> We
> +             * arbitrarily add this to the center of the filter array (this
> won't always
> +             * be the center of the filter function since it could get clipped
> on the
> +             * edges, but it doesn't matter enough to worry about that case).
> */
> +            leftovers = float_to_fixed(1.0f) - fixed_sum;
> +            fixed_filter_values[filter_size / 2] += leftovers;
> +
> +            filter[pixel].values = fixed_filter_values;
> +            filter[pixel].count = filter_size;
> +            filter[pixel].offset = src_begin;
> +            assert (filter[pixel].offset >= 0);
> +            assert (filter[pixel].offset + filter[pixel].count - 1 < src_size);
> +        }
> +    }
> +
> +    free (filter_values);
> +    return filter;
> +}
> +
> +/* start_column and start_row are in destination space */
> +PIXMAN_EXPORT
> +int downscale_lanczos_filter(const struct rescale_fetcher *fetcher, void
> *closure, unsigned orig_width, unsigned orig_height,
> +        signed scaled_width, signed scaled_height,
> +        uint16_t start_column, uint16_t start_row,
> +        uint16_t width, uint16_t height,
> +        uint32_t *dest, int dst_stride)
> +{
> +    struct filter *x_filter, *y_filter;
> +    int filter_index;
> +    int src_index = 0;
> +    int i;
> +
> +    /* XXX: this duplicates code in compute_lanczos_filter */
> +    int dest_support = LANCZOS_LOBES;
> +    float src_support = dest_support / ((float)scaled_height/orig_height);
> +
> +    int max_filter_size = ceil_int (src_support * 2) - floor_int (src_support
> * -2) + 1;
> +
> +    /* we use a ring buffer to store the downsampled rows because we want to
> +     * reuse the downsampled rows across different destination pixels */
> +    int ring_buf_size = max_filter_size;
> +    uint32_t *ring_buf = pixman_malloc_abc (ring_buf_size, scaled_width,
> sizeof(uint32_t));
> +
> +    uint32_t *scanline = fetcher->init (closure);
> +    void (*fetch_scanline)(void *closure, int y, uint32_t **scanline) =
> fetcher->fetch_scanline;
> +
> +    assert (start_column + width  <= scaled_width);
> +    assert (start_row    + height <= scaled_height);
> +
> +    x_filter = compute_lanczos_filter (start_column, width,  orig_width, 
> (float)scaled_width/orig_width);
> +    y_filter = compute_lanczos_filter (start_row,    height, orig_height,
> (float)scaled_height/orig_height);
> +
> +    if (!ring_buf || !scanline || !x_filter || !y_filter)
> +        return -1;
> +
> +    for (filter_index = 0; filter_index < height; filter_index++)
> +    {
> +        int filter_size   = y_filter[filter_index].count;
> +        int filter_offset = y_filter[filter_index].offset;
> +        int src1_index, src1_size;
> +        uint32_t *src1;
> +        assert(filter_offset >= 0);
> +
> +        /* read and downsample the rows needed to downsample the next column */
> +        while (src_index < filter_offset + filter_size)
> +        {
> +            fetch_scanline (closure, src_index, &scanline);
> +            /* downsample_row_convolve_sse2 (width, scanline, ring_buf + width
> * (src_index % ring_buf_size), x_filter, orig_width); */
> +            downsample_row_convolve(width, scanline, ring_buf + width *
> (src_index % ring_buf_size), x_filter, orig_width);
> +            src_index++;
> +        }
> +
> +        src1_index = filter_offset % ring_buf_size;
> +        assert (src1_index >= 0);
> +        assert (filter_size <= ring_buf_size);
> +        src1 = ring_buf + width * src1_index;
> +
> +        src1_size = MIN (ring_buf_size - src1_index, filter_size);
> +        assert (src1_size >= 0);
> +        assert (filter_size >= src1_size);
> +
> +        downsample_columns_convolve (width, src1, src1_size, ring_buf, dest,
> y_filter[filter_index].values, y_filter[filter_index].count);
> +        dest += dst_stride/4;
> +    }
> +
> +    free (ring_buf);
> +    fetcher->fini (closure, scanline);
> +
> +    for (i=0; i<width; i++)
> +        free (x_filter[i].values);
> +    for (i=0; i<height; i++)
> +        free (y_filter[i].values);
> +    free (x_filter);
> +    free (y_filter);
> +
> +    return 0;
> +}
> diff --git a/pixman/pixman-rescale-mult-old.c b/pixman/pixman-rescale-mult-old.c
> new file mode 100644
> index 0000000..861d9e7
> --- /dev/null
> +++ b/pixman/pixman-rescale-mult-old.c
> @@ -0,0 +1,290 @@
> +/* -*- Mode: c; c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t; -*- */
> +/*
> + * Copyright © 2009 Mozilla Corporation
> + *
> + * Permission to use, copy, modify, distribute, and sell this software and its
> + * documentation for any purpose is hereby granted without fee, provided that
> + * the above copyright notice appear in all copies and that both that
> + * copyright notice and this permission notice appear in supporting
> + * documentation, and that the name of Mozilla Corporation not be used in
> + * advertising or publicity pertaining to distribution of the software without
> + * specific, written prior permission.  Mozilla Corporation makes no
> + * representations about the suitability of this software for any purpose.  It
> + * is provided "as is" without express or implied warranty.
> + *
> + * MOZILLA CORPORATION DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
> + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT
> + * SHALL MOZILLA CORPORATION BE LIABLE FOR ANY SPECIAL, INDIRECT OR
> + * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
> + * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
> + * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
> + * OF THIS SOFTWARE.
> + *
> + * Author: Jeff Muizelaar, Mozilla Corp.
> + */
> +
> +#if 0
> +
> +/* This implements a box filter that supports non-integer box sizes */
> +
> +#ifdef HAVE_CONFIG_H
> +#include <config.h>
> +#endif
> +
> +#include <stdint.h>
> +#include <stdio.h>
> +#include <assert.h>
> +#include <stdlib.h>
> +#include "pixman-private.h"
> +#include "pixman-rescale.h"
> +#define abs(a) (a) > 0 ? (a) : -(a)
> +#define sign(x) ((x)>0 ? 1:-1)
> +
> +static void fetch_scanline(void *closure, int y, uint32_t *scanline)
> +{
> +    pixman_image_t *pict = closure;
> +    bits_image_t *bits = &pict->bits;
> +    if (y > pict->bits.height-1)
> +        y = pict->bits.height-1;
> +    if (!pixman_image_has_source_clipping(pict)) {
> +        fetchProc32 fetch = ACCESS(pixman_fetchProcForPicture32)(bits);
> +        fetch(bits, 0, y, pict->bits.width, scanline);
> +    } else {
> +        int x;
> +        fetchPixelProc32 fetch =
> ACCESS(pixman_fetchPixelProcForPicture32)(bits);
> +        for (x=0; x<bits->width; x++) {
> +            if (pixman_region32_contains_point (bits->common.src_clip, x,
> y,NULL))
> +                scanline[x] = fetch (bits, x, y);
> +            else
> +                scanline[x] = 0;
> +        }
> +    }
> +}
> +
> +/* we work in fixed point where 1. == 1 << 24 */
> +#define FIXED_SHIFT 24
> +
> +static void downsample_row_box_filter(
> +        int n,
> +        uint32_t *src, uint32_t *dest,
> +                int coverage[], int pixel_coverage)
> +{
> +    /* we need an array of the pixel contribution of each destination pixel on
> the boundaries.
> +     * we invert the value to get the value on the other size of the box */
> +    /*
> +
> +       value  = a * contribution * 1/box_size
> +       value += a * 1/box_size
> +       value += a * 1/box_size
> +       value += a * 1/box_size
> +       value += a * (1 - contribution) * 1/box_size
> +                a * (1/box_size - contribution * 1/box_size)
> +
> +        box size is constant
> +
> +
> +       value = a * contribtion_a * 1/box_size + b * contribution_b * 1/box_size
> +               contribution_b = (1 - contribution_a)
> +                              = (1 - contribution_a_next)
> +    */
> +
> +    /* box size = ceil(src_width/dest_width) */
> +
> +    int x = 0;
> +    while (n--) {
> +        uint32_t a = 0;
> +        uint32_t r = 0;
> +        uint32_t g = 0;
> +        uint32_t b = 0;
> +        int box = 1 << FIXED_SHIFT;
> +        int start_coverage = coverage[x];
> +        a = ((*src >> 24) & 0xff) * start_coverage;
> +        r = ((*src >> 16) & 0xff) * start_coverage;
> +        g = ((*src >>  8) & 0xff) * start_coverage;
> +        b = ((*src >>  0) & 0xff) * start_coverage;
> +        src++;
> +        x++;
> +        box -= start_coverage;
> +        while (box >= pixel_coverage) {
> +            a += ((*src >> 24) & 0xff) * pixel_coverage;
> +            r += ((*src >> 16) & 0xff) * pixel_coverage;
> +            g += ((*src >>  8) & 0xff) * pixel_coverage;
> +            b += ((*src >>  0) & 0xff) * pixel_coverage;
> +            src++;
> +            x++;
> +
> +            box -= pixel_coverage;
> +        }
> +        /* multiply by whatever is leftover
> +         * this ensures that we don't bias down.
> +         * i.e. start_coverage + n*pixel_coverage + box == 1 << 24 */
> +        if (box > 0) {
> +            a += ((*src >> 24) & 0xff) * box;
> +            r += ((*src >> 16) & 0xff) * box;
> +            g += ((*src >>  8) & 0xff) * box;
> +            b += ((*src >>  0) & 0xff) * box;
> +        }
> +
> +        a >>= FIXED_SHIFT;
> +        r >>= FIXED_SHIFT;
> +        g >>= FIXED_SHIFT;
> +        b >>= FIXED_SHIFT;
> +
> +        *dest = (a << 24) | (r << 16) | (g << 8) | b;
> +        dest++;
> +    }
> +}
> +
> +static void downsample_columns_box_filter(
> +        int n,
> +        int start_coverage,
> +        int pixel_coverage,
> +        uint32_t *src, uint32_t *dest)
> +{
> +    int stride = n;
> +    while (n--) {
> +        uint32_t a = 0;
> +        uint32_t r = 0;
> +        uint32_t g = 0;
> +        uint32_t b = 0;
> +        uint32_t *column_src = src;
> +        int box = 1 << FIXED_SHIFT;
> +        a = ((*column_src >> 24) & 0xff) * start_coverage;
> +        r = ((*column_src >> 16) & 0xff) * start_coverage;
> +        g = ((*column_src >>  8) & 0xff) * start_coverage;
> +        b = ((*column_src >>  0) & 0xff) * start_coverage;
> +        column_src += stride;
> +        box -= start_coverage;
> +        while (box >= pixel_coverage) {
> +            a += ((*column_src >> 24) & 0xff) * pixel_coverage;
> +            r += ((*column_src >> 16) & 0xff) * pixel_coverage;
> +            g += ((*column_src >>  8) & 0xff) * pixel_coverage;
> +            b += ((*column_src >>  0) & 0xff) * pixel_coverage;
> +            column_src += stride;
> +            box -= pixel_coverage;
> +        }
> +        if (box > 0) {
> +            a += ((*column_src >> 24) & 0xff) * box;
> +            r += ((*column_src >> 16) & 0xff) * box;
> +            g += ((*column_src >>  8) & 0xff) * box;
> +            b += ((*column_src >>  0) & 0xff) * box;
> +        }
> +        a >>= FIXED_SHIFT;
> +        r >>= FIXED_SHIFT;
> +        g >>= FIXED_SHIFT;
> +        b >>= FIXED_SHIFT;
> +
> +        *dest = (a << 24) | (r << 16) | (g << 8) | b;
> +        dest++;
> +        src++;
> +    }
> +}
> +
> +#if 1
> +int compute_coverage(int coverage[], int src_length, int dest_length) {
> +    int i;
> +    /* num = src_length/dest_length
> +       total = sum(pixel) / num
> +
> +       pixel * 1/num == pixel * dest_length / src_length
> +    */
> +    int full = 1<<24;
> +    /* the average contribution of each source pixel */
> +    int ratio = ((1 << 24)*(long long int)dest_length)/src_length;
> +    int finished = ((1 << 24)*(long long int)dest_length) - (((1 << 24)*(long
> long int)dest_length)/src_length)*src_length;
> +    int p=0;
> +    int p2;
> +    int remainder = full;
> +    /* because ((1 << 24)*(long long int)dest_length) won't always be
> divisible by src_length
> +     * we'll need someplace to put the other bits.
> +     *
> +     * We want to ensure a + n*ratio < 1<<24
> +     *
> +     * 1<<24
> +     * */
> +    for (i=0; i<src_length; i++) {
> +        if (remainder < ratio) {
> +            p = ratio - remainder;
> +            remainder = full - p;
> +        } else {
> +            p = ratio;
> +            remainder -= ratio;
> +        }
> +
> +        if ((((i+1)*ratio) % full) < ratio) {
> +            p2 = (((i+1)*ratio) % full);
> +        } else {
> +            p2 = ratio;
> +        }
> +
> +        //printf("%d %d %d %d %d\n", i, p, remainder, (i+1)*ratio, p2);
> +        //assert(p == p2);
> +
> +        coverage[i] = p;
> +    }
> +    //assert(remainder == 0);
> +    return ratio;
> +}
> +#endif
> +
> +
> +PIXMAN_EXPORT
> +int downscale_box_mult_old_filter(pixman_image_t *pict, unsigned origWidth,
> unsigned origHeight,
> +        signed scaledWidth, signed scaledHeight,
> +        uint16_t startColumn, uint16_t startRow,
> +        uint16_t width, uint16_t height,
> +        uint32_t *src, int srcStride,
> +        uint32_t *dest, int dstStride)
> +{
> +   // printf("%d %d %d %d\n", scaledWidth, scaledHeight, origWidth,
> origHeight);
> +        int yd1 = 0;
> +        int d;
> +
> +        /* we need to allocate enough room for ceil(src_height/dest_height)
> scanlines */
> +        uint32_t *temp_buf = pixman_malloc_abc ((origHeight +
> scaledHeight-1)/scaledHeight, scaledWidth, sizeof(uint32_t));
> +    if (!temp_buf)
> +            return -1;
> +
> +    //XXX: I suppose we should check whether this will succeed
> +        uint32_t *scanline = pixman_malloc_abc (origWidth, 1,
> sizeof(uint32_t));
> +
> +        int *x_coverage = pixman_malloc_abc (origWidth, 1, sizeof(int));
> +        int *y_coverage = pixman_malloc_abc (origHeight, 1, sizeof(int));
> +        int pixel_coverage_x = compute_coverage(x_coverage, origWidth,
> scaledWidth);
> +        int pixel_coverage_y = compute_coverage(y_coverage, origHeight,
> scaledHeight);
> +
> +        int y = 0;
> +        for (d = 0; d < startRow + height; d++)
> +    {
> +            int columns = 0;
> +            int box = 1 << FIXED_SHIFT;
> +            int start_coverage_y = y_coverage[y];
> +            fetch_scanline(pict, y, scanline);
> +            downsample_row_box_filter(width, scanline, temp_buf + width *
> columns,
> +                    x_coverage, pixel_coverage_x);
> +            columns++;
> +            y++;
> +            box -= start_coverage_y;
> +
> +            while (box >= pixel_coverage_y) {
> +                fetch_scanline(pict, y, scanline);
> +                downsample_row_box_filter(width, scanline, temp_buf + width *
> columns,
> +                    x_coverage, pixel_coverage_x);
> +                columns++;
> +                y++;
> +                box -= pixel_coverage_y;
> +            }
> +            if (box > 0) {
> +                fetch_scanline(pict, y, scanline);
> +                downsample_row_box_filter(width, scanline, temp_buf + width *
> columns,
> +                    x_coverage, pixel_coverage_x);
> +                columns++;
> +            }
> +            downsample_columns_box_filter(width, start_coverage_y,
> pixel_coverage_y, temp_buf, dest + (yd1 - startRow)*dstStride/4);
> +            yd1++;
> +        }
> +        free(temp_buf);
> +        return 0;
> +}
> +
> +#endif
> diff --git a/pixman/pixman-rescale.c b/pixman/pixman-rescale.c
> new file mode 100644
> index 0000000..20e2e7c
> --- /dev/null
> +++ b/pixman/pixman-rescale.c
> @@ -0,0 +1,124 @@
> +#ifdef HAVE_CONFIG_H
> +#include <config.h>
> +#endif
> +
> +#include <stdlib.h>
> +
> +#include "pixman-private.h"
> +#include "pixman-rescale.h"
> +
> +/* Fetcher documentation:
> + * Goals: we need a generic interface to fetch lines of ARGB32
> + * - we want to support converting to argb32
> + * - we also want to support having the rescaler read directly from the buffer
> + *   if the buffer is of a format compatible with the rescaler */
> +
> +static void fetch_convert(void *closure, int y, uint32_t **scanline_ptr)
> +{
> +    pixman_image_t *pict = closure;
> +    uint32_t *scanline = *scanline_ptr;
> +    pict->bits.fetch_scanline_raw_32(pict, 0, y, pict->bits.width, scanline,
> NULL, 0);
> +
> +}
> +
> +static uint32_t *fetch_convert_init(void *closure)
> +{
> +    pixman_image_t *pict = closure;
> +    return pixman_malloc_abc (pict->bits.width, 1, sizeof(uint32_t));
> +}
> +
> +static void fetch_convert_fini(void *closure, uint32_t *scanline)
> +{
> +    free(scanline);
> +}
> +
> +
> +static void fetch_raw(void *closure, int y, uint32_t **scanline)
> +{
> +    pixman_image_t *pict = closure;
> +    bits_image_t *bits = &pict->bits;
> +    /* set the scanline to the begining of the yth row */
> +    *scanline = bits->bits + y*bits->rowstride;
> +}
> +
> +static uint32_t *fetch_raw_init(void *closure)
> +{
> +    return closure;
> +}
> +
> +static void fetch_raw_fini(void *closure, uint32_t *scanline)
> +{
> +}
> +
> +const struct rescale_fetcher fetcher_convert = {
> +    fetch_convert,
> +    fetch_convert_init,
> +    fetch_convert_fini
> +};
> +
> +const struct rescale_fetcher fetcher_raw = {
> +    fetch_raw,
> +    fetch_raw_init,
> +    fetch_raw_fini
> +};
> +
> +/* downscale an pixman_image_t into an ARGB32 buffer
> + *
> + * scaled_width / original_width is the scale ratio
> + * using scaled_width instead of just passing in the ratio avoids any rounding
> errors because
> + * the ratio can be specified exactly
> + *
> + * start_column, start_row, width, height
> + * specify a rectangle in the scaled source space
> + *
> + * dest, dst_stride, width, and height allow specifying
> + * a rectangle in the destination buffer
> + */
> +PIXMAN_EXPORT
> +int downscale_image(pixman_image_t *pict, enum downscale_type type,
> +        int scaled_width, int scaled_height,
> +        int start_column, int start_row,
> +        int width, int height,
> +        uint32_t *dest, int dst_stride)
> +{
> +    const struct rescale_fetcher *fetcher;
> +    int orig_height = pict->bits.height;
> +    int orig_width  = pict->bits.width;
> +
> +    /* choose a fetcher */
> +    if (PIXMAN_FORMAT_BPP(pict->bits.format) == 32 &&
> +            PIXMAN_FORMAT_R(pict->bits.format) == 8 &&
> +            PIXMAN_FORMAT_G(pict->bits.format) == 8 &&
> +            PIXMAN_FORMAT_B(pict->bits.format) == 8)
> +    {
> +        fetcher = &fetcher_raw;
> +    } else
> +    {
> +        fetcher = &fetcher_convert;
> +    }
> +
> +    /* choose and run downscaler */
> +    switch (type)
> +    {
> +        case LANCZOS:
> +            return downscale_lanczos_filter(fetcher, pict, orig_width,
> orig_height,
> +                scaled_width, scaled_height,
> +                start_column, start_row,
> +                width, height,
> +                dest, dst_stride);
> +        case BOX:
> +            return downscale_box_filter(fetcher, pict, orig_width, orig_height,
> +                scaled_width, scaled_height,
> +                start_column, start_row,
> +                width, height,
> +                dest, dst_stride);
> +        case INTEGER_BOX:
> +            return downscale_integer_box_filter(fetcher, pict, orig_width,
> orig_height,
> +                scaled_width, scaled_height,
> +                start_column, start_row,
> +                width, height,
> +                dest, dst_stride);
> +        default:
> +            return -1;
> +    }
> +}
> diff --git a/pixman/pixman-rescale.h b/pixman/pixman-rescale.h
> new file mode 100644
> index 0000000..9c8cf73
> --- /dev/null
> +++ b/pixman/pixman-rescale.h
> @@ -0,0 +1,44 @@
> +#include "pixman-private.h"
> +struct rescale_fetcher
> +{
> +    void (*fetch_scanline)(void *closure, int y, uint32_t **scanline_ptr);
> +    uint32_t *(*init)(void *closure);
> +    void (*fini)(void *closure, uint32_t *scanline);
> +};
> +
> +enum downscale_type
> +{
> +    INTEGER_BOX,
> +    BOX,
> +    LANCZOS
> +};
> +
> +int downscale_image(pixman_image_t *image, enum downscale_type type,
> +        int scaled_width, int scaled_height,
> +        int start_column, int start_row,
> +        int width, int height,
> +        uint32_t *dest, int dst_stride);
> +
> +int downscale_integer_box_filter(
> +        const struct rescale_fetcher *fetcher, void *closure,
> +        unsigned orig_width, unsigned orig_height,
> +        signed scaledWidth, signed scaled_height,
> +        uint16_t start_column, uint16_t start_row,
> +        uint16_t width, uint16_t height,
> +        uint32_t *dest, int dst_stride);
> +
> +int downscale_box_filter(
> +        const struct rescale_fetcher *fetcher, void *closure,
> +        unsigned orig_width, unsigned orig_height,
> +        signed scaled_width, signed scaled_height,
> +        uint16_t start_column, uint16_t start_row,
> +        uint16_t width, uint16_t height,
> +        uint32_t *dest, int dst_stride);
> +
> +int downscale_lanczos_filter(
> +        const struct rescale_fetcher *fetcher, void *closure,
> +        unsigned orig_width, unsigned orig_height,
> +        signed scaledWidth, signed scaled_height,
> +        uint16_t start_column, uint16_t start_row,
> +        uint16_t width, uint16_t height,
> +        uint32_t *dest, int dst_stride);
-- 
Carlos Garcia Campos
PGP key: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x523E6462
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 197 bytes
Desc: not available
Url : http://lists.cairographics.org/archives/cairo/attachments/20091117/1adc406e/attachment-0001.pgp 


More information about the cairo mailing list