1 /*
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 <limits>
21 #include <stdint.h>
22 #include <sys/types.h>
23 
24 #include <limits>
25 
26 namespace android {
27 // ----------------------------------------------------------------------------
28 
29 template<typename RECT>
30 class region_operator
31 {
32 public:
33     typedef typename RECT::value_type TYPE;
34     static const TYPE max_value = std::numeric_limits<TYPE>::max();
35 
36     /*
37      * Common boolean operations:
38      * value is computed as 0b101 op 0b110
39      *    other boolean operation are possible, simply compute
40      *    their corresponding value with the above formulae and use
41      *    it when instantiating a region_operator.
42      */
43     static const uint32_t LHS = 0x5;  // 0b101
44     static const uint32_t RHS = 0x6;  // 0b110
45     enum {
46         op_nand = LHS & ~RHS,
47         op_and  = LHS &  RHS,
48         op_or   = LHS |  RHS,
49         op_xor  = LHS ^  RHS
50     };
51 
52     struct region {
53         RECT const* rects;
54         size_t count;
55         TYPE dx;
56         TYPE dy;
regionregion57         inline region(const region& rhs)
58             : rects(rhs.rects), count(rhs.count), dx(rhs.dx), dy(rhs.dy) { }
regionregion59         inline region(RECT const* _r, size_t _c)
60             : rects(_r), count(_c), dx(), dy() { }
regionregion61         inline region(RECT const* _r, size_t _c, TYPE _dx, TYPE _dy)
62             : rects(_r), count(_c), dx(_dx), dy(_dy) { }
63     };
64 
65     class region_rasterizer {
66         friend class region_operator;
67         virtual void operator()(const RECT& rect) = 0;
68     public:
~region_rasterizer()69         virtual ~region_rasterizer() { }
70     };
71 
region_operator(uint32_t op,const region & lhs,const region & rhs)72     inline region_operator(uint32_t op, const region& lhs, const region& rhs)
73         : op_mask(op), spanner(lhs, rhs)
74     {
75     }
76 
operator()77     void operator()(region_rasterizer& rasterizer) {
78         RECT current(Rect::EMPTY_RECT);
79         do {
80             SpannerInner spannerInner(spanner.lhs, spanner.rhs);
81             int inside = spanner.next(current.top, current.bottom);
82             spannerInner.prepare(inside);
83             do {
84                 int inner_inside = spannerInner.next(current.left, current.right);
85                 if ((op_mask >> inner_inside) & 1) {
86                     if (current.left < current.right &&
87                             current.top < current.bottom) {
88                         rasterizer(current);
89                     }
90                 }
91             } while(!spannerInner.isDone());
92         } while(!spanner.isDone());
93     }
94 
95 private:
96     uint32_t op_mask;
97 
98     class SpannerBase
99     {
100     public:
SpannerBase()101         SpannerBase()
102             : lhs_head(max_value), lhs_tail(max_value),
103               rhs_head(max_value), rhs_tail(max_value) {
104         }
105 
106         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 
next(TYPE & head,TYPE & tail,bool & more_lhs,bool & more_rhs)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:
Spanner(const region & _lhs,const region & _rhs)167         inline Spanner(const region& _lhs, const region& _rhs)
168         : lhs(_lhs), rhs(_rhs)
169         {
170             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             }
178         }
179 
isDone()180         inline bool isDone() const {
181             return !rhs.count && !lhs.count;
182         }
183 
next(TYPE & top,TYPE & bottom)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
advance(region & reg,TYPE & aTop,TYPE & aBottom)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:
SpannerInner(const region & _lhs,const region & _rhs)228         inline SpannerInner(const region& _lhs, const region& _rhs)
229             : lhs(_lhs), rhs(_rhs)
230         {
231         }
232 
prepare(int inside)233         inline void prepare(int inside) {
234             if (inside == SpannerBase::lhs_before_rhs) {
235                 if (lhs.count) {
236                     SpannerBase::lhs_head = lhs.rects->left  + lhs.dx;
237                     SpannerBase::lhs_tail = lhs.rects->right + lhs.dx;
238                 }
239                 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;
244                 if (rhs.count) {
245                     SpannerBase::rhs_head = rhs.rects->left  + rhs.dx;
246                     SpannerBase::rhs_tail = rhs.rects->right + rhs.dx;
247                 }
248             } else {
249                 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                 }
257             }
258         }
259 
isDone()260         inline bool isDone() const {
261             return SpannerBase::lhs_head == max_value &&
262                    SpannerBase::rhs_head == max_value;
263         }
264 
next(TYPE & left,TYPE & right)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
advance(region & reg,TYPE & left,TYPE & right)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 */
304