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 <utils/Log.h>
18
19#include "Debug.h"
20#include "CacheTexture.h"
21
22namespace android {
23namespace uirenderer {
24
25///////////////////////////////////////////////////////////////////////////////
26// CacheBlock
27///////////////////////////////////////////////////////////////////////////////
28
29/**
30 * Insert new block into existing linked list of blocks. Blocks are sorted in increasing-width
31 * order, except for the final block (the remainder space at the right, since we fill from the
32 * left).
33 */
34CacheBlock* CacheBlock::insertBlock(CacheBlock* head, CacheBlock* newBlock) {
35#if DEBUG_FONT_RENDERER
36    ALOGD("insertBlock: this, x, y, w, h = %p, %d, %d, %d, %d",
37            newBlock, newBlock->mX, newBlock->mY,
38            newBlock->mWidth, newBlock->mHeight);
39#endif
40
41    CacheBlock* currBlock = head;
42    CacheBlock* prevBlock = NULL;
43
44    while (currBlock && currBlock->mY != TEXTURE_BORDER_SIZE) {
45        if (newBlock->mWidth < currBlock->mWidth) {
46            newBlock->mNext = currBlock;
47            newBlock->mPrev = prevBlock;
48            currBlock->mPrev = newBlock;
49
50            if (prevBlock) {
51                prevBlock->mNext = newBlock;
52                return head;
53            } else {
54                return newBlock;
55            }
56        }
57
58        prevBlock = currBlock;
59        currBlock = currBlock->mNext;
60    }
61
62    // new block larger than all others - insert at end (but before the remainder space, if there)
63    newBlock->mNext = currBlock;
64    newBlock->mPrev = prevBlock;
65
66    if (currBlock) {
67        currBlock->mPrev = newBlock;
68    }
69
70    if (prevBlock) {
71        prevBlock->mNext = newBlock;
72        return head;
73    } else {
74        return newBlock;
75    }
76}
77
78CacheBlock* CacheBlock::removeBlock(CacheBlock* head, CacheBlock* blockToRemove) {
79#if DEBUG_FONT_RENDERER
80    ALOGD("removeBlock: this, x, y, w, h = %p, %d, %d, %d, %d",
81            blockToRemove, blockToRemove->mX, blockToRemove->mY,
82            blockToRemove->mWidth, blockToRemove->mHeight);
83#endif
84
85    CacheBlock* newHead = head;
86    CacheBlock* nextBlock = blockToRemove->mNext;
87    CacheBlock* prevBlock = blockToRemove->mPrev;
88
89    if (prevBlock) {
90        prevBlock->mNext = nextBlock;
91    } else {
92        newHead = nextBlock;
93    }
94
95    if (nextBlock) {
96        nextBlock->mPrev = prevBlock;
97    }
98
99    delete blockToRemove;
100
101    return newHead;
102}
103
104///////////////////////////////////////////////////////////////////////////////
105// CacheTexture
106///////////////////////////////////////////////////////////////////////////////
107
108bool CacheTexture::fitBitmap(const SkGlyph& glyph, uint32_t* retOriginX, uint32_t* retOriginY) {
109    if (glyph.fHeight + TEXTURE_BORDER_SIZE * 2 > mHeight) {
110        return false;
111    }
112
113    uint16_t glyphW = glyph.fWidth + TEXTURE_BORDER_SIZE;
114    uint16_t glyphH = glyph.fHeight + TEXTURE_BORDER_SIZE;
115
116    // roundedUpW equals glyphW to the next multiple of CACHE_BLOCK_ROUNDING_SIZE.
117    // This columns for glyphs that are close but not necessarily exactly the same size. It trades
118    // off the loss of a few pixels for some glyphs against the ability to store more glyphs
119    // of varying sizes in one block.
120    uint16_t roundedUpW = (glyphW + CACHE_BLOCK_ROUNDING_SIZE - 1) & -CACHE_BLOCK_ROUNDING_SIZE;
121
122    CacheBlock* cacheBlock = mCacheBlocks;
123    while (cacheBlock) {
124        // Store glyph in this block iff: it fits the block's remaining space and:
125        // it's the remainder space (mY == 0) or there's only enough height for this one glyph
126        // or it's within ROUNDING_SIZE of the block width
127        if (roundedUpW <= cacheBlock->mWidth && glyphH <= cacheBlock->mHeight &&
128                (cacheBlock->mY == TEXTURE_BORDER_SIZE ||
129                        (cacheBlock->mWidth - roundedUpW < CACHE_BLOCK_ROUNDING_SIZE))) {
130            if (cacheBlock->mHeight - glyphH < glyphH) {
131                // Only enough space for this glyph - don't bother rounding up the width
132                roundedUpW = glyphW;
133            }
134
135            *retOriginX = cacheBlock->mX;
136            *retOriginY = cacheBlock->mY;
137
138            // If this is the remainder space, create a new cache block for this column. Otherwise,
139            // adjust the info about this column.
140            if (cacheBlock->mY == TEXTURE_BORDER_SIZE) {
141                uint16_t oldX = cacheBlock->mX;
142                // Adjust remainder space dimensions
143                cacheBlock->mWidth -= roundedUpW;
144                cacheBlock->mX += roundedUpW;
145
146                if (mHeight - glyphH >= glyphH) {
147                    // There's enough height left over to create a new CacheBlock
148                    CacheBlock* newBlock = new CacheBlock(oldX, glyphH + TEXTURE_BORDER_SIZE,
149                            roundedUpW, mHeight - glyphH - TEXTURE_BORDER_SIZE);
150#if DEBUG_FONT_RENDERER
151                    ALOGD("fitBitmap: Created new block: this, x, y, w, h = %p, %d, %d, %d, %d",
152                            newBlock, newBlock->mX, newBlock->mY,
153                            newBlock->mWidth, newBlock->mHeight);
154#endif
155                    mCacheBlocks = CacheBlock::insertBlock(mCacheBlocks, newBlock);
156                }
157            } else {
158                // Insert into current column and adjust column dimensions
159                cacheBlock->mY += glyphH;
160                cacheBlock->mHeight -= glyphH;
161#if DEBUG_FONT_RENDERER
162                ALOGD("fitBitmap: Added to existing block: this, x, y, w, h = %p, %d, %d, %d, %d",
163                        cacheBlock, cacheBlock->mX, cacheBlock->mY,
164                        cacheBlock->mWidth, cacheBlock->mHeight);
165#endif
166            }
167
168            if (cacheBlock->mHeight < fmin(glyphH, glyphW)) {
169                // If remaining space in this block is too small to be useful, remove it
170                mCacheBlocks = CacheBlock::removeBlock(mCacheBlocks, cacheBlock);
171            }
172
173            mDirty = true;
174            const Rect r(*retOriginX - TEXTURE_BORDER_SIZE, *retOriginY - TEXTURE_BORDER_SIZE,
175                    *retOriginX + glyphW, *retOriginY + glyphH);
176            mDirtyRect.unionWith(r);
177            mNumGlyphs++;
178
179#if DEBUG_FONT_RENDERER
180            ALOGD("fitBitmap: current block list:");
181            mCacheBlocks->output();
182#endif
183
184            return true;
185        }
186        cacheBlock = cacheBlock->mNext;
187    }
188#if DEBUG_FONT_RENDERER
189    ALOGD("fitBitmap: returning false for glyph of size %d, %d", glyphW, glyphH);
190#endif
191    return false;
192}
193
194}; // namespace uirenderer
195}; // namespace android
196