chromium/third_party/skia/src/core/SkRegion.cpp

/*
 * Copyright 2006 The Android Open Source Project
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#include "include/core/SkRegion.h"

#include "include/private/base/SkMacros.h"
#include "include/private/base/SkMalloc.h"
#include "include/private/base/SkMath.h"
#include "include/private/base/SkTemplates.h"
#include "include/private/base/SkTo.h"
#include "src/base/SkBuffer.h"
#include "src/base/SkSafeMath.h"
#include "src/core/SkRegionPriv.h"

#include <algorithm>
#include <atomic>
#include <cstring>
#include <functional>

usingnamespaceskia_private;

/* Region Layout
 *
 *  TOP
 *
 *  [ Bottom, X-Intervals, [Left, Right]..., X-Sentinel ]
 *  ...
 *
 *  Y-Sentinel
 */

/////////////////////////////////////////////////////////////////////////////////////////////////

#define SkRegion_gEmptyRunHeadPtr …
#define SkRegion_gRectRunHeadPtr …

constexpr int kRunArrayStackCount = …;

// This is a simple data structure which is like a STArray<N,T,true>, except that:
//   - It does not initialize memory.
//   - It does not distinguish between reserved space and initialized space.
//   - resizeToAtLeast() instead of resize()
//   - Uses sk_realloc_throw()
//   - Can never be made smaller.
// Measurement:  for the `region_union_16` benchmark, this is 6% faster.
class RunArray { … };

/*  Pass in the beginning with the intervals.
 *  We back up 1 to read the interval-count.
 *  Return the beginning of the next scanline (i.e. the next Y-value)
 */
static SkRegionPriv::RunType* skip_intervals(const SkRegionPriv::RunType runs[]) { … }

bool SkRegion::RunsAreARect(const SkRegion::RunType runs[], int count,
                            SkIRect* bounds) { … }

//////////////////////////////////////////////////////////////////////////

SkRegion::SkRegion() { … }

SkRegion::SkRegion(const SkRegion& src) { … }

SkRegion::SkRegion(const SkIRect& rect) { … }

SkRegion::~SkRegion() { … }

void SkRegion::freeRuns() { … }

void SkRegion::allocateRuns(int count, int ySpanCount, int intervalCount) { … }

void SkRegion::allocateRuns(int count) { … }

void SkRegion::allocateRuns(const RunHead& head) { … }

SkRegion& SkRegion::operator=(const SkRegion& src) { … }

void SkRegion::swap(SkRegion& other) { … }

int SkRegion::computeRegionComplexity() const { … }

bool SkRegion::setEmpty() { … }

bool SkRegion::setRect(const SkIRect& r) { … }

bool SkRegion::setRegion(const SkRegion& src) { … }

bool SkRegion::op(const SkIRect& rect, const SkRegion& rgn, Op op) { … }

bool SkRegion::op(const SkRegion& rgn, const SkIRect& rect, Op op) { … }

///////////////////////////////////////////////////////////////////////////////

#ifdef SK_BUILD_FOR_ANDROID_FRAMEWORK
#include <stdio.h>
char* SkRegion::toString() {
    Iterator iter(*this);
    int count = 0;
    while (!iter.done()) {
        count++;
        iter.next();
    }
    // 4 ints, up to 10 digits each plus sign, 3 commas, '(', ')', SkRegion() and '\0'
    const int max = (count*((11*4)+5))+11+1;
    char* result = (char*)sk_malloc_throw(max);
    if (result == nullptr) {
        return nullptr;
    }
    count = snprintf(result, max, "SkRegion(");
    iter.reset(*this);
    while (!iter.done()) {
        const SkIRect& r = iter.rect();
        count += snprintf(result+count, max - count,
                "(%d,%d,%d,%d)", r.fLeft, r.fTop, r.fRight, r.fBottom);
        iter.next();
    }
    count += snprintf(result+count, max - count, ")");
    return result;
}
#endif

///////////////////////////////////////////////////////////////////////////////

int SkRegion::count_runtype_values(int* itop, int* ibot) const { … }

static bool isRunCountEmpty(int count) { … }

bool SkRegion::setRuns(RunType runs[], int count) { … }

void SkRegion::BuildRectRuns(const SkIRect& bounds,
                             RunType runs[kRectRegionRuns]) { … }

bool SkRegion::contains(int32_t x, int32_t y) const { … }

static SkRegionPriv::RunType scanline_bottom(const SkRegionPriv::RunType runs[]) { … }

static const SkRegionPriv::RunType* scanline_next(const SkRegionPriv::RunType runs[]) { … }

static bool scanline_contains(const SkRegionPriv::RunType runs[],
                              SkRegionPriv::RunType L, SkRegionPriv::RunType R) { … }

bool SkRegion::contains(const SkIRect& r) const { … }

bool SkRegion::contains(const SkRegion& rgn) const { … }

const SkRegion::RunType* SkRegion::getRuns(RunType tmpStorage[],
                                           int* intervals) const { … }

