[MPlayer-dev-eng] [PATCH] for bug #86 (quicksort for ODML overflows stack).

[Reimar Döffinger]

Hi,
> please comment on the attached patch. Alternative would be to use the
> sorting implementation in libc.
> I will apply within the next days if nobody objects.

I did it again! Well, here is the patch.

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){