19f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy/* 29f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy * Copyright (C) 2012 The Android Open Source Project 39f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy * 49f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy * Licensed under the Apache License, Version 2.0 (the "License"); 59f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy * you may not use this file except in compliance with the License. 69f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy * You may obtain a copy of the License at 79f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy * 89f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy * http://www.apache.org/licenses/LICENSE-2.0 99f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy * 109f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy * Unless required by applicable law or agreed to in writing, software 119f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy * distributed under the License is distributed on an "AS IS" BASIS, 129f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 139f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy * See the License for the specific language governing permissions and 149f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy * limitations under the License. 159f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy */ 169f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy 179f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy#include <utils/Log.h> 189f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy 199f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy#include "Debug.h" 209f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy#include "CacheTexture.h" 219f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy 229f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guynamespace android { 239f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guynamespace uirenderer { 249f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy 259f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy/////////////////////////////////////////////////////////////////////////////// 269f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy// CacheBlock 279f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy/////////////////////////////////////////////////////////////////////////////// 289f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy 299f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy/** 309f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy * Insert new block into existing linked list of blocks. Blocks are sorted in increasing-width 319f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy * order, except for the final block (the remainder space at the right, since we fill from the 329f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy * left). 339f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy */ 34e43f785b7ff3fdf75f6d1c92282ebca6db191f2fRomain GuyCacheBlock* CacheBlock::insertBlock(CacheBlock* head, CacheBlock* newBlock) { 359f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy#if DEBUG_FONT_RENDERER 369f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy ALOGD("insertBlock: this, x, y, w, h = %p, %d, %d, %d, %d", 379f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy newBlock, newBlock->mX, newBlock->mY, 389f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy newBlock->mWidth, newBlock->mHeight); 399f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy#endif 409b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 41e43f785b7ff3fdf75f6d1c92282ebca6db191f2fRomain Guy CacheBlock* currBlock = head; 42e43f785b7ff3fdf75f6d1c92282ebca6db191f2fRomain Guy CacheBlock* prevBlock = NULL; 439b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 449f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy while (currBlock && currBlock->mY != TEXTURE_BORDER_SIZE) { 459f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy if (newBlock->mWidth < currBlock->mWidth) { 469f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy newBlock->mNext = currBlock; 479f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy newBlock->mPrev = prevBlock; 489f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy currBlock->mPrev = newBlock; 499b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 509f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy if (prevBlock) { 519f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy prevBlock->mNext = newBlock; 529f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy return head; 539f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy } else { 549f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy return newBlock; 559f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy } 569f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy } 579b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 589f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy prevBlock = currBlock; 599f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy currBlock = currBlock->mNext; 609f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy } 619b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 629f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy // new block larger than all others - insert at end (but before the remainder space, if there) 639f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy newBlock->mNext = currBlock; 649f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy newBlock->mPrev = prevBlock; 659b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 669f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy if (currBlock) { 679f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy currBlock->mPrev = newBlock; 689f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy } 699b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 709f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy if (prevBlock) { 719f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy prevBlock->mNext = newBlock; 729f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy return head; 739f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy } else { 749f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy return newBlock; 759f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy } 769f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy} 779f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy 78e43f785b7ff3fdf75f6d1c92282ebca6db191f2fRomain GuyCacheBlock* CacheBlock::removeBlock(CacheBlock* head, CacheBlock* blockToRemove) { 799f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy#if DEBUG_FONT_RENDERER 809f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy ALOGD("removeBlock: this, x, y, w, h = %p, %d, %d, %d, %d", 819f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy blockToRemove, blockToRemove->mX, blockToRemove->mY, 829f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy blockToRemove->mWidth, blockToRemove->mHeight); 839f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy#endif 849b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 859f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy CacheBlock* newHead = head; 869f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy CacheBlock* nextBlock = blockToRemove->mNext; 879f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy CacheBlock* prevBlock = blockToRemove->mPrev; 889b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 899f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy if (prevBlock) { 909f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy prevBlock->mNext = nextBlock; 919f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy } else { 929f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy newHead = nextBlock; 939f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy } 949b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 959f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy if (nextBlock) { 969f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy nextBlock->mPrev = prevBlock; 979f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy } 989b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 999f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy delete blockToRemove; 1009b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 1019f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy return newHead; 1029f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy} 1039f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy 1049f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy/////////////////////////////////////////////////////////////////////////////// 1059f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy// CacheTexture 1069f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy/////////////////////////////////////////////////////////////////////////////// 1079f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy 108e43f785b7ff3fdf75f6d1c92282ebca6db191f2fRomain Guybool CacheTexture::fitBitmap(const SkGlyph& glyph, uint32_t* retOriginX, uint32_t* retOriginY) { 109e43f785b7ff3fdf75f6d1c92282ebca6db191f2fRomain Guy if (glyph.fHeight + TEXTURE_BORDER_SIZE * 2 > mHeight) { 1109f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy return false; 1119f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy } 1129f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy 1139f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy uint16_t glyphW = glyph.fWidth + TEXTURE_BORDER_SIZE; 1149f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy uint16_t glyphH = glyph.fHeight + TEXTURE_BORDER_SIZE; 1159b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 1169f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy // roundedUpW equals glyphW to the next multiple of CACHE_BLOCK_ROUNDING_SIZE. 1179f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy // This columns for glyphs that are close but not necessarily exactly the same size. It trades 1189f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy // off the loss of a few pixels for some glyphs against the ability to store more glyphs 1199f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy // of varying sizes in one block. 120e43f785b7ff3fdf75f6d1c92282ebca6db191f2fRomain Guy uint16_t roundedUpW = (glyphW + CACHE_BLOCK_ROUNDING_SIZE - 1) & -CACHE_BLOCK_ROUNDING_SIZE; 1219b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 122e43f785b7ff3fdf75f6d1c92282ebca6db191f2fRomain Guy CacheBlock* cacheBlock = mCacheBlocks; 1239f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy while (cacheBlock) { 1249f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy // Store glyph in this block iff: it fits the block's remaining space and: 1259f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy // it's the remainder space (mY == 0) or there's only enough height for this one glyph 1269f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy // or it's within ROUNDING_SIZE of the block width 1279f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy if (roundedUpW <= cacheBlock->mWidth && glyphH <= cacheBlock->mHeight && 1289f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy (cacheBlock->mY == TEXTURE_BORDER_SIZE || 1299f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy (cacheBlock->mWidth - roundedUpW < CACHE_BLOCK_ROUNDING_SIZE))) { 1309f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy if (cacheBlock->mHeight - glyphH < glyphH) { 1319f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy // Only enough space for this glyph - don't bother rounding up the width 1329f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy roundedUpW = glyphW; 1339f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy } 1349b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 1359f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy *retOriginX = cacheBlock->mX; 1369f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy *retOriginY = cacheBlock->mY; 1379b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 1389f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy // If this is the remainder space, create a new cache block for this column. Otherwise, 1399f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy // adjust the info about this column. 1409f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy if (cacheBlock->mY == TEXTURE_BORDER_SIZE) { 1419f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy uint16_t oldX = cacheBlock->mX; 1429f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy // Adjust remainder space dimensions 1439f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy cacheBlock->mWidth -= roundedUpW; 1449f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy cacheBlock->mX += roundedUpW; 1459b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 1469f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy if (mHeight - glyphH >= glyphH) { 1479f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy // There's enough height left over to create a new CacheBlock 148e43f785b7ff3fdf75f6d1c92282ebca6db191f2fRomain Guy CacheBlock* newBlock = new CacheBlock(oldX, glyphH + TEXTURE_BORDER_SIZE, 1499f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy roundedUpW, mHeight - glyphH - TEXTURE_BORDER_SIZE); 1509f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy#if DEBUG_FONT_RENDERER 1519f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy ALOGD("fitBitmap: Created new block: this, x, y, w, h = %p, %d, %d, %d, %d", 1529f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy newBlock, newBlock->mX, newBlock->mY, 1539f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy newBlock->mWidth, newBlock->mHeight); 1549f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy#endif 1559f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy mCacheBlocks = CacheBlock::insertBlock(mCacheBlocks, newBlock); 1569f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy } 1579f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy } else { 1589f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy // Insert into current column and adjust column dimensions 1599f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy cacheBlock->mY += glyphH; 1609f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy cacheBlock->mHeight -= glyphH; 1619f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy#if DEBUG_FONT_RENDERER 1629f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy ALOGD("fitBitmap: Added to existing block: this, x, y, w, h = %p, %d, %d, %d, %d", 1639f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy cacheBlock, cacheBlock->mX, cacheBlock->mY, 1649f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy cacheBlock->mWidth, cacheBlock->mHeight); 1659f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy#endif 1669f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy } 1679b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 1689f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy if (cacheBlock->mHeight < fmin(glyphH, glyphW)) { 1699f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy // If remaining space in this block is too small to be useful, remove it 1709f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy mCacheBlocks = CacheBlock::removeBlock(mCacheBlocks, cacheBlock); 1719f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy } 1729b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 1739f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy mDirty = true; 174b92d8f7979c29c7c09932578a11b2f8d6eec1d90Chet Haase const Rect r(*retOriginX - TEXTURE_BORDER_SIZE, *retOriginY - TEXTURE_BORDER_SIZE, 175b92d8f7979c29c7c09932578a11b2f8d6eec1d90Chet Haase *retOriginX + glyphW, *retOriginY + glyphH); 176b92d8f7979c29c7c09932578a11b2f8d6eec1d90Chet Haase mDirtyRect.unionWith(r); 1779b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy mNumGlyphs++; 1789b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 1799f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy#if DEBUG_FONT_RENDERER 1809f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy ALOGD("fitBitmap: current block list:"); 1819f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy mCacheBlocks->output(); 1829f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy#endif 1839b1204baf4740b4d443e72157dea98571cf84e1fRomain Guy 1849f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy return true; 1859f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy } 1869f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy cacheBlock = cacheBlock->mNext; 1879f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy } 1889f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy#if DEBUG_FONT_RENDERER 1899f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy ALOGD("fitBitmap: returning false for glyph of size %d, %d", glyphW, glyphH); 1909f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy#endif 1919f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy return false; 1929f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy} 1939f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy 1949f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy}; // namespace uirenderer 1959f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy}; // namespace android 196