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