Ogg Index - Revision history

Cpearce at 23:22, 22 November 2010

2010-11-22T23:22:15Z

← Older revision		Revision as of 23:22, 22 November 2010
Line 3:		Line 3:
	= Ogg Skeleton 3.3 with Keyframe Index =		= Ogg Skeleton 3.3 with Keyframe Index =

	~~'''DRAFT, last updated 27 January 2010'''~~		'''This specification is obsolete and has been superseded by [[Ogg Skeleton 4]]. Use that instead!'''

	'''This specification is ~~still a work in progress,~~ and ~~does not yet constitute an official~~ Ogg ~~track format~~.'''

	== Overview ==		== Overview ==

Silvia: typo - duplicate field

2010-03-20T06:37:26Z

typo - duplicate field

← Older revision		Revision as of 06:37, 20 March 2010
Line 157:		Line 157:
	# '''[NEW]''' Last-sample-time denominator: 8 byte signed integer, with value 0 if the timestamp is unknown. Decoders should always ensure that the denominator is not 0 before using it as a divisor!		# '''[NEW]''' Last-sample-time denominator: 8 byte signed integer, with value 0 if the timestamp is unknown. Decoders should always ensure that the denominator is not 0 before using it as a divisor!
	# '''[NEW]''' The length of the segment, in bytes: 8 byte unsigned integer, 0 if unknown.		# '''[NEW]''' The length of the segment, in bytes: 8 byte unsigned integer, 0 if unknown.
	# '''[NEW]''' The offset of the first non-header page, in bytes: 8 byte unsigned ~~integer.~~		# '''[NEW]''' The offset of the first non-header page, in bytes: 8 byte unsigned integer, 0 if unknown.
	~~# '''[NEW]''' The offset of the first non-header page in bytes: 8 byte unsigned~~ integer, 0 if unknown.

	The first-sample-time and last-sample-time are rational numbers, in units		The first-sample-time and last-sample-time are rational numbers, in units
Line 219:		Line 218:

	As per the Skeleton 3.0 track, '''the last packet in the Skeleton 3.3 track		As per the Skeleton 3.0 track, '''the last packet in the Skeleton 3.3 track
	is an empty EOS packet'''.		is an empty EOS packet'''.

	== Software Prototype ==		== Software Prototype ==

Cpearce at 01:45, 27 January 2010

2010-01-27T01:45:02Z

Show changes

Cpearce at 04:37, 14 January 2010

2010-01-14T04:37:10Z

Cpearce at 22:28, 10 January 2010

2010-01-10T22:28:45Z

Show changes

Conrad: add {{draft}} template

2009-09-24T05:52:25Z

add {{draft}} template

← Older revision		Revision as of 05:52, 24 September 2009
Line 1:		Line 1:
			{{draft}}

	= Ogg Index Track Specification Version 1 =		= Ogg Index Track Specification Version 1 =

Cpearce: /* Ogg Index Track Specification Version 1 */

2009-09-24T05:04:44Z

Ogg Index Track Specification Version 1

← Older revision		Revision as of 05:04, 24 September 2009
Line 2:		Line 2:

	'''DRAFT, last updated 24 September 2009'''		'''DRAFT, last updated 24 September 2009'''

			'''This specification is still a work in progress, and does not yet constitute an official Ogg track format.'''

Cpearce: /* Ogg Index Track Format Version 1 */

2009-09-24T04:56:29Z

Ogg Index Track Format Version 1

← Older revision		Revision as of 04:56, 24 September 2009
Line 1:		Line 1:
	= Ogg Index Track ~~Format~~ Version 1 =		= Ogg Index Track Specification Version 1 =

	'''DRAFT ~~SPECIFICATION'''~~		'''DRAFT, last updated 24 September 2009'''

	~~'''Updated~~ 24 September 2009'''

Cpearce: Draft of the Ogg Index track specification

2009-09-24T04:55:27Z

Draft of the Ogg Index track specification

New page

= Ogg Index Track Format Version 1 =

'''DRAFT SPECIFICATION'''

'''Updated 24 September 2009'''

== Overview ==

Seeking in an Ogg file is typically implemented as a bisection search
over the pages in the file. The Ogg physical bitstream is bisected and
the next Ogg page's end-time is extracted. The bisection continues until
it reaches an Ogg page with an end-time close enough to the seek target
time. However in media containing streams which have key frames and
interframes, such as Theora streams, your bisection search won't
necessarily stop at a keyframe, thus you can't simply resume playback
from that point. First you need to construct the keyframe's timestamp
from the last page's granulepos, and seek again to the start of the
keyframe and decode forward until you reach the frame at the seek
target.

