path: root/src/core/SkLinearBitmapPipeline_tile.h

/*
 * Copyright 2016 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#ifndef SkLinearBitmapPipeline_tile_DEFINED
#define SkLinearBitmapPipeline_tile_DEFINED

#include "SkLinearBitmapPipeline_core.h"
#include "SkPM4f.h"
#include <algorithm>
#include <cmath>
#include <limits>

namespace {

void assertTiled(const Sk4s& vs, SkScalar vMax) {
    SkASSERT(0 <= vs[0] && vs[0] < vMax);
    SkASSERT(0 <= vs[1] && vs[1] < vMax);
    SkASSERT(0 <= vs[2] && vs[2] < vMax);
    SkASSERT(0 <= vs[3] && vs[3] < vMax);
}

/*
 * Clamp in the X direction.
 * Observations:
 *   * sample pointer border - if the sample point is <= 0.5 or >= Max - 0.5 then the pixel
 *     value should be a border color. For this case, create the span using clampToSinglePixel.
 */
class XClampStrategy {
public:
    XClampStrategy(int32_t max)
        : fXMaxPixel{SkScalar(max - SK_ScalarHalf)}
        , fXMax{SkScalar(max)} { }

    void tileXPoints(Sk4s* xs) {
        *xs = Sk4s::Min(Sk4s::Max(*xs, SK_ScalarHalf), fXMaxPixel);
        assertTiled(*xs, fXMax);
    }

    template<typename Next>
    bool maybeProcessSpan(Span originalSpan, Next* next) {
        SkASSERT(!originalSpan.isEmpty());
        SkPoint start; SkScalar length; int count;
        std::tie(start, length, count) = originalSpan;
        SkScalar x = X(start);
        SkScalar y = Y(start);
        Span span{{x, y}, length, count};

        if (span.completelyWithin(0.0f, fXMax)) {
            next->pointSpan(span);
            return true;
        }
        if (1 == count || 0.0f == length) {
            return false;
        }

        SkScalar dx = length / (count - 1);

        //    A                 B     C
        // +-------+-------+-------++-------+-------+-------+     +-------+-------++------
        // |  *---*|---*---|*---*--||-*---*-|---*---|*---...|     |--*---*|---*---||*---*....
        // |       |       |       ||       |       |       | ... |       |       ||
        // |       |       |       ||       |       |       |     |       |       ||
        // +-------+-------+-------++-------+-------+-------+     +-------+-------++------
        //                         ^                                              ^
        //                         | xMin                                  xMax-1 | xMax
        //
        //     *---*---*---... - track of samples. * = sample
        //
        //     +-+                                 ||
        //     | |  - pixels in source space.      || - tile border.
        //     +-+                                 ||
        //
        // The length from A to B is the length in source space or 4 * dx or (count - 1) * dx
        // where dx is the distance between samples. There are 5 destination pixels
        // corresponding to 5 samples specified in the A, B span. The distance from A to the next
        // span starting at C is 5 * dx, so count * dx.
        // Remember, count is the number of pixels needed for the destination and the number of
        // samples.
        // Overall Strategy:
        // * Under - for portions of the span < xMin, take the color at pixel {xMin, y} and use it
        //   to fill in the 5 pixel sampled from A to B.
        // * Middle - for the portion of the span between xMin and xMax sample normally.
        // * Over - for the portion of the span > xMax, take the color at pixel {xMax-1, y} and
        //   use it to fill in the rest of the destination pixels.
        if (dx >= 0) {
            Span leftClamped = span.breakAt(SK_ScalarHalf, dx);
            if (!leftClamped.isEmpty()) {
                leftClamped.clampToSinglePixel({SK_ScalarHalf, y});
                next->pointSpan(leftClamped);
            }
            Span center = span.breakAt(fXMax, dx);
            if (!center.isEmpty()) {
                next->pointSpan(center);
            }
            if (!span.isEmpty()) {
                span.clampToSinglePixel({fXMaxPixel, y});
                next->pointSpan(span);
            }
        } else {
            Span rightClamped = span.breakAt(fXMax, dx);
            if (!rightClamped.isEmpty()) {
                rightClamped.clampToSinglePixel({fXMaxPixel, y});
                next->pointSpan(rightClamped);
            }
            Span center = span.breakAt(SK_ScalarHalf, dx);
            if (!center.isEmpty()) {
                next->pointSpan(center);
            }
            if (!span.isEmpty()) {
                span.clampToSinglePixel({SK_ScalarHalf, y});
                next->pointSpan(span);
            }
        }
        return true;
    }

private:
    const SkScalar fXMaxPixel;
    const SkScalar fXMax;
};

