src/core/SkTileGrid.cpp

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

#include "SkTileGrid.h"
#include "Sk4x.h"

SkTileGrid::SkTileGrid(int xTiles, int yTiles, const SkTileGridFactory::TileGridInfo& info)
    : fXTiles(xTiles)
    , fNumTiles(xTiles * yTiles)
    , fGridBounds(SkRect::MakeWH(xTiles * info.fTileInterval.width(),
                                 yTiles * info.fTileInterval.height()))
    , fMargin(-info.fMargin.fWidth  - 1,  // Outset margin by 1 as a provision for AA and to
              -info.fMargin.fHeight - 1,  // cancel the outset applied by getClipDeviceBounds().
              +info.fMargin.fWidth  + 1,
              +info.fMargin.fHeight + 1)
    , fOffset(info.fOffset.fX,
              info.fOffset.fY,
              info.fOffset.fX - SK_ScalarNearlyZero,  // We scrunch user-provided bounds in a little
              info.fOffset.fY - SK_ScalarNearlyZero)  // to make right and bottom edges exclusive.
    , fUserToGrid(SkScalarInvert(info.fTileInterval.width()),
                  SkScalarInvert(info.fTileInterval.height()),
                  SkScalarInvert(info.fTileInterval.width()),
                  SkScalarInvert(info.fTileInterval.height()))
    , fGridHigh(fXTiles - 1, yTiles - 1, fXTiles - 1, yTiles - 1)
    , fTiles(SkNEW_ARRAY(SkTDArray<unsigned>, fNumTiles)) {}

SkTileGrid::~SkTileGrid() {
    SkDELETE_ARRAY(fTiles);
}

void SkTileGrid::reserve(unsigned opCount) {
    if (fNumTiles == 0) {
        return;  // A tileless tile grid is nonsensical, but happens in at least cc_unittests.
    }

    // If we assume every op we're about to try to insert() falls within our grid bounds,
    // then every op has to hit at least one tile.  In fact, a quick scan over our small
    // SKP set shows that in the average SKP, each op hits two 256x256 tiles.

    // If we take those observations and further assume the ops are distributed evenly
    // across the picture, we get this guess for number of ops per tile:
    const int opsPerTileGuess = (2 * opCount) / fNumTiles;

    for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + fNumTiles; tile++) {
        tile->setReserve(opsPerTileGuess);
    }

    // In practice, this heuristic means we'll temporarily allocate about 30% more bytes
    // than if we made no setReserve() calls, but time spent in insert() drops by about 50%.
}

void SkTileGrid::flushDeferredInserts() {
    for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + fNumTiles; tile++) {
        tile->shrinkToFit();
    }
}

// Convert user-space bounds to grid tiles they cover (LT+RB both inclusive).
// Out of bounds queries are clamped to the single nearest tile.
void SkTileGrid::userToGrid(const Sk4f& user, SkIRect* out) const {
    // Map from user coordinates to grid tile coordinates.
    Sk4f grid = user.multiply(fUserToGrid);

    // Now that we're in grid coordinates, clamp to the grid bounds.
    grid = Sk4f::Max(grid, Sk4f(0,0,0,0));
    grid = Sk4f::Min(grid, fGridHigh);

    // Truncate to integers.
    grid.cast<Sk4i>().store(&out->fLeft);
}

// If the rect is inverted, sort it.
static Sk4f sorted(const Sk4f& ltrb) {
    // To sort:
    //   left, right = minmax(left, right)
    //   top, bottom = minmax(top, bottom)
    Sk4f rblt = ltrb.zwxy(),
         ltlt = Sk4f::Min(ltrb, rblt),  // Holds (2 copies of) new left and top.
         rbrb = Sk4f::Max(ltrb, rblt),  // Holds (2 copies of) new right and bottom.
         sort = Sk4f::XYAB(ltlt, rbrb);
    return sort;
}

