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