This is further complicated by the fact that packets often span multiple
Ogg pages, and that Ogg pages from different streams can be interleaved
between spanning packets.

The bisection method above works fine for seeking in local files, but
for seeking in files served over the Internet via HTTP, each bisection
or non sequential read can trigger a new HTTP request, which can have
very high latency, making seeking very slow.

== Seeking with an index ==

The Ogg index bitstream attempts to alleviate this problem, by providing
an index of periodic keyframes in an Ogg file. The index is contained in
a separate track which is embedded in the Ogg file, so that players
which don't understand the index track can just ignore it. In streams
without the concept of a keyframe, such as Vorbis streams where each
sample is independent, the index can instead record the time position at
periodic intervals, which achieves the same result. When this document
refers to keyframes, it also refers to these independent periodic
samples from keyframe-less streams.

The Ogg index bitstream provides seek algorithms with an ordered table
of the Ogg page start-offsets and end-times of key points in the indexed
streams in an Ogg segment.

A key point k is defined as follows. Each key point has an 8 byte offset
o, an 8 byte time t, and a 4 byte checksum c. This specifies that in
order to render the media at presentation time t milliseconds, the last
page which lies before the start of all the packets containing all the
key frames required to render at time t begins at offset o. The checksum
c is the checksum of the page which begins at offset o, which enables
you to verify that you're seeking to the intended page.

To seek in an Ogg bitstream which contains an index, you find the last
key point in the index with time less than or equal to the target time.
You then seek to the key point's offset, check that the page found there
has checksum c, and then decode forward until you encounter the sample
which corresponds to your seek target time. You are guaranteed to pass
keyframes on all indexed streams with time less than or equal to your
seek target time while decoding up to the seek target.

Be aware that you cannot assume that any or all Ogg files will contain
an index, and so when implementing Ogg seeking, you must gracefully
fall-back to a bisection search or other seek algorithm when the index
is not present.

The index also only holds data for the segment in which it resides, i.e.
if two Ogg files are concatenated together ("chained"), the index track
in one Ogg segment does not contain information about the keyframes in
the other Ogg segment.

The index also stores meta data about the segment in which it resides.
It stores the start time and the end time, and also the length of the
segment in bytes. This is so that if the seek target is outside of the
indexed range, you can immediately move to the next/previous segment and
either seek using that segment's index, or narrow the bisection window
if that segment has no index.

== Format Specification ==

Unless otherwise specified, all integers and fields in the bitstream are
encoded with the least significant bit coming first in each byte.
Integers and fields comprising of more than one byte are encoded least
significant byte first (i.e. little endian byte order).

An Ogg index track starts with an identifier header packet which
contains the following data, in the following order:

* The identifier "index\0".
* The index version format number, as a 1 byte unsigned integer. This specification describes version 1, so this field should have the value 0x01.
* The playback start time, in milliseconds, as an 8 byte unsigned integer, this is the presentation time of the first frame.
* The playback end time, in milliseconds, as an 8 byte unsigned integer, this is the end time of the last frame.
* The length of the indexed segment, in bytes, as an 8 byte unsigned integer.
* The number of key points in the index, 'n', as a 4 byte unsigned integer.

The track then contains one secondary header packet, which contains the
actual index. This is the "index packet", and it must begin on a new
page, but it may span multiple pages. The index packet contains the
following:

* 'n' key points, each of which contain, in the following order:
** the page offset as an 8 byte unsigned integer, followed by
** the checksum of the page found at the offset, as a 4 byte field,followed by
** the presentation times in milliseconds of the key point, as an 8 byte unsigned integer.

The size of the data in the index packet is (n * (8 + 4 + 8)) bytes. The
key points are stored in increasing order by offset.

The track then contains one empty EOS packet, which must start on a new
page. The track therefore contains exactly three packets, on three or
more pages.

The offsets stored in the keypoints is relative to the start of the Ogg
bitstream segment. So if you have a physical Ogg bitstream made up of
two chained Oggs, the offsets in the second Ogg segment's bitstream's
index are relative to the beginning of the second Ogg in the chain, not
the first. Also note that if a physical Ogg bitstream is made up of
chained Oggs, the presence of an index in one segment does not imply
that there will be an index in any other segment.

