Huw Davies : gdi32: Use a binary search to generate the clipped rects.

[Alexandre Julliard]

Module: wine
Branch: master
Commit: 7fd44a511f1093c79361485ba80e803b272bbb26
URL:    http://source.winehq.org/git/wine.git/?a=commit;h=7fd44a511f1093c79361485ba8...

Author: Huw Davies <huw(a)codeweavers.com>
Date:   Wed Jul  6 11:09:12 2016 +0100

gdi32: Use a binary search to generate the clipped rects.

Signed-off-by: Huw Davies <huw(a)codeweavers.com>
Signed-off-by: Alexandre Julliard <julliard(a)winehq.org>

---

 dlls/gdi32/dibdrv/dc.c   |  2 +-
 dlls/gdi32/gdi_private.h | 33 +++++++++++++++++++++++++++++++++
 2 files changed, 34 insertions(+), 1 deletion(-)

diff --git a/dlls/gdi32/dibdrv/dc.c b/dlls/gdi32/dibdrv/dc.c
index 314c651..9bd263c 100644
--- a/dlls/gdi32/dibdrv/dc.c
+++ b/dlls/gdi32/dibdrv/dc.c
@@ -280,7 +280,7 @@ int get_clipped_rects( const dib_info *dib, const RECT *rc, HRGN clip, struct cl
 
     if (!(region = get_wine_region( clip ))) return 0;
 
-    for (i = 0; i < region->numRects; i++)
+    for (i = region_find_pt( region, rect.left, rect.top, NULL ); i < region->numRects; i++)
     {
         if (region->rects[i].top >= rect.bottom) break;
         if (!intersect_rect( out, &rect, ®ion->rects[i] )) continue;
diff --git a/dlls/gdi32/gdi_private.h b/dlls/gdi32/gdi_private.h
index 15e50e1..9c58747 100644
--- a/dlls/gdi32/gdi_private.h
+++ b/dlls/gdi32/gdi_private.h
@@ -370,6 +370,39 @@ static inline void release_wine_region(HRGN rgn)
     GDI_ReleaseObj(rgn);
 }
 
+/**********************************************************
+ *     region_find_pt
+ *
+ * Return either the index of the rectangle that contains (x,y) or the first
+ * rectangle after it.  Sets *hit to TRUE if the region contains (x,y).
+ * Note if (x,y) follows all rectangles, then the return value will be rgn->numRects.
+ */
+static inline int region_find_pt( const WINEREGION *rgn, int x, int y, BOOL *hit )
+{
+    int i, start = 0, end = rgn->numRects - 1;
+    BOOL h = FALSE;
+
+    while (start <= end)
+    {
+        i = (start + end) / 2;
+
+        if (rgn->rects[i].bottom <= y ||
+            (rgn->rects[i].top <= y && rgn->rects[i].right <= x))
+            start = i + 1;
+        else if (rgn->rects[i].top > y ||
+                 (rgn->rects[i].bottom > y && rgn->rects[i].left > x))
+            end = i - 1;
+        else
+        {
+            h = TRUE;
+            break;
+        }
+    }
+
+    if (hit) *hit = h;
+    return h ? i : start;
+}
+
 /* null driver entry points */
 extern BOOL nulldrv_AbortPath( PHYSDEV dev ) DECLSPEC_HIDDEN;
 extern BOOL nulldrv_AlphaBlend( PHYSDEV dst_dev, struct bitblt_coords *dst,