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