avi_idx_quicksort overflows stack on >2GB ODML file

[phillip@…]

A large ODML (2.7GB) file created with mencoder was edited with VirtualDub;
sections cut out ond then "direct stream copy" saved. The resulting file is >2GB
and plays fine with Windows Media Player. When mplayer tries to play it
segfaults in avi_idx_quicksort. A bt under gdb suggests that the particular file
provides a pathological case for this quicksort and thousands of calls are made
overflowing the stack. I can upload the file if required but it is large, as
mentioned.

A test replacement of the avi_idx_quicksort with one using qsort in glibc seems
to fix the problem.

[partial gdb bt follows]
#22561 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=229376, to=292681)
at aviheader.c:69
#22562 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=229376, to=292683)
at aviheader.c:69
#22563 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=229376, to=292685)
at aviheader.c:69
#22564 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=229376, to=292687)
at aviheader.c:69
#22565 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=229376, to=292689)
at aviheader.c:69
#22566 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=229376, to=292691)
at aviheader.c:69
#22567 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=229376, to=292693)
at aviheader.c:69
#22568 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=229376, to=292695)
at aviheader.c:69
#22569 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=229376, to=292697)
at aviheader.c:69
#22570 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=229376, to=292699)
at aviheader.c:69
#22571 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=229376, to=292701)
at aviheader.c:69
#22572 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=229376, to=292703)
at aviheader.c:69
#22573 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=229376, to=292705)
at aviheader.c:69
#22574 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=229376, to=292707)
at aviheader.c:69
#22575 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=229376, to=292709)
at aviheader.c:69
#22576 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=229376, to=292711)
at aviheader.c:69
#22577 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=229376, to=292713)
at aviheader.c:69
#22578 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=229376, to=292715)
at aviheader.c:69
#22579 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=229376, to=292716)
at aviheader.c:69
#22580 0x081bb412 in avi_idx_quicksort (idx=0x4167a008, from=63343, to=292716)
at aviheader.c:69
#22581 0x081bb412 in avi_idx_quicksort (idx=0x4167a008, from=0, to=292716) at
aviheader.c:69
#22582 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=292717) at
aviheader.c:69
#22583 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=407404) at
aviheader.c:69
#22584 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=407405) at
aviheader.c:69
#22585 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=464748) at
aviheader.c:69
#22586 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=464749) at
aviheader.c:69
#22587 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=493420) at
aviheader.c:69
#22588 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=493421) at
aviheader.c:69
#22589 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=507756) at
aviheader.c:69
#22590 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=507757) at
aviheader.c:69
#22591 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=514924) at
aviheader.c:69
#22592 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=514925) at
aviheader.c:69
#22593 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=518508) at
aviheader.c:69
#22594 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=518509) at
aviheader.c:69
#22595 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=520300) at
aviheader.c:69
#22596 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=520301) at
aviheader.c:69
---Type <return> to continue, or q <return> to quit---
#22597 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=521196) at
aviheader.c:69
#22598 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=521197) at
aviheader.c:69
#22599 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=521644) at
aviheader.c:69
#22600 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=521645) at
aviheader.c:69
#22601 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=521868) at
aviheader.c:69
#22602 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=521869) at
aviheader.c:69
#22603 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=521980) at
aviheader.c:69
#22604 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=521981) at
aviheader.c:69
#22605 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=522036) at
aviheader.c:69
#22606 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=522037) at
aviheader.c:69
#22607 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=522064) at
aviheader.c:69
#22608 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=522065) at
aviheader.c:69
#22609 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=522067) at
aviheader.c:69
#22610 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=522071) at
aviheader.c:69
#22611 0x081bb42a in avi_idx_quicksort (idx=0x4167a008, from=0, to=522078) at
aviheader.c:69
#22612 0x081be176 in read_avi_header (demuxer=0x85d72e0, index_mode=-1) at
aviheader.c:519

---

The verbose output from mplayer before the SEGSEGV follows:

MPlayer 1.0pre5-3.3.4 (C) 2000-2004 MPlayer Team

CPU: Advanced Micro Devices Athlon MP/XP Thoroughbred 1798 MHz (Family: 6,
Stepping: 1)
Detected cache-line size is 64 bytes
CPUflags: MMX: 1 MMX2: 1 3DNow: 1 3DNow2: 1 SSE: 1 SSE2: 0
Compiled for x86 CPU with extensions: MMX MMX2 3DNow 3DNowEx SSE

