SkRegion.cpp File Reference

#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>

Go to the source code of this file.

Classes
class	RunArray
struct	spanRec
class	RgnOper

Macros
#define	SkRegion_gEmptyRunHeadPtr   ((SkRegionPriv::RunHead*)-1)
#define	SkRegion_gRectRunHeadPtr   nullptr
#define	assert_valid_pair(left, rite)
#define	QUICK_EXIT_TRUE_COUNT   (-1)

Functions
static SkRegionPriv::RunType *	skip_intervals (const SkRegionPriv::RunType runs[])
static bool	isRunCountEmpty (int count)
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)
static bool	scanline_intersects (const SkRegionPriv::RunType runs[], SkRegionPriv::RunType L, SkRegionPriv::RunType R)
static int32_t	pin_offset_s32 (int32_t min, int32_t max, int32_t offset)
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)
static int	operate (const SkRegionPriv::RunType a_runs[], const SkRegionPriv::RunType b_runs[], RunArray *dst, SkRegion::Op op, bool quickExit)
static bool	setEmptyCheck (SkRegion *result)
static bool	setRectCheck (SkRegion *result, const SkIRect &rect)
static bool	setRegionCheck (SkRegion *result, const SkRegion &rgn)
static bool	validate_run_count (int ySpanCount, int intervalCount, int runCount)
static bool	validate_run (const int32_t *runs, int runCount, const SkIRect &givenBounds, int32_t ySpanCount, int32_t intervalCount)
static void	visit_pairs (int pairCount, int y, const int32_t pairs[], const std::function< void(const SkIRect &)> &visitor)

Variables
constexpr int	kRunArrayStackCount = 256
struct {
uint8_t   fMin
uint8_t   fMax
}	gOpMinMax []

Macro Definition Documentation

assert_valid_pair

#define assert_valid_pair	(		left,
			rite
	)

Definition at line 682 of file SkRegion.cpp.

QUICK_EXIT_TRUE_COUNT

#define QUICK_EXIT_TRUE_COUNT   (-1)

Definition at line 899 of file SkRegion.cpp.

SkRegion_gEmptyRunHeadPtr

#define SkRegion_gEmptyRunHeadPtr   ((SkRegionPriv::RunHead*)-1)

Definition at line 38 of file SkRegion.cpp.

SkRegion_gRectRunHeadPtr

#define SkRegion_gRectRunHeadPtr   nullptr

Definition at line 39 of file SkRegion.cpp.

Function Documentation

distance_to_sentinel()

static int distance_to_sentinel ( const SkRegionPriv::RunType *  runs )

static

Definition at line 776 of file SkRegion.cpp.

                                                                 {
    const SkRegionPriv::RunType* ptr = runs;
    while (*ptr != SkRegion_kRunTypeSentinel) { ptr += 2; }
    return ptr - runs;
}

isRunCountEmpty()

static bool isRunCountEmpty ( int  count )

static

Definition at line 275 of file SkRegion.cpp.

                                       {
    return count <= 2;
}

operate()

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

static

