Add functions for measuring cursor positioning

New functions for computing the correspondence between cursor
position and advance, respecting grapheme boundaries.

Change-Id: I620378d5f64cd74300cd43db522adeb555825dff

5 files changed, 157 insertions, 5 deletions

diff --git a/include/minikin/Layout.h b/include/minikin/Layout.h
index 543f553..930407a 100644
--- a/include/minikin/Layout.h
+++ b/include/minikin/Layout.h
@@ -106,9 +106,13 @@ public:
     float getAdvance() const;
 
     // Get advances, copying into caller-provided buffer. The size of this
-    // buffer must match the length of the string (nchars arg to doLayout).
+    // buffer must match the length of the string (count arg to doLayout).
     void getAdvances(float* advances);
 
+    // The i parameter is an offset within the buf relative to start, it is < count, where
+    // start and count are the parameters to doLayout
+    float getCharAdvance(size_t i) const { return mAdvances[i]; }
+
     void getBounds(MinikinRect* rect);
 
     // Purge all caches, useful in low memory conditions
diff --git a/include/minikin/Measurement.h b/include/minikin/Measurement.h
new file mode 100644
index 0000000..fc47fa3
--- /dev/null
+++ b/include/minikin/Measurement.h
@@ -0,0 +1,31 @@
+/*
+ * Copyright (C) 2015 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.
+ */
+
+#ifndef MINIKIN_MEASUREMENT_H
+#define MINIKIN_MEASUREMENT_H
+
+#include <minikin/Layout.h>
+
+namespace android {
+
+float getRunAdvance(Layout& layout, const uint16_t* buf, size_t start, size_t count, size_t offset);
+
+size_t getOffsetForAdvance(Layout& layout, const uint16_t* buf, size_t start, size_t count,
+        float advance);
+
+}
+
+#endif  // MINIKIN_MEASUREMENT_H
diff --git a/libs/minikin/Android.mk b/libs/minikin/Android.mk
index 34b535c..873f279 100644
--- a/libs/minikin/Android.mk
+++ b/libs/minikin/Android.mk
@@ -25,6 +25,7 @@ LOCAL_SRC_FILES := \
     Hyphenator.cpp \
     Layout.cpp \
     LineBreaker.cpp \
+    Measurement.cpp \
     MinikinInternal.cpp \
     MinikinRefCounted.cpp \
     MinikinFontFreeType.cpp \
