From 4600c6823e4dea52a34fe881f5374691bc76f555 Mon Sep 17 00:00:00 2001 From: Soren Sandmann Pedersen Date: Tue, 22 May 2007 12:52:52 -0400 Subject: [PATCH] Add implementation of edge rasterization --- pixman/Makefile.am | 4 +- pixman/pixman-edge-imp.h | 152 +++++++++++++++++++++++ pixman/pixman-edge.c | 306 +++++++++++++++++++++++++++++++++++++++++++++++ pixman/pixman-private.h | 41 ++++++- pixman/pixman.h | 96 ++++++++------- 5 files changed, 547 insertions(+), 52 deletions(-) create mode 100644 pixman/pixman-edge-imp.h create mode 100644 pixman/pixman-edge.c diff --git a/pixman/Makefile.am b/pixman/Makefile.am index 19f5cf8..f620def 100644 --- a/pixman/Makefile.am +++ b/pixman/Makefile.am @@ -9,7 +9,9 @@ libpixman_la_SOURCES = \ pixman-image.c \ pixman-compose.c \ pixman-pict.c \ - pixman-utils.c + pixman-utils.c \ + pixman-edge.c \ + pixman-edge-imp.h if USE_MMX diff --git a/pixman/pixman-edge-imp.h b/pixman/pixman-edge-imp.h new file mode 100644 index 0000000..6754305 --- /dev/null +++ b/pixman/pixman-edge-imp.h @@ -0,0 +1,152 @@ +/* + * $Id$ + * + * Copyright © 2004 Keith Packard + * + * 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 Keith Packard not be used in + * advertising or publicity pertaining to distribution of the software without + * specific, written prior permission. Keith Packard makes no + * representations about the suitability of this software for any purpose. It + * is provided "as is" without express or implied warranty. + * + * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO + * EVENT SHALL KEITH PACKARD 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. + */ + +#ifndef rasterizeSpan +#endif + +#define GET_IMAGE(image) \ + uint32_t *buf = (image)->bits.bits; \ + uint32_t stride = (image)->bits.rowstride; \ + uint32_t width = (image)->bits.width; + +static void +rasterizeEdges (pixman_image_t *image, + pixman_edge_t *l, + pixman_edge_t *r, + pixman_fixed_t t, + pixman_fixed_t b) +{ + pixman_fixed_t y = t; + uint32_t *line; + GET_IMAGE(image); + + line = buf + pixman_fixed_to_int (y) * (stride / sizeof (uint32_t)); + + for (;;) + { + pixman_fixed_t lx; + pixman_fixed_t rx; + int lxi; + int rxi; + + /* clip X */ + lx = l->x; + if (lx < 0) + lx = 0; + rx = r->x; + if (pixman_fixed_to_int (rx) >= width) + rx = pixman_int_to_fixed (width); + + /* Skip empty (or backwards) sections */ + if (rx > lx) + { + + /* Find pixel bounds for span */ + lxi = pixman_fixed_to_int (lx); + rxi = pixman_fixed_to_int (rx); + +#if N_BITS == 1 + { + uint32_t *a = line; + uint32_t startmask; + uint32_t endmask; + int nmiddle; + int width = rxi - lxi; + int x = lxi; + + a += x >> FB_SHIFT; + x &= FB_MASK; + + ACCESS_MEM( + FbMaskBits (x, width, startmask, nmiddle, endmask); + if (startmask) { + WRITE(a, READ(a) | startmask); + a++; + } + while (nmiddle--) + WRITE(a++, FB_ALLONES); + if (endmask) + WRITE(a, READ(a) | endmask); + ); + } +#else + { + DefineAlpha(line,lxi); + int lxs; + int rxs; + + /* Sample coverage for edge pixels */ + lxs = RenderSamplesX (lx, N_BITS); + rxs = RenderSamplesX (rx, N_BITS); + + /* Add coverage across row */ + ACCESS_MEM( + if (lxi == rxi) + { + AddAlpha (rxs - lxs); + } + else + { + int xi; + + AddAlpha (N_X_FRAC(N_BITS) - lxs); + StepAlpha; + for (xi = lxi + 1; xi < rxi; xi++) + { + AddAlpha (N_X_FRAC(N_BITS)); + StepAlpha; + } + /* Do not add in a 0 alpha here. This check is necessary + * to avoid a buffer overrun when rx is exactly on a pixel + * boundary. + */ + if (rxs != 0) + AddAlpha (rxs); + }); + } +#endif + } + + if (y == b) + break; + +#if N_BITS > 1 + if (pixman_fixed_frac (y) != Y_FRAC_LAST(N_BITS)) + { + RenderEdgeStepSmall (l); + RenderEdgeStepSmall (r); + y += STEP_Y_SMALL(N_BITS); + } + else +#endif + { + RenderEdgeStepBig (l); + RenderEdgeStepBig (r); + y += STEP_Y_BIG(N_BITS); + line += stride; + } + } +} + +#undef rasterizeSpan diff --git a/pixman/pixman-edge.c b/pixman/pixman-edge.c new file mode 100644 index 0000000..56a6538 --- /dev/null +++ b/pixman/pixman-edge.c @@ -0,0 +1,306 @@ +/* + * $Id$ + * + * Copyright © 2004 Keith Packard + * + * 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 Keith Packard not be used in + * advertising or publicity pertaining to distribution of the software without + * specific, written prior permission. Keith Packard makes no + * representations about the suitability of this software for any purpose. It + * is provided "as is" without express or implied warranty. + * + * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO + * EVENT SHALL KEITH PACKARD 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. + */ +#include +#include +#include "pixman.h" +#include "pixman-private.h" + +/* + * 4 bit alpha + */ + +#define N_BITS 4 +#define rasterizeEdges fbRasterizeEdges4 + +#if BITMAP_BIT_ORDER == LSBFirst +#define Shift4(o) ((o) << 2) +#else +#define Shift4(o) ((1-(o)) << 2) +#endif + +#define Get4(x,o) (((x) >> Shift4(o)) & 0xf) +#define Put4(x,o,v) (((x) & ~(0xf << Shift4(o))) | (((v) & 0xf) << Shift4(o))) + +#define DefineAlpha(line,x) \ + uint8_t *__ap = (uint8_t *) line + ((x) >> 1); \ + int __ao = (x) & 1 + +#define StepAlpha ((__ap += __ao), (__ao ^= 1)) + +#define AddAlpha(a) { \ + uint8_t __o = READ(__ap); \ + uint8_t __a = (a) + Get4(__o, __ao); \ + WRITE(__ap, Put4 (__o, __ao, __a | (0 - ((__a) >> 4)))); \ +} + +#include "pixman-edge-imp.h" + +#undef AddAlpha +#undef StepAlpha +#undef DefineAlpha +#undef rasterizeEdges +#undef N_BITS + + +/* + * 1 bit alpha + */ + +#define N_BITS 1 +#define rasterizeEdges fbRasterizeEdges1 + +#include "pixman-edge-imp.h" + +#undef rasterizeEdges +#undef N_BITS + +/* + * 8 bit alpha + */ + +static inline uint8_t +clip255 (int x) +{ + if (x > 255) return 255; + return x; +} + +#define add_saturate_8(buf,val,length) \ + do { \ + int i__ = (length); \ + uint8_t *buf__ = (buf); \ + int val__ = (val); \ + \ + while (i__--) \ + { \ + WRITE((buf__), clip255 (READ((buf__)) + (val__))); \ + (buf__)++; \ + } \ + } while (0) + +/* + * We want to detect the case where we add the same value to a long + * span of pixels. The triangles on the end are filled in while we + * count how many sub-pixel scanlines contribute to the middle section. + * + * +--------------------------+ + * fill_height =| \ / + * +------------------+ + * |================| + * fill_start fill_end + */ +static void +fbRasterizeEdges8 (pixman_image_t *image, + pixman_edge_t *l, + pixman_edge_t *r, + pixman_fixed_t t, + pixman_fixed_t b) +{ + pixman_fixed_t y = t; + uint32_t *line; + int fill_start = -1, fill_end = -1; + int fill_size = 0; + uint32_t *buf = (image)->bits.bits; + uint32_t stride = (image)->bits.rowstride; + uint32_t width = (image)->bits.width; + + line = buf + pixman_fixed_to_int (y) * stride; + + for (;;) + { + uint8_t *ap = (uint8_t *) line; + pixman_fixed_t lx, rx; + int lxi, rxi; + + /* clip X */ + lx = l->x; + if (lx < 0) + lx = 0; + rx = r->x; + if (pixman_fixed_to_int (rx) >= width) + rx = pixman_int_to_fixed (width); + + /* Skip empty (or backwards) sections */ + if (rx > lx) + { + int lxs, rxs; + + /* Find pixel bounds for span. */ + lxi = pixman_fixed_to_int (lx); + rxi = pixman_fixed_to_int (rx); + + /* Sample coverage for edge pixels */ + lxs = RenderSamplesX (lx, 8); + rxs = RenderSamplesX (rx, 8); + + /* Add coverage across row */ + ACCESS_MEM ( + if (lxi == rxi) + { + WRITE(ap +lxi, clip255 (READ(ap + lxi) + rxs - lxs)); + } + else + { + WRITE(ap + lxi, clip255 (READ(ap + lxi) + N_X_FRAC(8) - lxs)); + + /* Move forward so that lxi/rxi is the pixel span */ + lxi++; + + /* Don't bother trying to optimize the fill unless + * the span is longer than 4 pixels. */ + if (rxi - lxi > 4) + { + if (fill_start < 0) + { + fill_start = lxi; + fill_end = rxi; + fill_size++; + } + else + { + if (lxi >= fill_end || rxi < fill_start) + { + /* We're beyond what we saved, just fill it */ + add_saturate_8 (ap + fill_start, + fill_size * N_X_FRAC(8), + fill_end - fill_start); + fill_start = lxi; + fill_end = rxi; + fill_size = 1; + } + else + { + /* Update fill_start */ + if (lxi > fill_start) + { + add_saturate_8 (ap + fill_start, + fill_size * N_X_FRAC(8), + lxi - fill_start); + fill_start = lxi; + } + else if (lxi < fill_start) + { + add_saturate_8 (ap + lxi, N_X_FRAC(8), + fill_start - lxi); + } + + /* Update fill_end */ + if (rxi < fill_end) + { + add_saturate_8 (ap + rxi, + fill_size * N_X_FRAC(8), + fill_end - rxi); + fill_end = rxi; + } + else if (fill_end < rxi) + { + add_saturate_8 (ap + fill_end, + N_X_FRAC(8), + rxi - fill_end); + } + fill_size++; + } + } + } + else + { + add_saturate_8 (ap + lxi, N_X_FRAC(8), rxi - lxi); + } + + /* Do not add in a 0 alpha here. This check is + * necessary to avoid a buffer overrun, (when rx + * is exactly on a pixel boundary). */ + if (rxs) + WRITE(ap + rxi, clip255 (READ(ap + rxi) + rxs)); + }); + } + + if (y == b) { + /* We're done, make sure we clean up any remaining fill. */ + if (fill_start != fill_end) { + ACCESS_MEM( + if (fill_size == N_Y_FRAC(8)) + { + MEMSET_WRAPPED (ap + fill_start, 0xff, fill_end - fill_start); + } + else + { + add_saturate_8 (ap + fill_start, fill_size * N_X_FRAC(8), + fill_end - fill_start); + }); + } + break; + } + + if (pixman_fixed_frac (y) != Y_FRAC_LAST(8)) + { + RenderEdgeStepSmall (l); + RenderEdgeStepSmall (r); + y += STEP_Y_SMALL(8); + } + else + { + RenderEdgeStepBig (l); + RenderEdgeStepBig (r); + y += STEP_Y_BIG(8); + if (fill_start != fill_end) + { + ACCESS_MEM( + if (fill_size == N_Y_FRAC(8)) + { + MEMSET_WRAPPED (ap + fill_start, 0xff, fill_end - fill_start); + } + else + { + add_saturate_8 (ap + fill_start, fill_size * N_X_FRAC(8), + fill_end - fill_start); + }); + fill_start = fill_end = -1; + fill_size = 0; + } + line += stride; + } + } +} + +void +pixman_rasterize_edges (pixman_image_t *image, + pixman_edge_t *l, + pixman_edge_t *r, + pixman_fixed_t t, + pixman_fixed_t b) +{ + switch (PIXMAN_FORMAT_BPP (image->bits.format)) + { + case 1: + fbRasterizeEdges1 (image, l, r, t, b); + break; + case 4: + fbRasterizeEdges4 (image, l, r, t, b); + break; + case 8: + fbRasterizeEdges8 (image, l, r, t, b); + break; + } +} diff --git a/pixman/pixman-private.h b/pixman/pixman-private.h index 0d5125e..d233ee4 100644 --- a/pixman/pixman-private.h +++ b/pixman/pixman-private.h @@ -15,6 +15,9 @@ #define TRUE 1 #endif +#define MSBFirst 0 +#define LSBFirst 1 + #ifdef WORDS_BIGENDIAN # define IMAGE_BYTE_ORDER MSBFirst # define BITMAP_BIT_ORDER MSBFirst @@ -33,6 +36,14 @@ # define FUNC ((const char*) ("???")) #endif + +#define FB_SHIFT 5 +#define FB_UNIT (1 << FB_SHIFT) +#define FB_HALFUNIT (1 << (FB_SHIFT-1)) +#define FB_MASK (FB_UNIT - 1) +#define FB_ALLONES ((uint32_t) -1) + + #if DEBUG #define return_if_fail(expr) \ @@ -250,6 +261,26 @@ void pixmanCompositeRect (const FbComposeData *data, #define FbStipMask(x,w) (FbStipRight(FB_STIP_ALLONES,(x) & FB_STIP_MASK) & \ FbStipLeft(FB_STIP_ALLONES,(FB_STIP_UNIT - ((x)+(w))) & FB_STIP_MASK)) +#define FbLeftMask(x) ( ((x) & FB_MASK) ? \ + FbScrRight(FB_ALLONES,(x) & FB_MASK) : 0) +#define FbRightMask(x) ( ((FB_UNIT - (x)) & FB_MASK) ? \ + FbScrLeft(FB_ALLONES,(FB_UNIT - (x)) & FB_MASK) : 0) + +#define FbMaskBits(x,w,l,n,r) { \ + n = (w); \ + r = FbRightMask((x)+n); \ + l = FbLeftMask(x); \ + if (l) { \ + n -= FB_UNIT - ((x) & FB_MASK); \ + if (n < 0) { \ + n = 0; \ + l &= r; \ + r = 0; \ + } \ + } \ + n >>= FB_SHIFT; \ + } + #if IMAGE_BYTE_ORDER == MSBFirst #define Fetch24(a) ((unsigned long) (a) & 1 ? \ ((READ(a) << 16) | READ((uint16_t *) ((a)+1))) : \ @@ -657,19 +688,19 @@ void pixmanCompositeRect (const FbComposeData *data, #define N_Y_FRAC(n) ((n) == 1 ? 1 : (1 << ((n)/2)) - 1) #define N_X_FRAC(n) ((1 << ((n)/2)) + 1) -#define STEP_Y_SMALL(n) (xFixed1 / N_Y_FRAC(n)) -#define STEP_Y_BIG(n) (xFixed1 - (N_Y_FRAC(n) - 1) * STEP_Y_SMALL(n)) +#define STEP_Y_SMALL(n) (pixman_fixed_1 / N_Y_FRAC(n)) +#define STEP_Y_BIG(n) (pixman_fixed_1 - (N_Y_FRAC(n) - 1) * STEP_Y_SMALL(n)) #define Y_FRAC_FIRST(n) (STEP_Y_SMALL(n) / 2) #define Y_FRAC_LAST(n) (Y_FRAC_FIRST(n) + (N_Y_FRAC(n) - 1) * STEP_Y_SMALL(n)) -#define STEP_X_SMALL(n) (xFixed1 / N_X_FRAC(n)) -#define STEP_X_BIG(n) (xFixed1 - (N_X_FRAC(n) - 1) * STEP_X_SMALL(n)) +#define STEP_X_SMALL(n) (pixman_fixed_1 / N_X_FRAC(n)) +#define STEP_X_BIG(n) (pixman_fixed_1 - (N_X_FRAC(n) - 1) * STEP_X_SMALL(n)) #define X_FRAC_FIRST(n) (STEP_X_SMALL(n) / 2) #define X_FRAC_LAST(n) (X_FRAC_FIRST(n) + (N_X_FRAC(n) - 1) * STEP_X_SMALL(n)) -#define RenderSamplesX(x,n) ((n) == 1 ? 0 : (xFixedFrac (x) + X_FRAC_FIRST(n)) / STEP_X_SMALL(n)) +#define RenderSamplesX(x,n) ((n) == 1 ? 0 : (pixman_fixed_frac (x) + X_FRAC_FIRST(n)) / STEP_X_SMALL(n)) /* * Step across a small sample grid gap diff --git a/pixman/pixman.h b/pixman/pixman.h index 3550f69..fbc9518 100644 --- a/pixman/pixman.h +++ b/pixman/pixman.h @@ -290,52 +290,6 @@ pixman_bool_t pixman_region_selfcheck (pixman_region16_t *region); void pixman_region_reset(pixman_region16_t *region, pixman_box16_t *box); /* - * Trapezoids - */ -typedef struct pixman_edge pixman_edge_t; - -/* - * An edge structure. This represents a single polygon edge - * and can be quickly stepped across small or large gaps in the - * sample grid - */ -struct pixman_render_edge -{ - pixman_fixed_t x; - pixman_fixed_t e; - pixman_fixed_t stepx; - pixman_fixed_t signdx; - pixman_fixed_t dy; - pixman_fixed_t dx; - - pixman_fixed_t stepx_small; - pixman_fixed_t stepx_big; - pixman_fixed_t dx_small; - pixman_fixed_t dx_big; -}; - -pixman_fixed_t pixman_sample_ceil_y (pixman_fixed_t y, - int bpp); -pixman_fixed_t pixman_sample_floor_y (pixman_fixed_t y, - int bpp); -void pixman_edge_step (pixman_edge_t *e, - int n); -void pixman_edge_init (pixman_edge_t *e, - int bpp, - pixman_fixed_t y_start, - pixman_fixed_t x_top, - pixman_fixed_t y_top, - pixman_fixed_t x_bot, - pixman_fixed_t y_bot); -void pixman_line_fixed_edge_init (pixman_edge_t *e, - int bpp, - pixman_fixed_t y, - pixman_line_fixed_t *line, - int x_off, - int y_off); - - -/* * Images */ typedef union pixman_image pixman_image_t; @@ -532,4 +486,54 @@ void pixman_image_composite_rect (pixman_op_t uint16_t width, uint16_t height); +/* + * Trapezoids + */ +typedef struct pixman_edge pixman_edge_t; + +/* + * An edge structure. This represents a single polygon edge + * and can be quickly stepped across small or large gaps in the + * sample grid + */ +struct pixman_edge +{ + pixman_fixed_t x; + pixman_fixed_t e; + pixman_fixed_t stepx; + pixman_fixed_t signdx; + pixman_fixed_t dy; + pixman_fixed_t dx; + + pixman_fixed_t stepx_small; + pixman_fixed_t stepx_big; + pixman_fixed_t dx_small; + pixman_fixed_t dx_big; +}; + +pixman_fixed_t pixman_sample_ceil_y (pixman_fixed_t y, + int bpp); +pixman_fixed_t pixman_sample_floor_y (pixman_fixed_t y, + int bpp); +void pixman_edge_step (pixman_edge_t *e, + int n); +void pixman_edge_init (pixman_edge_t *e, + int bpp, + pixman_fixed_t y_start, + pixman_fixed_t x_top, + pixman_fixed_t y_top, + pixman_fixed_t x_bot, + pixman_fixed_t y_bot); +void pixman_line_fixed_edge_init (pixman_edge_t *e, + int bpp, + pixman_fixed_t y, + pixman_line_fixed_t *line, + int x_off, + int y_off); +void pixman_rasterize_edges (pixman_image_t *image, + pixman_edge_t *l, + pixman_edge_t *r, + pixman_fixed_t t, + pixman_fixed_t b); + #endif /* PIXMAN_H__ */ -- 2.7.4