gfx/src/TiledRegion.cpp
author Ryan VanderMeulen <ryanvm@gmail.com>
Fri, 01 Sep 2017 15:37:08 -0400
changeset 430269 1d02aa80f2f8c283428f0a8a6310e7d1fec3936c
parent 347861 8e2f62943272dda354db63bfdb42510355dfaa72
child 440921 7aa291217448c40bb4af8b02bf408529e45f61f7
permissions -rw-r--r--
Backed out 9 changesets (bug 1383880) for decision task bustage. Backed out changeset 53f5d47a7cb0 (bug 1383880) Backed out changeset a0abda41172a (bug 1383880) Backed out changeset 729a7e2091e8 (bug 1383880) Backed out changeset a33f5a14a471 (bug 1383880) Backed out changeset 5b10d321cfee (bug 1383880) Backed out changeset 8056488d8aed (bug 1383880) Backed out changeset e62c90e3c1e8 (bug 1383880) Backed out changeset 91f116ce6c2a (bug 1383880) Backed out changeset 045498bc36c4 (bug 1383880)

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "TiledRegion.h"

#include <algorithm>

#include "mozilla/fallible.h"

namespace mozilla {
namespace gfx {

static const int32_t kTileSize = 256;
static const size_t kMaxTiles = 1000;

/**
 * TiledRegionImpl stores an array of non-empty rectangles (pixman_box32_ts) to
 * represent the region. Each rectangle is contained in a single tile;
 * rectangles never cross tile boundaries. The rectangles are sorted by their
 * tile's origin in top-to-bottom, left-to-right order.
 * (Note that this can mean that a rectangle r1 can come before another
 * rectangle r2 even if r2.y1 < r1.y1, as long as the two rects are in the same
 * row of tiles and r1.x1 < r2.x1.)
 * Empty tiles take up no space in the array - there is no rectangle stored for
 * them. As a result, any algorithm that needs to deal with empty tiles will
 * iterate through the mRects array and compare the positions of two
 * consecutive rects to figure out whether there are any empty tiles between
 * them.
 */

static pixman_box32_t
IntersectionOfNonEmptyBoxes(const pixman_box32_t& aBox1,
                            const pixman_box32_t& aBox2)
{
  return pixman_box32_t {
    std::max(aBox1.x1, aBox2.x1),
    std::max(aBox1.y1, aBox2.y1),
    std::min(aBox1.x2, aBox2.x2),
    std::min(aBox1.y2, aBox2.y2)
  };
}

// A TileIterator points to a specific tile inside a certain tile range, or to
// the end of the tile range. Advancing a TileIterator will move to the next
// tile inside the range (or to the range end). The next tile is either the
// tile to the right of the current one, or the first tile of the next tile
// row if the current tile is already the last tile in the row.
class TileIterator {
public:
  TileIterator(const pixman_box32_t& aTileBounds, const IntPoint& aPosition)
    : mTileBounds(aTileBounds)
    , mPos(aPosition)
  {}

  bool operator!=(const TileIterator& aOther) { return mPos != aOther.mPos; }
  bool operator==(const TileIterator& aOther) { return mPos == aOther.mPos; }

  IntPoint operator*() const { return mPos; }

  const TileIterator& operator++() {
    mPos.x += kTileSize;
    if (mPos.x >= mTileBounds.x2) {
      mPos.x = mTileBounds.x1;
      mPos.y += kTileSize;
    }
    return *this;
  }

  TileIterator& operator=(const IntPoint& aPosition)
  {
    mPos = aPosition;
    return *this;
  }

  bool IsBeforeTileContainingPoint(const IntPoint& aPoint) const
  {
    return (mPos.y + kTileSize) <= aPoint.y  ||
      (mPos.y <= aPoint.y && (mPos.x + kTileSize) <= aPoint.x);
  }

  bool IsAtTileContainingPoint(const IntPoint& aPoint) const
  {
    return mPos.y <= aPoint.y && aPoint.y < (mPos.y + kTileSize) &&
           mPos.x <= aPoint.x && aPoint.x < (mPos.x + kTileSize);

  }

