modules/demux/mkv/matroska_segment_seeker.cpp

   1 /*****************************************************************************
   2  * matroska_segment.hpp : matroska demuxer
   3  *****************************************************************************
   4  * Copyright (C) 2016 VLC authors and VideoLAN
   5  * $Id$
   6  *
   7  * Authors: Filip Roséen <filip@videolabs.io>
   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 #include "matroska_segment_seeker.hpp"
  25 #include "matroska_segment.hpp"
  26 #include "demux.hpp"
  27 #include "Ebml_parser.hpp"
  28 #include "Ebml_dispatcher.hpp"
  29 #include "util.hpp"
  30 #include "stream_io_callback.hpp"
  31
  32 #include <sstream>
  33 #include <limits>
  34
  35 namespace {
  36     template<class It, class T>
  37     It greatest_lower_bound( It beg, It end, T const& value )
  38     {
  39         It it = std::upper_bound( beg, end, value );
  40         if( it != beg ) --it;
  41         return it;
  42     }
  43
  44     // std::prev and std::next exists in C++11, in order to avoid ambiguity due
  45     // to ADL and iterators being defined within namespace std, these two
  46     // function-names have been postfixed with an underscore.
  47
  48     template<class It> It prev_( It it ) { return --it; }
  49     template<class It> It next_( It it ) { return ++it; }
  50 }
  51
  52 namespace mkv {
  53
  54 SegmentSeeker::cluster_positions_t::iterator
  55 SegmentSeeker::add_cluster_position( fptr_t fpos )
  56 {
  57     cluster_positions_t::iterator insertion_point = std::upper_bound(
  58       _cluster_positions.begin(),
  59       _cluster_positions.end(),
  60       fpos
  61     );
  62
  63     return _cluster_positions.insert( insertion_point, fpos );
  64 }
  65
  66 SegmentSeeker::cluster_map_t::iterator
  67 SegmentSeeker::add_cluster( KaxCluster * const p_cluster )
  68 {
  69     Cluster cinfo = {
  70         /* fpos     */ p_cluster->GetElementPosition(),
  71         /* pts      */ vlc_tick_t( p_cluster->GlobalTimecode() / INT64_C( 1000 ) ),
  72         /* duration */ vlc_tick_t( -1 ),
  73         /* size     */ p_cluster->IsFiniteSize()
  74             ? p_cluster->GetEndPosition() - p_cluster->GetElementPosition()
  75             : UINT64_MAX
  76     };
  77
  78     add_cluster_position( cinfo.fpos );
  79
  80     cluster_map_t::iterator it = _clusters.lower_bound( cinfo.pts );
  81
  82     if( it != _clusters.end() && it->second.pts == cinfo.pts )
  83     {
  84         // cluster already known
  85     }
  86     else
  87     {
  88         it = _clusters.insert( cluster_map_t::value_type( cinfo.pts, cinfo ) ).first;
  89     }
  90
  91     // ------------------------------------------------------------------
  92     // IF we have two adjecent clusters, update duration where applicable
  93     // ------------------------------------------------------------------
  94
  95     struct Duration {
  96         static void fix( Cluster& prev, Cluster& next )
  97         {
  98             if( ( prev.fpos + prev.size) == next.fpos )
  99                 prev.duration = next.pts - prev.pts;
 100         }
 101     };
 102
 103     if( it != _clusters.begin() )
 104     {
 105         Duration::fix( prev_( it )->second, it->second );
 106     }
 107
 108     if( it != _clusters.end() && next_( it ) != _clusters.end() )
 109     {
 110         Duration::fix( it->second, next_( it )->second );
 111     }
 112
 113     return it;
 114 }
 115
 116 void
 117 SegmentSeeker::add_seekpoint( track_id_t track_id, Seekpoint sp )
 118 {
 119     seekpoints_t&  seekpoints = _tracks_seekpoints[ track_id ];
 120     seekpoints_t::iterator it = std::lower_bound( seekpoints.begin(), seekpoints.end(), sp );
 121
 122     if( it != seekpoints.end() && it->pts == sp.pts )
 123     {
 124         if (sp.trust_level <= it->trust_level)
 125             return;
 126
 127         *it = sp;
 128     }
 129     else
 130     {
 131         seekpoints.insert( it, sp );
 132     }
 133 }
 134
 135 SegmentSeeker::tracks_seekpoint_t
 136 SegmentSeeker::find_greatest_seekpoints_in_range( fptr_t start_fpos, vlc_tick_t end_pts, track_ids_t const& filter_tracks )
 137 {
 138     tracks_seekpoint_t tpoints;
 139
 140     for( tracks_seekpoints_t::const_iterator it = _tracks_seekpoints.begin(); it != _tracks_seekpoints.end(); ++it )
 141     {
 142         if ( std::find( filter_tracks.begin(), filter_tracks.end(), it->first ) == filter_tracks.end() )
 143             continue;
 144
 145         Seekpoint sp = get_first_seekpoint_around( end_pts, it->second );
 146
 147         if( sp.fpos < start_fpos )
 148             continue;
 149
 150         if( sp.pts > end_pts )
 151             continue;
 152
 153         tpoints.insert( tracks_seekpoint_t::value_type( it->first, sp ) );
 154     }
 155
 156     if (tpoints.empty())
 157     {
 158         // try a further pts
 159         for( tracks_seekpoints_t::const_iterator it = _tracks_seekpoints.begin(); it != _tracks_seekpoints.end(); ++it )
 160         {
 161             if ( std::find( filter_tracks.begin(), filter_tracks.end(), it->first ) == filter_tracks.end() )
 162                 continue;
 163
 164             Seekpoint sp = get_first_seekpoint_around( end_pts, it->second );
 165
 166             if( sp.fpos < start_fpos )
 167                 continue;
 168
 169             tpoints.insert( tracks_seekpoint_t::value_type( it->first, sp ) );
 170         }
 171     }
 172
 173     return tpoints;
 174 }
 175
 176 SegmentSeeker::Seekpoint
 177 SegmentSeeker::get_first_seekpoint_around( vlc_tick_t pts, seekpoints_t const& seekpoints,
 178                                            Seekpoint::TrustLevel trust_level )
 179 {
 180     if( seekpoints.empty() )
 181     {
 182         return Seekpoint();
 183     }
 184
 185     typedef seekpoints_t::const_iterator iterator;
 186
 187     Seekpoint const needle ( std::numeric_limits<fptr_t>::max(), pts );
 188
 189     iterator const it_begin  = seekpoints.begin();
 190     iterator const it_end    = seekpoints.end();
 191     iterator const it_middle = greatest_lower_bound( it_begin, it_end, needle );
 192
 193     iterator it_before;
 194
 195     // rewrind to _previous_ seekpoint with appropriate trust
 196     for( it_before = it_middle; it_before != it_begin; --it_before )
 197     {
 198         if( it_before->trust_level >= trust_level )
 199             return *it_before;
 200     }
 201     return *it_begin;
 202 }
 203
 204 SegmentSeeker::seekpoint_pair_t
 205 SegmentSeeker::get_seekpoints_around( vlc_tick_t pts, seekpoints_t const& seekpoints )
 206 {
 207     if( seekpoints.empty() )
 208     {
 209         return seekpoint_pair_t();
 210     }
 211
 212     typedef seekpoints_t::const_iterator iterator;
 213
 214     Seekpoint const needle ( std::numeric_limits<fptr_t>::max(), pts );
 215
 216     iterator const it_begin  = seekpoints.begin();
 217     iterator const it_end    = seekpoints.end();
 218     iterator const it_middle = greatest_lower_bound( it_begin, it_end, needle );
 219
 220     if ( it_middle != it_end && (*it_middle).pts > pts)
 221         // found nothing low enough, use the first one
 222         return seekpoint_pair_t( *it_begin, Seekpoint() );
 223
 224     iterator it_before = it_middle;
 225     iterator it_after = it_middle == it_end ? it_middle : next_( it_middle ) ;
 226
 227     return seekpoint_pair_t( *it_before,
 228       it_after == it_end ? Seekpoint() : *it_after
 229     );
 230 }
 231
 232 SegmentSeeker::seekpoint_pair_t
 233 SegmentSeeker::get_seekpoints_around( vlc_tick_t target_pts, track_ids_t const& priority_tracks )
 234 {
 235     seekpoint_pair_t points;
 236
 237     if( _tracks_seekpoints.empty() )
 238         return points;
 239
 240     { // locate the max/min seekpoints for priority_tracks //
 241
 242         typedef track_ids_t::const_iterator track_iterator;
 243
 244         track_iterator const begin = priority_tracks.begin();
 245         track_iterator const end   = priority_tracks.end();
 246
 247         for( track_iterator it = begin; it != end; ++it )
 248         {
 249             seekpoint_pair_t track_points = get_seekpoints_around( target_pts, _tracks_seekpoints[ *it ] );
 250
 251             if( it == begin ) {
 252                 points = track_points;
 253                 continue;
 254             }
 255
 256             if( track_points.first.trust_level > Seekpoint::DISABLED &&
 257                 points.first.fpos > track_points.first.fpos )
 258                 points.first = track_points.first;
 259
 260             if( track_points.second.trust_level > Seekpoint::DISABLED &&
 261                 points.second.fpos < track_points.second.fpos )
 262                 points.second = track_points.second;
 263         }
 264     }
 265
 266     { // check if we got a cluster which is closer to target_pts than the found cues //
 267
 268         cluster_map_t::iterator it = _clusters.lower_bound( target_pts );
 269
 270         if( it != _clusters.begin() && --it != _clusters.end() )
 271         {
 272             Cluster const& cluster = it->second;
 273
 274             if( cluster.fpos > points.first.fpos )
 275             {
 276                 points.first = Seekpoint( cluster.fpos, cluster.pts );
 277
 278                 // do we need to update the max point? //
 279
 280                 if( points.second.fpos < points.first.fpos )
 281                     points.second = Seekpoint( cluster.fpos + cluster.size, cluster.pts + cluster.duration );
 282             }
 283         }
 284     }
 285
 286     return points;
 287 }
 288
 289 SegmentSeeker::tracks_seekpoint_t
 290 SegmentSeeker::get_seekpoints( matroska_segment_c& ms, vlc_tick_t target_pts,
 291                                track_ids_t const& priority_tracks, track_ids_t const& filter_tracks )
 292 {
 293     struct contains_all_of_t {
 294         bool operator()( tracks_seekpoint_t const& haystack, track_ids_t const& track_ids )
 295         {
 296             for( track_ids_t::const_iterator it = track_ids.begin(); it != track_ids.end(); ++it ) {
 297                 if( haystack.find( *it ) == haystack.end() )
 298                     return false;
 299             }
 300
 301             return true;
 302         }
 303     };
 304
 305     for( vlc_tick_t needle_pts = target_pts; ; )
 306     {
 307         seekpoint_pair_t seekpoints = get_seekpoints_around( needle_pts, priority_tracks );
 308
 309         Seekpoint const& start = seekpoints.first;
 310         Seekpoint const& end   = seekpoints.second;
 311
 312         if ( start.fpos == std::numeric_limits<fptr_t>::max() )
 313             return tracks_seekpoint_t();
 314
 315         if ( end.fpos != std::numeric_limits<fptr_t>::max() || !ms.b_cues )
 316             // do not read the whole (infinite?) file to get seek indexes
 317             index_range( ms, Range( start.fpos, end.fpos ), needle_pts );
 318
 319         tracks_seekpoint_t tpoints = find_greatest_seekpoints_in_range( start.fpos, target_pts, filter_tracks );
 320
 321         if( contains_all_of_t() ( tpoints, priority_tracks ) )
 322             return tpoints;
 323
 324         needle_pts = start.pts - 1;
 325     }
 326
 327     vlc_assert_unreachable();
 328 }
 329
 330 void
 331 SegmentSeeker::index_range( matroska_segment_c& ms, Range search_area, vlc_tick_t max_pts )
 332 {
 333     ranges_t areas_to_search = get_search_areas( search_area.start, search_area.end );
 334
 335     for( ranges_t::const_iterator range_it = areas_to_search.begin(); range_it != areas_to_search.end(); ++range_it )
 336         index_unsearched_range( ms, *range_it, max_pts );
 337 }
 338
 339 void
 340 SegmentSeeker::index_unsearched_range( matroska_segment_c& ms, Range search_area, vlc_tick_t max_pts )
 341 {
 342     mkv_jump_to( ms, search_area.start );
 343
 344     search_area.start = ms.es.I_O().getFilePointer();
 345
 346     fptr_t  block_pos = search_area.start;
 347     vlc_tick_t block_pts;
 348
 349     while( block_pos < search_area.end )
 350     {
 351         KaxBlock * block;
 352         KaxSimpleBlock * simpleblock;
 353
 354         bool     b_key_picture;
 355         bool     b_discardable_picture;
 356         int64_t  i_block_duration;
 357         track_id_t track_id;
 358
 359         if( ms.BlockGet( block, simpleblock, &b_key_picture, &b_discardable_picture, &i_block_duration ) )
 360             break;
 361
 362         KaxInternalBlock& internal_block = simpleblock
 363             ? static_cast<KaxInternalBlock&>( *simpleblock )
 364             : static_cast<KaxInternalBlock&>( *block );
 365
 366         block_pos = internal_block.GetElementPosition();
 367         block_pts = internal_block.GlobalTimecode() / 1000;
 368         track_id  = internal_block.TrackNum();
 369
 370         bool const b_valid_track = ms.FindTrackByBlock( block, simpleblock ) != NULL;
 371
 372         delete block;
 373
 374         if( b_valid_track )
 375         {
 376             if( b_key_picture )
 377                 add_seekpoint( track_id, Seekpoint( block_pos, block_pts ) );
 378
 379             if( max_pts < block_pts )
 380                 break;
 381         }
 382     }
 383
 384     search_area.end = ms.es.I_O().getFilePointer();
 385
 386     mark_range_as_searched( search_area );
 387 }
 388
 389 void
 390 SegmentSeeker::mark_range_as_searched( Range data )
 391 {
 392     /* TODO: this is utterly ugly, we should do the insertion in-place */
 393
 394     _ranges_searched.insert( std::upper_bound( _ranges_searched.begin(), _ranges_searched.end(), data ), data );
 395
 396     {
 397         ranges_t merged;
 398
 399         for( ranges_t::iterator it = _ranges_searched.begin(); it != _ranges_searched.end(); ++it )
 400         {
 401             if( merged.size() )
 402             {
 403                 Range& last_entry = *merged.rbegin();
 404
 405                 if( last_entry.end+1 >= it->start && last_entry.end < it->end )
 406                 {
 407                     last_entry.end = it->end;
 408                     continue;
 409                 }
 410
 411                 if( it->start >= last_entry.start && it->end <= last_entry.end )
 412                 {
 413                     last_entry.end = std::max( last_entry.end, it->end );
 414                     continue;
 415                 }
 416             }
 417
 418             merged.push_back( *it );
 419         }
 420
 421         _ranges_searched = merged;
 422     }
 423 }
 424
 425
 426 SegmentSeeker::ranges_t
 427 SegmentSeeker::get_search_areas( fptr_t start, fptr_t end ) const
 428 {
 429     ranges_t areas_to_search;
 430     Range needle ( start, end );
 431
 432     ranges_t::const_iterator it = greatest_lower_bound( _ranges_searched.begin(), _ranges_searched.end(), needle );
 433
 434     for( ; it != _ranges_searched.end() && needle.start < needle.end; ++it )
 435     {
 436         if( needle.start < it->start )
 437         {
 438             areas_to_search.push_back( Range( needle.start, it->start ) );
 439         }
 440
 441         if( needle.start <= it->end )
 442             needle.start = it->end + 1;
 443     }
 444
 445     needle.start = std::max( needle.start, start );
 446     if( it == _ranges_searched.end() && needle.start < needle.end )
 447     {
 448         areas_to_search.push_back( needle );
 449     }
 450
 451     return areas_to_search;
 452 }
 453
 454 void
 455 SegmentSeeker::mkv_jump_to( matroska_segment_c& ms, fptr_t fpos )
 456 {
 457     fptr_t i_cluster_pos = -1;
 458
 459     if ( fpos != std::numeric_limits<SegmentSeeker::fptr_t>::max() )
 460     {
 461         ms.cluster = NULL;
 462         if ( !_cluster_positions.empty() )
 463         {
 464             cluster_positions_t::iterator cluster_it = greatest_lower_bound(
 465               _cluster_positions.begin(), _cluster_positions.end(), fpos
 466             );
 467
 468             ms.es.I_O().setFilePointer( *cluster_it );
 469             ms.ep.reconstruct( &ms.es, ms.segment, &ms.sys.demuxer );
 470         }
 471
 472         while( ms.cluster == NULL || (
 473               ms.cluster->IsFiniteSize() && ms.cluster->GetEndPosition() < fpos ) )
 474         {
 475             if( !( ms.cluster = static_cast<KaxCluster*>( ms.ep.Get() ) ) )
 476             {
 477                 msg_Err( &ms.sys.demuxer, "unable to read KaxCluster during seek, giving up" );
 478                 return;
 479             }
 480
 481             i_cluster_pos = ms.cluster->GetElementPosition();
 482
 483             add_cluster_position( i_cluster_pos );
 484
 485             mark_range_as_searched( Range( i_cluster_pos, ms.es.I_O().getFilePointer() ) );
 486         }
 487     }
 488     else if (ms.cluster != NULL)
 489     {
 490         // make sure we start reading after the Cluster start
 491         ms.es.I_O().setFilePointer(ms.cluster->GetDataStart());
 492     }
 493
 494     ms.ep.Down();
 495
 496     /* read until cluster/timecode to initialize cluster */
 497
 498     while( EbmlElement * el = ms.ep.Get() )
 499     {
 500         if( MKV_CHECKED_PTR_DECL( p_tc, KaxClusterTimecode, el ) )
 501         {
 502             p_tc->ReadData( ms.es.I_O(), SCOPE_ALL_DATA );
 503             ms.cluster->InitTimecode( static_cast<uint64>( *p_tc ), ms.i_timescale );
 504             add_cluster(ms.cluster);
 505             break;
 506         }
 507         else if( MKV_CHECKED_PTR_DECL( p_tc, EbmlCrc32, el ) )
 508         {
 509             p_tc->ReadData( ms.es.I_O(), SCOPE_ALL_DATA ); /* avoid a skip that may fail */
 510         }
 511     }
 512
 513     /* TODO: add error handling; what if we never get a KaxCluster and/or KaxClusterTimecode? */
 514
 515     mark_range_as_searched( Range( i_cluster_pos, ms.es.I_O().getFilePointer() ) );
 516
 517     /* jump to desired position */
 518
 519     if ( fpos != std::numeric_limits<SegmentSeeker::fptr_t>::max() )
 520         ms.es.I_O().setFilePointer( fpos );
 521 }
 522
 523 } // namespace