180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Copyright 2012 Google Inc. 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Use of this source code is governed by a BSD-style license that can be 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found in the LICENSE file. 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifndef GrTextureStripAtlas_DEFINED 980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#define GrTextureStripAtlas_DEFINED 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 110a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger#include "GrBinHashKey.h" 120a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger#include "GrTHashTable.h" 1380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkBitmap.h" 1480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkGr.h" 1580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkTDArray.h" 160a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger#include "SkTypes.h" 1780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/** 1980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Maintains a single large texture whose rows store many textures of a small fixed height, 2080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * stored in rows across the x-axis such that we can safely wrap/repeat them horizontally. 2180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 2280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruclass GrTextureStripAtlas { 2380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querupublic: 2480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 2580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Descriptor struct which we'll use as a hash table key 2680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru **/ 2780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru struct Desc { 2880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Desc() { memset(this, 0, sizeof(*this)); } 2980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint16_t fWidth, fHeight, fRowHeight; 3080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrPixelConfig fConfig; 3180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrContext* fContext; 3280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const uint32_t* asKey() const { return reinterpret_cast<const uint32_t*>(this); } 3380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru }; 3480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 3680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Try to find an atlas with the required parameters, creates a new one if necessary 3780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 3880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static GrTextureStripAtlas* GetAtlas(const Desc& desc); 3980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru ~GrTextureStripAtlas(); 4180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 4380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Add a texture to the atlas 4480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * @param data Bitmap data to copy into the row 4580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * @return The row index we inserted into, or -1 if we failed to find an open row. The caller 4680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * is responsible for calling unlockRow() with this row index when it's done with it. 4780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 4880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int lockRow(const SkBitmap& data); 4980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void unlockRow(int row); 5080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 5180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 5280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * These functions help turn an integer row index in [0, 1, 2, ... numRows] into a scalar y 5380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * texture coordinate in [0, 1] that we can use in a shader. 5480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 5580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * If a regular texture access without using the atlas looks like: 5680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 5780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * texture2D(sampler, vec2(x, y)) 5880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 5980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Then when using the atlas we'd replace it with: 6080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 6180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * texture2D(sampler, vec2(x, yOffset + y * scaleFactor)) 6280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 6380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Where yOffset, returned by getYOffset(), is the offset to the start of the row within the 6480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * atlas and scaleFactor, returned by getVerticalScaleFactor(), is the y-scale of the row, 6580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * relative to the height of the overall atlas texture. 6680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 67363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger SkScalar getYOffset(int row) const { return SkIntToScalar(row) / fNumRows; } 68363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger SkScalar getVerticalScaleFactor() const { return SkIntToScalar(fDesc.fRowHeight) / fDesc.fHeight; } 6980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrContext* getContext() const { return fDesc.fContext; } 7180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrTexture* getTexture() const { return fTexture; } 7280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruprivate: 7480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Key to indicate an atlas row without any meaningful data stored in it 7680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const static uint32_t kEmptyAtlasRowKey = 0xffffffff; 7780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 7980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * The state of a single row in our cache, next/prev pointers allow these to be chained 8080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * together to represent LRU status 8180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 820a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger struct AtlasRow : public SkNoncopyable { 8380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru AtlasRow() : fKey(kEmptyAtlasRowKey), fLocks(0), fNext(NULL), fPrev(NULL) { } 8480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // GenerationID of the bitmap that is represented by this row, 0xffffffff means "empty" 8580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t fKey; 8680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // How many times this has been locked (0 == unlocked) 8780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int32_t fLocks; 8880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // We maintain an LRU linked list between unlocked nodes with these pointers 8980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru AtlasRow* fNext; 9080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru AtlasRow* fPrev; 9180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru }; 9280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 9380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 9480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * We'll only allow construction via the static GrTextureStripAtlas::GetAtlas 9580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 9680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrTextureStripAtlas(Desc desc); 9780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 9880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void lockTexture(); 9980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void unlockTexture(); 10080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 10280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Initialize our LRU list (if one already exists, clear it and start anew) 10380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 10480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void initLRU(); 10580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 10780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Grabs the least recently used free row out of the LRU list, returns NULL if no rows are free. 10880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 10980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru AtlasRow* getLRU(); 11080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void appendLRU(AtlasRow* row); 11280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void removeFromLRU(AtlasRow* row); 11380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 11580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Searches the key table for a key and returns the index if found; if not found, it returns 11680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * the bitwise not of the index at which we could insert the key to maintain a sorted list. 11780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru **/ 11880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int searchByKey(uint32_t key); 11980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 12080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 12180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Compare two atlas rows by key, so we can sort/search by key 12280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 1237839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger static bool KeyLess(const AtlasRow& lhs, const AtlasRow& rhs) { 1247839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return lhs.fKey < rhs.fKey; 12580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 12680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 12780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef SK_DEBUG 12880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void validate(); 12980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 13080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 13180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 13280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Clean up callback registered with GrContext. Allows this class to 13380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * free up any allocated AtlasEntry and GrTextureStripAtlas objects 13480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 13580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static void CleanUp(const GrContext* context, void* info); 13680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 13780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Hash table entry for atlases 13880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru class AtlasEntry; 139910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger class AtlasHashKey : public GrBinHashKey<sizeof(GrTextureStripAtlas::Desc)> { 140910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger public: 141910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger static bool Equals(const AtlasEntry& entry, const AtlasHashKey& key); 142910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger static bool LessThan(const AtlasEntry& entry, const AtlasHashKey& key); 143910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger }; 1440a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger class AtlasEntry : public ::SkNoncopyable { 14580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru public: 14680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru AtlasEntry() : fAtlas(NULL) {} 14780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru ~AtlasEntry() { SkDELETE(fAtlas); } 14880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru AtlasHashKey fKey; 14980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrTextureStripAtlas* fAtlas; 15080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru }; 15180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 15280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static GrTHashTable<AtlasEntry, AtlasHashKey, 8>* gAtlasCache; 15380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 15480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static GrTHashTable<AtlasEntry, AtlasHashKey, 8>* GetCache(); 15580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 15680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // We increment gCacheCount for each atlas 15780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static int32_t gCacheCount; 15880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 15980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // A unique ID for this texture (formed with: gCacheCount++), so we can be sure that if we 16080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // get a texture back from the texture cache, that it's the same one we last used. 161d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger const int32_t fCacheKey; 16280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 16380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Total locks on all rows (when this reaches zero, we can unlock our texture) 16480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int32_t fLockedRows; 16580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 16680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const Desc fDesc; 16780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const uint16_t fNumRows; 16880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrTexture* fTexture; 16980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 17080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Array of AtlasRows which store the state of all our rows. Stored in a contiguous array, in 17180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // order that they appear in our texture, this means we can subtract this pointer from a row 17280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // pointer to get its index in the texture, and can save storing a row number in AtlasRow. 17380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru AtlasRow* fRows; 17480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 17580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Head and tail for linked list of least-recently-used rows (front = least recently used). 17680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Note that when a texture is locked, it gets removed from this list until it is unlocked. 17780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru AtlasRow* fLRUFront; 17880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru AtlasRow* fLRUBack; 17980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 18080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // A list of pointers to AtlasRows that currently contain cached images, sorted by key 18180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkTDArray<AtlasRow*> fKeyTable; 18280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 18380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 184910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenbergerinline bool GrTextureStripAtlas::AtlasHashKey::Equals(const AtlasEntry& entry, 185910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger const AtlasHashKey& key) { 186910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger return entry.fKey == key; 187910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger} 188910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger 189910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenbergerinline bool GrTextureStripAtlas::AtlasHashKey::LessThan(const AtlasEntry& entry, 190910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger const AtlasHashKey& key) { 191910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger return entry.fKey < key; 192910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger} 193910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger 19480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 195