| /* |
| * Copyright (C) 2014 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 "StaticLayout" |
| |
| #include "ScopedIcuLocale.h" |
| #include "unicode/locid.h" |
| #include "unicode/brkiter.h" |
| #include "utils/misc.h" |
| #include "utils/Log.h" |
| #include "ScopedPrimitiveArray.h" |
| #include "JNIHelp.h" |
| #include "core_jni_helpers.h" |
| #include <cstdint> |
| #include <vector> |
| #include <list> |
| #include <algorithm> |
| |
| namespace android { |
| |
| struct JLineBreaksID { |
| jfieldID breaks; |
| jfieldID widths; |
| jfieldID flags; |
| }; |
| |
| static jclass gLineBreaks_class; |
| static JLineBreaksID gLineBreaks_fieldID; |
| |
| static const int CHAR_SPACE = 0x20; |
| static const int CHAR_TAB = 0x09; |
| static const int CHAR_NEWLINE = 0x0a; |
| static const int CHAR_ZWSP = 0x200b; |
| |
| class TabStops { |
| public: |
| // specified stops must be a sorted array (allowed to be null) |
| TabStops(JNIEnv* env, jintArray stops, jint defaultTabWidth) : |
| mStops(env), mTabWidth(defaultTabWidth) { |
| if (stops != NULL) { |
| mStops.reset(stops); |
| mNumStops = mStops.size(); |
| } else { |
| mNumStops = 0; |
| } |
| } |
| float width(float widthSoFar) const { |
| const jint* mStopsArray = mStops.get(); |
| for (int i = 0; i < mNumStops; i++) { |
| if (mStopsArray[i] > widthSoFar) { |
| return mStopsArray[i]; |
| } |
| } |
| // find the next tabstop after widthSoFar |
| return static_cast<int>((widthSoFar + mTabWidth) / mTabWidth) * mTabWidth; |
| } |
| private: |
| ScopedIntArrayRO mStops; |
| const int mTabWidth; |
| int mNumStops; |
| |
| // disable copying and assignment |
| TabStops(const TabStops&); |
| void operator=(const TabStops&); |
| }; |
| |
| enum PrimitiveType { |
| kPrimitiveType_Box, |
| kPrimitiveType_Glue, |
| kPrimitiveType_Penalty, |
| kPrimitiveType_Variable, |
| kPrimitiveType_Wordbreak |
| }; |
| |
| static const float PENALTY_INFINITY = 1e7; // forced non-break, negative infinity is forced break |
| |
| struct Primitive { |
| PrimitiveType type; |
| int location; |
| // 'Box' has width |
| // 'Glue' has width |
| // 'Penalty' has width and penalty |
| // 'Variable' has tabStop |
| // 'Wordbreak' has penalty |
| union { |
| struct { |
| float width; |
| float penalty; |
| }; |
| const TabStops* tabStop; |
| }; |
| }; |
| |
| class LineWidth { |
| public: |
| LineWidth(float firstWidth, int firstWidthLineCount, float restWidth) : |
| mFirstWidth(firstWidth), mFirstWidthLineCount(firstWidthLineCount), |
| mRestWidth(restWidth) {} |
| float getLineWidth(int line) const { |
| return (line < mFirstWidthLineCount) ? mFirstWidth : mRestWidth; |
| } |
| private: |
| const float mFirstWidth; |
| const int mFirstWidthLineCount; |
| const float mRestWidth; |
| }; |
| |
| class LineBreaker { |
| public: |
| LineBreaker(const std::vector<Primitive>& primitives, |
| const LineWidth& lineWidth) : |
| mPrimitives(primitives), mLineWidth(lineWidth) {} |
| virtual ~LineBreaker() {} |
| virtual void computeBreaks(std::vector<int>* breaks, std::vector<float>* widths, |
| std::vector<unsigned char>* flags) const = 0; |
| protected: |
| const std::vector<Primitive>& mPrimitives; |
| const LineWidth& mLineWidth; |
| }; |
| |
| class OptimizingLineBreaker : public LineBreaker { |
| public: |
| OptimizingLineBreaker(const std::vector<Primitive>& primitives, const LineWidth& lineWidth) : |
| LineBreaker(primitives, lineWidth) {} |
| void computeBreaks(std::vector<int>* breaks, std::vector<float>* widths, |
| std::vector<unsigned char>* flags) const { |
| int numBreaks = mPrimitives.size(); |
| Node* opt = new Node[numBreaks]; |
| opt[0].prev = -1; |
| opt[0].prevCount = 0; |
| opt[0].width = 0; |
| opt[0].demerits = 0; |
| opt[0].flags = false; |
| opt[numBreaks - 1].prev = -1; |
| opt[numBreaks - 1].prevCount = 0; |
| |
| std::list<int> active; |
| active.push_back(0); |
| int lastBreak = 0; |
| for (int i = 0; i < numBreaks; i++) { |
| const Primitive& p = mPrimitives[i]; |
| if (p.type == kPrimitiveType_Penalty) { |
| const bool finalBreak = (i + 1 == numBreaks); |
| bool breakFound = false; |
| Node bestBreak; |
| for (std::list<int>::iterator it = active.begin(); it != active.end(); /* incrementing done in loop */) { |
| const int pos = *it; |
| bool flags; |
| float width, printedWidth; |
| const int lines = opt[pos].prevCount; |
| const float maxWidth = mLineWidth.getLineWidth(lines); |
| // we have to compute metrics every time -- |
| // we can't really precompute this stuff and just deal with breaks |
| // because of the way tab characters work, this makes it computationally |
| // harder, but this way, we can still optimize while treating tab characters |
| // correctly |
| computeMetrics(pos, i, &width, &printedWidth, &flags); |
| if (printedWidth <= maxWidth) { |
| float demerits = computeDemerits(maxWidth, printedWidth, |
| finalBreak, p.penalty) + opt[pos].demerits; |
| if (!breakFound || demerits < bestBreak.demerits) { |
| bestBreak.prev = pos; |
| bestBreak.prevCount = opt[pos].prevCount + 1; |
| bestBreak.demerits = demerits; |
| bestBreak.width = printedWidth; |
| bestBreak.flags = flags; |
| breakFound = true; |
| } |
| ++it; |
| } else { |
| active.erase(it++); // safe to delete like this |
| } |
| } |
| if (p.penalty == -PENALTY_INFINITY) { |
| active.clear(); |
| } |
| if (breakFound) { |
| opt[i] = bestBreak; |
| active.push_back(i); |
| lastBreak = i; |
| } |
| if (active.empty()) { |
| // we can't give up! |
| float width, printedWidth; |
| bool flags; |
| const int lines = opt[lastBreak].prevCount; |
| const float maxWidth = mLineWidth.getLineWidth(lines); |
| const int breakIndex = desperateBreak(lastBreak, numBreaks, maxWidth, &width, &printedWidth, &flags); |
| |
| opt[breakIndex].prev = lastBreak; |
| opt[breakIndex].prevCount = lines + 1; |
| opt[breakIndex].demerits = 0; // doesn't matter, it's the only one |
| opt[breakIndex].width = width; |
| opt[breakIndex].flags = flags; |
| |
| active.push_back(breakIndex); |
| lastBreak = breakIndex; |
| i = breakIndex; // incremented by i++ |
| } |
| } |
| } |
| |
| int idx = numBreaks - 1; |
| int count = opt[idx].prevCount; |
| breaks->resize(count); |
| widths->resize(count); |
| flags->resize(count); |
| while (opt[idx].prev != -1) { |
| --count; |
| |
| (*breaks)[count] = mPrimitives[idx].location; |
| (*widths)[count] = opt[idx].width; |
| (*flags)[count] = opt[idx].flags; |
| |
| idx = opt[idx].prev; |
| } |
| delete[] opt; |
| } |
| private: |
| inline void computeMetrics(int start, int end, float* width, float* printedWidth, bool* flags) const { |
| bool f = false; |
| float w = 0, pw = 0; |
| for (int i = start; i < end; i++) { |
| const Primitive& p = mPrimitives[i]; |
| if (p.type == kPrimitiveType_Box || p.type == kPrimitiveType_Glue) { |
| w += p.width; |
| if (p.type == kPrimitiveType_Box) { |
| pw = w; |
| } |
| } else if (p.type == kPrimitiveType_Variable) { |
| w = p.tabStop->width(w); |
| f = true; |
| } |
| } |
| *width = w; |
| *printedWidth = pw; |
| *flags = f; |
| } |
| |
| inline float computeDemerits(float maxWidth, float width, bool finalBreak, float penalty) const { |
| float deviation = finalBreak ? 0 : maxWidth - width; |
| return (deviation * deviation) + penalty; |
| } |
| |
| // returns end pos (chosen break), -1 if fail |
| inline int desperateBreak(int start, int limit, float maxWidth, float* width, float* printedWidth, bool* flags) const { |
| float w = 0, pw = 0; |
| bool breakFound = false; |
| int breakIndex = 0, firstTabIndex = INT_MAX; |
| for (int i = start; i < limit; i++) { |
| const Primitive& p = mPrimitives[i]; |
| |
| if (p.type == kPrimitiveType_Box || p.type == kPrimitiveType_Glue) { |
| w += p.width; |
| if (p.type == kPrimitiveType_Box) { |
| pw = w; |
| } |
| } else if (p.type == kPrimitiveType_Variable) { |
| w = p.tabStop->width(w); |
| firstTabIndex = std::min(firstTabIndex, i); |
| } |
| |
| if (pw > maxWidth) { |
| if (breakFound) { |
| break; |
| } else { |
| // no choice, keep going |
| } |
| } |
| |
| // must make progress |
| if (i > start && (p.type == kPrimitiveType_Penalty || p.type == kPrimitiveType_Wordbreak)) { |
| breakFound = true; |
| breakIndex = i; |
| } |
| } |
| |
| if (breakFound) { |
| *width = w; |
| *printedWidth = pw; |
| *flags = (start <= firstTabIndex && firstTabIndex < breakIndex); |
| return breakIndex; |
| } else { |
| return -1; |
| } |
| } |
| |
| struct Node { |
| int prev; // set to sentinel value (-1) for initial node |
| int prevCount; // number of breaks so far |
| float demerits; |
| float width; |
| bool flags; |
| }; |
| }; |
| |
| class GreedyLineBreaker : public LineBreaker { |
| public: |
| GreedyLineBreaker(const std::vector<Primitive>& primitives, const LineWidth& lineWidth) : |
| LineBreaker(primitives, lineWidth) {} |
| void computeBreaks(std::vector<int>* breaks, std::vector<float>* widths, |
| std::vector<unsigned char>* flags) const { |
| int lineNum = 0; |
| float width = 0, printedWidth = 0; |
| bool breakFound = false, goodBreakFound = false; |
| int breakIndex = 0, goodBreakIndex = 0; |
| float breakWidth = 0, goodBreakWidth = 0; |
| int firstTabIndex = INT_MAX; |
| |
| float maxWidth = mLineWidth.getLineWidth(lineNum); |
| |
| const int numPrimitives = mPrimitives.size(); |
| // greedily fit as many characters as possible on each line |
| // loop over all primitives, and choose the best break point |
| // (if possible, a break point without splitting a word) |
| // after going over the maximum length |
| for (int i = 0; i < numPrimitives; i++) { |
| const Primitive& p = mPrimitives[i]; |
| |
| // update the current line width |
| if (p.type == kPrimitiveType_Box || p.type == kPrimitiveType_Glue) { |
| width += p.width; |
| if (p.type == kPrimitiveType_Box) { |
| printedWidth = width; |
| } |
| } else if (p.type == kPrimitiveType_Variable) { |
| width = p.tabStop->width(width); |
| // keep track of first tab character in the region we are examining |
| // so we can determine whether or not a line contains a tab |
| firstTabIndex = std::min(firstTabIndex, i); |
| } |
| |
| // find the best break point for the characters examined so far |
| if (printedWidth > maxWidth) { |
| if (breakFound || goodBreakFound) { |
| if (goodBreakFound) { |
| // a true line break opportunity existed in the characters examined so far, |
| // so there is no need to split a word |
| i = goodBreakIndex; // no +1 because of i++ |
| lineNum++; |
| maxWidth = mLineWidth.getLineWidth(lineNum); |
| breaks->push_back(mPrimitives[goodBreakIndex].location); |
| widths->push_back(goodBreakWidth); |
| flags->push_back(firstTabIndex < goodBreakIndex); |
| firstTabIndex = INT_MAX; |
| } else { |
| // must split a word because there is no other option |
| i = breakIndex; // no +1 because of i++ |
| lineNum++; |
| maxWidth = mLineWidth.getLineWidth(lineNum); |
| breaks->push_back(mPrimitives[breakIndex].location); |
| widths->push_back(breakWidth); |
| flags->push_back(firstTabIndex < breakIndex); |
| firstTabIndex = INT_MAX; |
| } |
| printedWidth = width = 0; |
| goodBreakFound = breakFound = false; |
| goodBreakWidth = breakWidth = 0; |
| continue; |
| } else { |
| // no choice, keep going... must make progress by putting at least one |
| // character on a line, even if part of that character is cut off -- |
| // there is no other option |
| } |
| } |
| |
| // update possible break points |
| if (p.type == kPrimitiveType_Penalty && p.penalty < PENALTY_INFINITY) { |
| // this does not handle penalties with width |
| |
| // handle forced line break |
| if (p.penalty == -PENALTY_INFINITY) { |
| lineNum++; |
| maxWidth = mLineWidth.getLineWidth(lineNum); |
| breaks->push_back(p.location); |
| widths->push_back(printedWidth); |
| flags->push_back(firstTabIndex < i); |
| firstTabIndex = INT_MAX; |
| printedWidth = width = 0; |
| goodBreakFound = breakFound = false; |
| goodBreakWidth = breakWidth = 0; |
| continue; |
| } |
| if (i > breakIndex && (printedWidth <= maxWidth || breakFound == false)) { |
| breakFound = true; |
| breakIndex = i; |
| breakWidth = printedWidth; |
| } |
| if (i > goodBreakIndex && printedWidth <= maxWidth) { |
| goodBreakFound = true; |
| goodBreakIndex = i; |
| goodBreakWidth = printedWidth; |
| } |
| } else if (p.type == kPrimitiveType_Wordbreak) { |
| // only do this if necessary -- we don't want to break words |
| // when possible, but sometimes it is unavoidable |
| if (i > breakIndex && (printedWidth <= maxWidth || breakFound == false)) { |
| breakFound = true; |
| breakIndex = i; |
| breakWidth = printedWidth; |
| } |
| } |
| } |
| |
| if (breakFound || goodBreakFound) { |
| // output last break if there are more characters to output |
| if (goodBreakFound) { |
| breaks->push_back(mPrimitives[goodBreakIndex].location); |
| widths->push_back(goodBreakWidth); |
| flags->push_back(firstTabIndex < goodBreakIndex); |
| } else { |
| breaks->push_back(mPrimitives[breakIndex].location); |
| widths->push_back(breakWidth); |
| flags->push_back(firstTabIndex < breakIndex); |
| } |
| } |
| } |
| }; |
| |
| class ScopedBreakIterator { |
| public: |
| ScopedBreakIterator(JNIEnv* env, BreakIterator* breakIterator, const jchar* inputText, |
| jint length) : mBreakIterator(breakIterator), mChars(inputText) { |
| UErrorCode status = U_ZERO_ERROR; |
| mUText = utext_openUChars(NULL, mChars, length, &status); |
| if (mUText == NULL) { |
| return; |
| } |
| |
| mBreakIterator->setText(mUText, status); |
| } |
| |
| inline BreakIterator* operator->() { |
| return mBreakIterator; |
| } |
| |
| ~ScopedBreakIterator() { |
| utext_close(mUText); |
| delete mBreakIterator; |
| } |
| private: |
| BreakIterator* mBreakIterator; |
| const jchar* mChars; |
| UText* mUText; |
| |
| // disable copying and assignment |
| ScopedBreakIterator(const ScopedBreakIterator&); |
| void operator=(const ScopedBreakIterator&); |
| }; |
| |
| static jint recycleCopy(JNIEnv* env, jobject recycle, jintArray recycleBreaks, |
| jfloatArray recycleWidths, jbooleanArray recycleFlags, |
| jint recycleLength, const std::vector<jint>& breaks, |
| const std::vector<jfloat>& widths, const std::vector<jboolean>& flags) { |
| int bufferLength = breaks.size(); |
| if (recycleLength < bufferLength) { |
| // have to reallocate buffers |
| recycleBreaks = env->NewIntArray(bufferLength); |
| recycleWidths = env->NewFloatArray(bufferLength); |
| recycleFlags = env->NewBooleanArray(bufferLength); |
| |
| env->SetObjectField(recycle, gLineBreaks_fieldID.breaks, recycleBreaks); |
| env->SetObjectField(recycle, gLineBreaks_fieldID.widths, recycleWidths); |
| env->SetObjectField(recycle, gLineBreaks_fieldID.flags, recycleFlags); |
| } |
| // copy data |
| env->SetIntArrayRegion(recycleBreaks, 0, breaks.size(), &breaks.front()); |
| env->SetFloatArrayRegion(recycleWidths, 0, widths.size(), &widths.front()); |
| env->SetBooleanArrayRegion(recycleFlags, 0, flags.size(), &flags.front()); |
| |
| return bufferLength; |
| } |
| |
| void computePrimitives(const jchar* textArr, const jfloat* widthsArr, jint length, const std::vector<int>& breaks, |
| const TabStops& tabStopCalculator, std::vector<Primitive>* primitives) { |
| int breaksSize = breaks.size(); |
| int breakIndex = 0; |
| Primitive p; |
| for (int i = 0; i < length; i++) { |
| p.location = i; |
| jchar c = textArr[i]; |
| if (c == CHAR_SPACE || c == CHAR_ZWSP) { |
| p.type = kPrimitiveType_Glue; |
| p.width = widthsArr[i]; |
| primitives->push_back(p); |
| } else if (c == CHAR_TAB) { |
| p.type = kPrimitiveType_Variable; |
| p.tabStop = &tabStopCalculator; // shared between all variable primitives |
| primitives->push_back(p); |
| } else if (c != CHAR_NEWLINE) { |
| while (breakIndex < breaksSize && breaks[breakIndex] < i) breakIndex++; |
| p.width = 0; |
| if (breakIndex < breaksSize && breaks[breakIndex] == i) { |
| p.type = kPrimitiveType_Penalty; |
| p.penalty = 0; |
| } else { |
| p.type = kPrimitiveType_Wordbreak; |
| } |
| if (widthsArr[i] != 0) { |
| primitives->push_back(p); |
| } |
| |
| p.type = kPrimitiveType_Box; |
| p.width = widthsArr[i]; |
| primitives->push_back(p); |
| } |
| } |
| // final break at end of everything |
| p.location = length; |
| p.type = kPrimitiveType_Penalty; |
| p.width = 0; |
| p.penalty = -PENALTY_INFINITY; |
| primitives->push_back(p); |
| } |
| |
| static jint nComputeLineBreaks(JNIEnv* env, jclass, jstring javaLocaleName, |
| jcharArray inputText, jfloatArray widths, jint length, |
| jfloat firstWidth, jint firstWidthLineLimit, jfloat restWidth, |
| jintArray variableTabStops, jint defaultTabStop, jboolean optimize, |
| jobject recycle, jintArray recycleBreaks, |
| jfloatArray recycleWidths, jbooleanArray recycleFlags, |
| jint recycleLength) { |
| std::vector<int> breaks; |
| |
| ScopedCharArrayRO textScopedArr(env, inputText); |
| ScopedFloatArrayRO widthsScopedArr(env, widths); |
| |
| ScopedIcuLocale icuLocale(env, javaLocaleName); |
| if (icuLocale.valid()) { |
| UErrorCode status = U_ZERO_ERROR; |
| BreakIterator* it = BreakIterator::createLineInstance(icuLocale.locale(), status); |
| if (!U_SUCCESS(status) || it == NULL) { |
| if (it) { |
| delete it; |
| } |
| } else { |
| ScopedBreakIterator breakIterator(env, it, textScopedArr.get(), length); |
| int loc = breakIterator->first(); |
| while ((loc = breakIterator->next()) != BreakIterator::DONE) { |
| breaks.push_back(loc); |
| } |
| } |
| } |
| |
| std::vector<Primitive> primitives; |
| TabStops tabStops(env, variableTabStops, defaultTabStop); |
| computePrimitives(textScopedArr.get(), widthsScopedArr.get(), length, breaks, tabStops, &primitives); |
| |
| LineWidth lineWidth(firstWidth, firstWidthLineLimit, restWidth); |
| std::vector<int> computedBreaks; |
| std::vector<float> computedWidths; |
| std::vector<unsigned char> computedFlags; |
| |
| if (optimize) { |
| OptimizingLineBreaker breaker(primitives, lineWidth); |
| breaker.computeBreaks(&computedBreaks, &computedWidths, &computedFlags); |
| } else { |
| GreedyLineBreaker breaker(primitives, lineWidth); |
| breaker.computeBreaks(&computedBreaks, &computedWidths, &computedFlags); |
| } |
| |
| return recycleCopy(env, recycle, recycleBreaks, recycleWidths, recycleFlags, recycleLength, |
| computedBreaks, computedWidths, computedFlags); |
| } |
| |
| static JNINativeMethod gMethods[] = { |
| {"nComputeLineBreaks", "(Ljava/lang/String;[C[FIFIF[IIZLandroid/text/StaticLayout$LineBreaks;[I[F[ZI)I", (void*) nComputeLineBreaks} |
| }; |
| |
| int register_android_text_StaticLayout(JNIEnv* env) |
| { |
| gLineBreaks_class = MakeGlobalRefOrDie(env, |
| FindClassOrDie(env, "android/text/StaticLayout$LineBreaks")); |
| |
| gLineBreaks_fieldID.breaks = GetFieldIDOrDie(env, gLineBreaks_class, "breaks", "[I"); |
| gLineBreaks_fieldID.widths = GetFieldIDOrDie(env, gLineBreaks_class, "widths", "[F"); |
| gLineBreaks_fieldID.flags = GetFieldIDOrDie(env, gLineBreaks_class, "flags", "[Z"); |
| |
| return RegisterMethodsOrDie(env, "android/text/StaticLayout", gMethods, NELEM(gMethods)); |
| } |
| |
| } |