Optimize TextLine#measureAllOffset performance

Bug: 238954768
Bug: 235353864
Test: atest StaticLayoutGetOffsetForHorizontalPerfTest
Change-Id: Ic3a1a8fc5ef5d160401d390b920f3f2a409528f0
diff --git a/core/java/android/text/TextLine.java b/core/java/android/text/TextLine.java
index 7394c22..e38073a 100644
--- a/core/java/android/text/TextLine.java
+++ b/core/java/android/text/TextLine.java
@@ -553,16 +553,11 @@
     @VisibleForTesting
     public float[] measureAllOffsets(boolean[] trailing, FontMetricsInt fmi) {
         float[] measurement = new float[mLen + 1];
-
-        int[] target = new int[mLen + 1];
-        for (int offset = 0; offset < target.length; ++offset) {
-            target[offset] = trailing[offset] ? offset - 1 : offset;
-        }
-        if (target[0] < 0) {
+        if (trailing[0]) {
             measurement[0] = 0;
         }
 
-        float h = 0;
+        float horizontal = 0;
         for (int runIndex = 0; runIndex < mDirections.getRunCount(); runIndex++) {
             final int runStart = mDirections.getRunStart(runIndex);
             if (runStart > mLen) break;
@@ -572,27 +567,48 @@
             int segStart = runStart;
             for (int j = mHasTabs ? runStart : runLimit; j <= runLimit; ++j) {
                 if (j == runLimit || charAt(j) == TAB_CHAR) {
-                    final  float oldh = h;
-                    final boolean advance = (mDir == Layout.DIR_RIGHT_TO_LEFT) == runIsRtl;
-                    final float w = measureRun(segStart, j, j, runIsRtl, fmi, null, 0);
-                    h += advance ? w : -w;
+                    final float oldHorizontal = horizontal;
+                    final boolean sameDirection =
+                            (mDir == Layout.DIR_RIGHT_TO_LEFT) == runIsRtl;
 
-                    final float baseh = advance ? oldh : h;
-                    FontMetricsInt crtfmi = advance ? fmi : null;
-                    for (int offset = segStart; offset <= j && offset <= mLen; ++offset) {
-                        if (target[offset] >= segStart && target[offset] < j) {
-                            measurement[offset] = baseh
-                                    + measureRun(segStart, offset, j, runIsRtl, crtfmi, null, 0);
+                    // We are using measurement to receive character advance here. So that it
+                    // doesn't need to allocate a new array.
+                    // But be aware that when trailing[segStart] is true, measurement[segStart]
+                    // will be computed in the previous run. And we need to store it first in case
+                    // measureRun overwrites the result.
+                    final float previousSegEndHorizontal = measurement[segStart];
+                    final float width =
+                            measureRun(segStart, j, j, runIsRtl, fmi, measurement, segStart);
+                    horizontal += sameDirection ? width : -width;
+
+                    float currHorizontal = sameDirection ? oldHorizontal : horizontal;
+                    final int segLimit = Math.min(j, mLen);
+
+                    for (int offset = segStart; offset <= segLimit; ++offset) {
+                        float advance = 0f;
+                        // When offset == segLimit, advance is meaningless.
+                        if (offset < segLimit) {
+                            advance = runIsRtl ? -measurement[offset] : measurement[offset];
                         }
+
+                        if (offset == segStart && trailing[offset]) {
+                            // If offset == segStart and trailing[segStart] is true, restore the
+                            // value of measurement[segStart] from the previous run.
+                            measurement[offset] = previousSegEndHorizontal;
+                        } else if (offset != segLimit || trailing[offset]) {
+                            measurement[offset] = currHorizontal;
+                        }
+
+                        currHorizontal += advance;
                     }
 
                     if (j != runLimit) {  // charAt(j) == TAB_CHAR
-                        if (target[j] == j) {
-                            measurement[j] = h;
+                        if (!trailing[j]) {
+                            measurement[j] = horizontal;
                         }
-                        h = mDir * nextTab(h * mDir);
-                        if (target[j + 1] == j) {
-                            measurement[j + 1] =  h;
+                        horizontal = mDir * nextTab(horizontal * mDir);
+                        if (trailing[j + 1]) {
+                            measurement[j + 1] = horizontal;
                         }
                     }
 
@@ -600,10 +616,9 @@
                 }
             }
         }
-        if (target[mLen] == mLen) {
-            measurement[mLen] = h;
+        if (!trailing[mLen]) {
+            measurement[mLen] = horizontal;
         }
-
         return measurement;
     }
 
diff --git a/core/tests/coretests/assets/fonts/ligature.ttf b/core/tests/coretests/assets/fonts/ligature.ttf
new file mode 100644
index 0000000..d1e8059
--- /dev/null
+++ b/core/tests/coretests/assets/fonts/ligature.ttf
Binary files differ
diff --git a/core/tests/coretests/assets/fonts/ligature.ttx b/core/tests/coretests/assets/fonts/ligature.ttx
new file mode 100644
index 0000000..d7881f4
--- /dev/null
+++ b/core/tests/coretests/assets/fonts/ligature.ttx
@@ -0,0 +1,224 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!-- Copyright (C) 2017 The Android Open Source Project
+
+     Licensed under the Apache License, Version 2.0 (the "License");
+     you may not use this file except in compliance with the License.
+     You may obtain a copy of the License at
+
+          http://www.apache.org/licenses/LICENSE-2.0
+
+     Unless required by applicable law or agreed to in writing, software
+     distributed under the License is distributed on an "AS IS" BASIS
+     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+     See the License for the specific language governing permissions and
+     limitations under the License.
+-->
+<ttFont sfntVersion="\x00\x01\x00\x00" ttLibVersion="3.0">
+
+  <GlyphOrder>
+    <GlyphID id="0" name=".notdef"/>
+    <GlyphID id="1" name="1em"/>
+    <GlyphID id="2" name="f"/>
+    <GlyphID id="3" name="i"/>
+    <GlyphID id="4" name="fi"/>
+  </GlyphOrder>
+
+  <head>
+    <tableVersion value="1.0"/>
+    <fontRevision value="1.0"/>
+    <checkSumAdjustment value="0x640cdb2f"/>
+    <magicNumber value="0x5f0f3cf5"/>
+    <flags value="00000000 00000011"/>
+    <unitsPerEm value="100"/>
+    <created value="Fri Mar 17 07:26:00 2017"/>
+    <macStyle value="00000000 00000000"/>
+    <lowestRecPPEM value="7"/>
+    <fontDirectionHint value="2"/>
+    <glyphDataFormat value="0"/>
+  </head>
+
+  <hhea>
+    <tableVersion value="0x00010000"/>
+    <ascent value="1000"/>
+    <descent value="-200"/>
+    <lineGap value="0"/>
+    <caretSlopeRise value="1"/>
+    <caretSlopeRun value="0"/>
+    <caretOffset value="0"/>
+    <reserved0 value="0"/>
+    <reserved1 value="0"/>
+    <reserved2 value="0"/>
+    <reserved3 value="0"/>
+    <metricDataFormat value="0"/>
+  </hhea>
+
+  <maxp>
+    <tableVersion value="0x10000"/>
+    <maxZones value="0"/>
+    <maxTwilightPoints value="0"/>
+    <maxStorage value="0"/>
+    <maxFunctionDefs value="0"/>
+    <maxInstructionDefs value="0"/>
+    <maxStackElements value="0"/>
+    <maxSizeOfInstructions value="0"/>
+    <maxComponentElements value="0"/>
+  </maxp>
+
+  <OS_2>
+    <!-- The fields 'usFirstCharIndex' and 'usLastCharIndex'
+         will be recalculated by the compiler -->
+    <version value="3"/>
+    <xAvgCharWidth value="594"/>
+    <usWeightClass value="400"/>
+    <usWidthClass value="5"/>
+    <fsType value="00000000 00001000"/>
+    <ySubscriptXSize value="650"/>
+    <ySubscriptYSize value="600"/>
+    <ySubscriptXOffset value="0"/>
+    <ySubscriptYOffset value="75"/>
+    <ySuperscriptXSize value="650"/>
+    <ySuperscriptYSize value="600"/>
+    <ySuperscriptXOffset value="0"/>
+    <ySuperscriptYOffset value="350"/>
+    <yStrikeoutSize value="50"/>
+    <yStrikeoutPosition value="300"/>
+    <sFamilyClass value="0"/>
+    <panose>
+      <bFamilyType value="0"/>
+      <bSerifStyle value="0"/>
+      <bWeight value="5"/>
+      <bProportion value="0"/>
+      <bContrast value="0"/>
+      <bStrokeVariation value="0"/>
+      <bArmStyle value="0"/>
+      <bLetterForm value="0"/>
+      <bMidline value="0"/>
+      <bXHeight value="0"/>
+    </panose>
+    <ulUnicodeRange1 value="00000000 00000000 00000000 00000001"/>
+    <ulUnicodeRange2 value="00000000 00000000 00000000 00000000"/>
+    <ulUnicodeRange3 value="00000000 00000000 00000000 00000000"/>
+    <ulUnicodeRange4 value="00000000 00000000 00000000 00000000"/>
+    <achVendID value="UKWN"/>
+    <fsSelection value="00000000 01000000"/>
+    <usFirstCharIndex value="32"/>
+    <usLastCharIndex value="122"/>
+    <sTypoAscender value="800"/>
+    <sTypoDescender value="-200"/>
+    <sTypoLineGap value="200"/>
+    <usWinAscent value="1000"/>
+    <usWinDescent value="200"/>
+    <ulCodePageRange1 value="00000000 00000000 00000000 00000001"/>
+    <ulCodePageRange2 value="00000000 00000000 00000000 00000000"/>
+    <sxHeight value="500"/>
+    <sCapHeight value="700"/>
+    <usDefaultChar value="0"/>
+    <usBreakChar value="32"/>
+    <usMaxContext value="0"/>
+  </OS_2>
+
+  <GSUB>
+    <Version value="0x00010000"/>
+    <ScriptList>
+      <ScriptRecord index="0">
+        <ScriptTag value="latn"/>
+        <Script>
+          <DefaultLangSys>
+            <ReqFeatureIndex value="65535"/>
+            <FeatureIndex index="0" value="0"/>
+          </DefaultLangSys>
+        </Script>
+      </ScriptRecord>
+    </ScriptList>
+    <FeatureList>
+      <FeatureRecord index="0">
+        <FeatureTag value="liga"/>
+        <Feature>
+          <LookupListIndex index="0" value="0"/>
+        </Feature>
+      </FeatureRecord>
+    </FeatureList>
+    <LookupList>
+      <Lookup index="0">
+        <LookupType value="4"/>
+        <LookupFlag value="0"/>
+        <LigatureSubst index="0">
+          <LigatureSet glyph="f">
+            <Ligature components="i" glyph="fi"/>
+          </LigatureSet>
+        </LigatureSubst>
+      </Lookup>
+    </LookupList>
+  </GSUB>
+
+  <hmtx>
+    <mtx name=".notdef" width="50" lsb="0"/>
+    <mtx name="1em" width="100" lsb="0"/>
+    <mtx name="f" width="50" lsb="0"/>
+    <mtx name="i" width="50" lsb="0"/>
+    <mtx name="fi" width="200" lsb="0"/>
+  </hmtx>
+
+  <cmap>
+    <tableVersion version="0"/>
+    <cmap_format_12 format="12" reserved="0" length="6" nGroups="1" platformID="3" platEncID="10" language="0">
+      <map code="0x0020" name="1em" />
+      <map code="0x002e" name="1em" />  <!-- . -->
+      <map code="0x0049" name="1em" />  <!-- I -->
+      <map code="0x0066" name="f" />    <!-- f -->
+      <map code="0x0069" name="i" />    <!-- i -->
+    </cmap_format_12>
+  </cmap>
+
+  <loca>
+    <!-- The 'loca' table will be calculated by the compiler -->
+  </loca>
+
+  <glyf>
+    <TTGlyph name=".notdef" xMin="0" yMin="0" xMax="0" yMax="0" />
+    <TTGlyph name="1em" xMin="0" yMin="0" xMax="0" yMax="0" />
+    <TTGlyph name="f" xMin="0" yMin="0" xMax="0" yMax="0" />
+    <TTGlyph name="i" xMin="0" yMin="0" xMax="0" yMax="0" />
+    <TTGlyph name="fi" xMin="0" yMin="0" xMax="0" yMax="0" />
+  </glyf>
+
+  <name>
+    <namerecord nameID="1" platformID="1" platEncID="0" langID="0x0" unicode="True">
+      Font for StaticLayoutLineBreakingTest
+    </namerecord>
+    <namerecord nameID="2" platformID="1" platEncID="0" langID="0x0" unicode="True">
+      Regular
+    </namerecord>
+    <namerecord nameID="4" platformID="1" platEncID="0" langID="0x0" unicode="True">
+      Font for StaticLayoutLineBreakingTest
+    </namerecord>
+    <namerecord nameID="6" platformID="1" platEncID="0" langID="0x0" unicode="True">
+      SampleFont-Regular
+    </namerecord>
+    <namerecord nameID="1" platformID="3" platEncID="1" langID="0x409">
+      Sample Font
+    </namerecord>
+    <namerecord nameID="2" platformID="3" platEncID="1" langID="0x409">
+      Regular
+    </namerecord>
+    <namerecord nameID="4" platformID="3" platEncID="1" langID="0x409">
+      Sample Font
+    </namerecord>
+    <namerecord nameID="6" platformID="3" platEncID="1" langID="0x409">
+      SampleFont-Regular
+    </namerecord>
+  </name>
+
+  <post>
+    <formatType value="3.0"/>
+    <italicAngle value="0.0"/>
+    <underlinePosition value="-75"/>
+    <underlineThickness value="50"/>
+    <isFixedPitch value="0"/>
+    <minMemType42 value="0"/>
+    <maxMemType42 value="0"/>
+    <minMemType1 value="0"/>
+    <maxMemType1 value="0"/>
+  </post>
+
+</ttFont>
diff --git a/core/tests/coretests/src/android/text/TextLineTest.java b/core/tests/coretests/src/android/text/TextLineTest.java
index e3bcc8d..213e2a9 100644
--- a/core/tests/coretests/src/android/text/TextLineTest.java
+++ b/core/tests/coretests/src/android/text/TextLineTest.java
@@ -30,9 +30,9 @@
 import android.text.style.ReplacementSpan;
 import android.text.style.TabStopSpan;
 
-import androidx.test.InstrumentationRegistry;
 import androidx.test.filters.SmallTest;
 import androidx.test.filters.Suppress;
+import androidx.test.platform.app.InstrumentationRegistry;
 import androidx.test.runner.AndroidJUnit4;
 
 import org.junit.Test;
@@ -98,6 +98,17 @@
             InstrumentationRegistry.getInstrumentation().getTargetContext().getAssets(),
             "fonts/StaticLayoutLineBreakingTestFont.ttf");
 
+    // The test font has following coverage and width.
+    // U+0020: 1em
+    // U+0049 (I): 1em
+    // U+0066 (f): 0.5em
+    // U+0069 (i): 0.5em
+    // ligature fi: 2em
+    // U+10331 (\uD800\uDF31): 10em
+    private static final Typeface TYPEFACE_LIGATURE = Typeface.createFromAsset(
+            InstrumentationRegistry.getInstrumentation().getTargetContext().getAssets(),
+            "fonts/ligature.ttf");
+
     private TextLine getTextLine(CharSequence str, TextPaint paint, TabStops tabStops) {
         Layout layout =
                 StaticLayout.Builder.obtain(str, 0, str.length(), paint, Integer.MAX_VALUE)
@@ -265,6 +276,34 @@
         TextLine tl = getTextLine("I I", paint);
         assertMeasurements(tl, 3, false,
                 new float[]{0.0f, 10.0f, 120.0f, 130.0f});
+        assertMeasurements(tl, 3, true,
+                new float[]{0.0f, 10.0f, 120.0f, 130.0f});
+    }
+
+    @Test
+    public void testMeasure_surrogate() {
+        final TextPaint paint = new TextPaint();
+        paint.setTypeface(TYPEFACE);
+        paint.setTextSize(10.0f);  // make 1em = 10px
+
+        TextLine tl = getTextLine("I\uD800\uDF31I", paint);
+        assertMeasurements(tl, 4, false,
+                new float[]{0.0f, 10.0f, 110.0f, 110.0f, 120.0f});
+        assertMeasurements(tl, 4, true,
+                new float[]{0.0f, 10.0f, 110.0f, 110.0f, 120.0f});
+    }
+
+    @Test
+    public void testMeasure_ligature() {
+        final TextPaint paint = new TextPaint();
+        paint.setTypeface(TYPEFACE_LIGATURE);
+        paint.setTextSize(10.0f);  // make 1em = 10px
+
+        TextLine tl = getTextLine("IfiI", paint);
+        assertMeasurements(tl, 4, false,
+                new float[]{0.0f, 10.0f, 20.0f, 30.0f, 40.0f});
+        assertMeasurements(tl, 4, true,
+                new float[]{0.0f, 10.0f, 20.0f, 30.0f, 40.0f});
     }
 
     @Test
diff --git a/libs/hwui/jni/Paint.cpp b/libs/hwui/jni/Paint.cpp
index ed453b1..f0a4bd0 100644
--- a/libs/hwui/jni/Paint.cpp
+++ b/libs/hwui/jni/Paint.cpp
@@ -517,10 +517,12 @@
         MinikinUtils::measureText(paint, bidiFlags, typeface, buf, start, count, bufSize,
                 advancesArray.get());
 
+        float result = minikin::getRunAdvance(advancesArray.get(), buf, start, count, offset);
         if (advances) {
+            minikin::distributeAdvances(advancesArray.get(), buf, start, count);
             env->SetFloatArrayRegion(advances, advancesIndex, count, advancesArray.get());
         }
-        return minikin::getRunAdvance(advancesArray.get(), buf, start, count, offset);
+        return result;
     }
 
     static jfloat getRunAdvance___CIIIIZI_F(JNIEnv *env, jclass, jlong paintHandle, jcharArray text,