1 /*****************************************************************************
2 * oggseek.c : ogg seeking functions for ogg demuxer vlc
3 *****************************************************************************
4 * Copyright (C) 2008 - 2010 Gabriel Finch <salsaman@gmail.com>
6 * Authors: Gabriel Finch <salsaman@gmail.com>
7 * adapted from: http://lives.svn.sourceforge.net/viewvc/lives/trunk/lives-plugins
8 * /plugins/decoders/ogg_theora_decoder.c
10 * This program is free software; you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation; either version 2 of the License, or
13 * (at your option) any later version.
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, write to the Free Software
22 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
23 *****************************************************************************/
25 /*****************************************************************************
27 *****************************************************************************/
33 #include <vlc_common.h>
34 #include <vlc_demux.h>
42 /************************************************************
44 *************************************************************/
46 /* free all entries in index list */
48 void oggseek_index_entries_free ( demux_index_entry_t
*idx
)
50 demux_index_entry_t
*idx_next
;
54 idx_next
= idx
->p_next
;
61 /* unlink and free idx. If idx is head of list, return new head */
63 static demux_index_entry_t
*index_entry_delete( demux_index_entry_t
*idx
)
65 demux_index_entry_t
*xidx
= idx
;
67 if ( idx
->p_prev
!= NULL
) idx
->p_prev
->p_next
= idx
->p_next
;
68 else xidx
= idx
->p_next
;
70 if ( idx
->p_next
!= NULL
) idx
->p_next
->p_prev
= idx
->p_prev
;
77 /* internal function to create a new list member */
79 static demux_index_entry_t
*index_entry_new( void )
81 demux_index_entry_t
*idx
= (demux_index_entry_t
*)malloc( sizeof( demux_index_entry_t
) );
82 idx
->p_next
= idx
->p_prev
= NULL
;
83 idx
->i_pagepos_end
= -1;
89 /* add a theora entry to our list; format is highest granulepos -> page offset of
92 const demux_index_entry_t
*oggseek_theora_index_entry_add ( logical_stream_t
*p_stream
,
96 /* add or update entry for keyframe */
97 demux_index_entry_t
*idx
;
98 demux_index_entry_t
*oidx
;
99 demux_index_entry_t
*last_idx
= NULL
;
106 if ( p_stream
== NULL
) return NULL
;
108 oidx
= idx
= p_stream
->idx
;
110 i_tkframe
= i_granule
>> p_stream
->i_granule_shift
;
111 i_tframe
= i_tkframe
+ i_granule
- ( i_tkframe
<< p_stream
->i_granule_shift
);
113 if ( i_tkframe
< 1 ) return NULL
;
117 demux_index_entry_t
*ie
= index_entry_new();
118 ie
->i_value
= i_granule
;
119 ie
->i_pagepos
= i_pagepos
;
125 while ( idx
!= NULL
)
127 i_gpos
= idx
->i_value
;
129 i_kframe
= i_gpos
>> p_stream
->i_granule_shift
;
130 if ( i_kframe
> i_tframe
) break;
132 if ( i_kframe
== i_tkframe
)
134 /* entry exists, update it if applicable, and return it */
135 i_frame
= i_kframe
+ i_gpos
- ( i_kframe
<< p_stream
->i_granule_shift
);
136 if ( i_frame
< i_tframe
)
138 idx
->i_value
= i_granule
;
139 idx
->i_pagepos
= i_pagepos
;
150 /* new entry; insert after last_idx */
152 idx
= index_entry_new();
154 if ( last_idx
!= NULL
)
156 idx
->p_next
= last_idx
->p_next
;
157 last_idx
->p_next
= idx
;
158 idx
->p_prev
= last_idx
;
166 if ( idx
->p_next
!= NULL
)
168 idx
->p_next
->p_prev
= idx
;
171 idx
->i_value
= i_granule
;
172 idx
->i_pagepos
= i_pagepos
;
180 /*********************************************************************
182 **********************************************************************/
184 /* seek in ogg file to offset i_pos and update the sync */
186 static void seek_byte( demux_t
*p_demux
, int64_t i_pos
)
188 demux_sys_t
*p_sys
= p_demux
->p_sys
;
190 if ( ! stream_Seek( p_demux
->s
, i_pos
) )
192 ogg_sync_reset( &p_sys
->oy
);
194 p_sys
->i_input_position
= i_pos
;
195 p_sys
->b_page_waiting
= false;
201 /* read bytes from the ogg file to try to find a page start */
203 static int64_t get_data( demux_t
*p_demux
, int64_t i_bytes_to_read
)
205 demux_sys_t
*p_sys
= p_demux
->p_sys
;
210 if ( p_sys
->i_total_length
> 0 )
212 if ( p_sys
->i_input_position
+ i_bytes_to_read
> p_sys
->i_total_length
)
214 i_bytes_to_read
= p_sys
->i_total_length
- p_sys
->i_input_position
;
215 if ( i_bytes_to_read
<= 0 ) {
221 seek_byte ( p_demux
, p_sys
->i_input_position
);
223 buf
= ogg_sync_buffer( &p_sys
->oy
, i_bytes_to_read
);
225 i_result
= stream_Read( p_demux
->s
, buf
, i_bytes_to_read
);
227 p_sys
->b_page_waiting
= false;
229 ogg_sync_wrote( &p_sys
->oy
, i_result
);
237 /* Find the first first ogg page for p_stream between offsets i_pos1 and i_pos2,
238 return file offset in bytes; -1 is returned on failure */
240 static int64_t find_first_page( demux_t
*p_demux
, int64_t i_pos1
, int64_t i_pos2
,
241 logical_stream_t
*p_stream
,
242 int64_t *pi_kframe
, int64_t *pi_frame
)
245 int64_t i_granulepos
;
246 int64_t i_bytes_to_read
= i_pos2
- i_pos1
+ 1;
247 int64_t i_bytes_read
;
248 int64_t i_pages_checked
= 0;
249 int64_t i_packets_checked
;
251 demux_sys_t
*p_sys
= p_demux
->p_sys
;
255 seek_byte( p_demux
, i_pos1
);
257 if ( i_pos1
== p_stream
->i_data_start
)
259 /* set a dummy granulepos at data_start */
260 *pi_kframe
= p_stream
->i_keyframe_offset
;
261 *pi_frame
= p_stream
->i_keyframe_offset
;
263 p_sys
->b_page_waiting
= true;
264 return p_sys
->i_input_position
;
267 if ( i_bytes_to_read
> OGGSEEK_BYTES_TO_READ
) i_bytes_to_read
= OGGSEEK_BYTES_TO_READ
;
272 if ( p_sys
->i_input_position
>= i_pos2
)
274 /* we reached the end and found no pages */
279 /* read next chunk */
280 if ( ! ( i_bytes_read
= get_data( p_demux
, i_bytes_to_read
) ) )
287 i_bytes_to_read
= OGGSEEK_BYTES_TO_READ
;
289 i_result
= ogg_sync_pageseek( &p_sys
->oy
, &p_sys
->current_page
);
293 /* found a page, sync to page start */
294 p_sys
->i_input_position
-= i_result
;
295 i_pos1
= p_sys
->i_input_position
;
299 if ( i_result
> 0 || ( i_result
== 0 && p_sys
->oy
.fill
> 3 &&
300 ! strncmp( (char *)p_sys
->oy
.data
, "OggS" , 4 ) ) )
302 i_pos1
= p_sys
->i_input_position
;
306 p_sys
->i_input_position
+= i_bytes_read
;
310 seek_byte( p_demux
, p_sys
->i_input_position
);
311 ogg_stream_reset( &p_stream
->os
);
316 if ( p_sys
->i_input_position
>= i_pos2
)
318 /* reached the end of the search region and nothing was found */
320 return p_sys
->i_input_position
;
323 p_sys
->b_page_waiting
= false;
325 if ( ! ( i_result
= oggseek_read_page( p_demux
) ) )
329 return p_sys
->i_input_position
;
333 if ( p_stream
->os
.serialno
!= ogg_page_serialno( &p_sys
->current_page
) )
335 /* page is not for this stream */
336 p_sys
->i_input_position
+= i_result
;
337 if ( ! i_pages_checked
) i_pos1
= p_sys
->i_input_position
;
342 ogg_stream_pagein( &p_stream
->os
, &p_sys
->current_page
);
345 i_packets_checked
= 0;
347 if ( ogg_stream_packetout( &p_stream
->os
, &op
) > 0 )
352 if ( i_packets_checked
)
354 i_granulepos
= ogg_page_granulepos( &p_sys
->current_page
);
356 oggseek_theora_index_entry_add( p_stream
, i_granulepos
, i_pos1
);
359 i_granulepos
>> p_stream
->i_granule_shift
;
361 *pi_frame
= *pi_kframe
+
362 i_granulepos
- ( *pi_kframe
<< p_stream
->i_granule_shift
);
364 p_sys
->b_page_waiting
= true;
369 /* -> start of next page */
370 p_sys
->i_input_position
+= i_result
;
381 /* Find the last frame for p_stream,
382 -1 is returned on failure */
384 static int64_t find_last_frame (demux_t
*p_demux
, logical_stream_t
*p_stream
)
389 int64_t i_frame
= -1;
390 int64_t i_last_frame
= -1;
391 int64_t i_kframe
= 0;
396 demux_sys_t
*p_sys
= p_demux
->p_sys
;
398 i_pos1
= p_stream
->i_data_start
;
399 i_pos2
= p_sys
->i_total_length
;
400 i_serialno
= p_stream
->os
.serialno
;
402 i_start_pos
= i_pos2
- OGGSEEK_BYTES_TO_READ
;
407 if ( i_start_pos
< i_pos1
) i_start_pos
= i_pos1
;
409 i_page_pos
= find_first_page( p_demux
, i_start_pos
, i_pos2
, p_stream
, &i_kframe
, &i_frame
);
413 /* no pages found in range */
414 if ( i_last_frame
>= 0 )
416 /* No more pages in range -> return last one */
419 if ( i_start_pos
<= i_pos1
)
425 i_pos2
-= i_start_pos
;
426 i_start_pos
-= OGGSEEK_BYTES_TO_READ
;
427 if ( i_start_pos
< i_pos1
) i_start_pos
= i_pos1
;
428 i_pos2
+= i_start_pos
;
432 /* found a page, see if we can find another one */
433 i_last_frame
= i_frame
;
434 i_start_pos
= i_page_pos
+ 1;
445 /* convert a theora frame to a granulepos */
447 static inline int64_t frame_to_gpos( logical_stream_t
*p_stream
, int64_t i_kframe
,
450 if ( p_stream
->fmt
.i_codec
== VLC_CODEC_THEORA
)
452 return ( i_kframe
<< p_stream
->i_granule_shift
) + ( i_frame
- i_kframe
);
462 /* seek to a suitable point to begin decoding for i_tframe. We can pre-set bounding positions
463 i_pos_lower and i_pos_higher to narrow the search domain. */
466 static int64_t ogg_seek( demux_t
*p_demux
, logical_stream_t
*p_stream
, int64_t i_tframe
,
467 int64_t i_pos_lower
, int64_t i_pos_upper
, int64_t *pi_pagepos
,
471 * We do two passes here, first with b_exact set, then with b_exact unset.
473 * If b_exact is set, we find the highest granulepos <= the target granulepos
474 * from this we extract an estimate of the keyframe (note that there could be other
475 * "hidden" keyframes between the found granulepos and the target).
477 * On the second pass we find the highest granulepos < target. This places us just before or
478 * at the start of the target keyframe.
480 * When we come to decode, we start from this second position, discarding any completed
481 * packets on that page, and read pages discarding packets until we get to the target frame.
483 * The function returns the granulepos which is found,
484 * sets the page offset in pi_pagepos. -1 is returned on error.
488 * we find the highest sync frame <= target frame, and return the sync_frame number
489 * b_exact should be set to true
492 * the method used is bi-sections:
493 * - we check the lower keyframe
494 * if this is == target we return
495 * if > target, or we find no keyframes, we go to the lower segment
496 * if < target we divide the segment in two and check the upper half
498 * This is then repeated until the segment size is too small to hold a packet,
499 * at which point we return our best match
501 * Two optimisations are made: - anything we discover about keyframes is added to our index
502 * - before calling this function we get approximate bounds from the index
504 * therefore, subsequent searches become more rapid.
515 int64_t i_best_kframe
= -1;
516 int64_t i_best_frame
= -1;
517 int64_t i_best_pagepos
= -1;
519 demux_sys_t
*p_sys
= p_demux
->p_sys
;
521 if ( i_tframe
< p_stream
->i_keyframe_offset
)
523 *pi_pagepos
= p_stream
->i_data_start
;
526 seek_byte( p_demux
, p_stream
->i_data_start
);
527 return frame_to_gpos( p_stream
, p_stream
->i_keyframe_offset
, 1 );
529 return frame_to_gpos( p_stream
, p_stream
->i_keyframe_offset
, 0 );
532 if ( i_pos_lower
< p_stream
->i_data_start
)
534 i_pos_lower
= p_stream
->i_data_start
;
537 if ( i_pos_upper
< 0 )
539 i_pos_upper
= p_sys
->i_total_length
;
542 if ( i_pos_upper
> p_sys
->i_total_length
)
544 i_pos_upper
= p_sys
->i_total_length
;
547 i_start_pos
= i_pos_lower
;
548 i_end_pos
= i_pos_upper
;
550 i_segsize
= ( i_end_pos
- i_start_pos
+ 1 ) >> 1;
554 /* see if the frame lies in current segment */
555 if ( i_start_pos
< i_pos_lower
)
557 i_start_pos
= i_pos_lower
;
559 if ( i_end_pos
> i_pos_upper
)
561 i_end_pos
= i_pos_upper
;
564 if ( i_start_pos
>= i_end_pos
)
566 if ( i_start_pos
== i_pos_lower
)
568 if ( ! b_exact
) seek_byte( p_demux
, i_start_pos
);
569 *pi_pagepos
= i_start_pos
;
570 return frame_to_gpos( p_stream
, p_stream
->i_keyframe_offset
, 1 );
575 if ( p_stream
->fmt
.i_codec
== VLC_CODEC_THEORA
)
577 i_pagepos
= find_first_page( p_demux
, i_start_pos
, i_end_pos
, p_stream
,
578 &i_kframe
, &i_frame
);
582 if ( i_pagepos
!= -1 && i_kframe
!= -1 )
586 if ( b_exact
&& i_frame
>= i_tframe
&& i_kframe
<= i_tframe
)
589 *pi_pagepos
= i_start_pos
;
590 return frame_to_gpos( p_stream
, i_kframe
, i_frame
);
593 if ( ( i_kframe
< i_tframe
|| ( b_exact
&& i_kframe
== i_tframe
) )
594 && i_kframe
> i_best_kframe
)
596 i_best_kframe
= i_kframe
;
597 i_best_frame
= i_frame
;
598 i_best_pagepos
= i_pagepos
;
601 if ( i_frame
>= i_tframe
)
603 /* check lower half of segment */
604 i_start_pos
-= i_segsize
;
605 i_end_pos
-= i_segsize
;
608 else i_start_pos
= i_pagepos
;
613 /* no keyframe found, check lower segment */
614 i_end_pos
-= i_segsize
;
615 i_start_pos
-= i_segsize
;
618 i_segsize
= ( i_end_pos
- i_start_pos
+ 1 ) >> 1;
619 i_start_pos
+= i_segsize
;
621 } while ( i_segsize
> 64 );
623 if ( i_best_kframe
>- 1 )
627 seek_byte( p_demux
, i_best_pagepos
);
629 *pi_pagepos
= i_best_pagepos
;
630 return frame_to_gpos( p_stream
, i_best_kframe
, i_best_frame
);
641 /* find upper and lower pagepos for i_tframe; if we find an exact match, we return it */
643 static demux_index_entry_t
*get_bounds_for ( logical_stream_t
*p_stream
, int64_t i_tframe
,
644 int64_t *pi_pos_lower
, int64_t *pi_pos_upper
)
650 demux_index_entry_t
*idx
= p_stream
->idx
;
652 *pi_pos_lower
= *pi_pos_upper
= -1;
654 while ( idx
!= NULL
)
657 if ( idx
-> i_pagepos
< 0 )
659 /* kframe was found to be invalid */
664 if ( p_stream
->fmt
.i_codec
== VLC_CODEC_THEORA
)
666 i_gpos
= idx
->i_value
;
667 i_kframe
= i_gpos
>> p_stream
->i_granule_shift
;
668 i_frame
= i_kframe
+ i_gpos
- ( i_kframe
<< p_stream
->i_granule_shift
);
673 if ( i_kframe
> i_tframe
)
675 *pi_pos_upper
= idx
->i_pagepos
;
679 if ( i_frame
< i_tframe
)
681 *pi_pos_lower
= idx
->i_pagepos
;
693 /* get highest frame in theora stream */
695 static int64_t find_last_theora_frame ( demux_t
*p_demux
, logical_stream_t
*p_stream
)
699 i_frame
= find_last_frame ( p_demux
, p_stream
);
701 /* We need to reset back to the start here, otherwise packets cannot be decoded.
702 * I think this is due to the fact that we seek to the end and then we must reset
703 * all logical streams, which causes remaining headers not to be read correctly.
704 * Seeking to 0 is the only value which seems to work, and it appears to have no
705 * adverse effects. */
707 seek_byte( p_demux
, 0 );
714 /************************************************************************
716 *************************************************************************/
721 /* return highest frame number for p_stream (which must be a theora or dirac video stream) */
723 int64_t oggseek_get_last_frame ( demux_t
*p_demux
, logical_stream_t
*p_stream
)
725 int64_t i_frame
= -1;
727 if ( p_stream
->fmt
.i_codec
== VLC_CODEC_THEORA
)
729 i_frame
= find_last_theora_frame ( p_demux
, p_stream
);
731 if ( i_frame
< 0 ) return -1;
735 /* unhandled video format */
744 /* seek to target frame in p_stream; actually we will probably end up just before it
747 * range for i_tframe is 0 -> p_sys->i_total_frames - 1
750 int oggseek_find_frame ( demux_t
*p_demux
, logical_stream_t
*p_stream
, int64_t i_tframe
)
753 const demux_index_entry_t
*fidx
;
755 /* lower and upper bounds for search domain */
759 int64_t i_granulepos
;
762 /* keyframe for i_tframe ( <= i_tframe ) */
765 /* keyframe for i_kframe ( <= i_kframe ) */
768 /* next frame to be decoded ( >= i_xkframe ) */
771 demux_sys_t
*p_sys
= p_demux
->p_sys
;
773 i_tframe
+= p_stream
->i_keyframe_offset
;
775 /* reduce the search domain */
776 fidx
= get_bounds_for( p_stream
, i_tframe
, &i_pos_lower
, &i_pos_upper
);
780 /* no exact match found; search the domain for highest keyframe <= i_tframe */
782 i_granulepos
= ogg_seek ( p_demux
, p_stream
, i_tframe
, i_pos_lower
, i_pos_upper
,
784 if ( i_granulepos
== -1 )
791 i_granulepos
= fidx
->i_value
;
794 if ( p_stream
->fmt
.i_codec
== VLC_CODEC_THEORA
)
796 i_kframe
= i_granulepos
>> p_stream
->i_granule_shift
;
797 if ( i_kframe
< p_stream
->i_keyframe_offset
)
799 i_kframe
= p_stream
->i_keyframe_offset
;
802 /* we found a keyframe, but we don't know where its packet starts, so search for a
803 frame just before it */
805 /* reduce search domain */
806 get_bounds_for( p_stream
, i_kframe
-1, &i_pos_lower
, &i_pos_upper
);
808 i_granulepos
= ogg_seek( p_demux
, p_stream
, i_kframe
-1, i_pos_lower
, i_pos_upper
,
811 /* i_cframe will be the next frame we decode */
812 i_xkframe
= i_granulepos
>> p_stream
->i_granule_shift
;
813 i_cframe
= i_xkframe
+ i_granulepos
- ( i_xkframe
<< p_stream
->i_granule_shift
) + 1;
815 if ( p_sys
->i_input_position
== p_stream
->i_data_start
)
817 i_cframe
= i_kframe
= p_stream
->i_keyframe_offset
;
821 oggseek_theora_index_entry_add( p_stream
, i_granulepos
, p_sys
->i_input_position
);
825 else return VLC_EGENERIC
;
827 p_stream
->i_skip_frames
= i_tframe
- i_cframe
;
829 ogg_stream_reset( &p_stream
->os
);
839 /****************************************************************************
840 * oggseek_read_page: Read a full Ogg page from the physical bitstream.
841 ****************************************************************************
842 * Returns number of bytes read. This should always be > 0
843 * unless we are at the end of stream.
845 ****************************************************************************/
846 int64_t oggseek_read_page( demux_t
*p_demux
)
848 demux_sys_t
*p_ogg
= p_demux
->p_sys
;
849 uint8_t header
[PAGE_HEADER_BYTES
+255];
857 demux_sys_t
*p_sys
= p_demux
->p_sys
;
859 /* store position of this page */
860 i_in_pos
= p_ogg
->i_input_position
= stream_Tell( p_demux
->s
);
862 if ( p_sys
->b_page_waiting
) {
863 msg_Warn( p_demux
, "Ogg page already loaded" );
867 if ( stream_Read ( p_demux
->s
, header
, PAGE_HEADER_BYTES
) < PAGE_HEADER_BYTES
)
869 stream_Seek( p_demux
->s
, i_in_pos
);
870 msg_Dbg ( p_demux
, "Reached clean EOF in ogg file" );
874 i_nsegs
= header
[ PAGE_HEADER_BYTES
- 1 ];
876 if ( stream_Read ( p_demux
->s
, header
+PAGE_HEADER_BYTES
, i_nsegs
) < i_nsegs
)
878 stream_Seek( p_demux
->s
, i_in_pos
);
879 msg_Warn ( p_demux
, "Reached broken EOF in ogg file" );
883 i_page_size
= PAGE_HEADER_BYTES
+ i_nsegs
;
885 for ( i
= 0; i
< i_nsegs
; i
++ )
887 i_page_size
+= header
[ PAGE_HEADER_BYTES
+ i
];
890 ogg_sync_reset( &p_ogg
->oy
);
892 buf
= ogg_sync_buffer( &p_ogg
->oy
, i_page_size
);
894 memcpy( buf
, header
, PAGE_HEADER_BYTES
+ i_nsegs
);
896 i_result
= stream_Read ( p_demux
->s
, (uint8_t*)buf
+ PAGE_HEADER_BYTES
+ i_nsegs
,
897 i_page_size
- PAGE_HEADER_BYTES
- i_nsegs
);
899 ogg_sync_wrote( &p_ogg
->oy
, i_result
+ PAGE_HEADER_BYTES
+ i_nsegs
);
904 if ( ogg_sync_pageout( &p_ogg
->oy
, &p_ogg
->current_page
) != 1 )
906 msg_Err( p_demux
, "Got invalid packet, read %"PRId64
" of %i: %s",i_result
,i_page_size
,
911 p_sys
->b_page_waiting
= false;
913 return i_result
+ PAGE_HEADER_BYTES
+ i_nsegs
;