[MPlayer-cvslog] CVS: main/libmpdemux aviheader.c,1.63,1.64

[Reimar Döffinger]

Hi,

On Sat, Jan 01, 2005 at 01:05:51PM +0100, Michael Niedermayer wrote:
> On Saturday 01 January 2005 12:02, Reimar Döffinger wrote:
> > > On Saturday 01 January 2005 09:39, D Richard Felker III wrote:
> > > > On Sat, Jan 01, 2005 at 01:16:55AM -0500, D Richard Felker III wrote:
> > > > > On Fri, Dec 31, 2004 at 05:02:50PM +0100, Reimar Döffinger CVS wrote:
> > > > > > CVS change done by Reimar Döffinger CVS
> > > > > >
> > > > > > Update of /cvsroot/mplayer/main/libmpdemux
> > > > > > In directory mail:/var2/tmp/cvs-serv30117/libmpdemux
> > > > > >
> > > > > > Modified Files:
> > > > > >  aviheader.c
> > > > > > Log Message:
> > > > > > fix quicksort to avoid stack overflow and extreme runtimes
> > > > > >
> > > > > >
> > > > > > Index: aviheader.c
> > > > > > ===================================================================
> > > > > > RCS file: /cvsroot/mplayer/main/libmpdemux/aviheader.c,v
> > > > > > retrieving revision 1.63
> > > > > > retrieving revision 1.64
> > > > > > diff -u -r1.63 -r1.64
> > > > > > --- aviheader.c 20 Oct 2004 02:13:33 -0000 1.63
> > > > > > +++ aviheader.c 31 Dec 2004 16:02:47 -0000 1.64
> > > > > > @@ -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);
> > > > >
> > > > > imnsho using rand() is forbidden. it corrupts the state of the
> > > > > caller.
> > > >
> > > > not to mention, it also makes debugging hell by making the program
> > > > non-deterministic.
> > >
> > > iam a little curious why libc qsort() isnt simply used?
> >
> > This is an alternative I asked about when posting the patch. What speaks
> > against it from my view is:
> > 1) I don't know if all libc on strange systems implement it.
> 
> i can assure u mplayer wont work on these without modifications, just try a 
> grep qsort *.c lib*/*.c

ok, convinced.

> > 2) There is no specification whatsoever of how this sorting algorithm
> > should behave - e.g. if it is a stable sort. I don't know if this is
> > relevant in this case, but it will lead into debugging hell as well IMHO...
> 
> ISO C standard draft: "If two elements compare as equal, their order in the 
> sorted array is unspecified"

Yes, that's in the qsort manpage, too.

> if this bothers u then just ensure that your comparission function never 
> returns 0

I'm not too comfortable with the fact the the implementation is
completely open. But well..

> > 3) That it has to use callbacks for comparison puts limits on
> > performance, although the implementation (usually?) is much better I
> > have to admit.
> 
> well the callback isnt needed, its just a matter of the compiler being able to 
> inline it, which is easily possible for these simple cases

I think the qsort function is already compiled (in the libc) so how
should the compiler be able to do inlining?

Anyway, what do you think about the attached patch? Would that be okay?
The comparision function is a bit ugly IMHO, but simply a-b won't work
because they are off_t and the return value is only int...

Greetings,
Reimar Döffinger
-------------- next part --------------
Index: libmpdemux/aviheader.c
===================================================================
RCS file: /cvsroot/mplayer/main/libmpdemux/aviheader.c,v
retrieving revision 1.64
diff -u -r1.64 aviheader.c
--- libmpdemux/aviheader.c	31 Dec 2004 16:02:47 -0000	1.64
+++ libmpdemux/aviheader.c	1 Jan 2005 13:11:10 -0000
@@ -44,45 +44,10 @@
     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;
-    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++;
-	if(hi <= lo) {
-	    if (hi != lo) {
-		memcpy(&temp, &idx[lo], sizeof(temp));
-		memcpy(&idx[lo], &idx[hi], sizeof(temp));
-		memcpy(&idx[hi], &temp, sizeof(temp));
-	    }
-	    lo--; hi++;
-	}
-    } while (lo >= hi);
-    if ((lo - from) < (to - hi)) {
-      avi_idx_quicksort(idx, from, lo);
-      from = hi;
-    } else {
-      avi_idx_quicksort(idx, hi, to);
-      to = lo;
-    }
-  }
+int avi_idx_cmp(const void *elem1,const void *elem2) {
+  register off_t a = AVI_IDX_OFFSET((AVIINDEXENTRY *)elem1);
+  register off_t b = AVI_IDX_OFFSET((AVIINDEXENTRY *)elem2);
+  return (a > b) - (b > a);
 }
 
 void read_avi_header(demuxer_t *demuxer,int index_mode){
@@ -535,7 +500,7 @@
 	    }
 	}
     }
-    avi_idx_quicksort(priv->idx, 0, priv->idx_size-1);
+    qsort(priv->idx, priv->idx_size, sizeof(AVIINDEXENTRY), avi_idx_cmp);
 
     /*
        Hack to work around a "wrong" index in some divx odml files