1/*
2 * Copyright 2015 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 GrBatchAtlas_DEFINED
9#define GrBatchAtlas_DEFINED
10
11#include "GrTexture.h"
12#include "SkPoint.h"
13#include "SkTDArray.h"
14#include "SkTInternalLList.h"
15
16#include "batches/GrDrawBatch.h"
17
18class GrRectanizer;
19
20struct GrBatchAtlasConfig {
21    int numPlotsX() const { return fWidth / fPlotWidth; }
22    int numPlotsY() const { return fHeight / fPlotWidth; }
23    int fWidth;
24    int fHeight;
25    int fLog2Width;
26    int fLog2Height;
27    int fPlotWidth;
28    int fPlotHeight;
29};
30
31class GrBatchAtlas {
32public:
33    // An AtlasID is an opaque handle which callers can use to determine if the atlas contains
34    // a specific piece of data
35    typedef uint64_t AtlasID;
36    static const uint32_t kInvalidAtlasID = 0;
37    static const uint64_t kInvalidAtlasGeneration = 0;
38
39    // A function pointer for use as a callback during eviction.  Whenever GrBatchAtlas evicts a
40    // specific AtlasID, it will call all of the registered listeners so they can optionally process
41    // the eviction
42    typedef void (*EvictionFunc)(GrBatchAtlas::AtlasID, void*);
43
44    GrBatchAtlas(GrTexture*, int numPlotsX, int numPlotsY);
45    ~GrBatchAtlas();
46
47    // Adds a width x height subimage to the atlas. Upon success it returns
48    // the containing GrPlot and absolute location in the backing texture.
49    // nullptr is returned if the subimage cannot fit in the atlas.
50    // If provided, the image data will be written to the CPU-side backing bitmap.
51    // NOTE: If the client intends to refer to the atlas, they should immediately call 'setUseToken'
52    // with the currentToken from the batch target, otherwise the next call to addToAtlas might
53    // cause an eviction
54    bool addToAtlas(AtlasID*, GrDrawBatch::Target*, int width, int height, const void* image,
55                    SkIPoint16* loc);
56
57    GrTexture* getTexture() const { return fTexture; }
58
59    uint64_t atlasGeneration() const { return fAtlasGeneration; }
60
61    inline bool hasID(AtlasID id) {
62        uint32_t index = GetIndexFromID(id);
63        SkASSERT(index < fNumPlots);
64        return fPlotArray[index]->genID() == GetGenerationFromID(id);
65    }
66
67    // To ensure the atlas does not evict a given entry, the client must set the last use token
68    inline void setLastUseToken(AtlasID id, GrBatchToken batchToken) {
69        SkASSERT(this->hasID(id));
70        uint32_t index = GetIndexFromID(id);
71        SkASSERT(index < fNumPlots);
72        this->makeMRU(fPlotArray[index]);
73        fPlotArray[index]->setLastUseToken(batchToken);
74    }
75
76    inline void registerEvictionCallback(EvictionFunc func, void* userData) {
77        EvictionData* data = fEvictionCallbacks.append();
78        data->fFunc = func;
79        data->fData = userData;
80    }
81
82    /*
83     * A class which can be handed back to GrBatchAtlas for updating in bulk last use tokens.  The
84     * current max number of plots the GrBatchAtlas can handle is 32, if in the future this is
85     * insufficient then we can move to a 64 bit int
86     */
87    class BulkUseTokenUpdater {
88    public:
89        BulkUseTokenUpdater() : fPlotAlreadyUpdated(0) {}
90        BulkUseTokenUpdater(const BulkUseTokenUpdater& that)
91            : fPlotsToUpdate(that.fPlotsToUpdate)
92            , fPlotAlreadyUpdated(that.fPlotAlreadyUpdated) {
93        }
94
95        void add(AtlasID id) {
96            int index = GrBatchAtlas::GetIndexFromID(id);
97            if (!this->find(index)) {
98                this->set(index);
99            }
100        }
101
102        void reset() {
103            fPlotsToUpdate.reset();
104            fPlotAlreadyUpdated = 0;
105        }
106
107    private:
108        bool find(int index) const {
109            SkASSERT(index < kMaxPlots);
110            return (fPlotAlreadyUpdated >> index) & 1;
111        }
112
113        void set(int index) {
114            SkASSERT(!this->find(index));
115            fPlotAlreadyUpdated = fPlotAlreadyUpdated | (1 << index);
116            fPlotsToUpdate.push_back(index);
117        }
118
119        static const int kMinItems = 4;
120        static const int kMaxPlots = 32;
121        SkSTArray<kMinItems, int, true> fPlotsToUpdate;
122        uint32_t fPlotAlreadyUpdated;
123
124        friend class GrBatchAtlas;
125    };
126
127    void setLastUseTokenBulk(const BulkUseTokenUpdater& updater, GrBatchToken batchToken) {
128        int count = updater.fPlotsToUpdate.count();
129        for (int i = 0; i < count; i++) {
130            BatchPlot* plot = fPlotArray[updater.fPlotsToUpdate[i]];
131            this->makeMRU(plot);
132            plot->setLastUseToken(batchToken);
133        }
134    }
135
136    static const int kGlyphMaxDim = 256;
137    static bool GlyphTooLargeForAtlas(int width, int height) {
138        return width > kGlyphMaxDim || height > kGlyphMaxDim;
139    }
140
141private:
142    // The backing GrTexture for a GrBatchAtlas is broken into a spatial grid of BatchPlots.
143    // The BatchPlots keep track of subimage placement via their GrRectanizer. A BatchPlot
144    // manages the lifetime of its data using two tokens, a last use token and a last upload token.
145    // Once a BatchPlot is "full" (i.e. there is no room for the new subimage according to the
146    // GrRectanizer), it can no longer be used unless the last use of the GrPlot has already been
147    // flushed through to the gpu.
148    class BatchPlot : public SkRefCnt {
149        SK_DECLARE_INTERNAL_LLIST_INTERFACE(BatchPlot);
150
151    public:
152        // index() is a unique id for the plot relative to the owning GrAtlas.  genID() is a
153        // monotonically incremented number which is bumped every time this plot is
154        // evicted from the cache (i.e., there is continuity in genID() across atlas spills).
155        uint32_t index() const { return fIndex; }
156        uint64_t genID() const { return fGenID; }
157        GrBatchAtlas::AtlasID id() const {
158            SkASSERT(GrBatchAtlas::kInvalidAtlasID != fID);
159            return fID;
160        }
161        SkDEBUGCODE(size_t bpp() const { return fBytesPerPixel; })
162
163        bool addSubImage(int width, int height, const void* image, SkIPoint16* loc);
164
165        // To manage the lifetime of a plot, we use two tokens.  We use the last upload token to
166        // know when we can 'piggy back' uploads, ie if the last upload hasn't been flushed to gpu,
167        // we don't need to issue a new upload even if we update the cpu backing store.  We use
168        // lastUse to determine when we can evict a plot from the cache, ie if the last use has
169        // already flushed through the gpu then we can reuse the plot.
170        GrBatchToken lastUploadToken() const { return fLastUpload; }
171        GrBatchToken lastUseToken() const { return fLastUse; }
172        void setLastUploadToken(GrBatchToken batchToken) {
173            SkASSERT(batchToken >= fLastUpload);
174            fLastUpload = batchToken;
175        }
176        void setLastUseToken(GrBatchToken batchToken) {
177            SkASSERT(batchToken >= fLastUse);
178            fLastUse = batchToken;
179        }
180
181        void uploadToTexture(GrBatchUploader::TextureUploader* uploader, GrTexture* texture);
182        void resetRects();
183
184    private:
185        BatchPlot(int index, uint64_t genID, int offX, int offY, int width, int height,
186                  GrPixelConfig config);
187
188        ~BatchPlot() override;
189
190        // Create a clone of this plot. The cloned plot will take the place of the
191        // current plot in the atlas.
192        BatchPlot* clone() const {
193            return new BatchPlot(fIndex, fGenID+1, fX, fY, fWidth, fHeight, fConfig);
194        }
195
196        static GrBatchAtlas::AtlasID CreateId(uint32_t index, uint64_t generation) {
197            SkASSERT(index < (1 << 16));
198            SkASSERT(generation < ((uint64_t)1 << 48));
199            return generation << 16 | index;
200        }
201
202        GrBatchToken          fLastUpload;
203        GrBatchToken          fLastUse;
204
205        const uint32_t        fIndex;
206        uint64_t              fGenID;
207        GrBatchAtlas::AtlasID fID;
208        unsigned char*        fData;
209        const int             fWidth;
210        const int             fHeight;
211        const int             fX;
212        const int             fY;
213        GrRectanizer*         fRects;
214        const SkIPoint16      fOffset;        // the offset of the plot in the backing texture
215        const GrPixelConfig   fConfig;
216        const size_t          fBytesPerPixel;
217        SkIRect               fDirtyRect;
218        SkDEBUGCODE(bool      fDirty;)
219
220        friend class GrBatchAtlas;
221
222        typedef SkRefCnt INHERITED;
223    };
224
225    typedef SkTInternalLList<BatchPlot> GrBatchPlotList;
226
227    static uint32_t GetIndexFromID(AtlasID id) {
228        return id & 0xffff;
229    }
230
231    // top 48 bits are reserved for the generation ID
232    static uint64_t GetGenerationFromID(AtlasID id) {
233        return (id >> 16) & 0xffffffffffff;
234    }
235
236    inline void updatePlot(GrDrawBatch::Target*, AtlasID*, BatchPlot*);
237
238    inline void makeMRU(BatchPlot* plot) {
239        if (fPlotList.head() == plot) {
240            return;
241        }
242
243        fPlotList.remove(plot);
244        fPlotList.addToHead(plot);
245    }
246
247    inline void processEviction(AtlasID);
248
249    friend class GrPlotUploader; // to access GrBatchPlot
250
251    GrTexture* fTexture;
252    SkDEBUGCODE(uint32_t fNumPlots;)
253
254    uint64_t fAtlasGeneration;
255
256    struct EvictionData {
257        EvictionFunc fFunc;
258        void* fData;
259    };
260
261    SkTDArray<EvictionData> fEvictionCallbacks;
262    // allocated array of GrBatchPlots
263    SkAutoTUnref<BatchPlot>* fPlotArray;
264    // LRU list of GrPlots (MRU at head - LRU at tail)
265    GrBatchPlotList fPlotList;
266};
267
268#endif
269