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

[D Richard Felker III]

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.

rich