class YClampStrategy {
public:
    YClampStrategy(int32_t max)
        : fYMaxPixel{SkScalar(max) - SK_ScalarHalf} { }

    void tileYPoints(Sk4s* ys) {
        *ys = Sk4s::Min(Sk4s::Max(*ys, SK_ScalarHalf), fYMaxPixel);
        assertTiled(*ys, fYMaxPixel + SK_ScalarHalf);
    }

    SkScalar tileY(SkScalar y) {
        Sk4f ys{y};
        tileYPoints(&ys);
        return ys[0];
    }

private:
    const SkScalar fYMaxPixel;
};

SkScalar tile_mod(SkScalar x, SkScalar base, SkScalar cap) {
    // When x is a negative number *very* close to zero, the difference becomes 0 - (-base) = base
    // which is an out of bound value. The min() corrects these problematic values.
    return std::min(x - SkScalarFloorToScalar(x / base) * base, cap);
}

class XRepeatStrategy {
public:
    XRepeatStrategy(int32_t max)
        : fXMax{SkScalar(max)}
        , fXCap{SkScalar(nextafterf(SkScalar(max), 0.0f))}
        , fXInvMax{1.0f / SkScalar(max)} { }

    void tileXPoints(Sk4s* xs) {
        Sk4s divX = *xs * fXInvMax;
        Sk4s modX = *xs - divX.floor() * fXMax;
        *xs = Sk4s::Min(fXCap, modX);
        assertTiled(*xs, fXMax);
    }

    template<typename Next>
    bool maybeProcessSpan(Span originalSpan, Next* next) {
        SkASSERT(!originalSpan.isEmpty());
        SkPoint start; SkScalar length; int count;
        std::tie(start, length, count) = originalSpan;
        // Make x and y in range on the tile.
        SkScalar x = tile_mod(X(start), fXMax, fXCap);
        SkScalar y = Y(start);
        SkScalar dx = length / (count - 1);

        // No need trying to go fast because the steps are larger than a tile or there is one point.
        if (SkScalarAbs(dx) >= fXMax || count <= 1) {
            return false;
        }

        //             A        B     C                  D                Z
        // +-------+-------+-------++-------+-------+-------++     +-------+-------++------
        // |       |   *---|*---*--||-*---*-|---*---|*---*--||     |--*---*|       ||
        // |       |       |       ||       |       |       || ... |       |       ||
        // |       |       |       ||       |       |       ||     |       |       ||
        // +-------+-------+-------++-------+-------+-------++     +-------+-------++------
        //                         ^^                       ^^                     ^^
        //                    xMax || xMin             xMax || xMin           xMax || xMin
        //
        //     *---*---*---... - track of samples. * = sample
        //
        //     +-+                                 ||
        //     | |  - pixels in source space.      || - tile border.
        //     +-+                                 ||
        //
        //
        // The given span starts at A and continues on through several tiles to sample point Z.
        // The idea is to break this into several spans one on each tile the entire span
        // intersects. The A to B span only covers a partial tile and has a count of 3 and the
        // distance from A to B is (count - 1) * dx or 2 * dx. The distance from A to the start of
        // the next span is count * dx or 3 * dx. Span C to D covers an entire tile has a count
        // of 5 and a length of 4 * dx. Remember, count is the number of pixels needed for the
        // destination and the number of samples.
        //
        // Overall Strategy:
        // While the span hangs over the edge of the tile, draw the span covering the tile then
        // slide the span over to the next tile.

        // The guard could have been count > 0, but then a bunch of math would be done in the
        // common case.

        Span span({x, y}, length, count);
        if (dx > 0) {
            while (!span.isEmpty() && span.endX() >= fXMax) {
                Span toDraw = span.breakAt(fXMax, dx);
                next->pointSpan(toDraw);
                span.offset(-fXMax);
            }
        } else {
            while (!span.isEmpty() && span.endX() < 0.0f) {
                Span toDraw = span.breakAt(0.0f, dx);
                next->pointSpan(toDraw);
                span.offset(fXMax);
            }
        }

        // All on a single tile.
        if (!span.isEmpty()) {
            next->pointSpan(span);
        }

        return true;
    }

private:
    const SkScalar fXMax;
    const SkScalar fXCap;
    const SkScalar fXInvMax;
};

