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