Improve utf16/utf8 mismatch with ubidi.

The ubidi code only works with utf16 and SkTextBlob only with utf8. This
requires translating indexes. The current code starts cold when
translating indexes for each run, leading to taking O(n^2) time on the
number of runs. However, since this code is iterating over the runs in
order and each run begins where the last left off, simply keeping the
previous run's utf8 and utf16 end positions and using them as the next
starting position makes this O(N).

Change-Id: I921a87511fb4cdf5f6e92cd483959cf758d95306
Reviewed-on: https://skia-review.googlesource.com/41503
Reviewed-by: Ben Wagner <bungeman@google.com>
Commit-Queue: Ben Wagner <bungeman@google.com>

1 files changed, 30 insertions, 15 deletions

diff --git a/tools/shape/SkShaper_harfbuzz.cpp b/tools/shape/SkShaper_harfbuzz.cpp
index 3947406b85..98cf6ccfe0 100644
--- a/tools/shape/SkShaper_harfbuzz.cpp
+++ b/tools/shape/SkShaper_harfbuzz.cpp
@@ -119,6 +119,8 @@ SkScalar SkShaper::shape(SkTextBlobBuilder* builder,
         return (SkScalar)x;
     }
 
+    const UChar* utf16End = utf16.getBuffer();
+    const char* utf8End = utf8text;
     for (int32_t i = 0; i < runCount; ++i) {
         int32_t start;
         int32_t length;
@@ -134,26 +136,39 @@ SkScalar SkShaper::shape(SkTextBlobBuilder* builder,
         // The difficulty here is the cluster mapping.
         // If the hb_buffer is created with utf16, clusters will be pointing to the utf16 indexes,
         // but the SkTextBlob can only take utf8 and utf8 cluster indexes.
-        // Instead of updating each cluster index, create the hb_buffer from the utf8.
-        // TODO: this is horribly inefficient.
-        const char* utf8textStart = utf8text;
-        const UChar* utf16Start = utf16.getBuffer();
-        while (utf16Start < utf16.getBuffer() + start) {
-            SkUTF16_NextUnichar(&utf16Start);
-            SkUTF8_NextUnichar(&utf8textStart);
+        // So populate the hb_buffer directly with utf32 and utf8 cluster indexes.
+        // Since this steps through the visual runs in order, it is expected that each run will
+        // start just after the previous one ended.
+        const UChar* utf16Start = utf16.getBuffer() + start;
+        const char* utf8Start;
+        if (utf16End == utf16Start) {
+            utf16Start = utf16End;
+            utf8Start = utf8End;
+        } else {
+            SkDEBUGFAIL("Did not expect to ever get here.");
+            utf16Start = utf16.getBuffer();
+            utf8Start = utf8text;
+            while (utf16Start < utf16.getBuffer() + start) {
+                SkUTF16_NextUnichar(&utf16Start);
+                SkUTF8_NextUnichar(&utf8Start);
+            }
         }
-        const char* utf8textEnd = utf8textStart;
-        const UChar* utf16End = utf16Start;
-        while (utf16End < utf16.getBuffer() + start + length) {
-            SkUTF16_NextUnichar(&utf16End);
-            SkUTF8_NextUnichar(&utf8textEnd);
+        const char* utf8Current = utf8Start;
+        const UChar* utf16Current = utf16Start;
+        utf16End = utf16Current + length;
+        while (utf16Current < utf16End) {
+            hb_codepoint_t u;
+            u = SkUTF16_NextUnichar(&utf16Current);
+            hb_buffer_add(buffer, u, utf8Current - utf8Start);
+            SkUTF8_NextUnichar(&utf8Current);
         }
-        size_t utf8runLength = utf8textEnd - utf8textStart;
+        hb_buffer_set_content_type(buffer, HB_BUFFER_CONTENT_TYPE_UNICODE);
+        utf8End = utf8Current;
+        size_t utf8runLength = utf8End - utf8Start;
         if (!SkTFitsIn<int>(utf8runLength)) {
             SkDebugf("Shaping error: utf8 too long");
             return (SkScalar)x;
         }
-        hb_buffer_add_utf8(buffer, utf8textStart, utf8runLength, 0, -1);
         hb_buffer_guess_segment_properties(buffer);
         //hb_buffer_set_script(buffer, script);
         hb_buffer_set_direction(buffer, direction ? HB_DIRECTION_RTL : HB_DIRECTION_LTR);
@@ -171,7 +186,7 @@ SkScalar SkShaper::shape(SkTextBlobBuilder* builder,
             return (SkScalar)x;
         }
         auto runBuffer = builder->allocRunTextPos(paint, len, utf8runLength, SkString());
-        memcpy(runBuffer.utf8text, utf8textStart, utf8runLength);
+        memcpy(runBuffer.utf8text, utf8Start, utf8runLength);
 
         double textSizeY = paint.getTextSize() / (double)FONT_SIZE_SCALE;
         double textSizeX = textSizeY * paint.getTextScaleX();