Definition at line 901 of file SkRegion.cpp.

                                   {
    const SkRegionPriv::RunType gEmptyScanline[] = {
        0,  // fake bottom value
        0,  // zero intervals
        SkRegion_kRunTypeSentinel,
        // just need a 2nd value, since spanRec.init() reads 2 values, even
        // though if the first value is the sentinel, it ignores the 2nd value.
        // w/o the 2nd value here, we might read uninitialized memory.
        // This happens when we are using gSentinel, which is pointing at
        // our sentinel value.
        0
    };
    const SkRegionPriv::RunType* const gSentinel = &gEmptyScanline[2];
 
    int a_top = *a_runs++;
    int a_bot = *a_runs++;
    int b_top = *b_runs++;
    int b_bot = *b_runs++;
 
    a_runs += 1;    // skip the intervalCount;
    b_runs += 1;    // skip the intervalCount;
 
    // Now a_runs and b_runs to their intervals (or sentinel)
 
    assert_sentinel(a_top, false);
    assert_sentinel(a_bot, false);
    assert_sentinel(b_top, false);
    assert_sentinel(b_bot, false);
 
    RgnOper oper(std::min(a_top, b_top), dst, op);
 
    int prevBot = SkRegion_kRunTypeSentinel; // so we fail the first test
 
    while (a_bot < SkRegion_kRunTypeSentinel ||
           b_bot < SkRegion_kRunTypeSentinel) {
        int                         top, bot SK_INIT_TO_AVOID_WARNING;
        const SkRegionPriv::RunType*    run0 = gSentinel;
        const SkRegionPriv::RunType*    run1 = gSentinel;
        bool                        a_flush = false;
        bool                        b_flush = false;
 
        if (a_top < b_top) {
            top = a_top;
            run0 = a_runs;
            if (a_bot <= b_top) {   // [...] <...>
                bot = a_bot;
                a_flush = true;
            } else {  // [...<..]...> or [...<...>...]
                bot = a_top = b_top;
            }
        } else if (b_top < a_top) {
            top = b_top;
            run1 = b_runs;
            if (b_bot <= a_top) {   // [...] <...>
                bot = b_bot;
                b_flush = true;
            } else {    // [...<..]...> or [...<...>...]
                bot = b_top = a_top;
            }
        } else {    // a_top == b_top
            top = a_top;    // or b_top
            run0 = a_runs;
            run1 = b_runs;
            if (a_bot <= b_bot) {
                bot = b_top = a_bot;
                a_flush = true;
            }
            if (b_bot <= a_bot) {
                bot = a_top = b_bot;
                b_flush = true;
            }
        }
 
        if (top > prevBot) {
            oper.addSpan(top, gSentinel, gSentinel);
        }
        oper.addSpan(bot, run0, run1);
 
        if (quickExit && !oper.isEmpty()) {
            return QUICK_EXIT_TRUE_COUNT;
        }
 
        if (a_flush) {
            a_runs = skip_intervals(a_runs);
            a_top = a_bot;
            a_bot = *a_runs++;
            a_runs += 1;    // skip uninitialized intervalCount
            if (a_bot == SkRegion_kRunTypeSentinel) {
                a_top = a_bot;
            }
        }
        if (b_flush) {
            b_runs = skip_intervals(b_runs);
            b_top = b_bot;
            b_bot = *b_runs++;
            b_runs += 1;    // skip uninitialized intervalCount
            if (b_bot == SkRegion_kRunTypeSentinel) {
                b_top = b_bot;
            }
        }
 
        prevBot = bot;
    }
    return oper.flush();
}

operate_on_span()

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

static

Definition at line 782 of file SkRegion.cpp.

                                             {
    // This is a worst-case for this span plus two for TWO terminating sentinels.
    array->resizeToAtLeast(
            dstOffset + distance_to_sentinel(a_runs) + distance_to_sentinel(b_runs) + 2);
    SkRegionPriv::RunType* dst = &(*array)[dstOffset]; // get pointer AFTER resizing.
 
    spanRec rec;
    bool    firstInterval = true;
 
    rec.init(a_runs, b_runs);
 
    while (!rec.done()) {
        rec.next();
 
        int left = rec.fLeft;
        int rite = rec.fRite;
 
        // add left,rite to our dst buffer (checking for coincidence
        if ((unsigned)(rec.fInside - min) <= (unsigned)(max - min) &&
                left < rite) {    // skip if equal
            if (firstInterval || *(dst - 1) < left) {
                *dst++ = (SkRegionPriv::RunType)(left);
                *dst++ = (SkRegionPriv::RunType)(rite);
                firstInterval = false;
            } else {
                // update the right edge
                *(dst - 1) = (SkRegionPriv::RunType)(rite);
            }
        }
    }
    SkASSERT(dst < &(*array)[array->count() - 1]);
    *dst++ = SkRegion_kRunTypeSentinel;
    return dst - &(*array)[0];
}