// The XRepeatUnitScaleStrategy exploits the situation where dx = 1.0. The main advantage is that
// the relationship between the sample points and the source pixels does not change from tile to
// repeated tile. This allows the tiler to calculate the span once and re-use it for each
// repeated tile. This is later exploited by some samplers to avoid converting pixels to linear
// space allowing the use of memmove to place pixel in the destination.
class XRepeatUnitScaleStrategy {
public:
    XRepeatUnitScaleStrategy(int32_t max)
        : fXMax{SkScalar(max)}
        , fXCap{SkScalar(nextafterf(SkScalar(max), 0.0f))}
        , fXInvMax{1.0f / SkScalar(max)} { }

    void tileXPoints(Sk4s* xs) {
        Sk4s divX = *xs * fXInvMax;
        Sk4s modX = *xs - divX.floor() * fXMax;
        *xs = Sk4s::Min(fXCap, modX);
        assertTiled(*xs, fXMax);
    }

    template<typename Next>
    bool maybeProcessSpan(Span originalSpan, Next* next) {
        SkASSERT(!originalSpan.isEmpty());
        SkPoint start; SkScalar length; int count;
        std::tie(start, length, count) = originalSpan;
        // Make x and y in range on the tile.
        SkScalar x = tile_mod(X(start), fXMax, fXCap);
        SkScalar y = Y(start);

        // No need trying to go fast because the steps are larger than a tile or there is one point.
        if (fXMax == 1 || count <= 1) {
            return false;
        }

        // x should be on the tile.
        SkASSERT(0.0f <= x && x < fXMax);
        Span span({x, y}, length, count);

        if (SkScalarFloorToScalar(x) != 0.0f) {
            Span toDraw = span.breakAt(fXMax, 1.0f);
            SkASSERT(0.0f <= toDraw.startX() && toDraw.endX() < fXMax);
            next->pointSpan(toDraw);
            span.offset(-fXMax);
        }

        // All of the span could have been on the first tile. If so, then no work to do.
        if (span.isEmpty()) return true;

        // At this point the span should be aligned to zero.
        SkASSERT(SkScalarFloorToScalar(span.startX()) == 0.0f);

        // Note: The span length has an unintuitive relation to the tile width. The tile width is
        // a half open interval [tb, te), but the span is a closed interval [sb, se]. In order to
        // compare the two, you need to convert the span to a half open interval. This is done by
        // adding dx to se. So, the span becomes: [sb, se + dx). Hence the + 1.0f below.
        SkScalar div = (span.length() + 1.0f) / fXMax;
        int32_t repeatCount = SkScalarFloorToInt(div);
        Span repeatableSpan{{0.0f, y}, fXMax - 1.0f, SkScalarFloorToInt(fXMax)};

        // Repeat the center section.
        SkASSERT(0.0f <= repeatableSpan.startX() && repeatableSpan.endX() < fXMax);
        if (repeatCount > 0) {
            next->repeatSpan(repeatableSpan, repeatCount);
        }

        // Calculate the advance past the center portion.
        SkScalar advance = SkScalar(repeatCount) * fXMax;

        // There may be some of the span left over.
        span.breakAt(advance, 1.0f);

        // All on a single tile.
        if (!span.isEmpty()) {
            span.offset(-advance);
            SkASSERT(0.0f <= span.startX() && span.endX() < fXMax);
            next->pointSpan(span);
        }

        return true;
    }

private:
    const SkScalar fXMax;
    const SkScalar fXCap;
    const SkScalar fXInvMax;
};

