RegionHelper.h revision 20f68782a4ea71c6a977d7f87d8288d3daa265ec 
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    };
66
67    inline region_operator(int op, const region& lhs, const region& rhs)
68        : op_mask(op), spanner(lhs, rhs)
69    {
70    }
71
72    void operator()(region_rasterizer& rasterizer) {
73        RECT current;
74        do {
75            SpannerInner spannerInner(spanner.lhs, spanner.rhs);
76            int inside = spanner.next(current.top, current.bottom);
77            spannerInner.prepare(inside);
78            do {
79                TYPE left, right;
80                int inside = spannerInner.next(current.left, current.right);
81                if ((op_mask >> inside) & 1) {
82                    if (current.left < current.right &&
83                            current.top < current.bottom) {
84                        rasterizer(current);
85                    }
86                }
87            } while(!spannerInner.isDone());
88        } while(!spanner.isDone());
89    }
90
91private:
92    uint32_t op_mask;
93
94    class SpannerBase
95    {
96    public:
97        enum {
98            lhs_before_rhs   = 0,
99            lhs_after_rhs    = 1,
100            lhs_coincide_rhs = 2
101        };
102
103    protected:
104        TYPE lhs_head;
105        TYPE lhs_tail;
106        TYPE rhs_head;
107        TYPE rhs_tail;
108
109        inline int next(TYPE& head, TYPE& tail,
110                bool& more_lhs, bool& more_rhs)
111        {
112            int inside;
113            more_lhs = false;
114            more_rhs = false;
115            if (lhs_head < rhs_head) {
116                inside = lhs_before_rhs;
117                head = lhs_head;
118                if (lhs_tail <= rhs_head) {
119                    tail = lhs_tail;
120                    more_lhs = true;
121                } else {
122                    lhs_head = rhs_head;
123                    tail = rhs_head;
124                }
125            } else if (rhs_head < lhs_head) {
126                inside = lhs_after_rhs;
127                head = rhs_head;
128                if (rhs_tail <= lhs_head) {
129                    tail = rhs_tail;
130                    more_rhs = true;
131                } else {
132                    rhs_head = lhs_head;
133                    tail = lhs_head;
134                }
135            } else {
136                inside = lhs_coincide_rhs;
137                head = lhs_head;
138                if (lhs_tail <= rhs_tail) {
139                    tail = rhs_head = lhs_tail;
140                    more_lhs = true;
141                }
142                if (rhs_tail <= lhs_tail) {
143                    tail = lhs_head = rhs_tail;
144                    more_rhs = true;
145                }
146            }
147            return inside;
148        }
149    };
150
151    class Spanner : protected SpannerBase
152    {
153        friend class region_operator;
154        region lhs;
155        region rhs;
156
157    public:
158        inline Spanner(const region& lhs, const region& rhs)
159            : lhs(lhs), rhs(rhs)
160        {
161            SpannerBase::lhs_head = lhs.rects->top      + lhs.dy;
162            SpannerBase::lhs_tail = lhs.rects->bottom   + lhs.dy;
163            SpannerBase::rhs_head = rhs.rects->top      + rhs.dy;
164            SpannerBase::rhs_tail = rhs.rects->bottom   + rhs.dy;
165        }
166
167        inline bool isDone() const {
168            return !rhs.count && !lhs.count;
169        }
170
171        inline int next(TYPE& top, TYPE& bottom)
172        {
173            bool more_lhs = false;
174            bool more_rhs = false;
175            int inside = SpannerBase::next(top, bottom, more_lhs, more_rhs);
176            if (more_lhs) {
177                advance(lhs, SpannerBase::lhs_head, SpannerBase::lhs_tail);
178            }
179            if (more_rhs) {
180                advance(rhs, SpannerBase::rhs_head, SpannerBase::rhs_tail);
181            }
182            return inside;
183        }
184
185    private:
186        static inline
187        void advance(region& reg, TYPE& aTop, TYPE& aBottom) {
188            // got to next span
189            size_t count = reg.count;
190            RECT const * rects = reg.rects;
191            RECT const * const end = rects + count;
192            const int top = rects->top;
193            while (rects != end && rects->top == top) {
194                rects++;
195                count--;
196            }
197            if (rects != end) {
198                aTop    = rects->top    + reg.dy;
199                aBottom = rects->bottom + reg.dy;
200            } else {
201                aTop    = max_value;
202                aBottom = max_value;
203            }
204            reg.rects = rects;
205            reg.count = count;
206        }
207    };
208
209    class SpannerInner : protected SpannerBase
210    {
211        region lhs;
212        region rhs;
213
214    public:
215        inline SpannerInner(const region& lhs, const region& rhs)
216            : lhs(lhs), rhs(rhs)
217        {
218        }
219
220        inline void prepare(int inside) {
221            SpannerBase::lhs_head = lhs.rects->left  + lhs.dx;
222            SpannerBase::lhs_tail = lhs.rects->right + lhs.dx;
223            SpannerBase::rhs_head = rhs.rects->left  + rhs.dx;
224            SpannerBase::rhs_tail = rhs.rects->right + rhs.dx;
225            if (inside == SpannerBase::lhs_before_rhs) {
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            } else {
232                // use both spans
233            }
234        }
235
236        inline bool isDone() const {
237            return SpannerBase::lhs_head == max_value &&
238                   SpannerBase::rhs_head == max_value;
239        }
240
241        inline int next(TYPE& left, TYPE& right)
242        {
243            bool more_lhs = false;
244            bool more_rhs = false;
245            int inside = SpannerBase::next(left, right, more_lhs, more_rhs);
246            if (more_lhs) {
247                advance(lhs, SpannerBase::lhs_head, SpannerBase::lhs_tail);
248            }
249            if (more_rhs) {
250                advance(rhs, SpannerBase::rhs_head, SpannerBase::rhs_tail);
251            }
252            return inside;
253        }
254
255    private:
256        static inline
257        void advance(region& reg, TYPE& left, TYPE& right) {
258            if (reg.rects && reg.count) {
259                const int cur_span_top = reg.rects->top;
260                reg.rects++;
261                reg.count--;
262                if (!reg.count || reg.rects->top != cur_span_top) {
263                    left  = max_value;
264                    right = max_value;
265                } else {
266                    left  = reg.rects->left  + reg.dx;
267                    right = reg.rects->right + reg.dx;
268                }
269            }
270        }
271    };
272
273    Spanner spanner;
274};
275
276// ----------------------------------------------------------------------------
277};
278
279#endif /* ANDROID_UI_PRIVATE_REGION_HELPER_H */
280