[MPlayer-cvslog] CVS: main/libmpdemux aviheader.c,1.63,1.64
D Richard Felker III
dalias at aerifal.cx
Sat Jan 1 09:39:04 CET 2005
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.
rich
More information about the MPlayer-cvslog
mailing list