sna/trapezoids: Use incremental region clipping for spans

Within a span, we have the advantage of knowing that we only need to
intersect one box with the clip region, and that box has monotonically
increasing y. This avoid having to compute RegionIntersect for every
span element which was very slow (e.g. libreoffice).

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>

1 files changed, 122 insertions, 207 deletions

diff --git a/src/sna/sna_trapezoids_precise.c b/src/sna/sna_trapezoids_precise.c
index 53f61d12..e7ea4337 100644
--- a/src/sna/sna_trapezoids_precise.c
+++ b/src/sna/sna_trapezoids_precise.c
@@ -1635,31 +1635,28 @@ struct span_thread {
 #define SPAN_THREAD_MAX_BOXES (8192/sizeof(struct sna_opacity_box))
 struct span_thread_boxes {
 	const struct sna_composite_spans_op *op;
+	const BoxRec *clip_start, *clip_end;
 	int num_boxes;
 	struct sna_opacity_box boxes[SPAN_THREAD_MAX_BOXES];
 };
 
-static void span_thread_add_boxes(struct sna *sna, void *data,
-				  const BoxRec *box, int count, float alpha)
+static void span_thread_add_box(struct sna *sna, void *data,
+				const BoxRec *box, float alpha)
 {
 	struct span_thread_boxes *b = data;
 
 	__DBG(("%s: adding %d boxes with alpha=%f\n",
 	       __FUNCTION__, count, alpha));
 
-	assert(count > 0 && count <= SPAN_THREAD_MAX_BOXES);
-	if (unlikely(b->num_boxes + count > SPAN_THREAD_MAX_BOXES)) {
-		DBG(("%s: flushing %d boxes, adding %d\n", __FUNCTION__, b->num_boxes, count));
-		assert(b->num_boxes <= SPAN_THREAD_MAX_BOXES);
+	if (unlikely(b->num_boxes == SPAN_THREAD_MAX_BOXES)) {
+		DBG(("%s: flushing %d boxes\n", __FUNCTION__, b->num_boxes));
 		b->op->thread_boxes(sna, b->op, b->boxes, b->num_boxes);
 		b->num_boxes = 0;
 	}
 
-	do {
-		b->boxes[b->num_boxes].box = *box++;
-		b->boxes[b->num_boxes].alpha = alpha;
-		b->num_boxes++;
-	} while (--count);
+	b->boxes[b->num_boxes].box = *box++;
+	b->boxes[b->num_boxes].alpha = alpha;
+	b->num_boxes++;
 	assert(b->num_boxes <= SPAN_THREAD_MAX_BOXES);
 }
 
@@ -1685,7 +1682,7 @@ span_thread_box(struct sna *sna,
 		}
 	}
 
-	span_thread_add_boxes(sna, op, box, 1, AREA_TO_FLOAT(coverage));
+	span_thread_add_box(sna, op, box, AREA_TO_FLOAT(coverage));
 }
 
 static void