// Does this rect intersect the grid?
bool SkTileGrid::intersectsGrid(const Sk4f& ltrb) const {
    SkRect bounds;
    ltrb.store(&bounds.fLeft);
    return SkRect::Intersects(bounds, fGridBounds);
    // TODO: If we can get it fast enough, write intersect using Sk4f.
}

void SkTileGrid::insert(unsigned opIndex, const SkRect& originalBounds, bool) {
    Sk4f bounds = Sk4f(&originalBounds.fLeft).add(fMargin).add(fOffset);
    SkASSERT(sorted(bounds).equal(bounds).allTrue());

    // TODO(mtklein): skip this check and just let out-of-bounds rects insert into nearest tile?
    if (!this->intersectsGrid(bounds)) {
        return;
    }

    SkIRect grid;
    this->userToGrid(bounds, &grid);

    // This is just a loop over y then x.  This compiles to a slightly faster and
    // more compact loop than if we just did fTiles[y * fXTiles + x].push(opIndex).
    SkTDArray<unsigned>* row = &fTiles[grid.fTop * fXTiles + grid.fLeft];
    for (int y = 0; y <= grid.fBottom - grid.fTop; y++) {
        SkTDArray<unsigned>* tile = row;
        for (int x = 0; x <= grid.fRight - grid.fLeft; x++) {
            (tile++)->push(opIndex);
        }
        row += fXTiles;
    }
}

// Number of tiles for which data is allocated on the stack in
// SkTileGrid::search. If malloc becomes a bottleneck, we may consider
// increasing this number. Typical large web page, say 2k x 16k, would
// require 512 tiles of size 256 x 256 pixels.
static const int kStackAllocationTileCount = 1024;

void SkTileGrid::search(const SkRect& originalQuery, SkTDArray<unsigned>* results) const {
    // The .subtract(fMargin) counteracts the .add(fMargin) applied in insert(),
    // which optimizes for lookups of size tileInterval + 2 * margin (aligned with the tile grid).
    // That .subtract(fMargin) may have inverted the rect, so we sort it.
    Sk4f query = sorted(Sk4f(&originalQuery.fLeft).subtract(fMargin).add(fOffset));

    SkIRect grid;
    this->userToGrid(query, &grid);

    const int tilesHit = (grid.fRight - grid.fLeft + 1) * (grid.fBottom - grid.fTop + 1);
    SkASSERT(tilesHit > 0);

    if (tilesHit == 1) {
        // A performance shortcut.  The merging code below would work fine here too.
        *results = fTiles[grid.fTop * fXTiles + grid.fLeft];
        return;
    }

    // We've got to merge the data in many tiles into a single sorted and deduplicated stream.
    // We do a simple k-way merge based on the value of opIndex.

    // Gather pointers to the starts and ends of the tiles to merge.
    SkAutoSTArray<kStackAllocationTileCount, const unsigned*> starts(tilesHit), ends(tilesHit);
    int i = 0;
    for (int y = grid.fTop; y <= grid.fBottom; y++) {
        for (int x = grid.fLeft; x <= grid.fRight; x++) {
            starts[i] = fTiles[y * fXTiles + x].begin();
            ends[i]   = fTiles[y * fXTiles + x].end();
            i++;
        }
    }

    // Merge tiles into results until they're fully consumed.
    results->reset();
    while (true) {
        // The tiles themselves are already ordered, so the earliest op is at the front of some
        // tile. It may be at the front of several, even all, tiles.
        unsigned earliest = SK_MaxU32;
        for (int i = 0; i < starts.count(); i++) {
            if (starts[i] < ends[i]) {
                earliest = SkTMin(earliest, *starts[i]);
            }
        }

        // If we didn't find an earliest op, there isn't anything left to merge.
        if (SK_MaxU32 == earliest) {
            return;
        }

        // We did find an earliest op. Output it, and step forward every tile that contains it.
        results->push(earliest);
        for (int i = 0; i < starts.count(); i++) {
            if (starts[i] < ends[i] && *starts[i] == earliest) {
                starts[i]++;
            }
        }
    }
}