1 /* 2 * Copyright 2006 The Android Open Source Project 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #include "SkStrike.h" 9 10 #include "SkGraphics.h" 11 #include "SkMakeUnique.h" 12 #include "SkMutex.h" 13 #include "SkOnce.h" 14 #include "SkPath.h" 15 #include "SkTemplates.h" 16 #include "SkTypeface.h" 17 #include <cctype> 18 19 namespace { 20 size_t compute_path_size(const SkPath& path) { 21 return sizeof(SkPath) + path.countPoints() * sizeof(SkPoint); 22 } 23 } // namespace 24 25 SkStrike::SkStrike( 26 const SkDescriptor& desc, 27 std::unique_ptr<SkScalerContext> scaler, 28 const SkFontMetrics& fontMetrics) 29 : fDesc{desc} 30 , fScalerContext{std::move(scaler)} 31 , fFontMetrics{fontMetrics} 32 , fIsSubpixel{fScalerContext->isSubpixel()} 33 , fAxisAlignment{fScalerContext->computeAxisAlignmentForHText()} 34 { 35 SkASSERT(fScalerContext != nullptr); 36 fMemoryUsed = sizeof(*this); 37 } 38 39 const SkDescriptor& SkStrike::getDescriptor() const { 40 return *fDesc.getDesc(); 41 } 42 43 #ifdef SK_DEBUG 44 #define VALIDATE() AutoValidate av(this) 45 #else 46 #define VALIDATE() 47 #endif 48 49 unsigned SkStrike::getGlyphCount() const { 50 return fScalerContext->getGlyphCount(); 51 } 52 53 int SkStrike::countCachedGlyphs() const { 54 return fGlyphMap.count(); 55 } 56 57 bool SkStrike::isGlyphCached(SkGlyphID glyphID, SkFixed x, SkFixed y) const { 58 SkPackedGlyphID packedGlyphID{glyphID, x, y}; 59 return fGlyphMap.find(packedGlyphID) != nullptr; 60 } 61 62 SkGlyph* SkStrike::getRawGlyphByID(SkPackedGlyphID id) { 63 return lookupByPackedGlyphID(id, kNothing_MetricsType); 64 } 65 66 const SkGlyph& SkStrike::getGlyphIDAdvance(uint16_t glyphID) { 67 VALIDATE(); 68 SkPackedGlyphID packedGlyphID(glyphID); 69 return *this->lookupByPackedGlyphID(packedGlyphID, kJustAdvance_MetricsType); 70 } 71 72 const SkGlyph& SkStrike::getGlyphIDMetrics(uint16_t glyphID) { 73 VALIDATE(); 74 SkPackedGlyphID packedGlyphID(glyphID); 75 return *this->lookupByPackedGlyphID(packedGlyphID, kFull_MetricsType); 76 } 77 78 const SkGlyph& SkStrike::getGlyphIDMetrics(uint16_t glyphID, SkFixed x, SkFixed y) { 79 VALIDATE(); 80 SkPackedGlyphID packedGlyphID(glyphID, x, y); 81 return *this->lookupByPackedGlyphID(packedGlyphID, kFull_MetricsType); 82 } 83 84 void SkStrike::getAdvances(SkSpan<const SkGlyphID> glyphIDs, SkPoint advances[]) { 85 for (auto glyphID : glyphIDs) { 86 auto glyph = this->getGlyphIDAdvance(glyphID); 87 *advances++ = SkPoint::Make(glyph.fAdvanceX, glyph.fAdvanceY); 88 } 89 } 90 91 SkGlyph* SkStrike::lookupByPackedGlyphID(SkPackedGlyphID packedGlyphID, MetricsType type) { 92 SkGlyph* glyphPtr = fGlyphMap.findOrNull(packedGlyphID); 93 94 if (glyphPtr == nullptr) { 95 // Glyph is not present in the stirke. Make a new glyph and fill it in. 96 97 fMemoryUsed += sizeof(SkGlyph); 98 glyphPtr = fAlloc.make<SkGlyph>(packedGlyphID); 99 fGlyphMap.set(glyphPtr); 100 101 switch (type) { 102 // * Nothing - is only used for raw glyphs. It is assumed that the advances, etc. are 103 // filled in by external code. This is used by the remote glyph cache to fill in glyphs. 104 case kNothing_MetricsType: 105 break; 106 case kJustAdvance_MetricsType: 107 fScalerContext->getAdvance(glyphPtr); 108 break; 109 case kFull_MetricsType: 110 fScalerContext->getMetrics(glyphPtr); 111 break; 112 } 113 } else { 114 // Glyph is present in strike. Make sure the glyph has the right data. 115 116 if (type == kFull_MetricsType && glyphPtr->isJustAdvance()) { 117 fScalerContext->getMetrics(glyphPtr); 118 } 119 } 120 121 return glyphPtr; 122 } 123 124 const void* SkStrike::findImage(const SkGlyph& glyph) { 125 if (glyph.fWidth > 0 && glyph.fWidth < kMaxGlyphWidth) { 126 if (nullptr == glyph.fImage) { 127 SkDEBUGCODE(SkMask::Format oldFormat = (SkMask::Format)glyph.fMaskFormat); 128 size_t size = const_cast<SkGlyph&>(glyph).allocImage(&fAlloc); 129 // check that alloc() actually succeeded 130 if (glyph.fImage) { 131 fScalerContext->getImage(glyph); 132 // TODO: the scaler may have changed the maskformat during 133 // getImage (e.g. from AA or LCD to BW) which means we may have 134 // overallocated the buffer. Check if the new computedImageSize 135 // is smaller, and if so, strink the alloc size in fImageAlloc. 136 fMemoryUsed += size; 137 } 138 SkASSERT(oldFormat == glyph.fMaskFormat); 139 } 140 } 141 return glyph.fImage; 142 } 143 144 void SkStrike::initializeImage(const volatile void* data, size_t size, SkGlyph* glyph) { 145 // Don't overwrite the image if we already have one. We could have used a fallback if the 146 // glyph was missing earlier. 147 if (glyph->fImage) return; 148 149 if (glyph->fWidth > 0 && glyph->fWidth < kMaxGlyphWidth) { 150 size_t allocSize = glyph->allocImage(&fAlloc); 151 // check that alloc() actually succeeded 152 if (glyph->fImage) { 153 SkASSERT(size == allocSize); 154 memcpy(glyph->fImage, const_cast<const void*>(data), allocSize); 155 fMemoryUsed += size; 156 } 157 } 158 } 159 160 const SkPath* SkStrike::findPath(const SkGlyph& glyph) { 161 162 if (!glyph.isEmpty()) { 163 // If the path already exists, return it. 164 if (glyph.fPathData != nullptr) { 165 if (glyph.fPathData->fHasPath) { 166 return &glyph.fPathData->fPath; 167 } 168 return nullptr; 169 } 170 171 const_cast<SkGlyph&>(glyph).addPath(fScalerContext.get(), &fAlloc); 172 if (glyph.fPathData != nullptr) { 173 fMemoryUsed += compute_path_size(glyph.fPathData->fPath); 174 } 175 176 return glyph.path(); 177 } 178 179 return nullptr; 180 } 181 182 bool SkStrike::initializePath(SkGlyph* glyph, const volatile void* data, size_t size) { 183 // Don't overwrite the path if we already have one. We could have used a fallback if the 184 // glyph was missing earlier. 185 if (glyph->fPathData) return true; 186 187 if (glyph->fWidth) { 188 SkGlyph::PathData* pathData = fAlloc.make<SkGlyph::PathData>(); 189 glyph->fPathData = pathData; 190 auto path = skstd::make_unique<SkPath>(); 191 if (!pathData->fPath.readFromMemory(const_cast<const void*>(data), size)) { 192 return false; 193 } 194 fMemoryUsed += compute_path_size(glyph->fPathData->fPath); 195 pathData->fHasPath = true; 196 } 197 198 return true; 199 } 200 201 bool SkStrike::belongsToCache(const SkGlyph* glyph) const { 202 return glyph && fGlyphMap.findOrNull(glyph->getPackedID()) == glyph; 203 } 204 205 const SkGlyph* SkStrike::getCachedGlyphAnySubPix(SkGlyphID glyphID, 206 SkPackedGlyphID vetoID) const { 207 for (SkFixed subY = 0; subY < SK_Fixed1; subY += SK_FixedQuarter) { 208 for (SkFixed subX = 0; subX < SK_Fixed1; subX += SK_FixedQuarter) { 209 SkPackedGlyphID packedGlyphID{glyphID, subX, subY}; 210 if (packedGlyphID == vetoID) continue; 211 if (SkGlyph* glyphPtr = fGlyphMap.findOrNull(packedGlyphID)) { 212 return glyphPtr; 213 } 214 } 215 } 216 217 return nullptr; 218 } 219 220 void SkStrike::initializeGlyphFromFallback(SkGlyph* glyph, const SkGlyph& fallback) { 221 fMemoryUsed += glyph->copyImageData(fallback, &fAlloc); 222 } 223 224 SkVector SkStrike::rounding() const { 225 return SkStrikeCommon::PixelRounding(fIsSubpixel, fAxisAlignment); 226 } 227 228 const SkGlyph& SkStrike::getGlyphMetrics(SkGlyphID glyphID, SkPoint position) { 229 if (!fIsSubpixel) { 230 return this->getGlyphIDMetrics(glyphID); 231 } else { 232 SkIPoint lookupPosition = SkStrikeCommon::SubpixelLookup(fAxisAlignment, position); 233 234 return this->getGlyphIDMetrics(glyphID, lookupPosition.x(), lookupPosition.y()); 235 } 236 } 237 238 // N.B. This glyphMetrics call culls all the glyphs which will not display based on a non-finite 239 // position or that there are no mask pixels. 240 int SkStrike::glyphMetrics(const SkGlyphID glyphIDs[], 241 const SkPoint positions[], 242 int n, 243 SkGlyphPos result[]) { 244 245 int drawableGlyphCount = 0; 246 const SkPoint* posCursor = positions; 247 for (int i = 0; i < n; i++) { 248 SkPoint glyphPos = *posCursor++; 249 if (SkScalarsAreFinite(glyphPos.x(), glyphPos.y())) { 250 const SkGlyph& glyph = this->getGlyphMetrics(glyphIDs[i], glyphPos); 251 if (!glyph.isEmpty()) { 252 result[drawableGlyphCount++] = {&glyph, glyphPos}; 253 } 254 } 255 } 256 257 return drawableGlyphCount; 258 } 259 260 #include "../pathops/SkPathOpsCubic.h" 261 #include "../pathops/SkPathOpsQuad.h" 262 263 static bool quad_in_bounds(const SkScalar* pts, const SkScalar bounds[2]) { 264 SkScalar min = SkTMin(SkTMin(pts[0], pts[2]), pts[4]); 265 if (bounds[1] < min) { 266 return false; 267 } 268 SkScalar max = SkTMax(SkTMax(pts[0], pts[2]), pts[4]); 269 return bounds[0] < max; 270 } 271 272 static bool cubic_in_bounds(const SkScalar* pts, const SkScalar bounds[2]) { 273 SkScalar min = SkTMin(SkTMin(SkTMin(pts[0], pts[2]), pts[4]), pts[6]); 274 if (bounds[1] < min) { 275 return false; 276 } 277 SkScalar max = SkTMax(SkTMax(SkTMax(pts[0], pts[2]), pts[4]), pts[6]); 278 return bounds[0] < max; 279 } 280 281 void SkStrike::OffsetResults(const SkGlyph::Intercept* intercept, SkScalar scale, 282 SkScalar xPos, SkScalar* array, int* count) { 283 if (array) { 284 array += *count; 285 for (int index = 0; index < 2; index++) { 286 *array++ = intercept->fInterval[index] * scale + xPos; 287 } 288 } 289 *count += 2; 290 } 291 292 void SkStrike::AddInterval(SkScalar val, SkGlyph::Intercept* intercept) { 293 intercept->fInterval[0] = SkTMin(intercept->fInterval[0], val); 294 intercept->fInterval[1] = SkTMax(intercept->fInterval[1], val); 295 } 296 297 void SkStrike::AddPoints(const SkPoint* pts, int ptCount, const SkScalar bounds[2], 298 bool yAxis, SkGlyph::Intercept* intercept) { 299 for (int i = 0; i < ptCount; ++i) { 300 SkScalar val = *(&pts[i].fY - yAxis); 301 if (bounds[0] < val && val < bounds[1]) { 302 AddInterval(*(&pts[i].fX + yAxis), intercept); 303 } 304 } 305 } 306 307 void SkStrike::AddLine(const SkPoint pts[2], SkScalar axis, bool yAxis, 308 SkGlyph::Intercept* intercept) { 309 SkScalar t = yAxis ? sk_ieee_float_divide(axis - pts[0].fX, pts[1].fX - pts[0].fX) 310 : sk_ieee_float_divide(axis - pts[0].fY, pts[1].fY - pts[0].fY); 311 if (0 <= t && t < 1) { // this handles divide by zero above 312 AddInterval(yAxis ? pts[0].fY + t * (pts[1].fY - pts[0].fY) 313 : pts[0].fX + t * (pts[1].fX - pts[0].fX), intercept); 314 } 315 } 316 317 void SkStrike::AddQuad(const SkPoint pts[3], SkScalar axis, bool yAxis, 318 SkGlyph::Intercept* intercept) { 319 SkDQuad quad; 320 quad.set(pts); 321 double roots[2]; 322 int count = yAxis ? quad.verticalIntersect(axis, roots) 323 : quad.horizontalIntersect(axis, roots); 324 while (--count >= 0) { 325 SkPoint pt = quad.ptAtT(roots[count]).asSkPoint(); 326 AddInterval(*(&pt.fX + yAxis), intercept); 327 } 328 } 329 330 void SkStrike::AddCubic(const SkPoint pts[4], SkScalar axis, bool yAxis, 331 SkGlyph::Intercept* intercept) { 332 SkDCubic cubic; 333 cubic.set(pts); 334 double roots[3]; 335 int count = yAxis ? cubic.verticalIntersect(axis, roots) 336 : cubic.horizontalIntersect(axis, roots); 337 while (--count >= 0) { 338 SkPoint pt = cubic.ptAtT(roots[count]).asSkPoint(); 339 AddInterval(*(&pt.fX + yAxis), intercept); 340 } 341 } 342 343 const SkGlyph::Intercept* SkStrike::MatchBounds(const SkGlyph* glyph, 344 const SkScalar bounds[2]) { 345 if (!glyph->fPathData) { 346 return nullptr; 347 } 348 const SkGlyph::Intercept* intercept = glyph->fPathData->fIntercept; 349 while (intercept) { 350 if (bounds[0] == intercept->fBounds[0] && bounds[1] == intercept->fBounds[1]) { 351 return intercept; 352 } 353 intercept = intercept->fNext; 354 } 355 return nullptr; 356 } 357 358 void SkStrike::findIntercepts(const SkScalar bounds[2], SkScalar scale, SkScalar xPos, 359 bool yAxis, SkGlyph* glyph, SkScalar* array, int* count) { 360 const SkGlyph::Intercept* match = MatchBounds(glyph, bounds); 361 362 if (match) { 363 if (match->fInterval[0] < match->fInterval[1]) { 364 OffsetResults(match, scale, xPos, array, count); 365 } 366 return; 367 } 368 369 SkGlyph::Intercept* intercept = fAlloc.make<SkGlyph::Intercept>(); 370 intercept->fNext = glyph->fPathData->fIntercept; 371 intercept->fBounds[0] = bounds[0]; 372 intercept->fBounds[1] = bounds[1]; 373 intercept->fInterval[0] = SK_ScalarMax; 374 intercept->fInterval[1] = SK_ScalarMin; 375 glyph->fPathData->fIntercept = intercept; 376 const SkPath* path = &(glyph->fPathData->fPath); 377 const SkRect& pathBounds = path->getBounds(); 378 if (*(&pathBounds.fBottom - yAxis) < bounds[0] || bounds[1] < *(&pathBounds.fTop - yAxis)) { 379 return; 380 } 381 SkPath::Iter iter(*path, false); 382 SkPoint pts[4]; 383 SkPath::Verb verb; 384 while (SkPath::kDone_Verb != (verb = iter.next(pts))) { 385 switch (verb) { 386 case SkPath::kMove_Verb: 387 break; 388 case SkPath::kLine_Verb: 389 AddLine(pts, bounds[0], yAxis, intercept); 390 AddLine(pts, bounds[1], yAxis, intercept); 391 AddPoints(pts, 2, bounds, yAxis, intercept); 392 break; 393 case SkPath::kQuad_Verb: 394 if (!quad_in_bounds(&pts[0].fY - yAxis, bounds)) { 395 break; 396 } 397 AddQuad(pts, bounds[0], yAxis, intercept); 398 AddQuad(pts, bounds[1], yAxis, intercept); 399 AddPoints(pts, 3, bounds, yAxis, intercept); 400 break; 401 case SkPath::kConic_Verb: 402 SkASSERT(0); // no support for text composed of conics 403 break; 404 case SkPath::kCubic_Verb: 405 if (!cubic_in_bounds(&pts[0].fY - yAxis, bounds)) { 406 break; 407 } 408 AddCubic(pts, bounds[0], yAxis, intercept); 409 AddCubic(pts, bounds[1], yAxis, intercept); 410 AddPoints(pts, 4, bounds, yAxis, intercept); 411 break; 412 case SkPath::kClose_Verb: 413 break; 414 default: 415 SkASSERT(0); 416 break; 417 } 418 } 419 if (intercept->fInterval[0] >= intercept->fInterval[1]) { 420 intercept->fInterval[0] = SK_ScalarMax; 421 intercept->fInterval[1] = SK_ScalarMin; 422 return; 423 } 424 OffsetResults(intercept, scale, xPos, array, count); 425 } 426 427 void SkStrike::dump() const { 428 const SkTypeface* face = fScalerContext->getTypeface(); 429 const SkScalerContextRec& rec = fScalerContext->getRec(); 430 SkMatrix matrix; 431 rec.getSingleMatrix(&matrix); 432 matrix.preScale(SkScalarInvert(rec.fTextSize), SkScalarInvert(rec.fTextSize)); 433 SkString name; 434 face->getFamilyName(&name); 435 436 SkString msg; 437 SkFontStyle style = face->fontStyle(); 438 msg.printf("cache typeface:%x %25s:(%d,%d,%d)\n %s glyphs:%3d", 439 face->uniqueID(), name.c_str(), style.weight(), style.width(), style.slant(), 440 rec.dump().c_str(), fGlyphMap.count()); 441 SkDebugf("%s\n", msg.c_str()); 442 } 443 444 bool SkStrike::decideCouldDrawFromPath(const SkGlyph& glyph) { 445 return !glyph.isEmpty() && this->findPath(glyph) != nullptr; 446 } 447 448 void SkStrike::onAboutToExitScope() { } 449 450 #ifdef SK_DEBUG 451 void SkStrike::forceValidate() const { 452 size_t memoryUsed = sizeof(*this); 453 fGlyphMap.foreach ([&memoryUsed](const SkGlyph* glyphPtr) { 454 memoryUsed += sizeof(SkGlyph); 455 if (glyphPtr->fImage) { 456 memoryUsed += glyphPtr->computeImageSize(); 457 } 458 if (glyphPtr->fPathData) { 459 memoryUsed += compute_path_size(glyphPtr->fPathData->fPath); 460 } 461 }); 462 SkASSERT(fMemoryUsed == memoryUsed); 463 } 464 465 void SkStrike::validate() const { 466 #ifdef SK_DEBUG_GLYPH_CACHE 467 forceValidate(); 468 #endif 469 } 470 #endif // SK_DEBUG 471 472 473