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