12e2aedc20476964763f09503939a9594e641051arileya@google.com/* 22e2aedc20476964763f09503939a9594e641051arileya@google.com * Copyright 2012 Google Inc. 32e2aedc20476964763f09503939a9594e641051arileya@google.com * 42e2aedc20476964763f09503939a9594e641051arileya@google.com * Use of this source code is governed by a BSD-style license that can be 52e2aedc20476964763f09503939a9594e641051arileya@google.com * found in the LICENSE file. 62e2aedc20476964763f09503939a9594e641051arileya@google.com */ 72e2aedc20476964763f09503939a9594e641051arileya@google.com 82e2aedc20476964763f09503939a9594e641051arileya@google.com#ifndef GrTextureStripAtlas_DEFINED 92e2aedc20476964763f09503939a9594e641051arileya@google.com#define GrTextureStripAtlas_DEFINED 102e2aedc20476964763f09503939a9594e641051arileya@google.com 11744998e666073166307d2522847b2536000a7619bsalomon#include "GrMurmur3HashKey.h" 12a0b40280a49a8a43af7929ead3b3489951c58501commit-bot@chromium.org#include "SkBitmap.h" 132e2aedc20476964763f09503939a9594e641051arileya@google.com#include "SkGr.h" 142e2aedc20476964763f09503939a9594e641051arileya@google.com#include "SkTDArray.h" 153d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips#include "SkTDynamicHash.h" 16a0b40280a49a8a43af7929ead3b3489951c58501commit-bot@chromium.org#include "SkTypes.h" 172e2aedc20476964763f09503939a9594e641051arileya@google.com 182e2aedc20476964763f09503939a9594e641051arileya@google.com/** 19fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com * Maintains a single large texture whose rows store many textures of a small fixed height, 202e2aedc20476964763f09503939a9594e641051arileya@google.com * stored in rows across the x-axis such that we can safely wrap/repeat them horizontally. 212e2aedc20476964763f09503939a9594e641051arileya@google.com */ 222e2aedc20476964763f09503939a9594e641051arileya@google.comclass GrTextureStripAtlas { 232e2aedc20476964763f09503939a9594e641051arileya@google.compublic: 242e2aedc20476964763f09503939a9594e641051arileya@google.com /** 252e2aedc20476964763f09503939a9594e641051arileya@google.com * Descriptor struct which we'll use as a hash table key 262e2aedc20476964763f09503939a9594e641051arileya@google.com **/ 272e2aedc20476964763f09503939a9594e641051arileya@google.com struct Desc { 282e2aedc20476964763f09503939a9594e641051arileya@google.com Desc() { memset(this, 0, sizeof(*this)); } 292e2aedc20476964763f09503939a9594e641051arileya@google.com uint16_t fWidth, fHeight, fRowHeight; 302e2aedc20476964763f09503939a9594e641051arileya@google.com GrPixelConfig fConfig; 312e2aedc20476964763f09503939a9594e641051arileya@google.com GrContext* fContext; 322e2aedc20476964763f09503939a9594e641051arileya@google.com const uint32_t* asKey() const { return reinterpret_cast<const uint32_t*>(this); } 332e2aedc20476964763f09503939a9594e641051arileya@google.com }; 342e2aedc20476964763f09503939a9594e641051arileya@google.com 352e2aedc20476964763f09503939a9594e641051arileya@google.com /** 362e2aedc20476964763f09503939a9594e641051arileya@google.com * Try to find an atlas with the required parameters, creates a new one if necessary 372e2aedc20476964763f09503939a9594e641051arileya@google.com */ 382e2aedc20476964763f09503939a9594e641051arileya@google.com static GrTextureStripAtlas* GetAtlas(const Desc& desc); 392e2aedc20476964763f09503939a9594e641051arileya@google.com 402e2aedc20476964763f09503939a9594e641051arileya@google.com ~GrTextureStripAtlas(); 412e2aedc20476964763f09503939a9594e641051arileya@google.com 422e2aedc20476964763f09503939a9594e641051arileya@google.com /** 432e2aedc20476964763f09503939a9594e641051arileya@google.com * Add a texture to the atlas 442e2aedc20476964763f09503939a9594e641051arileya@google.com * @param data Bitmap data to copy into the row 452e2aedc20476964763f09503939a9594e641051arileya@google.com * @return The row index we inserted into, or -1 if we failed to find an open row. The caller 462e2aedc20476964763f09503939a9594e641051arileya@google.com * is responsible for calling unlockRow() with this row index when it's done with it. 472e2aedc20476964763f09503939a9594e641051arileya@google.com */ 482e2aedc20476964763f09503939a9594e641051arileya@google.com int lockRow(const SkBitmap& data); 492e2aedc20476964763f09503939a9594e641051arileya@google.com void unlockRow(int row); 502e2aedc20476964763f09503939a9594e641051arileya@google.com 51fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com /** 52fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com * These functions help turn an integer row index in [0, 1, 2, ... numRows] into a scalar y 532e2aedc20476964763f09503939a9594e641051arileya@google.com * texture coordinate in [0, 1] that we can use in a shader. 542e2aedc20476964763f09503939a9594e641051arileya@google.com * 55fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com * If a regular texture access without using the atlas looks like: 562e2aedc20476964763f09503939a9594e641051arileya@google.com * 572e2aedc20476964763f09503939a9594e641051arileya@google.com * texture2D(sampler, vec2(x, y)) 582e2aedc20476964763f09503939a9594e641051arileya@google.com * 59fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com * Then when using the atlas we'd replace it with: 602e2aedc20476964763f09503939a9594e641051arileya@google.com * 61fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com * texture2D(sampler, vec2(x, yOffset + y * scaleFactor)) 622e2aedc20476964763f09503939a9594e641051arileya@google.com * 632e2aedc20476964763f09503939a9594e641051arileya@google.com * Where yOffset, returned by getYOffset(), is the offset to the start of the row within the 64fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com * atlas and scaleFactor, returned by getVerticalScaleFactor(), is the y-scale of the row, 652e2aedc20476964763f09503939a9594e641051arileya@google.com * relative to the height of the overall atlas texture. 662e2aedc20476964763f09503939a9594e641051arileya@google.com */ 6781712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com SkScalar getYOffset(int row) const { return SkIntToScalar(row) / fNumRows; } 6881712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com SkScalar getVerticalScaleFactor() const { return SkIntToScalar(fDesc.fRowHeight) / fDesc.fHeight; } 692e2aedc20476964763f09503939a9594e641051arileya@google.com 702e2aedc20476964763f09503939a9594e641051arileya@google.com GrContext* getContext() const { return fDesc.fContext; } 711f47f4f7325971dd53991e2bb02da94fa7c6d962robertphillips@google.com GrTexture* getTexture() const { return fTexture; } 722e2aedc20476964763f09503939a9594e641051arileya@google.com 732e2aedc20476964763f09503939a9594e641051arileya@google.comprivate: 742e2aedc20476964763f09503939a9594e641051arileya@google.com 752e2aedc20476964763f09503939a9594e641051arileya@google.com // Key to indicate an atlas row without any meaningful data stored in it 762e2aedc20476964763f09503939a9594e641051arileya@google.com const static uint32_t kEmptyAtlasRowKey = 0xffffffff; 772e2aedc20476964763f09503939a9594e641051arileya@google.com 78fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com /** 792e2aedc20476964763f09503939a9594e641051arileya@google.com * The state of a single row in our cache, next/prev pointers allow these to be chained 802e2aedc20476964763f09503939a9594e641051arileya@google.com * together to represent LRU status 812e2aedc20476964763f09503939a9594e641051arileya@google.com */ 82e3beb6bd7de7fa211681abbb0be58e80b19885e0commit-bot@chromium.org struct AtlasRow : SkNoncopyable { 832e2aedc20476964763f09503939a9594e641051arileya@google.com AtlasRow() : fKey(kEmptyAtlasRowKey), fLocks(0), fNext(NULL), fPrev(NULL) { } 842e2aedc20476964763f09503939a9594e641051arileya@google.com // GenerationID of the bitmap that is represented by this row, 0xffffffff means "empty" 85fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com uint32_t fKey; 862e2aedc20476964763f09503939a9594e641051arileya@google.com // How many times this has been locked (0 == unlocked) 87fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com int32_t fLocks; 882e2aedc20476964763f09503939a9594e641051arileya@google.com // We maintain an LRU linked list between unlocked nodes with these pointers 892e2aedc20476964763f09503939a9594e641051arileya@google.com AtlasRow* fNext; 902e2aedc20476964763f09503939a9594e641051arileya@google.com AtlasRow* fPrev; 912e2aedc20476964763f09503939a9594e641051arileya@google.com }; 922e2aedc20476964763f09503939a9594e641051arileya@google.com 93fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com /** 942e2aedc20476964763f09503939a9594e641051arileya@google.com * We'll only allow construction via the static GrTextureStripAtlas::GetAtlas 952e2aedc20476964763f09503939a9594e641051arileya@google.com */ 962e2aedc20476964763f09503939a9594e641051arileya@google.com GrTextureStripAtlas(Desc desc); 97fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 982e2aedc20476964763f09503939a9594e641051arileya@google.com void lockTexture(); 992e2aedc20476964763f09503939a9594e641051arileya@google.com void unlockTexture(); 1002e2aedc20476964763f09503939a9594e641051arileya@google.com 101fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com /** 1022e2aedc20476964763f09503939a9594e641051arileya@google.com * Initialize our LRU list (if one already exists, clear it and start anew) 1032e2aedc20476964763f09503939a9594e641051arileya@google.com */ 1042e2aedc20476964763f09503939a9594e641051arileya@google.com void initLRU(); 1052e2aedc20476964763f09503939a9594e641051arileya@google.com 1062e2aedc20476964763f09503939a9594e641051arileya@google.com /** 1072e2aedc20476964763f09503939a9594e641051arileya@google.com * Grabs the least recently used free row out of the LRU list, returns NULL if no rows are free. 1082e2aedc20476964763f09503939a9594e641051arileya@google.com */ 1092e2aedc20476964763f09503939a9594e641051arileya@google.com AtlasRow* getLRU(); 1102e2aedc20476964763f09503939a9594e641051arileya@google.com 1112e2aedc20476964763f09503939a9594e641051arileya@google.com void appendLRU(AtlasRow* row); 1122e2aedc20476964763f09503939a9594e641051arileya@google.com void removeFromLRU(AtlasRow* row); 1132e2aedc20476964763f09503939a9594e641051arileya@google.com 114fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com /** 115fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com * Searches the key table for a key and returns the index if found; if not found, it returns 1162e2aedc20476964763f09503939a9594e641051arileya@google.com * the bitwise not of the index at which we could insert the key to maintain a sorted list. 1172e2aedc20476964763f09503939a9594e641051arileya@google.com **/ 1182e2aedc20476964763f09503939a9594e641051arileya@google.com int searchByKey(uint32_t key); 1192e2aedc20476964763f09503939a9594e641051arileya@google.com 1202e2aedc20476964763f09503939a9594e641051arileya@google.com /** 1212e2aedc20476964763f09503939a9594e641051arileya@google.com * Compare two atlas rows by key, so we can sort/search by key 1222e2aedc20476964763f09503939a9594e641051arileya@google.com */ 12320f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com static bool KeyLess(const AtlasRow& lhs, const AtlasRow& rhs) { 12420f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com return lhs.fKey < rhs.fKey; 1252e2aedc20476964763f09503939a9594e641051arileya@google.com } 1262e2aedc20476964763f09503939a9594e641051arileya@google.com 1272e2aedc20476964763f09503939a9594e641051arileya@google.com#ifdef SK_DEBUG 1282e2aedc20476964763f09503939a9594e641051arileya@google.com void validate(); 1292e2aedc20476964763f09503939a9594e641051arileya@google.com#endif 1302e2aedc20476964763f09503939a9594e641051arileya@google.com 131cdb426d55a4bc4dae4f6d4f23e6994762950fdc3robertphillips@google.com /** 132cdb426d55a4bc4dae4f6d4f23e6994762950fdc3robertphillips@google.com * Clean up callback registered with GrContext. Allows this class to 133cdb426d55a4bc4dae4f6d4f23e6994762950fdc3robertphillips@google.com * free up any allocated AtlasEntry and GrTextureStripAtlas objects 134cdb426d55a4bc4dae4f6d4f23e6994762950fdc3robertphillips@google.com */ 135cdb426d55a4bc4dae4f6d4f23e6994762950fdc3robertphillips@google.com static void CleanUp(const GrContext* context, void* info); 136cdb426d55a4bc4dae4f6d4f23e6994762950fdc3robertphillips@google.com 137cdb426d55a4bc4dae4f6d4f23e6994762950fdc3robertphillips@google.com // Hash table entry for atlases 138a0b40280a49a8a43af7929ead3b3489951c58501commit-bot@chromium.org class AtlasEntry : public ::SkNoncopyable { 139cdb426d55a4bc4dae4f6d4f23e6994762950fdc3robertphillips@google.com public: 1403d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips // for SkTDynamicHash 1413d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips class Key : public GrMurmur3HashKey<sizeof(GrTextureStripAtlas::Desc)> {}; 1423d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips static const Key& GetKey(const AtlasEntry& entry) { return entry.fKey; } 1433d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips static uint32_t Hash(const Key& key) { return key.getHash(); } 1443d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips 1453d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips // AtlasEntry proper 146cdb426d55a4bc4dae4f6d4f23e6994762950fdc3robertphillips@google.com AtlasEntry() : fAtlas(NULL) {} 147cdb426d55a4bc4dae4f6d4f23e6994762950fdc3robertphillips@google.com ~AtlasEntry() { SkDELETE(fAtlas); } 1483d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips Key fKey; 149cdb426d55a4bc4dae4f6d4f23e6994762950fdc3robertphillips@google.com GrTextureStripAtlas* fAtlas; 150cdb426d55a4bc4dae4f6d4f23e6994762950fdc3robertphillips@google.com }; 151cdb426d55a4bc4dae4f6d4f23e6994762950fdc3robertphillips@google.com 1523d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips class Hash; 1533d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips static Hash* gAtlasCache; 154cdb426d55a4bc4dae4f6d4f23e6994762950fdc3robertphillips@google.com 1553d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips static Hash* GetCache(); 156cdb426d55a4bc4dae4f6d4f23e6994762950fdc3robertphillips@google.com 157f61c7463a945ebc891e2eead79051e4411bbeb57rileya@google.com // We increment gCacheCount for each atlas 1582e2aedc20476964763f09503939a9594e641051arileya@google.com static int32_t gCacheCount; 1592e2aedc20476964763f09503939a9594e641051arileya@google.com 160f61c7463a945ebc891e2eead79051e4411bbeb57rileya@google.com // A unique ID for this texture (formed with: gCacheCount++), so we can be sure that if we 161f61c7463a945ebc891e2eead79051e4411bbeb57rileya@google.com // get a texture back from the texture cache, that it's the same one we last used. 1620797c2cceadd7dfc2e7f9efa30b611d18efcdcddbsalomon@google.com const int32_t fCacheKey; 1632e2aedc20476964763f09503939a9594e641051arileya@google.com 1642e2aedc20476964763f09503939a9594e641051arileya@google.com // Total locks on all rows (when this reaches zero, we can unlock our texture) 1652e2aedc20476964763f09503939a9594e641051arileya@google.com int32_t fLockedRows; 1662e2aedc20476964763f09503939a9594e641051arileya@google.com 1672e2aedc20476964763f09503939a9594e641051arileya@google.com const Desc fDesc; 1682e2aedc20476964763f09503939a9594e641051arileya@google.com const uint16_t fNumRows; 1691f47f4f7325971dd53991e2bb02da94fa7c6d962robertphillips@google.com GrTexture* fTexture; 1702e2aedc20476964763f09503939a9594e641051arileya@google.com 1712e2aedc20476964763f09503939a9594e641051arileya@google.com // Array of AtlasRows which store the state of all our rows. Stored in a contiguous array, in 172fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com // order that they appear in our texture, this means we can subtract this pointer from a row 1732e2aedc20476964763f09503939a9594e641051arileya@google.com // pointer to get its index in the texture, and can save storing a row number in AtlasRow. 1742e2aedc20476964763f09503939a9594e641051arileya@google.com AtlasRow* fRows; 1752e2aedc20476964763f09503939a9594e641051arileya@google.com 1762e2aedc20476964763f09503939a9594e641051arileya@google.com // Head and tail for linked list of least-recently-used rows (front = least recently used). 1772e2aedc20476964763f09503939a9594e641051arileya@google.com // Note that when a texture is locked, it gets removed from this list until it is unlocked. 1782e2aedc20476964763f09503939a9594e641051arileya@google.com AtlasRow* fLRUFront; 1792e2aedc20476964763f09503939a9594e641051arileya@google.com AtlasRow* fLRUBack; 1802e2aedc20476964763f09503939a9594e641051arileya@google.com 1812e2aedc20476964763f09503939a9594e641051arileya@google.com // A list of pointers to AtlasRows that currently contain cached images, sorted by key 1822e2aedc20476964763f09503939a9594e641051arileya@google.com SkTDArray<AtlasRow*> fKeyTable; 1832e2aedc20476964763f09503939a9594e641051arileya@google.com}; 1842e2aedc20476964763f09503939a9594e641051arileya@google.com 1852e2aedc20476964763f09503939a9594e641051arileya@google.com#endif 186