Add TextLayout Cache

- use GenerationCache for caching
- move GenerationCache.h from libs/hwui/utils to include/utils
- add #define for cache activation / deactivation

Change-Id: Ifaf519f0b5e33b087a453e4aa6430162d8438f20

6 files changed, 614 insertions, 89 deletions

diff --git a/core/jni/Android.mk b/core/jni/Android.mk
index 41baca2..12eda8e 100644
--- a/core/jni/Android.mk
+++ b/core/jni/Android.mk
@@ -112,6 +112,7 @@ LOCAL_SRC_FILES:= \
 	android/graphics/Shader.cpp \
 	android/graphics/SurfaceTexture.cpp \
 	android/graphics/TextLayout.cpp \
+	android/graphics/TextLayoutCache.cpp \
 	android/graphics/Typeface.cpp \
 	android/graphics/Utils.cpp \
 	android/graphics/Xfermode.cpp \
diff --git a/core/jni/android/graphics/RtlProperties.h b/core/jni/android/graphics/RtlProperties.h
new file mode 100644
index 0000000..6d8ba91
--- /dev/null
+++ b/core/jni/android/graphics/RtlProperties.h
@@ -0,0 +1,49 @@
+/*
+ * Copyright (C) 2011 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 ANDROID_RTL_PROPERTIES_H
+#define ANDROID_RTL_PROPERTIES_H
+
+#include <cutils/properties.h>
+#include <stdlib.h>
+
+namespace android {
+
+/**
+ * Debug level for app developers.
+ */
+#define RTL_PROPERTY_DEBUG "rtl.debug_level"
+
+/**
+ * Debug levels. Debug levels are used as flags.
+ */
+enum RtlDebugLevel {
+    kRtlDebugDisabled = 0,
+    kRtlDebugMemory = 1,
+    kRtlDebugCaches = 2,
+    kRtlDebugAllocations = 3
+};
+
+static RtlDebugLevel readRtlDebugLevel() {
+    char property[PROPERTY_VALUE_MAX];
+    if (property_get(RTL_PROPERTY_DEBUG, property, NULL) > 0) {
+        return (RtlDebugLevel) atoi(property);
+    }
+    return kRtlDebugDisabled;
+}
+
+} // namespace android
+#endif // ANDROID_RTL_PROPERTIES_H
diff --git a/core/jni/android/graphics/TextLayout.cpp b/core/jni/android/graphics/TextLayout.cpp
index e957635..f1bb696 100644
--- a/core/jni/android/graphics/TextLayout.cpp
+++ b/core/jni/android/graphics/TextLayout.cpp
@@ -15,6 +15,7 @@
  */
 
 #include "TextLayout.h"
+#include "TextLayoutCache.h"
 
 #include <android_runtime/AndroidRuntime.h>
 
@@ -23,10 +24,12 @@
 #include "unicode/ushape.h"
 #include <utils/Log.h>
 
