Speedup overlong text detection

Detecting very long window titles is done via FbTk::TextUtils::doAlignment().
Instead of removing one char from the title at a time to see if it fits into a
given 'max_width', we now use a binary-search like approach to get faster to
the right value. This massively improves the speed for windows with
(arbitrary) long window titles (see bug #1090, javascript

    document.title = new Array(4999).join(".");

leads to massive waiting for fluxbox to detect that this window has a very
long title).

In addition to that Xft returns 'wrapped' shorts ('integer overflows') for
long texts: XGlpyhInfo.xOff is declared as signed short, it's able to hold
~32k pixels. A monospace font with font-size 10 produces an integer
overflow after 3276 chars / glyphs, thus rendering the check

    if (text_width < max_width) { /* ... */ }

pointless and leading rendering the whole title. By calculating some kind of
upper limit for a pseudo-wide glyph ("WW") and strictly cutting off the input
string at that limit prevents this issue.

3 files changed, 70 insertions, 26 deletions

diff --git a/src/FbTk/TextUtils.cc b/src/FbTk/TextUtils.cc
index fa2ea0c..ca141d1 100644
--- a/src/FbTk/TextUtils.cc
+++ b/src/FbTk/TextUtils.cc
@@ -24,7 +24,50 @@
 #include "Font.hh"
 #include "Theme.hh"
 
-#include <strings.h>
+#include <cstring>
+
+namespace {
+
+// calcs longest substring of 'text', fitting into 'max_width'
+// 'text_len' is an in-out parameter
+// 'text_width' is out parameter
+void maxTextLength(int max_width, const FbTk::Font& font, const char* const text,
+        unsigned int& text_len, int& text_width) {
+
+    text_width = font.textWidth(text, text_len);
+
+    // rendered text exceeds max_width. calculate 'len' to cut off 'text'.
+    if (text_width > max_width) {
+
+        // pick some good starting points for the search
+        //
+        //  [...........|.R ]
+        //  [WWWWWWWWWWL|   ]
+        //
+        //          max_width
+
+        int right = max_width / (font.textWidth(".", 1) + 1);
+        int left = max_width / (font.textWidth("WW", 2) + 1);
+        int middle;
+
+        // binary search for longest substring fitting into 'max_width' pixels
+        for ( ; left < (right - 1); ) {
+
+            middle = left + ((right - left) / 2);
+            text_width = font.textWidth(text, middle);
+
+            if (text_width < max_width) {
+                left = middle;
+            } else {
+                right = middle;
+            }
+        }
+
+        text_len = left;
+    }
+}
+
+}
 
 namespace FbTk {
 
@@ -35,31 +78,19 @@ int doAlignment(int max_width, int bevel, FbTk::Justify justify,
     if (text == 0 || textlen == 0)
         return 0;
 
-    int l = font.textWidth(text, textlen) + bevel;
-    unsigned int dlen = textlen;
-    int dx = bevel;
-    if (l > max_width) {
-        for (; dlen > 0; dlen--) {
-            l = font.textWidth(text, dlen) + bevel;
-            if (l<=max_width)
-                break;
-        }
-    }
+    int text_width;
+
+    maxTextLength(max_width - bevel, font, text, textlen, text_width);
+
+    newlen = textlen;
 
-    newlen = dlen;
-
-    switch (justify) {
-    case FbTk::RIGHT:
-        dx = max_width - l - bevel;
-    break;
-    case FbTk::CENTER:
-        dx = (max_width - l)/2;
-    break;
-    case FbTk::LEFT:
-    break;
+    if (justify == FbTk::RIGHT) {
+        return max_width - text_width;
+    } else if (justify == FbTk::CENTER) {
+        return (max_width - text_width + bevel)/2;
     }
 
-    return dx;
+    return bevel;
 }
 
 
diff --git a/src/FbTk/XftFontImp.cc b/src/FbTk/XftFontImp.cc
index 15c8212..9e57349 100644
--- a/src/FbTk/XftFontImp.cc
+++ b/src/FbTk/XftFontImp.cc
@@ -23,7 +23,9 @@
 #include "App.hh"
 #include "FbDrawable.hh"
 
-#include <math.h>
+#include <cmath>
+#include <cstdio>
+#include <algorithm>
 
 #ifdef HAVE_CONFIG_H
 #include "config.h"
@@ -32,7 +34,7 @@
 namespace FbTk {
 
 XftFontImp::XftFontImp(const char *name, bool utf8):
-    m_utf8mode(utf8), m_name("") {
+    m_utf8mode(utf8), m_name(""), m_maxlength(0x8000) {
 
     for (int r = ROT0; r <= ROT270; r++) {
         m_xftfonts[r] = 0;
@@ -74,6 +76,15 @@ bool XftFontImp::load(const std::string &name) {
     m_xftfonts_loaded[ROT0] = true;
     m_name = name;
 
+    // XGlyphInfo (used by XftFontImp::textWidth() / XftTextExtents8() etc)
+    // holds only type 'short' or 'unsigned short'. any text bigger than that
+    // yields either some negative or some 'wrapped' values ('integer
+    // overflow'). to prevent something like this we detect the maximium
+    // number of glyphs by calculating the amount of 'WW' (pretending a 'wide'
+    // glyph) fitting into 32k pixels 
+    unsigned int tw = textWidth("WW", 2);
+    m_maxlength = 0x8000 / tw;
+
     return true;
 }
 
@@ -160,6 +171,8 @@ unsigned int XftFontImp::textWidth(const char* text, unsigned int len) const {
 
     XftFont *font = m_xftfonts[ROT0];
 
+    len = std::min(len, m_maxlength);
+
 
 #ifdef HAVE_XFT_UTF8_STRING
     if (m_utf8mode) {
diff --git a/src/FbTk/XftFontImp.hh b/src/FbTk/XftFontImp.hh
index fd24762..bd02722 100644
--- a/src/FbTk/XftFontImp.hh
+++ b/src/FbTk/XftFontImp.hh
@@ -51,7 +51,7 @@ private:
     bool m_utf8mode;
 
     std::string m_name;
-    int m_angle;
+    unsigned int m_maxlength;
 };
 
 } // end namespace FbTk