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 23 namespace android { 24 // ---------------------------------------------------------------------------- 25 26 template<typename RECT> 27 class region_operator 28 { 29 public: 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(Rect::EMPTY_RECT); 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 93 private: 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
