blob: 92cfba8114de684c1bb79501be521c81c25a2917 [file] [log] [blame]
/*
* Copyright (C) 2009 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef ANDROID_UI_PRIVATE_REGION_HELPER_H
#define ANDROID_UI_PRIVATE_REGION_HELPER_H
#include <stdint.h>
#include <sys/types.h>
#include <limits>
#include <limits>
namespace android {
// ----------------------------------------------------------------------------
template <typename RECT>
class region_operator {
public:
typedef typename RECT::value_type TYPE;
static const TYPE max_value = std::numeric_limits<TYPE>::max();
/*
* Common boolean operations:
* value is computed as 0b101 op 0b110
* other boolean operation are possible, simply compute
* their corresponding value with the above formulae and use
* it when instantiating a region_operator.
*/
static const uint32_t LHS = 0x5; // 0b101
static const uint32_t RHS = 0x6; // 0b110
enum { op_nand = LHS & ~RHS, op_and = LHS & RHS, op_or = LHS | RHS, op_xor = LHS ^ RHS };
struct region {
RECT const* rects;
size_t count;
TYPE dx;
TYPE dy;
inline region(const region& rhs)
: rects(rhs.rects), count(rhs.count), dx(rhs.dx), dy(rhs.dy) {}
inline region(RECT const* _r, size_t _c) : rects(_r), count(_c), dx(), dy() {}
inline region(RECT const* _r, size_t _c, TYPE _dx, TYPE _dy)
: rects(_r), count(_c), dx(_dx), dy(_dy) {}
};
class region_rasterizer {
friend class region_operator;
virtual void operator()(const RECT& rect) = 0;
public:
virtual ~region_rasterizer() {}
};
inline region_operator(uint32_t op, const region& lhs, const region& rhs)
: op_mask(op), spanner(lhs, rhs) {}
void operator()(region_rasterizer& rasterizer) {
RECT current(Rect::EMPTY_RECT);
do {
SpannerInner spannerInner(spanner.lhs, spanner.rhs);
int inside = spanner.next(current.top, current.bottom);
spannerInner.prepare(inside);
do {
int inner_inside = spannerInner.next(current.left, current.right);
if ((op_mask >> inner_inside) & 1) {
if (current.left < current.right && current.top < current.bottom) {
rasterizer(current);
}
}
} while (!spannerInner.isDone());
} while (!spanner.isDone());
}
private:
uint32_t op_mask;
class SpannerBase {
public:
SpannerBase()
: lhs_head(max_value),
lhs_tail(max_value),
rhs_head(max_value),
rhs_tail(max_value) {}
enum { lhs_before_rhs = 0, lhs_after_rhs = 1, lhs_coincide_rhs = 2 };
protected:
TYPE lhs_head;
TYPE lhs_tail;
TYPE rhs_head;
TYPE rhs_tail;
inline int next(TYPE& head, TYPE& tail, bool& more_lhs, bool& more_rhs) {
int inside;
more_lhs = false;
more_rhs = false;
if (lhs_head < rhs_head) {
inside = lhs_before_rhs;
head = lhs_head;
if (lhs_tail <= rhs_head) {
tail = lhs_tail;
more_lhs = true;
} else {
lhs_head = rhs_head;
tail = rhs_head;
}
} else if (rhs_head < lhs_head) {
inside = lhs_after_rhs;
head = rhs_head;
if (rhs_tail <= lhs_head) {
tail = rhs_tail;
more_rhs = true;
} else {
rhs_head = lhs_head;
tail = lhs_head;
}
} else {
inside = lhs_coincide_rhs;
head = lhs_head;
if (lhs_tail <= rhs_tail) {
tail = rhs_head = lhs_tail;
more_lhs = true;
}
if (rhs_tail <= lhs_tail) {
tail = lhs_head = rhs_tail;
more_rhs = true;
}
}
return inside;
}
};
class Spanner : protected SpannerBase {
friend class region_operator;
region lhs;
region rhs;
public:
inline Spanner(const region& _lhs, const region& _rhs) : lhs(_lhs), rhs(_rhs) {
if (lhs.count) {
SpannerBase::lhs_head = lhs.rects->top + lhs.dy;
SpannerBase::lhs_tail = lhs.rects->bottom + lhs.dy;
}
if (rhs.count) {
SpannerBase::rhs_head = rhs.rects->top + rhs.dy;
SpannerBase::rhs_tail = rhs.rects->bottom + rhs.dy;
}
}
inline bool isDone() const { return !rhs.count && !lhs.count; }
inline int next(TYPE& top, TYPE& bottom) {
bool more_lhs = false;
bool more_rhs = false;
int inside = SpannerBase::next(top, bottom, more_lhs, more_rhs);
if (more_lhs) {
advance(lhs, SpannerBase::lhs_head, SpannerBase::lhs_tail);
}
if (more_rhs) {
advance(rhs, SpannerBase::rhs_head, SpannerBase::rhs_tail);
}
return inside;
}
private:
static inline void advance(region& reg, TYPE& aTop, TYPE& aBottom) {
// got to next span
size_t count = reg.count;
RECT const* rects = reg.rects;
RECT const* const end = rects + count;
const int top = rects->top;
while (rects != end && rects->top == top) {
rects++;
count--;
}
if (rects != end) {
aTop = rects->top + reg.dy;
aBottom = rects->bottom + reg.dy;
} else {
aTop = max_value;
aBottom = max_value;
}
reg.rects = rects;
reg.count = count;
}
};
class SpannerInner : protected SpannerBase {
region lhs;
region rhs;
public:
inline SpannerInner(const region& _lhs, const region& _rhs) : lhs(_lhs), rhs(_rhs) {}
inline void prepare(int inside) {
if (inside == SpannerBase::lhs_before_rhs) {
if (lhs.count) {
SpannerBase::lhs_head = lhs.rects->left + lhs.dx;
SpannerBase::lhs_tail = lhs.rects->right + lhs.dx;
}
SpannerBase::rhs_head = max_value;
SpannerBase::rhs_tail = max_value;
} else if (inside == SpannerBase::lhs_after_rhs) {
SpannerBase::lhs_head = max_value;
SpannerBase::lhs_tail = max_value;
if (rhs.count) {
SpannerBase::rhs_head = rhs.rects->left + rhs.dx;
SpannerBase::rhs_tail = rhs.rects->right + rhs.dx;
}
} else {
if (lhs.count) {
SpannerBase::lhs_head = lhs.rects->left + lhs.dx;
SpannerBase::lhs_tail = lhs.rects->right + lhs.dx;
}
if (rhs.count) {
SpannerBase::rhs_head = rhs.rects->left + rhs.dx;
SpannerBase::rhs_tail = rhs.rects->right + rhs.dx;
}
}
}
inline bool isDone() const {
return SpannerBase::lhs_head == max_value && SpannerBase::rhs_head == max_value;
}
inline int next(TYPE& left, TYPE& right) {
bool more_lhs = false;
bool more_rhs = false;
int inside = SpannerBase::next(left, right, more_lhs, more_rhs);
if (more_lhs) {
advance(lhs, SpannerBase::lhs_head, SpannerBase::lhs_tail);
}
if (more_rhs) {
advance(rhs, SpannerBase::rhs_head, SpannerBase::rhs_tail);
}
return inside;
}
private:
static inline void advance(region& reg, TYPE& left, TYPE& right) {
if (reg.rects && reg.count) {
const int cur_span_top = reg.rects->top;
reg.rects++;
reg.count--;
if (!reg.count || reg.rects->top != cur_span_top) {
left = max_value;
right = max_value;
} else {
left = reg.rects->left + reg.dx;
right = reg.rects->right + reg.dx;
}
}
}
};
Spanner spanner;
};
// ----------------------------------------------------------------------------
}; // namespace android
#endif /* ANDROID_UI_PRIVATE_REGION_HELPER_H */