[PATCH 1/2] gdi32: Use a binary search to generate the clipped rects.

[Huw Davies]

Signed-off-by: Huw Davies <huw at codeweavers.com>
---
 dlls/gdi32/dibdrv/dc.c   |  2 +-
 dlls/gdi32/gdi_private.h | 32 ++++++++++++++++++++++++++++++++
 2 files changed, 33 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, &region->rects[i] )) continue;
diff --git a/dlls/gdi32/gdi_private.h b/dlls/gdi32/gdi_private.h
index 15e50e1..729c18c 100644
--- a/dlls/gdi32/gdi_private.h
+++ b/dlls/gdi32/gdi_private.h
@@ -369,6 +369,38 @@ 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;
-- 
2.7.4