1/*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#ifndef GrTextureStripAtlas_DEFINED
9#define GrTextureStripAtlas_DEFINED
10
11#include "GrBinHashKey.h"
12#include "GrTHashTable.h"
13#include "SkBitmap.h"
14#include "SkGr.h"
15#include "SkTDArray.h"
16#include "SkTypes.h"
17
18/**
19 * Maintains a single large texture whose rows store many textures of a small fixed height,
20 * stored in rows across the x-axis such that we can safely wrap/repeat them horizontally.
21 */
22class GrTextureStripAtlas {
23public:
24    /**
25     * Descriptor struct which we'll use as a hash table key
26     **/
27    struct Desc {
28        Desc() { memset(this, 0, sizeof(*this)); }
29        uint16_t fWidth, fHeight, fRowHeight;
30        GrPixelConfig fConfig;
31        GrContext* fContext;
32        const uint32_t* asKey() const { return reinterpret_cast<const uint32_t*>(this); }
33    };
34
35    /**
36     * Try to find an atlas with the required parameters, creates a new one if necessary
37     */
38    static GrTextureStripAtlas* GetAtlas(const Desc& desc);
39
40    ~GrTextureStripAtlas();
41
42    /**
43     * Add a texture to the atlas
44     *  @param data Bitmap data to copy into the row
45     *  @return The row index we inserted into, or -1 if we failed to find an open row. The caller
46     *      is responsible for calling unlockRow() with this row index when it's done with it.
47     */
48    int lockRow(const SkBitmap& data);
49    void unlockRow(int row);
50
51    /**
52     * These functions help turn an integer row index in [0, 1, 2, ... numRows] into a scalar y
53     * texture coordinate in [0, 1] that we can use in a shader.
54     *
55     * If a regular texture access without using the atlas looks like:
56     *
57     *      texture2D(sampler, vec2(x, y))
58     *
59     * Then when using the atlas we'd replace it with:
60     *
61     *       texture2D(sampler, vec2(x, yOffset + y * scaleFactor))
62     *
63     * Where yOffset, returned by getYOffset(), is the offset to the start of the row within the
64     * atlas and scaleFactor, returned by getVerticalScaleFactor(), is the y-scale of the row,
65     * relative to the height of the overall atlas texture.
66     */
67    SkScalar getYOffset(int row) const { return SkIntToScalar(row) / fNumRows; }
68    SkScalar getVerticalScaleFactor() const { return SkIntToScalar(fDesc.fRowHeight) / fDesc.fHeight; }
69
70    GrContext* getContext() const { return fDesc.fContext; }
71    GrTexture* getTexture() const { return fTexture; }
72
73private:
74
75    // Key to indicate an atlas row without any meaningful data stored in it
76    const static uint32_t kEmptyAtlasRowKey = 0xffffffff;
77
78    /**
79     * The state of a single row in our cache, next/prev pointers allow these to be chained
80     * together to represent LRU status
81     */
82    struct AtlasRow : SkNoncopyable {
83        AtlasRow() : fKey(kEmptyAtlasRowKey), fLocks(0), fNext(NULL), fPrev(NULL) { }
84        // GenerationID of the bitmap that is represented by this row, 0xffffffff means "empty"
85        uint32_t fKey;
86        // How many times this has been locked (0 == unlocked)
87        int32_t fLocks;
88        // We maintain an LRU linked list between unlocked nodes with these pointers
89        AtlasRow* fNext;
90        AtlasRow* fPrev;
91    };
92
93    /**
94     * We'll only allow construction via the static GrTextureStripAtlas::GetAtlas
95     */
96    GrTextureStripAtlas(Desc desc);
97
98    void lockTexture();
99    void unlockTexture();
100
101    /**
102     * Initialize our LRU list (if one already exists, clear it and start anew)
103     */
104    void initLRU();
105
106    /**
107     * Grabs the least recently used free row out of the LRU list, returns NULL if no rows are free.
108     */
109    AtlasRow* getLRU();
110
111    void appendLRU(AtlasRow* row);
112    void removeFromLRU(AtlasRow* row);
113
114    /**
115     * Searches the key table for a key and returns the index if found; if not found, it returns
116     * the bitwise not of the index at which we could insert the key to maintain a sorted list.
117     **/
118    int searchByKey(uint32_t key);
119
120    /**
121     * Compare two atlas rows by key, so we can sort/search by key
122     */
123    static bool KeyLess(const AtlasRow& lhs, const AtlasRow& rhs) {
124        return lhs.fKey < rhs.fKey;
125    }
126
127#ifdef SK_DEBUG
128    void validate();
129#endif
130
131    /**
132     * Clean up callback registered with GrContext. Allows this class to
133     * free up any allocated AtlasEntry and GrTextureStripAtlas objects
134     */
135    static void CleanUp(const GrContext* context, void* info);
136
137    // Hash table entry for atlases
138    class AtlasEntry;
139    class AtlasHashKey : public GrBinHashKey<sizeof(GrTextureStripAtlas::Desc)> {
140    public:
141        static bool Equals(const AtlasEntry& entry, const AtlasHashKey& key);
142        static bool LessThan(const AtlasEntry& entry, const AtlasHashKey& key);
143    };
144    class AtlasEntry : public ::SkNoncopyable {
145    public:
146        AtlasEntry() : fAtlas(NULL) {}
147        ~AtlasEntry() { SkDELETE(fAtlas); }
148        AtlasHashKey fKey;
149        GrTextureStripAtlas* fAtlas;
150    };
151
152    static GrTHashTable<AtlasEntry, AtlasHashKey, 8>* gAtlasCache;
153
154    static GrTHashTable<AtlasEntry, AtlasHashKey, 8>* GetCache();
155
156    // We increment gCacheCount for each atlas
157    static int32_t gCacheCount;
158
159    // A unique ID for this texture (formed with: gCacheCount++), so we can be sure that if we
160    // get a texture back from the texture cache, that it's the same one we last used.
161    const int32_t fCacheKey;
162
163    // Total locks on all rows (when this reaches zero, we can unlock our texture)
164    int32_t fLockedRows;
165
166    const Desc fDesc;
167    const uint16_t fNumRows;
168    GrTexture* fTexture;
169
170    // Array of AtlasRows which store the state of all our rows. Stored in a contiguous array, in
171    // order that they appear in our texture, this means we can subtract this pointer from a row
172    // pointer to get its index in the texture, and can save storing a row number in AtlasRow.
173    AtlasRow* fRows;
174
175    // Head and tail for linked list of least-recently-used rows (front = least recently used).
176    // Note that when a texture is locked, it gets removed from this list until it is unlocked.
177    AtlasRow* fLRUFront;
178    AtlasRow* fLRUBack;
179
180    // A list of pointers to AtlasRows that currently contain cached images, sorted by key
181    SkTDArray<AtlasRow*> fKeyTable;
182};
183
184inline bool GrTextureStripAtlas::AtlasHashKey::Equals(const AtlasEntry& entry,
185                                                      const AtlasHashKey& key) {
186    return entry.fKey == key;
187}
188
189inline bool GrTextureStripAtlas::AtlasHashKey::LessThan(const AtlasEntry& entry,
190                                                        const AtlasHashKey& key) {
191    return entry.fKey < key;
192}
193
194#endif
195