Reading config file /usr/local/etc/mplayer/mplayer.confReading config file
/home/phillip/.mplayer/config
Reading /home/phillip/.mplayer/codecs.conf: Reading
/usr/local/etc/mplayer/codecs.conf: Using built-in default codecs.conf.
CommandLine: '-v' '-vo' 'x11' '/mnt/burner/Minority_Report.avi'
init_freetype
get_path('font/font.desc') -> '/home/phillip/.mplayer/font/font.desc'
font: can't open file: /home/phillip/.mplayer/font/font.desc
font: can't open file: /usr/local/share/mplayer/font/font.desc
Using MMX (with tiny bit MMX2) Optimized OnScreenDisplay
Using Linux hardware RTC timing (1024Hz).
Terminal type `rxvt' is not defined.
get_path('input.conf') -> '/home/phillip/.mplayer/input.conf'
get_path('Minority_Report.avi.conf') ->
'/home/phillip/.mplayer/Minority_Report.avi.conf'

Playing /mnt/burner/Minority_Report.avi.
[file] File size is 2332971008 bytes
STREAM: [file] /mnt/burner/Minority_Report.avi
STREAM: Description: File
STREAM: Author: Albeu
STREAM: Comment: based on the code from ??? (probably Arpi)
AVI file format detected.
list_end=0x2292
======= AVI Header =======
us/frame: 33367 (fps=29.970)
max bytes/sec: 0
padding: 0
MainAVIHeader.dwFlags: (272) HAS_INDEX IS_INTERLEAVED
frames total: 239173 initial: 0
streams: 2
Suggested BufferSize: 0
Size: 640 x 480
==========================
list_end=0x10F4
==> Found video stream: 0

STREAM Header =====

Type: vids FCC: DIVX (58564944)
Flags: 0
Priority: 0 Language: 0
InitialFrames: 0
Rate: 2997/100 = 29.970
Start: 0 Len: 261046
Suggested BufferSize: 92968
Quality 0
Sample size: 0
==========================
found 'bih', 40 bytes of 40
======= VIDEO Format ======

biSize 40
biWidth 640
biHeight 480
biPlanes 1
biBitCount 24
biCompression 1482049860='DIVX'
biSizeImage 921600

===========================Regenerating keyframe table for DIVX 4 video

AVI Super Index Header ==

FCC (indx) dwSize (4120) wLongsPerEntry(4)
bIndexSubType (0) bIndexType (0)
nEntriesInUse (32) dwChunkId (00dc)
dwReserved[0] (0) dwReserved[1] (0) dwReserved[2] (0)

===========================
ODML (00dc): [0] 0x000000008ace8856 0x10020 8192
ODML (00dc): [1] 0x000000008acf8876 0x10020 8192
ODML (00dc): [2] 0x000000008ad08896 0x10020 8192
ODML (00dc): [3] 0x000000008ad188b6 0x10020 8192
ODML (00dc): [4] 0x000000008ad288d6 0x10020 8192
ODML (00dc): [5] 0x000000008ad388f6 0x10020 8192
ODML (00dc): [6] 0x000000008ad48916 0x10020 8192
ODML (00dc): [7] 0x000000008ad58936 0x10020 8192
ODML (00dc): [8] 0x000000008ad68956 0x10020 8192
ODML (00dc): [9] 0x000000008ad78976 0x10020 8192
ODML (00dc): [10] 0x000000008ad88996 0x10020 8192
ODML (00dc): [11] 0x000000008ad989b6 0x10020 8192
ODML (00dc): [12] 0x000000008ada89d6 0x10020 8192
ODML (00dc): [13] 0x000000008adb89f6 0x10020 8192
ODML (00dc): [14] 0x000000008adc8a16 0x10020 8192
ODML (00dc): [15] 0x000000008add8a36 0x10020 8192
ODML (00dc): [16] 0x000000008ade8a56 0x10020 8192
ODML (00dc): [17] 0x000000008adf8a76 0x10020 8192
ODML (00dc): [18] 0x000000008ae08a96 0x10020 8192
ODML (00dc): [19] 0x000000008ae18ab6 0x10020 8192
ODML (00dc): [20] 0x000000008ae28ad6 0x10020 8192
ODML (00dc): [21] 0x000000008ae38af6 0x10020 8192
ODML (00dc): [22] 0x000000008ae48b16 0x10020 8192
ODML (00dc): [23] 0x000000008ae58b36 0x10020 8192
ODML (00dc): [24] 0x000000008ae68b56 0x10020 8192
ODML (00dc): [25] 0x000000008ae78b76 0x10020 8192
ODML (00dc): [26] 0x000000008ae88b96 0x10020 8192
ODML (00dc): [27] 0x000000008ae98bb6 0x10020 8192
ODML (00dc): [28] 0x000000008aea8bd6 0x10020 8192
ODML (00dc): [29] 0x000000008aeb8bf6 0x10020 8192
ODML (00dc): [30] 0x000000008aec8c16 0x10020 8192
ODML (00dc): [31] 0x000000008aed8c36 0xddd0 7094
list_end=0x2186
==> Found audio stream: 1

STREAM Header =====

Type: auds FCC: U (55)
Flags: 0
Priority: 0 Language: 0
InitialFrames: 1
Rate: 16000/1 = 16000.000
Start: 0 Len: 139363897
Suggested BufferSize: 8000
Quality 0
Sample size: 1
==========================
found 'wf', 30 bytes of 18
======= WAVE Format =======
Format Tag: 85 (0x55)
Channels: 1
Samplerate: 44100
avg byte/sec: 16000
Block align: 1
bits/sample: 0
cbSize: 12
mp3.wID=1
mp3.fdwFlags=0x2
mp3.nBlockSize=418
mp3.nFramesPerBlock=1
mp3.nCodecDelay=0
===========================

AVI Super Index Header ==

FCC (indx) dwSize (4120) wLongsPerEntry(4)
bIndexSubType (0) bIndexType (0)
nEntriesInUse (32) dwChunkId (01wb)
dwReserved[0] (0) dwReserved[1] (0) dwReserved[2] (0)

===========================
ODML (01wb): [0] 0x000000008aee6a06 0x10020 4380907
ODML (01wb): [1] 0x000000008aef6a26 0x10020 4373440
ODML (01wb): [2] 0x000000008af06a46 0x10020 4373440
ODML (01wb): [3] 0x000000008af16a66 0x10020 4373440
ODML (01wb): [4] 0x000000008af26a86 0x10020 4373440
ODML (01wb): [5] 0x000000008af36aa6 0x10020 4373440
ODML (01wb): [6] 0x000000008af46ac6 0x10020 4373440
ODML (01wb): [7] 0x000000008af56ae6 0x10020 4373440
ODML (01wb): [8] 0x000000008af66b06 0x10020 4373441
ODML (01wb): [9] 0x000000008af76b26 0x10020 4373440
ODML (01wb): [10] 0x000000008af86b46 0x10020 4373440
ODML (01wb): [11] 0x000000008af96b66 0x10020 4373440
ODML (01wb): [12] 0x000000008afa6b86 0x10020 4373440
ODML (01wb): [13] 0x000000008afb6ba6 0x10020 4373440
ODML (01wb): [14] 0x000000008afc6bc6 0x10020 4373440
ODML (01wb): [15] 0x000000008afd6be6 0x10020 4373440
ODML (01wb): [16] 0x000000008afe6c06 0x10020 4373440
ODML (01wb): [17] 0x000000008aff6c26 0x10020 4373441
ODML (01wb): [18] 0x000000008b006c46 0x10020 4373440
ODML (01wb): [19] 0x000000008b016c66 0x10020 4373440
ODML (01wb): [20] 0x000000008b026c86 0x10020 4373440
ODML (01wb): [21] 0x000000008b036ca6 0x10020 4373440
ODML (01wb): [22] 0x000000008b046cc6 0x10020 4373440
ODML (01wb): [23] 0x000000008b056ce6 0x10020 4373440
ODML (01wb): [24] 0x000000008b066d06 0x10020 4373440
ODML (01wb): [25] 0x000000008b076d26 0x10020 4373440
ODML (01wb): [26] 0x000000008b086d46 0x10020 4373441
ODML (01wb): [27] 0x000000008b096d66 0x10020 4373440
ODML (01wb): [28] 0x000000008b0a6d86 0x10020 4373440
ODML (01wb): [29] 0x000000008b0b6da6 0x10020 4373440
ODML (01wb): [30] 0x000000008b0c6dc6 0x10020 4373440
ODML (01wb): [31] 0x000000008b0d6de6 0xdd68 3779787
list_end=0x2292
AVI: dmlh found (size=248) (total_frames=261046)
list_end=0x7EC5AD3E
Found movie at 0x280C - 0x7EC5AD3E
Reading INDEX block, 478347 chunks for 239173 frames (fpos=0x7ec5ad46)
additional RIFF header...
list_end=0x8B0E4B4E
Found movie at 0x280C - 0x8B0E4B4E
AVI: ODML: Building odml index (2 superindexchunks)

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x1F4C) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x460C910) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x8B0FEB8) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0xD0B51EE) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x1165AFD0) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x15B8A792) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x1A0D0BA8) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x1E6B042E) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x22BF8A3A) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x27187556) dwReserved3 (0)

================================ AVI Standard Index Header ========

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x2B6F86EC) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x2FCA6F9C) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x3420EBA0) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x3875B88E) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x3CCFB834) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x41255F42) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x457A7EC8) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x49D66288) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x4E2BC2FA) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x5284FD56) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x56DC407E) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x5B346610) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x5F8B8DB4) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x63E2F17A) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x683BA14C) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x6C9087D0) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x70E2307A) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x75401CEC) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x7995C3B2) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x7DECE22A) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (00dc)
qwBaseOffset (0x82B95962) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix00) dwSize (56776) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (7094) dwChunkId (00dc)
qwBaseOffset (0x871180E8) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x4) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x460C6F2) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x8B0FC9A) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0xD0B4FD0) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x1165ADB2) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x15B8A574) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x1A0D098A) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x1E6B0210) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x22BF881C) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x27187338) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x2B6F84CE) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x2FCA6D7E) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x3420E982) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x3875B670) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x3CCFB616) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x41255D24) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x457A7CAA) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x49D6606A) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x4E2BC0DC) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x5284FB38) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x56DC3E60) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x5B3463F2) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x5F8B8B96) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x63E2EF5C) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x683B9F2E) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x6C9085B2) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x70E22E5C) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x75401ACE) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x7995C194) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x7DECE00C) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (65560) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (8192) dwChunkId (01wb)
qwBaseOffset (0x82B95744) dwReserved3 (0)

===========================

AVI Standard Index Header ==

FCC (ix01) dwSize (56672) wLongsPerEntry(2)
bIndexSubType (0) bIndexType (1)
nEntriesInUse (7081) dwChunkId (01wb)
qwBaseOffset (0x87117ECA) dwReserved3 (0)

===========================

===========================

[phillip@…]

Patch replacing avi_idx_quicksort with one using glibc's qsort

[phillip@…]

A proof of concept patch -- with this change mplayer no longer crashes and can
play and seek around the file without errors.

[reimar]

half-iterative quicksort limiting recursion depth

[reimar]

I prefer not to depend too much on libc and their quicksort implementation
(actually I doubt the usefulness of quicksort anyway, at least in that case).
This patch should make sure that recursion doesn't get deeper than log2(n).
Please test if it fixes your problem (and doesn't break anything else).

[phillip@…]

Fixed half-iterative quicksort patch.

[phillip@…]

The patch works, after some minor changes, see my attachment. It still takes
quite a while: from 30 - 80s depending on the size of the files (>2GB).
Thanks. I think you can close this bug; unless of course you want to change your
mind about glibc's qsort which takes 5s :)

Sorry my patch isn't against CVS but in any case the changes were moving the
assignments of hi and lo inside the loop and changing the loop condition to
(from < to). I've tested 3 different files >2GB created in the same way and they
all work fine.

[phillip@…]

In support of using qsort it is ANSI C and should be available with other libc.
Not that I'm that familiar with autoconf etc but at worst one could check for
qsort in stdlib.h and use it if available. I see no reason to use the (slower)
hand-coded version when a standard library function exists.

[reimar]

(In reply to comment #5)

In support of using qsort it is ANSI C and should be available with other libc.

It's existence may be ANSI C, but not how it works. Current glibc actually does
mergesort instead of quicksort, which has a significiantly different
characteristic... which also makes your comparison a bit unfair (_quicksort uses
quicksort combined with insertion sort).

Not that I'm that familiar with autoconf etc but at worst one could check for

We don't use autoconf, but let's better avoid starting yet another discussion
about that ;-)

qsort in stdlib.h and use it if available. I see no reason to use the (slower)
hand-coded version when a standard library function exists.

And I think it is not at all standard. But also the question would be whether
the hand-coded version is slower in this case or in all cases.
I personally would prefer replacing that loop by bubblesort anyway, it's a
simple and reliable iterative algorithm... But as I don't really know how much
there is to sort, so some testing would be needed...

[reimar]

using bubblesort instead of ugly recursive quicksort

[reimar]

Please test whether the speed of this is acceptable, for my test files it sure
was fast enough...
btw: man qsort says: "If two members compare as equal, their order in the
sorted array is undefined". This might cause problems (although I don't know
the code well enough to know for sure).

[phillip@…]

(In reply to comment #7)

Created an attachment (id=38)
using bubblesort instead of ugly recursive quicksort

Please test whether the speed of this is acceptable, for my test files it sure
was fast enough...

How many elements are sorted in your test files? Edited and unedited files >2G I
checked range from 350k to 750k entries with 4 near 500k. I gave up waiting for
the sort to end after 10mins... The qsort version (yes I realise it is actually
a merge sort with temp storage, but even when I force the use of _quicksort) was
still a few seconds. I'm not sure how entries relate to length etc but the 750k
entry file is nearly 4GB -- 4:10min with a keyframe every second - not typical
I'm sure.

btw: man qsort says: "If two members compare as equal, their order in the
sorted array is undefined". This might cause problems (although I don't know
the code well enough to know for sure).

Can't say I know either but I'm yet to notice any problem in that regard -- I'm
not sure if the old code was a stable sort either though... IIRC merge sort (the
sort qsort really uses is stable)

[reimar]

half-iterative quicksort with random pivot element

[reimar]

This is the version I intend to apply. The extreme cases shouldn't usually
happen with it anymore. Please test, and sorry for the long delay.

[reimar]

Applied that last version.