class YRepeatStrategy {
public:
    YRepeatStrategy(int32_t max)
        : fYMax{SkScalar(max)}
        , fYCap{SkScalar(nextafterf(SkScalar(max), 0.0f))}
        , fYsInvMax{1.0f / SkScalar(max)} { }

    void tileYPoints(Sk4s* ys) {
        Sk4s divY = *ys * fYsInvMax;
        Sk4s modY = *ys - divY.floor() * fYMax;
        *ys = Sk4s::Min(fYCap, modY);
        assertTiled(*ys, fYMax);
    }

    SkScalar tileY(SkScalar y) {
        SkScalar answer = tile_mod(y, fYMax, fYCap);
        SkASSERT(0 <= answer && answer < fYMax);
        return answer;
    }

private:
    const SkScalar fYMax;
    const SkScalar fYCap;
    const SkScalar fYsInvMax;
};
// max = 40
// mq2[x_] := Abs[(x - 40) - Floor[(x - 40)/80] * 80 - 40]
class XMirrorStrategy {
public:
    XMirrorStrategy(int32_t max)
        : fXMax{SkScalar(max)}
        , fXCap{SkScalar(nextafterf(SkScalar(max), 0.0f))}
        , fXDoubleInvMax{1.0f / (2.0f * SkScalar(max))} { }

    void tileXPoints(Sk4s* xs) {
        Sk4f bias   = *xs - fXMax;
        Sk4f div    = bias * fXDoubleInvMax;
        Sk4f mod    = bias - div.floor() * 2.0f * fXMax;
        Sk4f unbias = mod - fXMax;
        *xs = Sk4f::Min(unbias.abs(), fXCap);
        assertTiled(*xs, fXMax);
    }

    template <typename Next>
    bool maybeProcessSpan(Span originalSpan, Next* next) { return false; }

private:
    SkScalar fXMax;
    SkScalar fXCap;
    SkScalar fXDoubleInvMax;
};

class YMirrorStrategy {
public:
    YMirrorStrategy(int32_t max)
        : fYMax{SkScalar(max)}
        , fYCap{nextafterf(SkScalar(max), 0.0f)}
        , fYDoubleInvMax{1.0f / (2.0f * SkScalar(max))} { }

    void tileYPoints(Sk4s* ys) {
        Sk4f bias   = *ys - fYMax;
        Sk4f div    = bias * fYDoubleInvMax;
        Sk4f mod    = bias - div.floor() * 2.0f * fYMax;
        Sk4f unbias = mod - fYMax;
        *ys = Sk4f::Min(unbias.abs(), fYCap);
        assertTiled(*ys, fYMax);
    }

    SkScalar tileY(SkScalar y) {
        SkScalar bias   = y - fYMax;
        SkScalar div    = bias * fYDoubleInvMax;
        SkScalar mod    = bias - SkScalarFloorToScalar(div) * 2.0f * fYMax;
        SkScalar unbias = mod - fYMax;
        SkScalar answer = SkMinScalar(SkScalarAbs(unbias), fYCap);
        SkASSERT(0 <= answer && answer < fYMax);
        return answer;
    }

private:
    SkScalar fYMax;
    SkScalar fYCap;
    SkScalar fYDoubleInvMax;
};

}  // namespace
#endif  // SkLinearBitmapPipeline_tile_DEFINED