  pixman_box32_t IntersectionWith(const pixman_box32_t& aRect) const
  {
    pixman_box32_t tile = { mPos.x, mPos.y,
                            mPos.x + kTileSize, mPos.y + kTileSize };
    return IntersectionOfNonEmptyBoxes(tile, aRect);
  }

private:
  const pixman_box32_t& mTileBounds;
  IntPoint mPos;
};

// A TileRange describes a range of tiles contained inside a certain tile
// bounds (which is a rectangle that includes all tiles that you're
// interested in). The tile range can start and end at any point inside a
// tile row.
// The tile range end is described by the tile that starts at the bottom
// left corner of the tile bounds, i.e. the first tile under the tile
// bounds.
class TileRange {
public:
  // aTileBounds, aStart and aEnd need to be aligned with the tile grid.
  TileRange(const pixman_box32_t& aTileBounds,
            const IntPoint& aStart, const IntPoint& aEnd)
    : mTileBounds(aTileBounds)
    , mStart(aStart)
    , mEnd(aEnd)
  {}
  // aTileBounds needs to be aligned with the tile grid.
  explicit TileRange(const pixman_box32_t& aTileBounds)
    : mTileBounds(aTileBounds)
    , mStart(mTileBounds.x1, mTileBounds.y1)
    , mEnd(mTileBounds.x1, mTileBounds.y2)
  {}

  TileIterator Begin() const { return TileIterator(mTileBounds, mStart); }
  TileIterator End() const { return TileIterator(mTileBounds, mEnd); }

  // The number of tiles in this tile range.
  size_t Length() const
  {
    if (mEnd.y == mStart.y) {
      return (mEnd.x - mStart.x) / kTileSize;
    }
    int64_t numberOfFullRows = (((int64_t)mEnd.y - (int64_t)mStart.y) / kTileSize) - 1;
    int64_t tilesInFirstRow = ((int64_t)mTileBounds.x2 - (int64_t)mStart.x) / kTileSize;
    int64_t tilesInLastRow = ((int64_t)mEnd.x - (int64_t)mTileBounds.x1) / kTileSize;
    int64_t tilesInFullRow = ((int64_t)mTileBounds.x2 - (int64_t)mTileBounds.x1) / kTileSize;
    int64_t total = tilesInFirstRow + (tilesInFullRow * numberOfFullRows) + tilesInLastRow;
    MOZ_ASSERT(total > 0);
    // The total may be larger than what fits in a size_t, so clamp it to
    // SIZE_MAX in that case.
    return ((uint64_t)total > (uint64_t)SIZE_MAX) ? SIZE_MAX : (size_t)total;
  }

