TextLayoutCache.cpp revision 43e4985abfcb69db8fb39a95794eb34a2f142214 
1/*
2 * Copyright (C) 2011 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#define LOG_TAG "TextLayoutCache"
18
19#include "TextLayoutCache.h"
20#include "TextLayout.h"
21#include "SkFontHost.h"
22#include <unicode/unistr.h>
23#include <unicode/normlzr.h>
24
25extern "C" {
26  #include "harfbuzz-unicode.h"
27}
28
29namespace android {
30
31//--------------------------------------------------------------------------------------------------
32// Using DroidSansArabic for shaping Arabic with Harfbuzz because its metrics are more compatible
33// with the "Roboto" metrics (compared to DroidNaskh-Regular). When we will have an Arabic font
34// whose metrics are similar to the Roboto ones, then we will need to use it for shaping.
35#define TYPEFACE_ARABIC "/system/fonts/DroidSansArabic.ttf"
36#define TYPE_FACE_HEBREW_REGULAR "/system/fonts/DroidSansHebrew-Regular.ttf"
37#define TYPE_FACE_HEBREW_BOLD "/system/fonts/DroidSansHebrew-Bold.ttf"
38#define TYPEFACE_BENGALI "/system/fonts/Lohit-Bengali.ttf"
39#define TYPEFACE_DEVANAGARI "/system/fonts/Lohit-Devanagari.ttf"
40#define TYPEFACE_TAMIL "/system/fonts/Lohit-Tamil.ttf"
41#define TYPEFACE_THAI "/system/fonts/DroidSansThai.ttf"
42
43ANDROID_SINGLETON_STATIC_INSTANCE(TextLayoutEngine);
44
45static KeyedVector<UChar, UChar> gBidiMirrored;
46
47//--------------------------------------------------------------------------------------------------
48
49TextLayoutCache::TextLayoutCache(TextLayoutShaper* shaper) :
50        mShaper(shaper),
51        mCache(GenerationCache<TextLayoutCacheKey, sp<TextLayoutValue> >::kUnlimitedCapacity),
52        mSize(0), mMaxSize(MB(DEFAULT_TEXT_LAYOUT_CACHE_SIZE_IN_MB)),
53        mCacheHitCount(0), mNanosecondsSaved(0) {
54    init();
55}
56
57TextLayoutCache::~TextLayoutCache() {
58    mCache.clear();
59}
60
61void TextLayoutCache::init() {
62    mCache.setOnEntryRemovedListener(this);
63
64    mDebugLevel = readRtlDebugLevel();
65    mDebugEnabled = mDebugLevel & kRtlDebugCaches;
66    ALOGD("Using debug level = %d - Debug Enabled = %d", mDebugLevel, mDebugEnabled);
67
68    mCacheStartTime = systemTime(SYSTEM_TIME_MONOTONIC);
69
70    if (mDebugEnabled) {
71        ALOGD("Initialization is done - Start time = %lld", mCacheStartTime);
72    }
73
74    mInitialized = true;
75}
76
77/**
78 *  Callbacks
79 */
80void TextLayoutCache::operator()(TextLayoutCacheKey& text, sp<TextLayoutValue>& desc) {
81    size_t totalSizeToDelete = text.getSize() + desc->getSize();
82    mSize -= totalSizeToDelete;
83    if (mDebugEnabled) {
84        ALOGD("Cache value %p deleted, size = %d", desc.get(), totalSizeToDelete);
85    }
86}
87
88/*
89 * Cache clearing
90 */
91void TextLayoutCache::clear() {
92    mCache.clear();
93}
94
95/*
96 * Caching
97 */
98sp<TextLayoutValue> TextLayoutCache::getValue(const SkPaint* paint,
99            const jchar* text, jint start, jint count, jint contextCount, jint dirFlags) {
100    AutoMutex _l(mLock);
101    nsecs_t startTime = 0;
102    if (mDebugEnabled) {
103        startTime = systemTime(SYSTEM_TIME_MONOTONIC);
104    }
105
106    // Create the key
107    TextLayoutCacheKey key(paint, text, start, count, contextCount, dirFlags);
108
109    // Get value from cache if possible
110    sp<TextLayoutValue> value = mCache.get(key);
111
112    // Value not found for the key, we need to add a new value in the cache
113    if (value == NULL) {
114        if (mDebugEnabled) {
115            startTime = systemTime(SYSTEM_TIME_MONOTONIC);
116        }
117
118        value = new TextLayoutValue(contextCount);
119
120        // Compute advances and store them
121        mShaper->computeValues(value.get(), paint,
122                reinterpret_cast<const UChar*>(text), start, count,
123                size_t(contextCount), int(dirFlags));
124
125        if (mDebugEnabled) {
126            value->setElapsedTime(systemTime(SYSTEM_TIME_MONOTONIC) - startTime);
127        }
128
129        // Don't bother to add in the cache if the entry is too big
130        size_t size = key.getSize() + value->getSize();
131        if (size <= mMaxSize) {
132            // Cleanup to make some room if needed
133            if (mSize + size > mMaxSize) {
134                if (mDebugEnabled) {
135                    ALOGD("Need to clean some entries for making some room for a new entry");
136                }
137                while (mSize + size > mMaxSize) {
138                    // This will call the callback
139                    bool removedOne = mCache.removeOldest();
140                    LOG_ALWAYS_FATAL_IF(!removedOne, "The cache is non-empty but we "
141                            "failed to remove the oldest entry.  "
142                            "mSize = %u, size = %u, mMaxSize = %u, mCache.size() = %u",
143                            mSize, size, mMaxSize, mCache.size());
144                }
145            }
146
147            // Update current cache size
148            mSize += size;
149
150            // Copy the text when we insert the new entry
151            key.internalTextCopy();
152
153            bool putOne = mCache.put(key, value);
154            LOG_ALWAYS_FATAL_IF(!putOne, "Failed to put an entry into the cache.  "
155                    "This indicates that the cache already has an entry with the "
156                    "same key but it should not since we checked earlier!"
157                    " - start = %d, count = %d, contextCount = %d - Text = '%s'",
158                    start, count, contextCount, String8(text + start, count).string());
159
160            if (mDebugEnabled) {
161                nsecs_t totalTime = systemTime(SYSTEM_TIME_MONOTONIC) - startTime;
162                ALOGD("CACHE MISS: Added entry %p "
163                        "with start = %d, count = %d, contextCount = %d, "
164                        "entry size %d bytes, remaining space %d bytes"
165                        " - Compute time %0.6f ms - Put time %0.6f ms - Text = '%s'",
166                        value.get(), start, count, contextCount, size, mMaxSize - mSize,
167                        value->getElapsedTime() * 0.000001f,
168                        (totalTime - value->getElapsedTime()) * 0.000001f,
169                        String8(text + start, count).string());
170            }
171        } else {
172            if (mDebugEnabled) {
173                ALOGD("CACHE MISS: Calculated but not storing entry because it is too big "
174                        "with start = %d, count = %d, contextCount = %d, "
175                        "entry size %d bytes, remaining space %d bytes"
176                        " - Compute time %0.6f ms - Text = '%s'",
177                        start, count, contextCount, size, mMaxSize - mSize,
178                        value->getElapsedTime() * 0.000001f,
179                        String8(text + start, count).string());
180            }
181        }
182    } else {
183        // This is a cache hit, just log timestamp and user infos
184        if (mDebugEnabled) {
185            nsecs_t elapsedTimeThruCacheGet = systemTime(SYSTEM_TIME_MONOTONIC) - startTime;
186            mNanosecondsSaved += (value->getElapsedTime() - elapsedTimeThruCacheGet);
187            ++mCacheHitCount;
188
189            if (value->getElapsedTime() > 0) {
190                float deltaPercent = 100 * ((value->getElapsedTime() - elapsedTimeThruCacheGet)
191                        / ((float)value->getElapsedTime()));
192                ALOGD("CACHE HIT #%d with start = %d, count = %d, contextCount = %d"
193                        "- Compute time %0.6f ms - "
194                        "Cache get time %0.6f ms - Gain in percent: %2.2f - Text = '%s'",
195                        mCacheHitCount, start, count, contextCount,
196                        value->getElapsedTime() * 0.000001f,
197                        elapsedTimeThruCacheGet * 0.000001f,
198                        deltaPercent,
199                        String8(text + start, count).string());
200            }
201            if (mCacheHitCount % DEFAULT_DUMP_STATS_CACHE_HIT_INTERVAL == 0) {
202                dumpCacheStats();
203            }
204        }
205    }
206    return value;
207}
208
209void TextLayoutCache::dumpCacheStats() {
210    float remainingPercent = 100 * ((mMaxSize - mSize) / ((float)mMaxSize));
211    float timeRunningInSec = (systemTime(SYSTEM_TIME_MONOTONIC) - mCacheStartTime) / 1000000000;
212
213    size_t bytes = 0;
214    size_t cacheSize = mCache.size();
215    for (size_t i = 0; i < cacheSize; i++) {
216        bytes += mCache.getKeyAt(i).getSize() + mCache.getValueAt(i)->getSize();
217    }
218
219    ALOGD("------------------------------------------------");
220    ALOGD("Cache stats");
221    ALOGD("------------------------------------------------");
222    ALOGD("pid       : %d", getpid());
223    ALOGD("running   : %.0f seconds", timeRunningInSec);
224    ALOGD("entries   : %d", cacheSize);
225    ALOGD("max size  : %d bytes", mMaxSize);
226    ALOGD("used      : %d bytes according to mSize, %d bytes actual", mSize, bytes);
227    ALOGD("remaining : %d bytes or %2.2f percent", mMaxSize - mSize, remainingPercent);
228    ALOGD("hits      : %d", mCacheHitCount);
229    ALOGD("saved     : %0.6f ms", mNanosecondsSaved * 0.000001f);
230    ALOGD("------------------------------------------------");
231}
232
233/**
234 * TextLayoutCacheKey
235 */
236TextLayoutCacheKey::TextLayoutCacheKey(): text(NULL), start(0), count(0), contextCount(0),
237        dirFlags(0), typeface(NULL), textSize(0), textSkewX(0), textScaleX(0), flags(0),
238        hinting(SkPaint::kNo_Hinting)  {
239}
240
241TextLayoutCacheKey::TextLayoutCacheKey(const SkPaint* paint, const UChar* text,
242        size_t start, size_t count, size_t contextCount, int dirFlags) :
243            text(text), start(start), count(count), contextCount(contextCount),
244            dirFlags(dirFlags) {
245    typeface = paint->getTypeface();
246    textSize = paint->getTextSize();
247    textSkewX = paint->getTextSkewX();
248    textScaleX = paint->getTextScaleX();
249    flags = paint->getFlags();
250    hinting = paint->getHinting();
251}
252
253TextLayoutCacheKey::TextLayoutCacheKey(const TextLayoutCacheKey& other) :
254        text(NULL),
255        textCopy(other.textCopy),
256        start(other.start),
257        count(other.count),
258        contextCount(other.contextCount),
259        dirFlags(other.dirFlags),
260        typeface(other.typeface),
261        textSize(other.textSize),
262        textSkewX(other.textSkewX),
263        textScaleX(other.textScaleX),
264        flags(other.flags),
265        hinting(other.hinting) {
266    if (other.text) {
267        textCopy.setTo(other.text, other.contextCount);
268    }
269}
270
271int TextLayoutCacheKey::compare(const TextLayoutCacheKey& lhs, const TextLayoutCacheKey& rhs) {
272    int deltaInt = lhs.start - rhs.start;
273    if (deltaInt != 0) return (deltaInt);
274
275    deltaInt = lhs.count - rhs.count;
276    if (deltaInt != 0) return (deltaInt);
277
278    deltaInt = lhs.contextCount - rhs.contextCount;
279    if (deltaInt != 0) return (deltaInt);
280
281    if (lhs.typeface < rhs.typeface) return -1;
282    if (lhs.typeface > rhs.typeface) return +1;
283
284    if (lhs.textSize < rhs.textSize) return -1;
285    if (lhs.textSize > rhs.textSize) return +1;
286
287    if (lhs.textSkewX < rhs.textSkewX) return -1;
288    if (lhs.textSkewX > rhs.textSkewX) return +1;
289
290    if (lhs.textScaleX < rhs.textScaleX) return -1;
291    if (lhs.textScaleX > rhs.textScaleX) return +1;
292
293    deltaInt = lhs.flags - rhs.flags;
294    if (deltaInt != 0) return (deltaInt);
295
296    deltaInt = lhs.hinting - rhs.hinting;
297    if (deltaInt != 0) return (deltaInt);
298
299    deltaInt = lhs.dirFlags - rhs.dirFlags;
300    if (deltaInt) return (deltaInt);
301
302    return memcmp(lhs.getText(), rhs.getText(), lhs.contextCount * sizeof(UChar));
303}
304
305void TextLayoutCacheKey::internalTextCopy() {
306    textCopy.setTo(text, contextCount);
307    text = NULL;
308}
309
310size_t TextLayoutCacheKey::getSize() const {
311    return sizeof(TextLayoutCacheKey) + sizeof(UChar) * contextCount;
312}
313
314/**
315 * TextLayoutCacheValue
316 */
317TextLayoutValue::TextLayoutValue(size_t contextCount) :
318        mTotalAdvance(0), mElapsedTime(0) {
319    // Give a hint for advances and glyphs vectors size
320    mAdvances.setCapacity(contextCount);
321    mGlyphs.setCapacity(contextCount);
322}
323
324size_t TextLayoutValue::getSize() const {
325    return sizeof(TextLayoutValue) + sizeof(jfloat) * mAdvances.capacity() +
326            sizeof(jchar) * mGlyphs.capacity();
327}
328
329void TextLayoutValue::setElapsedTime(uint32_t time) {
330    mElapsedTime = time;
331}
332
333uint32_t TextLayoutValue::getElapsedTime() {
334    return mElapsedTime;
335}
336
337TextLayoutShaper::TextLayoutShaper() : mShaperItemGlyphArraySize(0) {
338    mDefaultTypeface = SkFontHost::CreateTypeface(NULL, NULL, NULL, 0, SkTypeface::kNormal);
339    mArabicTypeface = NULL;
340    mHebrewRegularTypeface = NULL;
341    mHebrewBoldTypeface = NULL;
342    mBengaliTypeface = NULL;
343    mThaiTypeface = NULL;
344    mDevanagariTypeface = NULL;
345    mTamilTypeface = NULL;
346
347    mFontRec.klass = &harfbuzzSkiaClass;
348    mFontRec.userData = 0;
349
350    // The values which harfbuzzSkiaClass returns are already scaled to
351    // pixel units, so we just set all these to one to disable further
352    // scaling.
353    mFontRec.x_ppem = 1;
354    mFontRec.y_ppem = 1;
355    mFontRec.x_scale = 1;
356    mFontRec.y_scale = 1;
357
358    memset(&mShaperItem, 0, sizeof(mShaperItem));
359
360    mShaperItem.font = &mFontRec;
361    mShaperItem.font->userData = &mShapingPaint;
362
363    // Fill the BiDi mirrored chars map
364    // See: http://www.unicode.org/Public/6.0.0/ucd/extracted/DerivedBinaryProperties.txt
365    gBidiMirrored.add('(', ')');
366    gBidiMirrored.add(')', '(');
367    gBidiMirrored.add('[', ']');
368    gBidiMirrored.add(']', '[');
369    gBidiMirrored.add('{', '}');
370    gBidiMirrored.add('}', '{');
371    gBidiMirrored.add('<', '>');
372    gBidiMirrored.add('>', '<');
373    gBidiMirrored.add(0x00ab, 0x00bb); // LEFT-POINTING DOUBLE ANGLE QUOTATION MARK
374    gBidiMirrored.add(0x00bb, 0x00ab); // RIGHT-POINTING DOUBLE ANGLE QUOTATION MARK
375    gBidiMirrored.add(0x2039, 0x203a); // SINGLE LEFT-POINTING ANGLE QUOTATION MARK
376    gBidiMirrored.add(0x203a, 0x2039); // SINGLE RIGHT-POINTING ANGLE QUOTATION MARK
377    gBidiMirrored.add(0x2264, 0x2265); // LESS-THAN OR EQUAL TO
378    gBidiMirrored.add(0x2265, 0x2264); // GREATER-THAN OR EQUAL TO
379}
380
381TextLayoutShaper::~TextLayoutShaper() {
382    SkSafeUnref(mDefaultTypeface);
383    SkSafeUnref(mArabicTypeface);
384    SkSafeUnref(mHebrewRegularTypeface);
385    SkSafeUnref(mHebrewBoldTypeface);
386    SkSafeUnref(mBengaliTypeface);
387    SkSafeUnref(mThaiTypeface);
388    SkSafeUnref(mDevanagariTypeface);
389    SkSafeUnref(mTamilTypeface);
390    deleteShaperItemGlyphArrays();
391}
392
393void TextLayoutShaper::computeValues(TextLayoutValue* value, const SkPaint* paint, const UChar* chars,
394        size_t start, size_t count, size_t contextCount, int dirFlags) {
395
396    computeValues(paint, chars, start, count, contextCount, dirFlags,
397            &value->mAdvances, &value->mTotalAdvance, &value->mGlyphs);
398#if DEBUG_ADVANCES
399    ALOGD("Advances - start = %d, count = %d, contextCount = %d, totalAdvance = %f", start, count,
400            contextCount, value->mTotalAdvance);
401#endif
402}
403
404void TextLayoutShaper::computeValues(const SkPaint* paint, const UChar* chars,
405        size_t start, size_t count, size_t contextCount, int dirFlags,
406        Vector<jfloat>* const outAdvances, jfloat* outTotalAdvance,
407        Vector<jchar>* const outGlyphs) {
408        if (!count) {
409            *outTotalAdvance = 0;
410            return;
411        }
412
413        UBiDiLevel bidiReq = 0;
414        bool forceLTR = false;
415        bool forceRTL = false;
416
417        switch (dirFlags) {
418            case kBidi_LTR: bidiReq = 0; break; // no ICU constant, canonical LTR level
419            case kBidi_RTL: bidiReq = 1; break; // no ICU constant, canonical RTL level
420            case kBidi_Default_LTR: bidiReq = UBIDI_DEFAULT_LTR; break;
421            case kBidi_Default_RTL: bidiReq = UBIDI_DEFAULT_RTL; break;
422            case kBidi_Force_LTR: forceLTR = true; break; // every char is LTR
423            case kBidi_Force_RTL: forceRTL = true; break; // every char is RTL
424        }
425
426        bool useSingleRun = false;
427        bool isRTL = forceRTL;
428        if (forceLTR || forceRTL) {
429            useSingleRun = true;
430        } else {
431            UBiDi* bidi = ubidi_open();
432            if (bidi) {
433                UErrorCode status = U_ZERO_ERROR;
434#if DEBUG_GLYPHS
435                ALOGD("******** ComputeValues -- start");
436                ALOGD("      -- string = '%s'", String8(chars + start, count).string());
437                ALOGD("      -- start = %d", start);
438                ALOGD("      -- count = %d", count);
439                ALOGD("      -- contextCount = %d", contextCount);
440                ALOGD("      -- bidiReq = %d", bidiReq);
441#endif
442                ubidi_setPara(bidi, chars, contextCount, bidiReq, NULL, &status);
443                if (U_SUCCESS(status)) {
444                    int paraDir = ubidi_getParaLevel(bidi) & kDirection_Mask; // 0 if ltr, 1 if rtl
445                    ssize_t rc = ubidi_countRuns(bidi, &status);
446#if DEBUG_GLYPHS
447                    ALOGD("      -- dirFlags = %d", dirFlags);
448                    ALOGD("      -- paraDir = %d", paraDir);
449                    ALOGD("      -- run-count = %d", int(rc));
450#endif
451                    if (U_SUCCESS(status) && rc == 1) {
452                        // Normal case: one run, status is ok
453                        isRTL = (paraDir == 1);
454                        useSingleRun = true;
455                    } else if (!U_SUCCESS(status) || rc < 1) {
456                        ALOGW("Need to force to single run -- string = '%s',"
457                                " status = %d, rc = %d",
458                                String8(chars + start, count).string(), status, int(rc));
459                        isRTL = (paraDir == 1);
460                        useSingleRun = true;
461                    } else {
462                        int32_t end = start + count;
463                        for (size_t i = 0; i < size_t(rc); ++i) {
464                            int32_t startRun = -1;
465                            int32_t lengthRun = -1;
466                            UBiDiDirection runDir = ubidi_getVisualRun(bidi, i, &startRun, &lengthRun);
467
468                            if (startRun == -1 || lengthRun == -1) {
469                                // Something went wrong when getting the visual run, need to clear
470                                // already computed data before doing a single run pass
471                                ALOGW("Visual run is not valid");
472                                outGlyphs->clear();
473                                outAdvances->clear();
474                                *outTotalAdvance = 0;
475                                isRTL = (paraDir == 1);
476                                useSingleRun = true;
477                                break;
478                            }
479
480                            if (startRun >= end) {
481                                continue;
482                            }
483                            int32_t endRun = startRun + lengthRun;
484                            if (endRun <= int32_t(start)) {
485                                continue;
486                            }
487                            if (startRun < int32_t(start)) {
488                                startRun = int32_t(start);
489                            }
490                            if (endRun > end) {
491                                endRun = end;
492                            }
493
494                            lengthRun = endRun - startRun;
495                            isRTL = (runDir == UBIDI_RTL);
496                            jfloat runTotalAdvance = 0;
497#if DEBUG_GLYPHS
498                            ALOGD("Processing Bidi Run = %d -- run-start = %d, run-len = %d, isRTL = %d",
499                                    i, startRun, lengthRun, isRTL);
500#endif
501                            computeRunValues(paint, chars + startRun, lengthRun, isRTL,
502                                    outAdvances, &runTotalAdvance, outGlyphs);
503
504                            *outTotalAdvance += runTotalAdvance;
505                        }
506                    }
507                } else {
508                    ALOGW("Cannot set Para");
509                    useSingleRun = true;
510                    isRTL = (bidiReq = 1) || (bidiReq = UBIDI_DEFAULT_RTL);
511                }
512                ubidi_close(bidi);
513            } else {
514                ALOGW("Cannot ubidi_open()");
515                useSingleRun = true;
516                isRTL = (bidiReq = 1) || (bidiReq = UBIDI_DEFAULT_RTL);
517            }
518        }
519
520        // Default single run case
521        if (useSingleRun){
522#if DEBUG_GLYPHS
523            ALOGD("Using a SINGLE BiDi Run "
524                    "-- run-start = %d, run-len = %d, isRTL = %d", start, count, isRTL);
525#endif
526            computeRunValues(paint, chars + start, count, isRTL,
527                    outAdvances, outTotalAdvance, outGlyphs);
528        }
529
530#if DEBUG_GLYPHS
531        ALOGD("      -- Total returned glyphs-count = %d", outGlyphs->size());
532        ALOGD("******** ComputeValues -- end");
533#endif
534}
535
536static void logGlyphs(HB_ShaperItem shaperItem) {
537    ALOGD("         -- glyphs count=%d", shaperItem.num_glyphs);
538    for (size_t i = 0; i < shaperItem.num_glyphs; i++) {
539        ALOGD("         -- glyph[%d] = %d, offset.x = %0.2f, offset.y = %0.2f", i,
540                shaperItem.glyphs[i],
541                HBFixedToFloat(shaperItem.offsets[i].x),
542                HBFixedToFloat(shaperItem.offsets[i].y));
543    }
544}
545
546void TextLayoutShaper::computeRunValues(const SkPaint* paint, const UChar* chars,
547        size_t count, bool isRTL,
548        Vector<jfloat>* const outAdvances, jfloat* outTotalAdvance,
549        Vector<jchar>* const outGlyphs) {
550    if (!count) {
551        // We cannot shape an empty run.
552        *outTotalAdvance = 0;
553        return;
554    }
555
556    UErrorCode error = U_ZERO_ERROR;
557    bool useNormalizedString = false;
558    for (ssize_t i = count - 1; i >= 0; --i) {
559        UChar ch1 = chars[i];
560        if (::ublock_getCode(ch1) == UBLOCK_COMBINING_DIACRITICAL_MARKS) {
561            // So we have found a diacritic, let's get now the main code point which is paired
562            // with it. As we can have several diacritics in a row, we need to iterate back again
563#if DEBUG_GLYPHS
564            ALOGD("The BiDi run '%s' is containing a Diacritic at position %d",
565                    String8(chars, count).string(), int(i));
566#endif
567            ssize_t j = i - 1;
568            for (; j >= 0;  --j) {
569                UChar ch2 = chars[j];
570                if (::ublock_getCode(ch2) != UBLOCK_COMBINING_DIACRITICAL_MARKS) {
571                    break;
572                }
573            }
574
575            // We could not found the main code point, so we will just use the initial chars
576            if (j < 0) {
577                break;
578            }
579
580#if DEBUG_GLYPHS
581            ALOGD("Found main code point at index %d", int(j));
582#endif
583            // We found the main code point, so we can normalize the "chunck" and fill
584            // the remaining with ZWSP so that the Paint.getTextWidth() APIs will still be able
585            // to get one advance per char
586            mBuffer.remove();
587            Normalizer::normalize(UnicodeString(chars + j, i - j + 1),
588                    UNORM_NFC, 0 /* no options */, mBuffer, error);
589            if (U_SUCCESS(error)) {
590                if (!useNormalizedString) {
591                    useNormalizedString = true;
592                    mNormalizedString.setTo(false /* not terminated*/, chars, count);
593                }
594                // Set the normalized chars
595                for (ssize_t k = j; k < j + mBuffer.length(); ++k) {
596                    mNormalizedString.setCharAt(k, mBuffer.charAt(k - j));
597                }
598                // Fill the remain part with ZWSP (ZWNJ and ZWJ would lead to weird results
599                // because some fonts are missing those glyphs)
600                for (ssize_t k = j + mBuffer.length(); k <= i; ++k) {
601                    mNormalizedString.setCharAt(k, UNICODE_ZWSP);
602                }
603            }
604            i = j - 1;
605        }
606    }
607
608    // Reverse "BiDi mirrored chars" in RTL mode only
609    // See: http://www.unicode.org/Public/6.0.0/ucd/extracted/DerivedBinaryProperties.txt
610    // This is a workaround because Harfbuzz is not able to do mirroring in all cases and
611    // script-run splitting with Harfbuzz is splitting on parenthesis
612    if (isRTL) {
613        for (ssize_t i = 0; i < ssize_t(count); i++) {
614            UChar ch = chars[i];
615            ssize_t index = gBidiMirrored.indexOfKey(ch);
616            // Skip non "BiDi mirrored" chars
617            if (index < 0) {
618                continue;
619            }
620            if (!useNormalizedString) {
621                useNormalizedString = true;
622                mNormalizedString.setTo(false /* not terminated*/, chars, count);
623            }
624            UChar result = gBidiMirrored.valueAt(index);
625            mNormalizedString.setCharAt(i, result);
626#if DEBUG_GLYPHS
627            ALOGD("Rewriting codepoint '%d' to '%d' at position %d",
628                    ch, mNormalizedString[i], int(i));
629#endif
630        }
631    }
632
633#if DEBUG_GLYPHS
634    if (useNormalizedString) {
635        ALOGD("Will use normalized string '%s', length = %d",
636                    String8(mNormalizedString.getTerminatedBuffer(),
637                            mNormalizedString.length()).string(),
638                    mNormalizedString.length());
639    } else {
640        ALOGD("Normalization is not needed or cannot be done, using initial string");
641    }
642#endif
643
644    assert(mNormalizedString.length() == count);
645
646    // Set the string properties
647    mShaperItem.string = useNormalizedString ? mNormalizedString.getTerminatedBuffer() : chars;
648    mShaperItem.stringLength = count;
649
650    // Define shaping paint properties
651    mShapingPaint.setTextSize(paint->getTextSize());
652    mShapingPaint.setTextSkewX(paint->getTextSkewX());
653    mShapingPaint.setTextScaleX(paint->getTextScaleX());
654    mShapingPaint.setFlags(paint->getFlags());
655    mShapingPaint.setHinting(paint->getHinting());
656
657    // Split the BiDi run into Script runs. Harfbuzz will populate the pos, length and script
658    // into the shaperItem
659    ssize_t indexFontRun = isRTL ? mShaperItem.stringLength - 1 : 0;
660    unsigned numCodePoints = 0;
661    jfloat totalAdvance = 0;
662    while ((isRTL) ?
663            hb_utf16_script_run_prev(&numCodePoints, &mShaperItem.item, mShaperItem.string,
664                    mShaperItem.stringLength, &indexFontRun):
665            hb_utf16_script_run_next(&numCodePoints, &mShaperItem.item, mShaperItem.string,
666                    mShaperItem.stringLength, &indexFontRun)) {
667
668        ssize_t startScriptRun = mShaperItem.item.pos;
669        size_t countScriptRun = mShaperItem.item.length;
670        ssize_t endScriptRun = startScriptRun + countScriptRun;
671
672#if DEBUG_GLYPHS
673        ALOGD("-------- Start of Script Run --------");
674        ALOGD("Shaping Script Run with");
675        ALOGD("         -- isRTL = %d", isRTL);
676        ALOGD("         -- HB script = %d", mShaperItem.item.script);
677        ALOGD("         -- startFontRun = %d", int(startScriptRun));
678        ALOGD("         -- endFontRun = %d", int(endScriptRun));
679        ALOGD("         -- countFontRun = %d", countScriptRun);
680        ALOGD("         -- run = '%s'", String8(chars + startScriptRun, countScriptRun).string());
681        ALOGD("         -- string = '%s'", String8(chars, count).string());
682#endif
683
684        // Initialize Harfbuzz Shaper and get the base glyph count for offsetting the glyphIDs
685        // and shape the Font run
686        size_t glyphBaseCount = shapeFontRun(paint, isRTL);
687
688#if DEBUG_GLYPHS
689        ALOGD("Got from Harfbuzz");
690        ALOGD("         -- glyphBaseCount = %d", glyphBaseCount);
691        ALOGD("         -- num_glypth = %d", mShaperItem.num_glyphs);
692        ALOGD("         -- kerning_applied = %d", mShaperItem.kerning_applied);
693        ALOGD("         -- isDevKernText = %d", paint->isDevKernText());
694
695        logGlyphs(mShaperItem);
696#endif
697        if (isRTL) {
698            endScriptRun = startScriptRun;
699#if DEBUG_GLYPHS
700            ALOGD("Updated endScriptRun = %d", int(endScriptRun));
701#endif
702        } else {
703            startScriptRun = endScriptRun;
704#if DEBUG_GLYPHS
705            ALOGD("Updated startScriptRun = %d", int(startScriptRun));
706#endif
707        }
708
709        if (mShaperItem.advances == NULL || mShaperItem.num_glyphs == 0) {
710#if DEBUG_GLYPHS
711            ALOGD("Advances array is empty or num_glypth = 0");
712#endif
713            outAdvances->insertAt(0, outAdvances->size(), countScriptRun);
714            continue;
715        }
716
717#if DEBUG_GLYPHS
718        ALOGD("Returned logclusters");
719        for (size_t i = 0; i < mShaperItem.num_glyphs; i++) {
720            ALOGD("         -- lc[%d] = %d, hb-adv[%d] = %0.2f", i, mShaperItem.log_clusters[i],
721                    i, HBFixedToFloat(mShaperItem.advances[i]));
722        }
723#endif
724        // Get Advances and their total
725        jfloat currentAdvance = HBFixedToFloat(mShaperItem.advances[mShaperItem.log_clusters[0]]);
726        jfloat totalFontRunAdvance = currentAdvance;
727        outAdvances->add(currentAdvance);
728        for (size_t i = 1; i < countScriptRun; i++) {
729            size_t clusterPrevious = mShaperItem.log_clusters[i - 1];
730            size_t cluster = mShaperItem.log_clusters[i];
731            if (cluster == clusterPrevious) {
732                outAdvances->add(0);
733            } else {
734                currentAdvance = HBFixedToFloat(mShaperItem.advances[mShaperItem.log_clusters[i]]);
735                outAdvances->add(currentAdvance);
736            }
737        }
738        // TODO: can be removed and go back in the previous loop when Harfbuzz log clusters are fixed
739        for (size_t i = 1; i < mShaperItem.num_glyphs; i++) {
740            currentAdvance = HBFixedToFloat(mShaperItem.advances[i]);
741            totalFontRunAdvance += currentAdvance;
742        }
743        totalAdvance += totalFontRunAdvance;
744
745#if DEBUG_ADVANCES
746        ALOGD("Returned advances");
747        for (size_t i = 0; i < countScriptRun; i++) {
748            ALOGD("         -- hb-adv[%d] = %0.2f, log_clusters = %d, total = %0.2f", i,
749                    (*outAdvances)[i], mShaperItem.log_clusters[i], totalFontRunAdvance);
750        }
751#endif
752        // Get Glyphs and reverse them in place if RTL
753        if (outGlyphs) {
754            size_t countGlyphs = mShaperItem.num_glyphs;
755#if DEBUG_GLYPHS
756            ALOGD("Returned script run glyphs -- count = %d", countGlyphs);
757#endif
758            for (size_t i = 0; i < countGlyphs; i++) {
759                jchar glyph = glyphBaseCount +
760                        (jchar) mShaperItem.glyphs[(!isRTL) ? i : countGlyphs - 1 - i];
761#if DEBUG_GLYPHS
762                ALOGD("         -- glyph[%d] = %d", i, glyph);
763#endif
764                outGlyphs->add(glyph);
765            }
766        }
767    }
768
769    *outTotalAdvance = totalAdvance;
770
771#if DEBUG_GLYPHS
772    ALOGD("-------- End of Script Run --------");
773#endif
774}
775
776
777size_t TextLayoutShaper::shapeFontRun(const SkPaint* paint, bool isRTL) {
778    // Reset kerning
779    mShaperItem.kerning_applied = false;
780
781    // Update Harfbuzz Shaper
782    mShaperItem.item.bidiLevel = isRTL;
783
784    SkTypeface* typeface = paint->getTypeface();
785
786    // Set the correct Typeface depending on the script
787    switch (mShaperItem.item.script) {
788    case HB_Script_Arabic:
789        typeface = getCachedTypeface(&mArabicTypeface, TYPEFACE_ARABIC);
790#if DEBUG_GLYPHS
791        ALOGD("Using Arabic Typeface");
792#endif
793        break;
794
795    case HB_Script_Hebrew:
796        if (typeface) {
797            switch (typeface->style()) {
798            case SkTypeface::kBold:
799            case SkTypeface::kBoldItalic:
800                typeface = getCachedTypeface(&mHebrewBoldTypeface, TYPE_FACE_HEBREW_BOLD);
801#if DEBUG_GLYPHS
802                ALOGD("Using Hebrew Bold/BoldItalic Typeface");
803#endif
804                break;
805
806            case SkTypeface::kNormal:
807            case SkTypeface::kItalic:
808            default:
809                typeface = getCachedTypeface(&mHebrewRegularTypeface, TYPE_FACE_HEBREW_REGULAR);
810#if DEBUG_GLYPHS
811                ALOGD("Using Hebrew Regular/Italic Typeface");
812#endif
813                break;
814            }
815        } else {
816            typeface = getCachedTypeface(&mHebrewRegularTypeface, TYPE_FACE_HEBREW_REGULAR);
817#if DEBUG_GLYPHS
818            ALOGD("Using Hebrew Regular Typeface");
819#endif
820        }
821        break;
822
823    case HB_Script_Bengali:
824        typeface = getCachedTypeface(&mBengaliTypeface, TYPEFACE_BENGALI);
825#if DEBUG_GLYPHS
826        ALOGD("Using Bengali Typeface");
827#endif
828        break;
829
830    case HB_Script_Thai:
831        typeface = getCachedTypeface(&mThaiTypeface, TYPEFACE_THAI);
832#if DEBUG_GLYPHS
833        ALOGD("Using Thai Typeface");
834#endif
835        break;
836
837    case HB_Script_Devanagari:
838        typeface = getCachedTypeface(&mDevanagariTypeface, TYPEFACE_DEVANAGARI);
839#if DEBUG_GLYPHS
840        ALOGD("Using Devanagari Typeface");
841#endif
842        break;
843
844    case HB_Script_Tamil:
845        typeface = getCachedTypeface(&mTamilTypeface, TYPEFACE_TAMIL);
846#if DEBUG_GLYPHS
847        ALOGD("Using Tamil Typeface");
848#endif
849        break;
850
851    default:
852        if (!typeface) {
853            typeface = mDefaultTypeface;
854#if DEBUG_GLYPHS
855            ALOGD("Using Default Typeface");
856#endif
857        } else {
858#if DEBUG_GLYPHS
859            ALOGD("Using Paint Typeface");
860#endif
861        }
862        break;
863    }
864
865    mShapingPaint.setTypeface(typeface);
866    mShaperItem.face = getCachedHBFace(typeface);
867
868#if DEBUG_GLYPHS
869    ALOGD("Run typeface = %p, uniqueID = %d, hb_face = %p",
870            typeface, typeface->uniqueID(), mShaperItem.face);
871#endif
872
873    // Get the glyphs base count for offsetting the glyphIDs returned by Harfbuzz
874    // This is needed as the Typeface used for shaping can be not the default one
875    // when we are shaping any script that needs to use a fallback Font.
876    // If we are a "common" script we dont need to shift
877    size_t baseGlyphCount = 0;
878    switch (mShaperItem.item.script) {
879    case HB_Script_Arabic:
880    case HB_Script_Hebrew:
881    case HB_Script_Bengali:
882    case HB_Script_Devanagari:
883    case HB_Script_Tamil:
884    case HB_Script_Thai:{
885        const uint16_t* text16 = (const uint16_t*)(mShaperItem.string + mShaperItem.item.pos);
886        SkUnichar firstUnichar = SkUTF16_NextUnichar(&text16);
887        baseGlyphCount = paint->getBaseGlyphCount(firstUnichar);
888        break;
889    }
890    default:
891        break;
892    }
893
894    // Shape
895    assert(mShaperItem.item.length > 0); // Harfbuzz will overwrite other memory if length is 0.
896    ensureShaperItemGlyphArrays(mShaperItem.item.length * 3 / 2);
897    mShaperItem.num_glyphs = mShaperItemGlyphArraySize;
898    while (!HB_ShapeItem(&mShaperItem)) {
899        // We overflowed our glyph arrays. Resize and retry.
900        // HB_ShapeItem fills in shaperItem.num_glyphs with the needed size.
901        ensureShaperItemGlyphArrays(mShaperItem.num_glyphs * 2);
902        mShaperItem.num_glyphs = mShaperItemGlyphArraySize;
903    }
904    return baseGlyphCount;
905}
906
907void TextLayoutShaper::ensureShaperItemGlyphArrays(size_t size) {
908    if (size > mShaperItemGlyphArraySize) {
909        deleteShaperItemGlyphArrays();
910        createShaperItemGlyphArrays(size);
911    }
912}
913
914void TextLayoutShaper::createShaperItemGlyphArrays(size_t size) {
915#if DEBUG_GLYPHS
916    ALOGD("Creating Glyph Arrays with size = %d", size);
917#endif
918    mShaperItemGlyphArraySize = size;
919
920    // These arrays are all indexed by glyph.
921    mShaperItem.glyphs = new HB_Glyph[size];
922    mShaperItem.attributes = new HB_GlyphAttributes[size];
923    mShaperItem.advances = new HB_Fixed[size];
924    mShaperItem.offsets = new HB_FixedPoint[size];
925
926    // Although the log_clusters array is indexed by character, Harfbuzz expects that
927    // it is big enough to hold one element per glyph.  So we allocate log_clusters along
928    // with the other glyph arrays above.
929    mShaperItem.log_clusters = new unsigned short[size];
930}
931
932void TextLayoutShaper::deleteShaperItemGlyphArrays() {
933    delete[] mShaperItem.glyphs;
934    delete[] mShaperItem.attributes;
935    delete[] mShaperItem.advances;
936    delete[] mShaperItem.offsets;
937    delete[] mShaperItem.log_clusters;
938}
939
940SkTypeface* TextLayoutShaper::getCachedTypeface(SkTypeface** typeface, const char path[]) {
941    if (!*typeface) {
942        *typeface = SkTypeface::CreateFromFile(path);
943        // CreateFromFile(path) can return NULL if the path is non existing
944        if (!*typeface) {
945#if DEBUG_GLYPHS
946        ALOGD("Font path '%s' is not valid, will use default font", path);
947#endif
948            return mDefaultTypeface;
949        }
950        (*typeface)->ref();
951#if DEBUG_GLYPHS
952        ALOGD("Created SkTypeface from file '%s' with uniqueID = %d", path, (*typeface)->uniqueID());
953#endif
954    }
955    return *typeface;
956}
957
958HB_Face TextLayoutShaper::getCachedHBFace(SkTypeface* typeface) {
959    SkFontID fontId = typeface->uniqueID();
960    ssize_t index = mCachedHBFaces.indexOfKey(fontId);
961    if (index >= 0) {
962        return mCachedHBFaces.valueAt(index);
963    }
964    HB_Face face = HB_NewFace(typeface, harfbuzzSkiaGetTable);
965    if (face) {
966#if DEBUG_GLYPHS
967        ALOGD("Created HB_NewFace %p from paint typeface = %p", face, typeface);
968#endif
969        mCachedHBFaces.add(fontId, face);
970    }
971    return face;
972}
973
974TextLayoutEngine::TextLayoutEngine() {
975    mShaper = new TextLayoutShaper();
976#if USE_TEXT_LAYOUT_CACHE
977    mTextLayoutCache = new TextLayoutCache(mShaper);
978#else
979    mTextLayoutCache = NULL;
980#endif
981}
982
983TextLayoutEngine::~TextLayoutEngine() {
984    delete mTextLayoutCache;
985    delete mShaper;
986}
987
988sp<TextLayoutValue> TextLayoutEngine::getValue(const SkPaint* paint, const jchar* text,
989        jint start, jint count, jint contextCount, jint dirFlags) {
990    sp<TextLayoutValue> value;
991#if USE_TEXT_LAYOUT_CACHE
992    value = mTextLayoutCache->getValue(paint, text, start, count,
993            contextCount, dirFlags);
994    if (value == NULL) {
995        ALOGE("Cannot get TextLayoutCache value for text = '%s'",
996                String8(text + start, count).string());
997    }
998#else
999    value = new TextLayoutValue(count);
1000    mShaper->computeValues(value.get(), paint,
1001            reinterpret_cast<const UChar*>(text), start, count, contextCount, dirFlags);
1002#endif
1003    return value;
1004}
1005
1006} // namespace android
1007