CacheTexture.cpp revision e43f785b7ff3fdf75f6d1c92282ebca6db191f2f
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 mNumGlyphs++; 175 176#if DEBUG_FONT_RENDERER 177 ALOGD("fitBitmap: current block list:"); 178 mCacheBlocks->output(); 179#endif 180 181 return true; 182 } 183 cacheBlock = cacheBlock->mNext; 184 } 185#if DEBUG_FONT_RENDERER 186 ALOGD("fitBitmap: returning false for glyph of size %d, %d", glyphW, glyphH); 187#endif 188 return false; 189} 190 191}; // namespace uirenderer 192}; // namespace android 193