Index: sub.c
===================================================================
RCS file: /cvsroot/mplayer/main/libvo/sub.c,v
retrieving revision 1.69
diff -u -b -B -r1.69 sub.c
--- sub.c	19 Jan 2003 20:13:49 -0000	1.69
+++ sub.c	25 Mar 2003 21:01:08 -0000
@@ -305,6 +305,136 @@
 
 // vo_draw_text_sub(int dxs,int dys,void (*draw_alpha)(int x0,int y0, int w,int h, unsigned char* src, unsigned char *srca, int stride))
 
+typedef struct _scache 
+{
+    int known;
+    int minw;
+    int maxw;
+    int lcnt;
+} scache;
+
+static int splitpos[1000];
+static int splitcnt;
+static scache cache[1000];
+
+// off ... offset of the first character
+// soff ... number of the previous whitespace (-1 for none)
+static void split(int *dest, char *src, int off, int soff, int *minw, int *maxw, int *lcnt, int dxs) 
+{
+    unsigned char *t;
+    int c,i,j,prevc;
+    int len;
+    int xsize_tot;
+    int wanted_linecnt;
+    int spaces[1000], xsizes[1000], spacecnt;
+
+    t = src;
+
+    // first level, clear cache
+    if (off == 0) {
+	for (j=0;j<100;j++){
+	    cache[j].known = 0;
+	}
+    }
+
+    spacecnt = 0;
+    xsize_tot=-vo_font->charspace;
+    prevc = -1;
+
+    len=strlen(t)-1;
+
+    // locate spaces
+    for (j=0;j<=len;j++){
+	if ((c=t[j])>=0x80){
+	    if (sub_utf8){
+		if ((c & 0xe0) == 0xc0)    /* 2 bytes U+00080..U+0007FF*/
+		    c = (c & 0x1f)<<6 | (t[++j] & 0x3f);
+		else if((c & 0xf0) == 0xe0){ /* 3 bytes U+00800..U+00FFFF*/
+		    c = (((c & 0x0f)<<6) | (t[++j] & 0x3f))<<6;
+		    c |= (t[++j] & 0x3f);
+		}
+	    } else if (sub_unicode) 
+		c = (c<<8) + t[++j]; 
+	}
+	if (!c) c++; // avoid UCS 0
+
+	if (xsize_tot < dxs*sub_width_p/100) {
+	    if (c == ' ' && prevc != ' ') {
+		spaces[spacecnt] = j;
+		xsizes[spacecnt] = xsize_tot;
+		spacecnt++;
+		if (spacecnt >= 1000)
+		{
+		    // too much spaces
+		    dest[0] = -1;
+		    return;
+		}
+		
+	    }
+	}
+
+	render_one_glyph(vo_font, c);
+	xsize_tot += vo_font->width[c]+vo_font->charspace+kerning(vo_font,prevc,c);
+	prevc = c;
+    }
+
+    // maximum acceptable line count
+    wanted_linecnt = xsize_tot/(dxs*sub_width_p/100)+2;
+    if (xsize_tot > dxs*sub_width_p/100 && spacecnt) {
+	int minw2 = 65535, maxw2 = 0, minpenalty = 65535, minsplit = spacecnt-1, xsize = 0, xlcnt = 1;
+	// try splitting at various places
+	for (i = spacecnt-1; i >= 0; i--) {
+	    int tmpminw2, tmpmaxw2, tmpxsize, tmpoff;
+
+	    int min_nextlines = (xsize_tot - xsizes[i])/(dxs*sub_width_p/100)+1;
+	    // following stuff is certainly too long, don't try anymore
+	    if (min_nextlines+1 > wanted_linecnt) break;
+
+	    t = src + spaces[i] + 1;
+	    tmpxsize = xsizes[i];
+	    tmpoff = soff + i + 1;
+	    
+	    // compute dimensions of the following lines
+	    if (cache[tmpoff].known) {
+		tmpminw2 = cache[tmpoff].minw;
+		tmpmaxw2 = cache[tmpoff].maxw;
+		xlcnt = cache[tmpoff].lcnt;
+	    } else {
+		split(dest+1, t, off + spaces[i] + 1, tmpoff, &tmpminw2, &tmpmaxw2, &xlcnt, dxs);
+		cache[tmpoff].known = 1;
+		cache[tmpoff].minw = tmpminw2;
+		cache[tmpoff].maxw = tmpmaxw2;
+		cache[tmpoff].lcnt = xlcnt;
+
+	    }
+	    
+	    // too long, try something else
+	    if (xlcnt+1 > wanted_linecnt) continue;
+
+	    // evaluate penalty
+	    if (abs(tmpminw2-xsizes[i])+abs(tmpmaxw2-xsizes[i]) < minpenalty) {
+		minsplit = i;
+		minpenalty = abs(tmpminw2-xsizes[i])+abs(tmpmaxw2-xsizes[i]);
+		minw2 = tmpminw2;
+		maxw2 = tmpmaxw2;
+		xsize = tmpxsize;
+	    }
+	}
+	dest[0] = off + spaces[minsplit];
+	t = src + spaces[minsplit] + 1;
+	split(dest+1, t, off + spaces[minsplit] + 1, soff + i + 1, &minw2, &maxw2, &xlcnt, dxs);
+	if (minw) *minw = minw2 < xsize ? minw2 : xsize;
+	if (maxw) *maxw = maxw2 > xsize ? maxw2 : xsize;
+	if (lcnt) *lcnt = xlcnt+1;
+    } else {
+	if (minw) *minw = xsize_tot;
+	if (maxw) *maxw = xsize_tot;
+	if (lcnt) *lcnt = 1;
+	dest[0] = -1;
+    }
+}
+
+
 inline static void vo_update_text_sub(mp_osd_obj_t* obj,int dxs,int dys){
    unsigned char *t;
    int c,i,j,l,x,y,font,prevc;
@@ -314,6 +444,7 @@
    int xsize,lastxsize;
    int xmin=dxs,xmax=0;
    int h,lasth;
+   int splitcnt;
    
    obj->flags|=OSDFLAG_CHANGED|OSDFLAG_VISIBLE;
 
@@ -337,12 +468,13 @@
 	  t=vo_sub->text[i++];	  
 	  len=strlen(t)-1;
 	  
-//	  printf("sub(%d) '%s'\n",len,t);
-//	  if(len<0) memy -=h; // according to max of vo_font->pic_a[font]->h 
-//	  else
+	  split(splitpos, t, 0, -1, NULL, NULL, NULL, dxs);
 
+	  xsize=-vo_font->charspace;
 	  prevc = -1;
 
+	  splitcnt = 0;
+
 	  for (j=0;j<=len;j++){
 	      if ((c=t[j])>=0x80){
 		 if (sub_utf8){
@@ -385,18 +517,7 @@
 	      }
 	      obj->params.subtitle.utbl[k++]=c;
 	      xsize+=vo_font->width[c]+vo_font->charspace+kerning(vo_font,prevc,c);
-	      if (dxs*sub_width_p/100<xsize){
-		  prevc = -1;
-		 if (lastStripPosition>0){
-		    j=lastStripPosition;
-		    xsize=lastxsize;
-		    k=lastk;
-		 } else {
-		    xsize -=vo_font->width[c]+vo_font->charspace+kerning(vo_font,prevc,c);; // go back
-		    k--; // cut line here
-		    while (t[j] && t[j]!=' ') j++; // jump to the nearest space
-		 }
-	      } else if (j<len) {
+	      if (j != splitpos[splitcnt] && j < len) {
 		  prevc = c;
 		  continue;
 	      }
@@ -411,7 +532,8 @@
 	      if(xmax<(dxs+xsize)/2) xmax=(dxs+xsize)/2;
 	      if (obj->params.subtitle.lines==MAX_UCSLINES||k>MAX_UCS){
 		 l=0; len=j; // end parsing
-	      } else if(l || j<len){ // not the last line or not the last char
+	      } else if (j == splitpos[splitcnt]){ // not the last line or not the last char
+		 splitcnt++;
 		 lastStripPosition=-1;
 		 xsize=-vo_font->charspace;
 		 lasth=h;