[cairo] pixman box filtering code prototype
Jeff Muizelaar
jeff at infidigm.net
Tue Nov 4 14:37:51 PST 2008
On Fri, Oct 24, 2008 at 11:09:34AM -0400, Jeff Muizelaar wrote:
> On Tue, Oct 14, 2008 at 03:00:21PM -0400, Jeff Muizelaar wrote:
> > For the default case, I think a better approach is to do a rectangular
> > box filter down to the scaled size and then do bilinear sampling from
> > this downscaled version as necessary. I think this should be more
> > performant than my box filtering code and should give the desired
> > quality for any affine matrix...
>
> I've attached a patch that has a rough implementation of this.
Here's an update. It should be basically correct at this time (although
it doesn't filter masks yet...). It still needs cleanup and
optimization.
-Jeff
diff --git a/pixman/Makefile.am b/pixman/Makefile.am
index 339e01e..4aa5f6d 100644
--- a/pixman/Makefile.am
+++ b/pixman/Makefile.am
@@ -26,6 +26,7 @@ libpixman_1_la_SOURCES = \
pixman-edge-imp.h \
pixman-trap.c \
pixman-compute-region.c \
+ pixman-rescale-box.c \
pixman-timer.c
libpixmanincludedir = $(includedir)/pixman-1/
diff --git a/pixman/pixman-image.c b/pixman/pixman-image.c
index e80c479..3c7526d 100644
--- a/pixman/pixman-image.c
+++ b/pixman/pixman-image.c
@@ -518,6 +518,14 @@ pixman_image_set_source_clipping (pixman_image_t *image,
common->src_clip = &common->full_region;
}
+PIXMAN_EXPORT pixman_bool_t
+pixman_image_has_source_clipping (pixman_image_t *image)
+{
+ image_common_t *common = &image->common;
+
+ return common->src_clip != &common->full_region;
+}
+
/* Unlike all the other property setters, this function does not
* copy the content of indexed. Doing this copying is simply
* way, way too expensive.
diff --git a/pixman/pixman-pict.c b/pixman/pixman-pict.c
index 070b190..0a73c13 100644
--- a/pixman/pixman-pict.c
+++ b/pixman/pixman-pict.c
@@ -36,6 +36,7 @@
#include "pixman-sse2.h"
#include "pixman-arm.h"
#include "pixman-combine32.h"
+#include "pixman-rescale-box.h"
#ifdef __GNUC__
# define inline __inline__ __attribute__ ((__always_inline__))
@@ -1770,6 +1771,56 @@ pixman_optimize_operator(pixman_op_t op, pixman_image_t *pSrc, pixman_image_t *p
}
+pixman_image_t *create_downscaled_image(pixman_image_t *img, int scaled_width, int scaled_height)
+{
+ pixman_image_t *new_src = pixman_image_create_bits (PIXMAN_a8r8g8b8,
+ scaled_width, scaled_height, NULL, scaled_width * sizeof(uint32_t*) // XXX: should this come from someplace else
+ );
+ if (!new_src)
+ goto fail;
+
+ if (downscale_box_filter(img, img->bits.width, img->bits.height,
+ scaled_width, scaled_height,
+ 0, 0,
+ scaled_width, scaled_height,
+ img->bits.bits, img->bits.rowstride*sizeof(uint32_t),
+ new_src->bits.bits, new_src->bits.rowstride*sizeof(uint32_t)))
+ goto resize_fail;
+
+ pixman_image_set_filter (new_src, img->common.filter,
+ img->common.filter_params,
+ img->common.n_filter_params);
+ pixman_transform_t new_transform = *(img->common.transform);
+//#define unscaled_debug
+#ifdef unscaled_debug
+ printf("%x %x %x, %x %x %x\n",
+ new_transform.matrix[0][0],
+ new_transform.matrix[0][1],
+ new_transform.matrix[0][2],
+ new_transform.matrix[1][0],
+ new_transform.matrix[1][1],
+ new_transform.matrix[1][2]);
+#endif
+ pixman_fixed_t scale_x, scale_y;
+ pixman_extract_scale (&new_transform, &scale_x, &scale_y);
+ pixman_transform_unscale (&new_transform, scale_x, scale_y);
+#if unscaled_debug
+ printf("%x %x %x, %x %x %x\n",
+ new_transform.matrix[0][0],
+ new_transform.matrix[0][1],
+ new_transform.matrix[0][2],
+ new_transform.matrix[1][0],
+ new_transform.matrix[1][1],
+ new_transform.matrix[1][2]);
+#endif
+ pixman_image_set_transform (new_src, &new_transform);
+ return new_src;
+
+resize_fail:
+ pixman_image_unref(new_src);
+fail:
+ return NULL;
+}
#if defined(USE_SSE2) && defined(__GNUC__) && !defined(__x86_64__) && !defined(__amd64__)
/*
@@ -1788,6 +1839,7 @@ pixman_optimize_operator(pixman_op_t op, pixman_image_t *pSrc, pixman_image_t *p
* See https://bugs.freedesktop.org/show_bug.cgi?id=15693
*/
+
__attribute__((__force_align_arg_pointer__))
#endif
PIXMAN_EXPORT void
@@ -1811,6 +1863,7 @@ pixman_image_composite (pixman_op_t op,
pixman_bool_t srcAlphaMap = pSrc->common.alpha_map != NULL;
pixman_bool_t maskAlphaMap = FALSE;
pixman_bool_t dstAlphaMap = pDst->common.alpha_map != NULL;
+ pixman_bool_t downscaled = FALSE;
CompositeFunc func = NULL;
#ifdef USE_MMX
@@ -1832,6 +1885,26 @@ pixman_image_composite (pixman_op_t op,
srcTransform = FALSE;
}
+
+ if (srcTransform && pSrc->type == BITS) {
+ int scaled_width;
+ int scaled_height;
+ pixman_get_scaled_size(pSrc->common.transform,
+ pSrc->bits.width, pSrc->bits.height,
+ &scaled_width, &scaled_height);
+ //printf("%d %d: %d %d\n", pSrc->bits.width, pSrc->bits.height, scaled_width, scaled_height);
+ if (scaled_width < pSrc->bits.width || scaled_height < pSrc->bits.height) {
+ if (pSrc->bits.format == PIXMAN_a8r8g8b8 && 1) {
+ //printf("downscale\n");
+ pSrc = create_downscaled_image(pSrc, scaled_width, scaled_height);
+ if (!pSrc)
+ return;
+ srcTransform = pSrc->common.transform != NULL;
+ downscaled = TRUE;
+ }
+ }
+ }
+
if (pMask && pMask->type == BITS)
{
maskRepeat = pMask->common.repeat == PIXMAN_REPEAT_NORMAL;
@@ -1966,6 +2039,8 @@ pixman_image_composite (pixman_op_t op,
pixman_walk_composite_region (op, pSrc, pMask, pDst, xSrc, ySrc,
xMask, yMask, xDst, yDst, width, height,
srcRepeat, maskRepeat, func);
+ if (downscaled)
+ pixman_image_unref(pSrc);
}
diff --git a/pixman/pixman-private.h b/pixman/pixman-private.h
index e26a0c3..ec5a6ba 100644
--- a/pixman/pixman-private.h
+++ b/pixman/pixman-private.h
@@ -709,6 +709,17 @@ pixman_rasterize_edges_accessors (pixman_image_t *image,
pixman_bool_t
pixman_image_is_opaque(pixman_image_t *image);
+void
+pixman_transform_unscale (pixman_transform_t *transform,
+ int height, int width);
+void
+pixman_get_scaled_size (pixman_transform_t *transform,
+ int height, int width,
+ int *scaled_height, int *scaled_width);
+
+void
+pixman_extract_scale (pixman_transform_t *transform,
+ int *scale_x, int *scale_y);
pixman_bool_t
pixman_image_can_get_solid (pixman_image_t *image);
@@ -792,4 +803,45 @@ void pixman_timer_register (PixmanTimer *timer);
#endif /* PIXMAN_TIMING */
+/**
+ * mul_fixed:
+ * @a: first number to multiply in fixed-point 16.16 format
+ * @b: second number to multiply in fixed-point 16.16 format
+ *
+ * Author : Frederic Plourde
+ **/
+static inline pixman_fixed_t
+mul_fixed (pixman_fixed_t a, pixman_fixed_t b)
+{
+ int64_t r = (int64_t)a * (int64_t)b;
+ return ( pixman_fixed_t )( r >> 16 );
+}
+
+/**
+ * div_fixed:
+ * @a: dividend in fixed-point 16.16 format
+ * @b: divisor in fixed-point 16.16 format
+ *
+ * Author : Frederic Plourde
+ **/
+static inline pixman_fixed_t
+div_fixed (pixman_fixed_t a, pixman_fixed_t b)
+{
+ int64_t div;
+
+ int64_t a_64 = ((int64_t)a) << 32 ;
+ int64_t b_64 = ((int64_t)b) << 16 ;
+
+ div = a_64 / b_64;
+
+ return (pixman_fixed_t)div;
+}
+
+static inline pixman_fixed_t
+square_fixed (pixman_fixed_t a)
+{
+ return mul_fixed(a,a);
+}
+
+
#endif /* PIXMAN_PRIVATE_H */
diff --git a/pixman/pixman-rescale-box.c b/pixman/pixman-rescale-box.c
new file mode 100644
index 0000000..9bf2ab6
--- /dev/null
+++ b/pixman/pixman-rescale-box.c
@@ -0,0 +1,369 @@
+/* -*- Mode: c; c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t; -*- */
+/*
+ * Copyright © 2008 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.
+ *
+ * Based on the code from "Fast Bitmap Strecthing" by Tomas Möller
+ *
+ * Scaling code from Graphics Gems book III
+ * http://www.acm.org/pubs/tog/GraphicsGems/gemsiii/fastBitmap.c
+ *
+ * License states - "All code here can be used without restrictions."
+ * http://www.acm.org/pubs/tog/GraphicsGems/
+ *
+ * Also inspired by Mozilla's gfx/src/imgScaler.c by
+ * Tim Rowley <tor at cs.brown.edu>
+ */
+
+/* The approach is inspired by Bresenham's line drawing algorithm
+ * A similar approach is used by SDL in its blitting code
+ * although they do have some intrastructure for dynamically
+ * generating code for a particular scaling.
+ *
+ * A more clever approach is used in Evas. It creates table of row indices
+ * and a table of column indices that map the destination coordinates
+ * to source pixels. This approach avoids having an additional conditional
+ * branch inside of the inner loop at the cost of having to precompute and
+ * access these tables.
+ *
+ * -- Jeff Muizelaar (July 2008) */
+
+#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-box.h"
+#define abs(a) (a) > 0 ? (a) : -(a)
+#define sign(x) ((x)>0 ? 1:-1)
+
+void fetch_scanline(void *closure, int y, uint32_t *scanline)
+{
+ pixman_image_t *pict = closure;
+ if (!pixman_image_has_source_clipping(pict)) {
+ fetchProc32 fetch = ACCESS(pixman_fetchProcForPicture32)(pict);
+ fetch(pict, 0, y, pict->bits.width, scanline);
+ } else {
+ int x;
+ bits_image_t *bits = &pict->bits;
+ 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;
+ }
+ }
+}
+
+
+/*
+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 r2
+ = 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 r2
+
+*/
+
+
+/* we can index on the bottom bit of the divisor.
+ *
+ * we could also do a multiply per pixel and accumulate precision
+*/
+/**********************************************************
+ Stretches a horizontal source line onto a horizontal
+ destination line. Used by RectStretch.
+**********************************************************/
+void downsample_row_box_filter(
+ int n,
+ uint32_t *src, uint32_t *dest,
+ long dx2, long e, long src_dx)
+{
+ while (n--) {
+ uint32_t a = 0;
+ uint32_t r = 0;
+ uint32_t g = 0;
+ uint32_t b = 0;
+ int count = 1;
+ a = (*src >> 24) & 0xff;
+ r = (*src >> 16) & 0xff;
+ g = (*src >> 8) & 0xff;
+ b = (*src >> 0) & 0xff;
+ while (e > 0) {
+ e -= dx2;
+ a += (*src >> 24) & 0xff;
+ r += (*src >> 16) & 0xff;
+ g += (*src >> 8) & 0xff;
+ b += (*src >> 0) & 0xff;
+ count++;
+ src++;
+ }
+ //XXX counts seem high...
+ a /= count;
+ r /= count;
+ g /= count;
+ b /= count;
+ *dest = (a << 24) | (r << 16) | (g << 8) | b;
+ dest++;
+
+ e += src_dx;
+ }
+}
+
+void downsample_row_box_filter_sse2(
+ int n,
+ uint32_t *src, uint32_t *dest,
+ long dx2, long e, long src_dx)
+{
+#if 0
+ while (n--) {
+ uint32_t a = 0;
+ uint32_t r = 0;
+ uint32_t g = 0;
+ uint32_t b = 0;
+ int count = 1;
+ a = (*src >> 24) & 0xff;
+ r = (*src >> 16) & 0xff;
+ g = (*src >> 8) & 0xff;
+ b = (*src >> 0) & 0xff;
+ while (e > 0) {
+ e -= dx2;
+ a += (*src >> 24) & 0xff;
+ r += (*src >> 16) & 0xff;
+ g += (*src >> 8) & 0xff;
+ b += (*src >> 0) & 0xff;
+ count++;
+ src++;
+ }
+ //XXX counts seem high...
+ a /= count;
+ r /= count;
+ g /= count;
+ b /= count;
+ *dest = (a << 24) | (r << 16) | (g << 8) | b;
+ dest++;
+
+ e += src_dx;
+ }
+#endif
+
+}
+
+
+void downsample_columns_box_filter(
+ int n,
+ int columns,
+ 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;
+ int h;
+ uint32_t *column_src = src;
+ 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;
+ }
+ a /= columns;
+ r /= columns;
+ g /= columns;
+ b /= columns;
+ *dest = (a << 24) | (r << 16) | (g << 8) | b;
+ dest++;
+ src++;
+ }
+}
+
+/**********************************************************
+ RectStretch enlarges or diminishes a source rectangle of
+ a bitmap to a destination rectangle. The source
+ rectangle is selected by the two points (xs1,ys1) and
+ (xs2,ys2), and the destination rectangle by (xd1,yd1) and
+ (xd2,yd2). Since readability of source-code is wanted,
+ some optimizations have been left out for the reader:
+ It's possible to read one line at a time, by first
+ stretching in x-direction and then stretching that bitmap
+ in y-direction.
+ Entry:
+ xs1,ys1 - first point of source rectangle
+ xs2,ys2 - second point of source rectangle
+ xd1,yd1 - first point of destination rectangle
+ xd2,yd2 - second point of destination rectangle
+**********************************************************/
+/* startColumn, startRow specify the index of the first source pixel from the source image.
+ * width and height specify the number of source pixels to be drawn
+ *
+ * origWidth, origHeight, scaledWidth and scaledHeight specify the scaling exactly
+ *
+ * x_center and y_center specify the offset within a pixel from which to start drawing
+ * they are, of course, specified in destination space
+ */
+#define ROUND
+//XXX:
+int downscale_box_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);
+ long xs2, ys2, xd2, yd2;
+ long yd1 = 0, ys1 = 0;
+ long xd1 = 0, xs1 = 0;
+ xs2 = origWidth ;
+ ys2 = origHeight ;
+ //xd2 = abs(scaledWidth) - 1;
+ xd2 = abs(scaledWidth) ;
+ yd2 = abs(scaledHeight) ;
+ long e,d,dx2;
+ short sy;
+ long dest_dy = abs(yd2);
+ long src_dy = abs(ys2);
+ if (scaledHeight < 0) {
+ ys1 = origHeight - ((src_dy<<1)+dest_dy)/(dest_dy << 1); // e = dy*2 - dx
+ sy = -1;
+ }
+ e = (src_dy<<1)-dest_dy; // e = dy*2 - dx
+ dx2 = dest_dy<<1; // dx2 = dx *2
+ src_dy <<= 1; // dy *= 2
+
+ long dest_dx,src_dx,ex,dx2x;
+ short src_sx;
+ dest_dx = abs(xd2);
+ src_dx = abs(xs2);
+ int src_direction = 1;
+#ifdef ROUND
+ ex = (src_dx<<1)-dest_dx;
+ dx2x = dest_dx<<1; // multiplying by 2 is for rounding purposes
+ src_dx <<= 1;
+#else
+ dx2x = dest_dx;
+ ex = src_dx - dest_dx;
+#endif
+
+ /* 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)*src_sx/(dest_dx*2);
+ long nex = (src_dx*startColumn + dest_dx)%(dest_dx*2) - dest_dx*2 + src_dx;
+ /* 2. Iteratively */
+ int src_offset = 0;
+ for (d = 0; d < startColumn; d++) {
+ //XXX: should be 'ex > 0'
+ while (ex > 0) {
+ src_offset += src_sx;
+ ex -= dx2x;
+ }
+ ex += src_dx;
+ }
+#if 0
+ if (nex != ex) {
+ printf("e: %d %d: %d %d %d\n", ex, nex, src_dx, startColumn, dest_dx);
+ assert(nex == ex);
+ }
+ if (nsrc_offset != src_offset) {
+ printf("off: %d %d: %d %d %d\n", src_offset, nsrc_offset, src_dx, startColumn, dest_dx);
+ assert(nsrc_offset == src_offset);
+ }
+
+#endif
+ //printf("src_offset %d %d %d\n", src_offset, nsrc_offset, ex);
+
+ src += src_offset;
+
+ /* we need to allocate enough room for ceil(src_height/dest_height) scanlines */
+ //XXX: I suppose we should check whether this will succeed
+ uint32_t *temp_buf = pixman_malloc_abc ((origHeight + scaledHeight-1)/scaledHeight, scaledWidth, sizeof(uint32_t));
+ if (!temp_buf)
+ return -1;
+
+ uint32_t *scanline = pixman_malloc_abc (origWidth, 1, sizeof(uint32_t));
+
+ int x = 0;
+ int y = 0;
+ for (d = 0; d < startRow + height; d++)
+ {
+ int columns = 0;
+ while (e > 0)
+ {
+ fetch_scanline(pict, y, scanline);
+ //XXX: we could turn these multiplications into additions
+ downsample_row_box_filter(width, src + ys1 * srcStride/4, temp_buf + width * columns,
+ dx2x, ex, src_dx);
+
+ ys1 ++;
+ e -= dx2;
+ columns++;
+ }
+ downsample_columns_box_filter(width, columns, temp_buf, dest + (yd1 - startRow)*dstStride/4);
+ yd1 += 1;
+ e += src_dy;
+ }
+ free(temp_buf);
+ return 0;
+}
+
diff --git a/pixman/pixman-transformed.c b/pixman/pixman-transformed.c
index fca1cdb..55cf4a8 100644
--- a/pixman/pixman-transformed.c
+++ b/pixman/pixman-transformed.c
@@ -555,11 +555,19 @@ ACCESS(fbFetchTransformed)(bits_image_t * pict, int x, int y, int width,
/* when using convolution filters or PIXMAN_REPEAT_PAD one might get here without a transform */
if (pict->common.transform)
{
- if (!pixman_transform_point_3d (pict->common.transform, &v))
+
+ pixman_transform_t transform = *pict->common.transform;
+#if 0
+ if (pict->downscaled) {
+ pict->downscale_width;
+ pict->downscale_height;
+ }
+#endif
+ if (!pixman_transform_point_3d (&transform, &v))
return;
- unit.vector[0] = pict->common.transform->matrix[0][0];
- unit.vector[1] = pict->common.transform->matrix[1][0];
- unit.vector[2] = pict->common.transform->matrix[2][0];
+ unit.vector[0] = transform.matrix[0][0];
+ unit.vector[1] = transform.matrix[1][0];
+ unit.vector[2] = transform.matrix[2][0];
affine = v.vector[2] == pixman_fixed_1 && unit.vector[2] == 0;
}
else
diff --git a/pixman/pixman-utils.c b/pixman/pixman-utils.c
index 22f522b..0f9af59 100644
--- a/pixman/pixman-utils.c
+++ b/pixman/pixman-utils.c
@@ -26,6 +26,7 @@
#endif
#include <stdlib.h>
+#include <math.h>
#include "pixman-private.h"
#include "pixman-mmx.h"
@@ -63,6 +64,271 @@ pixman_transform_point_3d (pixman_transform_t *transform,
return TRUE;
}
+#if 0
+pixman_fixed_inverse(pixman_fixed_t a)
+{
+ /* are there any value that don't have an inverse?
+ * yes. lots */
+}
+#endif
+
+/**
+ * sqrt_fixed:
+ * @x: number to sqrt in fixed-point 16.16 format
+ *
+ * This code is inspired by Ken Turkowski's fixed-point sqrt.
+ * http://www.worldserver.com/turk/computergraphics/FixedSqrt.pdf
+ *
+ * Author : Frederic Plourde
+ **/
+pixman_fixed_t
+sqrt_fixed (pixman_fixed_t x)
+{
+ const pixman_fixed_t pixman_fixed_095 = 0x0000F333;
+ const pixman_fixed_t pixman_fixed_sqrt_2 = 0x00016A0A;
+ int32_t y = x;
+ int32_t a = 0;
+
+ if (y <= 0)
+ {
+ return 0;
+ }
+ else if (y > pixman_fixed_1)
+ {
+ while (y & 0xFFFF0000)
+ {
+ y >>= 1;
+ a++;
+ }
+ }
+ else
+ {
+ while (!(y & 0xFFFF0000))
+ {
+ y <<= 1;
+ a--;
+ }
+ y >>= 1;
+ a++;
+ }
+
+ y = (pixman_fixed_095 + y) >> 1;
+
+ if (a & 0x00000001) // a is odd
+ {
+ a = a >> 1;
+
+ if (a > 0)
+ {
+ y = mul_fixed(mul_fixed(y, pixman_fixed_1 << a), pixman_fixed_sqrt_2);
+ }
+ else
+ {
+ y = mul_fixed(mul_fixed(y, pixman_fixed_1 >> -a), pixman_fixed_sqrt_2);
+ }
+ }
+ else // a is even
+ {
+ a = a >> 1;
+
+ if (a > 0)
+ {
+ y = mul_fixed(y, pixman_fixed_1 << a);
+ }
+ else
+ {
+ y = mul_fixed(y, pixman_fixed_1 >> -a);
+ }
+ }
+
+ // Iterate two times to improve accuracy.
+ // One of the below two lines may be removed to
+ // increase speed but at the cost of reduced accuracy.
+ y = (y + div_fixed(x, y)) >> 1;
+ y = (y + div_fixed(x, y)) >> 1;
+
+ return y;
+}
+
+void
+pixman_transform_unscale (pixman_transform_t *transform,
+ pixman_fixed_t xscale, pixman_fixed_t yscale)
+{
+ /*
+ we want to multiply the transform by the inverse of the following scaled
+ transform:
+
+ | xscale 0 0 |^-1 | 1/xscale 0 0 |
+ | 0 yscale 0 | == | 0 1/yscale 0 |
+ | 0 0 1 | | 0 0 1 |
+
+ multiplying with the transform matrix gives:
+
+ | 1/xscale 0 0 | | a b c | | a/xscale b/xscale c/xscale |
+ | 0 1/yscale 0 | * | d e f | = | d/yscale e/yscale f/yscale |
+ | 0 0 1 | | g h i | | g h i |
+
+ we perform this transformation directly to take advantage of the
+ increased accuracy */
+ transform->matrix[0][0] = div_fixed(transform->matrix[0][0], xscale);
+ transform->matrix[0][1] = div_fixed(transform->matrix[0][1], xscale);
+ transform->matrix[0][2] = div_fixed(transform->matrix[0][2], xscale);
+
+ transform->matrix[1][0] = div_fixed(transform->matrix[1][0], yscale);
+ transform->matrix[1][1] = div_fixed(transform->matrix[1][1], yscale);
+ transform->matrix[1][2] = div_fixed(transform->matrix[1][2], yscale);
+}
+
+void
+pixman_extract_scale (pixman_transform_t *transform,
+ int *scale_x, int *scale_y)
+{
+ pixman_fixed_t (*matrix)[3] = transform->matrix;
+ pixman_bool_t affine = matrix[2][0] == 0 && matrix[2][1] == 0 && matrix[2][2] == pixman_fixed_1;
+ if (affine) {
+#ifdef FIXED
+ *scale_x = sqrt_fixed(square_fixed(width) *(square_fixed(matrix[0][0]) + square_fixed(matrix[1][0])));
+ *scale_y = sqrt_fixed(square_fixed(height)*(square_fixed(matrix[0][1]) + square_fixed(matrix[1][1])));
+#else
+ double a = pixman_fixed_to_double(matrix[0][0]);
+ double b = pixman_fixed_to_double(matrix[0][1]);
+ double c = pixman_fixed_to_double(matrix[1][0]);
+ double d = pixman_fixed_to_double(matrix[1][1]);
+
+ *scale_x = pixman_double_to_fixed(sqrt(a*a + c*c));
+ *scale_y = pixman_double_to_fixed(sqrt(b*b + d*d));
+
+#endif
+ } else {
+#if 0
+ /*
+ / 2 2 2 \1/2
+ | width ((d w - y0 f) (c w - y0 e)) |
+ |-------------------------------------------------------|
+ | 2 |
+ \ (a d w - a y0 f - c b w + c x0 f + e b y0 - e x0 d) /
+
+ / 2 2 2 \1/2
+ | height ((b w - x0 f) (a w - x0 e)) |
+ |-------------------------------------------------------|
+ | 2 |
+ \ (a d w - a y0 f - c b w + c x0 f + e b y0 - e x0 d) /
+
+
+ */
+ /* this isn't too nice and hasn't been tested at all. floating point is used to help readability */
+ double a = matrix[0][0];
+ double b = matrix[0][1];
+ double x0 = matrix[0][2];
+ double c = matrix[1][0];
+ double d = matrix[1][1];
+ double y0 = matrix[1][2];
+ double e = matrix[2][0];
+ double f = matrix[2][1];
+ double w = matrix[2][2];
+
+ double det = (a*d*w - a*y0*f - c*b*w + c*x0*f + e*b*y0 - e*x0*d);
+ double topx = (pow(d*w - y0*f, 2.)+pow(c*w - y0*e, 2.))*width*width;
+ double topy = (pow(b*w - x0*f, 2.)+pow(a*w - x0*e, 2.))*height*height;
+ double distx = sqrt(topx/(det*det));
+ double disty = sqrt(topy/(det*det));
+ *scaled_width = pixman_double_to_fixed(distx);
+ *scaled_height = pixman_double_to_fixed(disty);
+#endif
+ }
+}
+
+
+//XXX: could be called pixman_get_scaled_size()...
+void
+pixman_get_scaled_size (pixman_transform_t *transform,
+ int height, int width,
+ int *scaled_height, int *scaled_width)
+{
+ pixman_fixed_t (*matrix)[3] = transform->matrix;
+/*
+ / 2 2 2 \1/2
+ |width (d + c )|
+ distx := |----------------|
+ | 2 |
+ \ (a d - c b) /
+
+ / 2 2 2 \1/2
+ |height (b + a )|
+ disty := |-----------------|
+ | 2 |
+ \ (a d - c b) /
+ / \1/2
+ |width² (d² + c²)|
+ distx := |----------------|
+ \ (a d - c b)² /
+
+ ⎛ height² (b² + a²) ⎞ ½
+ disty := ⎜ -------------------⎟
+ ⎝ (a d - c b)² ⎠
+*/
+ pixman_bool_t affine = matrix[2][0] == 0 && matrix[2][1] == 0 && matrix[2][2] == pixman_fixed_1;
+ if (affine) {
+#if fixed
+ pixman_fixed_t det = mul_fixed(matrix[0][0],matrix[1][1]) - mul_fixed(matrix[0][1],matrix[1][0]);
+
+ pixman_fixed_t topx = square_fixed(width) *(square_fixed(matrix[1][1]) + square_fixed(matrix[1][0]));
+ pixman_fixed_t topy = square_fixed(height)*(square_fixed(matrix[0][0]) + square_fixed(matrix[0][1]));
+
+ *scaled_width = sqrt_fixed(div_fixed(topx, square_fixed(det)));
+ *scaled_height = sqrt_fixed(div_fixed(topy, square_fixed(det)));
+#else
+ double a = pixman_fixed_to_double(matrix[0][0]);
+ double b = pixman_fixed_to_double(matrix[0][1]);
+ double c = pixman_fixed_to_double(matrix[1][0]);
+ double d = pixman_fixed_to_double(matrix[1][1]);
+
+ double det = (a*d - c*b);
+ double topx = (d*d + c*c)*width*width;
+ double topy = (b*b + a*a)*height*height;
+ double distx = sqrt(topx/(det*det));
+ double disty = sqrt(topy/(det*det));
+ *scaled_width = distx;
+ *scaled_height = disty;
+#endif
+
+ } else {
+ /*
+ / 2 2 2 \1/2
+ | width ((d w - y0 f) (c w - y0 e)) |
+ |-------------------------------------------------------|
+ | 2 |
+ \ (a d w - a y0 f - c b w + c x0 f + e b y0 - e x0 d) /
+
+ / 2 2 2 \1/2
+ | height ((b w - x0 f) (a w - x0 e)) |
+ |-------------------------------------------------------|
+ | 2 |
+ \ (a d w - a y0 f - c b w + c x0 f + e b y0 - e x0 d) /
+
+
+ */
+ /* this isn't too nice and hasn't been tested at all. floating point is used to help readability */
+ double a = matrix[0][0];
+ double b = matrix[0][1];
+ double x0 = matrix[0][2];
+ double c = matrix[1][0];
+ double d = matrix[1][1];
+ double y0 = matrix[1][2];
+ double e = matrix[2][0];
+ double f = matrix[2][1];
+ double w = matrix[2][2];
+
+ double det = (a*d*w - a*y0*f - c*b*w + c*x0*f + e*b*y0 - e*x0*d);
+ double topx = (pow(d*w - y0*f, 2.)+pow(c*w - y0*e, 2.))*width*width;
+ double topy = (pow(b*w - x0*f, 2.)+pow(a*w - x0*e, 2.))*height*height;
+ double distx = sqrt(topx/(det*det));
+ double disty = sqrt(topy/(det*det));
+ *scaled_width = pixman_double_to_fixed(distx);
+ *scaled_height = pixman_double_to_fixed(disty);
+ }
+}
+
PIXMAN_EXPORT pixman_bool_t
pixman_blt (uint32_t *src_bits,
uint32_t *dst_bits,
diff --git a/pixman/pixman.h b/pixman/pixman.h
index 36d91a9..23a4f34 100644
--- a/pixman/pixman.h
+++ b/pixman/pixman.h
@@ -615,6 +615,7 @@ pixman_bool_t pixman_image_set_filter (pixman_image_t
int n_filter_params);
void pixman_image_set_source_clipping (pixman_image_t *image,
pixman_bool_t source_clipping);
+pixman_bool_t pixman_image_has_source_clipping (pixman_image_t *image);
void pixman_image_set_alpha_map (pixman_image_t *image,
pixman_image_t *alpha_map,
int16_t x,
More information about the cairo
mailing list