Strechability of non-justified lines: refinements.

10 files changed, 93 insertions, 52 deletions

diff --git a/ChangeLog b/ChangeLog
index 9eab3563..defa0e3f 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -20,7 +20,8 @@ dillo-3.0.4 [not released yet]
    correction.
  - Fixed (possibly security) problem of FltkImgBuf caused by integer overflow
    (BUG#1129).
- - Some linebreaking fixes.
+ - Some linebreaking fixes, and optimization for non-justified text, including
+   new preference stretchability_factor.
  - Added white_bg_replacement preference.
    Patches: Sebastian Geerken
 +- Fix a set of bugs reported by Oulu Univ. Secure Programming Group
diff --git a/dillorc b/dillorc
index ab7d7d9a..16207711 100644
--- a/dillorc
+++ b/dillorc
@@ -116,6 +116,12 @@
 # Notice that there is no "penalty_em_dash_left_2", since breaking
 # left of an em-dash makes the line *begin*, not *end* with a dash.
 
+# This factor is multiplied with the line height to get the
+# stretchability of a non-justified line. The larger this factor (and
+# thus, the stretchability), the less likely the words are hyphenated;
+# so you can use this value to control hyphenation of non-justified
+# text.
+#stretchability_factor=1
 
 #-------------------------------------------------------------------------
 #                            PARSING SECTION
diff --git a/doc/dw-line-breaking.doc b/doc/dw-line-breaking.doc
index 54d03d19..e9e3b4ea 100644
--- a/doc/dw-line-breaking.doc
+++ b/doc/dw-line-breaking.doc
@@ -151,9 +151,12 @@ So we need the following values:
 - \f$w_i\f$ (the width of the word \f$i\f$ itself);
 - \f$s_i\f$ (the width of the space following the word \f$i\f$);
 - the stretchability \f$y_i\f$, a value denoting how much the space
-  after word\f$i\f$ can be stretched (typically \f${1\over 2} s_i\f$);
+  after word\f$i\f$ can be stretched (typically \f${1\over 2} s_i\f$
+  for justified text; otherwise 0, since the spaces are not
+  stretched);
 - the shrinkability \f$y_i\f$, a value denoting how much the space
-  after word\f$i\f$ can be shrunken (typically \f${1\over 3} s_i\f$);
+  after word\f$i\f$ can be shrunken (typically \f${1\over 3} s_i\f$
+  for justified text; otherwise 0, since the spaces are not shrinked);
 - the penalty \f$p_i\f$, if the line is broken after word \f$i\f$;
 - a width \f$h_i\f$, which is added, when the line is broken after
   word \f$i\f$.
@@ -171,13 +174,16 @@ We define:
 
 \f[W_a^b = \sum_{i=a}^{b} w_i + \sum_{i=a}^{b-1} s_i + h_b\f]
 
-\f[Y_a^b = \sum_{i=a}^{b-1} y_i\f]
+\f[Y_a^b = {Y_0}_a^b + \sum_{i=a}^{b-1} y_i\f]
 
-\f[Z_a^b = \sum_{i=a}^{b-1} z_i\f]
+\f[Z_a^b = {Z_0}_a^b + \sum_{i=a}^{b-1} z_i\f]
 
 
-\f$W_a^b\f$ is the total width, \f$Y_a^b\f$ the total stretchability, and
-\f$Z_a^b\f$ the total shrinkability.
+\f$W_a^b\f$ is the total width, \f$Y_a^b\f$ the total stretchability,
+and \f$Z_a^b\f$ the total shrinkability. \f${Y_0}_a^b\f$ and
+\f${Z_0}_a^b\f$ are the stretchability and shrinkability defined per
+line, and applied at the borders; they are 0 for justified text, but
+\f${Y_0}_a^b\f$ has a positive value otherwise, see below for details.
 
 Furthermore the *adjustment ratio* \f$r_a^b\f$:
 
@@ -217,6 +223,33 @@ integer arithmetic is used for performance, which make the actual
 code more complicated. See dw::Textblock::BadnessAndPenalty for
 details.)
 