///////////////////////////////////////////////////////////////////////////////

static bool scanline_intersects(const SkRegionPriv::RunType runs[],
                                SkRegionPriv::RunType L, SkRegionPriv::RunType R) { … }

bool SkRegion::intersects(const SkIRect& r) const { … }

bool SkRegion::intersects(const SkRegion& rgn) const { … }

///////////////////////////////////////////////////////////////////////////////

bool SkRegion::operator==(const SkRegion& b) const { … }

// Return a (new) offset such that when applied (+=) to min and max, we don't overflow/underflow
static int32_t pin_offset_s32(int32_t min, int32_t max, int32_t offset) { … }

void SkRegion::translate(int dx, int dy, SkRegion* dst) const { … }

///////////////////////////////////////////////////////////////////////////////

bool SkRegion::setRects(const SkIRect rects[], int count) { … }

///////////////////////////////////////////////////////////////////////////////

#if defined _WIN32  // disable warning : local variable used without having been initialized
#pragma warning ( push )
#pragma warning ( disable : 4701 )
#endif

#ifdef SK_DEBUG
static void assert_valid_pair(int left, int rite)
{ … }
#else
    #define assert_valid_pair …
#endif

struct spanRec { … };

static int distance_to_sentinel(const SkRegionPriv::RunType* runs) { … }

static int operate_on_span(const SkRegionPriv::RunType a_runs[],
                           const SkRegionPriv::RunType b_runs[],
                           RunArray* array, int dstOffset,
                           int min, int max) { … }

#if defined _WIN32
#pragma warning ( pop )
#endif

static const struct { … } gOpMinMax[] = …;
// need to ensure that the op enum lines up with our minmax array
static_assert …;
static_assert …;
static_assert …;
static_assert …;

class RgnOper { … };

// want a unique value to signal that we exited due to quickExit
#define QUICK_EXIT_TRUE_COUNT …

static int operate(const SkRegionPriv::RunType a_runs[],
                   const SkRegionPriv::RunType b_runs[],
                   RunArray* dst,
                   SkRegion::Op op,
                   bool quickExit) { … }

///////////////////////////////////////////////////////////////////////////////

/*  Given count RunTypes in a complex region, return the worst case number of
    logical intervals that represents (i.e. number of rects that would be
    returned from the iterator).

    We could just return count/2, since there must be at least 2 values per
    interval, but we can first trim off the const overhead of the initial TOP
    value, plus the final BOTTOM + 2 sentinels.
 */
#if 0 // UNUSED
static int count_to_intervals(int count) {
    SkASSERT(count >= 6);   // a single rect is 6 values
    return (count - 4) >> 1;
}
#endif

static bool setEmptyCheck(SkRegion* result) { … }

static bool setRectCheck(SkRegion* result, const SkIRect& rect) { … }

static bool setRegionCheck(SkRegion* result, const SkRegion& rgn) { … }

bool SkRegion::Oper(const SkRegion& rgnaOrig, const SkRegion& rgnbOrig, Op op,
                    SkRegion* result) { … }

bool SkRegion::op(const SkRegion& rgna, const SkRegion& rgnb, Op op) { … }

///////////////////////////////////////////////////////////////////////////////

size_t SkRegion::writeToMemory(void* storage) const { … }

static bool validate_run_count(int ySpanCount, int intervalCount, int runCount) { … }

// Validate that a memory sequence is a valid region.
// Try to check all possible errors.
// never read beyond &runs[runCount-1].
static bool validate_run(const int32_t* runs,
                         int runCount,
                         const SkIRect& givenBounds,
                         int32_t ySpanCount,
                         int32_t intervalCount) { … }
size_t SkRegion::readFromMemory(const void* storage, size_t length) { … }

///////////////////////////////////////////////////////////////////////////////

bool SkRegion::isValid() const { … }

#ifdef SK_DEBUG
void SkRegionPriv::Validate(const SkRegion& rgn) { … }

void SkRegion::dump() const { … }

#endif

///////////////////////////////////////////////////////////////////////////////

SkRegion::Iterator::Iterator(const SkRegion& rgn) { … }

bool SkRegion::Iterator::rewind() { … }

void SkRegion::Iterator::reset(const SkRegion& rgn) { … }

void SkRegion::Iterator::next() { … }

SkRegion::Cliperator::Cliperator(const SkRegion& rgn, const SkIRect& clip)
        : … { … }

void SkRegion::Cliperator::next() { … }

///////////////////////////////////////////////////////////////////////////////

SkRegion::Spanerator::Spanerator(const SkRegion& rgn, int y, int left,
                                 int right) { … }

bool SkRegion::Spanerator::next(int* left, int* right) { … }

///////////////////////////////////////////////////////////////////////////////////////////////////

static void visit_pairs(int pairCount, int y, const int32_t pairs[],
                        const std::function<void(const SkIRect&)>& visitor) { … }

void SkRegionPriv::VisitSpans(const SkRegion& rgn,
                              const std::function<void(const SkIRect&)>& visitor) { … }