GranulePosAndSeeking - Revision history

Gmaxwell: /* But how do I "seek to the desired time"? */

2012-05-30T23:57:49Z

But how do I "seek to the desired time"?

← Older revision		Revision as of 23:57, 30 May 2012
Line 81:		Line 81:
	Doing this correctly is somewhat more complicated than it seems due to the existence of continued pages and the risk of a small valid page being contained within a packet. Both of these challenges can be addressed but the solution is left as an exercise for the reader. <!-- Hint: The maximum page size is ~64kbytes -->		Doing this correctly is somewhat more complicated than it seems due to the existence of continued pages and the risk of a small valid page being contained within a packet. Both of these challenges can be addressed but the solution is left as an exercise for the reader. <!-- Hint: The maximum page size is ~64kbytes -->

-	The bisection search is very good compared to the obvious alternatives (a linear scan of the whole file), often taking just a couple of reads to locate the correct location in a file gigabytes in size but the truly obsessive can out-perform the bisection on average by using the local bitrate to pick a better target than the half way point used in a bisection search ([http://en.wikipedia.org/wiki/Secant_method secant method]). The improvement possible from better-than-bisection approaches is probably only relevant for seeking across a high latency network. In typical applications the added complexity may not be worth the cost.	+	The bisection search is very good compared to the obvious alternatives (a linear scan of the whole file), often taking just a couple of reads to locate the correct location in a file gigabytes in size but the truly obsessive can out-perform the bisection on average by using the local bitrate to pick a better target than the half way point used in a bisection search ([http://en.wikipedia.org/wiki/Secant_method secant method] but be careful about the worst case becoming linear; see [http://en.wikipedia.org/wiki/Brent%27s_method brents method]). The improvement possible from better-than-bisection approaches is probably only relevant for seeking across a high latency network. In typical applications the added complexity may not be worth the cost.

	== References ==		== References ==

Gmaxwell: on low level seeking

2009-06-06T19:06:58Z

on low level seeking

← Older revision		Revision as of 19:06, 6 June 2009
Line 67:		Line 67:
	only depends on the way the stream is constructed, so it can be large		only depends on the way the stream is constructed, so it can be large
	if pages in a particular logical bistream is sparse.		if pages in a particular logical bistream is sparse.
		+
		+	=== But how do I "seek to the desired time"?===
		+	The above assumes that you already know how to seek to a particular granpos within the stream efficiently.
		+
		+	This isn't as simple as it sounds because the Ogg format does not include an index. The lack of an index is a feature rather than a deficiency and it is one of the primary reasons to use Ogg over some other formats. Because Ogg doesn't have in index infinite streams and partial streams are automatically supported by correctly written applications. There is no risk of truncation or minor corruption making a stream unseekable. No memory is required to store an index, no is bandwidth wasted to transmit it, and seeking granularity is not limited to the precision of the index. On the other hand non-indexed formats can require a little more intelligence in the application and many applications have gotten it wrong (although this intelligence is also needed in a well written application fo indexed formats so that it can seek with a corrupted index or below the index granularity).
		+
		+	If you are thinking about seeking in an Ogg file by first building your own complete index: STOP. This is not the correct procedure. It seems simple but it requires a costly read of the entire stream (which may be gigabytes in size, or even infinite). There is a better way.
		+
		+	The correct way to seek to a particular granule value in Ogg is by using a [http://en.wikipedia.org/wiki/Bisection_method bisection search]: Seek to the middle of the stream, obtain sync, and compare your target granule position with the current position. If the target is less than the current position repeat these steps on the left side, if it's greater repeat it on the right side. By applying this recursive algorithm you are guaranteed to find your target location quickly.
		+
		+	To correctly support chaining you should first use this kind of search to locate the stream endpoints. Then the above approach can be applied within the streams to seek to any location within a chained file.
		+
		+	Doing this correctly is somewhat more complicated than it seems due to the existence of continued pages and the risk of a small valid page being contained within a packet. Both of these challenges can be addressed but the solution is left as an exercise for the reader. <!-- Hint: The maximum page size is ~64kbytes -->
		+
		+	The bisection search is very good compared to the obvious alternatives (a linear scan of the whole file), often taking just a couple of reads to locate the correct location in a file gigabytes in size but the truly obsessive can out-perform the bisection on average by using the local bitrate to pick a better target than the half way point used in a bisection search ([http://en.wikipedia.org/wiki/Secant_method secant method]). The improvement possible from better-than-bisection approaches is probably only relevant for seeking across a high latency network. In typical applications the added complexity may not be worth the cost.

	== References ==		== References ==

Rillian: /* Granules and Granuleshift */ Give the explanded granulepos->granule calculation

2008-11-20T01:39:12Z

Granules and Granuleshift: Give the explanded granulepos->granule calculation

← Older revision		Revision as of 01:39, 20 November 2008
Line 36:		Line 36:

	curr_granule = prev_granule + offset		curr_granule = prev_granule + offset
		+
		+	Which expands to this expression of the page granulepos:
		+
		+	curr_granule = (granulepos >> granuleshift) + (granulepos & ((1 << granuleshift) - 1)))

	Keyframes, and other data with no dependency on earlier packets, are encoded with:		Keyframes, and other data with no dependency on earlier packets, are encoded with:

Rillian: /* Granules and Granuleshift */ remove redundant `tags`

2008-11-20T01:38:40Z Granules and Granuleshift: remove redundant <tt> tags ← Older revision Revision as of 01:38, 20 November 2008 Line 26: Line 26: <tt>prev_granule</tt>, we define <tt>offset</tt> as the difference between these: <tt>prev_granule</tt>, we define <tt>offset</tt> as the difference between these: - <tt>offset = curr_granule - prev_granule</tt> + offset = curr_granule - prev_granule We refer to the number of bits used to encode the offset as the "granuleshift". This is fixed for all pages in We refer to the number of bits used to encode the offset as the "granuleshift". This is fixed for all pages in that track (logical bitstream). So we encode the later page's granulepos as: that track (logical bitstream). So we encode the later page's granulepos as: - <tt>granulepos = (prev_granule << granuleshift) | offset</tt> + granulepos = (prev_granule << granuleshift) | offset When decoding, we can extract the current_granule from a granulepos by simply adding these fields: When decoding, we can extract the current_granule from a granulepos by simply adding these fields: - <tt>granule = prev_granule + offset</tt> + curr_granule = prev_granule + offset Keyframes, and other data with no dependency on earlier packets, are encoded with: Keyframes, and other data with no dependency on earlier packets, are encoded with: - <tt>prev_granule = curr_granule, offset = 0</tt> + prev_granule = curr_granule, offset = 0 === Procedure for seeking on a single track === === Procedure for seeking on a single track ===

Conrad: /* Definitions */ 2008-11-19T13:00:55Z Definitions ← Older revision Revision as of 13:00, 19 November 2008 Line 8: Line 8: === Definitions === === Definitions === - Overload "time" to mean the time represented by a granulepos. Hence the time of a page is the time represented by the page granulepos. + Overload '''time''' to mean the time represented by a granulepos. Hence the time of a page is the time represented by the page granulepos. - Define "seek" to mean: for each logical bitstream, locate the bytewise-latest page in the bitstream with a time < the + Define '''seek''' to mean: for each logical bitstream, locate the bytewise-latest page in the bitstream with a time < the target time, then choose the bytewise-earliest among these pages. Thus if two pages have the same time, seeking will locate the bytewise-earlier page. target time, then choose the bytewise-earliest among these pages. Thus if two pages have the same time, seeking will locate the bytewise-earlier page. ==== Granules and Granuleshift ==== ==== Granules and Granuleshift ==== - We use the term "granule" to refer to time measured in the units of the codec. For audio codecs this is usually samples, and for video codecs it is frames or fields. + We use the term '''granule''' to refer to time measured in the units of the codec. For audio codecs this is usually samples, and for video codecs it is frames or fields. In some formats, pages have a dependency on the data of an earlier page; for example in Theora, interframes have a dependency on an earlier keyframe -- the keyframe data is required to decode the interframe. We encode both the time of the page and the time of the page it depends on into the granulepos. In order to do this we treat the granulepos as a bitfield as follows: In some formats, pages have a dependency on the data of an earlier page; for example in Theora, interframes have a dependency on an earlier keyframe -- the keyframe data is required to decode the interframe. We encode both the time of the page and the time of the page it depends on into the granulepos. In order to do this we treat the granulepos as a bitfield as follows: Conrad: /* Granulepos encoding and How seeking really works */ update variable names 2008-11-19T12:57:59Z Granulepos encoding and How seeking really works: update variable names ← Older revision Revision as of 12:57, 19 November 2008 Line 20: Line 20: +---------------------+-------------+ +---------------------+-------------+ - | granule_prev | offset | + | prev_granule | offset | +---------------------+-------------+ +---------------------+-------------+ - Then if a page has time in units of codec granules <tt>granule_curr</tt>, and the page it depends on has time + Then if a page has time in units of codec granules <tt>curr_granule</tt>, and the page it depends on has time - <tt>granule_prev</tt>, we define <tt>offset</tt> as the difference between these: + <tt>prev_granule</tt>, we define <tt>offset</tt> as the difference between these: - <tt>offset = granule_curr - granule_prev</tt> + <tt>offset = curr_granule - prev_granule</tt> We refer to the number of bits used to encode the offset as the "granuleshift". This is fixed for all pages in We refer to the number of bits used to encode the offset as the "granuleshift". This is fixed for all pages in that track (logical bitstream). So we encode the later page's granulepos as: that track (logical bitstream). So we encode the later page's granulepos as: - <tt>granulepos = (granule_prev << granuleshift) | offset</tt> + <tt>granulepos = (prev_granule << granuleshift) | offset</tt> When decoding, we can extract the current_granule from a granulepos by simply adding these fields: When decoding, we can extract the current_granule from a granulepos by simply adding these fields: - <tt>granule = granule_prev + offset</tt> + <tt>granule = prev_granule + offset</tt> Keyframes, and other data with no dependency on earlier packets, are encoded with: Keyframes, and other data with no dependency on earlier packets, are encoded with: - <tt>granule_prev = granule_curr, offset = 0</tt> + <tt>prev_granule = curr_granule, offset = 0</tt> === Procedure for seeking on a single track === === Procedure for seeking on a single track === Line 47: Line 47: # seek to the desired time # seek to the desired time - # read the granule_prev out of the granulepos + # read the prev_granule out of the granulepos - # seek to the time represented by the granule_prev + # seek to the time represented by the prev_granule === Procedure for seeking on a multitrack file === === Procedure for seeking on a multitrack file === Conrad: /* Procedure for seeking on a single track */ update variable names used 2008-11-19T12:55:32Z Procedure for seeking on a single track: update variable names used ← Older revision Revision as of 12:55, 19 November 2008 Line 47: Line 47: # seek to the desired time # seek to the desired time - # read the prev_granule out of the granulepos + # read the granule_prev out of the granulepos - # seek to there + # seek to the time represented by the granule_prev === Procedure for seeking on a multitrack file === === Procedure for seeking on a multitrack file === Conrad: /* Granules and Granuleshift */ 2008-11-19T12:54:24Z Granules and Granuleshift ← Older revision Revision as of 12:54, 19 November 2008 Line 13: Line 13: target time, then choose the bytewise-earliest among these pages. Thus if two pages have the same time, seeking will locate the bytewise-earlier page. target time, then choose the bytewise-earliest among these pages. Thus if two pages have the same time, seeking will locate the bytewise-earlier page. - === Granules and Granuleshift === + ==== Granules and Granuleshift ==== We use the term "granule" to refer to time measured in the units of the codec. For audio codecs this is usually samples, and for video codecs it is frames or fields. We use the term "granule" to refer to time measured in the units of the codec. For audio codecs this is usually samples, and for video codecs it is frames or fields. Conrad: /* Definitions */ expand explanation of granuleshift 2008-11-19T12:54:03Z Definitions: expand explanation of granuleshift ← Older revision Revision as of 12:54, 19 November 2008 Line 10: Line 10: Overload "time" to mean the time represented by a granulepos. Hence the time of a page is the time represented by the page granulepos. Overload "time" to mean the time represented by a granulepos. Hence the time of a page is the time represented by the page granulepos. - In some formats, pages have a dependency on the data of an earlier page; for example in Theora, interframes have + Define "seek" to mean: for each logical bitstream, locate the bytewise-latest page in the bitstream with a time < the - a dependency on an earlier keyframe -- the keyframe data is required to decode the interframe. We encode both the + target time, then choose the bytewise-earliest among these pages. Thus if two pages have the same time, seeking will locate the bytewise-earlier page. - time of the page and the time of the page it depends on into the granulepos. In order to do this we treat the + - granulepos as a bitfield as follows: + - +-----------------+-----------------+ + === Granules and Granuleshift === - | granulepos_prev | offset | + - +-----------------+-----------------+ + - We refer to the number of bits used to encode the offset as the "granuleshift". Then: + We use the term "granule" to refer to time measured in the units of the codec. For audio codecs this is usually samples, and for video codecs it is frames or fields. - <tt>granulepos = (granulepos_prev << granuleshift) | (current_time - granulepos_prev)</tt> + In some formats, pages have a dependency on the data of an earlier page; for example in Theora, interframes have a dependency on an earlier keyframe -- the keyframe data is required to decode the interframe. We encode both the time of the page and the time of the page it depends on into the granulepos. In order to do this we treat the granulepos as a bitfield as follows: - Define "seek" to mean: for each logical bitstream, locate the bytewise-latest page in the bitstream with a time < the + +---------------------+-------------+ - target time, then choose the bytewise-earliest among these pages. Thus if two pages have the same time, seeking will locate the bytewise-earlier page. + | granule_prev | offset | + +---------------------+-------------+ + + Then if a page has time in units of codec granules <tt>granule_curr</tt>, and the page it depends on has time + <tt>granule_prev</tt>, we define <tt>offset</tt> as the difference between these: + + <tt>offset = granule_curr - granule_prev</tt> + + We refer to the number of bits used to encode the offset as the "granuleshift". This is fixed for all pages in + that track (logical bitstream). So we encode the later page's granulepos as: + + <tt>granulepos = (granule_prev << granuleshift) | offset</tt> + + When decoding, we can extract the current_granule from a granulepos by simply adding these fields: + + <tt>granule = granule_prev + offset</tt> + + Keyframes, and other data with no dependency on earlier packets, are encoded with: + + <tt>granule_prev = granule_curr, offset = 0</tt> === Procedure for seeking on a single track === === Procedure for seeking on a single track === Conrad: /* Granulepos encoding and How seeking really works */ 2008-11-19T12:32:47Z Granulepos encoding and How seeking really works ← Older revision Revision as of 12:32, 19 November 2008 Line 5: Line 5: The purpose is to locate the earliest page that is required for rendering a given time offset. The purpose is to locate the earliest page that is required for rendering a given time offset. Due to the fact that two time-seeking operations are required, this procedure is commonly referred to as a "double seek". Due to the fact that two time-seeking operations are required, this procedure is commonly referred to as a "double seek". - === Definitions === === Definitions ===

← Older revision		Revision as of 01:38, 20 November 2008
Line 26:		Line 26:
	<tt>prev_granule</tt>, we define <tt>offset</tt> as the difference between these:		<tt>prev_granule</tt>, we define <tt>offset</tt> as the difference between these:

-	~~<tt>~~offset = curr_granule - prev_granule~~</tt>~~	+	offset = curr_granule - prev_granule

	We refer to the number of bits used to encode the offset as the "granuleshift". This is fixed for all pages in		We refer to the number of bits used to encode the offset as the "granuleshift". This is fixed for all pages in
	that track (logical bitstream). So we encode the later page's granulepos as:		that track (logical bitstream). So we encode the later page's granulepos as:

-	~~<tt>~~granulepos = (prev_granule << granuleshift) \| offset~~</tt>~~	+	granulepos = (prev_granule << granuleshift) \| offset

	When decoding, we can extract the current_granule from a granulepos by simply adding these fields:		When decoding, we can extract the current_granule from a granulepos by simply adding these fields:

-	~~<tt>granule~~ = prev_granule + offset~~</tt>~~	+	curr_granule = prev_granule + offset

	Keyframes, and other data with no dependency on earlier packets, are encoded with:		Keyframes, and other data with no dependency on earlier packets, are encoded with:

-	~~<tt>~~prev_granule = curr_granule, offset = 0~~</tt>~~	+	prev_granule = curr_granule, offset = 0

	=== Procedure for seeking on a single track ===		=== Procedure for seeking on a single track ===

← Older revision		Revision as of 13:00, 19 November 2008
Line 8:		Line 8:
	=== Definitions ===		=== Definitions ===

-	Overload "time" to mean the time represented by a granulepos. Hence the time of a page is the time represented by the page granulepos.	+	Overload '''time''' to mean the time represented by a granulepos. Hence the time of a page is the time represented by the page granulepos.

-	Define "seek" to mean: for each logical bitstream, locate the bytewise-latest page in the bitstream with a time < the	+	Define '''seek''' to mean: for each logical bitstream, locate the bytewise-latest page in the bitstream with a time < the
	target time, then choose the bytewise-earliest among these pages. Thus if two pages have the same time, seeking will locate the bytewise-earlier page.		target time, then choose the bytewise-earliest among these pages. Thus if two pages have the same time, seeking will locate the bytewise-earlier page.

	==== Granules and Granuleshift ====		==== Granules and Granuleshift ====

-	We use the term "granule" to refer to time measured in the units of the codec. For audio codecs this is usually samples, and for video codecs it is frames or fields.	+	We use the term '''granule''' to refer to time measured in the units of the codec. For audio codecs this is usually samples, and for video codecs it is frames or fields.

	In some formats, pages have a dependency on the data of an earlier page; for example in Theora, interframes have a dependency on an earlier keyframe -- the keyframe data is required to decode the interframe. We encode both the time of the page and the time of the page it depends on into the granulepos. In order to do this we treat the granulepos as a bitfield as follows:		In some formats, pages have a dependency on the data of an earlier page; for example in Theora, interframes have a dependency on an earlier keyframe -- the keyframe data is required to decode the interframe. We encode both the time of the page and the time of the page it depends on into the granulepos. In order to do this we treat the granulepos as a bitfield as follows:

← Older revision		Revision as of 12:57, 19 November 2008
Line 20:		Line 20:

	+---------------------+-------------+		+---------------------+-------------+
-	\| ~~granule_prev~~ \| offset \|	+	\| prev_granule \| offset \|
	+---------------------+-------------+		+---------------------+-------------+

-	Then if a page has time in units of codec granules <tt>~~granule_curr~~</tt>, and the page it depends on has time	+	Then if a page has time in units of codec granules <tt>curr_granule</tt>, and the page it depends on has time
-	<tt>~~granule_prev~~</tt>, we define <tt>offset</tt> as the difference between these:	+	<tt>prev_granule</tt>, we define <tt>offset</tt> as the difference between these:

-	<tt>offset = ~~granule_curr~~ - ~~granule_prev~~</tt>	+	<tt>offset = curr_granule - prev_granule</tt>

	We refer to the number of bits used to encode the offset as the "granuleshift". This is fixed for all pages in		We refer to the number of bits used to encode the offset as the "granuleshift". This is fixed for all pages in
	that track (logical bitstream). So we encode the later page's granulepos as:		that track (logical bitstream). So we encode the later page's granulepos as:

-	<tt>granulepos = (~~granule_prev~~ << granuleshift) \| offset</tt>	+	<tt>granulepos = (prev_granule << granuleshift) \| offset</tt>

	When decoding, we can extract the current_granule from a granulepos by simply adding these fields:		When decoding, we can extract the current_granule from a granulepos by simply adding these fields:

-	<tt>granule = ~~granule_prev~~ + offset</tt>	+	<tt>granule = prev_granule + offset</tt>

	Keyframes, and other data with no dependency on earlier packets, are encoded with:		Keyframes, and other data with no dependency on earlier packets, are encoded with:

-	<tt>~~granule_prev~~ = ~~granule_curr~~, offset = 0</tt>	+	<tt>prev_granule = curr_granule, offset = 0</tt>

	=== Procedure for seeking on a single track ===		=== Procedure for seeking on a single track ===
Line 47:		Line 47:

	# seek to the desired time		# seek to the desired time
-	# read the ~~granule_prev~~ out of the granulepos	+	# read the prev_granule out of the granulepos
-	# seek to the time represented by the ~~granule_prev~~	+	# seek to the time represented by the prev_granule

	=== Procedure for seeking on a multitrack file ===		=== Procedure for seeking on a multitrack file ===

← Older revision		Revision as of 12:55, 19 November 2008
Line 47:		Line 47:

	# seek to the desired time		# seek to the desired time
-	# read the ~~prev_granule~~ out of the granulepos	+	# read the granule_prev out of the granulepos
-	# seek to ~~there~~	+	# seek to the time represented by the granule_prev

	=== Procedure for seeking on a multitrack file ===		=== Procedure for seeking on a multitrack file ===

← Older revision		Revision as of 12:54, 19 November 2008
Line 13:		Line 13:
	target time, then choose the bytewise-earliest among these pages. Thus if two pages have the same time, seeking will locate the bytewise-earlier page.		target time, then choose the bytewise-earliest among these pages. Thus if two pages have the same time, seeking will locate the bytewise-earlier page.

-	=== Granules and Granuleshift ===	+	==== Granules and Granuleshift ====

	We use the term "granule" to refer to time measured in the units of the codec. For audio codecs this is usually samples, and for video codecs it is frames or fields.		We use the term "granule" to refer to time measured in the units of the codec. For audio codecs this is usually samples, and for video codecs it is frames or fields.

← Older revision		Revision as of 12:54, 19 November 2008
Line 10:		Line 10:
	Overload "time" to mean the time represented by a granulepos. Hence the time of a page is the time represented by the page granulepos.		Overload "time" to mean the time represented by a granulepos. Hence the time of a page is the time represented by the page granulepos.

-	~~In some formats~~, ~~pages have a dependency on~~ the ~~data of an earlier~~ page~~; for example~~ in ~~Theora, interframes have~~	+	Define "seek" to mean: for each logical bitstream, locate the bytewise-latest page in the bitstream with a time < the
-	a ~~dependency on an earlier keyframe -- the keyframe data is required to decode the interframe. We encode both~~ the	+	target time, then choose the bytewise-earliest among these pages. Thus if two pages have the same time, seeking will locate the bytewise-earlier page.
-	time of the ~~page and~~ the time of the page ~~it depends on into the granulepos~~. ~~In order to do this we treat the~~	+
-	~~granulepos as a bitfield as follows:~~	+

-	~~+-----------------+-----------------+~~	+	=== Granules and Granuleshift ===
-	~~\| granulepos_prev \| offset \|~~	+
-	~~+-----------------+-----------------+~~	+

-	We refer to the ~~number~~ of ~~bits used to encode~~ the ~~offset as the "granuleshift"~~. ~~Then:~~	+	We use the term "granule" to refer to time measured in the units of the codec. For audio codecs this is usually samples, and for video codecs it is frames or fields.

-	~~<tt>granulepos = (granulepos_prev << granuleshift) \| (current_time~~ - ~~granulepos_prev)</tt>~~	+	In some formats, pages have a dependency on the data of an earlier page; for example in Theora, interframes have a dependency on an earlier keyframe -- the keyframe data is required to decode the interframe. We encode both the time of the page and the time of the page it depends on into the granulepos. In order to do this we treat the granulepos as a bitfield as follows:

-	~~Define "seek" to mean: for each logical bitstream, locate the bytewise~~-~~latest page in the bitstream with~~ a time < the	+	+---------------------+-------------+
-	~~target~~ time, ~~then choose~~ the ~~bytewise-earliest among~~ these ~~pages~~. ~~Thus if two~~ pages ~~have~~ the ~~same time~~, ~~seeking will locate~~ the ~~bytewise-~~earlier ~~page.~~	+	\| granule_prev \| offset \|
		+	+---------------------+-------------+
		+
		+	Then if a page has time in units of codec granules <tt>granule_curr</tt>, and the page it depends on has time
		+	<tt>granule_prev</tt>, we define <tt>offset</tt> as the difference between these:
		+
		+	<tt>offset = granule_curr - granule_prev</tt>
		+
		+	We refer to the number of bits used to encode the offset as the "granuleshift". This is fixed for all pages in
		+	that track (logical bitstream). So we encode the later page's granulepos as:
		+
		+	<tt>granulepos = (granule_prev << granuleshift) \| offset</tt>
		+
		+	When decoding, we can extract the current_granule from a granulepos by simply adding these fields:
		+
		+	<tt>granule = granule_prev + offset</tt>
		+
		+	Keyframes, and other data with no dependency on earlier packets, are encoded with:
		+
		+	<tt>granule_prev = granule_curr, offset = 0</tt>

	=== Procedure for seeking on a single track ===		=== Procedure for seeking on a single track ===

← Older revision		Revision as of 12:32, 19 November 2008
Line 5:		Line 5:
	The purpose is to locate the earliest page that is required for rendering a given time offset.		The purpose is to locate the earliest page that is required for rendering a given time offset.
	Due to the fact that two time-seeking operations are required, this procedure is commonly referred to as a "double seek".		Due to the fact that two time-seeking operations are required, this procedure is commonly referred to as a "double seek".
-

	=== Definitions ===		=== Definitions ===

GranulePosAndSeeking - Revision history

Gmaxwell: /* But how do I "seek to the desired time"? */

Gmaxwell: on low level seeking

Rillian: /* Granules and Granuleshift */ Give the explanded granulepos->granule calculation

Rillian: /* Granules and Granuleshift */ remove redundant tags

Conrad: /* Definitions */

Conrad: /* Granulepos encoding and How seeking really works */ update variable names

Conrad: /* Procedure for seeking on a single track */ update variable names used

Conrad: /* Granules and Granuleshift */

Conrad: /* Definitions */ expand explanation of granuleshift

Conrad: /* Granulepos encoding and How seeking really works */

Rillian: /* Granules and Granuleshift */ remove redundant `tags`