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