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{
29public:
30    typedef typename RECT::value_type TYPE;
31    static const TYPE max_value = 0x7FFFFFF;
32
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        SpannerBase()
100            : lhs_head(max_value), lhs_tail(max_value),
101              rhs_head(max_value), rhs_tail(max_value) {
102        }
103
104        enum {
105            lhs_before_rhs   = 0,
106            lhs_after_rhs    = 1,
107            lhs_coincide_rhs = 2
108        };
109
110    protected:
111        TYPE lhs_head;
112        TYPE lhs_tail;
113        TYPE rhs_head;
114        TYPE rhs_tail;
115
116        inline int next(TYPE& head, TYPE& tail,
117                bool& more_lhs, bool& more_rhs)
118        {
119            int inside;
120            more_lhs = false;
121            more_rhs = false;
122            if (lhs_head < rhs_head) {
123                inside = lhs_before_rhs;
124                head = lhs_head;
125                if (lhs_tail <= rhs_head) {
126                    tail = lhs_tail;
127                    more_lhs = true;
128                } else {
129                    lhs_head = rhs_head;
130                    tail = rhs_head;
131                }
132            } else if (rhs_head < lhs_head) {
133                inside = lhs_after_rhs;
134                head = rhs_head;
135                if (rhs_tail <= lhs_head) {
136                    tail = rhs_tail;
137                    more_rhs = true;
138                } else {
139                    rhs_head = lhs_head;
140                    tail = lhs_head;
141                }
142            } else {
143                inside = lhs_coincide_rhs;
144                head = lhs_head;
145                if (lhs_tail <= rhs_tail) {
146                    tail = rhs_head = lhs_tail;
147                    more_lhs = true;
148                }
149                if (rhs_tail <= lhs_tail) {
150                    tail = lhs_head = rhs_tail;
151                    more_rhs = true;
152                }
153            }
154            return inside;
155        }
156    };
157
158    class Spanner : protected SpannerBase
159    {
160        friend class region_operator;
161        region lhs;
162        region rhs;
163
164    public:
165        inline Spanner(const region& lhs, const region& rhs)
166        : lhs(lhs), rhs(rhs)
167        {
168            if (lhs.count) {
169                SpannerBase::lhs_head = lhs.rects->top      + lhs.dy;
170                SpannerBase::lhs_tail = lhs.rects->bottom   + lhs.dy;
171            }
172            if (rhs.count) {
173                SpannerBase::rhs_head = rhs.rects->top      + rhs.dy;
174                SpannerBase::rhs_tail = rhs.rects->bottom   + rhs.dy;
175            }
176        }
177
178        inline bool isDone() const {
179            return !rhs.count && !lhs.count;
180        }
181
182        inline int next(TYPE& top, TYPE& bottom)
183        {
184            bool more_lhs = false;
185            bool more_rhs = false;
186            int inside = SpannerBase::next(top, bottom, more_lhs, more_rhs);
187            if (more_lhs) {
188                advance(lhs, SpannerBase::lhs_head, SpannerBase::lhs_tail);
189            }
190            if (more_rhs) {
191                advance(rhs, SpannerBase::rhs_head, SpannerBase::rhs_tail);
192            }
193            return inside;
194        }
195
196    private:
197        static inline
198        void advance(region& reg, TYPE& aTop, TYPE& aBottom) {
199            // got to next span
200            size_t count = reg.count;
201            RECT const * rects = reg.rects;
202            RECT const * const end = rects + count;
203            const int top = rects->top;
204            while (rects != end && rects->top == top) {
205                rects++;
206                count--;
207            }
208            if (rects != end) {
209                aTop    = rects->top    + reg.dy;
210                aBottom = rects->bottom + reg.dy;
211            } else {
212                aTop    = max_value;
213                aBottom = max_value;
214            }
215            reg.rects = rects;
216            reg.count = count;
217        }
218    };
219
220    class SpannerInner : protected SpannerBase
221    {
222        region lhs;
223        region rhs;
224
225    public:
226        inline SpannerInner(const region& lhs, const region& rhs)
227            : lhs(lhs), rhs(rhs)
228        {
229        }
230
231        inline void prepare(int inside) {
232            if (inside == SpannerBase::lhs_before_rhs) {
233                if (lhs.count) {
234                    SpannerBase::lhs_head = lhs.rects->left  + lhs.dx;
235                    SpannerBase::lhs_tail = lhs.rects->right + lhs.dx;
236                }
237                SpannerBase::rhs_head = max_value;
238                SpannerBase::rhs_tail = max_value;
239            } else if (inside == SpannerBase::lhs_after_rhs) {
240                SpannerBase::lhs_head = max_value;
241                SpannerBase::lhs_tail = max_value;
242                if (rhs.count) {
243                    SpannerBase::rhs_head = rhs.rects->left  + rhs.dx;
244                    SpannerBase::rhs_tail = rhs.rects->right + rhs.dx;
245                }
246            } else {
247                if (lhs.count) {
248                    SpannerBase::lhs_head = lhs.rects->left  + lhs.dx;
249                    SpannerBase::lhs_tail = lhs.rects->right + lhs.dx;
250                }
251                if (rhs.count) {
252                    SpannerBase::rhs_head = rhs.rects->left  + rhs.dx;
253                    SpannerBase::rhs_tail = rhs.rects->right + rhs.dx;
254                }
255            }
256        }
257
258        inline bool isDone() const {
259            return SpannerBase::lhs_head == max_value &&
260                   SpannerBase::rhs_head == max_value;
261        }
262
263        inline int next(TYPE& left, TYPE& right)
264        {
265            bool more_lhs = false;
266            bool more_rhs = false;
267            int inside = SpannerBase::next(left, right, more_lhs, more_rhs);
268            if (more_lhs) {
269                advance(lhs, SpannerBase::lhs_head, SpannerBase::lhs_tail);
270            }
271            if (more_rhs) {
272                advance(rhs, SpannerBase::rhs_head, SpannerBase::rhs_tail);
273            }
274            return inside;
275        }
276
277    private:
278        static inline
279        void advance(region& reg, TYPE& left, TYPE& right) {
280            if (reg.rects && reg.count) {
281                const int cur_span_top = reg.rects->top;
282                reg.rects++;
283                reg.count--;
284                if (!reg.count || reg.rects->top != cur_span_top) {
285                    left  = max_value;
286                    right = max_value;
287                } else {
288                    left  = reg.rects->left  + reg.dx;
289                    right = reg.rects->right + reg.dx;
290                }
291            }
292        }
293    };
294
295    Spanner spanner;
296};
297
298// ----------------------------------------------------------------------------
299};
300
301#endif /* ANDROID_UI_PRIVATE_REGION_HELPER_H */
302