The exact number of keyframes used to construct key points in the index
is up to the indexer, but to limit the index size, we recommend
including at most one key point per every 64KB of data, or every 500ms.

There can be only one index track per Ogg bitstream segment. The index
packet must occur before all non-metadata streams' content packets. In
practice this means that the index packet will occur along with other
secondary header pages, before the skeleton EOS page.

All pages in the index bitstream have their granulepos set as 0.

== Software Prototype ==

For a prototype indexer, see:

http://github.com/cpearce/OggIndex

To see how indexes improves network seeking performance, you can download a development
version of Firefox which can take advantage of indexes here:

http://pearce.org.nz/video/firefox-indexed-ogg-seek.linux.tar.bz2

http://pearce.org.nz/video/firefox-indexed-ogg-seek.macosx.dmg

http://pearce.org.nz/video/firefox-indexed-ogg-seek.win32.zip

Then point that browser here:

http://pearce.org.nz/video/indexed-seek-demo.html

← Older revision		Revision as of 04:37, 14 January 2010
Line 1:		Line 1:
	{{draft}}		{{draft}}

	= Ogg Skeleton 3.1 with Keyframe Index =		= Ogg Skeleton 3.2 with Keyframe Index =

	'''DRAFT, last updated 11 January 2010'''		'''DRAFT, last updated 14 January 2010'''

	'''This specification is still a work in progress, and does not yet constitute an official Ogg track format.'''		'''This specification is still a work in progress, and does not yet constitute an official Ogg track format.'''
Line 34:		Line 34:
	== Seeking with an index ==		== Seeking with an index ==

	The Skeleton 3.1 bitstream attempts to alleviate this problem, by		The Skeleton 3.2 bitstream attempts to alleviate this problem, by
	providing an index of periodic keyframes for every content stream in an		providing an index of periodic keyframes for every content stream in an
	Ogg segment. Note that the Skeleton 3.1 track only holds data for the		Ogg segment. Note that the Skeleton 3.2 track only holds data for the
	segment in which it resides. So if two Ogg files are concatenated together		segment in which it resides. So if two Ogg files are concatenated together
	("chained"), the Skeleton 3.1's keyframe indexes in the first Ogg segment		("chained"), the Skeleton 3.2's keyframe indexes in the first Ogg segment
	(the first Ogg in the "chain") do not contain information about the		(the first Ogg in the "chain") do not contain information about the
	keyframes in the second Ogg segment (the second Ogg in the "chain").		keyframes in the second Ogg segment (the second Ogg in the "chain").

	Each content track has a separate index, which is stored in its own		Each content track has a separate index, which is stored in its own
	packet in the Skeleton 3.1 track. The index for streams without the		packet in the Skeleton 3.2 track. The index for streams without the
	concept of a keyframe, such as Vorbis streams, can instead record the		concept of a keyframe, such as Vorbis streams, can instead record the
	time position at periodic intervals, which achieves the same result.		time position at periodic intervals, which achieves the same result.
Line 49:		Line 49:
	independent periodic samples from keyframe-less streams.		independent periodic samples from keyframe-less streams.

	All the Skeleton 3.1 track's pages appear in the header pages of the Ogg		All the Skeleton 3.2 track's pages appear in the header pages of the Ogg
	segment. This means the all the keyframe indexes are immediately		segment. This means the all the keyframe indexes are immediately
	available once the header packets have been read when playing the media		available once the header packets have been read when playing the media
Line 71:		Line 71:
	accounted for in the time stored in the keypoint.		accounted for in the time stored in the keypoint.

	The Skeleton 3.1 track contains one index for each content stream in the		The Skeleton 3.2 track contains one index for each content stream in the
	file. To seek in an Ogg file which contains keyframe indexes, first		file. To seek in an Ogg file which contains keyframe indexes, first
	construct the set which contains every active streams' last keypoint which		construct the set which contains every active streams' last keypoint which
Line 95:		Line 95:
	to ensure your decoder correctly knows how to parse the Skeleton track.		to ensure your decoder correctly knows how to parse the Skeleton track.

	The Skeleton 3.1 header packet also stores meta data about the segment in		The Skeleton 3.2 header packet also stores meta data about the segment in
	which it resides. It stores the timestamps of the first and last samples		which it resides. It stores the timestamps of the first and last samples
	in the segment. This also allows you to determine the duration of the		in the segment. This also allows you to determine the duration of the
