MultimediaWiki - User contributions [en]

FFmpeg / Libav Summer Of Code

2007-10-20T22:24:56Z

Ods15: /* Vorbis Encoder */

The [[FFmpeg]] project has been a participant in the [http://code.google.com/soc/ Google Summer of Code] program during the 2006 and 2007 seaons.

* [[FFmpeg Summer Of Code 2006|2006 project page]]
* [[FFmpeg Summer Of Code 2007|2007 project page]]

Each accepted project is developed in its own sandbox, separate from the main FFmpeg codebase. Naturally, the end goal of each of the accepted FFmpeg projects ought to be to have that code in shape for acceptance into the production codebase. This page tracks the status of each project.

== 2006 Projects ==

=== VC-1 Decoder ===
* Student: [[User:Kostya|Kostya Shishkov]]
* Mentor: [[User:Multimedia Mike|Mike Melanson]]
* Status: Accepted into the FFmpeg codebase.

=== AMR Decoder ===
* Student: [[User:superdump|Robert Swain]]
* Mentor: [[User:Merbanan|Benjamin Larsson]]
* Status: unfinished but slowly progressing

=== AC3 Decoder ===
* Student: [[User:Cloud9|Kartikey Mahendra BHATT]]
* Mentor: [[User:Merbanan|Benjamin Larsson]]
* Status: Not finished by the student but picked up by Justin Ruggles and committed to FFmpeg.

=== AAC Decoder ===
* Student: Maxim Gavrilov
* Mentor: [[User:ods15|Oded Shimon]]
* Status: unfinished, orphaned

=== Vorbis Encoder ===
* Student: Mathew Philip
* Mentor: [[User:ods15|Oded Shimon]]
* Status: Not finished by the student but picked up by [[User:ods15|Oded Shimon]] and committed to FFmpeg.

== 2007 Projects ==

=== RealVideo 4 Decoder ===
* Student: [[User:Kostya|Kostya Shishkov]]
* Mentor: [[User:Multimedia Mike|Mike Melanson]]
* Status: Not in FFmpeg codebase yet; project goal has also morphed to include RealVideo 3 decoder since the 2 schemes are so similar.

=== QCELP Decoder ===
* Student: [[User:Reynaldo|Reynaldo Verdejo Pinochet]]
* Mentor: [[User:Merbanan|Benjamin Larsson]]
* Status: slowly progressing, it's working though

=== Matroska Muxer ===
* Student: David Conrad
* Mentor: [[User:aurel|Aurélien Jacobs]]
* Status: Accepted into the FFmpeg codebase.

=== Video Filter API ===
* Student: [[User:Koorogi|Bobby Bingham]]
* Mentor: [[User:Merbanan|Benjamin Larsson]] and Michael Niedermayer
* Status: Working code for ffplay, colorspace negotiation is missing though, worked on by Vitor Sessak

=== E-AC3 Decoder ===
* Student: Bartlomiej Wolowiec
* Mentor: Justin Ruggles
* Status:

=== JPEG 2000 Encoder and Decoder ===
* Student: Kamil Nowosad
* Mentor: [[User:pengvado|Loren Merritt]]
* Status: The code is working but all features aren't supported.

=== Dirac Encoder and Decoder ===
* Student: Marco Gerards
* Mentor: [[User:Lu_zero|Luca Barbato]]
* Status:

=== TS Muxer ===
* Student: Xiaohui Sun
* Mentor: [[User:bcoudurier|Baptiste Coudurier]]
* Status: Changes requested during the review process for FFmpeg inclusion were never made, then the student disappeared.

NUT

2006-09-12T22:26:34Z

Ods15: /* Bounds of linear search */ fix <nowiki>

* Extensions: nut
* Website: http://www.nut.hu/

NUT is a container format under construction by [[MPlayer]] and [[FFmpeg]] developers.
Its main goals are to be simple to parse and easy to implement, flexible regarding the kind of codec supported and error-resistant while maintaining the smallest possible overhead.

== NUT seeking algo in libnut ==

=== Step 1 - Binary search and linear interpolation ===

==== Startup ====
Go to beginning of file if first syncpoint has not been found, and then go to EOF and search backward to find last syncpoint.
Pick the closest possible syncpoints for requested pts from syncpoint cache, one higher and one lower. If requested pts is lower than first syncpoint or higher than last syncpoint, then seek to either of those syncpoints and end seek.

Binary search is ended when the entire region between the 2 syncpoints picked has been scanned. Which could even be before it has begun thanks to syncpoint cache.

==== Guess position ====
Best results have been achieved by combining both linear interpolation and binary search, giving most of the weight to interpolation.

;hi, hi_pd: file position and timestamp of the top edge of the binary search.
;lo, lo_pd: file position and timestamp of the bottom edge of the binary search.
;time_pos: Requested pts.
;guess: beginning of linear search for syncpoint.

#define INTERPOLATE_WEIGHT (19./20)
if (hi - lo < nut->max_distance*2) guess = lo + 16;
else { // linear interpolation
double a = (double)(hi - lo) / (hi_pd - lo_pd);
guess = lo + a * (time_pos - lo_pd);
guess = guess * INTERPOLATE_WEIGHT + (lo+hi)/2 * (1 - INTERPOLATE_WEIGHT);
if (hi - guess < nut->max_distance*2) guess = hi - nut->max_distance*2; //(lo + hi)/2;
}
if (guess < lo + 16) guess = lo + 16;

The first conditional prevents too much recursing when the distance is already low. The last conditional prevents an infinite loop of syncpoint search constantly finding ''lo'' and achieving nothing.

==== Binary search ====
Now, find a syncpoint, bounded between ''guess'' and ''hi''. If it has a timestamp higher than requested pts, then replace ''hi'' and ''hi_pd'', otherwise replace ''lo'' and ''lo_pd''.
If a syncpoint was not found between ''guess'' and ''hi'', then, if ''guess'' is smaller or equal to ''lo + 16'', then you have scanned the entire area between ''lo'' and ''hi'', and your binary search is done. Otherwise, replace ''hi'' with ''guess'' and repeat the binary search.

After finding the 2 closest syncpoints bounding your requested pts, the bounds of linear are search are:

*start = lo_s.pos - (lo_s.back_ptr * 16 + 15);
*end = hi_s.pos;
*stopper = hi_s;

''stopper'' is used later to end linear search prematurely. Note that it is the '''top''' edge of binary search, meaning, it has a timestamp higher than requested pts.

=== Step 2 - Linear search ===

==== Bounds of linear search ====
Linear search of course ends at ''end'', however, it can end earlier:
* When you find a frame of any stream, with a dts higher than requested pts.
* When you find a frame for '''all''' active streams with a pts higher than requested pts.
* When you find a syncpoint immediately following the syncpoint pointed to by ''stopper'''s back_ptr, (from here on this syncpoint will be called ''stopper_syncpoint'') '''and''' all streams are active.
* When you reach ''stopper_syncpoint'', and you have not found a keyframe for any '''non'''-active between ''stopper''<nowiki>'</nowiki>s back_ptr and ''stopper_syncpoint'', with a pts lower than ''stopper.timestamp''. The reason for this is that ''stopper'' did not point because to ''stopper_syncpoint'' can only be because of active stream keyframes, and not non-active ones.
* When you find a keyframe for all '''non'''-active streams after ''stopper_syncpoint'' with a pts lower than ''stopper.timestamp'', which had a keyframe in the region in the previous condition. The logic is:
** ''stopper.timestamp'' is higher than requested pts.
** ''stopper_syncpoint'' is '''not''' the syncpoint pointed to by ''stopper.back_ptr'', but the one immediately following.
** If there was a keyframe for every non active stream after ''stopper_syncpoint'', with a pts lower than ''stopper.timestamp'', then the reason ''stopper'' does not point to ''stopper_syncpoint'' must be that there are no keyframes for '''active''' streams with a pts lower than ''stopper.timestamp'' after ''stopper_syncpoint''.
** There might be more keyframes in the region with a pts higher than ''stopper.timestamp'', but those are irrelevant because they are higher than requested pts.

The last 3 conditions can be phrased differently:
* When saying keyframes, only keyframes with a pts lower than ''stopper.timestamp'' are intended. Any other keyframes are irrelevant.
* The region ''stopper.back_ptr'' to ''stopper_syncpoint'' has a set of keyframes between it. These keyframes are the ones responsible for ''stopper'' pointing to ''stopper.back_ptr'' and not ''stopper_syncpoint''.
* If all streams are active, then it's impossible for there to be better keyframes for '''all''' active streams between ''stopper_syncpoint'' to the end of the linear search, because if there was, ''stopper.back_ptr'' would point there.
* If some streams are inactive, but none of them have a keyframe in the region specified above, then the keyframes responsible for ''stopper'' pointing to ''stopper.back_ptr'' are only from active streams, so again it is impossible there is a better position later in the linear search.
* If some streams are inactive, and some of them '''do''' have a keyframe in the region specified above, then those keyframes are ''possibly'' responsible for ''stopper'' pointing to ''stopper.back_ptr''. However, if we find more keyframes of those same inactive streams '''after''' the region, then they had nothing to do with ''stopper.back_ptr'', and again the condition is met.

==== Linear search implementation ====

# Start at ''start''.
# Search for syncpoint. If it is further than ''start + 15'', then the file is errored, and you can start playing immediately from this syncpoint.
# Perform full demuxing, buffering everything read. If you encounter any NUT error during demuxing, seek back to the syncpoint after ''start'' and end seek.
# On every syncpoint, flush the buffer and cache the syncpoint position.
#* If this syncpoint is ''stopper_syncpoint'', then do not flush the buffer, as it would be possible the linear search would end immediatelty afterwards and a second underlying seek would not be necessary.
# When finding keyframe of active stream with pts lower than requested pts, store position of keyframe. Discard previous value.
# End linear search as necessary by bounds given above.
# Pick the lowest value from positions of keyframes for active streams. This is the final position.
# Seek to closest syncpoint before the final position, preform a minimal demuxing until final position (to get proper last_pts context across all streams).
#* With luck this seek will not need an underlying seek, if you have not flushed the buffer since the requested position.
#* In most common case, ''stopper.back_ptr'' points to same syncpoint as the start of the linear search, as both syncpoints point to the same rare video keyframe.
#* If only video stream is active and the only non active stream is audio, you will most likely end your linear search immediately after ''stopper_syncpoint'' by finding an audio keyframe. Afterwards you will rewind right back to ''start'', and, since buffer hasn't been flushed, this will not need an underlying seek.

=== Index ===
With index, binary search step is skipped, and a much more limited linear search used, between two immediate syncpoints. The syncpoint picked is the highest possible one that has a keyframe for each active stream past the syncpoint with a pts lower than requested pts. The end of the linear search is the syncpoint immediately following.

=== Dynamic Index ===
Create the index in the same manner as creating the index in the muxer, remembering keyframes and EOR at syncpoint positions.
With one big difference - dynamic index can have gaps, thanks to seeking. Every syncpiont entry in the dynamic index has a flag indicating if it has a "unresearched region" gap from last syncpoint.

In seeking, dynamic index is used in the same manner as complete index. However, when deciding a syncpoint, the entire range of the syncpoint picked until the first syncpoint with a pts higher than requested is checked for having been already researched. If a "hole" is found anywhere in this range, dynamic index is disregarded and full binary search is performed.

=== End of Relevance (EOR) ===
Behavior with linear search:
* Treat EOR frames same as keyframes. Seeing an EOR frame for an active stream causes the stream to be ignored until the next keyframe of same stream.
* If all active streams are EOR by end of linear search, just use start of linear search as final seeking position.

For index:
* When picking the correct syncpoint to start linear search, ignore streams which have EOR with pts lower than requested pts and no keyframe with pts lower than requested pts.
* If all active streams are EOR, pick the syncpoint immediately before the syncpoint with the last EOR across all streams with pts lower than requested pts.

[[Category:Container Formats]]

User talk:Ods15

2006-04-01T06:34:27Z

Ods15: reply to diego

Oded, you have removed a little more than just spam from the [[NUT]] page... -- [[User:DonDiego|DonDiego]] 11:05, 29 March 2006 (EST)
:Heh, I forgot you don't accept my mails, I sent you this e-mail:
Uhh... no I didn't
Look carefully, I removed multiple data. (Am I missing something here or are you?
Look exactly at the data that I removed and what is left)
:-- [[User:Ods15|ods15]] 01:34, 1 April 2006 (EST)

NUT

2006-03-27T08:08:15Z

Ods15: Revert spam

* Extensions: nut
* Website: http://www.nut.hu/

NUT is a container format under construction by [[MPlayer]] and [[FFmpeg]] developers.
Its main goals are to be simple, flexible and error-resistant while maintaining the smallest possible overhead.

== NUT seeking algo in libnut ==

=== Step 1 - Binary search and linear interpolation ===

==== Startup ====
Go to beginning of file if first syncpoint has not been found, and then go to EOF and search backward to find last syncpoint.
Pick the closest possible syncpoints for requested pts from syncpoint cache, one higher and one lower. If requested pts is lower than first syncpoint or higher than last syncpoint, then seek to either of those syncpoints and end seek.

Binary search is ended when the entire region between the 2 syncpoints picked has been scanned. Which could even be before it has begun thanks to syncpoint cache.

==== Guess position ====
Best results have been achieved by combining both linear interpolation and binary search, giving most of the weight to interpolation.

;hi, hi_pd: file position and timestamp of the top edge of the binary search.
;lo, lo_pd: file position and timestamp of the bottom edge of the binary search.
;time_pos: Requested pts.
;guess: beginning of linear search for syncpoint.

#define INTERPOLATE_WEIGHT (19./20)
if (hi - lo < nut->max_distance*2) guess = lo + 16;
else { // linear interpolation
double a = (double)(hi - lo) / (hi_pd - lo_pd);
guess = lo + a * (time_pos - lo_pd);
guess = guess * INTERPOLATE_WEIGHT + (lo+hi)/2 * (1 - INTERPOLATE_WEIGHT);
if (hi - guess < nut->max_distance*2) guess = hi - nut->max_distance*2; //(lo + hi)/2;
}
if (guess < lo + 16) guess = lo + 16;

The first conditional prevents too much recursing when the distance is already low. The last conditional prevents an infinite loop of syncpoint search constantly finding ''lo'' and achieving nothing.

==== Binary search ====
Now, find a syncpoint, bounded between ''guess'' and ''hi''. If it has a timestamp higher than requested pts, then replace ''hi'' and ''hi_pd'', otherwise replace ''lo'' and ''lo_pd''.
If a syncpoint was not found between ''guess'' and ''hi'', then, if ''guess'' is smaller or equal to ''lo + 16'', then you have scanned the entire area between ''lo'' and ''hi'', and your binary search is done. Otherwise, replace ''hi'' with ''guess'' and repeat the binary search.

After finding the 2 closest syncpoints bounding your requested pts, the bounds of linear are search are:

*start = lo_s.pos - (lo_s.back_ptr * 16 + 15);
*end = hi_s.pos;
*stopper = hi_s;

''stopper'' is used later to end linear search prematurely. Note that it is the '''top''' edge of binary search, meaning, it has a timestamp higher than requested pts.

=== Step 2 - Linear search ===

==== Bounds of linear search ====
Linear search of course ends at ''end'', however, it can end earlier:
* When you find a frame of any stream, with a dts higher than requested pts.
* When you find a frame for '''all''' active streams with a pts higher than requested pts.
* When you find a syncpoint immediately following the syncpoint pointed to by ''stopper'''s back_ptr, (from here on this syncpoint will be called ''stopper_syncpoint'') '''and''' all streams are active.
* When you reach ''stopper_syncpoint'', and you have not found a keyframe for any '''non'''-active between ''stopper''<nowiki>'</nowiki>s back_ptr and ''stopper_syncpoint'', with a pts lower than ''stopper.timestamp''. The reason for this is that ''stopper'' did not point because to ''stopper_syncpoint'' can only be because of active stream keyframes, and not non-active ones.
* When you find a keyframe for all '''non'''-active streams after ''stopper_syncpoint'' with a pts lower than ''stopper.timestamp'', which had a keyframe in the region in the previous condition. The logic is:
** ''stopper.timestamp'' is higher than requested pts.
** ''stopper_syncpoint'' is '''not''' the syncpoint pointed to by ''stopper.back_ptr'', but the one immediately following.
** If there was a keyframe for every non active stream after ''stopper_syncpoint'', with a pts lower than ''stopper.timestamp'', then the reason ''stopper'' does not point to ''stopper_syncpoint'' must be that there are no keyframes for '''active''' streams with a pts lower than ''stopper.timestamp'' after ''stopper_syncpoint''.
** There might be more keyframes in the region with a pts higher than ''stopper.timestamp'', but those are irrelevant because they are higher than requested pts.

The last 3 conditions can be phrased differently:
* When saying keyframes, only keyframes with a pts lower than ''stopper.timestamp'' are intended. Any other keyframes are irrelevant.
* The region ''stopper.back_ptr'' to ''stopper_syncpoint'' has a set of keyframes between it. These keyframes are the ones responsible for ''stopper'' pointing to ''stopper.back_ptr'' and not ''stopper_syncpoint''.
* If all streams are active, then it's impossible for there to be better keyframes for '''all''' active streams between ''stopper_syncpoint'' to the end of the linear search, because if there was, ''stopper.back_ptr'' would point there.
* If some streams are inactive, but none of them have a keyframe in the region specified above, then the keyframes responsible for ''stopper'' pointing to ''stopper.back_ptr'' are only from active streams, so again it is impossible there is a better position later in the linear search.
* If some streams are inactive, and some of them '''do''' have a keyframe in the region specified above, then those keyframes are ''possibly'' responsible for ''stopper'' pointing to ''stopper.back_ptr''. However, if we find more keyframes of those same inactive streams '''after''' the region, then they had nothing to do with ''stopper.back_ptr'', and again the condition is met.

==== Linear search implementation ====

# Start at ''start''.
# Search for syncpoint. If it is further than ''start + 15'', then the file is errored, and you can start playing immediately from this syncpoint.
# Perform full demuxing, buffering everything read. If you encounter any NUT error during demuxing, seek back to the syncpoint after ''start'' and end seek.
# On every syncpoint, flush the buffer and cache the syncpoint position.
#* If this syncpoint is ''stopper_syncpoint'', then do not flush the buffer, as it would be possible the linear search would end immediatelty afterwards and a second underlying seek would not be necessary.
# When finding keyframe of active stream with pts lower than requested pts, store position of keyframe. Discard previous value.
# End linear search as necessary by bounds given above.
# Pick the lowest value from positions of keyframes for active streams. This is the final position.
# Seek to closest syncpoint before the final position, preform a minimal demuxing until final position (to get proper last_pts context across all streams).
#* With luck this seek will not need an underlying seek, if you have not flushed the buffer since the requested position.
#* In most common case, ''stopper.back_ptr'' points to same syncpoint as the start of the linear search, as both syncpoints point to the same rare video keyframe.
#* If only video stream is active and the only non active stream is audio, you will most likely end your linear search immediately after ''stopper_syncpoint'' by finding an audio keyframe. Afterwards you will rewind right back to ''start'', and, since buffer hasn't been flushed, this will not need an underlying seek.

=== Index ===
With index, binary search step is skipped, and a much more limited linear search used, between two immediate syncpoints. The syncpoint picked is the highest possible one that has a keyframe for each active stream past the syncpoint with a pts lower than requested pts. The end of the linear search is the syncpoint immediately following.

=== Dynamic Index ===
Create the index in the same manner as creating the index in the muxer, remembering keyframes and EOR at syncpoint positions.
With one big difference - dynamic index can have gaps, thanks to seeking. Every syncpiont entry in the dynamic index has a flag indicating if it has a "unresearched region" gap from last syncpoint.

In seeking, dynamic index is used in the same manner as complete index. However, when deciding a syncpoint, the entire range of the syncpoint picked until the first syncpoint with a pts higher than requested is checked for having been already researched. If a "hole" is found anywhere in this range, dynamic index is disregarded and full binary search is performed.

=== End of Relevance (EOR) ===
Behavior with linear search:
* Treat EOR frames same as keyframes. Seeing an EOR frame for an active stream causes the stream to be ignored until the next keyframe of same stream.
* If all active streams are EOR by end of linear search, just use start of linear search as final seeking position.

For index:
* When picking the correct syncpoint to start linear search, ignore streams which have EOR with pts lower than requested pts and no keyframe with pts lower than requested pts.
* If all active streams are EOR, pick the syncpoint immediately before the syncpoint with the last EOR across all streams with pts lower than requested pts.

[[Category:Container Formats]]

Understanding AAC

2006-03-16T19:00:40Z

Ods15: /* Overview */ Explain bitpacking

This portion of the MultimediaWiki tracks an effort to get an open, freely-distributable, usable, and clear specification for the Advanced Audio Coding (AAC) format. The goal is to understand enough details about the format to create new decoder implementations that can handle production bitstreams starting with data packaged inside MPEG-4 files.

The homepage for libfaad has a Wiki that provides some decent details regarding the background coding concepts:
[http://www.audiocoding.com/modules/wiki/?page=AAC http://www.audiocoding.com/modules/wiki/?page=AAC]

More possible details here: [http://www.ietf.org/proceedings/99nov/I-D/draft-ietf-avt-rtp-mpeg2aac-00.txt http://www.ietf.org/proceedings/99nov/I-D/draft-ietf-avt-rtp-mpeg2aac-00.txt] or [http://tools.ietf.org/wg/avt/draft-ietf-avt-rtp-mpeg2aac/ http://tools.ietf.org/wg/avt/draft-ietf-avt-rtp-mpeg2aac/]

== Overview ==
AAC is a perceptual audio codec which means that it throws away certain information during the compression process, information that has been deemed less important.

Surface details of the format can be found at Wikipedia: [http://en.wikipedia.org/wiki/Advanced_Audio_Coding http://en.wikipedia.org/wiki/Advanced_Audio_Coding]

Conformance vectors can be obtained here: [ftp://mpaudconf:adif2mp4@ftp.iis.fhg.de/ ftp://mpaudconf:adif2mp4@ftp.iis.fhg.de/]

AAC is a variable bitrate (VBR) block-based codec where each block decodes to 1024 time-domain samples. Allegedly, each frame stands alone and does not depend on previous frames (whereas many perceptual audio codecs overlap data with the previous frame).

AAC includes a variety of profiles:
* low complexity (LC): reported to be the simplest (Apple iTunes files)
* main (MAIN): LC profile with backwards prediction
* sample-rate scalability (SRS): submitted by Sony and reportedly similar to ATRAC/3
* long term prediction (LTP): main profile with forward prediction
* high efficiency (HE, HE-AAC, aacPlus): uses spectral band replication (SBR) and may use parametric stereo
* FAAD refers to another profile named LD, possibly the same as SRS
* provisions all over the libfaad source for error recovery (ER)
== Bitpacking ==
Done in most significant byte first, most significant bit first. Example:
5 bits: 2 (00010)
4 bits: 4 (0100)
4 bits: 2 (0010)
3 bits: 0 (000)

Byte 1: 00010010
Byte 2: 00010000

00010010 00010000
[ 2 ][ 4 ][2 ][0]

== Packaging/Encapsulation And Setup Data==
There is a variety of methods for packaging AAC data from transport. 2 methods used in packaging raw streams are to use ADTS and ADIF headers. The libfaad knowledge base also makes reference to LATM and LOAS packaging.

Much AAC data is encapsulated in MPEG-4 files which is an extension of the [[Apple QuickTime]] container format. the MPEG-4 file will have an audio 'trak' atom which will contain a 'stsd' description atom which will contain an 'mp4a' atom which will contain an 'esds' atom. Part of the esds atom contains the setup data for associated AAC stream. '''(TODO: need to document the precise format and method for obtaining the setup data.)''' This setup data is generally 2 bytes. This setup data has the following layout:
5 bits: object type
4 bits: frequency index
if (frequency index == 15)
24 bits: frequency
4 bits: channel configuration
1 bit: frame length flag
1 bit: dependsOnCoreCoder
1 bit: extensionFlag
These are the possible object types:
* 0: NULL
* 1: AAC Main
* 2: AAC Low complexity
* 3: AAC SSR
* 4: AAC Long term prediction
* 5: AAC High efficiency
* 6: Scalable
* 7: [[TwinVQ]]
* 8: CELP
* 9: HVXC
* 10: Reserved
* 11: Reserved
* 12: TTSI
* 13: Main synthetic
* 14: Wavetable synthesis
* 15: General MIDI
* 16: Algorithmic Synthesis and Audio FX
* 17: AAC Low complexity with error recovery
* 18: Reserved
* 19: AAC Long term prediction with error recovery
* 20: AAC scalable with error recovery
* 21: TwinVQ with error recovery
* 22: BSAC with error recovery
* 23: AAC LD with error recovery
* 24: CELP with error recovery
* 25: HXVC with error recovery
* 26: HILN with error recovery
* 27: Parametric with error recovery
* 28: Reserved
* 29: Reserved
* 30: Reserved
* 31: Reserved
There are 13 supported frequencies (frequency indices 13..14 are invalid):
* 0: 96000 Hz
* 1: 88200 Hz
* 2: 64000 Hz
* 3: 48000 Hz
* 4: 44100 Hz
* 5: 32000 Hz
* 6: 24000 Hz
* 7: 22050 Hz
* 8: 16000 Hz
* 9: 12000 Hz
* 10: 11025 Hz
* 11: 8000 Hz
* 12: 7350 Hz
* 15: frequency is written explictly
These are the channel configurations:
* 0: custom configuration '''(TODO)'''
* 1: 1 channel: front-center
* 2: 2 channels: front-left, front-right
* 3: 3 channels: front-center, front-left, front-right
* 4: 4 channels: front-center, front-left, front-right, back-center
* 5: 5 channels: front-center, front-left, front-right, back-left, back-right
* 6: 6 channels: front-center, front-left, front-right, back-left, back-right, LFE-channel
* 7: 8 channels: front-center, front-left, front-right, side-left, side-right, back-left, back-right, LFE-channel
frame length flag:
* 0: Each packet contains 1024 samples
* 1: Each packet contains 960 samples

== Frames And Syntax Elements ==
In an MPEG-4 file, the AAC data is broken up into a series of variable length frames.

An AAC frame is comprised of blocks called syntax elements. Read the first 3 bits from the frame's bitstream to find the first element type. Decode the element. Proceed to read the first 3 bits of the next element and repeat the decoding process until the frame is depleted.

There are 8 different syntax elements:
* 0 SCE single channel element (codes a single audio channel)
* 1 CPE channel pair element (codes stereo signal)
* 2 CCE something to do with channel coupling, not implemented in libfaad2
* 3 LFE low-frequency effects? referenced as "special effects" in RTP doc
* 4 DSE data stream element (user data)
* 5 PCE program configuration element (describe bitstream)
* 6 FIL fill element (pad space/extension data)
* 7 END marks the end of the frame
This is an example layout for a 5.1 audio stream:
SCE CPE CPE LFE END
indicates
center - left/right - surround left/right - lfe - end
An ID within the respective CPE blocks indicates its channel assignments (front vs. surround).

== Decoding Process ==
First, let's list a few basic terms that FAAD2 uses throughout its decoding process:

* ics = individual channel stream, the basic audio unit that FAAD2 is concerned with
* ms = any parameter with this in its name deals with mid/side coding
* sfb = probably something to do with scale factors
* swb = scalefactor window band
* is = intensity stereo

As mentioned above, the ics is an important data structure in AAC decoding. These are its fields, according to FAAD2:

max_sfb
num_swb
num_window_groups
num_windows
window_sequence
window_group_length[8]
window_shape
scale_factor_grouping
section_sfb_offset[8][8*15]
swb_offset
section_codebook[8][15*8]
section_start[8][15*8]
section_end[8][15*8]
sfb_codebook[8][15*8]
number_sections[8] ''// number of sections in a group''
global_gain
scale_factors[8][51] ''// FAAD2 comment: [0..255]?''
ms_mask_present
ms_used[MAX_WINDOW_GROUPS][MAX_SFB] ''// dimensions = [8][51]''
noise_used
pulse_data_present
tns_data_present
gain_control_data_present
predictor_data_present
pulse_info pulse
tns_info tns
''data structures for main profile, document later''
''data structures for LTP, document later''
''data structures for SSR, document later''
''data structures for error resilience, document later''

These pages detail the process for decoding the various syntax elements:

* [[Decoding AAC SCE and LFE]]
* [[Decoding AAC CPE]]
** [[Reconstructing AAC CPE]]
* Decoding AAC CCE
* Decoding AAC DSE
* Decoding AAC PCE
* [[Decoding AAC FIL]]
* [[Decoding AAC END]]

Understanding AAC

2006-03-16T18:56:20Z

Ods15: /* Packaging/Encapsulation And Setup Data */ Corrections, updates

This portion of the MultimediaWiki tracks an effort to get an open, freely-distributable, usable, and clear specification for the Advanced Audio Coding (AAC) format. The goal is to understand enough details about the format to create new decoder implementations that can handle production bitstreams starting with data packaged inside MPEG-4 files.

The homepage for libfaad has a Wiki that provides some decent details regarding the background coding concepts:
[http://www.audiocoding.com/modules/wiki/?page=AAC http://www.audiocoding.com/modules/wiki/?page=AAC]

More possible details here: [http://www.ietf.org/proceedings/99nov/I-D/draft-ietf-avt-rtp-mpeg2aac-00.txt http://www.ietf.org/proceedings/99nov/I-D/draft-ietf-avt-rtp-mpeg2aac-00.txt] or [http://tools.ietf.org/wg/avt/draft-ietf-avt-rtp-mpeg2aac/ http://tools.ietf.org/wg/avt/draft-ietf-avt-rtp-mpeg2aac/]

== Overview ==
AAC is a perceptual audio codec which means that it throws away certain information during the compression process, information that has been deemed less important.

Surface details of the format can be found at Wikipedia: [http://en.wikipedia.org/wiki/Advanced_Audio_Coding http://en.wikipedia.org/wiki/Advanced_Audio_Coding]

Conformance vectors can be obtained here: [ftp://mpaudconf:adif2mp4@ftp.iis.fhg.de/ ftp://mpaudconf:adif2mp4@ftp.iis.fhg.de/]

AAC is a variable bitrate (VBR) block-based codec where each block decodes to 1024 time-domain samples. Allegedly, each frame stands alone and does not depend on previous frames (whereas many perceptual audio codecs overlap data with the previous frame).

AAC includes a variety of profiles:
* low complexity (LC): reported to be the simplest (Apple iTunes files)
* main (MAIN): LC profile with backwards prediction
* sample-rate scalability (SRS): submitted by Sony and reportedly similar to ATRAC/3
* long term prediction (LTP): main profile with forward prediction
* high efficiency (HE, HE-AAC, aacPlus): uses spectral band replication (SBR) and may use parametric stereo
* FAAD refers to another profile named LD, possibly the same as SRS
* provisions all over the libfaad source for error recovery (ER)

== Packaging/Encapsulation And Setup Data==
There is a variety of methods for packaging AAC data from transport. 2 methods used in packaging raw streams are to use ADTS and ADIF headers. The libfaad knowledge base also makes reference to LATM and LOAS packaging.

Much AAC data is encapsulated in MPEG-4 files which is an extension of the [[Apple QuickTime]] container format. the MPEG-4 file will have an audio 'trak' atom which will contain a 'stsd' description atom which will contain an 'mp4a' atom which will contain an 'esds' atom. Part of the esds atom contains the setup data for associated AAC stream. '''(TODO: need to document the precise format and method for obtaining the setup data.)''' This setup data is generally 2 bytes. This setup data has the following layout:
5 bits: object type
4 bits: frequency index
if (frequency index == 15)
24 bits: frequency
4 bits: channel configuration
1 bit: frame length flag
1 bit: dependsOnCoreCoder
1 bit: extensionFlag
These are the possible object types:
* 0: NULL
* 1: AAC Main
* 2: AAC Low complexity
* 3: AAC SSR
* 4: AAC Long term prediction
* 5: AAC High efficiency
* 6: Scalable
* 7: [[TwinVQ]]
* 8: CELP
* 9: HVXC
* 10: Reserved
* 11: Reserved
* 12: TTSI
* 13: Main synthetic
* 14: Wavetable synthesis
* 15: General MIDI
* 16: Algorithmic Synthesis and Audio FX
* 17: AAC Low complexity with error recovery
* 18: Reserved
* 19: AAC Long term prediction with error recovery
* 20: AAC scalable with error recovery
* 21: TwinVQ with error recovery
* 22: BSAC with error recovery
* 23: AAC LD with error recovery
* 24: CELP with error recovery
* 25: HXVC with error recovery
* 26: HILN with error recovery
* 27: Parametric with error recovery
* 28: Reserved
* 29: Reserved
* 30: Reserved
* 31: Reserved
There are 13 supported frequencies (frequency indices 13..14 are invalid):
* 0: 96000 Hz
* 1: 88200 Hz
* 2: 64000 Hz
* 3: 48000 Hz
* 4: 44100 Hz
* 5: 32000 Hz
* 6: 24000 Hz
* 7: 22050 Hz
* 8: 16000 Hz
* 9: 12000 Hz
* 10: 11025 Hz
* 11: 8000 Hz
* 12: 7350 Hz
* 15: frequency is written explictly
These are the channel configurations:
* 0: custom configuration '''(TODO)'''
* 1: 1 channel: front-center
* 2: 2 channels: front-left, front-right
* 3: 3 channels: front-center, front-left, front-right
* 4: 4 channels: front-center, front-left, front-right, back-center
* 5: 5 channels: front-center, front-left, front-right, back-left, back-right
* 6: 6 channels: front-center, front-left, front-right, back-left, back-right, LFE-channel
* 7: 8 channels: front-center, front-left, front-right, side-left, side-right, back-left, back-right, LFE-channel
frame length flag:
* 0: Each packet contains 1024 samples
* 1: Each packet contains 960 samples

== Frames And Syntax Elements ==
In an MPEG-4 file, the AAC data is broken up into a series of variable length frames.

An AAC frame is comprised of blocks called syntax elements. Read the first 3 bits from the frame's bitstream to find the first element type. Decode the element. Proceed to read the first 3 bits of the next element and repeat the decoding process until the frame is depleted.

There are 8 different syntax elements:
* 0 SCE single channel element (codes a single audio channel)
* 1 CPE channel pair element (codes stereo signal)
* 2 CCE something to do with channel coupling, not implemented in libfaad2
* 3 LFE low-frequency effects? referenced as "special effects" in RTP doc
* 4 DSE data stream element (user data)
* 5 PCE program configuration element (describe bitstream)
* 6 FIL fill element (pad space/extension data)
* 7 END marks the end of the frame
This is an example layout for a 5.1 audio stream:
SCE CPE CPE LFE END
indicates
center - left/right - surround left/right - lfe - end
An ID within the respective CPE blocks indicates its channel assignments (front vs. surround).

== Decoding Process ==
First, let's list a few basic terms that FAAD2 uses throughout its decoding process:

* ics = individual channel stream, the basic audio unit that FAAD2 is concerned with
* ms = any parameter with this in its name deals with mid/side coding
* sfb = probably something to do with scale factors
* swb = scalefactor window band
* is = intensity stereo

As mentioned above, the ics is an important data structure in AAC decoding. These are its fields, according to FAAD2:

max_sfb
num_swb
num_window_groups
num_windows
window_sequence
window_group_length[8]
window_shape
scale_factor_grouping
section_sfb_offset[8][8*15]
swb_offset
section_codebook[8][15*8]
section_start[8][15*8]
section_end[8][15*8]
sfb_codebook[8][15*8]
number_sections[8] ''// number of sections in a group''
global_gain
scale_factors[8][51] ''// FAAD2 comment: [0..255]?''
ms_mask_present
ms_used[MAX_WINDOW_GROUPS][MAX_SFB] ''// dimensions = [8][51]''
noise_used
pulse_data_present
tns_data_present
gain_control_data_present
predictor_data_present
pulse_info pulse
tns_info tns
''data structures for main profile, document later''
''data structures for LTP, document later''
''data structures for SSR, document later''
''data structures for error resilience, document later''

These pages detail the process for decoding the various syntax elements:

* [[Decoding AAC SCE and LFE]]
* [[Decoding AAC CPE]]
** [[Reconstructing AAC CPE]]
* Decoding AAC CCE
* Decoding AAC DSE
* Decoding AAC PCE
* [[Decoding AAC FIL]]
* [[Decoding AAC END]]

NUT

2006-03-12T18:12:27Z

Ods15: /* Linear search implementation */

* Extensions: nut
* Website: http://www.nut.hu/

NUT is a container format under construction by [[MPlayer]] and [[FFmpeg]] developers.
Its main goals are to be simple, flexible and error-resistant while maintaining the smallest possible overhead.

== NUT seeking algo in libnut ==

=== Step 1 - Binary search and linear interpolation ===

==== Startup ====
Go to beginning of file if first syncpoint has not been found, and then go to EOF and search backward to find last syncpoint.
Pick the closest possible syncpoints for requested pts from syncpoint cache, one higher and one lower. If requested pts is lower than first syncpoint or higher than last syncpoint, then seek to either of those syncpoints and end seek.

Binary search is ended when the entire region between the 2 syncpoints picked has been scanned. Which could even be before it has begun thanks to syncpoint cache.

==== Guess position ====
Best results have been achieved by combining both linear interpolation and binary search, giving most of the weight to interpolation.

;hi, hi_pd: file position and timestamp of the top edge of the binary search.
;lo, lo_pd: file position and timestamp of the bottom edge of the binary search.
;time_pos: Requested pts.
;guess: begginning of linear search for syncpoint.

#define INTERPOLATE_WEIGHT (19./20)
if (hi - lo < nut->max_distance*2) guess = lo + 16;
else { // linear interpolation
double a = (double)(hi - lo) / (hi_pd - lo_pd);
guess = lo + a * (time_pos - lo_pd);
guess = guess * INTERPOLATE_WEIGHT + (lo+hi)/2 * (1 - INTERPOLATE_WEIGHT);
if (hi - guess < nut->max_distance*2) guess = hi - nut->max_distance*2; //(lo + hi)/2;
}
if (guess < lo + 16) guess = lo + 16;

The first conditional prevents too much recursing when the distance is already low. The last conditional prevents infinite loop of syncpoint search constantly finding ''lo'' and achieving nothing.

==== Binary search ====
Now, find a syncpoint, bounded between ''guess'' and ''hi''. If it has a timestamp higher than requested pts, then replace ''hi'' and ''hi_pd'', otherwise replace ''lo'' and ''lo_pd''.
If a syncpoint was not found between ''guess'' and ''hi'', then, if ''guess'' is smaller or equal to ''lo + 16'', then you have scanned the entire area between ''lo'' and ''hi'', and your binary search is done. Otherwise, replace ''hi'' with ''guess'' and repeat the binary search.

After finding the 2 closest syncpoints bounding your requested pts, the bounds of linear are search are:

*start = lo_s.pos - (lo_s.back_ptr * 16 + 15);
*end = hi_s.pos;
*stopper = hi_s;

''stopper'' is used later to end linear search prematurely. Note that it is the '''top''' edge of binary search, meaning, it has a timestamp higher than requested pts.

=== Step 2 - Linear search ===

==== Bounds of linear search ====
Linear search of course ends at ''end'', however, it can end earlier:
* When you find a frame of any stream, with a dts higher than requested pts.
* When you find a frame for '''all''' active streams with a pts higher than requested pts.
* When you find a syncpoint immediately following the syncpoint pointed to by ''stopper'''s back_ptr, (from here on this syncpoint will be called ''stopper_syncpoint'') '''and''' all streams are active.
* When you reach ''stopper_syncpoint'', and you have not found a keyframe for any '''non'''-active between ''stopper''<nowiki>'</nowiki>s back_ptr and ''stopper_syncpoint'', with a pts lower than ''stopper.timestamp''. The reason for this is that ''stopper'' did not point because to ''stopper_syncpoint'' can only be because of active stream keyframes, and not non active ones.
* When you find a keyframe for all '''non'''-active streams after ''stopper_syncpoint'' with a pts lower than ''stopper.timestamp'', which had a keyframe in the region in the previous condition. The logic is:
** ''stopper.timestamp'' is higher than requested pts.
** ''stopper_syncpoint'' is '''not''' the syncpoint pointed to by ''stopper.back_ptr'', but the one immediately following.
** If there was a keyframe for every non active stream after ''stopper_syncpoint'', with a pts lower than ''stopper.timestamp'', then the reason ''stopper'' does not point to ''stopper_syncpoint'' must be that there are no keyframes for '''active''' streams with a pts lower than ''stopper.timestamp'' after ''stopper_syncpoint''.
** There might be more keyframes in the region with a pts higher than ''stopper.timestamp'', but those are irrelevant because they are higher than requested pts.

The last 3 conditions can be phrased differently:
* When saying keyframes, only keyframes with a pts lower than ''stopper.timestamp'' are intended. Any other keyframes are irrelavent.
* The region ''stopper.back_ptr'' to ''stopper_syncpoint'' has a set of keyframes between it. These keyframes are the ones responsible for ''stopper'' pointing to ''stopper.back_ptr'' and not ''stopper_syncpoint''.
* If all streams are active, then it's impossible for there to be better keyframes for '''all''' active streams between ''stopper_syncpoint'' to the end of the linear search, because if there was, ''stopper.back_ptr'' would point there.
* If some streams are inactive, but none of them have a keyframe in the region specified above, then the keyframes responsible for ''stopper'' pointing to ''stopper.back_ptr'' are only from active streams, so again it is impossible there is a better position later in the linear search.
* If some streams are inactive, and some of them '''do''' have a keyframe in the region specified above, then those keyframes are ''possibly'' responsible for ''stopper'' pointing to ''stopper.back_ptr''. However, if we find more keyframes of those same inactive streams '''after''' the region, then they had nothing to do with ''stopper.back_ptr'', and again the condition is met.

==== Linear search implementation ====

# Start at ''start''.
# Search for syncpoint. If it is further than ''start + 15'', then the file is errored, and you can start playing immediately from this syncpoint.
# Perform full demuxing, buffering everything read. If you encounter any NUT error during demuxing, seek back to the syncpoint after ''start'' and end seek.
# On every syncpoint, flush the buffer and cache the syncpoint position.
#* If this syncpoint is ''stopper_syncpoint'', then do not flush the buffer, as it would be possible the linear search would end immediatelty afterwards and a second underlying seek would not be necessary.
# When finding keyframe of active stream with pts lower than requested pts, store position of keyframe. Discard previous value.
# End linear search as necessary by bounds given above.
# Pick the lowest value from positions of keyframes for active streams. This is the final position.
# Seek to closest syncpoint before the final position, preform a minimal demuxing until final position (to get proper last_pts context across all streams).
#* With luck this seek will not need an underlying seek, if you have not flushed the buffer since the requested position.
#* In most common case, ''stopper.back_ptr'' points to same syncpoint as the start of the linear search, as both syncpoints point to the same rare video keyframe.
#* If only video stream is active and the only non active stream is audio, you will most likely end your linear search immediately after ''stopper_syncpoint'' by finding an audio keyframe. Afterwards you will rewind right back to ''start'', and, since buffer hasn't been flushed, this will not need an underlying seek.

=== Index ===
With index, binary search step is skipped, and a much more limited linear search used, between two immediate syncpoints. The syncpoint picked is the highest possible one that has a keyframe for each active stream past the syncpoint with a pts lower than requested pts. The end of the linear search is the syncpoint immediately following.

=== Dynamic Index ===
Create the index in the same manner as creating the index in the muxer, remembering keyframes and EOR at syncpoint positions.
With one big difference - dynamic index can have gaps, thanks to seeking. Every syncpiont entry in the dynamic index has a flag indicating if it has a "unresearched region" gap from last syncpoint.

In seeking, dynamic index is used in the same manner as complete index. However, when deciding a syncpoint, the entire range of the syncpoint picked until the first syncpoint with a pts higher than requested is checked for having been already researched. If a "hole" is found anywhere in this range, dynamic index is disregarded and full binary search is performed.

=== End of Relavence ===
Behavior with linear search:
* Treat EOR frames same as keyframes. Seeing an EOR frame for an active stream causes the stream to be ignored until the next keyframe of same stream.
* If all active streams are EOR by end of linear search, just use start of linear search as final seeking position.

For index:
* When picking the correct syncpoint to start linear search, ignore streams which have EOR with pts lower than requested pts and no keyframe with pts lower than requested pts.
* If all active streams are EOR, pick the syncpoint immediately before the syncpoint with the last EOR across all streams with pts lower than requested pts.

[[Category:Container Formats]]

NUT

2006-03-12T18:11:46Z

Ods15: /* Binary search */ some fixes

* Extensions: nut
* Website: http://www.nut.hu/

NUT is a container format under construction by [[MPlayer]] and [[FFmpeg]] developers.
Its main goals are to be simple, flexible and error-resistant while maintaining the smallest possible overhead.

== NUT seeking algo in libnut ==

=== Step 1 - Binary search and linear interpolation ===

==== Startup ====
Go to beginning of file if first syncpoint has not been found, and then go to EOF and search backward to find last syncpoint.
Pick the closest possible syncpoints for requested pts from syncpoint cache, one higher and one lower. If requested pts is lower than first syncpoint or higher than last syncpoint, then seek to either of those syncpoints and end seek.

Binary search is ended when the entire region between the 2 syncpoints picked has been scanned. Which could even be before it has begun thanks to syncpoint cache.

==== Guess position ====
Best results have been achieved by combining both linear interpolation and binary search, giving most of the weight to interpolation.

;hi, hi_pd: file position and timestamp of the top edge of the binary search.
;lo, lo_pd: file position and timestamp of the bottom edge of the binary search.
;time_pos: Requested pts.
;guess: begginning of linear search for syncpoint.

#define INTERPOLATE_WEIGHT (19./20)
if (hi - lo < nut->max_distance*2) guess = lo + 16;
else { // linear interpolation
double a = (double)(hi - lo) / (hi_pd - lo_pd);
guess = lo + a * (time_pos - lo_pd);
guess = guess * INTERPOLATE_WEIGHT + (lo+hi)/2 * (1 - INTERPOLATE_WEIGHT);
if (hi - guess < nut->max_distance*2) guess = hi - nut->max_distance*2; //(lo + hi)/2;
}
if (guess < lo + 16) guess = lo + 16;

The first conditional prevents too much recursing when the distance is already low. The last conditional prevents infinite loop of syncpoint search constantly finding ''lo'' and achieving nothing.

==== Binary search ====
Now, find a syncpoint, bounded between ''guess'' and ''hi''. If it has a timestamp higher than requested pts, then replace ''hi'' and ''hi_pd'', otherwise replace ''lo'' and ''lo_pd''.
If a syncpoint was not found between ''guess'' and ''hi'', then, if ''guess'' is smaller or equal to ''lo + 16'', then you have scanned the entire area between ''lo'' and ''hi'', and your binary search is done. Otherwise, replace ''hi'' with ''guess'' and repeat the binary search.

After finding the 2 closest syncpoints bounding your requested pts, the bounds of linear are search are:

*start = lo_s.pos - (lo_s.back_ptr * 16 + 15);
*end = hi_s.pos;
*stopper = hi_s;

''stopper'' is used later to end linear search prematurely. Note that it is the '''top''' edge of binary search, meaning, it has a timestamp higher than requested pts.

=== Step 2 - Linear search ===

==== Bounds of linear search ====
Linear search of course ends at ''end'', however, it can end earlier:
* When you find a frame of any stream, with a dts higher than requested pts.
* When you find a frame for '''all''' active streams with a pts higher than requested pts.
* When you find a syncpoint immediately following the syncpoint pointed to by ''stopper'''s back_ptr, (from here on this syncpoint will be called ''stopper_syncpoint'') '''and''' all streams are active.
* When you reach ''stopper_syncpoint'', and you have not found a keyframe for any '''non'''-active between ''stopper''<nowiki>'</nowiki>s back_ptr and ''stopper_syncpoint'', with a pts lower than ''stopper.timestamp''. The reason for this is that ''stopper'' did not point because to ''stopper_syncpoint'' can only be because of active stream keyframes, and not non active ones.
* When you find a keyframe for all '''non'''-active streams after ''stopper_syncpoint'' with a pts lower than ''stopper.timestamp'', which had a keyframe in the region in the previous condition. The logic is:
** ''stopper.timestamp'' is higher than requested pts.
** ''stopper_syncpoint'' is '''not''' the syncpoint pointed to by ''stopper.back_ptr'', but the one immediately following.
** If there was a keyframe for every non active stream after ''stopper_syncpoint'', with a pts lower than ''stopper.timestamp'', then the reason ''stopper'' does not point to ''stopper_syncpoint'' must be that there are no keyframes for '''active''' streams with a pts lower than ''stopper.timestamp'' after ''stopper_syncpoint''.
** There might be more keyframes in the region with a pts higher than ''stopper.timestamp'', but those are irrelevant because they are higher than requested pts.

The last 3 conditions can be phrased differently:
* When saying keyframes, only keyframes with a pts lower than ''stopper.timestamp'' are intended. Any other keyframes are irrelavent.
* The region ''stopper.back_ptr'' to ''stopper_syncpoint'' has a set of keyframes between it. These keyframes are the ones responsible for ''stopper'' pointing to ''stopper.back_ptr'' and not ''stopper_syncpoint''.
* If all streams are active, then it's impossible for there to be better keyframes for '''all''' active streams between ''stopper_syncpoint'' to the end of the linear search, because if there was, ''stopper.back_ptr'' would point there.
* If some streams are inactive, but none of them have a keyframe in the region specified above, then the keyframes responsible for ''stopper'' pointing to ''stopper.back_ptr'' are only from active streams, so again it is impossible there is a better position later in the linear search.
* If some streams are inactive, and some of them '''do''' have a keyframe in the region specified above, then those keyframes are ''possibly'' responsible for ''stopper'' pointing to ''stopper.back_ptr''. However, if we find more keyframes of those same inactive streams '''after''' the region, then they had nothing to do with ''stopper.back_ptr'', and again the condition is met.

==== Linear search implementation ====

# Start at ''start''.
# Search for syncpoint. If it is further than ''start + 7'', then the file is errored, and you can start playing immediately from this syncpoint.
# Perform full demuxing, buffering everything read. If you encounter any NUT error during demuxing, seek back to the syncpoint after ''start'' and end seek.
# On every syncpoint, flush the buffer and cache the syncpoint position.
#* If this syncpoint is ''stopper_syncpoint'', then do not flush the buffer, as it would be possible the linear search would end immediatelty afterwards and a second underlying seek would not be necessary.
# When finding keyframe of active stream with pts lower than requested pts, store position of keyframe. Discard previous value.
# End linear search as necessary by bounds given above.
# Pick the lowest value from positions of keyframes for active streams. This is the final position.
# Seek to closest syncpoint before the final position, preform a minimal demuxing until final position (to get proper last_pts context across all streams).
#* With luck this seek will not need an underlying seek, if you have not flushed the buffer since the requested position.
#* In most common case, ''stopper.back_ptr'' points to same syncpoint as the start of the linear search, as both syncpoints point to the same rare video keyframe.
#* If only video stream is active and the only non active stream is audio, you will most likely end your linear search immediately after ''stopper_syncpoint'' by finding an audio keyframe. Afterwards you will rewind right back to ''start'', and, since buffer hasn't been flushed, this will not need an underlying seek.

=== Index ===
With index, binary search step is skipped, and a much more limited linear search used, between two immediate syncpoints. The syncpoint picked is the highest possible one that has a keyframe for each active stream past the syncpoint with a pts lower than requested pts. The end of the linear search is the syncpoint immediately following.

=== Dynamic Index ===
Create the index in the same manner as creating the index in the muxer, remembering keyframes and EOR at syncpoint positions.
With one big difference - dynamic index can have gaps, thanks to seeking. Every syncpiont entry in the dynamic index has a flag indicating if it has a "unresearched region" gap from last syncpoint.

In seeking, dynamic index is used in the same manner as complete index. However, when deciding a syncpoint, the entire range of the syncpoint picked until the first syncpoint with a pts higher than requested is checked for having been already researched. If a "hole" is found anywhere in this range, dynamic index is disregarded and full binary search is performed.

=== End of Relavence ===
Behavior with linear search:
* Treat EOR frames same as keyframes. Seeing an EOR frame for an active stream causes the stream to be ignored until the next keyframe of same stream.
* If all active streams are EOR by end of linear search, just use start of linear search as final seeking position.

For index:
* When picking the correct syncpoint to start linear search, ignore streams which have EOR with pts lower than requested pts and no keyframe with pts lower than requested pts.
* If all active streams are EOR, pick the syncpoint immediately before the syncpoint with the last EOR across all streams with pts lower than requested pts.

[[Category:Container Formats]]

NUT

2006-03-12T07:12:31Z

Ods15: /* Guess position */ Change to 16 and wheight

* Extensions: nut
* Website: http://www.nut.hu/

NUT is a container format under construction by [[MPlayer]] and [[FFmpeg]] developers.
Its main goals are to be simple, flexible and error-resistant while maintaining the smallest possible overhead.

== NUT seeking algo in libnut ==

=== Step 1 - Binary search and linear interpolation ===

==== Startup ====
Go to beginning of file if first syncpoint has not been found, and then go to EOF and search backward to find last syncpoint.
Pick the closest possible syncpoints for requested pts from syncpoint cache, one higher and one lower. If requested pts is lower than first syncpoint or higher than last syncpoint, then seek to either of those syncpoints and end seek.

Binary search is ended when the entire region between the 2 syncpoints picked has been scanned. Which could even be before it has begun thanks to syncpoint cache.

==== Guess position ====
Best results have been achieved by combining both linear interpolation and binary search, giving most of the weight to interpolation.

;hi, hi_pd: file position and timestamp of the top edge of the binary search.
;lo, lo_pd: file position and timestamp of the bottom edge of the binary search.
;time_pos: Requested pts.
;guess: begginning of linear search for syncpoint.

#define INTERPOLATE_WEIGHT (19./20)
if (hi - lo < nut->max_distance*2) guess = lo + 16;
else { // linear interpolation
double a = (double)(hi - lo) / (hi_pd - lo_pd);
guess = lo + a * (time_pos - lo_pd);
guess = guess * INTERPOLATE_WEIGHT + (lo+hi)/2 * (1 - INTERPOLATE_WEIGHT);
if (hi - guess < nut->max_distance*2) guess = hi - nut->max_distance*2; //(lo + hi)/2;
}
if (guess < lo + 16) guess = lo + 16;

The first conditional prevents too much recursing when the distance is already low. The last conditional prevents infinite loop of syncpoint search constantly finding ''lo'' and achieving nothing.

==== Binary search ====
Now, find a syncpoint, bounded between ''guess'' and ''hi''. If it has a timestamp higher than requested pts, then replace ''hi'' and ''hi_pd'', otherwise replace ''lo'' and ''lo_pd''.
If a syncpoint was not found between ''guess'' and ''hi'', then, if ''guess'' is smaller or equal to ''lo + 11'', then you have scanned the entire area between ''lo'' and ''hi'', and your binary search is done. Otherwise, replace ''hi'' with ''guess'' and repeat the binary search.

After finding the 2 closest syncpoints bounding your requested pts, the bounds of linear are search are:

*start = lo_s.pos - (lo_s.back_ptr * 8 + 7);
*end = lo_s.pos;
*stopper = hi_s;

''stopper'' is used later to end linear search prematurely. Note that it is the '''top''' edge of binary search, meaning, it has a timestamp higher than requested pts.

=== Step 2 - Linear search ===

==== Bounds of linear search ====
Linear search of course ends at ''end'', however, it can end earlier:
* When you find a frame of any stream, with a dts higher than requested pts.
* When you find a frame for '''all''' active streams with a pts higher than requested pts.
* When you find a syncpoint immediately following the syncpoint pointed to by ''stopper'''s back_ptr, (from here on this syncpoint will be called ''stopper_syncpoint'') '''and''' all streams are active.
* When you reach ''stopper_syncpoint'', and you have not found a keyframe for any '''non'''-active between ''stopper''<nowiki>'</nowiki>s back_ptr and ''stopper_syncpoint'', with a pts lower than ''stopper.timestamp''. The reason for this is that ''stopper'' did not point because to ''stopper_syncpoint'' can only be because of active stream keyframes, and not non active ones.
* When you find a keyframe for all '''non'''-active streams after ''stopper_syncpoint'' with a pts lower than ''stopper.timestamp'', which had a keyframe in the region in the previous condition. The logic is:
** ''stopper.timestamp'' is higher than requested pts.
** ''stopper_syncpoint'' is '''not''' the syncpoint pointed to by ''stopper.back_ptr'', but the one immediately following.
** If there was a keyframe for every non active stream after ''stopper_syncpoint'', with a pts lower than ''stopper.timestamp'', then the reason ''stopper'' does not point to ''stopper_syncpoint'' must be that there are no keyframes for '''active''' streams with a pts lower than ''stopper.timestamp'' after ''stopper_syncpoint''.
** There might be more keyframes in the region with a pts higher than ''stopper.timestamp'', but those are irrelevant because they are higher than requested pts.

The last 3 conditions can be phrased differently:
* When saying keyframes, only keyframes with a pts lower than ''stopper.timestamp'' are intended. Any other keyframes are irrelavent.
* The region ''stopper.back_ptr'' to ''stopper_syncpoint'' has a set of keyframes between it. These keyframes are the ones responsible for ''stopper'' pointing to ''stopper.back_ptr'' and not ''stopper_syncpoint''.
* If all streams are active, then it's impossible for there to be better keyframes for '''all''' active streams between ''stopper_syncpoint'' to the end of the linear search, because if there was, ''stopper.back_ptr'' would point there.
* If some streams are inactive, but none of them have a keyframe in the region specified above, then the keyframes responsible for ''stopper'' pointing to ''stopper.back_ptr'' are only from active streams, so again it is impossible there is a better position later in the linear search.
* If some streams are inactive, and some of them '''do''' have a keyframe in the region specified above, then those keyframes are ''possibly'' responsible for ''stopper'' pointing to ''stopper.back_ptr''. However, if we find more keyframes of those same inactive streams '''after''' the region, then they had nothing to do with ''stopper.back_ptr'', and again the condition is met.

==== Linear search implementation ====

# Start at ''start''.
# Search for syncpoint. If it is further than ''start + 7'', then the file is errored, and you can start playing immediately from this syncpoint.
# Perform full demuxing, buffering everything read. If you encounter any NUT error during demuxing, seek back to the syncpoint after ''start'' and end seek.
# On every syncpoint, flush the buffer and cache the syncpoint position.
#* If this syncpoint is ''stopper_syncpoint'', then do not flush the buffer, as it would be possible the linear search would end immediatelty afterwards and a second underlying seek would not be necessary.
# When finding keyframe of active stream with pts lower than requested pts, store position of keyframe. Discard previous value.
# End linear search as necessary by bounds given above.
# Pick the lowest value from positions of keyframes for active streams. This is the final position.
# Seek to closest syncpoint before the final position, preform a minimal demuxing until final position (to get proper last_pts context across all streams).
#* With luck this seek will not need an underlying seek, if you have not flushed the buffer since the requested position.
#* In most common case, ''stopper.back_ptr'' points to same syncpoint as the start of the linear search, as both syncpoints point to the same rare video keyframe.
#* If only video stream is active and the only non active stream is audio, you will most likely end your linear search immediately after ''stopper_syncpoint'' by finding an audio keyframe. Afterwards you will rewind right back to ''start'', and, since buffer hasn't been flushed, this will not need an underlying seek.

=== Index ===
With index, binary search step is skipped, and a much more limited linear search used, between two immediate syncpoints. The syncpoint picked is the highest possible one that has a keyframe for each active stream past the syncpoint with a pts lower than requested pts. The end of the linear search is the syncpoint immediately following.

=== Dynamic Index ===
Create the index in the same manner as creating the index in the muxer, remembering keyframes and EOR at syncpoint positions.
With one big difference - dynamic index can have gaps, thanks to seeking. Every syncpiont entry in the dynamic index has a flag indicating if it has a "unresearched region" gap from last syncpoint.

In seeking, dynamic index is used in the same manner as complete index. However, when deciding a syncpoint, the entire range of the syncpoint picked until the first syncpoint with a pts higher than requested is checked for having been already researched. If a "hole" is found anywhere in this range, dynamic index is disregarded and full binary search is performed.

=== End of Relavence ===
Behavior with linear search:
* Treat EOR frames same as keyframes. Seeing an EOR frame for an active stream causes the stream to be ignored until the next keyframe of same stream.
* If all active streams are EOR by end of linear search, just use start of linear search as final seeking position.

For index:
* When picking the correct syncpoint to start linear search, ignore streams which have EOR with pts lower than requested pts and no keyframe with pts lower than requested pts.
* If all active streams are EOR, pick the syncpoint immediately before the syncpoint with the last EOR across all streams with pts lower than requested pts.

[[Category:Container Formats]]

Rewind

2006-03-03T16:13:19Z

Ods15: category

Rewind is the project name of my ([[User:merbanan|Benjamin Larsson]]) collection of different tools to aid Reverse Engineering.
The goal is to combine all the tools into 'the' tool for codec RE'ing work under Linux.

== Elftractor ==
This Perl script can analyze elf binaries to extract the data tables. The produced tables look quite good
and tables with 1 or 2 dimensions can be produced. The script uses a database which can be edited to adjust
the different types of possibe tables. Rudimentary function skeleton generation can also be done.

Features missing:
* >2 dimensions for table generation
* always generate compilable tables

== REbug ==
A set of macros and functions that can trace a selected calltree. Based partly on this code [http://www.multimedia.cx/pre/loadxan.c.txt].
Currently the output can then be processed to produce call graphs over executed code.

Current features:
* function call tracing
* function argument dumping
* function return value dumping
* executed calltree graphing

Features missing:
* memory tracking - lookup the use of malloc in the executed code
* structure resolver - check all malloced memory for pointers to other malloced memory
* argument typing - check/guess if the arguments are pointers to allocateded or stack memory, table elements or something else
* loop detection - guess existence of loop construct by checking the amount of consecutive calls
* code skeleton generation - generate a code template with the generated information
* structure graphing - generate a nice looking graph over the relations in the structures

== Argument resolver ==
This Perl script can analyse the IDA Pro produced assembly of a binary and give a fairly accurate number of arguments to a function
and its return type. This script is meant to be used together with REbug output.

[[Category: RE Tools]]

NUT

2006-02-25T07:55:23Z

Ods15: /* Bounds of linear search */ Clarify...

* Extensions: nut
* Website: http://www.nut.hu/

NUT is a container format under construction by [[MPlayer]] and [[FFmpeg]] developers.
Its main goals are to be simple, flexible and error-resistant while maintaining the smallest possible overhead.

== NUT seeking algo in libnut ==

=== Step 1 - Binary search and linear interpolation ===

==== Startup ====
Go to beginning of file if first syncpoint has not been found, and then go to EOF and search backward to find last syncpoint.
Pick the closest possible syncpoints for requested pts from syncpoint cache, one higher and one lower. If requested pts is lower than first syncpoint or higher than last syncpoint, then seek to either of those syncpoints and end seek.

Binary search is ended when the entire region between the 2 syncpoints picked has been scanned. Which could even be before it has begun thanks to syncpoint cache.

==== Guess position ====
Best results have been achieved by combining both linear interpolation and binary search, giving most of the weight to interpolation.

;hi, hi_pd: file position and timestamp of the top edge of the binary search.
;lo, lo_pd: file position and timestamp of the bottom edge of the binary search.
;time_pos: Requested pts.
;guess: begginning of linear search for syncpoint.

#define INTERPOLATE_WEIGHT (7./8)
if (hi - lo < nut->max_distance*2) guess = lo + 8;
else { // linear interpolation
double a = (double)(hi - lo) / (hi_pd - lo_pd);
guess = lo + a * (time_pos - lo_pd);
guess = guess * INTERPOLATE_WEIGHT + (lo+hi)/2 * (1 - INTERPOLATE_WEIGHT);
if (hi - guess < nut->max_distance*2) guess = hi - nut->max_distance*2; //(lo + hi)/2;
}
if (guess < lo + 8) guess = lo + 8;

The first conditional prevents too much recursing when the distance is already low. The last conditional prevents infinite loop of syncpoint search constantly finding ''lo'' and achieving nothing.

==== Binary search ====
Now, find a syncpoint, bounded between ''guess'' and ''hi''. If it has a timestamp higher than requested pts, then replace ''hi'' and ''hi_pd'', otherwise replace ''lo'' and ''lo_pd''.
If a syncpoint was not found between ''guess'' and ''hi'', then, if ''guess'' is smaller or equal to ''lo + 11'', then you have scanned the entire area between ''lo'' and ''hi'', and your binary search is done. Otherwise, replace ''hi'' with ''guess'' and repeat the binary search.

After finding the 2 closest syncpoints bounding your requested pts, the bounds of linear are search are:

*start = lo_s.pos - (lo_s.back_ptr * 8 + 7);
*end = lo_s.pos;
*stopper = hi_s;

''stopper'' is used later to end linear search prematurely. Note that it is the '''top''' edge of binary search, meaning, it has a timestamp higher than requested pts.

=== Step 2 - Linear search ===

==== Bounds of linear search ====
Linear search of course ends at ''end'', however, it can end earlier:
* When you find a frame of any stream, with a dts higher than requested pts.
* When you find a frame for '''all''' active streams with a pts higher than requested pts.
* When you find a syncpoint immediately following the syncpoint pointed to by ''stopper'''s back_ptr, (from here on this syncpoint will be called ''stopper_syncpoint'') '''and''' all streams are active.
* When you reach ''stopper_syncpoint'', and you have not found a keyframe for any '''non'''-active between ''stopper''<nowiki>'</nowiki>s back_ptr and ''stopper_syncpoint'', with a pts lower than ''stopper.timestamp''. The reason for this is that ''stopper'' did not point because to ''stopper_syncpoint'' can only be because of active stream keyframes, and not non active ones.
* When you find a keyframe for all '''non'''-active streams after ''stopper_syncpoint'' with a pts lower than ''stopper.timestamp'', which had a keyframe in the region in the previous condition. The logic is:
** ''stopper.timestamp'' is higher than requested pts.
** ''stopper_syncpoint'' is '''not''' the syncpoint pointed to by ''stopper.back_ptr'', but the one immediately following.
** If there was a keyframe for every non active stream after ''stopper_syncpoint'', with a pts lower than ''stopper.timestamp'', then the reason ''stopper'' does not point to ''stopper_syncpoint'' must be that there are no keyframes for '''active''' streams with a pts lower than ''stopper.timestamp'' after ''stopper_syncpoint''.
** There might be more keyframes in the region with a pts higher than ''stopper.timestamp'', but those are irrelevant because they are higher than requested pts.

The last 3 conditions can be phrased differently:
* When saying keyframes, only keyframes with a pts lower than ''stopper.timestamp'' are intended. Any other keyframes are irrelavent.
* The region ''stopper.back_ptr'' to ''stopper_syncpoint'' has a set of keyframes between it. These keyframes are the ones responsible for ''stopper'' pointing to ''stopper.back_ptr'' and not ''stopper_syncpoint''.
* If all streams are active, then it's impossible for there to be better keyframes for '''all''' active streams between ''stopper_syncpoint'' to the end of the linear search, because if there was, ''stopper.back_ptr'' would point there.
* If some streams are inactive, but none of them have a keyframe in the region specified above, then the keyframes responsible for ''stopper'' pointing to ''stopper.back_ptr'' are only from active streams, so again it is impossible there is a better position later in the linear search.
* If some streams are inactive, and some of them '''do''' have a keyframe in the region specified above, then those keyframes are ''possibly'' responsible for ''stopper'' pointing to ''stopper.back_ptr''. However, if we find more keyframes of those same inactive streams '''after''' the region, then they had nothing to do with ''stopper.back_ptr'', and again the condition is met.

==== Linear search implementation ====

# Start at ''start''.
# Search for syncpoint. If it is further than ''start + 7'', then the file is errored, and you can start playing immediately from this syncpoint.
# Perform full demuxing, buffering everything read. If you encounter any NUT error during demuxing, seek back to the syncpoint after ''start'' and end seek.
# On every syncpoint, flush the buffer and cache the syncpoint position.
#* If this syncpoint is ''stopper_syncpoint'', then do not flush the buffer, as it would be possible the linear search would end immediatelty afterwards and a second underlying seek would not be necessary.
# When finding keyframe of active stream with pts lower than requested pts, store position of keyframe. Discard previous value.
# End linear search as necessary by bounds given above.
# Pick the lowest value from positions of keyframes for active streams. This is the final position.
# Seek to closest syncpoint before the final position, preform a minimal demuxing until final position (to get proper last_pts context across all streams).
#* With luck this seek will not need an underlying seek, if you have not flushed the buffer since the requested position.
#* In most common case, ''stopper.back_ptr'' points to same syncpoint as the start of the linear search, as both syncpoints point to the same rare video keyframe.
#* If only video stream is active and the only non active stream is audio, you will most likely end your linear search immediately after ''stopper_syncpoint'' by finding an audio keyframe. Afterwards you will rewind right back to ''start'', and, since buffer hasn't been flushed, this will not need an underlying seek.

=== Index ===
With index, binary search step is skipped, and a much more limited linear search used, between two immediate syncpoints. The syncpoint picked is the highest possible one that has a keyframe for each active stream past the syncpoint with a pts lower than requested pts. The end of the linear search is the syncpoint immediately following.

=== Dynamic Index ===
Create the index in the same manner as creating the index in the muxer, remembering keyframes and EOR at syncpoint positions.
With one big difference - dynamic index can have gaps, thanks to seeking. Every syncpiont entry in the dynamic index has a flag indicating if it has a "unresearched region" gap from last syncpoint.

In seeking, dynamic index is used in the same manner as complete index. However, when deciding a syncpoint, the entire range of the syncpoint picked until the first syncpoint with a pts higher than requested is checked for having been already researched. If a "hole" is found anywhere in this range, dynamic index is disregarded and full binary search is performed.

=== End of Relavence ===
Behavior with linear search:
* Treat EOR frames same as keyframes. Seeing an EOR frame for an active stream causes the stream to be ignored until the next keyframe of same stream.
* If all active streams are EOR by end of linear search, just use start of linear search as final seeking position.

For index:
* When picking the correct syncpoint to start linear search, ignore streams which have EOR with pts lower than requested pts and no keyframe with pts lower than requested pts.
* If all active streams are EOR, pick the syncpoint immediately before the syncpoint with the last EOR across all streams with pts lower than requested pts.

[[Category:Container Formats]]

NUT

2006-02-25T07:36:29Z

Ods15: /* Bounds of linear search */ Fix wiki

* Extensions: nut
* Website: http://www.nut.hu/

NUT is a container format under construction by [[MPlayer]] and [[FFmpeg]] developers.
Its main goals are to be simple, flexible and error-resistant while maintaining the smallest possible overhead.

== NUT seeking algo in libnut ==

=== Step 1 - Binary search and linear interpolation ===

==== Startup ====
Go to beginning of file if first syncpoint has not been found, and then go to EOF and search backward to find last syncpoint.
Pick the closest possible syncpoints for requested pts from syncpoint cache, one higher and one lower. If requested pts is lower than first syncpoint or higher than last syncpoint, then seek to either of those syncpoints and end seek.

Binary search is ended when the entire region between the 2 syncpoints picked has been scanned. Which could even be before it has begun thanks to syncpoint cache.

==== Guess position ====
Best results have been achieved by combining both linear interpolation and binary search, giving most of the weight to interpolation.

;hi, hi_pd: file position and timestamp of the top edge of the binary search.
;lo, lo_pd: file position and timestamp of the bottom edge of the binary search.
;time_pos: Requested pts.
;guess: begginning of linear search for syncpoint.

#define INTERPOLATE_WEIGHT (7./8)
if (hi - lo < nut->max_distance*2) guess = lo + 8;
else { // linear interpolation
double a = (double)(hi - lo) / (hi_pd - lo_pd);
guess = lo + a * (time_pos - lo_pd);
guess = guess * INTERPOLATE_WEIGHT + (lo+hi)/2 * (1 - INTERPOLATE_WEIGHT);
if (hi - guess < nut->max_distance*2) guess = hi - nut->max_distance*2; //(lo + hi)/2;
}
if (guess < lo + 8) guess = lo + 8;

The first conditional prevents too much recursing when the distance is already low. The last conditional prevents infinite loop of syncpoint search constantly finding ''lo'' and achieving nothing.

==== Binary search ====
Now, find a syncpoint, bounded between ''guess'' and ''hi''. If it has a timestamp higher than requested pts, then replace ''hi'' and ''hi_pd'', otherwise replace ''lo'' and ''lo_pd''.
If a syncpoint was not found between ''guess'' and ''hi'', then, if ''guess'' is smaller or equal to ''lo + 11'', then you have scanned the entire area between ''lo'' and ''hi'', and your binary search is done. Otherwise, replace ''hi'' with ''guess'' and repeat the binary search.

After finding the 2 closest syncpoints bounding your requested pts, the bounds of linear are search are:

*start = lo_s.pos - (lo_s.back_ptr * 8 + 7);
*end = lo_s.pos;
*stopper = hi_s;

''stopper'' is used later to end linear search prematurely. Note that it is the '''top''' edge of binary search, meaning, it has a timestamp higher than requested pts.

=== Step 2 - Linear search ===

==== Bounds of linear search ====
Linear search of course ends at ''end'', however, it can end earlier:
* When you find a frame of any stream, with a dts higher than requested pts.
* When you find a frame for '''all''' active streams with a pts higher than requested pts.
* When you find a syncpoint immediately following the syncpoint pointed to by ''stopper'''s back_ptr, (from here on this syncpoint will be called ''stopper_syncpoint'') '''and''' all streams are active.
* When you reach ''stopper_syncpoint'', and you have not found a keyframe for any '''non'''-active between ''stopper''<nowiki>'</nowiki>s back_ptr and ''stopper_syncpoint'', with a pts lower than ''stopper.timestamp''. The reason for this is that ''stopper'' did not point because to ''stopper_syncpoint'' can only be because of active stream keyframes, and not non active ones.
* When you find a keyframe for all '''non'''-active streams after ''stopper_syncpoint'' with a pts lower than ''stopper.timestamp'', which had a keyframe in the region in the previous condition. The logic is:
** ''stopper.timestamp'' is higher than requested pts.
** ''stopper_syncpoint'' is '''not''' the syncpoint pointed to by ''stopper.back_ptr'', but the one immediately following.
** If there was a keyframe for every non active stream after ''stopper_syncpoint'', with a pts lower than ''stopper.timestamp'', then the reason ''stopper'' does not point to ''stopper_syncpoint'' must be that there are no keyframes for '''active''' streams with a pts lower than ''stopper.timestamp'' after ''stopper_syncpoint''.
** There might be more keyframes in the region with a pts higher than ''stopper.timestamp'', but those are irrelevant because they are higher than requested pts.

==== Linear search implementation ====

# Start at ''start''.
# Search for syncpoint. If it is further than ''start + 7'', then the file is errored, and you can start playing immediately from this syncpoint.
# Perform full demuxing, buffering everything read. If you encounter any NUT error during demuxing, seek back to the syncpoint after ''start'' and end seek.
# On every syncpoint, flush the buffer and cache the syncpoint position.
#* If this syncpoint is ''stopper_syncpoint'', then do not flush the buffer, as it would be possible the linear search would end immediatelty afterwards and a second underlying seek would not be necessary.
# When finding keyframe of active stream with pts lower than requested pts, store position of keyframe. Discard previous value.
# End linear search as necessary by bounds given above.
# Pick the lowest value from positions of keyframes for active streams. This is the final position.
# Seek to closest syncpoint before the final position, preform a minimal demuxing until final position (to get proper last_pts context across all streams).
#* With luck this seek will not need an underlying seek, if you have not flushed the buffer since the requested position.
#* In most common case, ''stopper.back_ptr'' points to same syncpoint as the start of the linear search, as both syncpoints point to the same rare video keyframe.
#* If only video stream is active and the only non active stream is audio, you will most likely end your linear search immediately after ''stopper_syncpoint'' by finding an audio keyframe. Afterwards you will rewind right back to ''start'', and, since buffer hasn't been flushed, this will not need an underlying seek.

=== Index ===
With index, binary search step is skipped, and a much more limited linear search used, between two immediate syncpoints. The syncpoint picked is the highest possible one that has a keyframe for each active stream past the syncpoint with a pts lower than requested pts. The end of the linear search is the syncpoint immediately following.

=== Dynamic Index ===
Create the index in the same manner as creating the index in the muxer, remembering keyframes and EOR at syncpoint positions.
With one big difference - dynamic index can have gaps, thanks to seeking. Every syncpiont entry in the dynamic index has a flag indicating if it has a "unresearched region" gap from last syncpoint.

In seeking, dynamic index is used in the same manner as complete index. However, when deciding a syncpoint, the entire range of the syncpoint picked until the first syncpoint with a pts higher than requested is checked for having been already researched. If a "hole" is found anywhere in this range, dynamic index is disregarded and full binary search is performed.

=== End of Relavence ===
Behavior with linear search:
* Treat EOR frames same as keyframes. Seeing an EOR frame for an active stream causes the stream to be ignored until the next keyframe of same stream.
* If all active streams are EOR by end of linear search, just use start of linear search as final seeking position.

For index:
* When picking the correct syncpoint to start linear search, ignore streams which have EOR with pts lower than requested pts and no keyframe with pts lower than requested pts.
* If all active streams are EOR, pick the syncpoint immediately before the syncpoint with the last EOR across all streams with pts lower than requested pts.

[[Category:Container Formats]]

NUT

2006-02-25T07:34:35Z

Ods15: /* Bounds of linear search */ Another condition for stopping linear search

* Extensions: nut
* Website: http://www.nut.hu/

NUT is a container format under construction by [[MPlayer]] and [[FFmpeg]] developers.
Its main goals are to be simple, flexible and error-resistant while maintaining the smallest possible overhead.

== NUT seeking algo in libnut ==

=== Step 1 - Binary search and linear interpolation ===

==== Startup ====
Go to beginning of file if first syncpoint has not been found, and then go to EOF and search backward to find last syncpoint.
Pick the closest possible syncpoints for requested pts from syncpoint cache, one higher and one lower. If requested pts is lower than first syncpoint or higher than last syncpoint, then seek to either of those syncpoints and end seek.

Binary search is ended when the entire region between the 2 syncpoints picked has been scanned. Which could even be before it has begun thanks to syncpoint cache.

==== Guess position ====
Best results have been achieved by combining both linear interpolation and binary search, giving most of the weight to interpolation.

;hi, hi_pd: file position and timestamp of the top edge of the binary search.
;lo, lo_pd: file position and timestamp of the bottom edge of the binary search.
;time_pos: Requested pts.
;guess: begginning of linear search for syncpoint.

#define INTERPOLATE_WEIGHT (7./8)
if (hi - lo < nut->max_distance*2) guess = lo + 8;
else { // linear interpolation
double a = (double)(hi - lo) / (hi_pd - lo_pd);
guess = lo + a * (time_pos - lo_pd);
guess = guess * INTERPOLATE_WEIGHT + (lo+hi)/2 * (1 - INTERPOLATE_WEIGHT);
if (hi - guess < nut->max_distance*2) guess = hi - nut->max_distance*2; //(lo + hi)/2;
}
if (guess < lo + 8) guess = lo + 8;

The first conditional prevents too much recursing when the distance is already low. The last conditional prevents infinite loop of syncpoint search constantly finding ''lo'' and achieving nothing.

==== Binary search ====
Now, find a syncpoint, bounded between ''guess'' and ''hi''. If it has a timestamp higher than requested pts, then replace ''hi'' and ''hi_pd'', otherwise replace ''lo'' and ''lo_pd''.
If a syncpoint was not found between ''guess'' and ''hi'', then, if ''guess'' is smaller or equal to ''lo + 11'', then you have scanned the entire area between ''lo'' and ''hi'', and your binary search is done. Otherwise, replace ''hi'' with ''guess'' and repeat the binary search.

After finding the 2 closest syncpoints bounding your requested pts, the bounds of linear are search are:

*start = lo_s.pos - (lo_s.back_ptr * 8 + 7);
*end = lo_s.pos;
*stopper = hi_s;

''stopper'' is used later to end linear search prematurely. Note that it is the '''top''' edge of binary search, meaning, it has a timestamp higher than requested pts.

=== Step 2 - Linear search ===

==== Bounds of linear search ====
Linear search of course ends at ''end'', however, it can end earlier:
* When you find a frame of any stream, with a dts higher than requested pts.
* When you find a frame for '''all''' active streams with a pts higher than requested pts.
* When you find a syncpoint immediately following the syncpoint pointed to by ''stopper'''s back_ptr, (from here on this syncpoint will be called ''stopper_syncpoint'') '''and''' all streams are active.
* When you reach ''stopper_syncpoint'', and you have not found a keyframe for any '''non'''-active between ''stopper'''s back_ptr and ''stopper_syncpoint'', with a pts lower than ''stopper.timestamp''. The reason for this is that ''stopper'' did not point because to ''stopper_syncpoint'' can only be because of active stream keyframes, and not non active ones.
* When you find a keyframe for all '''non'''-active streams after ''stopper_syncpoint'' with a pts lower than ''stopper.timestamp'', which had a keyframe in the region in the previous condition. The logic is:
** ''stopper.timestamp'' is higher than requested pts.
** ''stopper_syncpoint'' is '''not''' the syncpoint pointed to by ''stopper.back_ptr'', but the one immediately following.
** If there was a keyframe for every non active stream after ''stopper_syncpoint'', with a pts lower than ''stopper.timestamp'', then the reason ''stopper'' does not point to ''stopper_syncpoint'' must be that there are no keyframes for '''active''' streams with a pts lower than ''stopper.timestamp'' after ''stopper_syncpoint''.
** There might be more keyframes in the region with a pts higher than ''stopper.timestamp'', but those are irrelevant because they are higher than requested pts.

==== Linear search implementation ====

# Start at ''start''.
# Search for syncpoint. If it is further than ''start + 7'', then the file is errored, and you can start playing immediately from this syncpoint.
# Perform full demuxing, buffering everything read. If you encounter any NUT error during demuxing, seek back to the syncpoint after ''start'' and end seek.
# On every syncpoint, flush the buffer and cache the syncpoint position.
#* If this syncpoint is ''stopper_syncpoint'', then do not flush the buffer, as it would be possible the linear search would end immediatelty afterwards and a second underlying seek would not be necessary.
# When finding keyframe of active stream with pts lower than requested pts, store position of keyframe. Discard previous value.
# End linear search as necessary by bounds given above.
# Pick the lowest value from positions of keyframes for active streams. This is the final position.
# Seek to closest syncpoint before the final position, preform a minimal demuxing until final position (to get proper last_pts context across all streams).
#* With luck this seek will not need an underlying seek, if you have not flushed the buffer since the requested position.
#* In most common case, ''stopper.back_ptr'' points to same syncpoint as the start of the linear search, as both syncpoints point to the same rare video keyframe.
#* If only video stream is active and the only non active stream is audio, you will most likely end your linear search immediately after ''stopper_syncpoint'' by finding an audio keyframe. Afterwards you will rewind right back to ''start'', and, since buffer hasn't been flushed, this will not need an underlying seek.

=== Index ===
With index, binary search step is skipped, and a much more limited linear search used, between two immediate syncpoints. The syncpoint picked is the highest possible one that has a keyframe for each active stream past the syncpoint with a pts lower than requested pts. The end of the linear search is the syncpoint immediately following.

=== Dynamic Index ===
Create the index in the same manner as creating the index in the muxer, remembering keyframes and EOR at syncpoint positions.
With one big difference - dynamic index can have gaps, thanks to seeking. Every syncpiont entry in the dynamic index has a flag indicating if it has a "unresearched region" gap from last syncpoint.

In seeking, dynamic index is used in the same manner as complete index. However, when deciding a syncpoint, the entire range of the syncpoint picked until the first syncpoint with a pts higher than requested is checked for having been already researched. If a "hole" is found anywhere in this range, dynamic index is disregarded and full binary search is performed.

=== End of Relavence ===
Behavior with linear search:
* Treat EOR frames same as keyframes. Seeing an EOR frame for an active stream causes the stream to be ignored until the next keyframe of same stream.
* If all active streams are EOR by end of linear search, just use start of linear search as final seeking position.

For index:
* When picking the correct syncpoint to start linear search, ignore streams which have EOR with pts lower than requested pts and no keyframe with pts lower than requested pts.
* If all active streams are EOR, pick the syncpoint immediately before the syncpoint with the last EOR across all streams with pts lower than requested pts.

[[Category:Container Formats]]

NUT

2006-02-24T19:22:23Z

Ods15: Dynamic index and EOR

* Extensions: nut
* Website: http://www.nut.hu/

NUT is a container format under construction by [[MPlayer]] and [[FFmpeg]] developers.
Its main goals are to be simple, flexible and error-resistant while maintaining the smallest possible overhead.

== NUT seeking algo in libnut ==

=== Step 1 - Binary search and linear interpolation ===

==== Startup ====
Go to beginning of file if first syncpoint has not been found, and then go to EOF and search backward to find last syncpoint.
Pick the closest possible syncpoints for requested pts from syncpoint cache, one higher and one lower. If requested pts is lower than first syncpoint or higher than last syncpoint, then seek to either of those syncpoints and end seek.

Binary search is ended when the entire region between the 2 syncpoints picked has been scanned. Which could even be before it has begun thanks to syncpoint cache.

==== Guess position ====
Best results have been achieved by combining both linear interpolation and binary search, giving most of the weight to interpolation.

;hi, hi_pd: file position and timestamp of the top edge of the binary search.
;lo, lo_pd: file position and timestamp of the bottom edge of the binary search.
;time_pos: Requested pts.
;guess: begginning of linear search for syncpoint.

#define INTERPOLATE_WEIGHT (7./8)
if (hi - lo < nut->max_distance*2) guess = lo + 8;
else { // linear interpolation
double a = (double)(hi - lo) / (hi_pd - lo_pd);
guess = lo + a * (time_pos - lo_pd);
guess = guess * INTERPOLATE_WEIGHT + (lo+hi)/2 * (1 - INTERPOLATE_WEIGHT);
if (hi - guess < nut->max_distance*2) guess = hi - nut->max_distance*2; //(lo + hi)/2;
}
if (guess < lo + 8) guess = lo + 8;

The first conditional prevents too much recursing when the distance is already low. The last conditional prevents infinite loop of syncpoint search constantly finding ''lo'' and achieving nothing.

==== Binary search ====
Now, find a syncpoint, bounded between ''guess'' and ''hi''. If it has a timestamp higher than requested pts, then replace ''hi'' and ''hi_pd'', otherwise replace ''lo'' and ''lo_pd''.
If a syncpoint was not found between ''guess'' and ''hi'', then, if ''guess'' is smaller or equal to ''lo + 11'', then you have scanned the entire area between ''lo'' and ''hi'', and your binary search is done. Otherwise, replace ''hi'' with ''guess'' and repeat the binary search.

After finding the 2 closest syncpoints bounding your requested pts, the bounds of linear are search are:

*start = lo_s.pos - (lo_s.back_ptr * 8 + 7);
*end = lo_s.pos;
*stopper = hi_s;

''stopper'' is used later to end linear search prematurely. Note that it is the '''top''' edge of binary search, meaning, it has a timestamp higher than requested pts.

=== Step 2 - Linear search ===

==== Bounds of linear search ====
Linear search of course ends at ''end'', however, it can end earlier:
* When you find a frame of any stream, with a dts higher than requested pts.
* When you find a frame for '''all''' active streams with a pts higher than requested pts.
* When you find a syncpoint immediately following the syncpoint pointed to by ''stopper'''s back_ptr, (from here on this syncpoint will be called ''stopper_syncpoint'') '''and''' all streams are active.
* When you find a keyframe for all '''non'''-active streams after ''stopper_syncpoint'' with a pts lower than ''stopper.timestamp''. The logic is:
** ''stopper.timestamp'' is higher than requested pts.
** ''stopper_syncpoint'' is '''not''' the syncpoint pointed to by ''stopper.back_ptr'', but the one immediately following.
** If there was a keyframe for every non active stream after ''stopper_syncpoint'', with a pts lower than ''stopper.timestamp'', then the reason ''stopper'' does not point to ''stopper_syncpoint'' must be that there are no keyframes for '''active''' streams with a pts lower than ''stopper.timestamp'' after ''stopper_syncpoint''.
** There might be more keyframes in the region with a pts higher than ''stopper.timestamp'', but those are irrelevant because they are higher than requested pts.

==== Linear search implementation ====

# Start at ''start''.
# Search for syncpoint. If it is further than ''start + 7'', then the file is errored, and you can start playing immediately from this syncpoint.
# Perform full demuxing, buffering everything read. If you encounter any NUT error during demuxing, seek back to the syncpoint after ''start'' and end seek.
# On every syncpoint, flush the buffer and cache the syncpoint position.
#* If this syncpoint is ''stopper_syncpoint'', then do not flush the buffer, as it would be possible the linear search would end immediatelty afterwards and a second underlying seek would not be necessary.
# When finding keyframe of active stream with pts lower than requested pts, store position of keyframe. Discard previous value.
# End linear search as necessary by bounds given above.
# Pick the lowest value from positions of keyframes for active streams. This is the final position.
# Seek to closest syncpoint before the final position, preform a minimal demuxing until final position (to get proper last_pts context across all streams).
#* With luck this seek will not need an underlying seek, if you have not flushed the buffer since the requested position.
#* In most common case, ''stopper.back_ptr'' points to same syncpoint as the start of the linear search, as both syncpoints point to the same rare video keyframe.
#* If only video stream is active and the only non active stream is audio, you will most likely end your linear search immediately after ''stopper_syncpoint'' by finding an audio keyframe. Afterwards you will rewind right back to ''start'', and, since buffer hasn't been flushed, this will not need an underlying seek.

=== Index ===
With index, binary search step is skipped, and a much more limited linear search used, between two immediate syncpoints. The syncpoint picked is the highest possible one that has a keyframe for each active stream past the syncpoint with a pts lower than requested pts. The end of the linear search is the syncpoint immediately following.

=== Dynamic Index ===
Create the index in the same manner as creating the index in the muxer, remembering keyframes and EOR at syncpoint positions.
With one big difference - dynamic index can have gaps, thanks to seeking. Every syncpiont entry in the dynamic index has a flag indicating if it has a "unresearched region" gap from last syncpoint.

In seeking, dynamic index is used in the same manner as complete index. However, when deciding a syncpoint, the entire range of the syncpoint picked until the first syncpoint with a pts higher than requested is checked for having been already researched. If a "hole" is found anywhere in this range, dynamic index is disregarded and full binary search is performed.

=== End of Relavence ===
Behavior with linear search:
* Treat EOR frames same as keyframes. Seeing an EOR frame for an active stream causes the stream to be ignored until the next keyframe of same stream.
* If all active streams are EOR by end of linear search, just use start of linear search as final seeking position.

For index:
* When picking the correct syncpoint to start linear search, ignore streams which have EOR with pts lower than requested pts and no keyframe with pts lower than requested pts.
* If all active streams are EOR, pick the syncpoint immediately before the syncpoint with the last EOR across all streams with pts lower than requested pts.

[[Category:Container Formats]]

User talk:Snacky

2006-02-03T20:54:13Z

Ods15: that redirect probably doesn't belong there

NUT

2006-02-02T08:48:43Z

Ods15: /* Bounds of linear search */ typo

NUT

2006-02-02T08:02:03Z

Ods15: /* Guess position */ libnut changed, max_distance*2

NUT

2006-02-02T07:53:13Z

Ods15: syncpoints have timestamps, not pts. Bounds of linear search are wrong

NUT

2006-02-02T01:22:50Z

Ods15: /* Linear search implementation */ i meant bullets

NUT

2006-02-02T01:22:23Z

Ods15: /* Linear search implementation */ more about buffering and seeking

NUT

2006-02-02T01:12:46Z

Ods15: /* Linear search implementation */ handling NUT errors

NUT

2006-02-02T01:04:07Z

Ods15: /* Binary search */ clarify

NUT

2006-02-02T01:00:53Z

Ods15: /* Bounds of linear search */ oops, lower, not higher

NUT

2006-02-02T00:55:27Z

Ods15: /* Index */ I really did mean a single syncpoint, this was a grammar mistake, not a typo

NUT

2006-02-01T17:16:08Z

Ods15: Explain NUT seeking algo

* Extensions: nut
* Website: http://www.nut.hu/

NUT is (still) experimental format under construction by [[MPlayer]] and [[FFmpeg]] developers.
Main goals are to be simple, flexible, error resistant and of course with smallest possible overhead.

== NUT seeking algo in libnut ==

=== Step 1 - Binary search and linear interpolation ===

==== Startup ====
Go to begginning of file if first syncpoint has not been found, and then go to EOF and search backward to find last syncpoint.
Pick the closest possible syncpoints for requested pts, one higher and one lower. If requested pts is lower than first syncpoint or higher than last syncpoint, then seek to either of those syncpoints and end seek.

Binary search is ended when the entire region between the 2 syncpoints picked has been scanned. Which could even be before it has begun thanks to syncpoint cache.

==== Guess position ====
Best results have been achieved by combining both linear interpolation and binary search, giving most of the weight to interpolation.

;hi, hi_pd: file position and timestamp of the top edge of the binary search.
;lo, lo_pd: file position and timestamp of the bottom edge of the binary search.
;time_pos: Requested pts.
;guess: begginning of linear search for syncpoint.

#define INTERPOLATE_WEIGHT (7./8)
if (hi - lo < nut->max_distance) guess = lo + 8;
else { // linear interpolation
double a = (double)(hi - lo) / (hi_pd - lo_pd);
guess = lo + a * (time_pos - lo_pd);
guess = guess * INTERPOLATE_WEIGHT + (lo+hi)/2 * (1 - INTERPOLATE_WEIGHT);
if (hi - guess < nut->max_distance*2) guess = hi - nut->max_distance*2; //(lo + hi)/2;
}
if (guess < lo + 8) guess = lo + 8;

The first conditional prevent too much recursing when the distance is already low. The last conditional prevents infinite loop of syncpoint search constantly finding ''lo'' and achieving nothing.

==== Binary search ====
Now, find a syncpoint, bounded between ''guess'' and ''hi''. If it has a pts higher than requested pts, then replace ''hi'' and ''hi_pd'', otherwise replace ''lo'' and ''lo_pd''.
If a syncpoint was not found between ''guess'' and ''hi'', then, if ''guess'' is smaller or equal to ''lo + 11'', then you have scanned the entire area between ''lo'' and ''hi'', and your binary search is done. Otherwise, replace ''hi'' with ''guess'' and repeat the binary search.

After finding the 2 closest syncpoints bounding your requested pts, the bounds of linear are search are:

*start = lo_s.pos - (lo_s.back_ptr * 8 + 7);
*end = lo_s.pos;
*stopper = hi_s;

''stopper'' is used later to end linear search prematurely.

=== Step 2 - Linear search ===

==== Bounds of linear search ====
Linear search ofcourse ends at ''end'', however, it can end earlier:
* When you find any frame of an active stream, with a pts higher than requested pts.
* When you find a syncpoint immediately following the syncpoint pointed to by ''stopper'''s back_ptr, (from here on this syncpoint will be called ''stopper_syncpoint'') '''and''' all streams are active.
* When you find a keyframe for all '''non'''-active streams after after ''stopper_syncpoint'' with a pts higher than ''stopper.pts''. The logic is:
** ''stopper.pts'' is higher than requested pts.
** ''stopper_syncpoint'' is '''not''' the syncpoint pointed to by ''stopper.back_ptr'', but the one immediately following.
** If there was a keyframe for every non active stream after ''stopper_syncpoint'', with a pts lower than ''stopper.pts'', then the reason ''stopper'' does not point to ''stopper_syncpoint'' must be that there are no keyframes for '''active''' streams with a pts lower than ''stopper.pts'' after ''stopper_syncpoint''.
** There might be more keyframes in the region with a pts higher than ''stopper.pts'', but those are irrelavent because they are higher than requested pts.

==== Linear search implementation ====

# Start at ''start''.
# Search for syncpoint. If it is further than ''start + 7'', then the file is errored, and you can start playing immediately from this syncpoint.
# Preform full demuxing, buffering everything read.
# On every syncpoint, flush the buffer and cache the syncpoint position.
# When finding keyframe of active stream with pts lower than requested pts, store position of keyframe. Discard previous value.
# End linear search as necessary by bounds given above.
# Pick the lowest value from positions of keyframes for active streams, This is the final position.
# Seek to closest syncpoint before the final position, preform a minimal demuxing until final position (to get proper last_pts context across all streams).

=== Index ===
With index, binary search step is skipped, and a much more limited linear search used, between two immediate syncpoints. The syncpoint picked are the highest possible ones that have a keyframe for each active stream past the syncpoint with a pts lower than requested pts. The end of the linear search is the syncpoint immediately following.

Dynamic index is used in the same manner as complete index. However, when deciding a syncpoint, the entire range of the syncpoint picked until the first syncpoint with a pts higher than requested is checked for having been already reaserched. If a "hole" is found anywhere in this range, dynamic index is disregarded and full binary search is preformed.

[[Category:Container Formats]]

User:Ods15

2006-01-17T05:31:32Z

Ods15: me

I'm Oded Shimon, [[MPlayer]] developer. My main current project right now is [[NUT]].

Microsoft Audio/Video Interleaved

2006-01-16T18:56:07Z

Ods15: /* AVI */

Uses RIFF tree for structure.

== RIFF ==

General structure for all RIFF nodes:

Nodes can be data or '''LIST''', data structure is:

4 bytes name (a.k.a. FourCC)
4 bytes length, 32 bit integer in little-endian
''length'' bytes data
optionally 1 byte padding if length is odd

'''LIST''' structure is:

4 bytes string "LIST"
4 bytes length, 32 bit integer in little-endian
4 bytes name
''length'' bytes data - data is a list of nodes.
optionally 1 byte padding if length is odd

An entire RIFF file has the structure:

4 bytes string "RIFF"
4 bytes length, 32 bit integer in little-endian
4 bytes name
''length'' bytes data - data is a list of nodes.

== AVI ==

An AVI has this RIFF structure:

RIFF "AVI " (space at end)
LIST "hdrl"
DATA "avih", len: 56
LIST "strl"
DATA "strh", len: 56
DATA "strf"
''LIST "strl"''
...
''LIST: name: `INFO''' (optional)
...
LIST "movi"
DATA "00dc"
DATA "01wb"
...
DATA "idx1"

AVI

2006-01-16T18:50:24Z

Ods15: redirect

#REDIRECT [[Microsoft Audio/Video Interleaved]]

Microsoft Audio/Video Interleaved

2006-01-16T18:46:13Z

Ods15:

Uses RIFF tree for structure.

== RIFF ==

General structure for all RIFF nodes:

Nodes can be data or '''LIST''', data structure is:

4 bytes name (a.k.a. FourCC)
4 bytes length, 32 bit integer in little-endian
''length'' bytes data
optionally 1 byte padding if length is odd

'''LIST''' structure is:

4 bytes string "LIST"
4 bytes length, 32 bit integer in little-endian
4 bytes name
''length'' bytes data - data is a list of nodes.
optionally 1 byte padding if length is odd

An entire RIFF file has the structure:

4 bytes string "RIFF"
4 bytes length, 32 bit integer in little-endian
4 bytes name
''length'' bytes data - data is a list of nodes.

== AVI ==

An AVI has this RIFF structure:

RIFF: name: `AVI ' (space at end)
LIST: name: `hdrl'
DATA: name: `avih', len: 56
LIST: name: `strl'
DATA: name: `strh', len: 56
DATA: name: `strf'
LIST: name: `strl'
DATA: name: `strh', len: 56
DATA: name: `strf'
LIST: name: `INFO'
optional info
LIST: name: `movi'
DATA: name: `00dc'
DATA: name: `01wb'
...
DATA: name: `idx1'