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 namespace android {
25 // ----------------------------------------------------------------------------
26 
27 template<typename RECT>
28 class region_operator
29 {
30 public:
31     typedef typename RECT::value_type TYPE;
32     static const TYPE max_value = std::numeric_limits<TYPE>::max();
33 
34     /*
35      * Common boolean operations:
36      * value is computed as 0b101 op 0b110
37      *    other boolean operation are possible, simply compute
38      *    their corresponding value with the above formulae and use
39      *    it when instantiating a region_operator.
40      */
41     static const uint32_t LHS = 0x5;  // 0b101
42     static const uint32_t RHS = 0x6;  // 0b110
43     enum {
44         op_nand = LHS & ~RHS,
45         op_and  = LHS &  RHS,
46         op_or   = LHS |  RHS,
47         op_xor  = LHS ^  RHS
48     };
49 
50     struct region {
51         RECT const* rects;
52         size_t count;
53         TYPE dx;
54         TYPE dy;
regionregion55         inline region(const region& rhs)
56             : rects(rhs.rects), count(rhs.count), dx(rhs.dx), dy(rhs.dy) { }
regionregion57         inline region(RECT const* _r, size_t _c)
58             : rects(_r), count(_c), dx(), dy() { }
regionregion59         inline region(RECT const* _r, size_t _c, TYPE _dx, TYPE _dy)
60             : rects(_r), count(_c), dx(_dx), dy(_dy) { }
61     };
62 
63     class region_rasterizer {
64         friend class region_operator;
65         virtual void operator()(const RECT& rect) = 0;
66     public:
~region_rasterizer()67         virtual ~region_rasterizer() { }
68     };
69 
region_operator(uint32_t op,const region & lhs,const region & rhs)70     inline region_operator(uint32_t op, const region& lhs, const region& rhs)
71         : op_mask(op), spanner(lhs, rhs)
72     {
73     }
74 
operator()75     void operator()(region_rasterizer& rasterizer) {
76         RECT current(Rect::EMPTY_RECT);
77         do {
78             SpannerInner spannerInner(spanner.lhs, spanner.rhs);
79             int inside = spanner.next(current.top, current.bottom);
80             spannerInner.prepare(inside);
81             do {
82                 TYPE left, right;
83                 int inner_inside = spannerInner.next(current.left, current.right);
84                 if ((op_mask >> inner_inside) & 1) {
85                     if (current.left < current.right &&
86                             current.top < current.bottom) {
87                         rasterizer(current);
88                     }
89                 }
90             } while(!spannerInner.isDone());
91         } while(!spanner.isDone());
92     }
93 
94 private:
95     uint32_t op_mask;
96 
97     class SpannerBase
98     {
99     public:
SpannerBase()100         SpannerBase()
101             : lhs_head(max_value), lhs_tail(max_value),
102               rhs_head(max_value), rhs_tail(max_value) {
103         }
104 
105         enum {
106             lhs_before_rhs   = 0,
107             lhs_after_rhs    = 1,
108             lhs_coincide_rhs = 2
109         };
110 
111     protected:
112         TYPE lhs_head;
113         TYPE lhs_tail;
114         TYPE rhs_head;
115         TYPE rhs_tail;
116 
next(TYPE & head,TYPE & tail,bool & more_lhs,bool & more_rhs)117         inline int next(TYPE& head, TYPE& tail,
118                 bool& more_lhs, bool& more_rhs)
119         {
120             int inside;
121             more_lhs = false;
122             more_rhs = false;
123             if (lhs_head < rhs_head) {
124                 inside = lhs_before_rhs;
125                 head = lhs_head;
126                 if (lhs_tail <= rhs_head) {
127                     tail = lhs_tail;
128                     more_lhs = true;
129                 } else {
130                     lhs_head = rhs_head;
131                     tail = rhs_head;
132                 }
133             } else if (rhs_head < lhs_head) {
134                 inside = lhs_after_rhs;
135                 head = rhs_head;
136                 if (rhs_tail <= lhs_head) {
137                     tail = rhs_tail;
138                     more_rhs = true;
139                 } else {
140                     rhs_head = lhs_head;
141                     tail = lhs_head;
142                 }
143             } else {
144                 inside = lhs_coincide_rhs;
145                 head = lhs_head;
146                 if (lhs_tail <= rhs_tail) {
147                     tail = rhs_head = lhs_tail;
148                     more_lhs = true;
149                 }
150                 if (rhs_tail <= lhs_tail) {
151                     tail = lhs_head = rhs_tail;
152                     more_rhs = true;
153                 }
154             }
155             return inside;
156         }
157     };
158 
159     class Spanner : protected SpannerBase
160     {
161         friend class region_operator;
162         region lhs;
163         region rhs;
164 
165     public:
Spanner(const region & _lhs,const region & _rhs)166         inline Spanner(const region& _lhs, const region& _rhs)
167         : lhs(_lhs), rhs(_rhs)
168         {
169             if (lhs.count) {
170                 SpannerBase::lhs_head = lhs.rects->top      + lhs.dy;
171                 SpannerBase::lhs_tail = lhs.rects->bottom   + lhs.dy;
172             }
173             if (rhs.count) {
174                 SpannerBase::rhs_head = rhs.rects->top      + rhs.dy;
175                 SpannerBase::rhs_tail = rhs.rects->bottom   + rhs.dy;
176             }
177         }
178 
isDone()179         inline bool isDone() const {
180             return !rhs.count && !lhs.count;
181         }
182 
next(TYPE & top,TYPE & bottom)183         inline int next(TYPE& top, TYPE& bottom)
184         {
185             bool more_lhs = false;
186             bool more_rhs = false;
187             int inside = SpannerBase::next(top, bottom, more_lhs, more_rhs);
188             if (more_lhs) {
189                 advance(lhs, SpannerBase::lhs_head, SpannerBase::lhs_tail);
190             }
191             if (more_rhs) {
192                 advance(rhs, SpannerBase::rhs_head, SpannerBase::rhs_tail);
193             }
194             return inside;
195         }
196 
197     private:
198         static inline
advance(region & reg,TYPE & aTop,TYPE & aBottom)199         void advance(region& reg, TYPE& aTop, TYPE& aBottom) {
200             // got to next span
201             size_t count = reg.count;
202             RECT const * rects = reg.rects;
203             RECT const * const end = rects + count;
204             const int top = rects->top;
205             while (rects != end && rects->top == top) {
206                 rects++;
207                 count--;
208             }
209             if (rects != end) {
210                 aTop    = rects->top    + reg.dy;
211                 aBottom = rects->bottom + reg.dy;
212             } else {
213                 aTop    = max_value;
214                 aBottom = max_value;
215             }
216             reg.rects = rects;
217             reg.count = count;
218         }
219     };
220 
221     class SpannerInner : protected SpannerBase
222     {
223         region lhs;
224         region rhs;
225 
226     public:
SpannerInner(const region & _lhs,const region & _rhs)227         inline SpannerInner(const region& _lhs, const region& _rhs)
228             : lhs(_lhs), rhs(_rhs)
229         {
230         }
231 
prepare(int inside)232         inline void prepare(int inside) {
233             if (inside == SpannerBase::lhs_before_rhs) {
234                 if (lhs.count) {
235                     SpannerBase::lhs_head = lhs.rects->left  + lhs.dx;
236                     SpannerBase::lhs_tail = lhs.rects->right + lhs.dx;
237                 }
238                 SpannerBase::rhs_head = max_value;
239                 SpannerBase::rhs_tail = max_value;
240             } else if (inside == SpannerBase::lhs_after_rhs) {
241                 SpannerBase::lhs_head = max_value;
242                 SpannerBase::lhs_tail = max_value;
243                 if (rhs.count) {
244                     SpannerBase::rhs_head = rhs.rects->left  + rhs.dx;
245                     SpannerBase::rhs_tail = rhs.rects->right + rhs.dx;
246                 }
247             } else {
248                 if (lhs.count) {
249                     SpannerBase::lhs_head = lhs.rects->left  + lhs.dx;
250                     SpannerBase::lhs_tail = lhs.rects->right + lhs.dx;
251                 }
252                 if (rhs.count) {
253                     SpannerBase::rhs_head = rhs.rects->left  + rhs.dx;
254                     SpannerBase::rhs_tail = rhs.rects->right + rhs.dx;
255                 }
256             }
257         }
258 
isDone()259         inline bool isDone() const {
260             return SpannerBase::lhs_head == max_value &&
261                    SpannerBase::rhs_head == max_value;
262         }
263 
next(TYPE & left,TYPE & right)264         inline int next(TYPE& left, TYPE& right)
265         {
266             bool more_lhs = false;
267             bool more_rhs = false;
268             int inside = SpannerBase::next(left, right, more_lhs, more_rhs);
269             if (more_lhs) {
270                 advance(lhs, SpannerBase::lhs_head, SpannerBase::lhs_tail);
271             }
272             if (more_rhs) {
273                 advance(rhs, SpannerBase::rhs_head, SpannerBase::rhs_tail);
274             }
275             return inside;
276         }
277 
278     private:
279         static inline
advance(region & reg,TYPE & left,TYPE & right)280         void advance(region& reg, TYPE& left, TYPE& right) {
281             if (reg.rects && reg.count) {
282                 const int cur_span_top = reg.rects->top;
283                 reg.rects++;
284                 reg.count--;
285                 if (!reg.count || reg.rects->top != cur_span_top) {
286                     left  = max_value;
287                     right = max_value;
288                 } else {
289                     left  = reg.rects->left  + reg.dx;
290                     right = reg.rects->right + reg.dx;
291                 }
292             }
293         }
294     };
295 
296     Spanner spanner;
297 };
298 
299 // ----------------------------------------------------------------------------
300 };
301 
302 #endif /* ANDROID_UI_PRIVATE_REGION_HELPER_H */
303