-// Log debug messages from RTL related allocations
-#define DEBUG_RTL_ALLOCATIONS 0
-
 namespace android {
+
+#if USE_TEXT_LAYOUT_CACHE
+TextLayoutCache TextLayout::mCache;
+#endif
+
 // Returns true if we might need layout.  If bidiFlags force LTR, assume no layout, if
 // bidiFlags indicate there probably is RTL, assume we do, otherwise scan the text
 // looking for a character >= the first RTL character in unicode and assume we do if
@@ -60,14 +63,10 @@ bool TextLayout::needsLayout(const jchar* text, jint len, jint bidiFlags) {
  * @return the length of the shaped text, or -1 if error
  */
 int TextLayout::shapeRtlText(const jchar* context, jsize start, jsize count, jsize contextCount,
-                        jchar* shaped, UErrorCode &status) {
+                        jchar* shaped, UErrorCode& status) {
     SkAutoSTMalloc<CHAR_BUFFER_SIZE, jchar> tempBuffer(contextCount);
     jchar* buffer = tempBuffer.get();
 
-#if DEBUG_RTL_ALLOCATIONS
-    LOGD("TextLayout::shapeRtlText - allocated buffer with size: %d", contextCount);
-#endif
-
     // Use fixed length since we need to keep start and count valid
     u_shapeArabic(context, contextCount, buffer, contextCount,
                    U_SHAPE_LENGTH_FIXED_SPACES_NEAR |
@@ -105,8 +104,8 @@ int TextLayout::shapeRtlText(const jchar* context, jsize start, jsize count, jsi
  * @flags line bidi flags
  * @return the length of the reordered, shaped line, or -1 if error
  */
-jint TextLayout::layoutLine(const jchar* text, jint len, jint flags, int &dir, jchar* buffer,
-        UErrorCode &status) {
+jint TextLayout::layoutLine(const jchar* text, jint len, jint flags, int& dir, jchar* buffer,
+        UErrorCode& status) {
     static const int RTL_OPTS = UBIDI_DO_MIRRORING | UBIDI_KEEP_BASE_COMBINING |
             UBIDI_REMOVE_BIDI_CONTROLS | UBIDI_OUTPUT_REVERSE;
 
@@ -156,7 +155,7 @@ jint TextLayout::layoutLine(const jchar* text, jint len, jint flags, int &dir, j
     return result;
 }
 
-bool TextLayout::prepareText(SkPaint *paint, const jchar* text, jsize len, jint bidiFlags,
+bool TextLayout::prepareText(SkPaint* paint, const jchar* text, jsize len, jint bidiFlags,
         const jchar** outText, int32_t* outBytes, jchar** outBuffer) {
     const jchar *workText = text;
     jchar *buffer = NULL;
@@ -166,11 +165,6 @@ bool TextLayout::prepareText(SkPaint *paint, const jchar* text, jsize len, jint
         if (!buffer) {
             return false;
         }
-
-#if DEBUG_RTL_ALLOCATIONS
-    LOGD("TextLayout::prepareText - allocated buffer with size: %d", len);
-#endif
-
         UErrorCode status = U_ZERO_ERROR;
         len = layoutLine(text, len, bidiFlags, dir, buffer, status); // might change len, dir
         if (!U_SUCCESS(status)) {
@@ -178,7 +172,6 @@ bool TextLayout::prepareText(SkPaint *paint, const jchar* text, jsize len, jint
             free(buffer);
             return false; // can't render
         }
-
         workText = buffer; // use the shaped text
     }
 
@@ -262,74 +255,24 @@ void TextLayout::drawTextRun(SkPaint* paint, const jchar* chars,
      }
  }
 
-void TextLayout::getTextRunAdvances(SkPaint *paint, const jchar *chars, jint start,
+void TextLayout::getTextRunAdvances(SkPaint* paint, const jchar* chars, jint start,
                                     jint count, jint contextCount, jint dirFlags,
-                                    jfloat *resultAdvances, jfloat &resultTotalAdvance) {
-    resultTotalAdvance = 0;
-
-    SkAutoSTMalloc<CHAR_BUFFER_SIZE, jchar> tempBuffer(contextCount);
-    jchar* buffer = tempBuffer.get();
-
-#if DEBUG_RTL_ALLOCATIONS
-    LOGD("TextLayout::getTextRunAdvances - allocated buffer with size: %d", contextCount);
+                                    jfloat* resultAdvances, jfloat& resultTotalAdvance) {
+#if USE_TEXT_LAYOUT_CACHE
+    // Return advances from the cache. Compute them if needed
+    mCache.getRunAdvances(paint, chars, start, count, contextCount,
+            dirFlags, resultAdvances, &resultTotalAdvance);
+#else
+    // Compute advances and return them
+    RunAdvanceDescription::computeAdvances(paint, chars, start, count, contextCount, dirFlags,
+            resultAdvances, &resultTotalAdvance);
 #endif
-
-    SkScalar* scalarArray = (SkScalar*)resultAdvances;
-
-    // this is where we'd call harfbuzz
-    // for now we just use ushape.c
-
-    int widths;
-    const jchar* text;
-    if (dirFlags & 0x1) { // rtl, call arabic shaping in case
-        UErrorCode status = U_ZERO_ERROR;
-        // Use fixed length since we need to keep start and count valid
-        u_shapeArabic(chars, contextCount, buffer, contextCount,
-                      U_SHAPE_LENGTH_FIXED_SPACES_NEAR |
-                      U_SHAPE_TEXT_DIRECTION_LOGICAL | U_SHAPE_LETTERS_SHAPE |
-                      U_SHAPE_X_LAMALEF_SUB_ALTERNATE, &status);
-        // we shouldn't fail unless there's an out of memory condition,
-        // in which case we're hosed anyway
-        for (int i = start, e = i + count; i < e; ++i) {
-          if (buffer[i] == UNICODE_NOT_A_CHAR) {
-            buffer[i] = UNICODE_ZWSP; // zero-width-space for skia
-          }
-        }
-        text = buffer + start;
-        widths = paint->getTextWidths(text, count << 1, scalarArray);
-    } else {
-        text = chars + start;
-        widths = paint->getTextWidths(text, count << 1, scalarArray);
-    }
-
-    if (widths < count) {
-        // Skia operates on code points, not code units, so surrogate pairs return only
-        // one value. Expand the result so we have one value per UTF-16 code unit.
-
-        // Note, skia's getTextWidth gets confused if it encounters a surrogate pair,
-        // leaving the remaining widths zero.  Not nice.
-        for (int i = 0, p = 0; i < widths; ++i) {
-            resultTotalAdvance += resultAdvances[p++] = SkScalarToFloat(scalarArray[i]);
-            if (p < count &&
-                    text[p] >= UNICODE_FIRST_LOW_SURROGATE &&
-                    text[p] < UNICODE_FIRST_PRIVATE_USE &&
-                    text[p-1] >= UNICODE_FIRST_HIGH_SURROGATE &&
-                    text[p-1] < UNICODE_FIRST_LOW_SURROGATE) {
-                resultAdvances[p++] = 0;
-            }
-        }
-    } else {
-        for (int i = 0; i < count; i++) {
-            resultTotalAdvance += resultAdvances[i] = SkScalarToFloat(scalarArray[i]);
-        }
-    }
 }
 
 
 // Draws a paragraph of text on a single line, running bidi and shaping
 void TextLayout::drawText(SkPaint* paint, const jchar* text, jsize len,
                           int bidiFlags, jfloat x, jfloat y, SkCanvas* canvas) {
-
     handleText(paint, text, len, bidiFlags, x, y, canvas, NULL);
 }
 
@@ -353,10 +296,6 @@ void TextLayout::drawTextOnPath(SkPaint* paint, const jchar* text, int count,
 
     SkAutoSTMalloc<CHAR_BUFFER_SIZE, jchar> buffer(count);
 
-#if DEBUG_RTL_ALLOCATIONS
-    LOGD("TextLayout::drawTextOnPath - allocated buffer with size: %d", count);
-#endif
-
     int dir = kDirection_LTR;
     UErrorCode status = U_ZERO_ERROR;
     count = layoutLine(text, count, bidiFlags, dir, buffer.get(), status);
diff --git a/core/jni/android/graphics/TextLayout.h b/core/jni/android/graphics/TextLayout.h
index c98f745..a950d13 100644
--- a/core/jni/android/graphics/TextLayout.h
+++ b/core/jni/android/graphics/TextLayout.h
@@ -20,6 +20,8 @@
 #include "SkPaint.h"
 #include "unicode/utypes.h"
 
+#include "TextLayoutCache.h"
+
 namespace android {
 
 #define UNICODE_NOT_A_CHAR              0xffff
@@ -34,6 +36,11 @@ namespace android {
  */
 #define CHAR_BUFFER_SIZE 80
 
+/**
+ * Turn on for using the Cache
+ */
+#define USE_TEXT_LAYOUT_CACHE 1
+
 class TextLayout {
 public:
 
@@ -62,22 +69,23 @@ public:
                             jint start, jint count, jint contextCount,
                             int dirFlags, jfloat x, jfloat y, SkCanvas* canvas);
 
-    static void getTextRunAdvances(SkPaint *paint, const jchar *chars, jint start,
+    static void getTextRunAdvances(SkPaint* paint, const jchar* chars, jint start,
                                    jint count, jint contextCount, jint dirFlags,
-                                   jfloat *resultAdvances, jfloat &resultTotalAdvance);
+                                   jfloat* resultAdvances, jfloat& resultTotalAdvance);
 
     static void drawText(SkPaint* paint, const jchar* text, jsize len,
                          jint bidiFlags, jfloat x, jfloat y, SkCanvas* canvas);
 
-    static void getTextPath(SkPaint *paint, const jchar *text, jsize len,
-                            jint bidiFlags, jfloat x, jfloat y, SkPath *path);
+    static void getTextPath(SkPaint* paint, const jchar* text, jsize len,
+                            jint bidiFlags, jfloat x, jfloat y, SkPath* path);
 
     static void drawTextOnPath(SkPaint* paint, const jchar* text, jsize len,
                                int bidiFlags, jfloat hOffset, jfloat vOffset,
                                SkPath* path, SkCanvas* canvas);
                                
-   static bool prepareText(SkPaint *paint, const jchar* text, jsize len, jint bidiFlags,
+    static bool prepareText(SkPaint* paint, const jchar* text, jsize len, jint bidiFlags,
         const jchar** outText, int32_t* outBytes, jchar** outBuffer);
+
     static bool prepareRtlTextRun(const jchar* context, jsize start, jsize& count,
         jsize contextCount, jchar* shaped);
         
@@ -85,11 +93,15 @@ public:
 private:
     static bool needsLayout(const jchar* text, jint len, jint bidiFlags);
     static int shapeRtlText(const jchar* context, jsize start, jsize count, jsize contextCount,
-                            jchar* shaped, UErrorCode &status);
+                            jchar* shaped, UErrorCode& status);
     static jint layoutLine(const jchar* text, jint len, jint flags, int &dir, jchar* buffer,
                            UErrorCode &status);
-    static void handleText(SkPaint *paint, const jchar* text, jsize len,
-                           int bidiFlags, jfloat x, jfloat y,SkCanvas *canvas, SkPath *path);
+    static void handleText(SkPaint* paint, const jchar* text, jsize len,
+                           int bidiFlags, jfloat x, jfloat y, SkCanvas* canvas, SkPath* path);
+
+#if USE_TEXT_LAYOUT_CACHE
+    static TextLayoutCache mCache;
+#endif
 };
 
 }
diff --git a/core/jni/android/graphics/TextLayoutCache.cpp b/core/jni/android/graphics/TextLayoutCache.cpp
new file mode 100644
index 0000000..7888769
--- /dev/null
+++ b/core/jni/android/graphics/TextLayoutCache.cpp
@@ -0,0 +1,210 @@
+/*
+ * Copyright (C) 2011 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.
+ */
+
+#include "TextLayoutCache.h"
+
+namespace android {
+
+TextLayoutCache::TextLayoutCache():
+        mCache(GenerationCache<TextLayoutCacheKey, RunAdvanceDescription*>::kUnlimitedCapacity),
+        mSize(0), mMaxSize(MB(DEFAULT_TEXT_LAYOUT_CACHE_SIZE_IN_MB)),
+        mCacheHitCount(0), mNanosecondsSaved(0) {
+    init();
+}
+
+TextLayoutCache::TextLayoutCache(uint32_t max):
+        mCache(GenerationCache<TextLayoutCacheKey, RunAdvanceDescription*>::kUnlimitedCapacity),
+        mSize(0), mMaxSize(max),
+        mCacheHitCount(0), mNanosecondsSaved(0) {
+    init();
+}
+
+TextLayoutCache::~TextLayoutCache() {
+    mCache.clear();
+}
+
+void TextLayoutCache::init() {
+    mCache.setOnEntryRemovedListener(this);
+
+    mDebugLevel = readRtlDebugLevel();
+    mDebugEnabled = mDebugLevel & kRtlDebugCaches;
+    LOGD("Using TextLayoutCache debug level: %d - Debug Enabled: %d", mDebugLevel, mDebugEnabled);
+
+    mCacheStartTime = systemTime(SYSTEM_TIME_MONOTONIC);
+    if (mDebugEnabled) {
+        LOGD("TextLayoutCache start time: %lld", mCacheStartTime);
+    }
+
+    mInitialized = true;
+    if (mDebugEnabled) {
+        LOGD("TextLayoutCache initialization is done");
+    }
+}
+
+/*
+ * Size management
+ */
+
+uint32_t TextLayoutCache::getSize() {
+    return mSize;
+}
+
+uint32_t TextLayoutCache::getMaxSize() {
+    return mMaxSize;
+}
+
+void TextLayoutCache::setMaxSize(uint32_t maxSize) {
+    mMaxSize = maxSize;
+    removeOldests();
+}
+
+void TextLayoutCache::removeOldests() {
+    while (mSize > mMaxSize) {
+        mCache.removeOldest();
+    }
+}
+
+/**
+ *  Callbacks
+ */
+void TextLayoutCache::operator()(TextLayoutCacheKey& text, RunAdvanceDescription*& desc) {
+    if (desc) {
+        size_t totalSizeToDelete = text.getSize() + desc->getSize();
+        mSize -= totalSizeToDelete;
+        if (mDebugEnabled) {
+            LOGD("RunAdvance description deleted, size = %d", totalSizeToDelete);
+        }
+        delete desc;
+    }
+}
+
+/*
+ * Cache clearing
+ */
+void TextLayoutCache::clear() {
+    mCache.clear();
+}
+
+/*
+ * Caching
+ */
+void TextLayoutCache::getRunAdvances(SkPaint* paint, const jchar* text,
+        jint start, jint count, jint contextCount, jint dirFlags,
+        jfloat* outAdvances, jfloat* outTotalAdvance) {
+
+    AutoMutex _l(mLock);
+
+    nsecs_t startTime = 0;
+    if (mDebugEnabled) {
+        startTime = systemTime(SYSTEM_TIME_MONOTONIC);
+    }
+
+    TextLayoutCacheKey entry(paint, text, start, count, contextCount, dirFlags);
+
+    // Get entry for cache if possible
+    RunAdvanceDescription* desc = mCache.get(entry);
+
+    // Value not found for the entry, we need to add a new value in the cache
+    if (!desc) {
+        desc = new RunAdvanceDescription();
+
+        // Compute advances and store them
+        desc->computeAdvances(paint, text, start, count, contextCount, dirFlags);
+        desc->copyResult(outAdvances, outTotalAdvance);
+
+        // Don't bother to add in the cache if the entry is too big
+        size_t size = entry.getSize() + desc->getSize();
+        if (size <= mMaxSize) {
+            // Cleanup to make some room if needed
+            if (mSize + size > mMaxSize) {
+                if (mDebugEnabled) {
+                    LOGD("TextLayoutCache: need to clean some entries "
+                            "for making some room for a new entry");
+                }
+                while (mSize + size > mMaxSize) {
+                    // This will call the callback
+                    mCache.removeOldest();
+                }
+            }
+
+            // Update current cache size
+            mSize += size;
+
+            // Copy the text when we insert the new entry
+            entry.internalTextCopy();
+            mCache.put(entry, desc);
+
+            if (mDebugEnabled) {
+                // Update timing information for statistics.
+                desc->setElapsedTime(systemTime(SYSTEM_TIME_MONOTONIC) - startTime);
+
+                LOGD("CACHE MISS: Added entry for text='%s' with start=%d, count=%d, "
+                        "contextCount=%d, entry size %d bytes, remaining space %d bytes"
+                        " - Compute time in nanos: %d",
+                        String8(text, contextCount).string(), start, count, contextCount,
+                        size, mMaxSize - mSize, desc->getElapsedTime());
+            }
+        } else {
+            if (mDebugEnabled) {
+                LOGD("CACHE MISS: Calculated but not storing entry because it is too big "
+                        "for text='%s' with start=%d, count=%d, contextCount=%d, "
+                        "entry size %d bytes, remaining space %d bytes"
+                        " - Compute time in nanos: %d",
+                        String8(text, contextCount).string(), start, count, contextCount,
+                        size, mMaxSize - mSize, desc->getElapsedTime());
+            }
+            delete desc;
+        }
+    } else {
+        // This is a cache hit, just copy the pre-computed results
+        desc->copyResult(outAdvances, outTotalAdvance);
+        if (mDebugEnabled) {
+            nsecs_t elapsedTimeThruCacheGet = systemTime(SYSTEM_TIME_MONOTONIC) - startTime;
+            mNanosecondsSaved += (desc->getElapsedTime() - elapsedTimeThruCacheGet);
+            ++mCacheHitCount;
+
+            if (desc->getElapsedTime() > 0) {
+                float deltaPercent = 100 * ((desc->getElapsedTime() - elapsedTimeThruCacheGet)
+                        / ((float)desc->getElapsedTime()));
+                LOGD("CACHE HIT #%d for text='%s' with start=%d, count=%d, contextCount=%d "
+                        "- Compute time in nanos: %d - "
+                        "Cache get time in nanos: %lld - Gain in percent: %2.2f",
+                        mCacheHitCount, String8(text, contextCount).string(), start, count,
+                        contextCount,
+                        desc->getElapsedTime(), elapsedTimeThruCacheGet, deltaPercent);
+            }
+            if (mCacheHitCount % DEFAULT_DUMP_STATS_CACHE_HIT_INTERVAL == 0) {
+                dumpCacheStats();
+            }
+        }
+    }
+}
+
+void TextLayoutCache::dumpCacheStats() {
+    float remainingPercent = 100 * ((mMaxSize - mSize) / ((float)mMaxSize));
+    float timeRunningInSec = (systemTime(SYSTEM_TIME_MONOTONIC) - mCacheStartTime) / 1000000000;
+    LOGD("------------------------------------------------");
+    LOGD("TextLayoutCache stats");
+    LOGD("------------------------------------------------");
+    LOGD("running   : %.0f seconds", timeRunningInSec);
+    LOGD("size      : %d bytes", mMaxSize);
+    LOGD("remaining : %d bytes or %2.2f percent", mMaxSize - mSize, remainingPercent);
+    LOGD("hits      : %d", mCacheHitCount);
+    LOGD("saved     : %lld milliseconds", mNanosecondsSaved / 1000000);
+    LOGD("------------------------------------------------");
+}
+
+} // namespace android
diff --git a/core/jni/android/graphics/TextLayoutCache.h b/core/jni/android/graphics/TextLayoutCache.h
new file mode 100644
index 0000000..9d55918
--- /dev/null
+++ b/core/jni/android/graphics/TextLayoutCache.h
@@ -0,0 +1,314 @@
+/*
+ * Copyright (C) 2011 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 ANDROID_TEXT_LAYOUT_CACHE_H
+#define ANDROID_TEXT_LAYOUT_CACHE_H
+
+#include "RtlProperties.h"
+
+#include "stddef.h"
+#include <utils/threads.h>
+#include <utils/String16.h>
+#include "utils/GenerationCache.h"
+#include "utils/Compare.h"
+
+#include "SkPaint.h"
+#include "SkTemplates.h"
+
+#include "unicode/ubidi.h"
+#include "unicode/ushape.h"
+
+#include <android_runtime/AndroidRuntime.h>
+
+#define UNICODE_NOT_A_CHAR              0xffff
+#define UNICODE_ZWSP                    0x200b
+#define UNICODE_FIRST_LOW_SURROGATE     0xdc00
+#define UNICODE_FIRST_HIGH_SURROGATE    0xd800
+#define UNICODE_FIRST_PRIVATE_USE       0xe000
+#define UNICODE_FIRST_RTL_CHAR          0x0590
+
+// Temporary buffer size
+#define CHAR_BUFFER_SIZE 80
+
+// Converts a number of mega-bytes into bytes
+#define MB(s) s * 1024 * 1024
+
+// Define the default cache size in Mb
+#define DEFAULT_TEXT_LAYOUT_CACHE_SIZE_IN_MB 0.125f
+
+// Define the interval in number of cache hits between two statistics dump
+#define DEFAULT_DUMP_STATS_CACHE_HIT_INTERVAL 100
+
+namespace android {
+
+/**
+ * TextLayoutCacheKey is the Cache key
+ */
+class TextLayoutCacheKey {
+public:
+    TextLayoutCacheKey() : text(NULL), start(0), count(0), contextCount(0),
+            dirFlags(0), textSize(0), typeface(NULL), textSkewX(0), fakeBoldText(false)  {
+    }
+
+    TextLayoutCacheKey(const SkPaint* paint,
+            const UChar* text, size_t start, size_t count,
+            size_t contextCount, int dirFlags) :
+                text(text), start(start), count(count), contextCount(contextCount),
+                dirFlags(dirFlags) {
+        textSize = paint->getTextSize();
+        typeface = paint->getTypeface();
+        textSkewX = paint->getTextSkewX();
+        fakeBoldText = paint->isFakeBoldText();
+    }
+
+    bool operator<(const TextLayoutCacheKey& rhs) const {
+        LTE_INT(count) {
+            LTE_INT(contextCount) {
+                LTE_INT(start) {
+                    LTE_FLOAT(textSize) {
+                        LTE_INT(typeface) {
+                            LTE_INT(textSkewX) {
+                                LTE_INT(fakeBoldText) {
+                                    LTE_INT(dirFlags) {
+                                        return strncmp16(text, rhs.text, contextCount) < 0;
+                                    }
+                                }
+                            }
+                        }
+                    }
+                }
+            }
+        }
+        return false;
+    }
+
+    // We need to copy the text when we insert the key into the cache itself.
+    // We don't need to copy the text when we are only comparing keys.
+    void internalTextCopy() {
+        textCopy.setTo(text, contextCount);
+        text = textCopy.string();
+    }
+
+    /**
+     * Get the size of the Cache key.
+     */
+    size_t getSize() {
+        return sizeof(TextLayoutCacheKey) + sizeof(UChar) * contextCount;
+    }
+
+private:
+    const UChar* text;
+    String16 textCopy;
+    size_t start;
+    size_t count;
+    size_t contextCount;
+    int dirFlags;
+    float textSize;
+    SkTypeface* typeface;
+    float textSkewX;
+    bool fakeBoldText;
+}; // TextLayoutCacheKey
+
+/*
+ * RunAdvanceDescription is the Cache entry
+ */
+class RunAdvanceDescription {
+public:
+    RunAdvanceDescription() {
+        advances = NULL;
+        totalAdvance = 0;
+    }
+
+    ~RunAdvanceDescription() {
+        delete[] advances;
+    }
+
+    void setElapsedTime(uint32_t time) {
+        elapsedTime = time;
+    }
+
+    uint32_t getElapsedTime() {
+        return elapsedTime;
+    }
+
+    void computeAdvances(SkPaint* paint, const UChar* chars, size_t start, size_t count,
+            size_t contextCount, int dirFlags) {
+        advances = new float[count];
+        this->count = count;
+
+        computeAdvances(paint, chars, start, count, contextCount, dirFlags,
+                advances, &totalAdvance);
+    }
+
+    void copyResult(jfloat* outAdvances, jfloat* outTotalAdvance) {
+        memcpy(outAdvances, advances, count * sizeof(jfloat));
+        *outTotalAdvance = totalAdvance;
+    }
+
+    /**
+     * Get the size of the Cache entry
+     */
+    size_t getSize() {
+        return sizeof(RunAdvanceDescription) + sizeof(jfloat) * count;
+    }
+
+    static void computeAdvances(SkPaint* paint, const UChar* chars, size_t start, size_t count,
+            size_t contextCount, int dirFlags, jfloat* outAdvances, jfloat* outTotalAdvance) {
+        SkAutoSTMalloc<CHAR_BUFFER_SIZE, jchar> tempBuffer(contextCount);
+        jchar* buffer = tempBuffer.get();
+
+        SkScalar* scalarArray = (SkScalar*)outAdvances;
+
+        // this is where we'd call harfbuzz
+        // for now we just use ushape.c
+        size_t widths;
+        const jchar* text;
+        if (dirFlags & 0x1) { // rtl, call arabic shaping in case
+            UErrorCode status = U_ZERO_ERROR;
+            // Use fixed length since we need to keep start and count valid
+            u_shapeArabic(chars, contextCount, buffer, contextCount,
+                    U_SHAPE_LENGTH_FIXED_SPACES_NEAR |
+                    U_SHAPE_TEXT_DIRECTION_LOGICAL | U_SHAPE_LETTERS_SHAPE |
+                    U_SHAPE_X_LAMALEF_SUB_ALTERNATE, &status);
+            // we shouldn't fail unless there's an out of memory condition,
+            // in which case we're hosed anyway
+            for (int i = start, e = i + count; i < e; ++i) {
+                if (buffer[i] == UNICODE_NOT_A_CHAR) {
+                    buffer[i] = UNICODE_ZWSP; // zero-width-space for skia
+                }
+            }
+            text = buffer + start;
+            widths = paint->getTextWidths(text, count << 1, scalarArray);
+        } else {
+            text = chars + start;
+            widths = paint->getTextWidths(text, count << 1, scalarArray);
+        }
+
+        jfloat totalAdvance = 0;
+        if (widths < count) {
+            // Skia operates on code points, not code units, so surrogate pairs return only
+            // one value. Expand the result so we have one value per UTF-16 code unit.
+
+            // Note, skia's getTextWidth gets confused if it encounters a surrogate pair,
+            // leaving the remaining widths zero.  Not nice.
+            for (size_t i = 0, p = 0; i < widths; ++i) {
+                totalAdvance += outAdvances[p++] = SkScalarToFloat(scalarArray[i]);
+                if (p < count &&
+                        text[p] >= UNICODE_FIRST_LOW_SURROGATE &&
+                        text[p] < UNICODE_FIRST_PRIVATE_USE &&
+                        text[p-1] >= UNICODE_FIRST_HIGH_SURROGATE &&
+                        text[p-1] < UNICODE_FIRST_LOW_SURROGATE) {
+                    outAdvances[p++] = 0;
+                }
+            }
+        } else {
+            for (size_t i = 0; i < count; i++) {
+                totalAdvance += outAdvances[i] = SkScalarToFloat(scalarArray[i]);
+            }
+        }
+        *outTotalAdvance = totalAdvance;
+    }
+
+private:
+    jfloat* advances;
+    jfloat totalAdvance;
+    size_t count;
+
+    uint32_t elapsedTime;
+}; // RunAdvanceDescription
+
+
+class TextLayoutCache: public OnEntryRemoved<TextLayoutCacheKey, RunAdvanceDescription*>
+{
+public:
+    TextLayoutCache();
+    TextLayoutCache(uint32_t maxByteSize);
+
+    virtual ~TextLayoutCache();
+
+    bool isInitialized() {
+        return mInitialized;
+    }
+
+    /**
+     * Used as a callback when an entry is removed from the cache.
+     * Do not invoke directly.
+     */
+    void operator()(TextLayoutCacheKey& text, RunAdvanceDescription*& desc);
+
+    /**
+     * Get cache entries
+     */
+    void getRunAdvances(SkPaint* paint, const jchar* text,
+            jint start, jint count, jint contextCount, jint dirFlags,
+            jfloat* outAdvances, jfloat* outTotalAdvance);
+
+    /**
+     * Clear the cache
+     */
+    void clear();
+
+    /**
+     * Sets the maximum size of the cache in bytes.
+     */
+    void setMaxSize(uint32_t maxSize);
+
+    /**
+     * Returns the maximum size of the cache in bytes.
+     */
+    uint32_t getMaxSize();
+
+    /**
+     * Returns the current size of the cache in bytes.
+     */
+    uint32_t getSize();
+
+private:
+    Mutex mLock;
+    bool mInitialized;
+
+    GenerationCache<TextLayoutCacheKey, RunAdvanceDescription*> mCache;
+
+    uint32_t mSize;
+    uint32_t mMaxSize;
+
+    uint32_t mCacheHitCount;
+    uint64_t mNanosecondsSaved;
+
+    uint64_t mCacheStartTime;
+
+    RtlDebugLevel mDebugLevel;
+    bool mDebugEnabled;
+
+    /*
+     * Class initialization
+     */
+    void init();
+
+    /**
+     * Remove oldest entries until we are having enough space
+     */
+    void removeOldests();
+
+    /**
+     * Dump Cache statistics
+     */
+    void dumpCacheStats();
+}; // TextLayoutCache
+
+} // namespace android
+#endif /* ANDROID_TEXT_LAYOUT_CACHE_H */
+