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