+Ragged Borders
+--------------
+
+For other than justified text (left-, right-aligned and centered), the
+spaces between the words are not shrinked or stretched (so \f$y_i\f$
+and \f$z_i\f$ are 0), but additional space is added to the left or
+right border or to both. For this reason, an additional stretchability
+\f${Y_0}_a^b\f$ is added (see definition above). Since this space at
+the border is 0 in an ideal case (\f$W_a^b = l\f$), it cannot be
+shrunken, so \f${Z_0}_a^b\f$ is 0.
+
+This is not equivalent to the calculation of the total stretchability
+as done for justified text, since in this case, the stretchability
+depends on the number of words: consider the typical case that all
+spaces and stretchabilities are equal (\f$y_a = y_{a + 1} = \ldots =
+y_b\f$). With \f$n\f$ words, the total strechability would be \f$n
+\cdot y_a\f$, so increase with an increasing number of words
+(\f$y_a\fb$ is constant). This is correct for justified text, but for
+other alignments, where only one space (or two, for centered text) is
+changed, this would mean that a line with many narrow words is more
+stretchable than a line with few wide words.
+
+It is obvious that left-aligned text can be handled in the same way as
+right-aligned text. [... Centered text? ...]
+
+[... Exact value of stretchability; relation to penalties ...]
+
 
 Hyphens
 =======
@@ -336,33 +369,6 @@ Low Priority
 be used? Currently, this is redundant to
 dw::Textblock::BadnessAndPenalty.
 
-**Other than justified text:** The calculation of badness is designed
-for justified text. For other alignments, it may be modified. The
-point is the definition of stretchability and for the line.
-
-Consider left-aligned text. Most importantly, not the spaces between
-the words, but the space on the right border is adjusted. If the
-actual line width (sum of words and normal spaces, \f$W_a^b\f$ above)
-equals the the ideal width (e. g. given by the browser window
-width, \f$l\f$ above), this space is zero, so it is not possible to
-shrink it further. For this reason, the shrinkability is now already
-set to 0.
-
-On the other hand, there should be a stretchability for the space on
-the right border. However, only the spaces between the words have a
-stretchability; later, the differences are summed up and used to fill
-the space on the right. This works, but is a bit imprecise, since the
-stretchability of the space on the right depends on the number of words
-in the line.
-
-(Likewise, if you modify the code to assign a positive value for the
-shrinkability for left-aligned text, the difference is summed up and
-used for the right border; since this difference is negative, the
-lines will, when spaces are shrunken, get too long!)
-
-Analogous considerations must be made for right-aligned and centered
-text. (For centered texts, there are two adjustable spaces.)
-
 Solved (Must Be Documented)
 ---------------------------
 
diff --git a/dw/textblock.cc b/dw/textblock.cc
index d7e1704e..1d486083 100644
--- a/dw/textblock.cc
+++ b/dw/textblock.cc
@@ -79,6 +79,8 @@ int Textblock::penalties[PENALTY_NUM][2] = {
    { 100, 800 }
 };
 
+int Textblock::stretchabilityFactor = 100;
+
 /**
  * The character which is used to draw a hyphen at the end of a line,
  * either caused by automatic hyphenation, or by soft hyphens.
@@ -115,6 +117,11 @@ void Textblock::setPenaltyEmDashRight2 (int penaltyRightEmDash2)
    penalties[PENALTY_EM_DASH_RIGHT][1] = penaltyRightEmDash2;
 }
 
+void Textblock::setStretchabilityFactor (int stretchabilityFactor)
+{
+   Textblock::stretchabilityFactor = stretchabilityFactor;
+}
+
 Textblock::Textblock (bool limitTextWidth)
 {
    registerName ("dw::Textblock", &CLASS_ID);
diff --git a/dw/textblock.hh b/dw/textblock.hh
index 48213e6c..7cf62f5c 100644
--- a/dw/textblock.hh
+++ b/dw/textblock.hh
@@ -341,8 +341,9 @@ protected:
                                   words: the value compared to the
                                   ideal width of the line, if the line
                                   would be broken after this word. */