  // If aTileOrigin does not describe a tile inside our tile bounds, move it
  // to the next tile that you'd encounter by "advancing" a tile iterator
  // inside these tile bounds. If aTileOrigin is after the last tile inside
  // our tile bounds, move it to the range end tile.
  // The result of this method is a valid end tile for a tile range with our
  // tile bounds.
  IntPoint MoveIntoBounds(const IntPoint& aTileOrigin) const
  {
    IntPoint p = aTileOrigin;
    if (p.x < mTileBounds.x1) {
      p.x = mTileBounds.x1;
    } else if (p.x >= mTileBounds.x2) {
      p.x = mTileBounds.x1;
      p.y += kTileSize;
    }
    if (p.y < mTileBounds.y1) {
      p.y = mTileBounds.y1;
      p.x = mTileBounds.x1;
    } else if (p.y >= mTileBounds.y2) {
      // There's only one valid state after the end of the tile range, and that's
      // the bottom left point of the tile bounds.
      p.x = mTileBounds.x1;
      p.y = mTileBounds.y2;
    }
    return p;
  }

private:
  const pixman_box32_t& mTileBounds;
  const IntPoint mStart;
  const IntPoint mEnd;
};

static IntPoint
TileContainingPoint(const IntPoint& aPoint)
{
  return IntPoint(RoundDownToMultiple(aPoint.x, kTileSize),
                  RoundDownToMultiple(aPoint.y, kTileSize));
}

enum class IterationAction : uint8_t {
  CONTINUE,
  STOP
};

enum class IterationEndReason : uint8_t {
  NOT_STOPPED,
  STOPPED
};

template<
  typename HandleEmptyTilesFunction,
  typename HandleNonEmptyTileFunction,
  typename RectArrayT>
IterationEndReason ProcessIntersectedTiles(const pixman_box32_t& aRect,
                                           RectArrayT& aRectArray,
                                           HandleEmptyTilesFunction aHandleEmptyTiles,
                                           HandleNonEmptyTileFunction aHandleNonEmptyTile)
{
  pixman_box32_t tileBounds = {
    RoundDownToMultiple(aRect.x1, kTileSize),
    RoundDownToMultiple(aRect.y1, kTileSize),
    RoundUpToMultiple(aRect.x2, kTileSize),
    RoundUpToMultiple(aRect.y2, kTileSize)
  };
  if (tileBounds.x2 < tileBounds.x1 || tileBounds.y2 < tileBounds.y1) {
    // RoundUpToMultiple probably overflowed. Bail out.
    return IterationEndReason::STOPPED;
  }

  TileRange tileRange(tileBounds);
  TileIterator rangeEnd = tileRange.End();

  // tileIterator points to the next tile in tileRange, or to rangeEnd if we're
  // done.
  TileIterator tileIterator = tileRange.Begin();

  // We iterate over the rectangle array. Depending on the position of the
  // rectangle we encounter, we may need to advance tileIterator by zero, one,
  // or more tiles:
  //  - Zero if the rectangle we encountered is outside the tiles that
  //    intersect aRect.
  //  - One if the rectangle is in the exact tile that we're interested in next
  //    (i.e. the tile that tileIterator points at).
  //  - More than one if the encountered rectangle is in a tile that's further
  //    to the right or to the bottom than tileIterator. In that case there is
  //    at least one empty tile between the last rectangle we encountered and
  //    the current one.
  for (size_t i = 0; i < aRectArray.Length() && tileIterator != rangeEnd; i++) {
    MOZ_ASSERT(aRectArray[i].x1 < aRectArray[i].x2 && aRectArray[i].y1 < aRectArray[i].y2, "empty rect");
    IntPoint rectOrigin(aRectArray[i].x1, aRectArray[i].y1);
    if (tileIterator.IsBeforeTileContainingPoint(rectOrigin)) {
      IntPoint tileOrigin = TileContainingPoint(rectOrigin);
      IntPoint afterEmptyTiles = tileRange.MoveIntoBounds(tileOrigin);
      TileRange emptyTiles(tileBounds, *tileIterator, afterEmptyTiles);
      if (aHandleEmptyTiles(aRectArray, i, emptyTiles) == IterationAction::STOP) {
        return IterationEndReason::STOPPED;
      }
      tileIterator = afterEmptyTiles;
      if (tileIterator == rangeEnd) {
        return IterationEndReason::NOT_STOPPED;
      }
    }
    if (tileIterator.IsAtTileContainingPoint(rectOrigin)) {
      pixman_box32_t rectIntersection = tileIterator.IntersectionWith(aRect);
      if (aHandleNonEmptyTile(aRectArray, i, rectIntersection) == IterationAction::STOP) {
        return IterationEndReason::STOPPED;
      }
      ++tileIterator;
    }
  }

  if (tileIterator != rangeEnd) {
    // We've looked at all of our existing rectangles but haven't covered all
    // of the tiles that we're interested in yet. So we need to deal with the
    // remaining tiles now.
    size_t endIndex = aRectArray.Length();
    TileRange emptyTiles(tileBounds, *tileIterator, *rangeEnd);
    if (aHandleEmptyTiles(aRectArray, endIndex, emptyTiles) == IterationAction::STOP) {
      return IterationEndReason::STOPPED;
    }
  }
  return IterationEndReason::NOT_STOPPED;
}

static pixman_box32_t
UnionBoundsOfNonEmptyBoxes(const pixman_box32_t& aBox1,
                           const pixman_box32_t& aBox2)
{
  return { std::min(aBox1.x1, aBox2.x1),
           std::min(aBox1.y1, aBox2.y1),
           std::max(aBox1.x2, aBox2.x2),
           std::max(aBox1.y2, aBox2.y2) };
}

// Returns true when adding the rectangle was successful, and false if
// allocation failed.
// When this returns false, our internal state might not be consistent and we
// need to be cleared.
bool
TiledRegionImpl::AddRect(const pixman_box32_t& aRect)
{
  // We are adding a rectangle that can span multiple tiles.
  // For each empty tile that aRect intersects, we need to add the intersection
  // of aRect with that tile to mRects, respecting the order of mRects.
  // For each tile that already has a rectangle, we need to enlarge that
  // existing rectangle to include the intersection of aRect with the tile.
  return ProcessIntersectedTiles(aRect, mRects,
    [&aRect](nsTArray<pixman_box32_t>& rects, size_t& rectIndex, TileRange emptyTiles) {
      CheckedInt<size_t> newLength(rects.Length());
      newLength += emptyTiles.Length();
      if (!newLength.isValid() || newLength.value() >= kMaxTiles ||
          !rects.InsertElementsAt(rectIndex, emptyTiles.Length(), fallible)) {
        return IterationAction::STOP;
      }
      for (TileIterator tileIt = emptyTiles.Begin();
           tileIt != emptyTiles.End();
           ++tileIt, ++rectIndex) {
        rects[rectIndex] = tileIt.IntersectionWith(aRect);
      }
      return IterationAction::CONTINUE;
    },
    [](nsTArray<pixman_box32_t>& rects, size_t rectIndex, const pixman_box32_t& rectIntersectionWithTile) {
      rects[rectIndex] =
        UnionBoundsOfNonEmptyBoxes(rects[rectIndex], rectIntersectionWithTile);
      return IterationAction::CONTINUE;
    }) == IterationEndReason::NOT_STOPPED;
}

static bool
NonEmptyBoxesIntersect(const pixman_box32_t& aBox1, const pixman_box32_t& aBox2)
{
  return aBox1.x1 < aBox2.x2 && aBox2.x1 < aBox1.x2 &&
         aBox1.y1 < aBox2.y2 && aBox2.y1 < aBox1.y2;
}

bool
TiledRegionImpl::Intersects(const pixman_box32_t& aRect) const
{
  // aRect intersects this region if it intersects any of our rectangles.
  return ProcessIntersectedTiles(aRect, mRects,
    [](const nsTArray<pixman_box32_t>& rects, size_t& rectIndex, TileRange emptyTiles) {
      // Ignore empty tiles and keep on iterating.
      return IterationAction::CONTINUE;
    },
    [](const nsTArray<pixman_box32_t>& rects, size_t rectIndex, const pixman_box32_t& rectIntersectionWithTile) {
      if (NonEmptyBoxesIntersect(rects[rectIndex], rectIntersectionWithTile)) {
        // Found an intersecting rectangle, so aRect intersects this region.
        return IterationAction::STOP;
      }
      return IterationAction::CONTINUE;
    }) == IterationEndReason::STOPPED;
}

static bool
NonEmptyBoxContainsNonEmptyBox(const pixman_box32_t& aBox1, const pixman_box32_t& aBox2)
{
  return aBox1.x1 <= aBox2.x1 && aBox2.x2 <= aBox1.x2 &&
         aBox1.y1 <= aBox2.y1 && aBox2.y2 <= aBox1.y2;
}

bool
TiledRegionImpl::Contains(const pixman_box32_t& aRect) const
{
  // aRect is contained in this region if aRect does not intersect any empty
  // tiles and, for each non-empty tile, if the intersection of aRect with that
  // tile is contained in the existing rectangle we have in that tile.
  return ProcessIntersectedTiles(aRect, mRects,
    [](const nsTArray<pixman_box32_t>& rects, size_t& rectIndex, TileRange emptyTiles) {
      // Found an empty tile that intersects aRect, so aRect is not contained
      // in this region.
      return IterationAction::STOP;
    },
    [](const nsTArray<pixman_box32_t>& rects, size_t rectIndex, const pixman_box32_t& rectIntersectionWithTile) {
      if (!NonEmptyBoxContainsNonEmptyBox(rects[rectIndex], rectIntersectionWithTile)) {
        // Our existing rectangle in this tile does not cover the part of aRect that
        // intersects this tile, so aRect is not contained in this region.
        return IterationAction::STOP;
      }
      return IterationAction::CONTINUE;
    }) == IterationEndReason::NOT_STOPPED;
}

} // namespace gfx
} // namespace mozilla