modules/spu/subsdelay.c

   1 /*****************************************************************************
   2  * subsdelay.c : Subsdelay plugin for vlc
   3  *****************************************************************************
   4  * Copyright © 2011 VideoLAN
   5  * $Id$
   6  *
   7  * Authors: Yuval Tze <yuvaltze@gmail.com>
   8  *
   9  * This program is free software; you can redistribute it and/or modify it
  10  * under the terms of the GNU Lesser General Public License as published by
  11  * the Free Software Foundation; either version 2.1 of the License, or
  12  * (at your option) any later version.
  13  *
  14  * This program is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  17  * GNU Lesser General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU Lesser General Public License
  20  * along with this program; if not, write to the Free Software Foundation,
  21  * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
  22  *****************************************************************************/
  23
  24 /*****************************************************************************
  25  * Preamble
  26  *****************************************************************************/
  27
  28 #ifdef HAVE_CONFIG_H
  29 #include "config.h"
  30 #endif
  31
  32 #include <vlc_common.h>
  33 #include <vlc_plugin.h>
  34 #include <vlc_filter.h>
  35 #include <vlc_subpicture.h>
  36 #include <vlc_es.h>
  37 #include <stdlib.h>
  38
  39 /*****************************************************************************
  40  * Local constants
  41  *****************************************************************************/
  42
  43 /* descriptions */
  44
  45 #define SUBSDELAY_HELP N_("Change subtitle delay")
  46
  47 #define MODE_TEXT N_( "Delay calculation mode" )
  48 #define MODE_LONGTEXT N_( \
  49     "Absolute delay - add absolute delay to each subtitle. " \
  50     "Relative to source delay - multiply subtitle delay. " \
  51     "Relative to source content - determine subtitle delay from its content (text)." )
  52
  53 #define FACTOR_TEXT N_( "Calculation factor" )
  54 #define FACTOR_LONGTEXT N_( "Calculation factor. " \
  55     "In Absolute delay mode the factor represents seconds.")
  56
  57 #define OVERLAP_TEXT N_( "Maximum overlapping subtitles" )
  58 #define OVERLAP_LONGTEXT N_( "Maximum number of subtitles allowed at the same time." )
  59
  60 #define MIN_ALPHA_TEXT N_( "Minimum alpha value" )
  61 #define MIN_ALPHA_LONGTEXT N_( \
  62     "Alpha value of the earliest subtitle, where 0 is fully transparent and 255 is fully opaque." )
  63
  64 #define MIN_STOPS_INTERVAL_TEXT N_( "Interval between two disappearances" )
  65 #define MIN_STOPS_INTERVAL_LONGTEXT N_( \
  66     "Minimum time (in milliseconds) that subtitle should stay after its predecessor has disappeared " \
  67     "(subtitle delay will be extended to meet this requirement)." )
  68
  69 #define MIN_STOP_START_INTERVAL_TEXT N_( "Interval between disappearance and appearance" )
  70 #define MIN_STOP_START_INTERVAL_LONGTEXT N_( \
  71     "Minimum time (in milliseconds) between subtitle disappearance and newer subtitle appearance " \
  72     "(earlier subtitle delay will be extended to fill the gap)." )
  73
  74 #define MIN_START_STOP_INTERVAL_TEXT N_( "Interval between appearance and disappearance" )
  75 #define MIN_START_STOP_INTERVAL_LONGTEXT N_( \
  76     "Minimum time (in milliseconds) that subtitle should stay after newer subtitle has appeared " \
  77     "(earlier subtitle delay will be shortened to avoid the overlap)." )
  78
  79 static const int pi_mode_values[] = { 0, 1, 2 };
  80 static const char * const ppsz_mode_descriptions[] = { N_( "Absolute delay" ), N_( "Relative to source delay" ), N_(
  81         "Relative to source content" ) };
  82
  83 /* parameters */
  84
  85 #define CFG_PREFIX "subsdelay-"
  86
  87 #define CFG_MODE                    CFG_PREFIX "mode"
  88 #define CFG_FACTOR                  CFG_PREFIX "factor"
  89 #define CFG_OVERLAP                 CFG_PREFIX "overlap"
  90
  91 #define CFG_MIN_ALPHA               CFG_PREFIX "min-alpha"
  92 #define CFG_MIN_STOPS_INTERVAL      CFG_PREFIX "min-stops"
  93 #define CFG_MIN_STOP_START_INTERVAL CFG_PREFIX "min-stop-start"
  94 #define CFG_MIN_START_STOP_INTERVAL CFG_PREFIX "min-start-stop"
  95
  96
  97 /* max subtitles handled on the heap */
  98 #define SUBSDELAY_MAX_ENTRIES 16
  99
 100 /* factor convert macros */
 101 #define INT_FACTOR_BASE                  1000
 102 #define FLOAT_FACTOR_TO_INT_FACTOR( x )  (int)( ( x ) * INT_FACTOR_BASE )
 103 #define INT_FACTOR_TO_MICROSEC( x )      ( ( x ) * ( CLOCK_FREQ / INT_FACTOR_BASE ) )
 104 #define INT_FACTOR_TO_RANK_FACTOR( x )   ( x )
 105 #define MILLISEC_TO_MICROSEC( x )        ( ( x ) * 1000 )
 106
 107
 108 #define SUBSDELAY_MODE_ABSOLUTE                0
 109 #define SUBSDELAY_MODE_RELATIVE_SOURCE_DELAY   1
 110 #define SUBSDELAY_MODE_RELATIVE_SOURCE_CONTENT 2
 111
 112
 113 /*****************************************************************************
 114  * subsdelay_heap_entry_t: Heap entry
 115  *****************************************************************************/
 116
 117 typedef struct subsdelay_heap_entry_t subsdelay_heap_entry_t;
 118
 119 struct subsdelay_heap_entry_t
 120 {
 121     subpicture_t *p_subpic; /* local subtitle */
 122
 123     subpicture_t *p_source; /* subtitle source */
 124
 125     filter_t *p_filter; /* assigned subsdelay filter */
 126
 127     subsdelay_heap_entry_t *p_next; /* next entry */
 128
 129     bool b_update_stop; /* new stop value should be calculated */
 130
 131     bool b_update_ephemer; /* actual stop value is unknown */
 132
 133     bool b_update_position; /* subtitle position should be updated */
 134
 135     bool b_check_empty; /* subtitle content should be checked */
 136
 137     vlc_tick_t i_new_stop; /* new stop value */
 138
 139     /* last region data*/
 140
 141     int i_last_region_x;
 142
 143     int i_last_region_y;
 144
 145     int i_last_region_align;
 146
 147     bool b_last_region_saved;
 148 };
 149
 150 /*****************************************************************************
 151  * subsdelay_heap_t: Heap
 152  *****************************************************************************/
 153
 154 typedef struct
 155 {
 156     vlc_mutex_t lock; /* heap global lock */
 157
 158     subsdelay_heap_entry_t *p_list[SUBSDELAY_MAX_ENTRIES]; /* subtitles entries array */
 159
 160     subsdelay_heap_entry_t *p_head; /* subtitles entries linked list */
 161
 162     int i_count; /* subtitles count */
 163
 164 } subsdelay_heap_t;
 165
 166
 167
 168 /*****************************************************************************
 169 * filter_sys_t: Subsdelay filter descriptor
 170  *****************************************************************************/
 171
 172 typedef struct
 173 {
 174     int i_mode; /* delay calculation mode */
 175
 176     int i_factor; /* calculation factor */
 177
 178     int i_overlap; /* max overlap */
 179
 180     int i_min_alpha; /* oldest subtitle alpha value */
 181
 182     int64_t i_min_stops_interval;
 183
 184     int64_t i_min_stop_start_interval;
 185
 186     int64_t i_min_start_stop_interval;
 187
 188     subsdelay_heap_t heap; /* subpictures list */
 189 } filter_sys_t;
 190
 191
 192 /*****************************************************************************
 193  * Filter functions
 194  *****************************************************************************/
 195
 196 static int SubsdelayCreate( vlc_object_t * );
 197
 198 static void SubsdelayDestroy( vlc_object_t * );
 199
 200 static subpicture_t * SubsdelayFilter( filter_t *p_filter, subpicture_t* p_subpic );
 201
 202 static int SubsdelayCallback( vlc_object_t *p_this, char const *psz_var, vlc_value_t oldval, vlc_value_t newval,
 203         void *p_data );
 204
 205 /*****************************************************************************
 206  * Helper functions
 207  *****************************************************************************/
 208
 209 static void SubsdelayEnforceDelayRules( filter_t *p_filter );
 210
 211 static int64_t SubsdelayEstimateDelay( filter_t *p_filter, subsdelay_heap_entry_t *p_entry );
 212
 213 static void SubsdelayRecalculateDelays( filter_t *p_filter );
 214
 215 static int SubsdelayCalculateAlpha( filter_t *p_filter, int i_overlapping, int i_source_alpha );
 216
 217 static int SubsdelayGetTextRank( char *psz_text );
 218
 219 static bool SubsdelayIsTextEmpty( const text_segment_t* p_segment );
 220
 221 /*****************************************************************************
 222  * Subpicture functions
 223  *****************************************************************************/
 224
 225 static int SubpicValidateWrapper( subpicture_t *p_subpic, bool has_src_changed, const video_format_t *p_fmt_src,
 226                                   bool has_dst_changed, const video_format_t *p_fmt_dst, vlc_tick_t i_ts );
 227
 228 static void SubpicUpdateWrapper( subpicture_t *p_subpic, const video_format_t *p_fmt_src,
 229                                   const video_format_t *p_fmt_dst, vlc_tick_t i_ts );
 230
 231 static void SubpicDestroyWrapper( subpicture_t *p_subpic );
 232
 233 static void SubpicLocalUpdate( subpicture_t* p_subpic, vlc_tick_t i_ts );
 234
 235 static bool SubpicIsEmpty( subpicture_t* p_subpic );
 236
 237 static subpicture_t *SubpicClone( subpicture_t *p_source, subpicture_updater_t *updater );
 238
 239 static void SubpicDestroyClone( subpicture_t *p_subpic );
 240
 241 /*****************************************************************************
 242  * Heap functions
 243  *****************************************************************************/
 244
 245 static void SubsdelayHeapInit( subsdelay_heap_t *p_heap );
 246
 247 static void SubsdelayHeapDestroy( subsdelay_heap_t *p_heap );
 248
 249 static subsdelay_heap_entry_t *SubsdelayHeapPush( subsdelay_heap_t *p_heap, subpicture_t *p_subpic, filter_t *p_filter );
 250
 251 static void SubsdelayHeapRemove( subsdelay_heap_t *p_heap, subsdelay_heap_entry_t *p_entry );
 252
 253 static void SubsdelayRebuildList( subsdelay_heap_t *p_heap );
 254
 255 static void SubsdelayHeapLock( subsdelay_heap_t *p_heap );
 256
 257 static void SubsdelayHeapUnlock( subsdelay_heap_t *p_heap );
 258
 259 static subsdelay_heap_entry_t * SubsdelayEntryCreate( subpicture_t *p_subpic, filter_t *p_filter );
 260
 261 static void SubsdelayEntryDestroy( subsdelay_heap_entry_t *p_entry );
 262
 263 /* heap / entries special functionality */
 264
 265 static int SubsdelayHeapCountOverlap( subsdelay_heap_t *p_heap, subsdelay_heap_entry_t *p_entry, vlc_tick_t i_date );
 266
 267 static void SubsdelayEntryNewStopValueUpdated( subsdelay_heap_entry_t *p_entry );
 268
 269 /*****************************************************************************
 270  * Module descriptor
 271  *****************************************************************************/
 272
 273 vlc_module_begin()
 274         set_shortname( N_("Subsdelay") )
 275         set_description( N_("Subtitle delay") )
 276         set_help( SUBSDELAY_HELP )
 277         set_capability( "sub filter", 0 )
 278         set_callbacks( SubsdelayCreate, SubsdelayDestroy )
 279         set_category( CAT_VIDEO )
 280         set_subcategory( SUBCAT_VIDEO_SUBPIC )
 281
 282         add_integer( CFG_MODE, 1, MODE_TEXT, MODE_LONGTEXT, false )
 283         change_integer_list( pi_mode_values, ppsz_mode_descriptions )
 284
 285         add_float_with_range( CFG_FACTOR, 2, 0, 20, FACTOR_TEXT, FACTOR_LONGTEXT, false )
 286
 287         add_integer_with_range( CFG_OVERLAP, 3, 1, 4, OVERLAP_TEXT, OVERLAP_LONGTEXT, false )
 288
 289         add_integer_with_range( CFG_MIN_ALPHA, 70, 0, 255, MIN_ALPHA_TEXT, MIN_ALPHA_LONGTEXT, false )
 290
 291         set_section( N_("Overlap fix"), NULL )
 292
 293         add_integer( CFG_MIN_STOPS_INTERVAL, 1000, MIN_STOPS_INTERVAL_TEXT, MIN_STOPS_INTERVAL_LONGTEXT, false )
 294
 295         add_integer( CFG_MIN_START_STOP_INTERVAL, 1000, MIN_START_STOP_INTERVAL_TEXT,
 296                      MIN_START_STOP_INTERVAL_LONGTEXT, false )
 297
 298         add_integer( CFG_MIN_STOP_START_INTERVAL, 1000, MIN_STOP_START_INTERVAL_TEXT,
 299                      MIN_STOP_START_INTERVAL_LONGTEXT, false )
 300
 301     vlc_module_end ()
 302
 303 static const char * const ppsz_filter_options[] = { "mode", "factor", "overlap", NULL };
 304
 305 /*****************************************************************************
 306  * SubsdelayCreate: Create subsdelay filter
 307  *****************************************************************************/
 308 static int SubsdelayCreate( vlc_object_t *p_this )
 309 {
 310     filter_t *p_filter = (filter_t *) p_this;
 311     filter_sys_t *p_sys;
 312
 313     /* allocate structure */
 314     p_sys = (filter_sys_t*) malloc( sizeof(filter_sys_t) );
 315
 316     if( !p_sys )
 317     {
 318         return VLC_ENOMEM;
 319     }
 320
 321     /* init parameters */
 322
 323     p_sys->i_mode = var_CreateGetIntegerCommand( p_filter, CFG_MODE );
 324     var_AddCallback( p_filter, CFG_MODE, SubsdelayCallback, p_sys );
 325
 326     p_sys->i_factor = FLOAT_FACTOR_TO_INT_FACTOR( var_CreateGetFloatCommand( p_filter, CFG_FACTOR ) );
 327     var_AddCallback( p_filter, CFG_FACTOR, SubsdelayCallback, p_sys );
 328
 329     p_sys->i_overlap = var_CreateGetIntegerCommand( p_filter, CFG_OVERLAP );
 330     var_AddCallback( p_filter, CFG_OVERLAP, SubsdelayCallback, p_sys );
 331
 332     p_sys->i_min_alpha = var_CreateGetIntegerCommand( p_filter, CFG_MIN_ALPHA );
 333     var_AddCallback( p_filter, CFG_MIN_ALPHA, SubsdelayCallback, p_sys );
 334
 335     p_sys->i_min_stops_interval
 336             = MILLISEC_TO_MICROSEC( var_CreateGetIntegerCommand( p_filter, CFG_MIN_STOPS_INTERVAL ) );
 337     var_AddCallback( p_filter, CFG_MIN_STOPS_INTERVAL, SubsdelayCallback, p_sys );
 338
 339     p_sys->i_min_stop_start_interval
 340             = MILLISEC_TO_MICROSEC( var_CreateGetIntegerCommand( p_filter, CFG_MIN_STOP_START_INTERVAL ) );
 341     var_AddCallback( p_filter, CFG_MIN_STOP_START_INTERVAL, SubsdelayCallback, p_sys );
 342
 343     p_sys->i_min_start_stop_interval
 344             = MILLISEC_TO_MICROSEC( var_CreateGetIntegerCommand( p_filter, CFG_MIN_START_STOP_INTERVAL ) );
 345     var_AddCallback( p_filter, CFG_MIN_START_STOP_INTERVAL, SubsdelayCallback, p_sys );
 346
 347     p_filter->p_sys = p_sys;
 348     p_filter->pf_sub_filter = SubsdelayFilter;
 349
 350     config_ChainParse( p_filter, CFG_PREFIX, ppsz_filter_options, p_filter->p_cfg );
 351
 352     SubsdelayHeapInit( &p_sys->heap );
 353
 354     return VLC_SUCCESS;
 355 }
 356
 357 /*****************************************************************************
 358  * SubsdelayDestroy: Destroy subsdelay filter
 359  *****************************************************************************/
 360 static void SubsdelayDestroy( vlc_object_t *p_this )
 361 {
 362     filter_t *p_filter = (filter_t *) p_this;
 363     filter_sys_t *p_sys = p_filter->p_sys;
 364
 365     SubsdelayHeapDestroy( &p_sys->heap );
 366
 367     /* destroy parameters */
 368
 369     var_DelCallback( p_filter, CFG_MODE, SubsdelayCallback, p_sys );
 370     var_Destroy( p_filter, CFG_MODE );
 371
 372     var_DelCallback( p_filter, CFG_FACTOR, SubsdelayCallback, p_sys );
 373     var_Destroy( p_filter, CFG_FACTOR );
 374
 375     var_DelCallback( p_filter, CFG_OVERLAP, SubsdelayCallback, p_sys );
 376     var_Destroy( p_filter, CFG_OVERLAP );
 377
 378     var_DelCallback( p_filter, CFG_MIN_ALPHA, SubsdelayCallback, p_sys );
 379     var_Destroy( p_filter, CFG_MIN_ALPHA );
 380
 381     var_DelCallback( p_filter, CFG_MIN_STOPS_INTERVAL, SubsdelayCallback, p_sys );
 382     var_Destroy( p_filter, CFG_MIN_STOPS_INTERVAL );
 383
 384     var_DelCallback( p_filter, CFG_MIN_STOP_START_INTERVAL, SubsdelayCallback, p_sys );
 385     var_Destroy( p_filter, CFG_MIN_STOP_START_INTERVAL );
 386
 387     var_DelCallback( p_filter, CFG_MIN_START_STOP_INTERVAL, SubsdelayCallback, p_sys );
 388     var_Destroy( p_filter, CFG_MIN_START_STOP_INTERVAL );
 389
 390     free( p_sys );
 391 }
 392
 393 /*****************************************************************************
 394  * SubsdelayFilter: Filter new subpicture
 395  *****************************************************************************/
 396 static subpicture_t * SubsdelayFilter( filter_t *p_filter, subpicture_t* p_subpic )
 397 {
 398     subsdelay_heap_t *p_heap;
 399     subsdelay_heap_entry_t *p_entry;
 400
 401     if( !p_subpic->b_subtitle )
 402     {
 403         return p_subpic;
 404     }
 405
 406     if( SubpicIsEmpty( p_subpic ) )
 407     {
 408         /* empty subtitles usually helps terminate ephemer subtitles, but this filter calculates the stop value anyway,
 409            so this subtitle can be dropped */
 410
 411         subpicture_Delete( p_subpic );
 412
 413         return NULL;
 414     }
 415
 416     filter_sys_t *p_sys = p_filter->p_sys;
 417     p_heap = &p_sys->heap;
 418
 419     /* add subpicture to the heap */
 420
 421     SubsdelayHeapLock( p_heap );
 422
 423     p_entry = SubsdelayHeapPush( p_heap, p_subpic, p_filter );
 424     if( !p_entry )
 425     {
 426         SubsdelayHeapUnlock( p_heap );
 427
 428         msg_Err(p_filter, "Can't add subpicture to the heap");
 429
 430         return p_subpic;
 431     }
 432
 433     p_subpic = p_entry->p_subpic; /* get the local subpic */
 434
 435     if( p_subpic->b_ephemer )
 436     {
 437         /* set a relativly long delay in hope that the next subtitle
 438            will arrive in this time and the real delay could be determined */
 439
 440         p_subpic->i_stop = p_subpic->i_start + 20000000; /* start + 20 sec */
 441         p_subpic->b_ephemer = false;
 442     }
 443
 444
 445     SubsdelayEnforceDelayRules( p_filter );
 446
 447     SubsdelayHeapUnlock( p_heap );
 448
 449     return p_subpic;
 450 }
 451
 452 /*****************************************************************************
 453  * SubsdelayCallback: Subsdelay parameters callback
 454  *****************************************************************************/
 455 static int SubsdelayCallback( vlc_object_t *p_this, char const *psz_var, vlc_value_t oldval, vlc_value_t newval,
 456         void *p_data )
 457 {
 458     filter_sys_t *p_sys = (filter_sys_t *) p_data;
 459
 460     VLC_UNUSED( oldval );
 461
 462     SubsdelayHeapLock( &p_sys->heap );
 463
 464     if( !strcmp( psz_var, CFG_MODE ) )
 465     {
 466         p_sys->i_mode = newval.i_int;
 467     }
 468     else if( !strcmp( psz_var, CFG_FACTOR ) )
 469     {
 470         p_sys->i_factor = FLOAT_FACTOR_TO_INT_FACTOR( newval.f_float );
 471     }
 472     else if( !strcmp( psz_var, CFG_OVERLAP ) )
 473     {
 474         p_sys->i_overlap = newval.i_int;
 475     }
 476     else if( !strcmp( psz_var, CFG_MIN_ALPHA ) )
 477     {
 478         p_sys->i_min_alpha = newval.i_int;
 479     }
 480     else if( !strcmp( psz_var, CFG_MIN_STOPS_INTERVAL ) )
 481     {
 482         p_sys->i_min_stops_interval = MILLISEC_TO_MICROSEC( newval.i_int );
 483     }
 484     else if( !strcmp( psz_var, CFG_MIN_STOP_START_INTERVAL ) )
 485     {
 486         p_sys->i_min_stop_start_interval = MILLISEC_TO_MICROSEC( newval.i_int );
 487     }
 488     else if( !strcmp( psz_var, CFG_MIN_START_STOP_INTERVAL ) )
 489     {
 490         p_sys->i_min_start_stop_interval = MILLISEC_TO_MICROSEC( newval.i_int );
 491     }
 492     else
 493     {
 494         SubsdelayHeapUnlock( &p_sys->heap );
 495         return VLC_ENOVAR;
 496     }
 497
 498     SubsdelayRecalculateDelays( (filter_t *) p_this );
 499
 500     SubsdelayHeapUnlock( &p_sys->heap );
 501     return VLC_SUCCESS;
 502 }
 503
 504 /*****************************************************************************
 505  * SubsdelayHeapInit: Initialize heap
 506  *****************************************************************************/
 507 static void SubsdelayHeapInit( subsdelay_heap_t *p_heap )
 508 {
 509     p_heap->i_count = 0;
 510     p_heap->p_head = NULL;
 511
 512     vlc_mutex_init( &p_heap->lock );
 513 }
 514
 515 /*****************************************************************************
 516  * SubsdelayHeapDestroy: Destroy the heap and remove its entries
 517  *****************************************************************************/
 518 static void SubsdelayHeapDestroy( subsdelay_heap_t *p_heap )
 519 {
 520     SubsdelayHeapLock( p_heap );
 521
 522     for( subsdelay_heap_entry_t *p_entry = p_heap->p_head;
 523          p_entry != NULL; p_entry = p_entry->p_next )
 524     {
 525         p_entry->p_subpic->i_stop = p_entry->p_source->i_stop;
 526
 527         p_entry->p_filter = NULL;
 528     }
 529
 530     SubsdelayHeapUnlock( p_heap );
 531
 532     vlc_mutex_destroy( &p_heap->lock );
 533 }
 534
 535 /*****************************************************************************
 536  * SubsdelayHeapPush: Add new subpicture to the heap
 537  *****************************************************************************/
 538 static subsdelay_heap_entry_t *SubsdelayHeapPush( subsdelay_heap_t *p_heap, subpicture_t *p_subpic, filter_t *p_filter )
 539 {
 540     subsdelay_heap_entry_t *p_last, *p_new_entry;
 541
 542     if( p_heap->i_count >= SUBSDELAY_MAX_ENTRIES )
 543     {
 544         return NULL; /* the heap is full */
 545     }
 546
 547     p_new_entry = SubsdelayEntryCreate( p_subpic, p_filter );
 548
 549     if( !p_new_entry )
 550     {
 551         return NULL;
 552     }
 553
 554
 555     p_last = NULL;
 556
 557     for( subsdelay_heap_entry_t *p_entry = p_heap->p_head; p_entry != NULL;
 558          p_entry = p_entry->p_next )
 559     {
 560         if( p_entry->p_source->i_start > p_subpic->i_start )
 561         {
 562             /* the new entry should be inserted before p_entry */
 563             break;
 564         }
 565
 566         p_last = p_entry;
 567     }
 568
 569     if( p_last )
 570     {
 571         p_new_entry->p_next = p_last->p_next;
 572         p_last->p_next = p_new_entry;
 573
 574
 575         if( p_last->b_update_ephemer )
 576         {
 577             /* the correct stop value can be determined */
 578
 579             p_last->p_source->i_stop = p_new_entry->p_source->i_start;
 580             p_last->b_update_ephemer = false;
 581         }
 582     }
 583     else
 584     {
 585         p_new_entry->p_next = p_heap->p_head;
 586         p_heap->p_head = p_new_entry;
 587     }
 588
 589
 590     /* rebuild list */
 591
 592     SubsdelayRebuildList( p_heap );
 593
 594     return p_new_entry;
 595 }
 596
 597 /*****************************************************************************
 598  * SubsdelayHeapRemove: Remove entry
 599  *****************************************************************************/
 600 static void SubsdelayHeapRemove( subsdelay_heap_t *p_heap, subsdelay_heap_entry_t *p_entry )
 601 {
 602     subsdelay_heap_entry_t *p_prev;
 603
 604     p_prev = NULL;
 605
 606     for( subsdelay_heap_entry_t *p_curr = p_heap->p_head; p_curr != NULL;
 607          p_curr = p_curr->p_next )
 608     {
 609         if( p_curr == p_entry )
 610         {
 611             break;
 612         }
 613
 614         p_prev = p_curr;
 615     }
 616
 617     if( p_prev )
 618     {
 619         p_prev->p_next = p_entry->p_next;
 620     }
 621     else
 622     {
 623         p_heap->p_head = p_entry->p_next;
 624     }
 625
 626     p_entry->p_filter = NULL;
 627
 628     SubsdelayRebuildList( p_heap );
 629 }
 630
 631
 632 static void SubsdelayRebuildList( subsdelay_heap_t *p_heap )
 633 {
 634     int i_index;
 635
 636     i_index = 0;
 637     for( subsdelay_heap_entry_t *p_curr = p_heap->p_head; p_curr != NULL;
 638          p_curr = p_curr->p_next )
 639     {
 640         p_heap->p_list[i_index] = p_curr;
 641         i_index++;
 642     }
 643
 644     p_heap->i_count = i_index;
 645 }
 646
 647 /*****************************************************************************
 648  * SubsdelayHeapLock: Lock the heap
 649  *****************************************************************************/
 650 static void SubsdelayHeapLock( subsdelay_heap_t *p_heap )
 651 {
 652     vlc_mutex_lock( &p_heap->lock );
 653 }
 654
 655 /*****************************************************************************
 656  * SubsdelayHeapUnlock: Unlock the heap
 657  *****************************************************************************/
 658 static void SubsdelayHeapUnlock( subsdelay_heap_t *p_heap )
 659 {
 660     vlc_mutex_unlock( &p_heap->lock );
 661 }
 662
 663
 664 /*****************************************************************************
 665  * SubsdelayHeapCreateEntry: Create new entry
 666  *****************************************************************************/
 667 static subsdelay_heap_entry_t * SubsdelayEntryCreate( subpicture_t *p_source, filter_t *p_filter )
 668 {
 669     subsdelay_heap_entry_t *p_entry;
 670
 671     subpicture_t *p_new_subpic;
 672
 673     subpicture_updater_t updater;
 674
 675     /* allocate structure */
 676
 677     p_entry = (subsdelay_heap_entry_t *) malloc( sizeof( subsdelay_heap_entry_t ) );
 678
 679     if( !p_entry )
 680     {
 681         return NULL;
 682     }
 683
 684     /* initialize local updater */
 685
 686     updater.p_sys = p_entry;
 687     updater.pf_validate = SubpicValidateWrapper;
 688     updater.pf_update = SubpicUpdateWrapper;
 689     updater.pf_destroy = SubpicDestroyWrapper;
 690
 691     /* create new subpic */
 692
 693     p_new_subpic = SubpicClone( p_source,  &updater );
 694
 695     if( !p_new_subpic )
 696     {
 697         free( p_entry );
 698         return NULL;
 699     }
 700
 701     /* initialize entry */
 702
 703     p_entry->p_subpic = p_new_subpic;
 704     p_entry->p_source = p_source;
 705     p_entry->p_filter = p_filter;
 706     p_entry->p_next = NULL;
 707     p_entry->b_update_stop = true;
 708     p_entry->b_update_ephemer = p_source->b_ephemer;
 709     p_entry->b_update_position = true;
 710     p_entry->b_check_empty = true;
 711     p_entry->i_new_stop = p_source->i_stop;
 712     p_entry->b_last_region_saved = false;
 713     p_entry->i_last_region_x = 0;
 714     p_entry->i_last_region_y = 0;
 715     p_entry->i_last_region_align = 0;
 716
 717     return p_entry;
 718 }
 719
 720 /*****************************************************************************
 721  * SubsdelayEntryDestroy: Destroy entry
 722  *****************************************************************************/
 723 static void SubsdelayEntryDestroy( subsdelay_heap_entry_t *p_entry )
 724 {
 725     SubpicDestroyClone( p_entry->p_source );
 726     free( p_entry );
 727 }
 728
 729 /*****************************************************************************
 730  * SubsdelayHeapCountOverlap: Count overlapping subtitles at a given time
 731  *****************************************************************************/
 732 static int SubsdelayHeapCountOverlap( subsdelay_heap_t *p_heap, subsdelay_heap_entry_t *p_entry, vlc_tick_t i_date )
 733 {
 734     int i_overlaps;
 735
 736     VLC_UNUSED( p_heap );
 737
 738     i_overlaps = 0;
 739
 740     for( subsdelay_heap_entry_t *p_curr = p_entry->p_next; p_curr != NULL;
 741          p_curr = p_curr->p_next )
 742     {
 743         if( p_curr->p_source->i_start > i_date )
 744         {
 745             break;
 746         }
 747
 748         if( !p_curr->b_check_empty ) /* subtitle was checked, and it's not empty */
 749         {
 750             i_overlaps++;
 751         }
 752     }
 753
 754     return i_overlaps;
 755 }
 756
 757 /*****************************************************************************
 758  * SubsdelayEntryNewStopValueUpdated: Update source stop value after the new
 759  *     stop value was changed
 760  *****************************************************************************/
 761 static void SubsdelayEntryNewStopValueUpdated( subsdelay_heap_entry_t *p_entry )
 762 {
 763     if( !p_entry->b_update_stop )
 764     {
 765         p_entry->p_subpic->i_stop = p_entry->i_new_stop - VLC_TICK_FROM_MS(100); /* 0.1 sec less */
 766     }
 767 }
 768
 769 /*****************************************************************************
 770  * SubsdelayEnforceDelayRules: Update subtitles delay after adding new
 771  *     subtitle or changing subtitle stop value
 772  *****************************************************************************/
 773 static void SubsdelayEnforceDelayRules( filter_t *p_filter )
 774 {
 775     subsdelay_heap_entry_t ** p_list;
 776     int i_count, i_overlap;
 777     vlc_tick_t i_offset;
 778     int64_t i_min_stops_interval;
 779     int64_t i_min_stop_start_interval;
 780     int64_t i_min_start_stop_interval;
 781
 782     filter_sys_t *p_sys = p_filter->p_sys;
 783
 784     p_list = p_sys->heap.p_list;
 785     i_count = p_sys->heap.i_count;
 786
 787     i_overlap = p_sys->i_overlap;
 788     i_min_stops_interval = p_sys->i_min_stops_interval;
 789     i_min_stop_start_interval = p_sys->i_min_stop_start_interval;
 790     i_min_start_stop_interval = p_sys->i_min_start_stop_interval;
 791
 792     /* step 1 - enforce min stops interval rule (extend delays) */
 793
 794     /* look for:
 795     [subtitle 1 ..............]
 796            [subtitle 2 ..............]
 797                               |<-MinStopsInterval->|
 798
 799      * and extend newer subtitle:
 800     [subtitle 1 ..............]
 801            [subtitle 2 ............................]
 802                               |<-MinStopsInterval->|
 803     */
 804
 805     for( int i = 0; i < i_count - 1; i++ )
 806     {
 807         p_list[i + 1]->i_new_stop = __MAX( p_list[i + 1]->i_new_stop,
 808                 p_list[i]->i_new_stop + i_min_stops_interval );
 809     }
 810
 811     /* step 2 - enforce min stop start interval rule (extend delays) */
 812
 813     /* look for:
 814     [subtitle 1 .........]
 815                                    [subtitle 2 ....]
 816           |<-MinStopStartInterval->|
 817
 818      * and fill the gap:
 819     [subtitle 1 ..................]
 820                                    [subtitle 2 ....]
 821           |<-MinStopStartInterval->|
 822     */
 823
 824     for( int i = 0; i < i_count; i++ )
 825     {
 826         for( int j = i + 1; j < __MIN( i_count, i + 1 + i_overlap ); j++ )
 827         {
 828             i_offset = p_list[j]->p_source->i_start - p_list[i]->i_new_stop;
 829
 830             if( i_offset <= 0 )
 831             {
 832                 continue;
 833             }
 834
 835             if( i_offset < i_min_stop_start_interval )
 836             {
 837                 p_list[i]->i_new_stop = p_list[j]->p_source->i_start;
 838             }
 839
 840             break;
 841         }
 842     }
 843
 844     /* step 3 - enforce min start stop interval rule (shorten delays) */
 845
 846     /* look for:
 847     [subtitle 1 ............]
 848                     [subtitle 2 ....................]
 849                     |<-MinStartStopInterval->|
 850
 851      * and remove the overlapping part:
 852     [subtitle 1 ...]
 853                     [subtitle 2 ....................]
 854                     |<-MinStartStopInterval->|
 855     */
 856
 857
 858     for( int i = 0; i < i_count; i++ )
 859     {
 860         for( int j = i + 1; j < __MIN( i_count, i + 1 + i_overlap ); j++ )
 861         {
 862             i_offset = p_list[i]->i_new_stop - p_list[j]->p_source->i_start;
 863
 864             if( i_offset <= 0 )
 865             {
 866                 break;
 867             }
 868
 869             if( i_offset < i_min_start_stop_interval )
 870             {
 871                 p_list[i]->i_new_stop = p_list[j]->p_source->i_start;
 872                 break;
 873             }
 874         }
 875     }
 876
 877     /* step 4 - enforce max overlapping rule (shorten delays)*/
 878
 879     /* look for: (overlap = 2)
 880     [subtitle 1 ..............]
 881              [subtitle 2 ..............]
 882                       [subtitle 3 ..............]
 883
 884
 885      * and cut older subtitle:
 886     [subtitle 1 .....]
 887              [subtitle 2 ..............]
 888                       [subtitle 3 ..............]
 889     */
 890
 891     for( int i = 0; i < i_count - i_overlap; i++ )
 892     {
 893         if( p_list[i]->i_new_stop > p_list[i + i_overlap]->p_source->i_start )
 894         {
 895             p_list[i]->i_new_stop = p_list[i + i_overlap]->p_source->i_start;
 896         }
 897     }
 898
 899     /* finally - update all */
 900
 901     for( int i = 0; i < i_count; i++ )
 902     {
 903         SubsdelayEntryNewStopValueUpdated( p_list[i] );
 904     }
 905 }
 906
 907 /*****************************************************************************
 908  * SubsdelayRecalculateDelays: Recalculate subtitles delay after changing
 909  *     one of the filter's parameters
 910  *****************************************************************************/
 911 static void SubsdelayRecalculateDelays( filter_t *p_filter )
 912 {
 913     filter_sys_t *p_sys = p_filter->p_sys;
 914     for( subsdelay_heap_entry_t *p_curr = p_sys->heap.p_head;
 915          p_curr != NULL; p_curr = p_curr->p_next )
 916     {
 917         if( !p_curr->b_update_ephemer )
 918         {
 919             p_curr->i_new_stop = p_curr->p_source->i_start + SubsdelayEstimateDelay( p_filter, p_curr );
 920             p_curr->b_update_stop = false;
 921         }
 922     }
 923
 924     SubsdelayEnforceDelayRules( p_filter );
 925 }
 926
 927 /*****************************************************************************
 928  * SubpicValidateWrapper: Subpicture validate callback wrapper
 929  *****************************************************************************/
 930 static int SubpicValidateWrapper( subpicture_t *p_subpic, bool has_src_changed, const video_format_t *p_fmt_src,
 931                                   bool has_dst_changed, const video_format_t *p_fmt_dst, vlc_tick_t i_ts )
 932 {
 933     subsdelay_heap_entry_t *p_entry;
 934     vlc_tick_t i_new_ts;
 935     int i_result = VLC_SUCCESS;
 936
 937     p_entry = p_subpic->updater.p_sys;
 938     if( !p_entry )
 939     {
 940         return VLC_SUCCESS;
 941     }
 942
 943     /* call source validate */
 944     if( p_entry->p_source->updater.pf_validate )
 945     {
 946         i_new_ts = p_entry->p_source->i_start +
 947                    ( (double)( p_entry->p_source->i_stop - p_entry->p_source->i_start ) * ( i_ts - p_entry->p_source->i_start ) ) /
 948                    ( p_entry->i_new_stop - p_entry->p_source->i_start );
 949
 950         i_result = p_entry->p_source->updater.pf_validate( p_entry->p_source, has_src_changed, p_fmt_src,
 951                                                         has_dst_changed, p_fmt_dst, i_new_ts );
 952     }
 953
 954
 955     p_entry->b_last_region_saved = false;
 956
 957     if( p_subpic->p_region )
 958     {
 959         /* save copy */
 960         p_entry->i_last_region_x = p_subpic->p_region->i_x;
 961         p_entry->i_last_region_y = p_subpic->p_region->i_y;
 962         p_entry->i_last_region_align = p_subpic->p_region->i_align;
 963
 964         p_entry->b_last_region_saved = true;
 965     }
 966
 967     if( !i_result )
 968     {
 969         /* subpic update isn't necessary, so local update should be called here */
 970         SubpicLocalUpdate( p_subpic, i_ts );
 971     }
 972
 973     return i_result;
 974 }
 975
 976 /*****************************************************************************
 977  * SubpicUpdateWrapper: Subpicture update callback wrapper
 978  *****************************************************************************/
 979 static void SubpicUpdateWrapper( subpicture_t *p_subpic, const video_format_t *p_fmt_src,
 980                                   const video_format_t *p_fmt_dst, vlc_tick_t i_ts )
 981 {
 982     subsdelay_heap_entry_t *p_entry;
 983     vlc_tick_t i_new_ts;
 984
 985     p_entry = p_subpic->updater.p_sys;
 986     if( !p_entry )
 987     {
 988         return;
 989     }
 990
 991     /* call source update */
 992     if( p_entry->p_source->updater.pf_update )
 993     {
 994         i_new_ts = p_entry->p_source->i_start +
 995                    ( (double)( p_entry->p_source->i_stop - p_entry->p_source->i_start ) * ( i_ts - p_entry->p_source->i_start ) ) /
 996                    ( p_entry->i_new_stop - p_entry->p_source->i_start );
 997
 998         p_entry->p_source->p_region = p_entry->p_subpic->p_region;
 999
1000         p_entry->p_source->updater.pf_update( p_entry->p_source, p_fmt_src, p_fmt_dst, i_new_ts );
1001
1002         p_entry->p_subpic->p_region = p_entry->p_source->p_region;
1003     }
1004
1005     SubpicLocalUpdate( p_subpic, i_ts );
1006 }
1007
1008 /*****************************************************************************
1009  * SubpicDestroyCallback: Subpicture destroy callback
1010  *****************************************************************************/
1011 static void SubpicDestroyWrapper( subpicture_t *p_subpic )
1012 {
1013     subsdelay_heap_entry_t *p_entry;
1014     subsdelay_heap_t *p_heap;
1015
1016     p_entry = p_subpic->updater.p_sys;
1017
1018     if( !p_entry )
1019     {
1020         return;
1021     }
1022
1023     if( p_entry->p_filter )
1024     {
1025         filter_sys_t *p_sys = p_entry->p_filter->p_sys;
1026         p_heap = &p_sys->heap;
1027
1028         SubsdelayHeapLock( p_heap );
1029         SubsdelayHeapRemove( p_heap, p_entry );
1030         SubsdelayHeapUnlock( p_heap );
1031     }
1032
1033     SubsdelayEntryDestroy( p_entry );
1034 }
1035
1036 /*****************************************************************************
1037  * SubpicLocalUpdate: rewrite some of the subpicture parameters
1038  *****************************************************************************/
1039 static void SubpicLocalUpdate( subpicture_t* p_subpic, vlc_tick_t i_ts )
1040 {
1041     subsdelay_heap_entry_t *p_entry;
1042     subsdelay_heap_t *p_heap;
1043     filter_t *p_filter;
1044
1045     int i_overlapping;
1046
1047     p_entry = p_subpic->updater.p_sys;
1048     if( !p_entry || !p_entry->p_filter )
1049     {
1050         return;
1051     }
1052
1053     p_filter = p_entry->p_filter;
1054     filter_sys_t *p_sys = p_filter->p_sys;
1055     p_heap = &p_sys->heap;
1056
1057     SubsdelayHeapLock( p_heap );
1058
1059     if( p_entry->b_check_empty && p_subpic->p_region )
1060     {
1061         //FIXME: What if there is more than one segment?
1062         if( SubsdelayIsTextEmpty( p_subpic->p_region->p_text ) )
1063         {
1064             /* remove empty subtitle */
1065
1066             p_subpic->b_ephemer = false;
1067             p_subpic->i_stop = p_subpic->i_start;
1068
1069             SubsdelayHeapRemove( p_heap, p_entry );
1070
1071             SubsdelayHeapUnlock( p_heap );
1072
1073             return;
1074         }
1075
1076         p_entry->b_check_empty = false;
1077     }
1078
1079     if( p_entry->b_update_stop && !p_entry->b_update_ephemer )
1080     {
1081         p_entry->i_new_stop = p_entry->p_source->i_start + SubsdelayEstimateDelay( p_filter, p_entry );
1082         p_entry->b_update_stop = false;
1083
1084         SubsdelayEnforceDelayRules( p_filter );
1085     }
1086
1087     i_overlapping = SubsdelayHeapCountOverlap( p_heap, p_entry, i_ts );
1088
1089     p_subpic->i_alpha = SubsdelayCalculateAlpha( p_filter, i_overlapping, p_entry->p_source->i_alpha );
1090
1091     if( p_entry->b_update_position )
1092     {
1093         p_subpic->b_absolute = false;
1094
1095         if( p_subpic->p_region )
1096         {
1097             p_subpic->p_region->i_x = 0;
1098             p_subpic->p_region->i_y = 10;
1099             p_subpic->p_region->i_align = ( p_subpic->p_region->i_align & ( ~SUBPICTURE_ALIGN_MASK ) )
1100                     | SUBPICTURE_ALIGN_BOTTOM;
1101         }
1102
1103         p_entry->b_update_position = false;
1104     }
1105     else if( p_entry->b_last_region_saved )
1106     {
1107         p_subpic->b_absolute = true;
1108
1109         if( p_subpic->p_region )
1110         {
1111             p_subpic->p_region->i_x = p_entry->i_last_region_x;
1112             p_subpic->p_region->i_y = p_entry->i_last_region_y;
1113             p_subpic->p_region->i_align = p_entry->i_last_region_align;
1114         }
1115     }
1116
1117     SubsdelayHeapUnlock( p_heap );
1118 }
1119
1120 /*****************************************************************************
1121  * SubpicIsEmpty: subpic region contains empty string
1122  *****************************************************************************/
1123 static bool SubpicIsEmpty( subpicture_t* p_subpic )
1124 {
1125     return ( p_subpic->p_region && ( SubsdelayIsTextEmpty( p_subpic->p_region->p_text ) ) );
1126 }
1127
1128 /*****************************************************************************
1129  * SubpicClone: Clone subpicture (shallow copy)
1130  *****************************************************************************/
1131 static subpicture_t *SubpicClone( subpicture_t *p_source, subpicture_updater_t *updater )
1132 {
1133     subpicture_t *p_subpic;
1134     subpicture_updater_t subpic_updater;
1135     subpicture_private_t *p_subpic_private;
1136
1137     p_subpic = subpicture_New( updater );
1138
1139     if( !p_subpic )
1140     {
1141         return NULL;
1142     }
1143
1144     /* save private members */
1145     subpic_updater = p_subpic->updater;
1146     p_subpic_private = p_subpic->p_private;
1147
1148     /* copy the entire struct */
1149     memcpy( p_subpic, p_source, sizeof( subpicture_t ) );
1150
1151     /* restore private members */
1152     p_subpic->updater = subpic_updater;
1153     p_subpic->p_private = p_subpic_private;
1154
1155     return p_subpic;
1156 }
1157
1158 /*****************************************************************************
1159  * SubpicDestroyClone: destroy cloned subpicture (shared references will not
1160  *     be destroyed)
1161  *****************************************************************************/
1162 static void SubpicDestroyClone( subpicture_t *p_subpic )
1163 {
1164     p_subpic->p_region = NULL; /* don't destroy region */
1165     subpicture_Delete( p_subpic );
1166 }
1167
1168 /*****************************************************************************
1169  * SubsdelayEstimateDelay: Calculate new subtitle delay according to its
1170  *     content and the calculation mode
1171  *****************************************************************************/
1172 static int64_t SubsdelayEstimateDelay( filter_t *p_filter, subsdelay_heap_entry_t *p_entry )
1173 {
1174     int i_mode;
1175     int i_factor;
1176     int i_rank;
1177
1178     filter_sys_t *p_sys = p_filter->p_sys;
1179
1180     i_mode = p_sys->i_mode;
1181     i_factor = p_sys->i_factor;
1182
1183     if( i_mode == SUBSDELAY_MODE_ABSOLUTE )
1184     {
1185         return ( p_entry->p_source->i_stop - p_entry->p_source->i_start + INT_FACTOR_TO_MICROSEC( i_factor ) );
1186     }
1187
1188     if( i_mode == SUBSDELAY_MODE_RELATIVE_SOURCE_CONTENT )
1189     {
1190         if( p_entry->p_subpic && p_entry->p_subpic->p_region && ( p_entry->p_subpic->p_region->p_text ) )
1191         {
1192             //FIXME: We only use a single segment here
1193             i_rank = SubsdelayGetTextRank( p_entry->p_subpic->p_region->p_text->psz_text );
1194
1195             return ( i_rank * INT_FACTOR_TO_RANK_FACTOR( i_factor ) );
1196         }
1197
1198         /* content is unavailable, calculation mode should be based on source delay */
1199         i_mode = SUBSDELAY_MODE_RELATIVE_SOURCE_DELAY;
1200     }
1201
1202     if( i_mode == SUBSDELAY_MODE_RELATIVE_SOURCE_DELAY )
1203     {
1204         return ( ( i_factor * ( p_entry->p_source->i_stop - p_entry->p_source->i_start ) ) / INT_FACTOR_BASE );
1205     }
1206
1207     return 10000000; /* 10 sec */
1208 }
1209
1210 /*****************************************************************************
1211  * SubsdelayCalculateAlpha: Calculate subtitle alpha according to source alpha
1212  *     value and number of overlapping subtitles
1213  *****************************************************************************/
1214 static int SubsdelayCalculateAlpha( filter_t *p_filter, int i_overlapping, int i_source_alpha )
1215 {
1216     int i_new_alpha;
1217     int i_min_alpha;
1218
1219     filter_sys_t *p_sys = p_filter->p_sys;
1220
1221     i_min_alpha = p_sys->i_min_alpha;
1222
1223     if( i_overlapping > p_sys->i_overlap - 1)
1224     {
1225         i_overlapping = p_sys->i_overlap - 1;
1226     }
1227
1228     switch ( p_sys->i_overlap )
1229     {
1230     case 1:
1231         i_new_alpha = 255;
1232         break;
1233
1234     case 2:
1235         i_new_alpha = 255 - i_overlapping * ( 255 - i_min_alpha );
1236         break;
1237
1238     case 3:
1239         i_new_alpha = 255 - i_overlapping * ( 255 - i_min_alpha ) / 2;
1240         break;
1241
1242     default:
1243         i_new_alpha = 255 - i_overlapping * ( 255 - i_min_alpha ) / 3;
1244         break;
1245     }
1246
1247     return ( i_source_alpha * i_new_alpha ) / 255;
1248 }
1249
1250 /*****************************************************************************
1251  * SubsdelayGetWordRank: Calculate single word rank according to its length
1252  *****************************************************************************/
1253 static int SubsdelayGetWordRank( int i_length )
1254 {
1255     /* p_rank[0] = p_rank[1] = p_rank[2] = 300;
1256     for( i = 3; i < 20; i++ ) p_rank[i] = (int) ( 1.1 * p_rank[i - 1] ); */
1257
1258     static const int p_rank[20] = { 300, 300, 300, 330, 363, 399, 438, 481, 529, 581,
1259                                     639, 702, 772, 849, 933, 1026, 1128, 1240, 1364, 1500 };
1260
1261     if( i_length < 1 )
1262     {
1263         return 0;
1264     }
1265
1266     if( i_length > 20 )
1267     {
1268         i_length = 20;
1269     }
1270
1271     return p_rank[i_length - 1];
1272 }
1273
1274 /*****************************************************************************
1275  * SubsdelayGetTextRank: Calculate text rank
1276  *****************************************************************************/
1277 static int SubsdelayGetTextRank( char *psz_text )
1278 {
1279     bool b_skip_esc;
1280     bool b_skip_tag;
1281     char c;
1282
1283     int i, i_word_length, i_rank;
1284
1285     i = 0;
1286     i_word_length = 0;
1287     i_rank = 0;
1288
1289     b_skip_esc = false;
1290     b_skip_tag = false;
1291
1292     while ( psz_text[i] != '\0' )
1293     {
1294         c = psz_text[i];
1295         i++;
1296
1297         if( c == '\\' && !b_skip_esc )
1298         {
1299             b_skip_esc = true;
1300             continue;
1301         }
1302
1303         if( psz_text[i] == '<' )
1304         {
1305             b_skip_tag = true;
1306             continue;
1307         }
1308
1309         if( !b_skip_esc && !b_skip_tag )
1310         {
1311             if( c == ' ' || c == ',' || c == '.' || c == '-' || c == '?' || c == '!' ) /* common delimiters */
1312             {
1313                 if( i_word_length > 0 )
1314                 {
1315                     i_rank += SubsdelayGetWordRank( i_word_length );
1316                 }
1317
1318                 i_word_length = 0;
1319             }
1320             else
1321             {
1322                 i_word_length++;
1323             }
1324         }
1325
1326         b_skip_esc = false;
1327
1328         if( c == '>' )
1329         {
1330             b_skip_tag = false;
1331         }
1332
1333     }
1334
1335     if( i_word_length > 0 )
1336     {
1337         i_rank += SubsdelayGetWordRank( i_word_length );
1338     }
1339
1340     return i_rank;
1341 }
1342
1343 /*****************************************************************************
1344  * SubsdelayIsTextEmpty: Check if the text contains spaces only
1345  *****************************************************************************/
1346 static bool SubsdelayIsTextEmpty( const text_segment_t *p_segment )
1347 {
1348     while ( p_segment )
1349     {
1350         if ( strlen( p_segment->psz_text ) > 0 )
1351         {
1352             size_t offset = strspn( p_segment->psz_text, " " );
1353             if ( p_segment->psz_text[offset] )
1354                 return false;
1355         }
1356         p_segment = p_segment->p_next;
1357     }
1358
1359     return true;
1360 }