diff --git a/libs/minikin/GraphemeBreak.cpp b/libs/minikin/GraphemeBreak.cpp
index 5d8978d..f8f386c 100644
--- a/libs/minikin/GraphemeBreak.cpp
+++ b/libs/minikin/GraphemeBreak.cpp
@@ -41,7 +41,7 @@ bool GraphemeBreak::isGraphemeBreak(const uint16_t* buf, size_t start, size_t co
     uint32_t c2 = 0;
     size_t offset_back = offset;
     U16_PREV(buf, start, offset_back, c1);
-    U16_NEXT(buf, offset, count, c2);
+    U16_NEXT(buf, offset, start + count, c2);
     int32_t p1 = u_getIntPropertyValue(c1, UCHAR_GRAPHEME_CLUSTER_BREAK);
     int32_t p2 = u_getIntPropertyValue(c2, UCHAR_GRAPHEME_CLUSTER_BREAK);
     // Rule GB3, CR x LF
@@ -54,7 +54,7 @@ bool GraphemeBreak::isGraphemeBreak(const uint16_t* buf, size_t start, size_t co
     }
     // Rule GB5, / (Control | CR | LF)
     if (p2 == U_GCB_CONTROL || p2 == U_GCB_CR || p2 == U_GCB_LF) {
-        // exclude zero-width control characters from breaking (tailoring of TR29)
+        // exclude zero-width control characters from breaking (tailoring of UAX #29)
         if (c2 == 0x00ad
                 || (c2 >= 0x200b && c2 <= 0x200f)
                 || (c2 >= 0x2028 && c2 <= 0x202e)
@@ -83,12 +83,12 @@ bool GraphemeBreak::isGraphemeBreak(const uint16_t* buf, size_t start, size_t co
     if (p2 == U_GCB_EXTEND || p2 == U_GCB_SPACING_MARK) {
         if (c2 == 0xe33) {
             // most other implementations break THAI CHARACTER SARA AM
-            // (tailoring of TR29)
+            // (tailoring of UAX #29)
             return true;
         }
         return false;
     }
-    // Cluster indic syllables togeter (tailoring of TR29)
+    // Cluster indic syllables together (tailoring of UAX #29)
     if (u_getIntPropertyValue(c1, UCHAR_CANONICAL_COMBINING_CLASS) == 9  // virama
             && u_getIntPropertyValue(c2, UCHAR_GENERAL_CATEGORY) == U_OTHER_LETTER) {
         return false;
diff --git a/libs/minikin/Measurement.cpp b/libs/minikin/Measurement.cpp
new file mode 100644
index 0000000..21df5d8
--- /dev/null
+++ b/libs/minikin/Measurement.cpp
@@ -0,0 +1,116 @@
+/*
+ * Copyright (C) 2015 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.
+ */
+
+#define LOG_TAG "Minikin"
+#include <cutils/log.h>
+
+#include <cmath>
+#include <unicode/uchar.h>
+
+#include <minikin/GraphemeBreak.h>
+#include <minikin/Measurement.h>
+
+namespace android {
+
+// These could be considered helper methods of layout, but need only be loosely coupled, so
+// are separate.
+
+float getRunAdvance(Layout& layout, const uint16_t* buf, size_t start, size_t count,
+        size_t offset) {
+    float advance = 0.0f;
+    size_t lastCluster = start;
+    float clusterWidth = 0.0f;
+    for (size_t i = start; i < offset; i++) {
+        float charAdvance = layout.getCharAdvance(i - start);
+        if (charAdvance != 0.0f) {
+            advance += charAdvance;
+            lastCluster = i;
+            clusterWidth = charAdvance;
+        }
+    }
+    if (offset < start + count && layout.getCharAdvance(offset) == 0.0f) {
+        // In the middle of a cluster, distribute width of cluster so that each grapheme cluster
+        // gets an equal share.
+        // TODO: get caret information out of font when that's available
+        size_t nextCluster;
+        for (nextCluster = offset + 1; nextCluster < start + count; nextCluster++) {
+            if (layout.getCharAdvance(nextCluster - start) != 0.0f) break;
+        }
+        int numGraphemeClusters = 0;
+        int numGraphemeClustersAfter = 0;
+        for (size_t i = lastCluster; i < nextCluster; i++) {
+            bool isAfter = i >= offset;
+            if (GraphemeBreak::isGraphemeBreak(buf, start, count, i)) {
+                numGraphemeClusters++;
+                if (isAfter) {
+                    numGraphemeClustersAfter++;
+                }
+            }
+        }
+        if (numGraphemeClusters > 0) {
+            advance -= clusterWidth * numGraphemeClustersAfter / numGraphemeClusters;
+        }
+    }
+    return advance;
+}
+
+/**
+ * Essentially the inverse of getRunAdvance. Compute the value of offset for which the
+ * measured caret comes closest to the provided advance param, and which is on a grapheme
+ * cluster boundary.
+ *
+ * The actual implementation fast-forwards through clusters to get "close", then does a finer-grain
+ * search within the cluster and grapheme breaks.
+ */
+size_t getOffsetForAdvance(Layout& layout, const uint16_t* buf, size_t start, size_t count,
+        float advance) {
+    float x = 0.0f, xLastClusterStart = 0.0f, xSearchStart = 0.0f;
+    size_t lastClusterStart = start, searchStart = start;
+    for (size_t i = start; i < start + count; i++) {
+        if (GraphemeBreak::isGraphemeBreak(buf, start, count, i)) {
+            searchStart = lastClusterStart;
+            xSearchStart = xLastClusterStart;
+        }
+        float width = layout.getCharAdvance(i - start);
+        if (width != 0.0f) {
+            lastClusterStart = i;
+            xLastClusterStart = x;
+            x += width;
+            if (x > advance) {
+                break;
+            }
+        }
+    }
+    size_t best = searchStart;
+    float bestDist = FLT_MAX;
+    for (size_t i = searchStart; i <= start + count; i++) {
+        if (GraphemeBreak::isGraphemeBreak(buf, start, count, i)) {
+            // "getRunAdvance(layout, buf, start, count, bufSize, i) - advance" but more efficient
+            float delta = getRunAdvance(layout, buf, searchStart, count, i) + xSearchStart
+                    - advance;
+            if (std::abs(delta) < bestDist) {
+                bestDist = std::abs(delta);
+                best = i;
+            }
+            if (delta >= 0.0f) {
+                break;
+            }
+        }
+    }
+    return best;
+}
+
+}