1/*
2 * Copyright (C) 2012 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include <SkGlyph.h>
18
19#include "CacheTexture.h"
20#include "../Debug.h"
21#include "../Extensions.h"
22#include "../PixelBuffer.h"
23
24namespace android {
25namespace uirenderer {
26
27///////////////////////////////////////////////////////////////////////////////
28// CacheBlock
29///////////////////////////////////////////////////////////////////////////////
30
31/**
32 * Insert new block into existing linked list of blocks. Blocks are sorted in increasing-width
33 * order, except for the final block (the remainder space at the right, since we fill from the
34 * left).
35 */
36CacheBlock* CacheBlock::insertBlock(CacheBlock* head, CacheBlock* newBlock) {
37#if DEBUG_FONT_RENDERER
38    ALOGD("insertBlock: this, x, y, w, h = %p, %d, %d, %d, %d",
39            newBlock, newBlock->mX, newBlock->mY,
40            newBlock->mWidth, newBlock->mHeight);
41#endif
42
43    CacheBlock* currBlock = head;
44    CacheBlock* prevBlock = NULL;
45
46    while (currBlock && currBlock->mY != TEXTURE_BORDER_SIZE) {
47        if (newBlock->mWidth < currBlock->mWidth) {
48            newBlock->mNext = currBlock;
49            newBlock->mPrev = prevBlock;
50            currBlock->mPrev = newBlock;
51
52            if (prevBlock) {
53                prevBlock->mNext = newBlock;
54                return head;
55            } else {
56                return newBlock;
57            }
58        }
59
60        prevBlock = currBlock;
61        currBlock = currBlock->mNext;
62    }
63
64    // new block larger than all others - insert at end (but before the remainder space, if there)
65    newBlock->mNext = currBlock;
66    newBlock->mPrev = prevBlock;
67
68    if (currBlock) {
69        currBlock->mPrev = newBlock;
70    }
71
72    if (prevBlock) {
73        prevBlock->mNext = newBlock;
74        return head;
75    } else {
76        return newBlock;
77    }
78}
79
80CacheBlock* CacheBlock::removeBlock(CacheBlock* head, CacheBlock* blockToRemove) {
81#if DEBUG_FONT_RENDERER
82    ALOGD("removeBlock: this, x, y, w, h = %p, %d, %d, %d, %d",
83            blockToRemove, blockToRemove->mX, blockToRemove->mY,
84            blockToRemove->mWidth, blockToRemove->mHeight);
85#endif
86
87    CacheBlock* newHead = head;
88    CacheBlock* nextBlock = blockToRemove->mNext;
89    CacheBlock* prevBlock = blockToRemove->mPrev;
90
91    if (prevBlock) {
92        prevBlock->mNext = nextBlock;
93    } else {
94        newHead = nextBlock;
95    }
96
97    if (nextBlock) {
98        nextBlock->mPrev = prevBlock;
99    }
100
101    delete blockToRemove;
102
103    return newHead;
104}
105
106///////////////////////////////////////////////////////////////////////////////
107// CacheTexture
108///////////////////////////////////////////////////////////////////////////////
109
110CacheTexture::CacheTexture(uint16_t width, uint16_t height, uint32_t maxQuadCount) :
111            mTexture(NULL), mTextureId(0), mWidth(width), mHeight(height),
112            mLinearFiltering(false), mDirty(false), mNumGlyphs(0),
113            mMesh(NULL), mCurrentQuad(0), mMaxQuadCount(maxQuadCount) {
114    mCacheBlocks = new CacheBlock(TEXTURE_BORDER_SIZE, TEXTURE_BORDER_SIZE,
115            mWidth - TEXTURE_BORDER_SIZE, mHeight - TEXTURE_BORDER_SIZE, true);
116
117    // OpenGL ES 3.0+ lets us specify the row length for unpack operations such
118    // as glTexSubImage2D(). This allows us to upload a sub-rectangle of a texture.
119    // With OpenGL ES 2.0 we have to upload entire stripes instead.
120    mHasES3 = Extensions::getInstance().getMajorGlVersion() >= 3;
121}
122
123CacheTexture::~CacheTexture() {
124    releaseMesh();
125    releaseTexture();
126    reset();
127}
128
129void CacheTexture::reset() {
130    // Delete existing cache blocks
131    while (mCacheBlocks != NULL) {
132        CacheBlock* tmpBlock = mCacheBlocks;
133        mCacheBlocks = mCacheBlocks->mNext;
134        delete tmpBlock;
135    }
136    mNumGlyphs = 0;
137    mCurrentQuad = 0;
138}
139
140void CacheTexture::init() {
141    // reset, then create a new remainder space to start again
142    reset();
143    mCacheBlocks = new CacheBlock(TEXTURE_BORDER_SIZE, TEXTURE_BORDER_SIZE,
144            mWidth - TEXTURE_BORDER_SIZE, mHeight - TEXTURE_BORDER_SIZE, true);
145}
146
147void CacheTexture::releaseMesh() {
148    delete[] mMesh;
149}
150
151void CacheTexture::releaseTexture() {
152    if (mTexture) {
153        delete mTexture;
154        mTexture = NULL;
155    }
156    if (mTextureId) {
157        glDeleteTextures(1, &mTextureId);
158        mTextureId = 0;
159    }
160    mDirty = false;
161    mCurrentQuad = 0;
162}
163
164void CacheTexture::setLinearFiltering(bool linearFiltering, bool bind) {
165   if (linearFiltering != mLinearFiltering) {
166       mLinearFiltering = linearFiltering;
167
168       const GLenum filtering = linearFiltering ? GL_LINEAR : GL_NEAREST;
169       if (bind) glBindTexture(GL_TEXTURE_2D, getTextureId());
170       glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, filtering);
171       glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, filtering);
172   }
173}
174
175void CacheTexture::allocateMesh() {
176    if (!mMesh) {
177        mMesh = new TextureVertex[mMaxQuadCount * 4];
178    }
179}
180
181void CacheTexture::allocateTexture() {
182    if (!mTexture) {
183        mTexture = PixelBuffer::create(GL_ALPHA, mWidth, mHeight);
184    }
185
186    if (!mTextureId) {
187        glGenTextures(1, &mTextureId);
188
189        glBindTexture(GL_TEXTURE_2D, mTextureId);
190        glPixelStorei(GL_UNPACK_ALIGNMENT, 1);
191        // Initialize texture dimensions
192        glTexImage2D(GL_TEXTURE_2D, 0, GL_ALPHA, mWidth, mHeight, 0,
193                GL_ALPHA, GL_UNSIGNED_BYTE, 0);
194
195        const GLenum filtering = getLinearFiltering() ? GL_LINEAR : GL_NEAREST;
196        glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, filtering);
197        glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, filtering);
198
199        glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_CLAMP_TO_EDGE);
200        glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_CLAMP_TO_EDGE);
201    }
202}
203
204bool CacheTexture::upload() {
205    const Rect& dirtyRect = mDirtyRect;
206
207    uint32_t x = mHasES3 ? dirtyRect.left : 0;
208    uint32_t y = dirtyRect.top;
209    uint32_t width = mHasES3 ? dirtyRect.getWidth() : mWidth;
210    uint32_t height = dirtyRect.getHeight();
211
212    // The unpack row length only needs to be specified when a new
213    // texture is bound
214    if (mHasES3) {
215        glPixelStorei(GL_UNPACK_ROW_LENGTH, mWidth);
216    }
217
218    mTexture->upload(x, y, width, height, y * mWidth + x);
219
220    setDirty(false);
221
222    return mHasES3;
223}
224
225void CacheTexture::setDirty(bool dirty) {
226    mDirty = dirty;
227    if (!dirty) {
228        mDirtyRect.setEmpty();
229    }
230}
231
232bool CacheTexture::fitBitmap(const SkGlyph& glyph, uint32_t* retOriginX, uint32_t* retOriginY) {
233    if (glyph.fHeight + TEXTURE_BORDER_SIZE * 2 > mHeight) {
234        return false;
235    }
236
237    uint16_t glyphW = glyph.fWidth + TEXTURE_BORDER_SIZE;
238    uint16_t glyphH = glyph.fHeight + TEXTURE_BORDER_SIZE;
239
240    // roundedUpW equals glyphW to the next multiple of CACHE_BLOCK_ROUNDING_SIZE.
241    // This columns for glyphs that are close but not necessarily exactly the same size. It trades
242    // off the loss of a few pixels for some glyphs against the ability to store more glyphs
243    // of varying sizes in one block.
244    uint16_t roundedUpW = (glyphW + CACHE_BLOCK_ROUNDING_SIZE - 1) & -CACHE_BLOCK_ROUNDING_SIZE;
245
246    CacheBlock* cacheBlock = mCacheBlocks;
247    while (cacheBlock) {
248        // Store glyph in this block iff: it fits the block's remaining space and:
249        // it's the remainder space (mY == 0) or there's only enough height for this one glyph
250        // or it's within ROUNDING_SIZE of the block width
251        if (roundedUpW <= cacheBlock->mWidth && glyphH <= cacheBlock->mHeight &&
252                (cacheBlock->mY == TEXTURE_BORDER_SIZE ||
253                        (cacheBlock->mWidth - roundedUpW < CACHE_BLOCK_ROUNDING_SIZE))) {
254            if (cacheBlock->mHeight - glyphH < glyphH) {
255                // Only enough space for this glyph - don't bother rounding up the width
256                roundedUpW = glyphW;
257            }
258
259            *retOriginX = cacheBlock->mX;
260            *retOriginY = cacheBlock->mY;
261
262            // If this is the remainder space, create a new cache block for this column. Otherwise,
263            // adjust the info about this column.
264            if (cacheBlock->mY == TEXTURE_BORDER_SIZE) {
265                uint16_t oldX = cacheBlock->mX;
266                // Adjust remainder space dimensions
267                cacheBlock->mWidth -= roundedUpW;
268                cacheBlock->mX += roundedUpW;
269
270                if (mHeight - glyphH >= glyphH) {
271                    // There's enough height left over to create a new CacheBlock
272                    CacheBlock* newBlock = new CacheBlock(oldX, glyphH + TEXTURE_BORDER_SIZE,
273                            roundedUpW, mHeight - glyphH - TEXTURE_BORDER_SIZE);
274#if DEBUG_FONT_RENDERER
275                    ALOGD("fitBitmap: Created new block: this, x, y, w, h = %p, %d, %d, %d, %d",
276                            newBlock, newBlock->mX, newBlock->mY,
277                            newBlock->mWidth, newBlock->mHeight);
278#endif
279                    mCacheBlocks = CacheBlock::insertBlock(mCacheBlocks, newBlock);
280                }
281            } else {
282                // Insert into current column and adjust column dimensions
283                cacheBlock->mY += glyphH;
284                cacheBlock->mHeight -= glyphH;
285#if DEBUG_FONT_RENDERER
286                ALOGD("fitBitmap: Added to existing block: this, x, y, w, h = %p, %d, %d, %d, %d",
287                        cacheBlock, cacheBlock->mX, cacheBlock->mY,
288                        cacheBlock->mWidth, cacheBlock->mHeight);
289#endif
290            }
291
292            if (cacheBlock->mHeight < fmin(glyphH, glyphW)) {
293                // If remaining space in this block is too small to be useful, remove it
294                mCacheBlocks = CacheBlock::removeBlock(mCacheBlocks, cacheBlock);
295            }
296
297            mDirty = true;
298            const Rect r(*retOriginX - TEXTURE_BORDER_SIZE, *retOriginY - TEXTURE_BORDER_SIZE,
299                    *retOriginX + glyphW, *retOriginY + glyphH);
300            mDirtyRect.unionWith(r);
301            mNumGlyphs++;
302
303#if DEBUG_FONT_RENDERER
304            ALOGD("fitBitmap: current block list:");
305            mCacheBlocks->output();
306#endif
307
308            return true;
309        }
310        cacheBlock = cacheBlock->mNext;
311    }
312#if DEBUG_FONT_RENDERER
313    ALOGD("fitBitmap: returning false for glyph of size %d, %d", glyphW, glyphH);
314#endif
315    return false;
316}
317
318}; // namespace uirenderer
319}; // namespace android
320