1/*
2 * Copyright © 2012 Intel Corporation
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21 * SOFTWARE.
22 *
23 * Authors:
24 *    Chris Wilson <chris@chris-wilson.co.uk>
25 *
26 */
27
28#include "fb.h"
29#include "fbclip.h"
30
31static const BoxRec *
32find_clip_row_for_y(const BoxRec *begin, const BoxRec *end, int16_t y)
33{
34	const BoxRec *mid;
35
36	if (end == begin)
37		return end;
38
39	if (end - begin == 1) {
40		if (begin->y2 > y)
41			return begin;
42		else
43			return end;
44	}
45
46	mid = begin + (end - begin) / 2;
47	if (mid->y2 > y)
48		return find_clip_row_for_y(begin, mid, y);
49	else
50		return find_clip_row_for_y(mid, end, y);
51}
52
53const BoxRec *
54fbClipBoxes(const RegionRec *region, const BoxRec *box, const BoxRec **end)
55{
56	const BoxRec *c0, *c1;
57
58	DBG(("%s: box=(%d, %d),(%d, %d); region=(%d, %d),(%d, %d) x %ld\n",
59	     __FUNCTION__,
60	     box->x1, box->y1, box->x2, box->y2,
61	     region->extents.x1, region->extents.y1,
62	     region->extents.x2, region->extents.y2,
63	     region->data ? region->data->numRects : 1));
64
65	if (box->x1 >= region->extents.x2 || box->x2 <= region->extents.x1 ||
66	    box->y1 >= region->extents.y2 || box->y2 <= region->extents.y1) {
67		DBG(("%s: no intersection\n", __FUNCTION__));
68		return *end = box;
69	}
70
71	if (region->data == NULL) {
72		*end = &region->extents + 1;
73		return &region->extents;
74	}
75
76	c0 = (const BoxRec *)(region->data + 1);
77	c1 = c0 + region->data->numRects;
78
79	if (c0->y2 <= box->y1) {
80		DBG(("%s: first clip (%d, %d), (%d, %d) before box (%d, %d), (%d, %d)\n",
81		     __FUNCTION__,
82		     c0->x1, c0->y1, c0->x2, c0->y2,
83		     box->x1, box->y1, box->x2, box->y2));
84		c0 = find_clip_row_for_y(c0, c1, box->y1);
85	}
86
87	DBG(("%s: c0=(%d, %d),(%d, %d) x %ld\n",
88	     __FUNCTION__, c0->x1, c0->y1, c0->x2, c0->y2, (long)(c1 - c0)));
89
90	*end = c1;
91	return c0;
92}
93