pin_offset_s32()

static int32_t pin_offset_s32 ( int32_t  min, int32_t  max, int32_t  offset  )

static

Definition at line 587 of file SkRegion.cpp.

                                                                        {
    SkASSERT(min <= max);
    const int32_t lo = -SK_MaxS32-1,
                  hi = +SK_MaxS32;
    if ((int64_t)min + offset < lo) { offset = lo - min; }
    if ((int64_t)max + offset > hi) { offset = hi - max; }
    return offset;
}

scanline_bottom()

static SkRegionPriv::RunType scanline_bottom ( const SkRegionPriv::RunType  runs[] )

static

Definition at line 398 of file SkRegion.cpp.

                                                                             {
    return runs[0];
}

scanline_contains()

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

static

Definition at line 407 of file SkRegion.cpp.

                                                                            {
    runs += 2;  // skip Bottom and IntervalCount
    for (;;) {
        if (L < runs[0]) {
            break;
        }
        if (R <= runs[1]) {
            return true;
        }
        runs += 2;
    }
    return false;
}

scanline_intersects()

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

static

Definition at line 487 of file SkRegion.cpp.

                                                                              {
    runs += 2;  // skip Bottom and IntervalCount
    for (;;) {
        if (R <= runs[0]) {
            break;
        }
        if (L < runs[1]) {
            return true;
        }
        runs += 2;
    }
    return false;
}

scanline_next()

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

static

Definition at line 402 of file SkRegion.cpp.

                                                                                  {
    // skip [B N [L R]... S]
    return runs + 2 + runs[1] * 2 + 1;
}

setEmptyCheck()

static bool setEmptyCheck ( SkRegion *  result )

static

Definition at line 1028 of file SkRegion.cpp.

                                            {
    return result ? result->setEmpty() : false;
}

setRectCheck()

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

static

Definition at line 1032 of file SkRegion.cpp.

                                                                {
    return result ? result->setRect(rect) : !rect.isEmpty();
}

setRegionCheck()

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

static

Definition at line 1036 of file SkRegion.cpp.

                                                                  {
    return result ? result->setRegion(rgn) : !rgn.isEmpty();
}

skip_intervals()

static SkRegionPriv::RunType * skip_intervals ( const SkRegionPriv::RunType  runs[] )

static

Definition at line 84 of file SkRegion.cpp.

                                                                             {
    int intervals = runs[-1];
#ifdef SK_DEBUG
    if (intervals > 0) {
        SkASSERT(runs[0] < runs[1]);
        SkASSERT(runs[1] < SkRegion_kRunTypeSentinel);
    } else {
        SkASSERT(0 == intervals);
        SkASSERT(SkRegion_kRunTypeSentinel == runs[0]);
    }
#endif
    runs += intervals * 2 + 1;
    return const_cast<SkRegionPriv::RunType*>(runs);
}

validate_run()

static bool validate_run ( const int32_t *  runs, int  runCount, const SkIRect &  givenBounds, int32_t  ySpanCount, int32_t  intervalCount  )

static

