Merge with main repo.

10 files changed, 150 insertions, 65 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..ac4f61d6 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,53 @@ 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\f$ 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? ...]
+
+The default value for the stretchability is the line height without
+the space between the lines (more precisely: the maximum of all word
+heights). The exact value not so important when comparing different
+possible values for the badness \f$\beta_a^b\f$, when \f${Y_0}_a^b\f$
+is nearly constant for different \f$b\f$ (which is the case for the
+actual value), but it is important for the comparison with penalties,
+which are constant. To be considered is also that for non-justified
+text, hyphenation is differently (less) desirable; this effect can be
+achieved by enlarging the stretchability, which will lead to a smaller
+badness, and so make hyphenation less likely. The user can configure
+the stretchability by changing the preference value
+*stretchability_factor* (default: 1.0).
+
+(Comparison to T<sub>E</sub>X: Knuth and Plass describe a method for
+ragged borders, which is effectively the same as described here (Knuth
+1999, pp.&nbsp;93--94). The value for the stretchability of the line
+is slightly less, 1&nsbp;em (ibid., see also p.&nsbp;72 for the
+definition of the units). However, this article suggests a value for
+the hyphenation penalty, which is ten times larger than the value for
+justified text; this would suggest a larger value for
+*stretchability_factor*.)
+
 
 Hyphens
 =======
@@ -336,33 +389,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.&nbsp;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 7950ba96..a79462e1 100644
--- a/dw/textblock.cc
+++ b/dw/textblock.cc
@@ -176,6 +176,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.
@@ -212,6 +214,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 0f5ae38e..b85937ba 100644
--- a/dw/textblock.hh
+++ b/dw/textblock.hh
@@ -379,8 +379,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 */
 
@@ -465,6 +466,11 @@ protected:
     */
    static int penalties[PENALTY_NUM][2];
 
+   /**
+    * ...
+    */
+   static int stretchabilityFactor;
+
    bool limitTextWidth; /* from preferences */
 
    int redrawY;
@@ -621,8 +627,10 @@ protected:
    void handleWordExtremes (int wordIndex);
    void correctLastWordExtremes ();
 
-   static int getShrinkability(struct Word *word);
-   static int getStretchability(struct Word *word);
+   static int getSpaceShrinkability(struct Word *word);
+   static int getSpaceStretchability(struct Word *word);
+   static int getLineShrinkability(Word *lastWord);
+   static int getLineStretchability(Word *lastWord);
    int hyphenateWord (int wordIndex);
    void accumulateWordForLine (int lineIndex, int wordIndex);
    void accumulateWordData (int wordIndex);
@@ -665,6 +673,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 58b8c494..b1a2cbd9 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 {
@@ -274,9 +274,9 @@ void Textblock::printWord (Word *word)
    printWordWithFlags (word);
 
    printf (" [%d / %d + %d - %d => %d + %d - %d] => ",
-           word->size.width, word->origSpace, getStretchability(word),
-           getShrinkability(word), word->totalWidth, word->totalStretchability,
-           word->totalShrinkability);
+           word->size.width, word->origSpace, getSpaceStretchability(word),
+           getSpaceShrinkability(word), word->totalWidth,
+           word->totalSpaceStretchability, word->totalSpaceShrinkability);
    word->badnessAndPenalty.print ();
 }
 
@@ -291,18 +291,19 @@ void Textblock::justifyLine (Line *line, int diff)
     * values. */
 
    if (diff > 0) {
-      int stretchabilitySum = 0;
+      int spaceStretchabilitySum = 0;
       for (int i = line->firstWord; i < line->lastWord; i++)
-         stretchabilitySum += getStretchability(words->getRef(i));
+         spaceStretchabilitySum += getSpaceStretchability(words->getRef(i));
 
-      if (stretchabilitySum > 0) {
-         int stretchabilityCum = 0;
+      if (spaceStretchabilitySum > 0) {
+         int spaceStretchabilityCum = 0;
          int spaceDiffCum = 0;
          for (int i = line->firstWord; i < line->lastWord; i++) {
             Word *word = words->getRef (i);
-            stretchabilityCum += getStretchability(word);
+            spaceStretchabilityCum += getSpaceStretchability(word);
             int spaceDiff =
-               stretchabilityCum * diff / stretchabilitySum - spaceDiffCum;
+               spaceStretchabilityCum * diff / spaceStretchabilitySum
+               - spaceDiffCum;
             spaceDiffCum += spaceDiff;
 
             PRINTF ("         %d (of %d): diff = %d\n", i, words->size (),
@@ -312,18 +313,19 @@ void Textblock::justifyLine (Line *line, int diff)
          }
       }
    } else if (diff < 0) {
-      int shrinkabilitySum = 0;
+      int spaceShrinkabilitySum = 0;
       for (int i = line->firstWord; i < line->lastWord; i++)
-         shrinkabilitySum += getShrinkability(words->getRef(i));
+         spaceShrinkabilitySum += getSpaceShrinkability(words->getRef(i));
 
-      if (shrinkabilitySum > 0) {
-         int shrinkabilityCum = 0;
+      if (spaceShrinkabilitySum > 0) {
+         int spaceShrinkabilityCum = 0;
          int spaceDiffCum = 0;
          for (int i = line->firstWord; i < line->lastWord; i++) {
             Word *word = words->getRef (i);
-            shrinkabilityCum += getShrinkability(word);
+            spaceShrinkabilityCum += getSpaceShrinkability(word);
             int spaceDiff =
-               shrinkabilityCum * diff / shrinkabilitySum - spaceDiffCum;
+               spaceShrinkabilityCum * diff / spaceShrinkabilitySum
+               - spaceDiffCum;
             spaceDiffCum += spaceDiff;
 
             word->effSpace = word->origSpace + spaceDiff;
@@ -1045,23 +1047,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 = 0;
-      word->totalShrinkability = 0;
+      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 + getStretchability(prevWord);
-      word->totalShrinkability =
-         prevWord->totalShrinkability + getShrinkability(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);
@@ -1272,7 +1282,7 @@ void Textblock::removeTemporaryLines ()
    lines->setSize (nonTemporaryLines);
 }
 
-int Textblock::getShrinkability(struct Word *word)
+int Textblock::getSpaceShrinkability(struct Word *word)
 {
    if (word->spaceStyle->textAlign == core::style::TEXT_ALIGN_JUSTIFY)
       return word->origSpace / 3;
@@ -1280,9 +1290,30 @@ int Textblock::getShrinkability(struct Word *word)
       return 0;
 }
 
-int Textblock::getStretchability(struct Word *word)
+int Textblock::getSpaceStretchability(struct Word *word)
 {
-   return word->origSpace / 2;
+   if (word->spaceStyle->textAlign == core::style::TEXT_ALIGN_JUSTIFY)
+      return word->origSpace / 2;
+   else
+      return 0;
+
+   // Alternative: return word->origSpace / 2;
+}
+
+int Textblock::getLineShrinkability(Word *lastWord)
+{
+   return 0;
+}
+
+int Textblock::getLineStretchability(Word *lastWord)
+{
+   if (lastWord->spaceStyle->textAlign == core::style::TEXT_ALIGN_JUSTIFY)
+      return 0;
+   else
+      return stretchabilityFactor * (lastWord->maxAscent
+                                     + lastWord->maxDescent) / 100;
+
+   // Alternative: return 0;
 }
 
 } // namespace dw
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 }
    };