-      int totalStretchability; // includes all *before* current word
-      int totalShrinkability;  // includes all *before* current word
+      int maxAscent, maxDescent;
+      int totalSpaceStretchability; // includes all *before* current word
+      int totalSpaceShrinkability;  // includes all *before* current word
       BadnessAndPenalty badnessAndPenalty; /* when line is broken after this
                                             * word */
 
@@ -422,6 +423,11 @@ protected:
     */
    static int penalties[PENALTY_NUM][2];
 
+   /**
+    * ...
+    */
+   static int stretchabilityFactor;
+
    bool limitTextWidth; /* from preferences */
 
    int redrawY;
@@ -575,8 +581,8 @@ protected:
 
    static int getSpaceShrinkability(struct Word *word);
    static int getSpaceStretchability(struct Word *word);
-   static int getLineShrinkability(struct Word *someWord);
-   static int getLineStretchability(struct Word *someWord);
+   static int getLineShrinkability(Word *lastWord);
+   static int getLineStretchability(Word *lastWord);
    int hyphenateWord (int wordIndex);
    void accumulateWordForLine (int lineIndex, int wordIndex);
    void accumulateWordData (int wordIndex);
@@ -619,6 +625,7 @@ public:
    static void setPenaltyEmDashLeft (int penaltyLeftEmDash);
    static void setPenaltyEmDashRight (int penaltyRightEmDash);
    static void setPenaltyEmDashRight2 (int penaltyRightEmDash2);
+   static void setStretchabilityFactor (int stretchabilityFactor);
 
    Textblock(bool limitTextWidth);
    ~Textblock();
diff --git a/dw/textblock_linebreaking.cc b/dw/textblock_linebreaking.cc
index 33195ab1..61e58cdb 100644
--- a/dw/textblock_linebreaking.cc
+++ b/dw/textblock_linebreaking.cc
@@ -91,7 +91,7 @@ void Textblock::BadnessAndPenalty::calcBadness (int totalWidth, int idealWidth,
             badness = ratio * ratio * ratio;
          }
       }
-   } else { // if (word->totalWidth > availWidth)
+   } else { // if (totalWidth > availWidth)
       if (totalShrinkability == 0)
          badnessState = TOO_TIGHT;
       else {
@@ -276,7 +276,7 @@ void Textblock::printWord (Word *word)
    printf (" [%d / %d + %d - %d => %d + %d - %d] => ",
            word->size.width, word->origSpace, getSpaceStretchability(word),
            getSpaceShrinkability(word), word->totalWidth,
-           word->totalStretchability, word->totalShrinkability);
+           word->totalSpaceStretchability, word->totalSpaceShrinkability);
    word->badnessAndPenalty.print ();
 }
 
@@ -1036,23 +1036,31 @@ void Textblock::accumulateWordData (int wordIndex)
    if (wordIndex == firstWordOfLine) {
       // first word of the (not neccessarily yet existing) line
       word->totalWidth = word->size.width + word->hyphenWidth;
-      word->totalStretchability = getLineStretchability (word);
-      word->totalShrinkability = getLineShrinkability (word);
+      word->maxAscent = word->size.ascent;
+      word->maxDescent = word->size.descent;
+      word->totalSpaceStretchability = 0;
+      word->totalSpaceShrinkability = 0;
    } else {
       Word *prevWord = words->getRef (wordIndex - 1);
 
       word->totalWidth = prevWord->totalWidth
          + prevWord->origSpace - prevWord->hyphenWidth
          + word->size.width + word->hyphenWidth;
-      word->totalStretchability =
-         prevWord->totalStretchability + getSpaceStretchability(prevWord);
-      word->totalShrinkability =
-         prevWord->totalShrinkability + getSpaceShrinkability(prevWord);
+      word->maxAscent = misc::max (prevWord->size.ascent, word->size.ascent);
+      word->maxDescent = misc::max (prevWord->size.descent, word->size.descent);
+      word->totalSpaceStretchability =
+         prevWord->totalSpaceStretchability + getSpaceStretchability(prevWord);
+      word->totalSpaceShrinkability =
+         prevWord->totalSpaceShrinkability + getSpaceShrinkability(prevWord);
    }
 