Definition at line 1200 of file SkRegion.cpp.

                                                {
    // Region Layout:
    //    Top ( Bottom Span_Interval_Count ( Left Right )* Sentinel )+ Sentinel
    if (!validate_run_count(SkToInt(ySpanCount), SkToInt(intervalCount), runCount)) {
        return false;
    }
    SkASSERT(runCount >= 7);  // 7==SkRegion::kRectRegionRuns
    // quick safety check:
    if (runs[runCount - 1] != SkRegion_kRunTypeSentinel ||
        runs[runCount - 2] != SkRegion_kRunTypeSentinel) {
        return false;
    }
    const int32_t* const end = runs + runCount;
    SkIRect bounds = {0, 0, 0 ,0};  // calulated bounds
    SkIRect rect = {0, 0, 0, 0};    // current rect
    rect.fTop = *runs++;
    if (rect.fTop == SkRegion_kRunTypeSentinel) {
        return false;  // no rect can contain SkRegion_kRunTypeSentinel
    }
    if (rect.fTop != givenBounds.fTop) {
        return false;  // Must not begin with empty span that does not contribute to bounds.
    }
    do {
        --ySpanCount;
        if (ySpanCount < 0) {
            return false;  // too many yspans
        }
        rect.fBottom = *runs++;
        if (rect.fBottom == SkRegion_kRunTypeSentinel) {
            return false;
        }
        if (rect.fBottom > givenBounds.fBottom) {
            return false;  // Must not end with empty span that does not contribute to bounds.
        }
        if (rect.fBottom <= rect.fTop) {
            return false;  // y-intervals must be ordered; rects must be non-empty.
        }
 
        int32_t xIntervals = *runs++;
        SkASSERT(runs < end);
        if (xIntervals < 0 || xIntervals > intervalCount || runs + 1 + 2 * xIntervals > end) {
            return false;
        }
        intervalCount -= xIntervals;
        bool firstInterval = true;
        int32_t lastRight = 0;  // check that x-intervals are distinct and ordered.
        while (xIntervals-- > 0) {
            rect.fLeft = *runs++;
            rect.fRight = *runs++;
            if (rect.fLeft == SkRegion_kRunTypeSentinel ||
                rect.fRight == SkRegion_kRunTypeSentinel ||
                rect.fLeft >= rect.fRight ||  // check non-empty rect
                (!firstInterval && rect.fLeft <= lastRight)) {
                return false;
            }
            lastRight = rect.fRight;
            firstInterval = false;
            bounds.join(rect);
        }
        if (*runs++ != SkRegion_kRunTypeSentinel) {
            return false;  // required check sentinal.
        }
        rect.fTop = rect.fBottom;
        SkASSERT(runs < end);
    } while (*runs != SkRegion_kRunTypeSentinel);
    ++runs;
    if (ySpanCount != 0 || intervalCount != 0 || givenBounds != bounds) {
        return false;
    }
    SkASSERT(runs == end);  // if ySpanCount && intervalCount are right, must be correct length.
    return true;
}

validate_run_count()

static bool validate_run_count ( int  ySpanCount, int  intervalCount, int  runCount  )

static

Definition at line 1182 of file SkRegion.cpp.

                                                                                {
    // return 2 + 3 * ySpanCount + 2 * intervalCount;
    if (ySpanCount < 1 || intervalCount < 2) {
        return false;
    }
    SkSafeMath safeMath;
    int sum = 2;
    sum = safeMath.addInt(sum, ySpanCount);
    sum = safeMath.addInt(sum, ySpanCount);
    sum = safeMath.addInt(sum, ySpanCount);
    sum = safeMath.addInt(sum, intervalCount);
    sum = safeMath.addInt(sum, intervalCount);
    return safeMath && sum == runCount;
}

visit_pairs()

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

static

Definition at line 1547 of file SkRegion.cpp.

                                                                          {
    for (int i = 0; i < pairCount; ++i) {
        visitor({ pairs[0], y, pairs[1], y + 1 });
        pairs += 2;
    }
}

Variable Documentation

fMax

uint8_t fMax

Definition at line 826 of file SkRegion.cpp.

fMin

uint8_t fMin

Definition at line 825 of file SkRegion.cpp.

const struct { ... } gOpMinMax[]

Initial value:

= {
    { 1, 1 },   
    { 3, 3 },   
    { 1, 3 },   
    { 1, 2 }    
}

kRunArrayStackCount

constexpr int kRunArrayStackCount = 256

constexpr

Definition at line 41 of file SkRegion.cpp.