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

[Michael Niedermayer]

Hi

On Saturday 01 January 2005 12:02, Reimar Döffinger wrote:
> Hi,
>
> > 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


> 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"
if this bothers u then just ensure that your comparission function never 
returns 0


> 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

[...]
-- 
Michael

"I do not agree with what you have to say, but I'll defend to the death your
right to say it." -- Voltaire