tile spans

src/core/SkLinearBitmapPipeline.cpp

 /*
  * Copyright 2016 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "SkLinearBitmapPipeline.h"
 #include "SkPM4f.h"
 
@@ skipping 356 matching lines @@
         , fXMax{X(max) - 1.0f}
         , fYMax{Y(max) - 1.0f} { }
 
     void processPoints(Sk4f* xs, Sk4f* ys) {
         *xs = Sk4f::Min(Sk4f::Max(*xs, fXMin), fXMax);
         *ys = Sk4f::Min(Sk4f::Max(*ys, fYMin), fYMax);
     }
 
     template <typename Next>
     bool maybeProcessSpan(SkPoint start, SkScalar length, int count, Next* next) {
-        return false;
+        SkScalar xMin = fXMin[0];

[mtklein, 2016/02/23 15:51:56]

It's occurred to me that we should probably be using Sk4s for coordinate-y
values, not Sk4f.

[herb_g, 2016/02/23 21:10:23]

Done.

+        SkScalar xMax = fXMax[0];
+        SkScalar yMin = fYMin[0];
+        SkScalar yMax = fYMax[0];
+        SkScalar x = X(start);
+        SkScalar y = std::min(std::max(yMin, start.fY), yMax);

[mtklein, 2016/02/23 15:51:56]

Weird to write X(start) and start.fY...

[herb_g, 2016/02/23 21:10:23]

Done.

+

[mtklein, 2016/02/23 15:51:56]

Some ideas:
   - invert the logic so the easy case comes first and returns early?
   - try SSA style so we don't have to reason about values changing?
   - explain the clever clamp is len = 0 trick?

bool under = xMin > x, 
      over = xMax < x + length;

if (!under && !over) {
    // Our span is fully inside the tile.
    next->pointSpan(...);
    return true;
}

SkASSERT(count > 0);
SkScalar dx = length / (count-1);

int before = 0;
SkScalar xMid = x;
if (under) {
   before = SkScalarFloorToInt((xMin - x) / dx) + 1;
   xMid = xMin;
}

int after = 0;
if (over) {
   after = SkScalarFloorToInt((x + length - xMax) / dx) + 1;
}

int middle = count - before - after;
SkScalar lenMid = length - (before+after)*dx;
...
// spanning with 0 length effects the clamp on either side... we'll step in
source space by 0 between each pixel.
SendSpan({xMin  ,y},      0, before);  
SendSpan({xMid  ,y}, lenMid, middle);
SendSpan({xMax-1,y},      0, after);    // explain the -1?

[herb_g, 2016/02/23 21:10:23]

I did this a totally different way. Please re-review. 

+        int beforeCount = 0;
+        int middleCount = count;
+        int afterCount = 0;
+        if (x < xMin || x + length > xMax) {
+            SkScalar dx = length / (count - 1);

[f(malita), 2016/02/23 20:53:48]

'count' is the span/pixel count, right - why (count - 1)?

[f(malita), 2016/02/23 21:04:08]

A more general comment re. dx and dst->src mapping via dx multiplication: is
this perspective-proof?

I do the exact same thing for gradients, and I'm pretty sure it assumes a
kLinear_MatrixClass - so I don't have much hope there.  Just curious whether you
have extra machinery that would make it work for bitmap shaders or just don't
care about persp.

+
+            if (x < xMin) {
+                SkScalar overLength = xMin - x;
+                beforeCount = SkScalarFloorToInt(overLength / dx) + 1;
+                middleCount -= beforeCount;
+                length = length - dx * beforeCount;
+                x = xMin;
+            }
+
+            if (x + length > xMax) {
+                SkScalar overLength = (x + length) - xMax;
+                afterCount = SkScalarFloorToInt(overLength / dx) + 1;
+                middleCount -= afterCount;
+                length = length - dx * afterCount;
+            }
+            auto SendSpan = [&](SkPoint start, SkScalar length, int count) {

[f(malita), 2016/02/23 20:53:48]

Looks like we only need to capture 'next' here.

[herb_g, 2016/02/23 21:30:35]

This is gone. I made Span handle count == 1.

+                if (count > 0) {
+                    if (count == 1) {
+                        next->pointListFew(1, Sk4f{X(start)}, Sk4f{Y(start)});

[mtklein, 2016/02/23 15:51:56]

Why can't pointSpan handle count == 1?

[herb_g, 2016/02/23 21:30:35]

There was a NaN problem with the division in a deeper part of the stack. I fixed
that, and count == 1 works now.

+                    } else {
+                        next->pointSpan(start, length, count);
+                    }
+                }
+            };
+            SendSpan(SkPoint{xMin, y}, 0.0f, beforeCount);
+            SendSpan(SkPoint{x, y}, length, middleCount);
+            SendSpan(SkPoint{xMax - 1, y}, 0.0f, afterCount);
+        } else {
+            next->pointSpan(start, length, count);
+        }
+
+        return true;
     }
 
 private:
     const Sk4f fXMin{SK_FloatNegativeInfinity};
     const Sk4f fYMin{SK_FloatNegativeInfinity};
     const Sk4f fXMax{SK_FloatInfinity};
     const Sk4f fYMax{SK_FloatInfinity};
 };
 template <typename Next = SkLinearBitmapPipeline::BilerpProcessorInterface>
 using Clamp = BilerpProcessor<ClampStrategy, Next>;
 
+// It would be nice to use fmod, but it uses trunc based rounding where floor rounding is needed.
+static float tile_mod(float l, float base) {

[mtklein, 2016/02/23 15:51:56]

I think you might want to pick a different letter---or a longer name---than l. 
It looks surprisingly similar to 1 here.

[herb_g, 2016/02/23 21:10:23]

Done.

+    return l - std::floor(l / base) * base;

[mtklein, 2016/02/23 15:51:56]

We're getting a little loosey-goosey about SkScalar and float here.
Shouldn't these arguments be SkScalar?

[herb_g, 2016/02/23 21:10:23]

Done.

+}
+
 class RepeatStrategy {
 public:
     RepeatStrategy(X max) : fXMax{max}, fXInvMax{1.0f/max} { }
     RepeatStrategy(Y max) : fYMax{max}, fYInvMax{1.0f/max} { }
     RepeatStrategy(SkSize max)
         : fXMax{X(max)}
         , fXInvMax{1.0f / X(max)}
         , fYMax{Y(max)}
         , fYInvMax{1.0f / Y(max)} { }
 
     void processPoints(Sk4f* xs, Sk4f* ys) {
         Sk4f divX = (*xs * fXInvMax).floor();
         Sk4f divY = (*ys * fYInvMax).floor();
         Sk4f baseX = (divX * fXMax);
         Sk4f baseY = (divY * fYMax);
         *xs = *xs - baseX;
         *ys = *ys - baseY;
     }
 
     template <typename Next>
     bool maybeProcessSpan(SkPoint start, SkScalar length, int count, Next* next) {
-        return false;
+        SkScalar x = tile_mod(X(start), fXMax[0]);
+        SkScalar y = tile_mod(Y(start), fYMax[0]);
+        SkScalar dx = length / (count - 1);

[f(malita), 2016/02/23 20:53:48]

Same question re count - 1.

[herb_g, 2016/02/23 21:30:35]

Added much documentation. See if that answers the question.

+        auto SendSpan = [&](SkPoint start, SkScalar length, int count) {
+            if (count > 0) {
+                if (count == 1) {
+                    next->pointListFew(1, Sk4f{X(start)}, Sk4f{Y(start)});
+                } else {
+                    next->pointSpan(start, length, count);
+                }
+            }
+        };
+        while (x + length > fXMax[0]) {

[mtklein, 2016/02/23 15:51:56]

Explain how this works?

[herb_g, 2016/02/23 21:10:23]

Done.

+            SkScalar lengthForTile = std::min(fXMax[0] - x, length);
+            int countForTile = SkScalarFloorToInt(lengthForTile / dx);

[f(malita), 2016/02/23 20:53:48]

I noticed we always pad one to the count in the clamp case, while here we let it
floor to zero.  Are we guaranteed to make progress in that case?  I'm guessing
in general we are, since we wrap x back to 0 so the next iteration will pick up
a full tile.

Still makes me a bit nervous - what if the image is 1px wide?

[herb_g, 2016/02/23 21:30:35]

If the source is 1 pixel wide, then this should make progress because of the
calculation to the start of the next pixel. Please see new documentation and see
if it answers the problem.

+            SkScalar lengthForDx = countForTile * dx;
+            SendSpan({x, y}, lengthForDx, countForTile);
+            length -= lengthForDx;
+            count -= countForTile;

[f(malita), 2016/02/23 20:53:48]

Looks like we only track count in order to handle the leftover outside the loop.
Can we fold that in?  Maybe something along these lines:

  while (length > 0) {
      SkScalar lengthForTile = std::min(fXMax[0] - x, length);
      int countForTile = SkScalarFloorToInt(lengthForTile / dx);
      SkScalar lengthForDx = countForTile * dx;
      SendSpan({x, y}, lengthForDx, countForTile);
      length -= lengthForDx;
      x = 0;
  }
      
    

[herb_g, 2016/02/23 21:30:35]

That would mean a bunch of calculation in the common case.

+            x = 0;
+        }
+        SendSpan({x, y}, length, count);
+
+        return true;
     }
 
 private:
     const Sk4f fXMax{0.0f};
     const Sk4f fXInvMax{0.0f};
     const Sk4f fYMax{0.0f};
     const Sk4f fYInvMax{0.0f};
 };
 
 template <typename Next = SkLinearBitmapPipeline::BilerpProcessorInterface>
@@ skipping 280 matching lines @@
     if (count == 1) {
         fFirstStage->pointListFew(1, Sk4f{x + 0.5f}, Sk4f{y + 0.5f});
     } else {
         // The count and length arguments start out in a precise relation in order to keep the
         // math correct through the different stages. Count is the number of pixel to produce.
         // Since the code samples at pixel centers, length is the distance from the center of the
         // first pixel to the center of the last pixel. This implies that length is count-1.
         fFirstStage->pointSpan(SkPoint{x + 0.5f, y + 0.5f}, count - 1, count);
     }
 }