[MPlayer-users] [BUGREPORT] ODML avi_idx_quicksort SEGFAULT

[Reimar Döffinger]

Hi,
On Tue, Dec 28, 2004 at 02:38:08PM -0800, RC wrote:
> On Tue, 28 Dec 2004 12:20:19 +0100
> Reimar Döffinger <Reimar.Doeffinger at stud.uni-karlsruhe.de> wrote:
> 
> > -noodml in mencoder should probably fix it, too...
> 
> Not with a 4GB+ file, even with largefile support compiled in.
> 
> > All suggested solutions are very ugly IMHO.
> 
> Your bubble-sort patch just seems to hang there for several minutes. 

Yes, I underestimated the size of the problem there.

> The (fixed) half-iterative quicksort patch seems to work well-enough.

Thanks for testing. Could you try the attached patch? I fixed
compilation for gcc 2.95 and randomized pivot element selection (hey, I
have a lecture on randomized algorithms this semester after all ;-) ).
With that the extreme cases should hardly ever happen anymore - despite
my dislike of randomness in algorithms it sometimes makes sense...

Greetings,
Reimar Döffinger
-------------- next part --------------
Index: libmpdemux/aviheader.c
===================================================================
RCS file: /cvsroot/mplayer/main/libmpdemux/aviheader.c,v
retrieving revision 1.63
diff -u -r1.63 aviheader.c
--- libmpdemux/aviheader.c	20 Oct 2004 02:13:33 -0000	1.63
+++ libmpdemux/aviheader.c	29 Dec 2004 13:43:19 -0000
@@ -44,15 +44,25 @@
     return 0;
 }
 
-/*
+/**
  * Simple quicksort for AVIINDEXENTRYs
+ * To avoid too deep recursion, the bigger part is handled iteratively,
+ * thus limiting recursion to log2(n) levels.
+ * The pivot element is randomized to "even out" otherwise extreme cases.
  */
 static void avi_idx_quicksort(AVIINDEXENTRY *idx, int from, int to)
 {
     AVIINDEXENTRY temp;
-    int lo = to;
-    int hi = from;
-    off_t pivot_ofs = AVI_IDX_OFFSET(&idx[(from + to) / 2]);
+    int lo;
+    int hi;
+    off_t pivot_ofs;
+    int pivot_idx;
+  while (from < to) {
+    pivot_idx = from;
+    pivot_idx += rand() % (to - from + 1);
+    pivot_ofs = AVI_IDX_OFFSET(&idx[pivot_idx]);
+    lo = to;
+    hi = from;
     do {
 	while(pivot_ofs < AVI_IDX_OFFSET(&idx[lo])) lo--;
 	while(pivot_ofs > AVI_IDX_OFFSET(&idx[hi])) hi++;
@@ -65,8 +75,14 @@
 	    lo--; hi++;
 	}
     } while (lo >= hi);
-    if (from < lo) avi_idx_quicksort(idx, from, lo);
-    if (to > hi) avi_idx_quicksort(idx, hi, to);
+    if ((lo - from) < (to - hi)) {
+      avi_idx_quicksort(idx, from, lo);
+      from = hi;
+    } else {
+      avi_idx_quicksort(idx, hi, to);
+      to = lo;
+    }
+  }
 }
 
 void read_avi_header(demuxer_t *demuxer,int index_mode){