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