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