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