blob: 6c2ad4fd7e836b7d610eff7e9cab2479344df9ce [file] [log] [blame]
Mathias Agopian20f68782009-05-11 00:03:41 -07001/*
2 * Copyright (C) 2009 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#ifndef ANDROID_UI_PRIVATE_REGION_HELPER_H
18#define ANDROID_UI_PRIVATE_REGION_HELPER_H
19
20#include <stdint.h>
21#include <sys/types.h>
22
Steven Moreland1da02892017-06-23 10:23:41 -070023#include <limits>
24
Mathias Agopian20f68782009-05-11 00:03:41 -070025namespace android {
26// ----------------------------------------------------------------------------
27
28template<typename RECT>
29class region_operator
30{
Mathias Agopian068d47f2012-09-11 18:56:23 -070031public:
Fabien Sanglardf8e93662017-02-16 19:29:35 -080032 typedef typename RECT::value_type TYPE;
33 static const TYPE max_value = std::numeric_limits<TYPE>::max();
Mathias Agopian20f68782009-05-11 00:03:41 -070034
Fabien Sanglardf8e93662017-02-16 19:29:35 -080035 /*
Mathias Agopian20f68782009-05-11 00:03:41 -070036 * Common boolean operations:
37 * value is computed as 0b101 op 0b110
38 * other boolean operation are possible, simply compute
39 * their corresponding value with the above formulae and use
40 * it when instantiating a region_operator.
41 */
42 static const uint32_t LHS = 0x5; // 0b101
43 static const uint32_t RHS = 0x6; // 0b110
44 enum {
45 op_nand = LHS & ~RHS,
46 op_and = LHS & RHS,
47 op_or = LHS | RHS,
48 op_xor = LHS ^ RHS
49 };
50
51 struct region {
52 RECT const* rects;
53 size_t count;
54 TYPE dx;
55 TYPE dy;
56 inline region(const region& rhs)
57 : rects(rhs.rects), count(rhs.count), dx(rhs.dx), dy(rhs.dy) { }
Colin Cross382ecd32016-09-26 13:33:59 -070058 inline region(RECT const* _r, size_t _c)
59 : rects(_r), count(_c), dx(), dy() { }
60 inline region(RECT const* _r, size_t _c, TYPE _dx, TYPE _dy)
61 : rects(_r), count(_c), dx(_dx), dy(_dy) { }
Mathias Agopian20f68782009-05-11 00:03:41 -070062 };
63
64 class region_rasterizer {
65 friend class region_operator;
66 virtual void operator()(const RECT& rect) = 0;
Mathias Agopiane7c4c282009-07-07 12:29:17 -070067 public:
Colin Cross17576de2016-09-26 13:07:06 -070068 virtual ~region_rasterizer() { }
Mathias Agopian20f68782009-05-11 00:03:41 -070069 };
70
Colin Cross8f279962016-09-26 13:08:16 -070071 inline region_operator(uint32_t op, const region& lhs, const region& rhs)
Mathias Agopian20f68782009-05-11 00:03:41 -070072 : op_mask(op), spanner(lhs, rhs)
73 {
74 }
75
76 void operator()(region_rasterizer& rasterizer) {
Pablo Ceballos60d69222015-08-07 14:47:20 -070077 RECT current(Rect::EMPTY_RECT);
Mathias Agopian20f68782009-05-11 00:03:41 -070078 do {
79 SpannerInner spannerInner(spanner.lhs, spanner.rhs);
80 int inside = spanner.next(current.top, current.bottom);
81 spannerInner.prepare(inside);
82 do {
83 TYPE left, right;
Colin Cross382ecd32016-09-26 13:33:59 -070084 int inner_inside = spannerInner.next(current.left, current.right);
85 if ((op_mask >> inner_inside) & 1) {
Mathias Agopian20f68782009-05-11 00:03:41 -070086 if (current.left < current.right &&
87 current.top < current.bottom) {
88 rasterizer(current);
89 }
90 }
Mathias Agopian38a7fa22009-10-15 18:08:15 -070091 } while(!spannerInner.isDone());
Mathias Agopian20f68782009-05-11 00:03:41 -070092 } while(!spanner.isDone());
93 }
94
95private:
96 uint32_t op_mask;
97
98 class SpannerBase
99 {
100 public:
Mathias Agopian3aecbb02012-04-16 18:40:30 -0700101 SpannerBase()
102 : lhs_head(max_value), lhs_tail(max_value),
103 rhs_head(max_value), rhs_tail(max_value) {
104 }
105
Mathias Agopian20f68782009-05-11 00:03:41 -0700106 enum {
107 lhs_before_rhs = 0,
108 lhs_after_rhs = 1,
109 lhs_coincide_rhs = 2
110 };
111
112 protected:
113 TYPE lhs_head;
114 TYPE lhs_tail;
115 TYPE rhs_head;
116 TYPE rhs_tail;
117
118 inline int next(TYPE& head, TYPE& tail,
119 bool& more_lhs, bool& more_rhs)
120 {
121 int inside;
122 more_lhs = false;
123 more_rhs = false;
124 if (lhs_head < rhs_head) {
125 inside = lhs_before_rhs;
126 head = lhs_head;
127 if (lhs_tail <= rhs_head) {
128 tail = lhs_tail;
129 more_lhs = true;
130 } else {
131 lhs_head = rhs_head;
132 tail = rhs_head;
133 }
134 } else if (rhs_head < lhs_head) {
135 inside = lhs_after_rhs;
136 head = rhs_head;
137 if (rhs_tail <= lhs_head) {
138 tail = rhs_tail;
139 more_rhs = true;
140 } else {
141 rhs_head = lhs_head;
142 tail = lhs_head;
143 }
144 } else {
145 inside = lhs_coincide_rhs;
146 head = lhs_head;
147 if (lhs_tail <= rhs_tail) {
148 tail = rhs_head = lhs_tail;
149 more_lhs = true;
150 }
151 if (rhs_tail <= lhs_tail) {
152 tail = lhs_head = rhs_tail;
153 more_rhs = true;
154 }
155 }
156 return inside;
157 }
158 };
159
160 class Spanner : protected SpannerBase
161 {
162 friend class region_operator;
163 region lhs;
164 region rhs;
165
166 public:
Colin Cross382ecd32016-09-26 13:33:59 -0700167 inline Spanner(const region& _lhs, const region& _rhs)
168 : lhs(_lhs), rhs(_rhs)
Mathias Agopian20f68782009-05-11 00:03:41 -0700169 {
Mathias Agopian3aecbb02012-04-16 18:40:30 -0700170 if (lhs.count) {
171 SpannerBase::lhs_head = lhs.rects->top + lhs.dy;
172 SpannerBase::lhs_tail = lhs.rects->bottom + lhs.dy;
173 }
174 if (rhs.count) {
175 SpannerBase::rhs_head = rhs.rects->top + rhs.dy;
176 SpannerBase::rhs_tail = rhs.rects->bottom + rhs.dy;
177 }
Mathias Agopian20f68782009-05-11 00:03:41 -0700178 }
179
180 inline bool isDone() const {
181 return !rhs.count && !lhs.count;
182 }
183
184 inline int next(TYPE& top, TYPE& bottom)
185 {
186 bool more_lhs = false;
187 bool more_rhs = false;
188 int inside = SpannerBase::next(top, bottom, more_lhs, more_rhs);
189 if (more_lhs) {
190 advance(lhs, SpannerBase::lhs_head, SpannerBase::lhs_tail);
191 }
192 if (more_rhs) {
193 advance(rhs, SpannerBase::rhs_head, SpannerBase::rhs_tail);
194 }
195 return inside;
196 }
197
198 private:
199 static inline
200 void advance(region& reg, TYPE& aTop, TYPE& aBottom) {
201 // got to next span
202 size_t count = reg.count;
203 RECT const * rects = reg.rects;
204 RECT const * const end = rects + count;
205 const int top = rects->top;
206 while (rects != end && rects->top == top) {
207 rects++;
208 count--;
209 }
210 if (rects != end) {
211 aTop = rects->top + reg.dy;
212 aBottom = rects->bottom + reg.dy;
213 } else {
214 aTop = max_value;
215 aBottom = max_value;
216 }
217 reg.rects = rects;
218 reg.count = count;
219 }
220 };
221
222 class SpannerInner : protected SpannerBase
223 {
224 region lhs;
225 region rhs;
226
227 public:
Colin Cross382ecd32016-09-26 13:33:59 -0700228 inline SpannerInner(const region& _lhs, const region& _rhs)
229 : lhs(_lhs), rhs(_rhs)
Mathias Agopian20f68782009-05-11 00:03:41 -0700230 {
231 }
232
233 inline void prepare(int inside) {
Mathias Agopian20f68782009-05-11 00:03:41 -0700234 if (inside == SpannerBase::lhs_before_rhs) {
Mathias Agopian3aecbb02012-04-16 18:40:30 -0700235 if (lhs.count) {
236 SpannerBase::lhs_head = lhs.rects->left + lhs.dx;
237 SpannerBase::lhs_tail = lhs.rects->right + lhs.dx;
238 }
Mathias Agopian20f68782009-05-11 00:03:41 -0700239 SpannerBase::rhs_head = max_value;
240 SpannerBase::rhs_tail = max_value;
241 } else if (inside == SpannerBase::lhs_after_rhs) {
242 SpannerBase::lhs_head = max_value;
243 SpannerBase::lhs_tail = max_value;
Mathias Agopian3aecbb02012-04-16 18:40:30 -0700244 if (rhs.count) {
245 SpannerBase::rhs_head = rhs.rects->left + rhs.dx;
246 SpannerBase::rhs_tail = rhs.rects->right + rhs.dx;
247 }
Mathias Agopian20f68782009-05-11 00:03:41 -0700248 } else {
Mathias Agopian3aecbb02012-04-16 18:40:30 -0700249 if (lhs.count) {
250 SpannerBase::lhs_head = lhs.rects->left + lhs.dx;
251 SpannerBase::lhs_tail = lhs.rects->right + lhs.dx;
252 }
253 if (rhs.count) {
254 SpannerBase::rhs_head = rhs.rects->left + rhs.dx;
255 SpannerBase::rhs_tail = rhs.rects->right + rhs.dx;
256 }
Mathias Agopian20f68782009-05-11 00:03:41 -0700257 }
258 }
259
260 inline bool isDone() const {
261 return SpannerBase::lhs_head == max_value &&
262 SpannerBase::rhs_head == max_value;
263 }
264
265 inline int next(TYPE& left, TYPE& right)
266 {
267 bool more_lhs = false;
268 bool more_rhs = false;
269 int inside = SpannerBase::next(left, right, more_lhs, more_rhs);
270 if (more_lhs) {
271 advance(lhs, SpannerBase::lhs_head, SpannerBase::lhs_tail);
272 }
273 if (more_rhs) {
274 advance(rhs, SpannerBase::rhs_head, SpannerBase::rhs_tail);
275 }
276 return inside;
277 }
278
279 private:
280 static inline
281 void advance(region& reg, TYPE& left, TYPE& right) {
282 if (reg.rects && reg.count) {
283 const int cur_span_top = reg.rects->top;
284 reg.rects++;
285 reg.count--;
286 if (!reg.count || reg.rects->top != cur_span_top) {
287 left = max_value;
288 right = max_value;
289 } else {
290 left = reg.rects->left + reg.dx;
291 right = reg.rects->right + reg.dx;
292 }
293 }
294 }
295 };
296
297 Spanner spanner;
298};
299
300// ----------------------------------------------------------------------------
301};
302
303#endif /* ANDROID_UI_PRIVATE_REGION_HELPER_H */