+   int totalStretchability =
+      word->totalSpaceStretchability + getLineStretchability (word);
+   int totalShrinkability =
+      word->totalSpaceShrinkability + getLineShrinkability (word);
    word->badnessAndPenalty.calcBadness (word->totalWidth, availWidth,
-                                        word->totalStretchability,
-                                        word->totalShrinkability);
+                                        totalStretchability,
+                                        totalShrinkability);
 
    //printf ("      => ");
    //printWord (word);
@@ -1281,17 +1289,18 @@ int Textblock::getSpaceStretchability(struct Word *word)
    // Alternative: return word->origSpace / 2;
 }
 
-int Textblock::getLineShrinkability(struct Word *someWord)
+int Textblock::getLineShrinkability(Word *lastWord)
 {
    return 0;
 }
 
-int Textblock::getLineStretchability(struct Word *someWord)
+int Textblock::getLineStretchability(Word *lastWord)
 {
-   if (someWord->spaceStyle->textAlign == core::style::TEXT_ALIGN_JUSTIFY)
+   if (lastWord->spaceStyle->textAlign == core::style::TEXT_ALIGN_JUSTIFY)
       return 0;
    else
-      return 3 * someWord->origSpace;
+      return stretchabilityFactor * (lastWord->maxAscent
+                                     + lastWord->maxDescent) / 100;
 
    // Alternative: return 0;
 }
diff --git a/src/dillo.cc b/src/dillo.cc
index 6a7747ed..e519d4df 100644
--- a/src/dillo.cc
+++ b/src/dillo.cc
@@ -472,6 +472,7 @@ int main(int argc, char **argv)
    dw::Textblock::setPenaltyEmDashLeft (prefs.penalty_em_dash_left);
    dw::Textblock::setPenaltyEmDashRight (prefs.penalty_em_dash_right);
    dw::Textblock::setPenaltyEmDashRight2 (prefs.penalty_em_dash_right_2);
+   dw::Textblock::setStretchabilityFactor (prefs.stretchability_factor);
 
    /* command line options override preferences */
    if (options_got & DILLO_CLI_FULLWINDOW)
diff --git a/src/prefs.c b/src/prefs.c
index 4b45b51e..a192c324 100644
--- a/src/prefs.c
+++ b/src/prefs.c
@@ -118,6 +118,7 @@ void a_Prefs_init(void)
    prefs.penalty_em_dash_left = 800;
    prefs.penalty_em_dash_right = 100;
    prefs.penalty_em_dash_right_2 = 800;
+   prefs.stretchability_factor = 100;
 }
 
 /*
diff --git a/src/prefs.h b/src/prefs.h
index bdb3aaee..de3e0342 100644
--- a/src/prefs.h
+++ b/src/prefs.h
@@ -107,6 +107,7 @@ typedef struct {
    bool_t middle_click_drags_page;
    int penalty_hyphen, penalty_hyphen_2;
    int penalty_em_dash_left, penalty_em_dash_right, penalty_em_dash_right_2;
+   int stretchability_factor;
 } DilloPrefs;
 
 /* Global Data */
diff --git a/src/prefsparser.cc b/src/prefsparser.cc
index f6522d45..86f8580c 100644
--- a/src/prefsparser.cc
+++ b/src/prefsparser.cc
@@ -130,6 +130,8 @@ int PrefsParser::parseOption(char *name, char *value)
       { "penalty_em_dash_right", &prefs.penalty_em_dash_right,
         PREFS_FRACTION_100 },
       { "penalty_em_dash_right_2", &prefs.penalty_em_dash_right_2,
+        PREFS_FRACTION_100 },
+      { "stretchability_factor", &prefs.stretchability_factor,
         PREFS_FRACTION_100 }
    };