pixman: Branch 'master' - 5 commits
Søren Sandmann Pedersen
sandmann at kemper.freedesktop.org
Thu Aug 11 00:37:28 PDT 2011
pixman/pixman-region.c | 60 ++++++++++++---
test/Makefile.am | 2
test/lowlevel-blt-bench.c | 1
test/region-contains-test.c | 169 ++++++++++++++++++++++++++++++++++++++++++++
test/utils.c | 11 ++
test/utils.h | 16 +++-
6 files changed, 240 insertions(+), 19 deletions(-)
New commits:
commit bdfb5944ffd460631c082e560c89a6c9830b37de
Author: Søren Sandmann Pedersen <ssp at redhat.com>
Date: Mon Aug 8 10:18:07 2011 -0400
Don't include stdint.h in lowlevel-blt-bench.c
Some systems don't have the file, and the types are already defined in
pixman.h.
https://bugs.freedesktop.org//show_bug.cgi?id=37422
diff --git a/test/lowlevel-blt-bench.c b/test/lowlevel-blt-bench.c
index d58587d..b00e487 100644
--- a/test/lowlevel-blt-bench.c
+++ b/test/lowlevel-blt-bench.c
@@ -22,7 +22,6 @@
* DEALINGS IN THE SOFTWARE.
*/
-#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
commit e5d85ce6629c84b9dad5a9c76bd9f895157c5a74
Author: Søren Sandmann Pedersen <ssp at redhat.com>
Date: Tue Aug 2 03:03:48 2011 -0400
Use find_box_for_y() in pixman_region_contains_point() too
The same binary search from the previous commit can be used in this
function too.
V2: Remove check from loop that is not needed anymore, pointed out by
Andrea Canciani.
diff --git a/pixman/pixman-region.c b/pixman/pixman-region.c
index 71995fd..9ff5157 100644
--- a/pixman/pixman-region.c
+++ b/pixman/pixman-region.c
@@ -2378,13 +2378,13 @@ PREFIX (_contains_point) (region_type_t * region,
return(TRUE);
}
- for (pbox = PIXREGION_BOXPTR (region), pbox_end = pbox + numRects;
- pbox != pbox_end;
- pbox++)
- {
- if (y >= pbox->y2)
- continue; /* not there yet */
+ pbox = PIXREGION_BOXPTR (region);
+ pbox_end = pbox + numRects;
+
+ pbox = find_box_for_y (pbox, pbox_end, y);
+ for (;pbox != pbox_end; pbox++)
+ {
if ((y < pbox->y1) || (x < pbox->x1))
break; /* missed it */
commit 04bd4bdca622f060d7d39caddeaa495d3e6eb0cb
Author: Søren Sandmann Pedersen <ssp at redhat.com>
Date: Mon Aug 1 22:32:09 2011 -0400
Speed up pixman_region{,32}_contains_rectangle()
When someone selects some text in Firefox under a non-composited X
server and initiates a drag, a shaped window is created with a complex
shape corresponding to the outline of the text. Then, on every mouse
movement pixman_region_contains_rectangle() is called many times on
that complicated region. And pixman_region_contains_rectangle() is
doing a linear scan through the rectangles in the region, although the
scan does exit when it finds the first box that can't possibly
intersect the passed-in rectangle.
This patch changes the loop so that it uses a binary search to skip
boxes that don't overlap the current y position. The performance
improvement for the text dragging case is easily noticable.
V2: Use the binary search for the "getting up to speed or skippping
remainder of band" as well.
diff --git a/pixman/pixman-region.c b/pixman/pixman-region.c
index 142493b..71995fd 100644
--- a/pixman/pixman-region.c
+++ b/pixman/pixman-region.c
@@ -2086,6 +2086,40 @@ PIXMAN_EXPORT PREFIX (_inverse) (region_type_t *new_reg, /* Destination region
return TRUE;
}
+/* In time O(log n), locate the first box whose y2 is greater than y.
+ * Return @end if no such box exists.
+ */
+static box_type_t *
+find_box_for_y (box_type_t *begin, box_type_t *end, int y)
+{
+ box_type_t *mid;
+
+ if (end == begin)
+ return end;
+
+ if (end - begin == 1)
+ {
+ if (begin->y2 > y)
+ return begin;
+ else
+ return end;
+ }
+
+ mid = begin + (end - begin) / 2;
+ if (mid->y2 > y)
+ {
+ /* If no box is found in [begin, mid], the function
+ * will return @mid, which is then known to be the
+ * correct answer.
+ */
+ return find_box_for_y (begin, mid, y);
+ }
+ else
+ {
+ return find_box_for_y (mid, end, y);
+ }
+}
+
/*
* rect_in(region, rect)
* This routine takes a pointer to a region and a pointer to a box
@@ -2102,7 +2136,6 @@ PIXMAN_EXPORT PREFIX (_inverse) (region_type_t *new_reg, /* Destination region
* partially in the region) or is outside the region (we reached a band
* that doesn't overlap the box at all and part_in is false)
*/
-
pixman_region_overlap_t
PIXMAN_EXPORT PREFIX (_contains_rectangle) (region_type_t * region,
box_type_t * prect)
@@ -2139,12 +2172,15 @@ PIXMAN_EXPORT PREFIX (_contains_rectangle) (region_type_t * region,
/* can stop when both part_out and part_in are TRUE, or we reach prect->y2 */
for (pbox = PIXREGION_BOXPTR (region), pbox_end = pbox + numRects;
- pbox != pbox_end;
- pbox++)
+ pbox != pbox_end;
+ pbox++)
{
-
- if (pbox->y2 <= y)
- continue; /* getting up to speed or skipping remainder of band */
+ /* getting up to speed or skipping remainder of band */
+ if (pbox->y2 <= y)
+ {
+ if ((pbox = find_box_for_y (pbox, pbox_end, y)) == pbox_end)
+ break;
+ }
if (pbox->y1 > y)
{
commit 795ec5af2fc86fb0ebeca9ce82913d6002267a12
Author: Søren Sandmann Pedersen <ssp at redhat.com>
Date: Tue Aug 2 01:32:15 2011 -0400
New test of pixman_region_contains_{rectangle,point}
This test generates random regions and checks whether random boxes and
points are contained within them. The results are combined and a CRC32
value is computed and compared to a known-correct one.
diff --git a/test/Makefile.am b/test/Makefile.am
index 9dc7219..9f61fc9 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -15,6 +15,7 @@ TESTPROGRAMS = \
scaling-crash-test \
scaling-helpers-test \
gradient-crash-test \
+ region-contains-test \
alphamap \
stress-test \
composite-traps-test \
@@ -26,6 +27,7 @@ TESTPROGRAMS = \
pdf_op_test_SOURCES = pdf-op-test.c utils.c utils.h
region_test_SOURCES = region-test.c utils.c utils.h
blitters_test_SOURCES = blitters-test.c utils.c utils.h
+region_contains_test_SOURCES = region-contains-test.c utils.c utils.h
composite_traps_test_SOURCES = composite-traps-test.c utils.c utils.h
scaling_test_SOURCES = scaling-test.c utils.c utils.h
affine_test_SOURCES = affine-test.c utils.c utils.h
diff --git a/test/region-contains-test.c b/test/region-contains-test.c
new file mode 100644
index 0000000..d761c4b
--- /dev/null
+++ b/test/region-contains-test.c
@@ -0,0 +1,169 @@
+#include <assert.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include "utils.h"
+
+static void
+make_random_region (pixman_region32_t *region)
+{
+ int n_boxes;
+
+ pixman_region32_init (region);
+
+ n_boxes = lcg_rand_n (64);
+ while (n_boxes--)
+ {
+ int32_t x1, y1, x2, y2;
+
+ x1 = (int32_t)lcg_rand_u32();
+ y1 = (int32_t)lcg_rand_u32();
+ x2 = (int32_t)lcg_rand_u32();
+ y2 = (int32_t)lcg_rand_u32();
+
+ pixman_region32_union_rect (region, region, x1, y1, x2, y2);
+ }
+}
+
+static void
+print_box (pixman_box32_t *box)
+{
+ printf (" %d %d %d %d\n", box->x1, box->y1, box->x2, box->y2);
+}
+
+static int32_t
+random_coord (pixman_region32_t *region, pixman_bool_t x)
+{
+ pixman_box32_t *b, *bb;
+ int n_boxes;
+ int begin, end;
+
+ if (lcg_rand_n (14))
+ {
+ bb = pixman_region32_rectangles (region, &n_boxes);
+ if (n_boxes == 0)
+ goto use_extent;
+ b = bb + lcg_rand_n (n_boxes);
+ }
+ else
+ {
+ use_extent:
+ b = pixman_region32_extents (region);
+ n_boxes = 1;
+ }
+
+ if (x)
+ {
+ begin = b->x1;
+ end = b->x2;
+ }
+ else
+ {
+ begin = b->y1;
+ end = b->y2;
+ }
+
+ switch (lcg_rand_n (5))
+ {
+ case 0:
+ return begin - lcg_rand_u32();
+ case 1:
+ return end + lcg_rand_u32 ();
+ case 2:
+ return end;
+ case 3:
+ return begin;
+ default:
+ return (begin + end) / 2;
+ }
+ return 0;
+}
+
+static uint32_t
+compute_crc32_u32 (uint32_t crc32, uint32_t v)
+{
+ if (!is_little_endian())
+ {
+ v = ((v & 0xff000000) >> 24) |
+ ((v & 0x00ff0000) >> 8) |
+ ((v & 0x0000ff00) << 8) |
+ ((v & 0x000000ff) << 24);
+ }
+
+ return compute_crc32 (crc32, &v, sizeof (int32_t));
+}
+
+static uint32_t
+crc32_box32 (uint32_t crc32, pixman_box32_t *box)
+{
+ crc32 = compute_crc32_u32 (crc32, box->x1);
+ crc32 = compute_crc32_u32 (crc32, box->y1);
+ crc32 = compute_crc32_u32 (crc32, box->x2);
+ crc32 = compute_crc32_u32 (crc32, box->y2);
+
+ return crc32;
+}
+
+static uint32_t
+test_region_contains_rectangle (int i, int verbose)
+{
+ pixman_box32_t box;
+ pixman_box32_t rbox = { 0, 0, 0, 0 };
+ pixman_region32_t region;
+ uint32_t r, r1, r2, r3, r4, crc32;
+
+ lcg_srand (i);
+
+ make_random_region (®ion);
+
+ box.x1 = random_coord (®ion, TRUE);
+ box.x2 = box.x1 + lcg_rand_u32 ();
+ box.y1 = random_coord (®ion, FALSE);
+ box.y2 = box.y1 + lcg_rand_u32 ();
+
+ if (verbose)
+ {
+ int n_rects;
+ pixman_box32_t *boxes;
+
+ boxes = pixman_region32_rectangles (®ion, &n_rects);
+
+ printf ("region:\n");
+ while (n_rects--)
+ print_box (boxes++);
+ printf ("box:\n");
+ print_box (&box);
+ }
+
+ crc32 = 0;
+
+ r1 = pixman_region32_contains_point (®ion, box.x1, box.y1, &rbox);
+ crc32 = crc32_box32 (crc32, &rbox);
+ r2 = pixman_region32_contains_point (®ion, box.x1, box.y2, &rbox);
+ crc32 = crc32_box32 (crc32, &rbox);
+ r3 = pixman_region32_contains_point (®ion, box.x2, box.y1, &rbox);
+ crc32 = crc32_box32 (crc32, &rbox);
+ r4 = pixman_region32_contains_point (®ion, box.x2, box.y2, &rbox);
+ crc32 = crc32_box32 (crc32, &rbox);
+
+ r = pixman_region32_contains_rectangle (®ion, &box);
+ r = (i << 8) | (r << 4) | (r1 << 3) | (r2 << 2) | (r3 << 1) | (r4 << 0);
+
+ crc32 = compute_crc32_u32 (crc32, r);
+
+ if (verbose)
+ printf ("results: %d %d %d %d %d\n", (r & 0xf0) >> 4, r1, r2, r3, r4);
+
+ pixman_region32_fini (®ion);
+
+ return crc32;
+}
+
+int
+main (int argc, const char *argv[])
+{
+ return fuzzer_test_main ("region_contains",
+ 1000000,
+ 0x86311506,
+ test_region_contains_rectangle,
+ argc, argv);
+}
diff --git a/test/utils.c b/test/utils.c
index 4025602..44188ea 100644
--- a/test/utils.c
+++ b/test/utils.c
@@ -130,6 +130,14 @@ compute_crc32 (uint32_t in_crc32,
return (crc32 ^ 0xFFFFFFFF);
}
+pixman_bool_t
+is_little_endian (void)
+{
+ volatile uint16_t endian_check_var = 0x1234;
+
+ return (*(volatile uint8_t *)&endian_check_var == 0x34);
+}
+
/* perform endian conversion of pixel data
*/
void
@@ -142,8 +150,7 @@ image_endian_swap (pixman_image_t *img)
int i, j;
/* swap bytes only on big endian systems */
- volatile uint16_t endian_check_var = 0x1234;
- if (*(volatile uint8_t *)&endian_check_var != 0x12)
+ if (is_little_endian())
return;
if (bpp == 8)
diff --git a/test/utils.h b/test/utils.h
index 000aaa6..f0c9c30 100644
--- a/test/utils.h
+++ b/test/utils.h
@@ -61,6 +61,10 @@ compute_crc32 (uint32_t in_crc32,
const void *buf,
size_t buf_len);
+/* Returns TRUE if running on a little endian system */
+pixman_bool_t
+is_little_endian (void);
+
/* perform endian conversion of pixel data
*/
void
commit 842591d9d12a24a9a06308ae03996153c5a99e64
Author: Søren Sandmann Pedersen <ssp at redhat.com>
Date: Wed Aug 3 18:38:20 2011 -0400
Fix lcg_rand_u32() to return 32 random bits.
The lcg_rand() function only returns 15 random bits, so lcg_rand_u32()
would always have 0 in bit 31 and bit 15. Fix that by calling
lcg_rand() three times, to generate 15, 15, and 2 random bits
respectively.
V2: Use the 10/11 most significant bits from the 3 lcg results and mix
them with the low ones from the adjacent one, as suggested by Andrea
Canciani.
diff --git a/test/utils.h b/test/utils.h
index 615ad78..000aaa6 100644
--- a/test/utils.h
+++ b/test/utils.h
@@ -44,10 +44,14 @@ lcg_rand_N (int max)
static inline uint32_t
lcg_rand_u32 (void)
{
- uint32_t lo = lcg_rand();
- uint32_t hi = lcg_rand();
-
- return (hi << 16) | lo;
+ /* This uses the 10/11 most significant bits from the 3 lcg results
+ * (and mixes them with the low from the adjacent one).
+ */
+ uint32_t lo = lcg_rand() >> -(32 - 15 - 11 * 2);
+ uint32_t mid = lcg_rand() << (32 - 15 - 11 * 1);
+ uint32_t hi = lcg_rand() << (32 - 15 - 11 * 0);
+
+ return (hi ^ mid ^ lo);
}
/* CRC 32 computation
More information about the xorg-commit
mailing list