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