fribidi: update for version 1.0
[vlc.git] / modules / text_renderer / freetype / text_layout.c
1 /*****************************************************************************
2  * text_layout.c : Text shaping and layout
3  *****************************************************************************
4  * Copyright (C) 2015 VLC authors and VideoLAN
5  * $Id$
6  *
7  * Authors: Salah-Eddin Shaban <salshaaban@gmail.com>
8  *          Laurent Aimar <fenrir@videolan.org>
9  *          Sigmund Augdal Helberg <dnumgis@videolan.org>
10  *          Gildas Bazin <gbazin@videolan.org>
11  *          Jean-Baptiste Kempf <jb@videolan.org>
12  *          Naohiro Koriyama <nkoriyama@gmail.com>
13  *          David Fuhrmann <dfuhrmann@videolan.org>
14  *          Erwan Tulou <erwan10@videolan.org>
15  *          Devin Heitmueller <dheitmueller@kernellabs.com>
16  *
17  * This program is free software; you can redistribute it and/or modify it
18  * under the terms of the GNU Lesser General Public License as published by
19  * the Free Software Foundation; either version 2.1 of the License, or
20  * (at your option) any later version.
21  *
22  * This program is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
25  * GNU Lesser General Public License for more details.
26  *
27  * You should have received a copy of the GNU Lesser General Public License
28  * along with this program; if not, write to the Free Software Foundation, Inc.,
29  * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
30  *****************************************************************************/
31
32 /** \ingroup freetype
33  * @{
34  * \file
35  * Text shaping and layout
36  */
37
38 #ifdef HAVE_CONFIG_H
39 # include "config.h"
40 #endif
41
42 #include <vlc_common.h>
43 #include <vlc_filter.h>
44 #include <vlc_text_style.h>
45
46 /* Freetype */
47 #include <ft2build.h>
48 #include FT_FREETYPE_H
49 #include FT_GLYPH_H
50 #include FT_STROKER_H
51 #include FT_SYNTHESIS_H
52
53 /* RTL */
54 #if defined(HAVE_FRIBIDI)
55 # define FRIBIDI_NO_DEPRECATED 1
56 # include <fribidi.h>
57 #endif
58
59 /* Complex Scripts */
60 #if defined(HAVE_HARFBUZZ)
61 # include <hb.h>
62 # include <hb-ft.h>
63 #endif
64
65 #include "freetype.h"
66 #include "text_layout.h"
67 #include "platform_fonts.h"
68
69 /* Win32 */
70 #ifdef _WIN32
71 # undef HAVE_FONTCONFIG
72 # define HAVE_FONT_FALLBACK
73 #endif
74
75 /* FontConfig */
76 #ifdef HAVE_FONTCONFIG
77 # define HAVE_FONT_FALLBACK
78 #endif
79
80 /* Android */
81 #ifdef __ANDROID__
82 # define HAVE_FONT_FALLBACK
83 #endif
84
85 /* Darwin */
86 #ifdef __APPLE__
87 # define HAVE_FONT_FALLBACK
88 #endif
89
90 #ifndef HAVE_FONT_FALLBACK
91 # warning YOU ARE MISSING FONTS FALLBACK. TEXT WILL BE INCORRECT
92 #endif
93
94 /**
95  * Within a paragraph, run_desc_t represents a run of characters
96  * having the same font face, size, and style, Unicode script
97  * and text direction
98  */
99 typedef struct run_desc_t
100 {
101     int                         i_start_offset;
102     int                         i_end_offset;
103     FT_Face                     p_face;
104     const text_style_t         *p_style;
105
106 #ifdef HAVE_HARFBUZZ
107     hb_script_t                 script;
108     hb_direction_t              direction;
109     hb_font_t                  *p_hb_font;
110     hb_buffer_t                *p_buffer;
111     hb_glyph_info_t            *p_glyph_infos;
112     hb_glyph_position_t        *p_glyph_positions;
113     unsigned int                i_glyph_count;
114 #endif
115
116 } run_desc_t;
117
118 /**
119  * Glyph bitmaps. Advance and offset are 26.6 values
120  */
121 typedef struct glyph_bitmaps_t
122 {
123     FT_Glyph p_glyph;
124     FT_Glyph p_outline;
125     FT_Glyph p_shadow;
126     FT_BBox  glyph_bbox;
127     FT_BBox  outline_bbox;
128     FT_BBox  shadow_bbox;
129     int      i_x_offset;
130     int      i_y_offset;
131     int      i_x_advance;
132     int      i_y_advance;
133 } glyph_bitmaps_t;
134
135 typedef struct paragraph_t
136 {
137     uni_char_t          *p_code_points;    /**< Unicode code points */
138     int                 *pi_glyph_indices; /**< Glyph index values within the run's font face */
139     text_style_t       **pp_styles;
140     ruby_block_t      **pp_ruby;
141     FT_Face             *pp_faces;         /**< Used to determine run boundaries when performing font fallback */
142     int                 *pi_run_ids;       /**< The run to which each glyph belongs */
143     glyph_bitmaps_t     *p_glyph_bitmaps;
144     uint8_t             *pi_karaoke_bar;
145     int                  i_size;
146     run_desc_t          *p_runs;
147     int                  i_runs_count;
148     int                  i_runs_size;
149
150 #ifdef HAVE_HARFBUZZ
151     hb_script_t         *p_scripts;
152 #endif
153
154 #ifdef HAVE_FRIBIDI
155     FriBidiCharType     *p_types;
156 #if FRIBIDI_MAJOR_VERSION >= 1
157     FriBidiBracketType  *p_btypes;
158 #endif
159     FriBidiLevel        *p_levels;
160     FriBidiStrIndex     *pi_reordered_indices;
161     FriBidiParType       paragraph_type;
162 #endif
163
164 } paragraph_t;
165
166 static void FreeLine( line_desc_t *p_line )
167 {
168     for( int i = 0; i < p_line->i_character_count; i++ )
169     {
170         line_character_t *ch = &p_line->p_character[i];
171         FT_Done_Glyph( (FT_Glyph)ch->p_glyph );
172         if( ch->p_outline )
173             FT_Done_Glyph( (FT_Glyph)ch->p_outline );
174         if( ch->p_shadow )
175             FT_Done_Glyph( (FT_Glyph)ch->p_shadow );
176     }
177
178 //    if( p_line->p_ruby )
179 //        FreeLine( p_line->p_ruby );
180
181     free( p_line->p_character );
182     free( p_line );
183 }
184
185 void FreeLines( line_desc_t *p_lines )
186 {
187     for( line_desc_t *p_line = p_lines; p_line != NULL; )
188     {
189         line_desc_t *p_next = p_line->p_next;
190         FreeLine( p_line );
191         p_line = p_next;
192     }
193 }
194
195 line_desc_t *NewLine( int i_count )
196 {
197     line_desc_t *p_line = malloc( sizeof(*p_line) );
198
199     if( !p_line )
200         return NULL;
201
202     p_line->p_next = NULL;
203     p_line->i_width = 0;
204     p_line->i_base_line = 0;
205     p_line->i_character_count = 0;
206     p_line->i_first_visible_char_index = -1;
207     p_line->i_last_visible_char_index = -2;
208
209     BBoxInit( &p_line->bbox );
210
211     p_line->p_character = calloc( i_count, sizeof(*p_line->p_character) );
212     if( !p_line->p_character )
213     {
214         free( p_line );
215         return NULL;
216     }
217     return p_line;
218 }
219
220 static void ShiftGlyph( FT_BitmapGlyph g, int x, int y )
221 {
222     if( g )
223     {
224         g->left += x;
225         g->top += y;
226     }
227 }
228
229 static void ShiftChar( line_character_t *c, int x, int y )
230 {
231     ShiftGlyph( c->p_glyph, x, y );
232     ShiftGlyph( c->p_shadow, x, y );
233     ShiftGlyph( c->p_outline, x, y );
234     c->bbox.yMin += y;
235     c->bbox.yMax += y;
236     c->bbox.xMin += x;
237     c->bbox.xMax += x;
238 }
239
240 static void ShiftLine( line_desc_t *p_line, int x, int y )
241 {
242     for( int i=0; i<p_line->i_character_count; i++ )
243         ShiftChar( &p_line->p_character[i], x, y );
244     p_line->i_base_line += y;
245     p_line->bbox.yMin += y;
246     p_line->bbox.yMax += y;
247     p_line->bbox.xMin += x;
248     p_line->bbox.xMax += x;
249 }
250
251 static void MoveLineTo( line_desc_t *p_line, int x, int y )
252 {
253     ShiftLine( p_line, x - p_line->bbox.xMin,
254                        y - p_line->bbox.yMax );
255 }
256
257 static void IndentCharsFrom( line_desc_t *p_line, int i_start, int i_count, int w, int h )
258 {
259     for( int i=0; i<i_count; i++ )
260     {
261         line_character_t *p_ch = &p_line->p_character[i_start + i];
262         ShiftChar( p_ch, w, h );
263         BBoxEnlarge( &p_line->bbox, &p_ch->bbox );
264     }
265 }
266
267 static int RubyBaseAdvance( const line_desc_t *p_line, int i_start, int *pi_count )
268 {
269     int i_total = 0;
270     *pi_count = 0;
271     for( int i = i_start; i < p_line->i_character_count; i++ )
272     {
273         if( p_line->p_character[i].p_ruby != p_line->p_character[i_start].p_ruby )
274             break;
275         (*pi_count)++;
276         i_total += (p_line->p_character[i].bbox.xMax - p_line->p_character[i].bbox.xMin);
277     }
278     return i_total;
279 }
280
281 static void FixGlyph( FT_Glyph glyph, FT_BBox *p_bbox,
282                       FT_Pos i_x_advance, FT_Pos i_y_advance,
283                       const FT_Vector *p_pen )
284 {
285     FT_BitmapGlyph glyph_bmp = (FT_BitmapGlyph)glyph;
286     if( p_bbox->xMin >= p_bbox->xMax )
287     {
288         p_bbox->xMin = FT_CEIL(p_pen->x);
289         p_bbox->xMax = FT_CEIL(p_pen->x + i_x_advance);
290         glyph_bmp->left = p_bbox->xMin;
291     }
292     if( p_bbox->yMin >= p_bbox->yMax )
293     {
294         p_bbox->yMax = FT_CEIL(p_pen->y);
295         p_bbox->yMin = FT_CEIL(p_pen->y + i_y_advance);
296         glyph_bmp->top  = p_bbox->yMax;
297     }
298 }
299
300 static paragraph_t *NewParagraph( filter_t *p_filter,
301                                   int i_size,
302                                   const uni_char_t *p_code_points,
303                                   text_style_t **pp_styles,
304                                   ruby_block_t **pp_ruby,
305                                   uint32_t *pi_k_dates,
306                                   int i_runs_size )
307 {
308     paragraph_t *p_paragraph = calloc( 1, sizeof( paragraph_t ) );
309     if( !p_paragraph )
310         return 0;
311
312     p_paragraph->i_size = i_size;
313     p_paragraph->p_code_points =
314             vlc_alloc( i_size, sizeof( *p_paragraph->p_code_points ) );
315     p_paragraph->pi_glyph_indices =
316             vlc_alloc( i_size, sizeof( *p_paragraph->pi_glyph_indices ) );
317     p_paragraph->pp_styles =
318             vlc_alloc( i_size, sizeof( *p_paragraph->pp_styles ) );
319     p_paragraph->pp_faces =
320             calloc( i_size, sizeof( *p_paragraph->pp_faces ) );
321     p_paragraph->pi_run_ids =
322             calloc( i_size, sizeof( *p_paragraph->pi_run_ids ) );
323     p_paragraph->p_glyph_bitmaps =
324             calloc( i_size, sizeof( *p_paragraph->p_glyph_bitmaps ) );
325     p_paragraph->pi_karaoke_bar =
326             calloc( i_size, sizeof( *p_paragraph->pi_karaoke_bar ) );
327     if( pp_ruby )
328         p_paragraph->pp_ruby = calloc( i_size, sizeof( *p_paragraph->pp_ruby ) );
329
330     p_paragraph->p_runs = calloc( i_runs_size, sizeof( run_desc_t ) );
331     p_paragraph->i_runs_size = i_runs_size;
332     p_paragraph->i_runs_count = 0;
333
334     if( !p_paragraph->p_code_points || !p_paragraph->pi_glyph_indices
335      || !p_paragraph->pp_styles || !p_paragraph->pp_faces
336      || !p_paragraph->pi_run_ids|| !p_paragraph->p_glyph_bitmaps
337      || !p_paragraph->pi_karaoke_bar || !p_paragraph->p_runs )
338         goto error;
339
340     if( p_code_points )
341         memcpy( p_paragraph->p_code_points, p_code_points,
342                 i_size * sizeof( *p_code_points ) );
343     if( pp_styles )
344         memcpy( p_paragraph->pp_styles, pp_styles,
345                 i_size * sizeof( *pp_styles ) );
346     if( p_paragraph->pp_ruby )
347         memcpy( p_paragraph->pp_ruby, pp_ruby, i_size * sizeof( *pp_ruby ) );
348
349     if( pi_k_dates )
350     {
351         int64_t i_elapsed  = var_GetInteger( p_filter, "spu-elapsed" ) / 1000;
352         for( int i = 0; i < i_size; ++i )
353         {
354             p_paragraph->pi_karaoke_bar[ i ] = pi_k_dates[ i ] >= i_elapsed;
355         }
356     }
357
358 #ifdef HAVE_HARFBUZZ
359     p_paragraph->p_scripts = vlc_alloc( i_size, sizeof( *p_paragraph->p_scripts ) );
360     if( !p_paragraph->p_scripts )
361         goto error;
362 #endif
363
364 #ifdef HAVE_FRIBIDI
365     p_paragraph->p_levels = vlc_alloc( i_size, sizeof( *p_paragraph->p_levels ) );
366     p_paragraph->p_types = vlc_alloc( i_size, sizeof( *p_paragraph->p_types ) );
367 #if FRIBIDI_MAJOR_VERSION >= 1
368     p_paragraph->p_btypes = vlc_alloc( i_size, sizeof( *p_paragraph->p_btypes ) );
369 #endif
370     p_paragraph->pi_reordered_indices =
371             vlc_alloc( i_size, sizeof( *p_paragraph->pi_reordered_indices ) );
372
373     if( !p_paragraph->p_levels || !p_paragraph->p_types
374      || !p_paragraph->pi_reordered_indices )
375         goto error;
376
377     for( int i=0; i<i_size; i++ )
378         p_paragraph->pi_reordered_indices[i] = i;
379
380     int i_direction = var_InheritInteger( p_filter, "freetype-text-direction" );
381     if( i_direction == 0 )
382         p_paragraph->paragraph_type = FRIBIDI_PAR_LTR;
383     else if( i_direction == 1 )
384         p_paragraph->paragraph_type = FRIBIDI_PAR_RTL;
385     else
386         p_paragraph->paragraph_type = FRIBIDI_PAR_ON;
387 #endif
388
389     return p_paragraph;
390
391 error:
392     if( p_paragraph->p_code_points ) free( p_paragraph->p_code_points );
393     if( p_paragraph->pi_glyph_indices ) free( p_paragraph->pi_glyph_indices );
394     if( p_paragraph->pp_styles ) free( p_paragraph->pp_styles );
395     if( p_paragraph->pp_ruby ) free( p_paragraph->pp_ruby );
396     if( p_paragraph->pp_faces ) free( p_paragraph->pp_faces );
397     if( p_paragraph->pi_run_ids ) free( p_paragraph->pi_run_ids );
398     if( p_paragraph->p_glyph_bitmaps ) free( p_paragraph->p_glyph_bitmaps );
399     if (p_paragraph->pi_karaoke_bar ) free( p_paragraph->pi_karaoke_bar );
400     if( p_paragraph->p_runs ) free( p_paragraph->p_runs );
401 #ifdef HAVE_HARFBUZZ
402     if( p_paragraph->p_scripts ) free( p_paragraph->p_scripts );
403 #endif
404 #ifdef HAVE_FRIBIDI
405     if( p_paragraph->p_levels ) free( p_paragraph->p_levels );
406     if( p_paragraph->p_types ) free( p_paragraph->p_types );
407 #if FRIBIDI_MAJOR_VERSION >= 1
408     if( p_paragraph->p_btypes ) free( p_paragraph->p_btypes );
409 #endif
410     if( p_paragraph->pi_reordered_indices )
411         free( p_paragraph->pi_reordered_indices );
412 #endif
413     free( p_paragraph );
414     return 0;
415 }
416
417 static void FreeParagraph( paragraph_t *p_paragraph )
418 {
419     free( p_paragraph->p_runs );
420     free( p_paragraph->pi_glyph_indices );
421     free( p_paragraph->p_glyph_bitmaps );
422     free( p_paragraph->pi_karaoke_bar );
423     free( p_paragraph->pi_run_ids );
424     free( p_paragraph->pp_faces );
425     free( p_paragraph->pp_ruby );
426     free( p_paragraph->pp_styles );
427     free( p_paragraph->p_code_points );
428
429 #ifdef HAVE_HARFBUZZ
430     free( p_paragraph->p_scripts );
431 #endif
432
433 #ifdef HAVE_FRIBIDI
434     free( p_paragraph->pi_reordered_indices );
435     free( p_paragraph->p_types );
436 #if FRIBIDI_MAJOR_VERSION >= 1
437     free( p_paragraph->p_btypes );
438 #endif
439     free( p_paragraph->p_levels );
440 #endif
441
442     free( p_paragraph );
443 }
444
445 #ifdef HAVE_FRIBIDI
446 static int AnalyzeParagraph( paragraph_t *p_paragraph )
447 {
448     fribidi_get_bidi_types(  p_paragraph->p_code_points,
449                              p_paragraph->i_size,
450                              p_paragraph->p_types );
451 #if FRIBIDI_MAJOR_VERSION >= 1
452     fribidi_get_bracket_types( p_paragraph->p_code_points,
453                                p_paragraph->i_size,
454                                p_paragraph->p_types,
455                                p_paragraph->p_btypes );
456     fribidi_get_par_embedding_levels_ex( p_paragraph->p_types,
457                                       p_paragraph->p_btypes,
458                                       p_paragraph->i_size,
459                                       &p_paragraph->paragraph_type,
460                                       p_paragraph->p_levels );
461 #else
462     fribidi_get_par_embedding_levels( p_paragraph->p_types,
463                                       p_paragraph->i_size,
464                                       &p_paragraph->paragraph_type,
465                                       p_paragraph->p_levels );
466 #endif
467
468 #ifdef HAVE_HARFBUZZ
469     hb_unicode_funcs_t *p_funcs = hb_unicode_funcs_get_default();
470     for( int i = 0; i < p_paragraph->i_size; ++i )
471         p_paragraph->p_scripts[ i ] =
472             hb_unicode_script( p_funcs, p_paragraph->p_code_points[ i ] );
473
474     hb_script_t i_last_script;
475     int i_last_script_index = -1;
476     int i_last_set_index = -1;
477
478     /*
479      * For shaping to work, characters that are assigned HB_SCRIPT_COMMON or
480      * HB_SCRIPT_INHERITED should be resolved to the last encountered valid
481      * script value, if any, and to the first one following them otherwise
482      */
483     for( int i = 0; i < p_paragraph->i_size; ++i )
484     {
485         if( p_paragraph->p_scripts[ i ] == HB_SCRIPT_COMMON
486             || p_paragraph->p_scripts[ i ] == HB_SCRIPT_INHERITED)
487         {
488             if( i_last_script_index != -1)
489             {
490                 p_paragraph->p_scripts[ i ] = i_last_script;
491                 i_last_set_index = i;
492             }
493         }
494         else
495         {
496             for( int j = i_last_set_index + 1; j < i; ++j )
497                 p_paragraph->p_scripts[ j ] = p_paragraph->p_scripts[ i ];
498
499             i_last_script = p_paragraph->p_scripts[ i ];
500             i_last_script_index = i;
501             i_last_set_index = i;
502         }
503     }
504 #endif //HAVE_HARFBUZZ
505
506     return VLC_SUCCESS;
507 }
508 #endif //HAVE_FRIBIDI
509
510 static int AddRun( filter_t *p_filter,
511                    paragraph_t *p_paragraph,
512                    int i_start_offset,
513                    int i_end_offset,
514                    FT_Face p_face,
515                    const text_style_t *p_style )
516 {
517     if( i_start_offset >= i_end_offset
518      || i_start_offset < 0 || i_start_offset >= p_paragraph->i_size
519      || i_end_offset <= 0  || i_end_offset > p_paragraph->i_size )
520     {
521         msg_Err( p_filter,
522                  "AddRun() invalid parameters. Paragraph size: %d, "
523                  "Start offset: %d, End offset: %d",
524                  p_paragraph->i_size, i_start_offset, i_end_offset );
525         return VLC_EGENERIC;
526     }
527
528     if( p_paragraph->i_runs_count == p_paragraph->i_runs_size )
529     {
530         run_desc_t *p_new_runs =
531             realloc( p_paragraph->p_runs,
532                      p_paragraph->i_runs_size * 2 * sizeof( *p_new_runs ) );
533         if( !p_new_runs )
534             return VLC_ENOMEM;
535
536         memset( p_new_runs + p_paragraph->i_runs_size , 0,
537                 p_paragraph->i_runs_size * sizeof( *p_new_runs ) );
538
539         p_paragraph->p_runs = p_new_runs;
540         p_paragraph->i_runs_size *= 2;
541     }
542
543     int i_run_id = p_paragraph->i_runs_count;
544     run_desc_t *p_run = p_paragraph->p_runs + p_paragraph->i_runs_count++;
545     p_run->i_start_offset = i_start_offset;
546     p_run->i_end_offset = i_end_offset;
547     p_run->p_face = p_face;
548
549     if( p_style )
550         p_run->p_style = p_style;
551     else
552         p_run->p_style = p_paragraph->pp_styles[ i_start_offset ];
553
554 #ifdef HAVE_HARFBUZZ
555     p_run->script = p_paragraph->p_scripts[ i_start_offset ];
556     p_run->direction = p_paragraph->p_levels[ i_start_offset ] & 1 ?
557             HB_DIRECTION_RTL : HB_DIRECTION_LTR;
558 #endif
559
560     for( int i = i_start_offset; i < i_end_offset; ++i )
561         p_paragraph->pi_run_ids[ i ] = i_run_id;
562
563     return VLC_SUCCESS;
564 }
565
566 #ifdef HAVE_FONT_FALLBACK
567 /**
568  * Add a run with font fallback, possibly breaking the run further
569  * into runs of glyphs that end up having the same font face.
570  */
571 static int AddRunWithFallback( filter_t *p_filter, paragraph_t *p_paragraph,
572                                int i_start_offset, int i_end_offset )
573 {
574     if( i_start_offset >= i_end_offset
575      || i_start_offset < 0 || i_start_offset >= p_paragraph->i_size
576      || i_end_offset <= 0  || i_end_offset > p_paragraph->i_size )
577     {
578         msg_Err( p_filter,
579                  "AddRunWithFallback() invalid parameters. Paragraph size: %d, "
580                  "Start offset: %d, End offset: %d",
581                  p_paragraph->i_size, i_start_offset, i_end_offset );
582         return VLC_EGENERIC;
583     }
584
585     const text_style_t *p_style = p_paragraph->pp_styles[ i_start_offset ];
586
587     /* Maximum number of faces to try for each run */
588     #define MAX_FACES 5
589     FT_Face pp_faces[ MAX_FACES ] = {0};
590
591     pp_faces[ 0 ] = SelectAndLoadFace( p_filter, p_style, 0 );
592
593     for( int i = i_start_offset; i < i_end_offset; ++i )
594     {
595         int i_index = 0;
596         int i_glyph_index = 0;
597         FT_Face p_face = NULL;
598         do {
599             p_face = pp_faces[ i_index ];
600             if( !p_face )
601                 p_face = pp_faces[ i_index ] =
602                      SelectAndLoadFace( p_filter, p_style,
603                                         p_paragraph->p_code_points[ i ] );
604             if( !p_face )
605                 continue;
606             i_glyph_index = FT_Get_Char_Index( p_face,
607                                                p_paragraph->p_code_points[ i ] );
608             if( i_glyph_index )
609             {
610                 p_paragraph->pp_faces[ i ] = p_face;
611
612                 /*
613                  * Move p_face to the beginning of the array. Otherwise strikethrough
614                  * lines can appear segmented, being rendered at a certain height
615                  * through spaces and at a different height through words.
616                  * Skip this step for the specified special characters. See #15840.
617                  */
618                 if( i_index > 0 )
619                 {
620                     uni_char_t codepoint = p_paragraph->p_code_points[ i ];
621                     if( codepoint != 0x0009 && codepoint != 0x00A0
622                      && codepoint != 0x1680 && codepoint != 0x061C
623                      && codepoint != 0x202F && codepoint != 0x205F
624                      && codepoint != 0x3000 && codepoint != 0xFEFF
625                      && !( codepoint >= 0x2000 && codepoint <= 0x200F )
626                      && !( codepoint >= 0x202A && codepoint <= 0x202E )
627                      && !( codepoint >= 0x2060 && codepoint <= 0x2069 ) )
628                     {
629                         pp_faces[ i_index ] = pp_faces[ 0 ];
630                         pp_faces[ 0 ] = p_face;
631                     }
632                 }
633             }
634
635         } while( i_glyph_index == 0 && ++i_index < MAX_FACES );
636     }
637
638     int i_run_start = i_start_offset;
639     for( int i = i_start_offset; i <= i_end_offset; ++i )
640     {
641         if( i == i_end_offset
642          || p_paragraph->pp_faces[ i_run_start ] != p_paragraph->pp_faces[ i ] )
643         {
644             if( AddRun( p_filter, p_paragraph, i_run_start, i,
645                         p_paragraph->pp_faces[ i_run_start ], NULL ) )
646                 return VLC_EGENERIC;
647
648             i_run_start = i;
649         }
650     }
651
652     return VLC_SUCCESS;
653 }
654 #endif
655
656 static bool FaceStyleEquals( filter_t *p_filter, const text_style_t *p_style1,
657                              const text_style_t *p_style2 )
658 {
659     if( !p_style1 || !p_style2 )
660         return false;
661     if( p_style1 == p_style2 )
662         return true;
663
664     const int i_style_mask = STYLE_BOLD | STYLE_ITALIC | STYLE_HALFWIDTH | STYLE_DOUBLEWIDTH;
665
666     const char *psz_fontname1 = p_style1->i_style_flags & STYLE_MONOSPACED
667                               ? p_style1->psz_monofontname : p_style1->psz_fontname;
668
669     const char *psz_fontname2 = p_style2->i_style_flags & STYLE_MONOSPACED
670                               ? p_style2->psz_monofontname : p_style2->psz_fontname;
671
672     const int i_size1 = ConvertToLiveSize( p_filter, p_style1 );
673     const int i_size2 = ConvertToLiveSize( p_filter, p_style2 );
674
675     return (p_style1->i_style_flags & i_style_mask) == (p_style2->i_style_flags & i_style_mask)
676          && i_size1 == i_size2
677          && !strcasecmp( psz_fontname1, psz_fontname2 );
678 }
679
680 /**
681  * Segment a paragraph into runs
682  */
683 static int ItemizeParagraph( filter_t *p_filter, paragraph_t *p_paragraph )
684 {
685     if( p_paragraph->i_size <= 0 )
686     {
687         msg_Err( p_filter,
688                  "ItemizeParagraph() invalid parameters. Paragraph size: %d",
689                  p_paragraph->i_size );
690         return VLC_EGENERIC;
691     }
692
693     int i_last_run_start = 0;
694     const text_style_t *p_last_style = p_paragraph->pp_styles[ 0 ];
695
696 #ifdef HAVE_HARFBUZZ
697     hb_script_t last_script = p_paragraph->p_scripts[ 0 ];
698     FriBidiLevel last_level = p_paragraph->p_levels[ 0 ];
699 #endif
700
701     for( int i = 0; i <= p_paragraph->i_size; ++i )
702     {
703         if( i == p_paragraph->i_size
704 #ifdef HAVE_HARFBUZZ
705             || last_script != p_paragraph->p_scripts[ i ]
706             || last_level != p_paragraph->p_levels[ i ]
707 #endif
708             || !FaceStyleEquals( p_filter, p_last_style, p_paragraph->pp_styles[ i ] ) )
709         {
710             int i_ret;
711 #ifdef HAVE_FONT_FALLBACK
712             i_ret = AddRunWithFallback( p_filter, p_paragraph, i_last_run_start, i );
713 #else
714             i_ret = AddRun( p_filter, p_paragraph, i_last_run_start, i, NULL, NULL );
715 #endif
716             if( i_ret )
717                 return i_ret;
718
719             if( i < p_paragraph->i_size )
720             {
721                 i_last_run_start = i;
722                 p_last_style = p_paragraph->pp_styles[ i ];
723 #ifdef HAVE_HARFBUZZ
724                 last_script = p_paragraph->p_scripts[ i ];
725                 last_level = p_paragraph->p_levels[ i ];
726 #endif
727             }
728         }
729     }
730     return VLC_SUCCESS;
731 }
732
733 #ifdef HAVE_HARFBUZZ
734 /**
735  * Shape an itemized paragraph using HarfBuzz.
736  * This is where the glyphs of complex scripts get their positions
737  * (offsets and advance values) and final forms.
738  * Glyph substitutions of base glyphs and diacritics may take place,
739  * so the paragraph size may change.
740  */
741 static int ShapeParagraphHarfBuzz( filter_t *p_filter,
742                                    paragraph_t **p_old_paragraph )
743 {
744     paragraph_t *p_paragraph = *p_old_paragraph;
745     paragraph_t *p_new_paragraph = 0;
746     filter_sys_t *p_sys = p_filter->p_sys;
747     int i_total_glyphs = 0;
748     int i_ret = VLC_EGENERIC;
749
750     if( p_paragraph->i_size <= 0 || p_paragraph->i_runs_count <= 0 )
751     {
752         msg_Err( p_filter, "ShapeParagraphHarfBuzz() invalid parameters. "
753                  "Paragraph size: %d. Runs count %d",
754                  p_paragraph->i_size, p_paragraph->i_runs_count );
755         return VLC_EGENERIC;
756     }
757
758     for( int i = 0; i < p_paragraph->i_runs_count; ++i )
759     {
760         run_desc_t *p_run = p_paragraph->p_runs + i;
761         const text_style_t *p_style = p_run->p_style;
762
763         /*
764          * With HarfBuzz and no font fallback, this is where font faces
765          * are loaded. In the other two paths (shaping with FriBidi or no
766          * shaping at all), faces are loaded in LoadGlyphs().
767          *
768          * If we have font fallback, font faces in all paths will be
769          * loaded in AddRunWithFallback(), except for runs of codepoints
770          * for which no font could be found.
771          */
772         FT_Face p_face = 0;
773         if( !p_run->p_face )
774         {
775             p_face = SelectAndLoadFace( p_filter, p_style, 0 );
776             if( !p_face )
777             {
778                 p_face = p_sys->p_face;
779                 p_style = p_sys->p_default_style;
780                 p_run->p_style = p_style;
781             }
782             p_run->p_face = p_face;
783         }
784         else
785             p_face = p_run->p_face;
786
787         p_run->p_hb_font = hb_ft_font_create( p_face, 0 );
788         if( !p_run->p_hb_font )
789         {
790             msg_Err( p_filter,
791                      "ShapeParagraphHarfBuzz(): hb_ft_font_create() error" );
792             goto error;
793         }
794
795         p_run->p_buffer = hb_buffer_create();
796         if( !p_run->p_buffer )
797         {
798             msg_Err( p_filter,
799                      "ShapeParagraphHarfBuzz(): hb_buffer_create() error" );
800             goto error;
801         }
802
803         hb_buffer_set_direction( p_run->p_buffer, p_run->direction );
804         hb_buffer_set_script( p_run->p_buffer, p_run->script );
805 #ifdef __OS2__
806         hb_buffer_add_utf16( p_run->p_buffer,
807                              p_paragraph->p_code_points + p_run->i_start_offset,
808                              p_run->i_end_offset - p_run->i_start_offset, 0,
809                              p_run->i_end_offset - p_run->i_start_offset );
810 #else
811         hb_buffer_add_utf32( p_run->p_buffer,
812                              p_paragraph->p_code_points + p_run->i_start_offset,
813                              p_run->i_end_offset - p_run->i_start_offset, 0,
814                              p_run->i_end_offset - p_run->i_start_offset );
815 #endif
816         hb_shape( p_run->p_hb_font, p_run->p_buffer, 0, 0 );
817         p_run->p_glyph_infos =
818             hb_buffer_get_glyph_infos( p_run->p_buffer, &p_run->i_glyph_count );
819         p_run->p_glyph_positions =
820             hb_buffer_get_glyph_positions( p_run->p_buffer, &p_run->i_glyph_count );
821
822         if( p_run->i_glyph_count <= 0 )
823         {
824             msg_Err( p_filter,
825                      "ShapeParagraphHarfBuzz() invalid glyph count in shaped run" );
826             goto error;
827         }
828
829         i_total_glyphs += p_run->i_glyph_count;
830     }
831
832     p_new_paragraph = NewParagraph( p_filter, i_total_glyphs,
833                                     NULL, NULL, NULL, NULL,
834                                     p_paragraph->i_runs_size );
835     if( !p_new_paragraph )
836     {
837         i_ret = VLC_ENOMEM;
838         goto error;
839     }
840     if( p_paragraph->pp_ruby )
841     {
842         p_new_paragraph->pp_ruby = calloc(p_new_paragraph->i_size,
843                                           sizeof(ruby_block_t *));
844     }
845
846     p_new_paragraph->paragraph_type = p_paragraph->paragraph_type;
847
848     int i_index = 0;
849     for( int i = 0; i < p_paragraph->i_runs_count; ++i )
850     {
851         run_desc_t *p_run = p_paragraph->p_runs + i;
852         hb_glyph_info_t *p_infos = p_run->p_glyph_infos;
853         hb_glyph_position_t *p_positions = p_run->p_glyph_positions;
854         for( unsigned int j = 0; j < p_run->i_glyph_count; ++j )
855         {
856             /*
857              * HarfBuzz reverses the order of glyphs in RTL runs. We reverse
858              * it again here to keep the glyphs in their logical order.
859              * For line breaking of paragraphs to work correctly, visual
860              * reordering should be done after line breaking has taken
861              * place.
862              */
863             int i_run_index = p_run->direction == HB_DIRECTION_LTR ?
864                     j : p_run->i_glyph_count - 1 - j;
865             int i_source_index =
866                     p_infos[ i_run_index ].cluster + p_run->i_start_offset;
867
868             p_new_paragraph->p_code_points[ i_index ] = 0;
869             p_new_paragraph->pi_glyph_indices[ i_index ] =
870                 p_infos[ i_run_index ].codepoint;
871             p_new_paragraph->p_scripts[ i_index ] =
872                 p_paragraph->p_scripts[ i_source_index ];
873             p_new_paragraph->p_types[ i_index ] =
874                 p_paragraph->p_types[ i_source_index ];
875             p_new_paragraph->p_levels[ i_index ] =
876                 p_paragraph->p_levels[ i_source_index ];
877             p_new_paragraph->pp_styles[ i_index ] =
878                 p_paragraph->pp_styles[ i_source_index ];
879             if( p_new_paragraph->pp_ruby )
880                 p_new_paragraph->pp_ruby[ i_index ] =
881                     p_paragraph->pp_ruby[ i_source_index ];
882             p_new_paragraph->pi_karaoke_bar[ i_index ] =
883                 p_paragraph->pi_karaoke_bar[ i_source_index ];
884             p_new_paragraph->p_glyph_bitmaps[ i_index ].i_x_offset =
885                 p_positions[ i_run_index ].x_offset;
886             p_new_paragraph->p_glyph_bitmaps[ i_index ].i_y_offset =
887                 p_positions[ i_run_index ].y_offset;
888             p_new_paragraph->p_glyph_bitmaps[ i_index ].i_x_advance =
889                 p_positions[ i_run_index ].x_advance;
890             p_new_paragraph->p_glyph_bitmaps[ i_index ].i_y_advance =
891                 p_positions[ i_run_index ].y_advance;
892
893             ++i_index;
894         }
895         if( AddRun( p_filter, p_new_paragraph, i_index - p_run->i_glyph_count,
896                     i_index, p_run->p_face, p_run->p_style ) )
897             goto error;
898     }
899
900     for( int i = 0; i < p_paragraph->i_runs_count; ++i )
901     {
902         hb_font_destroy( p_paragraph->p_runs[ i ].p_hb_font );
903         hb_buffer_destroy( p_paragraph->p_runs[ i ].p_buffer );
904     }
905     FreeParagraph( *p_old_paragraph );
906     *p_old_paragraph = p_new_paragraph;
907
908     return VLC_SUCCESS;
909
910 error:
911     for( int i = 0; i < p_paragraph->i_runs_count; ++i )
912     {
913         if( p_paragraph->p_runs[ i ].p_hb_font )
914             hb_font_destroy( p_paragraph->p_runs[ i ].p_hb_font );
915         if( p_paragraph->p_runs[ i ].p_buffer )
916             hb_buffer_destroy( p_paragraph->p_runs[ i ].p_buffer );
917     }
918
919     if( p_new_paragraph )
920         FreeParagraph( p_new_paragraph );
921
922     return i_ret;
923 }
924 #endif
925
926 #ifdef HAVE_FRIBIDI
927 #ifndef HAVE_HARFBUZZ
928 /**
929  * Shape a paragraph with FriBidi.
930  * Shaping with FriBidi is currently limited to mirroring and simple
931  * Arabic shaping.
932  */
933 static int ShapeParagraphFriBidi( filter_t *p_filter, paragraph_t *p_paragraph )
934 {
935
936     if( p_paragraph->i_size <= 0 )
937     {
938         msg_Err( p_filter,
939                 "ShapeParagraphFriBidi() invalid parameters. Paragraph size: %d",
940                  p_paragraph->i_size );
941         return VLC_EGENERIC;
942     }
943
944     FriBidiJoiningType *p_joining_types =
945             vlc_alloc( p_paragraph->i_size, sizeof( *p_joining_types ) );
946     if( !p_joining_types )
947         return VLC_ENOMEM;
948
949     fribidi_get_joining_types( p_paragraph->p_code_points,
950                                p_paragraph->i_size, p_joining_types );
951     fribidi_join_arabic( p_paragraph->p_types, p_paragraph->i_size,
952                          p_paragraph->p_levels, p_joining_types );
953     fribidi_shape( FRIBIDI_FLAGS_DEFAULT | FRIBIDI_FLAGS_ARABIC,
954                    p_paragraph->p_levels,
955                    p_paragraph->i_size,
956                    p_joining_types,
957                    p_paragraph->p_code_points );
958
959     free( p_joining_types );
960
961     return VLC_SUCCESS;
962 }
963
964 /**
965  * Zero-width invisible characters include Unicode control characters and
966  * zero-width spaces among other things. If not removed they can show up in the
967  * text as squares or other glyphs depending on the font. Zero-width spaces are
968  * inserted when shaping with FriBidi, when it performs glyph substitution for
969  * ligatures.
970  */
971 static int RemoveZeroWidthCharacters( paragraph_t *p_paragraph )
972 {
973     for( int i = 0; i < p_paragraph->i_size; ++i )
974     {
975         uni_char_t ch = p_paragraph->p_code_points[ i ];
976         if( ch == 0xfeff
977          || ch == 0x061c
978          || ( ch >= 0x202a && ch <= 0x202e )
979          || ( ch >= 0x2060 && ch <= 0x2069 )
980          || ( ch >= 0x200b && ch <= 0x200f ) )
981         {
982             glyph_bitmaps_t *p_bitmaps = p_paragraph->p_glyph_bitmaps + i;
983             if( p_bitmaps->p_glyph )
984                 FT_Done_Glyph( p_bitmaps->p_glyph );
985             if( p_bitmaps->p_outline )
986                 FT_Done_Glyph( p_bitmaps->p_outline );
987             p_bitmaps->p_glyph = 0;
988             p_bitmaps->p_outline = 0;
989             p_bitmaps->p_shadow = 0;
990             p_bitmaps->i_x_advance = 0;
991             p_bitmaps->i_y_advance = 0;
992         }
993     }
994
995     return VLC_SUCCESS;
996 }
997
998 /**
999  * Set advance values of non-spacing marks to zero. Diacritics are
1000  * not positioned correctly but the text is more readable.
1001  * For full shaping HarfBuzz is required.
1002  */
1003 static int ZeroNsmAdvance( paragraph_t *p_paragraph )
1004 {
1005     for( int i = 0; i < p_paragraph->i_size; ++i )
1006         if( p_paragraph->p_types[ i ] == FRIBIDI_TYPE_NSM )
1007         {
1008             p_paragraph->p_glyph_bitmaps[ i ].i_x_advance = 0;
1009             p_paragraph->p_glyph_bitmaps[ i ].i_y_advance = 0;
1010         }
1011     return VLC_SUCCESS;
1012 }
1013 #endif
1014 #endif
1015
1016 /**
1017  * Load the glyphs of a paragraph. When shaping with HarfBuzz the glyph indices
1018  * have already been determined at this point, as well as the advance values.
1019  */
1020 static int LoadGlyphs( filter_t *p_filter, paragraph_t *p_paragraph,
1021                        bool b_use_glyph_indices, bool b_overwrite_advance,
1022                        unsigned *pi_max_advance_x )
1023 {
1024     if( p_paragraph->i_size <= 0 || p_paragraph->i_runs_count <= 0 )
1025     {
1026         msg_Err( p_filter, "LoadGlyphs() invalid parameters. "
1027                  "Paragraph size: %d. Runs count %d", p_paragraph->i_size,
1028                  p_paragraph->i_runs_count );
1029         return VLC_EGENERIC;
1030     }
1031
1032     filter_sys_t *p_sys = p_filter->p_sys;
1033     *pi_max_advance_x = 0;
1034
1035     for( int i = 0; i < p_paragraph->i_runs_count; ++i )
1036     {
1037         run_desc_t *p_run = p_paragraph->p_runs + i;
1038         const text_style_t *p_style = p_run->p_style;
1039         const int i_live_size = ConvertToLiveSize( p_filter, p_style );
1040
1041         FT_Face p_face = 0;
1042         if( !p_run->p_face )
1043         {
1044             p_face = SelectAndLoadFace( p_filter, p_style,
1045                                         p_paragraph->p_code_points[p_run->i_start_offset] );
1046             if( !p_face )
1047             {
1048                 /* Uses the default font and style */
1049                 p_face = p_sys->p_face;
1050                 p_style = p_sys->p_default_style;
1051                 p_run->p_style = p_style;
1052             }
1053             p_run->p_face = p_face;
1054         }
1055         else
1056             p_face = p_run->p_face;
1057
1058         if( p_sys->p_stroker && (p_style->i_style_flags & STYLE_OUTLINE) )
1059         {
1060             double f_outline_thickness =
1061                 var_InheritInteger( p_filter, "freetype-outline-thickness" ) / 100.0;
1062             f_outline_thickness = VLC_CLIP( f_outline_thickness, 0.0, 0.5 );
1063             int i_radius = ( i_live_size << 6 ) * f_outline_thickness;
1064             FT_Stroker_Set( p_sys->p_stroker,
1065                             i_radius,
1066                             FT_STROKER_LINECAP_ROUND,
1067                             FT_STROKER_LINEJOIN_ROUND, 0 );
1068         }
1069
1070         for( int j = p_run->i_start_offset; j < p_run->i_end_offset; ++j )
1071         {
1072             int i_glyph_index;
1073             if( b_use_glyph_indices )
1074                 i_glyph_index = p_paragraph->pi_glyph_indices[ j ];
1075             else
1076                 i_glyph_index =
1077                     FT_Get_Char_Index( p_face, p_paragraph->p_code_points[ j ] );
1078
1079             glyph_bitmaps_t *p_bitmaps = p_paragraph->p_glyph_bitmaps + j;
1080
1081 #define SKIP_GLYPH( p_bitmaps ) \
1082     { \
1083         p_bitmaps->p_glyph = 0; \
1084         p_bitmaps->p_outline = 0; \
1085         p_bitmaps->p_shadow = 0; \
1086         p_bitmaps->i_x_advance = 0; \
1087         p_bitmaps->i_y_advance = 0; \
1088         continue; \
1089     }
1090
1091             if( !i_glyph_index )
1092             {
1093                 uni_char_t codepoint = p_paragraph->p_code_points[ j ];
1094                 /*
1095                  * If the font has no support for special space characters, use regular
1096                  * space glyphs instead of the .notdef glyph.
1097                  */
1098                 if( codepoint == 0x0009 || codepoint == 0x00A0
1099                  || codepoint == 0x1680 || codepoint == 0x3000
1100                  || codepoint == 0x202F || codepoint == 0x205F
1101                  || ( codepoint >= 0x2000 && codepoint <= 0x200A )
1102 #ifdef HAVE_FRIBIDI
1103                  || p_paragraph->p_types[ j ] == FRIBIDI_TYPE_WS
1104                  || p_paragraph->p_types[ j ] == FRIBIDI_TYPE_CS
1105                  || p_paragraph->p_types[ j ] == FRIBIDI_TYPE_SS
1106 #endif
1107                  )
1108                 {
1109                     i_glyph_index = 3;
1110                 }
1111                 /* Skip carriage returns */
1112                 else if( codepoint == 0x0D
1113 #ifdef HAVE_FRIBIDI
1114                  || p_paragraph->p_types[ j ] == FRIBIDI_TYPE_BS
1115 #endif
1116                  )
1117                     SKIP_GLYPH( p_bitmaps )
1118             }
1119
1120             if( FT_Load_Glyph( p_face, i_glyph_index,
1121                                FT_LOAD_NO_BITMAP | FT_LOAD_DEFAULT )
1122              && FT_Load_Glyph( p_face, i_glyph_index, FT_LOAD_DEFAULT ) )
1123                 SKIP_GLYPH( p_bitmaps )
1124
1125             if( ( p_style->i_style_flags & STYLE_BOLD )
1126                   && !( p_face->style_flags & FT_STYLE_FLAG_BOLD ) )
1127                 FT_GlyphSlot_Embolden( p_face->glyph );
1128             if( ( p_style->i_style_flags & STYLE_ITALIC )
1129                   && !( p_face->style_flags & FT_STYLE_FLAG_ITALIC ) )
1130                 FT_GlyphSlot_Oblique( p_face->glyph );
1131
1132             if( FT_Get_Glyph( p_face->glyph, &p_bitmaps->p_glyph ) )
1133                 SKIP_GLYPH( p_bitmaps )
1134
1135 #undef SKIP_GLYPH
1136
1137             if( p_filter->p_sys->p_stroker && (p_style->i_style_flags & STYLE_OUTLINE) )
1138             {
1139                 p_bitmaps->p_outline = p_bitmaps->p_glyph;
1140                 if( FT_Glyph_StrokeBorder( &p_bitmaps->p_outline,
1141                                            p_filter->p_sys->p_stroker, 0, 0 ) )
1142                     p_bitmaps->p_outline = 0;
1143             }
1144
1145             if( p_style->i_shadow_alpha != STYLE_ALPHA_TRANSPARENT )
1146                 p_bitmaps->p_shadow = p_bitmaps->p_outline ?
1147                                       p_bitmaps->p_outline : p_bitmaps->p_glyph;
1148
1149             if( b_overwrite_advance )
1150             {
1151                 p_bitmaps->i_x_advance = p_face->glyph->advance.x;
1152                 p_bitmaps->i_y_advance = p_face->glyph->advance.y;
1153             }
1154         }
1155
1156         int i_max_run_advance_x = FT_FLOOR( FT_MulFix( p_face->max_advance_width, p_face->size->metrics.x_scale ) );
1157         if( i_max_run_advance_x > *pi_max_advance_x )
1158             *pi_max_advance_x = i_max_run_advance_x;
1159     }
1160     return VLC_SUCCESS;
1161 }
1162
1163 static int LayoutLine( filter_t *p_filter,
1164                        paragraph_t *p_paragraph,
1165                        int i_first_char, int i_last_char,
1166                        bool b_grid,
1167                        line_desc_t **pp_line )
1168 {
1169     if( p_paragraph->i_size <= 0 || p_paragraph->i_runs_count <= 0
1170      || i_first_char < 0 || i_last_char < 0
1171      || i_first_char > i_last_char
1172      || i_last_char >= p_paragraph->i_size )
1173     {
1174         msg_Err( p_filter,
1175                  "LayoutLine() invalid parameters. "
1176                  "Paragraph size: %d. Runs count: %d. "
1177                  "Start char: %d. End char: %d",
1178                  p_paragraph->i_size, p_paragraph->i_runs_count,
1179                  i_first_char, i_last_char );
1180         return VLC_EGENERIC;
1181     }
1182
1183     filter_sys_t *p_sys = p_filter->p_sys;
1184     int i_last_run = -1;
1185     run_desc_t *p_run = 0;
1186     const text_style_t *p_style = 0;
1187     FT_Face p_face = 0;
1188     FT_Vector pen = { .x = 0, .y = 0 };
1189
1190     int i_font_size = 0;
1191     int i_font_width = 0;
1192     int i_font_max_advance_y = 0;
1193     int i_ul_offset = 0;
1194     int i_ul_thickness = 0;
1195
1196 #ifdef HAVE_FRIBIDI
1197     bool b_reordered = ( 0 ==
1198         fribidi_reorder_line( 0, &p_paragraph->p_types[i_first_char],
1199                           1 + i_last_char - i_first_char,
1200                           0, p_paragraph->paragraph_type,
1201                           &p_paragraph->p_levels[i_first_char],
1202                           0, &p_paragraph->pi_reordered_indices[i_first_char] ) );
1203 #endif
1204
1205     line_desc_t *p_line = NewLine( 1 + i_last_char - i_first_char );
1206     if( !p_line )
1207         return VLC_ENOMEM;
1208
1209     for( int i = i_first_char; i <= i_last_char; ++i )
1210     {
1211         int i_paragraph_index;
1212 #ifdef HAVE_FRIBIDI
1213         if( b_reordered )
1214             i_paragraph_index = p_paragraph->pi_reordered_indices[ i ];
1215         else
1216 #endif
1217         i_paragraph_index = i;
1218
1219         line_character_t *p_ch = &p_line->p_character[p_line->i_character_count];
1220         p_ch->p_style = p_paragraph->pp_styles[ i_paragraph_index ];
1221
1222         if( p_paragraph->pp_ruby )
1223             p_ch->p_ruby = p_paragraph->pp_ruby[ i ];
1224
1225         glyph_bitmaps_t *p_bitmaps =
1226                 p_paragraph->p_glyph_bitmaps + i_paragraph_index;
1227
1228         if( !p_bitmaps->p_glyph )
1229         {
1230             BBoxInit( &p_ch->bbox );
1231             continue;
1232         }
1233
1234         if( i_last_run != p_paragraph->pi_run_ids[ i_paragraph_index ] )
1235         {
1236             i_last_run = p_paragraph->pi_run_ids[ i_paragraph_index ];
1237             p_run = p_paragraph->p_runs + i_last_run;
1238             p_style = p_run->p_style;
1239             p_face = p_run->p_face;
1240
1241             i_font_width = i_font_size = ConvertToLiveSize( p_filter, p_style );
1242             if( p_style->i_style_flags & STYLE_HALFWIDTH )
1243                 i_font_width /= 2;
1244             else if( p_style->i_style_flags & STYLE_DOUBLEWIDTH )
1245                 i_font_width *= 2;
1246         }
1247
1248         FT_Vector pen_new = {
1249             .x = pen.x + p_paragraph->p_glyph_bitmaps[ i_paragraph_index ].i_x_offset,
1250             .y = pen.y + p_paragraph->p_glyph_bitmaps[ i_paragraph_index ].i_y_offset
1251         };
1252         FT_Vector pen_shadow = {
1253             .x = pen_new.x + p_sys->f_shadow_vector_x * ( i_font_width << 6 ),
1254             .y = pen_new.y + p_sys->f_shadow_vector_y * ( i_font_size << 6 )
1255         };
1256
1257         if( p_bitmaps->p_shadow )
1258         {
1259             if( FT_Glyph_To_Bitmap( &p_bitmaps->p_shadow, FT_RENDER_MODE_NORMAL,
1260                                     &pen_shadow, 0 ) )
1261                 p_bitmaps->p_shadow = 0;
1262             else
1263                 FT_Glyph_Get_CBox( p_bitmaps->p_shadow, ft_glyph_bbox_pixels,
1264                                    &p_bitmaps->shadow_bbox );
1265         }
1266         if( p_bitmaps->p_glyph )
1267         {
1268             if( FT_Glyph_To_Bitmap( &p_bitmaps->p_glyph, FT_RENDER_MODE_NORMAL,
1269                                     &pen_new, 1 ) )
1270             {
1271                 FT_Done_Glyph( p_bitmaps->p_glyph );
1272                 if( p_bitmaps->p_outline )
1273                     FT_Done_Glyph( p_bitmaps->p_outline );
1274                 if( p_bitmaps->p_shadow )
1275                     FT_Done_Glyph( p_bitmaps->p_shadow );
1276                 continue;
1277             }
1278             else
1279                 FT_Glyph_Get_CBox( p_bitmaps->p_glyph, ft_glyph_bbox_pixels,
1280                                    &p_bitmaps->glyph_bbox );
1281         }
1282         if( p_bitmaps->p_outline )
1283         {
1284             if( FT_Glyph_To_Bitmap( &p_bitmaps->p_outline, FT_RENDER_MODE_NORMAL,
1285                                     &pen_new, 1 ) )
1286             {
1287                 FT_Done_Glyph( p_bitmaps->p_outline );
1288                 p_bitmaps->p_outline = 0;
1289             }
1290             else
1291                 FT_Glyph_Get_CBox( p_bitmaps->p_outline, ft_glyph_bbox_pixels,
1292                                    &p_bitmaps->outline_bbox );
1293         }
1294
1295         FixGlyph( p_bitmaps->p_glyph, &p_bitmaps->glyph_bbox,
1296                   p_bitmaps->i_x_advance, p_bitmaps->i_y_advance,
1297                   &pen_new );
1298         if( p_bitmaps->p_outline )
1299             FixGlyph( p_bitmaps->p_outline, &p_bitmaps->outline_bbox,
1300                       p_bitmaps->i_x_advance, p_bitmaps->i_y_advance,
1301                       &pen_new );
1302         if( p_bitmaps->p_shadow )
1303             FixGlyph( p_bitmaps->p_shadow, &p_bitmaps->shadow_bbox,
1304                       p_bitmaps->i_x_advance, p_bitmaps->i_y_advance,
1305                       &pen_shadow );
1306
1307         int i_line_offset    = 0;
1308         int i_line_thickness = 0;
1309
1310         if( p_ch->p_style->i_style_flags & (STYLE_UNDERLINE | STYLE_STRIKEOUT) )
1311         {
1312             i_line_offset =
1313                 abs( FT_FLOOR( FT_MulFix( p_face->underline_position,
1314                                           p_face->size->metrics.y_scale ) ) );
1315
1316             i_line_thickness =
1317                 abs( FT_CEIL( FT_MulFix( p_face->underline_thickness,
1318                                          p_face->size->metrics.y_scale ) ) );
1319
1320             if( p_ch->p_style->i_style_flags & STYLE_STRIKEOUT )
1321             {
1322                 /* Move the baseline to make it strikethrough instead of
1323                  * underline. That means that strikethrough takes precedence
1324                  */
1325                 i_line_offset -=
1326                     abs( FT_FLOOR( FT_MulFix( p_face->descender * 2,
1327                                               p_face->size->metrics.y_scale ) ) );
1328                 p_bitmaps->glyph_bbox.yMax =
1329                     __MAX( p_bitmaps->glyph_bbox.yMax,
1330                            - i_line_offset );
1331                 p_bitmaps->glyph_bbox.yMin =
1332                     __MIN( p_bitmaps->glyph_bbox.yMin,
1333                            i_line_offset - i_line_thickness );
1334             }
1335             else if( i_line_thickness > 0 )
1336             {
1337                 p_bitmaps->glyph_bbox.yMin =
1338                     __MIN( p_bitmaps->glyph_bbox.yMin,
1339                            - i_line_offset - i_line_thickness );
1340
1341                 /* The real underline thickness and position are
1342                  * updated once the whole line has been parsed */
1343                 i_ul_offset = __MAX( i_ul_offset, i_line_offset );
1344                 i_ul_thickness = __MAX( i_ul_thickness, i_line_thickness );
1345                 i_line_thickness = -1;
1346             }
1347         }
1348
1349         p_ch->p_glyph = ( FT_BitmapGlyph ) p_bitmaps->p_glyph;
1350         p_ch->p_outline = ( FT_BitmapGlyph ) p_bitmaps->p_outline;
1351         p_ch->p_shadow = ( FT_BitmapGlyph ) p_bitmaps->p_shadow;
1352         p_ch->b_in_karaoke = (p_paragraph->pi_karaoke_bar[ i_paragraph_index ] != 0);
1353
1354         p_ch->i_line_thickness = i_line_thickness;
1355         p_ch->i_line_offset = i_line_offset;
1356
1357         /* Compute bounding box for all glyphs */
1358         p_ch->bbox = p_bitmaps->glyph_bbox;
1359         if( p_bitmaps->p_outline )
1360             BBoxEnlarge( &p_ch->bbox, &p_bitmaps->outline_bbox );
1361         if( p_bitmaps->p_shadow )
1362             BBoxEnlarge( &p_ch->bbox, &p_bitmaps->shadow_bbox );
1363
1364         BBoxEnlarge( &p_line->bbox, &p_ch->bbox );
1365
1366         pen.x += p_bitmaps->i_x_advance;
1367         pen.y += p_bitmaps->i_y_advance;
1368
1369         /* Get max advance for grid mode */
1370         if( b_grid && i_font_max_advance_y == 0 && p_face )
1371         {
1372             i_font_max_advance_y = abs( FT_FLOOR( FT_MulFix( p_face->max_advance_height,
1373                                       p_face->size->metrics.y_scale ) ) );
1374         }
1375
1376         /* Keep track of blank/spaces in front/end of line */
1377         if( p_ch->p_glyph->bitmap.rows )
1378         {
1379             if( p_line->i_first_visible_char_index < 0 )
1380                 p_line->i_first_visible_char_index = p_line->i_character_count;
1381             p_line->i_last_visible_char_index = p_line->i_character_count;
1382         }
1383
1384         p_line->i_character_count++;
1385     }
1386
1387     /* Second pass for ruby layout */
1388     if( p_paragraph->pp_ruby )
1389     {
1390         const int i_ruby_baseline = p_line->bbox.yMax;
1391         const ruby_block_t *p_prevruby = NULL;
1392         for( int i = 0; i < p_line->i_character_count; ++i )
1393         {
1394             line_character_t *p_ch = &p_line->p_character[i];
1395             if( p_ch->p_ruby == p_prevruby || !p_ch->p_glyph )
1396                 continue;
1397             p_prevruby = p_ch->p_ruby;
1398             if( !p_ch->p_ruby )
1399                 continue;
1400             line_desc_t *p_rubyline = p_ch->p_ruby->p_laid;
1401             if( !p_rubyline )
1402                 continue;
1403
1404             int i_rubyadvance = (p_rubyline->bbox.xMax - p_rubyline->bbox.xMin);
1405             int i_rubyheight = (p_rubyline->bbox.yMax - p_rubyline->bbox.yMin);
1406             MoveLineTo( p_rubyline, p_ch->bbox.xMin, i_ruby_baseline + i_rubyheight );
1407             BBoxEnlarge( &p_line->bbox, &p_rubyline->bbox );
1408
1409             int i_count;
1410             int i_baseadvance = RubyBaseAdvance( p_line, i, &i_count );
1411             if( i_baseadvance < i_rubyadvance )
1412             {
1413                 IndentCharsFrom( p_line, i, i_count, (i_rubyadvance - i_baseadvance) / 2, 0 );
1414                 IndentCharsFrom( p_line, i + i_count, p_line->i_character_count - (i + i_count),
1415                                  (i_rubyadvance - i_baseadvance + 1), 0 );
1416             }
1417             else if( i_baseadvance > i_rubyadvance + 1 )
1418             {
1419                 ShiftLine( p_rubyline, (i_baseadvance - i_rubyadvance) / 2, 0 );
1420                 BBoxEnlarge( &p_line->bbox, &p_rubyline->bbox ); /* shouldn't be needed */
1421             }
1422         }
1423     }
1424
1425     p_line->i_width = __MAX( 0, p_line->bbox.xMax - p_line->bbox.xMin );
1426
1427     if( b_grid )
1428         p_line->i_height = i_font_max_advance_y;
1429     else
1430         p_line->i_height = __MAX( 0, p_line->bbox.yMax - p_line->bbox.yMin );
1431
1432     if( i_ul_thickness > 0 )
1433     {
1434         for( int i = 0; i < p_line->i_character_count; i++ )
1435         {
1436             line_character_t *ch = &p_line->p_character[i];
1437             if( ch->i_line_thickness < 0 )
1438             {
1439                 ch->i_line_offset    = i_ul_offset;
1440                 ch->i_line_thickness = i_ul_thickness;
1441             }
1442         }
1443     }
1444
1445     *pp_line = p_line;
1446     return VLC_SUCCESS;
1447 }
1448
1449 static inline void ReleaseGlyphBitMaps(glyph_bitmaps_t *p_bitmaps)
1450 {
1451     if( p_bitmaps->p_glyph )
1452         FT_Done_Glyph( p_bitmaps->p_glyph );
1453     if( p_bitmaps->p_outline )
1454         FT_Done_Glyph( p_bitmaps->p_outline );
1455 }
1456
1457 static inline bool IsWhitespaceAt( paragraph_t *p_paragraph, size_t i )
1458 {
1459     return ( p_paragraph->p_code_points[ i ] == ' '
1460 #ifdef HAVE_FRIBIDI
1461             || p_paragraph->p_types[ i ] == FRIBIDI_TYPE_WS
1462 #endif
1463     );
1464 }
1465
1466 static int LayoutParagraph( filter_t *p_filter, paragraph_t *p_paragraph,
1467                             unsigned i_max_width, unsigned i_max_advance_x,
1468                             bool b_grid, bool b_balance,
1469                             line_desc_t **pp_lines )
1470 {
1471     if( p_paragraph->i_size <= 0 || p_paragraph->i_runs_count <= 0 )
1472     {
1473         msg_Err( p_filter, "LayoutParagraph() invalid parameters. "
1474                  "Paragraph size: %d. Runs count %d",
1475                  p_paragraph->i_size, p_paragraph->i_runs_count );
1476         return VLC_EGENERIC;
1477     }
1478
1479     /*
1480      * Check max line width to allow for outline and shadow glyphs,
1481      * and any extra width caused by visual reordering
1482      */
1483     if( i_max_width <= i_max_advance_x )
1484     {
1485         msg_Err( p_filter, "LayoutParagraph(): Invalid max width" );
1486         return VLC_EGENERIC;
1487     }
1488
1489     i_max_width <<= 6;
1490     i_max_advance_x <<= 6;
1491
1492     int i_line_start = 0;
1493     FT_Pos i_width = 0;
1494     FT_Pos i_preferred_width = i_max_width;
1495     FT_Pos i_total_width = 0;
1496     FT_Pos i_last_space_width = 0;
1497     int i_last_space = -1;
1498     line_desc_t *p_first_line = NULL;
1499     line_desc_t **pp_line = &p_first_line;
1500
1501     for( int i = 0; i < p_paragraph->i_size; ++i )
1502     {
1503         if( !IsWhitespaceAt( p_paragraph, i ) || i != i_last_space + 1 )
1504             i_total_width += p_paragraph->p_glyph_bitmaps[ i ].i_x_advance;
1505         else
1506             i_last_space = i;
1507     }
1508     i_last_space = -1;
1509
1510     if( i_total_width == 0 )
1511     {
1512         for( int i=0; i < p_paragraph->i_size; ++i )
1513             ReleaseGlyphBitMaps( &p_paragraph->p_glyph_bitmaps[ i ] );
1514         return VLC_SUCCESS;
1515     }
1516
1517     if( b_balance )
1518     {
1519         int i_line_count = i_total_width / (i_max_width - i_max_advance_x) + 1;
1520         i_preferred_width = i_total_width / i_line_count;
1521     }
1522
1523     for( int i = 0; i <= p_paragraph->i_size; ++i )
1524     {
1525         if( i == p_paragraph->i_size )
1526         {
1527             if( i_line_start < i )
1528                 if( LayoutLine( p_filter, p_paragraph,
1529                                 i_line_start, i - 1, b_grid, pp_line ) )
1530                     goto error;
1531
1532             break;
1533         }
1534
1535         if( p_paragraph->pp_ruby &&
1536             p_paragraph->pp_ruby[i] &&
1537             p_paragraph->pp_ruby[i]->p_laid )
1538         {
1539             /* Just forward as non breakable */
1540             const ruby_block_t *p_rubyseq = p_paragraph->pp_ruby[i];
1541             int i_advance = 0;
1542             int i_advanceruby = p_rubyseq->p_laid->i_width;
1543             while( i + 1 < p_paragraph->i_size &&
1544                    p_rubyseq == p_paragraph->pp_ruby[i + 1] )
1545                 i_advance += p_paragraph->p_glyph_bitmaps[ i++ ].i_x_advance;
1546             /* Just forward as non breakable */
1547             i_width += (i_advance < i_advanceruby) ? i_advanceruby : i_advance;
1548             continue;
1549         }
1550
1551         if( IsWhitespaceAt( p_paragraph, i ) )
1552         {
1553             if( i_line_start == i )
1554             {
1555                 /*
1556                  * Free orphaned white space glyphs not belonging to any lines.
1557                  * At this point p_shadow points to either p_glyph or p_outline,
1558                  * so we should not free it explicitly.
1559                  */
1560                 ReleaseGlyphBitMaps( &p_paragraph->p_glyph_bitmaps[ i ] );
1561                 i_line_start = i + 1;
1562                 continue;
1563             }
1564
1565             if( i_last_space == i - 1 )
1566             {
1567                 p_paragraph->p_glyph_bitmaps[ i - 1 ].i_x_advance = 0;
1568                 i_last_space = i;
1569                 continue;
1570             }
1571
1572             i_last_space = i;
1573             i_last_space_width = i_width;
1574         }
1575
1576         const run_desc_t *p_run = &p_paragraph->p_runs[p_paragraph->pi_run_ids[i]];
1577         const int i_advance_x = p_paragraph->p_glyph_bitmaps[ i ].i_x_advance;
1578
1579         if( ( i_last_space_width + i_advance_x > i_preferred_width &&
1580               p_run->p_style->e_wrapinfo == STYLE_WRAP_DEFAULT )
1581             || i_width + i_advance_x > i_max_width )
1582         {
1583             if( i_line_start == i )
1584             {
1585                 /* If wrapping, algorithm would not end shifting lines down.
1586                  *  Not wrapping, that can't be rendered anymore. */
1587                 msg_Dbg( p_filter, "LayoutParagraph(): First glyph width in line exceeds maximum, skipping" );
1588                 for( ; i < p_paragraph->i_size; ++i )
1589                     ReleaseGlyphBitMaps( &p_paragraph->p_glyph_bitmaps[ i ] );
1590                 return VLC_SUCCESS;
1591             }
1592
1593             int i_newline_start;
1594             if( i_last_space > i_line_start && p_run->p_style->e_wrapinfo == STYLE_WRAP_DEFAULT )
1595                 i_newline_start = i_last_space; /* we break line on last space */
1596             else
1597                 i_newline_start = i; /* we break line on last char */
1598
1599             if( LayoutLine( p_filter, p_paragraph, i_line_start,
1600                             i_newline_start - 1, b_grid, pp_line ) )
1601                 goto error;
1602
1603             /* Handle early end of renderable content;
1604                We're over size and we can't break space */
1605             if( p_run->p_style->e_wrapinfo == STYLE_WRAP_NONE )
1606             {
1607                 for( ; i < p_paragraph->i_size; ++i )
1608                     ReleaseGlyphBitMaps( &p_paragraph->p_glyph_bitmaps[ i ] );
1609                 break;
1610             }
1611
1612             pp_line = &( *pp_line )->p_next;
1613
1614             /* If we created a line up to previous space, we only keep the difference for
1615                our current width since that split */
1616             if( i_newline_start == i_last_space )
1617             {
1618                 i_width = i_width - i_last_space_width;
1619                 if( i_newline_start + 1 < p_paragraph->i_size )
1620                     i_line_start = i_newline_start + 1;
1621                 else
1622                     i_line_start = i_newline_start; // == i
1623             }
1624             else
1625             {
1626                 i_width = 0;
1627                 i_line_start = i_newline_start;
1628             }
1629             i_last_space_width = 0;
1630         }
1631         i_width += i_advance_x;
1632     }
1633
1634     *pp_lines = p_first_line;
1635     return VLC_SUCCESS;
1636
1637 error:
1638     for( int i = i_line_start; i < p_paragraph->i_size; ++i )
1639         ReleaseGlyphBitMaps( &p_paragraph->p_glyph_bitmaps[ i ] );
1640     if( p_first_line )
1641         FreeLines( p_first_line );
1642     return VLC_EGENERIC;
1643 }
1644
1645 static paragraph_t * BuildParagraph( filter_t *p_filter,
1646                                      int i_size,
1647                                      const uni_char_t *p_uchars,
1648                                      text_style_t **pp_styles,
1649                                      ruby_block_t **pp_ruby,
1650                                      uint32_t *pi_k_dates,
1651                                      int i_runs_size,
1652                                      unsigned *pi_max_advance_x )
1653 {
1654     paragraph_t *p_paragraph = NewParagraph( p_filter, i_size,
1655                                 p_uchars,
1656                                 pp_styles,
1657                                 pp_ruby,
1658                                 pi_k_dates,
1659                                 i_runs_size );
1660     if( !p_paragraph )
1661         return NULL;
1662
1663 #ifdef HAVE_FRIBIDI
1664     if( AnalyzeParagraph( p_paragraph ) )
1665         goto error;
1666 #endif
1667
1668     if( ItemizeParagraph( p_filter, p_paragraph ) )
1669         goto error;
1670
1671 #if defined HAVE_HARFBUZZ
1672     if( ShapeParagraphHarfBuzz( p_filter, &p_paragraph ) )
1673         goto error;
1674
1675     if( LoadGlyphs( p_filter, p_paragraph, true, false, pi_max_advance_x ) )
1676         goto error;
1677
1678 #elif defined HAVE_FRIBIDI
1679     if( ShapeParagraphFriBidi( p_filter, p_paragraph ) )
1680         goto error;
1681     if( LoadGlyphs( p_filter, p_paragraph, false, true, pi_max_advance_x ) )
1682         goto error;
1683     if( RemoveZeroWidthCharacters( p_paragraph ) )
1684         goto error;
1685     if( ZeroNsmAdvance( p_paragraph ) )
1686         goto error;
1687 #else
1688     if( LoadGlyphs( p_filter, p_paragraph, false, true, pi_max_advance_x ) )
1689         goto error;
1690 #endif
1691
1692     return p_paragraph;
1693
1694 error:
1695     if( p_paragraph )
1696         FreeParagraph( p_paragraph );
1697
1698     return NULL;
1699 }
1700
1701 static int LayoutRubyText( filter_t *p_filter,
1702                            const uni_char_t *p_uchars,
1703                            int i_uchars,
1704                            text_style_t *p_style,
1705                            line_desc_t **pp_line )
1706 {
1707     unsigned int i_max_advance_x;
1708
1709     text_style_t **pp_styles = malloc(sizeof(*pp_styles) * i_uchars);
1710     for(int i=0;i<i_uchars;i++)
1711         pp_styles[i] = p_style;
1712
1713     paragraph_t *p_paragraph = BuildParagraph( p_filter, i_uchars,
1714                                                p_uchars, pp_styles,
1715                                                NULL, NULL, 1,
1716                                                &i_max_advance_x );
1717     if( !p_paragraph )
1718     {
1719         free( pp_styles );
1720         return VLC_EGENERIC;
1721     }
1722
1723     if( LayoutLine( p_filter, p_paragraph,
1724                     0, i_uchars - 1,
1725                     false, pp_line ) )
1726     {
1727         free( pp_styles );
1728         FreeParagraph( p_paragraph );
1729         return VLC_EGENERIC;
1730     }
1731
1732     FreeParagraph( p_paragraph );
1733     free( pp_styles );
1734
1735     return VLC_SUCCESS;
1736 }
1737
1738 int LayoutTextBlock( filter_t *p_filter,
1739                      const layout_text_block_t *p_textblock,
1740                      line_desc_t **pp_lines, FT_BBox *p_bbox,
1741                      int *pi_max_face_height )
1742 {
1743     line_desc_t *p_first_line = 0;
1744     line_desc_t **pp_line = &p_first_line;
1745     size_t i_paragraph_start = 0;
1746     unsigned i_total_height = 0;
1747     unsigned i_max_advance_x = 0;
1748     int i_max_face_height = 0;
1749
1750     /* Prepare ruby content */
1751     if( p_textblock->pp_ruby )
1752     {
1753         ruby_block_t *p_prev = NULL;
1754         for( size_t i=0; i<p_textblock->i_count; i++ )
1755         {
1756             if( p_textblock->pp_ruby[i] == p_prev )
1757                 continue;
1758             p_prev = p_textblock->pp_ruby[i];
1759             if( p_prev )
1760                 LayoutRubyText( p_filter, p_prev->p_uchars, p_prev->i_count,
1761                                 p_prev->p_style, &p_prev->p_laid );
1762         }
1763     }
1764     /* !Prepare ruby content */
1765
1766     for( size_t i = 0; i <= p_textblock->i_count; ++i )
1767     {
1768         if( i == p_textblock->i_count || p_textblock->p_uchars[ i ] == '\n' )
1769         {
1770             if( i_paragraph_start == i )
1771             {
1772                 i_paragraph_start = i + 1;
1773                 continue;
1774             }
1775
1776             paragraph_t *p_paragraph =
1777                     BuildParagraph( p_filter,
1778                                     i - i_paragraph_start,
1779                                     &p_textblock->p_uchars[i_paragraph_start],
1780                                     &p_textblock->pp_styles[i_paragraph_start],
1781                                     p_textblock->pp_ruby ?
1782                                     &p_textblock->pp_ruby[i_paragraph_start] : NULL,
1783                                     p_textblock->pi_k_durations ?
1784                                     &p_textblock->pi_k_durations[i_paragraph_start] : NULL,
1785                                     20, &i_max_advance_x );
1786             if( !p_paragraph )
1787             {
1788                 if( p_first_line ) FreeLines( p_first_line );
1789                 return VLC_ENOMEM;
1790             }
1791
1792             if( LayoutParagraph( p_filter, p_paragraph,
1793                                  p_textblock->i_max_width,
1794                                  i_max_advance_x,
1795                                  p_textblock->b_grid, p_textblock->b_balanced,
1796                                  pp_line ) )
1797             {
1798                 FreeParagraph( p_paragraph );
1799                 if( p_first_line ) FreeLines( p_first_line );
1800                 return VLC_EGENERIC;
1801             }
1802
1803             FreeParagraph( p_paragraph );
1804
1805             for( ; *pp_line; pp_line = &(*pp_line)->p_next )
1806             {
1807                 /* only cut at max i_max_height + 1 line due to
1808                  * approximate font sizing vs region size */
1809                 if( p_textblock->i_max_height > 0 && i_total_height > p_textblock->i_max_height )
1810                 {
1811                     i_total_height = p_textblock->i_max_height + 1;
1812                     line_desc_t *p_todelete = *pp_line;
1813                     while( p_todelete ) /* Drop extra lines */
1814                     {
1815                         line_desc_t *p_next = p_todelete->p_next;
1816                         FreeLine( p_todelete );
1817                         p_todelete = p_next;
1818                     }
1819                     *pp_line = NULL;
1820                     i = p_textblock->i_count + 1; /* force no more paragraphs */
1821                     break; /* ! no p_next ! */
1822                 }
1823                 else if( (*pp_line)->i_height > i_max_face_height )
1824                 {
1825                     i_max_face_height = (*pp_line)->i_height;
1826                 }
1827                 i_total_height += (*pp_line)->i_height;
1828             }
1829             i_paragraph_start = i + 1;
1830         }
1831     }
1832
1833     int i_base_line = 0;
1834     FT_BBox bbox;
1835     BBoxInit( &bbox );
1836
1837     for( line_desc_t *p_line = p_first_line; p_line; p_line = p_line->p_next )
1838     {
1839         p_line->i_base_line = i_base_line;
1840         p_line->bbox.yMin -= i_base_line;
1841         p_line->bbox.yMax -= i_base_line;
1842         BBoxEnlarge( &bbox, &p_line->bbox );
1843
1844         i_base_line += i_max_face_height;
1845     }
1846
1847     *pi_max_face_height = i_max_face_height;
1848     *pp_lines = p_first_line;
1849     *p_bbox = bbox;
1850     return VLC_SUCCESS;
1851 }
1852