renderer/src/intersection_board.cpp

/*
 * Copyright 2024 Rive
 */

#include "intersection_board.hpp"

#include "rive/math/math_types.hpp"

#if !SIMD_NATIVE_GVEC &&                                                       \
    (defined(__SSE2__) || defined(_M_AMD64) || defined(_M_X64))
// MSVC doesn't get codegen for the inner loop. Provide direct SSE intrinsics.
#include <emmintrin.h>
#define FALLBACK_ON_SSE2_INTRINSICS
#else
#endif

namespace rive::gpu
{
void IntersectionTile::reset(int left,
                             int top,
                             int16_t baselineGroupIndex,
                             uint16_t baselineOverlapBits)
{
    // Since we mask non-intersecting groupIndices to zero, the "mask and max"
    // algorithm is only correct for positive values. (baselineGroupIndex is
    // only signed because SSE doesn't have an unsigned max instruction.)
    assert(baselineGroupIndex >= 0);
    m_topLeft = {left, top, left, top};
    m_baselineGroupIndex = baselineGroupIndex;
    m_maxGroupIndex = baselineGroupIndex;
    m_baselineOverlapBits = baselineOverlapBits;
    m_overlapBitsForMaxGroup = baselineOverlapBits;
    m_edges.clear();
    m_groupIndices.clear();
    m_overlapBits.clear();
    m_rectangleCount = 0;
}

template <GroupingType Type>
void IntersectionTile::addRectangle(int4 ltrb,
                                    int16_t groupIndex,
                                    uint16_t currentRectangleOverlapBits)
{
    assert(simd::all(ltrb.xy < ltrb.zw)); // Ensure ltrb isn't zero or negative.
    assert(groupIndex >= 0);

    if constexpr (Type == GroupingType::overlapAllowed)
    {
        if (m_overlapBits.size() != m_groupIndices.size())
        {
            // We did not previously have any overlap bits and now we're about
            // to - initialize the array with zeros (everything already in the
            // intersection tile has zeros as its overlap bits, or else the
            // boardContainsNonzeroOverlapBits flag would have already been
            // set).
            assert(m_overlapBits.empty());
            m_overlapBits.resize(m_groupIndices.size());
        }
    }
    else
    {
        static_assert(Type == GroupingType::disjoint);

        // Shouldn't pass any overlap bits in if we indicated they weren't
        // relevant
        assert(currentRectangleOverlapBits == 0);
    }

#if !defined(NDEBUG)
    // Ensure this rectangle preserves the integrity of our list.
    {
        auto r = findMaxIntersectingGroupIndex<Type>(ltrb, {});
        auto maxGroup = simd::reduce_max(r.maxGroupIndices);
        if constexpr (Type == GroupingType::overlapAllowed)
        {
            // If overlapping is allowed, this rectangle can be in the same
            // group as another it overlaps, but cannot be below it.
            assert(groupIndex >= maxGroup);
            assert(groupIndex >= m_baselineGroupIndex);
        }
        else
        {
            // If no overlapping is allowed, this rectangle cannot be at or
            // below a group it overlaps.
            assert(groupIndex > maxGroup);
            assert(groupIndex > m_baselineGroupIndex);
        }
    }
#endif

    // Translate ltrb to our tile and negate the right and bottom sides.
    ltrb -= m_topLeft;
    // right = TILE_DIM - right, bottom = TILE_DIM- bottom
    ltrb.zw = TILE_DIM - ltrb.zw;
    // Ensure ltrb isn't completely outside the tile.
    assert(simd::all(ltrb < TILE_DIM));
    ltrb = simd::max(ltrb, int4(0)); // Clamp ltrb to our tile.

    if constexpr (Type == GroupingType::overlapAllowed)
    {
        if (groupIndex == m_baselineGroupIndex &&
            (currentRectangleOverlapBits | m_baselineOverlapBits) ==
                m_baselineOverlapBits)
        {
            // Nothing needs to be done here, this is going into the baseline
            // group and it adds no new overlap bits that are not already in the
            // baseline.
            return;
        }
    }

    if (simd::all(ltrb == 0))
    {
        // ltrb covers the entire tile
        if constexpr (Type == GroupingType::overlapAllowed)
        {
            // This rectangle is allowed to be at or higher than the max group
            // (rather than strictly above it, in the no-overlap case)
            assert(groupIndex >= m_maxGroupIndex);

            if (groupIndex == m_maxGroupIndex)
            {
                // This rectangle is within the existing max group, so do a
                // heavier-handed update (some rectangles in the max group
                // may still need to stay, so we can't do a reset)
                updateBaselineToMaxGroupIndex<Type>(
                    currentRectangleOverlapBits);
                return;
            }
        }
        else
        {
            // If no overlapping is allowed, a full-tile rectangle had
            // better be above the current max group.
            assert(groupIndex > m_maxGroupIndex);
        }

        // Setting a new baseline, so reset everything, update the group index
        // and baseline overlap
        reset(m_topLeft.x,
              m_topLeft.y,
              groupIndex,
              currentRectangleOverlapBits);
        return;
    }

    // Append a chunk if needed, to make room for this new rectangle.
    uint32_t subIdx = m_rectangleCount % CHUNK_SIZE;
    if (subIdx == 0)
    {
        // Push back maximally negative rectangles so they always fail
        // intersection tests.
        assert(m_edges.size() * CHUNK_SIZE == m_rectangleCount);
        m_edges.push_back(int8x32(TILE_DIM + TILE_EDGE_BIAS));

        // Uninitialized since the corresponding rectangles never pass an
        // intersection test.
        assert(m_groupIndices.size() * CHUNK_SIZE == m_rectangleCount);
        m_groupIndices.emplace_back();

        if constexpr (Type == GroupingType::overlapAllowed)
        {
            assert(m_overlapBits.size() * CHUNK_SIZE == m_rectangleCount);
            m_overlapBits.emplace_back();
        }
    }

    // m_edges is a list of 8 rectangles encoded as
    // [L, T, TILE_DIM - R, TILE_DIM - B], relative to m_topLeft. The data is
    // also transposed: [L0..L7, T0..T7, -R0..R7, -B0..B7]. Bias ltrb so
    // we can use int8_t. SSE doesn't have an unsigned byte compare.
    int4 biased = ltrb + TILE_EDGE_BIAS;
    m_edges.back()[subIdx] = biased.x;
    m_edges.back()[subIdx + 1 * CHUNK_SIZE] = biased.y;
    m_edges.back()[subIdx + 2 * CHUNK_SIZE] =
        biased.z; // Already converted to "TILE_DIM - right" above.
    m_edges.back()[subIdx + 3 * CHUNK_SIZE] =
        biased.w; // Already converted to "TILE_DIM - bottom" above.

    m_groupIndices.back()[subIdx] = groupIndex;

    if constexpr (Type == GroupingType::overlapAllowed)
    {
        m_overlapBits.back()[subIdx] = currentRectangleOverlapBits;

        if (groupIndex > m_maxGroupIndex)
        {
            // There's a new maximum group, so set it and restart its overlap
            // bits.
            m_maxGroupIndex = groupIndex;
            m_overlapBitsForMaxGroup = currentRectangleOverlapBits;
        }
        else if (groupIndex == m_maxGroupIndex)
        {
            // This is going into the existing max group so add its overlap bits
            // to the max group's tracked overlap bits
            m_overlapBitsForMaxGroup |= currentRectangleOverlapBits;
        }
    }
    else
    {
        // If we aren't tracking overlap bits then simply ensuring the max group
        // index is correct is sufficient.
        m_maxGroupIndex = std::max(m_maxGroupIndex, groupIndex);
    }

    ++m_rectangleCount;
}

#ifdef WITH_RIVE_TOOLS
template <GroupingType Type>
void IntersectionTile::testingOnly_addRectangleAndValidate(
    int4 ltrb,
    int16_t groupIndex,
    uint16_t currentRectangleOverlapBits)
{
    addRectangle<Type>(ltrb, groupIndex, currentRectangleOverlapBits);

    // Baseline should not be higher than the inserted rectangle,
    // max group should not be lower.
    assert(m_baselineGroupIndex <= groupIndex);
    assert(m_maxGroupIndex >= groupIndex);

    // Should be no baseline overlap bits if there's no baseline
    // (ditto for max group)
    assert(m_baselineGroupIndex != 0 || m_baselineOverlapBits == 0);
    assert(m_maxGroupIndex != 0 || m_overlapBitsForMaxGroup == 0);

    uint16_t foundOverlapBitsForMaxGroup;

    if constexpr (Type == GroupingType::overlapAllowed)
    {
        foundOverlapBitsForMaxGroup = (m_baselineGroupIndex == m_maxGroupIndex)
                                          ? m_baselineOverlapBits
                                          : 0u;
    }
    else
    {
        // Ignore this value (not using std::ignore here because it
        // would require initializing the value first, which would
        // mean the compiler won't catch a mistake where this gets
        // used elsewhere when it shouldn't be)
        (void)foundOverlapBitsForMaxGroup;

        // If overlap isn't allowed this should never be allocated
        assert(m_overlapBits.empty());
    }

    // Exhaustively check to ensure that the overlap bits and max
    // group indices match our tracked values.
    auto maxGroupIndexFound = m_baselineGroupIndex;
    for (auto i = 0u; i < m_rectangleCount; i++)
    {
        auto outerI = i / CHUNK_SIZE;
        auto innerI = i % CHUNK_SIZE;

        assert(m_groupIndices[outerI][innerI] >= m_baselineGroupIndex);
        assert(m_groupIndices[outerI][innerI] <= m_maxGroupIndex);
        if constexpr (Type == GroupingType::overlapAllowed)
        {
            if (m_groupIndices[outerI][innerI] == m_maxGroupIndex)
            {
                foundOverlapBitsForMaxGroup |= m_overlapBits[outerI][innerI];
            }
        }
        maxGroupIndexFound =
            std::max(maxGroupIndexFound, m_groupIndices[outerI][innerI]);
    }

    if constexpr (Type == GroupingType::overlapAllowed)
    {
        assert(foundOverlapBitsForMaxGroup == m_overlapBitsForMaxGroup);
        if (m_baselineGroupIndex == m_maxGroupIndex)
        {
            // max group is allowed to have more set bits than the
            // baseline (as there might be non-full-tile rectangles
            // at that level), but there should never be bits in
            // baseline that aren't part of the max group set if
            // their group indices match.
            assert((m_overlapBitsForMaxGroup | m_baselineOverlapBits) ==
                   m_overlapBitsForMaxGroup);
        }
    }
    else
    {
        assert(m_overlapBitsForMaxGroup == 0);
        assert(m_baselineOverlapBits == 0);
    }

    assert(maxGroupIndexFound == m_maxGroupIndex);
}
#endif

template <GroupingType Type>
void IntersectionTile::updateBaselineToMaxGroupIndex(
    uint16_t additionalBaselineOverlapBits)
{
    // This should only be called when overlap testing is enabled. The template
    // argument is really just here to make it hard to accidentally call this
    // from a place where it will be wrong
    static_assert(Type == GroupingType::overlapAllowed);

    // We've added a full-tile rectangle at m_maxGroupIndex, which means we can
    // update the baseline and its overlap bits.
    if ((additionalBaselineOverlapBits | m_overlapBitsForMaxGroup) ==
            additionalBaselineOverlapBits ||
        m_rectangleCount == 0)
    {
        // This rectangle both covers the whole tile and either it contains all
        // of the existing overlap bits in this group, or there are no
        // existing rectangles (the max group is the already just the baseline),
        // which means we can do a simple reset, as we don't need to keep any
        // rectangles - even ones that are in this max group.
        reset(m_topLeft.x,
              m_topLeft.y,
              m_maxGroupIndex,
              m_overlapBitsForMaxGroup | additionalBaselineOverlapBits);
        return;
    }

    m_overlapBitsForMaxGroup |= additionalBaselineOverlapBits;

    if (m_maxGroupIndex == m_baselineGroupIndex)
    {
        if (m_overlapBitsForMaxGroup == m_baselineOverlapBits)
        {
            // This rectangle does not change the baseline or its bits in
            // any way, so we're done early.
            return;
        }

        m_baselineOverlapBits |= additionalBaselineOverlapBits;
    }
    else
    {
        m_baselineGroupIndex = m_maxGroupIndex;
        m_baselineOverlapBits = additionalBaselineOverlapBits;
    }

    // Do a pass through the array and zero out the group indices of any
    // rectangles that should no longer remain in the list (this makes the test
    // in the compaction loop more efficient).
    {
#if !defined(FALLBACK_ON_SSE2_INTRINSICS)
        auto baselineGroupIndexVector = int16x8(m_baselineGroupIndex);
        auto baselineOverlapBitsVector = uint16x8(m_baselineOverlapBits);
#else
        auto baselineGroupIndexVector = _mm_set1_epi16(m_baselineGroupIndex);
        auto baselineOverlapBitsVector = _mm_set1_epi16(m_baselineOverlapBits);
#endif
        for (size_t i = 0; i < m_groupIndices.size(); i++)
        {
#if !defined(FALLBACK_ON_SSE2_INTRINSICS)
            // Groups under the baseline will go away
            auto mask = m_groupIndices[i] >= baselineGroupIndexVector;

            // Of those that remained, only keep the ones where the overlap bits
            // have bits that aren't in the baseline's bits.
            mask &= ((baselineOverlapBitsVector | m_overlapBits[i]) !=
                     baselineOverlapBitsVector);

            m_groupIndices[i] &= mask;
#else
            // The SSE2 code has to build the mask backwards from the above
            // code, as there is neither a ">=" or "!=" operator.
            auto groupIndices = math::bit_cast<__m128i>(m_groupIndices[i]);
            auto overlapBits = math::bit_cast<__m128i>(m_overlapBits[i]);
            auto mask = _mm_cmpgt_epi16(baselineGroupIndexVector, groupIndices);

            mask = _mm_or_si128(
                mask,
                _mm_cmpeq_epi16(
                    baselineOverlapBitsVector,
                    _mm_or_si128(baselineOverlapBitsVector, overlapBits)));

            // Conveniently, there is a (~mask & groupIndices) single operation
            // to allow us to use the inverted mask directly.
            groupIndices = _mm_andnot_si128(mask, groupIndices);
            m_groupIndices[i] = math::bit_cast<int16x8>(groupIndices);
#endif
        }
    }

    // Now, remove all of the rectangles that are no longer above the line.
    // (Thankfully, ordering doesn't matter, so we don't need the partitioning
    // to be stable)

    // Start by scaning the first index forward until we find a rectangle that
    // doesn't need to stay (or we hit the end)
    size_t firstIdx = 0u;
    while (m_groupIndices[firstIdx / CHUNK_SIZE][firstIdx % CHUNK_SIZE] != 0)
    {
        firstIdx++;
        if (firstIdx == m_rectangleCount)
        {
            // Every rectangle stays! We don't have to do any additional
            // work.
            return;
        }
    }

    size_t lastIdx = m_rectangleCount - 1;
    while (lastIdx > firstIdx &&
           m_groupIndices[lastIdx / CHUNK_SIZE][lastIdx % CHUNK_SIZE] == 0)
    {
        --lastIdx;
    }

    while (firstIdx < lastIdx)
    {
        // Now first index points to something that should go and last index
        // points to something that should stay, and they're out of order. Move
        // the latter element to the beginning to put it into place.
        {
            size_t firstOuterIdx = firstIdx / CHUNK_SIZE;
            size_t firstInnerIdx = firstIdx % CHUNK_SIZE;
            size_t lastOuterIdx = lastIdx / CHUNK_SIZE;
            size_t lastInnerIdx = lastIdx % CHUNK_SIZE;

            // Put the one that wants to stay at the first index.

            m_edges[firstOuterIdx][firstInnerIdx + 0] =
                m_edges[lastOuterIdx][lastInnerIdx + 0];
            m_edges[firstOuterIdx][firstInnerIdx + CHUNK_SIZE] =
                m_edges[lastOuterIdx][lastInnerIdx + CHUNK_SIZE];
            m_edges[firstOuterIdx][firstInnerIdx + 2 * CHUNK_SIZE] =
                m_edges[lastOuterIdx][lastInnerIdx + 2 * CHUNK_SIZE];
            m_edges[firstOuterIdx][firstInnerIdx + 3 * CHUNK_SIZE] =
                m_edges[lastOuterIdx][lastInnerIdx + 3 * CHUNK_SIZE];

            m_groupIndices[firstOuterIdx][firstInnerIdx] =
                m_groupIndices[lastOuterIdx][lastInnerIdx];
            m_overlapBits[firstOuterIdx][firstInnerIdx] =
                m_overlapBits[lastOuterIdx][lastInnerIdx];

            // Update the group index at the last index to be a 0, which now
            // marks it as a "this doesn't need to stay" rectangle. This allows
            // it to act as a sentinel value for the loop where we increment
            // firstRectangleIndex so it can avoid an extra bounds check.
            m_groupIndices[lastOuterIdx][lastInnerIdx] = 0;
        }

        // Because of that zero, we're now guaranteed that there
        // is a rectangle that should be removed to the right of the first index
        // and one that should stay to the left of the last index (minimally,
        // the ones we just adjusted), so these inner loops do not need to
        // bounds check.
        do
        {
            ++firstIdx;
            assert(firstIdx < m_rectangleCount);
        } while (m_groupIndices[firstIdx / CHUNK_SIZE][firstIdx % CHUNK_SIZE] !=
                 0);

        do
        {
            --lastIdx;
            // NOTE: This assert seems backwards, but it's an unsigned variable
            // and will wrap past zero, and thus go *very* positive.
            assert(lastIdx < m_rectangleCount);
        } while (m_groupIndices[lastIdx / CHUNK_SIZE][lastIdx % CHUNK_SIZE] ==
                 0);
    }

    // firstRectangleIndex now points to the first rectangle that needs to be
    // removed, which means it is also our new rectangle count.
    m_rectangleCount = firstIdx;
    auto vectorElementCount = (m_rectangleCount + CHUNK_SIZE - 1) / CHUNK_SIZE;
    m_edges.resize(vectorElementCount);
    m_groupIndices.resize(vectorElementCount);
    m_overlapBits.resize(vectorElementCount);

    if (vectorElementCount > 0 && (m_rectangleCount % CHUNK_SIZE) != 0)
    {
        auto& lastEdges = m_edges.back();
        auto& lastGroupIndices = m_groupIndices.back();
        auto& lastOverlapBits = m_overlapBits.back();

        constexpr auto DEFAULT_EDGE_EXTENT = TILE_DIM + TILE_EDGE_BIAS;

        // We have a chunk with potentially some boxes that had entries that
        // shouldn't anymore, so clear them.
        for (auto i = (m_rectangleCount % CHUNK_SIZE); i < CHUNK_SIZE; i++)
        {
            lastEdges[i + 0 * CHUNK_SIZE] = DEFAULT_EDGE_EXTENT;
            lastEdges[i + 1 * CHUNK_SIZE] = DEFAULT_EDGE_EXTENT;
            lastEdges[i + 2 * CHUNK_SIZE] = DEFAULT_EDGE_EXTENT;
            lastEdges[i + 3 * CHUNK_SIZE] = DEFAULT_EDGE_EXTENT;
            lastGroupIndices[i] = 0;
            lastOverlapBits[i] = 0;
        }
    }
}

template <GroupingType Type>
IntersectionTile::FindResult IntersectionTile::findMaxIntersectingGroupIndex(
    int4 ltrb,
    FindResult running) const
{
    assert(simd::all(ltrb.xy < ltrb.zw)); // Ensure ltrb isn't zero or negative.

    // Since we mask non-intersecting groupIndices to zero, the "mask and max"
    // algorithm is only correct for positive values. (running.maxGroupIndices
    // is only signed because SSE pre 4.1 doesn't have an unsigned max
    // instruction.)
    assert(simd::all(running.maxGroupIndices >= 0));
    assert(m_baselineGroupIndex >= 0);
    assert(m_maxGroupIndex >= m_baselineGroupIndex);

    // Translate ltrb to our tile and negate the left and top sides.
    ltrb -= m_topLeft;
    // left = TILE_DIM - left, top = TILE_DIM - top
    ltrb.xy = TILE_DIM - ltrb.xy;
    assert(
        simd::all(ltrb > 0)); // Ensure ltrb isn't completely outside the tile.
    ltrb = simd::min(ltrb, int4(TILE_DIM)); // Clamp ltrb to our tile.

    if (simd::all(ltrb == TILE_DIM))
    {
        // ltrb covers the tile -- we know it intersects with every rectangle.
        if constexpr (Type == GroupingType::overlapAllowed)
        {
            auto currentMax = running.maxGroupIndices[0];
            if (currentMax < m_maxGroupIndex)
            {
                // The first element's max group index is changing, so restart
                // its overlap bits with the new set.
                running.maxGroupIndices[0] = m_maxGroupIndex;
                running.overlapBits[0] = m_overlapBitsForMaxGroup;
            }
            else if (currentMax == m_maxGroupIndex)
            {
                // The group index of this element is the same, so just add in
                // any new overlap bits that might exist.
                running.overlapBits[0] |= m_overlapBitsForMaxGroup;
            }
        }
        else
        {
            static_assert(Type == GroupingType::disjoint);

            running.maxGroupIndices[0] =
                std::max(running.maxGroupIndices[0], m_maxGroupIndex);
        }

        return running;
    }

    // Intersection test: l0 < r1 &&
    //                    t0 < b1 &&
    //                    r0 > l1 &&
    //                    b0 > t1
    //
    // Or, to make them all use the same operator: +l0 < +r1 &&
    //                                             +t0 < +b1 &&
    //                                             -r0 < -l1 &&
    //                                             -b0 < -t1
    //
    // m_edges are already encoded like the left column, so encode "ltrb" like
    // the right.
    //
    // Bias ltrb so we can use int8_t. SSE (pre-4.1) doesn't have an unsigned
    // byte compare.
    int4 biased = ltrb + TILE_EDGE_BIAS;
    int8x8 r = biased.z;
    int8x8 b = biased.w;
    int8x8 _l = biased.x; // Already converted to "TILE_DIM - left" above.
    int8x8 _t = biased.y; // Already converted to "TILE_DIM - top" above.

    assert(m_edges.size() == m_groupIndices.size());
    if constexpr (Type == GroupingType::overlapAllowed)
    {
        assert(m_edges.size() == m_overlapBits.size());
    }

#if !defined(FALLBACK_ON_SSE2_INTRINSICS)
    auto edges = m_edges.begin();
    auto groupIndices = m_groupIndices.begin();
    const uint16x8* groupOverlapBits = nullptr;

    // We only care about groupOverlapBits if this rectangle overlap testing is
    // enabled *and* there are non-zero overlap bits in the mix
    if constexpr (Type == GroupingType::overlapAllowed)
    {
        groupOverlapBits = m_overlapBits.data();
    }
    PUSH_DISABLE_CLANG_SIMD_ABI_WARNING()
    int8x32 complement = simd::join(r, b, _l, _t);
    for (; edges != m_edges.end(); ++edges, ++groupIndices)
    {
        // Test 32 edges!
        auto edgeMasks = *edges < complement;
        // Since the transposed L,T,R,B rows are a each 64-bit vectors,
        // "and-reducing" them returns the intersection test (l0 < r1 && t0 < b1
        // && r0 > l1 && b0 > t1) in each byte.
        int64_t isectMask =
            simd::reduce_and(math::bit_cast<int64x4>(edgeMasks));
        // Each element of isectMasks8 is 0xff if we intersect with the
        // corresponding rectangle, otherwise 0.
        int8x8 isectMasks8 = math::bit_cast<int8x8>(isectMask);
        // Widen isectMasks8 to 16 bits per mask, where each element of
        // isectMasks16 is 0xffff if we intersect with the rectangle, otherwise
        // 0.
        int16x8 isectMasks16 =
            math::bit_cast<int16x8>(simd::zip(isectMasks8, isectMasks8));
        // Mask out any groupIndices we don't intersect with so they don't
        // participate in the test for maximum groupIndex.
        int16x8 maskedGroupIndices = isectMasks16 & *groupIndices;

        // Doing this as a compile-time check to not have to do the test in the
        // loop at runtime.
        if constexpr (Type == GroupingType::overlapAllowed)
        {
            // Clear any bits from the running overlap where the new index is
            // covering it (i.e. there's a new closest group index)
            auto keepRunningBits =
                (maskedGroupIndices <= running.maxGroupIndices);
            running.overlapBits &= keepRunningBits;

            // Keep any bits from the current group where the running index is
            // not closer (i.e. where current is not covered).
            // Note: this will additionally keep bits where there has not yet
            // been an intersection (index is 0), and the current rectangle was
            // not intersected. This is fine - these bits will get cleared by
            // the above code when a rectangle intersection finally *does*
            // happen, so we can save on an additional mask with isectMask16.
            auto keepCurrentBits =
                (running.maxGroupIndices <= maskedGroupIndices);
            auto maskedOverlapBits = *groupOverlapBits & keepCurrentBits;

            // Combine the two sets, ultimately this will add bits from
            // overlapping rectangles that are in the new-highest draw group and
            // clear any bits that are not.
            running.overlapBits |= maskedOverlapBits;

            ++groupOverlapBits;
        }

        running.maxGroupIndices =
            simd::max(maskedGroupIndices, running.maxGroupIndices);
    }
    POP_DISABLE_CLANG_SIMD_ABI_WARNING()

#else
    // MSVC doesn't get good codegen for the above loop. Provide direct SSE
    // intrinsics.
    const __m128i* edgeData = reinterpret_cast<const __m128i*>(m_edges.data());
    const __m128i* groupIndices =
        reinterpret_cast<const __m128i*>(m_groupIndices.data());
    const __m128i* groupOverlapBits = nullptr;
    if constexpr (Type == GroupingType::overlapAllowed)
    {
        groupOverlapBits =
            reinterpret_cast<const __m128i*>(m_overlapBits.data());
    }
    __m128i complementLO = math::bit_cast<__m128i>(simd::join(r, b));
    __m128i complementHI = math::bit_cast<__m128i>(simd::join(_l, _t));
    __m128i localMaxGroupIndices =
        math::bit_cast<__m128i>(running.maxGroupIndices);
    auto localOverlapBits = math::bit_cast<__m128i>(running.overlapBits);
    for (size_t i = 0; i < m_groupIndices.size(); ++i)
    {
        __m128i edgesLO = edgeData[i * 2];
        __m128i edgesHI = edgeData[i * 2 + 1];
        // Test 32 edges!
        __m128i edgeMasksLO = _mm_cmpgt_epi8(complementLO, edgesLO);
        __m128i edgeMasksHI = _mm_cmpgt_epi8(complementHI, edgesHI);
        // AND L & R masks (bits 0:63) and T & B masks (bits 63:127).
        __m128i partialIsectMasks = _mm_and_si128(edgeMasksLO, edgeMasksHI);
        // Widen partial edge masks from 8 bits to 16.
        __m128i partialIsectMasksTB16 =
            _mm_unpackhi_epi8(partialIsectMasks, partialIsectMasks);
        __m128i partialIsectMasksLR16 =
            _mm_unpacklo_epi8(partialIsectMasks, partialIsectMasks);
        // AND LR masks with TB masks for a full LTRB intersection mask.
        __m128i isectMasks16 =
            _mm_and_si128(partialIsectMasksLR16, partialIsectMasksTB16);
        // Mask out the groupIndices that don't intersect.
        __m128i maskedGroupIndices =
            _mm_and_si128(isectMasks16, groupIndices[i]);

        // Doing this as a compile-time check to not have to do the test in the
        // loop at runtime.
        if constexpr (Type == GroupingType::overlapAllowed)
        {
            // Clear any bits from the running overlap where the new index is
            // covering it (i.e. there's a new closest group index)
            // NOTE: that masks and the "and"s are reversed from the non-SSE2
            // code above: SSE2 does not have integral >= or <= operations, so
            // the formulation here uses "!(a > b)" as equivalent to (a <= b),
            // thankfully using no additional instructions thanks to the
            // existence of "andnot" instructions.
            auto clearRunningBits =
                _mm_cmpgt_epi16(maskedGroupIndices, localMaxGroupIndices);

            // andnot is (~a & b) so clearRunningBits needs to come first as
            // it's what we intend to negate
            localOverlapBits =
                _mm_andnot_si128(clearRunningBits, localOverlapBits);

            // Keep any bits from the current group where the running index is
            // not closer (i.e. where current is not covered).
            // Note: this will additionally keep bits where there has not yet
            // been an intersection (index is 0), and the current rectangle was
            // not intersected. This is fine - these bits will get cleared by
            // the above code when a rectangle intersection finally *does*
            // happen, so we can save on an additional mask with isectMask16.
            auto clearCurrentBits =
                _mm_cmpgt_epi16(localMaxGroupIndices, maskedGroupIndices);
            auto maskedOverlapBits =
                _mm_andnot_si128(clearCurrentBits, groupOverlapBits[i]);

            // Combine the two sets, ultimately this will add bits from
            // overlapping rectangles that are in the new-highest draw group and
            // clear any bits that are not.
            localOverlapBits =
                _mm_or_si128(localOverlapBits, maskedOverlapBits);
        }

        // Accumulate max intersecting groupIndices.
        localMaxGroupIndices =
            _mm_max_epi16(maskedGroupIndices, localMaxGroupIndices);
    }
    running.maxGroupIndices = math::bit_cast<int16x8>(localMaxGroupIndices);

    if constexpr (Type == GroupingType::overlapAllowed)
    {
        running.overlapBits = math::bit_cast<uint16x8>(localOverlapBits);
    }

#endif // !FALLBACK_ON_SSE2_INTRINSICS

    // Ensure we never drop below our baseline index.
    if constexpr (Type == GroupingType::overlapAllowed)
    {
        if (running.maxGroupIndices[0] < m_baselineGroupIndex)
        {
            // We're bumping this entry up so the overlap bits need to
            // be cleared.
            running.maxGroupIndices[0] = m_baselineGroupIndex;
            running.overlapBits[0] = m_baselineOverlapBits;
        }
        else if (running.maxGroupIndices[0] == m_baselineGroupIndex)
        {
            running.overlapBits[0] |= m_baselineOverlapBits;
        }
    }
    else
    {
        running.maxGroupIndices[0] =
            std::max(running.maxGroupIndices[0], m_baselineGroupIndex);
    }
    return running;
}

void IntersectionBoard::resizeAndReset(uint32_t viewportWidth,
                                       uint32_t viewportHeight)
{
    m_viewportSize =
        int2{static_cast<int>(viewportWidth), static_cast<int>(viewportHeight)};

    // Divide the board into TILE_DIM x TILE_DIM tiles.
    int2 dims = (m_viewportSize + TILE_DIM - 1) / TILE_DIM;
    m_cols = dims.x;
    m_rows = dims.y;
    if (m_tiles.size() < m_cols * m_rows)
    {
        m_tiles.resize(m_cols * m_rows);
    }
    auto tileIter = m_tiles.begin();
    for (int y = 0; y < m_rows; ++y)
    {
        for (int x = 0; x < m_cols; ++x)
        {
            tileIter->reset(x * TILE_DIM, y * TILE_DIM);
            ++tileIter;
        }
    }
}

int16_t IntersectionBoard::addRectangle(int4 ltrb,
                                        uint16_t currentRectangleOverlapBits,
                                        uint16_t disallowOverlapMask,
                                        int16_t layerCount)
{
    switch (m_groupingType)
    {
        case GroupingType::overlapAllowed:
            return addRectangle<GroupingType::overlapAllowed>(
                ltrb,
                currentRectangleOverlapBits,
                disallowOverlapMask,
                layerCount);
        case GroupingType::disjoint:
            return addRectangle<GroupingType::disjoint>(
                ltrb,
                currentRectangleOverlapBits,
                disallowOverlapMask,
                layerCount);
    }

    RIVE_UNREACHABLE();
}

template <GroupingType Type>
int16_t IntersectionBoard::addRectangle(int4 ltrb,
                                        uint16_t currentRectangleOverlapBits,
                                        uint16_t disallowedOverlapBitsMask,
                                        int16_t layerCount)
{
    if constexpr (Type == GroupingType::overlapAllowed)
    {
        assert(
            layerCount == 1 &&
            "rectangles that are allowed to overlap should only be a single layer");
    }

    // Discard empty, negative, or offscreen rectangles.
    if (simd::any(ltrb.xy >= m_viewportSize || ltrb.zw <= 0 ||
                  ltrb.xy >= ltrb.zw))
    {
        return 0;
    }

    // Clamp ltrb to the viewport to avoid integer overflows.
    ltrb.xy = simd::max(ltrb.xy, int2(0));
    ltrb.zw = simd::min(ltrb.zw, m_viewportSize);

    // Find the tiled row and column that each corner of the rectangle falls on.
    int4 span = (ltrb - int4{0, 0, 1, 1}) / TILE_DIM;
    span = simd::clamp(span, int4(0), int4{m_cols, m_rows, m_cols, m_rows} - 1);
    assert(simd::all(span.xy <= span.zw));

    // Accumulate the max groupIndex from each tile the rectangle touches.
    IntersectionTile::FindResult results;
    for (int y = span.y; y <= span.w; ++y)
    {
        auto tileIter = m_tiles.begin() + y * m_cols + span.x;
        for (int x = span.x; x <= span.z; ++x)
        {
            results =
                tileIter->findMaxIntersectingGroupIndex<Type>(ltrb, results);
            ++tileIter;
        }
    }

    // Find the absolute max group index this rectangle intersects with.
    int16_t bottomGroupIndex = simd::reduce_max(results.maxGroupIndices);
    // It is the caller's responsibility to not insert more rectangles than can
    // fit in a signed 16-bit integer.
    assert(bottomGroupIndex <=
           std::numeric_limits<int16_t>::max() - layerCount);

    if constexpr (Type == GroupingType::overlapAllowed)
    {
        // Clear bits of anything that wasn't in our max draw group, they don't
        // matter (there's already a barrier between them)
        auto overlapMask = (results.maxGroupIndices == bottomGroupIndex);
        results.overlapBits &= overlapMask;

        // Now doing this reduce will give just the bits related to things we
        // overlapped.
        int16_t allOverlapBits = simd::reduce_or(results.overlapBits);
        if ((allOverlapBits & disallowedOverlapBitsMask) != 0)
        {
            // Bits were set in any overlapping rectangle that prevent an
            // overlap here, so we cannot stay in the same group.
            bottomGroupIndex++;
        }
        else
        {
            bottomGroupIndex = std::max(bottomGroupIndex, int16_t(1));
        }
    }
    else
    {
        // With no overlapping allowed, always start in the next group up from
        // the lowest one we intersected (or 1, if no intersection occurred)
        bottomGroupIndex++;
    }

    // Add the rectangle and its newly-found groupIndex to each tile it touches.
    int16_t topGroupIndex = bottomGroupIndex + layerCount - 1;
    for (int y = span.y; y <= span.w; ++y)
    {
        auto tileIter = m_tiles.begin() + y * m_cols + span.x;
        for (int x = span.x; x <= span.z; ++x)
        {
            tileIter->addRectangle<Type>(ltrb,
                                         topGroupIndex,
                                         currentRectangleOverlapBits);
            ++tileIter;
        }
    }

    return bottomGroupIndex;
}

// Explicitly instantiate the public template methods to ensure they get linked

template IntersectionTile::FindResult IntersectionTile::
    findMaxIntersectingGroupIndex<GroupingType::disjoint>(
        int4 ltrb,
        FindResult running) const;
template IntersectionTile::FindResult IntersectionTile::
    findMaxIntersectingGroupIndex<GroupingType::overlapAllowed>(
        int4 ltrb,
        FindResult running) const;

template void IntersectionTile::addRectangle<GroupingType::disjoint>(
    int4 ltrb,
    int16_t groupIndex,
    uint16_t overlapBits);
template void IntersectionTile::addRectangle<GroupingType::overlapAllowed>(
    int4 ltrb,
    int16_t groupIndex,
    uint16_t overlapBits);

#ifdef WITH_RIVE_TOOLS
template void IntersectionTile::testingOnly_addRectangleAndValidate<
    GroupingType::disjoint>(int4 ltrb,
                            int16_t groupIndex,
                            uint16_t overlapBits);
template void IntersectionTile::testingOnly_addRectangleAndValidate<
    GroupingType::overlapAllowed>(int4 ltrb,
                                  int16_t groupIndex,
                                  uint16_t overlapBits);
#endif
} // namespace rive::gpu