@@ -1695,35 +1692,28 @@ span_thread_clipped_box(struct sna *sna,
 			const BoxRec *box,
 			int coverage)
 {
-	pixman_region16_t region;
+	struct span_thread_boxes *b = (struct span_thread_boxes *)op;
+	const BoxRec *c;
 
 	__DBG(("%s: %d -> %d @ %f\n", __FUNCTION__, box->x1, box->x2,
 	       AREA_TO_FLOAT(coverage)));
 
-	pixman_region_init_rects(&region, box, 1);
-	RegionIntersect(&region, &region, clip);
-	if (region_num_rects(&region)) {
-		struct span_thread_boxes *b = (struct span_thread_boxes *)op;
-
-		if (region.data == NULL && b->num_boxes) {
-			struct sna_opacity_box *bb = &b->boxes[b->num_boxes-1];
-			if (bb->box.x1 == region.extents.x1 &&
-			    bb->box.x2 == region.extents.x2 &&
-			    bb->box.y2 == region.extents.y1 &&
-			    bb->alpha == AREA_TO_FLOAT(coverage)) {
-				bb->box.y2 = region.extents.y2;
-				__DBG(("%s: contracted double row: %d -> %d\n", __func__, bb->box.y1, bb->box.y2));
-				goto out;
-			}
-		}
+	b->clip_start =
+		find_clip_box_for_y(b->clip_start, b->clip_end, box->y1);
 
-		span_thread_add_boxes(sna, op,
-				      region_rects(&region),
-				      region_num_rects(&region),
-				      AREA_TO_FLOAT(coverage));
+	c = b->clip_start;
+	while (c != b->clip_end) {
+		BoxRec clipped;
+
+		if (box->y2 <= c->y1)
+			break;
+
+		clipped = *box;
+		if (!box_intersect(&clipped, c++))
+			continue;
+
+		span_thread_add_box(sna, op, &clipped, AREA_TO_FLOAT(coverage));
 	}
-out:
-	pixman_region_fini(&region);
 }
 
 static span_func_t
@@ -1741,7 +1731,7 @@ thread_choose_span(struct sna_composite_spans_op *tmp,
 
 	assert(!is_mono(dst, maskFormat));
 	assert(tmp->thread_boxes);
-	DBG(("%s: clipped? %d\n", __FUNCTION__, clip->data != NULL));
+	DBG(("%s: clipped? %d x %d\n", __FUNCTION__, clip->data != NULL, region_num_rects(clip)));
 	if (clip->data)
 		span = span_thread_clipped_box;
 	else
@@ -1750,6 +1740,17 @@ thread_choose_span(struct sna_composite_spans_op *tmp,
 	return span;
 }
 
+inline static void
+span_thread_boxes_init(struct span_thread_boxes *boxes,
+		       const struct sna_composite_spans_op *op,
+		       const RegionRec *clip)
+{
+	boxes->op = op;
+	boxes->clip_start = region_rects(clip);
+	boxes->clip_end = boxes->clip_start + region_num_rects(clip);
+	boxes->num_boxes = 0;
+}
+
 static void
 span_thread(void *arg)
 {
@@ -1762,8 +1763,7 @@ span_thread(void *arg)
 	if (!tor_init(&tor, &thread->extents, 2*thread->ntrap))
 		return;
 
-	boxes.op = thread->op;
-	boxes.num_boxes = 0;
+	span_thread_boxes_init(&boxes, thread->op, thread->clip);
 
 	y1 = thread->extents.y1 - thread->draw_y;
 	y2 = thread->extents.y2 - thread->draw_y;
@@ -2212,6 +2212,52 @@ static force_inline uint8_t coverage_opacity(int coverage, uint8_t opacity)
 	return opacity == 255 ? coverage : mul_8_8(coverage, opacity);
 }
 
+struct clipped_span {
+	span_func_t span;
+	const BoxRec *clip_start, *clip_end;
+};
+
+static void
+tor_blt_clipped(struct sna *sna,
+		struct sna_composite_spans_op *op,
+		pixman_region16_t *clip,
+		const BoxRec *box,
+		int coverage)
+{
+	struct clipped_span *cs = (struct clipped_span *)clip;
+	const BoxRec *c;
+
+	cs->clip_start =
+		find_clip_box_for_y(cs->clip_start, cs->clip_end, box->y1);
+
+	c = cs->clip_start;
+	while (c != cs->clip_end) {
+		BoxRec clipped;
+
+		if (box->y2 <= c->y1)
+			break;
+
+		clipped = *box;
+		if (!box_intersect(&clipped, c++))
+			continue;
+
+		cs->span(sna, op, NULL, &clipped, coverage);
+	}
+}
+
+inline static span_func_t
+clipped_span(struct clipped_span *cs,
+	     span_func_t span,
+	     const RegionRec *clip)
+{
+	if (clip->data) {
+		cs->span = span;
+		region_get_boxes(clip, &cs->clip_start, &cs->clip_end);
+		span = tor_blt_clipped;
+	}
+	return span;
+}
+
 static void _tor_blt_src(struct inplace *in, const BoxRec *box, uint8_t v)
 {
 	uint8_t *ptr = in->ptr;
@@ -2247,25 +2293,6 @@ tor_blt_src(struct sna *sna,
 }
 
 static void
-tor_blt_src_clipped(struct sna *sna,
-		    struct sna_composite_spans_op *op,
-		    pixman_region16_t *clip,
-		    const BoxRec *box,
-		    int coverage)
-{
-	pixman_region16_t region;
-	int n;
-
-	pixman_region_init_rects(&region, box, 1);
-	RegionIntersect(&region, &region, clip);
-	n = region_num_rects(&region);
-	box = region_rects(&region);
-	while (n--)
-		tor_blt_src(sna, op, NULL, box++, coverage);
-	pixman_region_fini(&region);
-}
-
-static void
 tor_blt_in(struct sna *sna,
 	   struct sna_composite_spans_op *op,
 	   pixman_region16_t *clip,
@@ -2297,25 +2324,6 @@ tor_blt_in(struct sna *sna,
 }
 
 static void
-tor_blt_in_clipped(struct sna *sna,
-		   struct sna_composite_spans_op *op,
-		   pixman_region16_t *clip,
-		   const BoxRec *box,
-		   int coverage)
-{
-	pixman_region16_t region;
-	int n;
-
-	pixman_region_init_rects(&region, box, 1);
-	RegionIntersect(&region, &region, clip);
-	n = region_num_rects(&region);
-	box = region_rects(&region);
-	while (n--)
-		tor_blt_in(sna, op, NULL, box++, coverage);
-	pixman_region_fini(&region);
-}
-
-static void
 tor_blt_add(struct sna *sna,
 	    struct sna_composite_spans_op *op,
 	    pixman_region16_t *clip,
@@ -2354,25 +2362,6 @@ tor_blt_add(struct sna *sna,
 }
 
 static void
-tor_blt_add_clipped(struct sna *sna,
-		    struct sna_composite_spans_op *op,
-		    pixman_region16_t *clip,
-		    const BoxRec *box,
-		    int coverage)
-{
-	pixman_region16_t region;
-	int n;
-
-	pixman_region_init_rects(&region, box, 1);
-	RegionIntersect(&region, &region, clip);
-	n = region_num_rects(&region);
-	box = region_rects(&region);
-	while (n--)
-		tor_blt_add(sna, op, NULL, box++, coverage);
-	pixman_region_fini(&region);
-}
-
-static void
 tor_blt_lerp32(struct sna *sna,
 	       struct sna_composite_spans_op *op,
 	       pixman_region16_t *clip,
@@ -2425,25 +2414,6 @@ tor_blt_lerp32(struct sna *sna,
 	}
 }
 
-static void
-tor_blt_lerp32_clipped(struct sna *sna,
-		       struct sna_composite_spans_op *op,
-		       pixman_region16_t *clip,
-		       const BoxRec *box,
-		       int coverage)
-{
-	pixman_region16_t region;
-	int n;
-
-	pixman_region_init_rects(&region, box, 1);
-	RegionIntersect(&region, &region, clip);
-	n = region_num_rects(&region);
-	box = region_rects(&region);
-	while (n--)
-		tor_blt_lerp32(sna, op, NULL, box++, coverage);
-	pixman_region_fini(&region);
-}
-
 struct pixman_inplace {
 	pixman_image_t *image, *source, *mask;
 	uint32_t color;
@@ -2471,24 +2441,6 @@ pixmask_span_solid(struct sna *sna,
 			       pi->dx + box->x1, pi->dy + box->y1,
 			       box->x2 - box->x1, box->y2 - box->y1);
 }
-static void
-pixmask_span_solid__clipped(struct sna *sna,
-			    struct sna_composite_spans_op *op,
-			    pixman_region16_t *clip,
-			    const BoxRec *box,
-			    int coverage)
-{
-	pixman_region16_t region;
-	int n;
-
-	pixman_region_init_rects(&region, box, 1);
-	RegionIntersect(&region, &region, clip);
-	n = region_num_rects(&region);
-	box = region_rects(&region);
-	while (n--)
-		pixmask_span_solid(sna, op, NULL, box++, coverage);
-	pixman_region_fini(&region);
-}
 
 static void
 pixmask_span(struct sna *sna,
@@ -2509,24 +2461,6 @@ pixmask_span(struct sna *sna,
 			       pi->dx + box->x1, pi->dy + box->y1,
 			       box->x2 - box->x1, box->y2 - box->y1);
 }
-static void
-pixmask_span__clipped(struct sna *sna,
-		      struct sna_composite_spans_op *op,
-		      pixman_region16_t *clip,
-		      const BoxRec *box,
-		      int coverage)
-{
-	pixman_region16_t region;
-	int n;
-
-	pixman_region_init_rects(&region, box, 1);
-	RegionIntersect(&region, &region, clip);
-	n = region_num_rects(&region);
-	box = region_rects(&region);
-	while (n--)
-		pixmask_span(sna, op, NULL, box++, coverage);
-	pixman_region_fini(&region);
-}
 
 struct inplace_x8r8g8b8_thread {
 	xTrapezoid *traps;
@@ -2545,6 +2479,7 @@ static void inplace_x8r8g8b8_thread(void *arg)
 	struct inplace_x8r8g8b8_thread *thread = arg;
 	struct tor tor;
 	span_func_t span;
+	struct clipped_span clipped;
 	RegionPtr clip;
 	int y1, y2, n;
 
@@ -2575,12 +2510,11 @@ static void inplace_x8r8g8b8_thread(void *arg)
 		inplace.stride = pixmap->devKind;
 		inplace.color = thread->color;
 
-		if (clip->data)
-			span = tor_blt_lerp32_clipped;
-		else
-			span = tor_blt_lerp32;
+		span = clipped_span(&clipped, tor_blt_lerp32, clip);
 
-		tor_render(NULL, &tor, (void*)&inplace, clip, span, false);
+		tor_render(NULL, &tor,
+			   (void*)&inplace, (void *)&clipped,
+			   span, false);
 	} else if (thread->is_solid) {
 		struct pixman_inplace pi;
 
@@ -2593,10 +2527,7 @@ static void inplace_x8r8g8b8_thread(void *arg)
 						     1, 1, pi.bits, 0);
 		pixman_image_set_repeat(pi.source, PIXMAN_REPEAT_NORMAL);
 
-		if (clip->data)
-			span = pixmask_span_solid__clipped;
-		else
-			span = pixmask_span_solid;
+		span = clipped_span(&clipped, pixmask_span_solid, clip);
 
 		tor_render(NULL, &tor, (void*)&pi, clip, span, false);
 
@@ -2617,12 +2548,11 @@ static void inplace_x8r8g8b8_thread(void *arg)
 		pi.bits = pixman_image_get_data(pi.mask);
 		pi.op = thread->op;
 
-		if (clip->data)
-			span = pixmask_span__clipped;
-		else
-			span = pixmask_span;
+		span = clipped_span(&clipped, pixmask_span, clip);
 
-		tor_render(NULL, &tor, (void*)&pi, clip, span, false);
+		tor_render(NULL, &tor,
+			   (void*)&pi, (void *)&clipped,
+			   span, false);
 
 		pixman_image_unref(pi.mask);
 		pixman_image_unref(pi.source);
@@ -2741,6 +2671,7 @@ trapezoid_span_inplace__x8r8g8b8(CARD8 op,
 	if (num_threads == 1) {
 		struct tor tor;
 		span_func_t span;
+		struct clipped_span clipped;
 
 		if (!tor_init(&tor, &region.extents, 2*ntrap))
 			return true;
@@ -2766,17 +2697,14 @@ trapezoid_span_inplace__x8r8g8b8(CARD8 op,
 			inplace.stride = pixmap->devKind;
 			inplace.color = color;
 
-			if (dst->pCompositeClip->data)
-				span = tor_blt_lerp32_clipped;
-			else
-				span = tor_blt_lerp32;
-
+			span = clipped_span(&clipped, tor_blt_lerp32, dst->pCompositeClip);
 			DBG(("%s: render inplace op=%d, color=%08x\n",
 			     __FUNCTION__, op, color));
 
 			if (sigtrap_get() == 0) {
-				tor_render(NULL, &tor, (void*)&inplace,
-					   dst->pCompositeClip, span, false);
+				tor_render(NULL, &tor,
+					   (void*)&inplace, (void*)&clipped,
+					   span, false);
 				sigtrap_put();
 			}
 		} else if (is_solid) {
@@ -2791,15 +2719,11 @@ trapezoid_span_inplace__x8r8g8b8(CARD8 op,
 							     1, 1, pi.bits, 0);
 			pixman_image_set_repeat(pi.source, PIXMAN_REPEAT_NORMAL);
 
-			if (dst->pCompositeClip->data)
-				span = pixmask_span_solid__clipped;
-			else
-				span = pixmask_span_solid;
-
+			span = clipped_span(&clipped, pixmask_span_solid, dst->pCompositeClip);
 			if (sigtrap_get() == 0) {
-				tor_render(NULL, &tor, (void*)&pi,
-					   dst->pCompositeClip, span,
-					   false);
+				tor_render(NULL, &tor,
+					   (void*)&pi, (void*)&clipped,
+					    span, false);
 				sigtrap_put();
 			}
 
@@ -2820,15 +2744,11 @@ trapezoid_span_inplace__x8r8g8b8(CARD8 op,
 			pi.bits = pixman_image_get_data(pi.mask);
 			pi.op = op;
 
-			if (dst->pCompositeClip->data)
-				span = pixmask_span__clipped;
-			else
-				span = pixmask_span;
-
+			span = clipped_span(&clipped, pixmask_span, dst->pCompositeClip);
 			if (sigtrap_get() == 0) {
-				tor_render(NULL, &tor, (void*)&pi,
-					   dst->pCompositeClip, span,
-					   false);
+				tor_render(NULL, &tor,
+					   (void*)&pi, (void *)&clipped,
+					   span, false);
 				sigtrap_put();
 			}
 
@@ -2890,9 +2810,9 @@ trapezoid_span_inplace__x8r8g8b8(CARD8 op,
 
 struct inplace_thread {
 	xTrapezoid *traps;
-	RegionPtr clip;
 	span_func_t span;
 	struct inplace inplace;
+	struct clipped_span clipped;
 	BoxRec extents;
 	int dx, dy;
 	int draw_x, draw_y;
@@ -2917,8 +2837,9 @@ static void inplace_thread(void *arg)
 		tor_add_trapezoid(&tor, &thread->traps[n], thread->dx, thread->dy);
 	}
 
-	tor_render(NULL, &tor, (void*)&thread->inplace,
-		   thread->clip, thread->span, thread->unbounded);
+	tor_render(NULL, &tor, 
+		   (void*)&thread->inplace, (void*)&thread->clipped,
+		   thread->span, thread->unbounded);
 
 	tor_fini(&tor);
 }
@@ -2932,6 +2853,7 @@ precise_trapezoid_span_inplace(struct sna *sna,
 			       bool fallback)
 {
 	struct inplace inplace;
+	struct clipped_span clipped;
 	span_func_t span;
 	PixmapPtr pixmap;
 	struct sna_pixmap *priv;
@@ -3049,21 +2971,12 @@ precise_trapezoid_span_inplace(struct sna *sna,
 	     dst->pCompositeClip->data != NULL));
 
 	if (op == PictOpSrc) {
-		if (dst->pCompositeClip->data)
-			span = tor_blt_src_clipped;
-		else
-			span = tor_blt_src;
+		span = tor_blt_src;
 	} else if (op == PictOpIn) {
-		if (dst->pCompositeClip->data)
-			span = tor_blt_in_clipped;
-		else
-			span = tor_blt_in;
+		span = tor_blt_in;
 	} else {
 		assert(op == PictOpAdd);
-		if (dst->pCompositeClip->data)
-			span = tor_blt_add_clipped;
-		else
-			span = tor_blt_add;
+		span = tor_blt_add;
 	}
 
 	DBG(("%s: move-to-cpu(dst)\n", __FUNCTION__));
@@ -3081,6 +2994,8 @@ precise_trapezoid_span_inplace(struct sna *sna,
 	inplace.stride = pixmap->devKind;
 	inplace.opacity = color >> 24;
 
+	span = clipped_span(&clipped, span, dst->pCompositeClip);
+
 	num_threads = 1;
 	if (!NO_GPU_THREADS &&
 	    (flags & COMPOSITE_SPANS_RECTILINEAR) == 0)
@@ -3103,8 +3018,9 @@ precise_trapezoid_span_inplace(struct sna *sna,
 		}
 
 		if (sigtrap_get() == 0) {
-			tor_render(NULL, &tor, (void*)&inplace,
-				   dst->pCompositeClip, span, unbounded);
+			tor_render(NULL, &tor,
+				   (void*)&inplace, (void *)&clipped,
+				   span, unbounded);
 			sigtrap_put();
 		}
 
@@ -3122,7 +3038,7 @@ precise_trapezoid_span_inplace(struct sna *sna,
 		threads[0].ntrap = ntrap;
 		threads[0].inplace = inplace;
 		threads[0].extents = region.extents;
-		threads[0].clip = dst->pCompositeClip;
+		threads[0].clipped = clipped;
 		threads[0].span = span;
 		threads[0].unbounded = unbounded;
 		threads[0].dx = dx;
@@ -3345,8 +3261,7 @@ tristrip_thread(void *arg)
 	if (!tor_init(&tor, &thread->extents, 2*thread->count))
 		return;
 
-	boxes.op = thread->op;
-	boxes.num_boxes = 0;
+	span_thread_boxes_init(&boxes, thread->op, thread->clip);
 
 	cw = 0; ccw = 1;
 	polygon_add_line(tor.polygon,