Line 112:		Line 112:
	significant byte first (i.e. little endian byte order).		significant byte first (i.e. little endian byte order).

	The Skeleton 3.1 track is intended to be backwards compatible with the		The Skeleton 3.2 track is intended to be backwards compatible with the
	Skeleton 3.0 specification, available at		Skeleton 3.0 specification, available at
	http://www.xiph.org/ogg/doc/skeleton.html . Unless specified		http://www.xiph.org/ogg/doc/skeleton.html . Unless specified
	differently here, it is safe to assume that anything specified for a		differently here, it is safe to assume that anything specified for a
	Skeleton 3.0 track holds for a Skeleton 3.1 track.		Skeleton 3.0 track holds for a Skeleton 3.2 track.

	As per the Skeleton 3.0 track, a segment containing a Skeleton 3.1 track		As per the Skeleton 3.0 track, a segment containing a Skeleton 3.2 track
	must begin with a '''Skeleton 3.1 fishead BOS packet''' on a page by itself, with the		must begin with a '''Skeleton 3.2 fishead BOS packet''' on a page by itself, with the
	following format:		following format:

Line 134:		Line 134:
	# '''[NEW]''' Last-sample-time numerator: 8 byte signed integer representing the end time of the last sample in the segment.		# '''[NEW]''' Last-sample-time numerator: 8 byte signed integer representing the end time of the last sample in the segment.
	# '''[NEW]''' Last-sample-time denominator: 8 byte signed integer, with value 0 if the timestamp is unknown. Decoders should always ensure that the denominator is not 0 before using it as a divisor!		# '''[NEW]''' Last-sample-time denominator: 8 byte signed integer, with value 0 if the timestamp is unknown. Decoders should always ensure that the denominator is not 0 before using it as a divisor!
	# '''[NEW]''' The length of the segment, in bytes: 8 byte ~~signed~~ integer, -1 if unknown.		# '''[NEW]''' The length of the segment, in bytes: 8 byte unsigned integer, 0 if unknown.
			# '''[NEW]''' The offset of the first non-header page, in bytes: 8 byte unsigned integer.

	The first-sample-time and last-sample-time are rational numbers, in units		The first-sample-time and last-sample-time are rational numbers, in units
Line 142:		Line 143:
	subtracting the first-sample-time from the last-sample-time.		subtracting the first-sample-time from the last-sample-time.

	In Skeleton 3.1 the "fisbone" packets remain unchanged from Skeleton		In Skeleton 3.2 the "fisbone" packets remain unchanged from Skeleton
	3.0, and will still follow after the other streams' BOS pages and		3.0, and will still follow after the other streams' BOS pages and
	secondary header pages.		secondary header pages.

	Before the Skeleton EOS page in the segment header pages come the		Before the Skeleton EOS page in the segment header pages come the
	'''Skeleton 3.1 keyframe index packets'''. There is one index packet for each		'''Skeleton 3.2 keyframe index packets'''. There is one index packet for each
	content stream in the Ogg segment. Each index packet contains the		content stream in the Ogg segment. Each index packet contains the
	following:		following:
Line 153:		Line 154:
	# Identifier 6 bytes: "index\0"		# Identifier 6 bytes: "index\0"
	# The serialno of the stream this index applies to, as a 4 byte field.		# The serialno of the stream this index applies to, as a 4 byte field.
	# The number of keypoints in this index packet, 'n' as a 4 byte unsigned integer. This can be 0.		# The number of keypoints in this index packet, 'n' as a 8 byte unsigned integer. This can be 0.
	# The keypoint presentation time denominator, as an 8 byte signed integer.		# The keypoint presentation time denominator, as an 8 byte signed integer.
	# 'n' key points, each of which contain, in the following order:		# 'n' key points, each of which contain, in the following order:
Line 185:		Line 186:

	Recent [http://firefogg.org/nightly/ ffmpeg2theora nightlies] will also include a keyframe index in the Skeleton		Recent [http://firefogg.org/nightly/ ffmpeg2theora nightlies] will also include a keyframe index in the Skeleton
	3.1 track if you specify the command line option <tt>--seek-index</tt>.		3.2 track if you specify the command line option <tt>--seek-index</tt>.

	To see how indexes improves network seeking performance, you can download a development		To see how indexes improves network seeking performance, you can download a development