[x264-devel] Doubt in Trellis Algorithm for SlicePath analysis

[Jason Garrett-Glaser]

On Tue, May 25, 2010 at 4:41 PM, Nageswara Gunupudi
<Nageswara.Gunupudi at harmonicinc.com> wrote:
> Hi,
>
>
>
> I have doubt in x264_slicetype_analyse function which try to find the best
> GOP structure with B frames when X264_B_ADAPT_TRELLIS is used.
>
> When analyzing the each slicetype path, the best paths are initialized and
> the frame type analysis is carried over the number of frames in lookahead
> using following loop.
>
>
>
> for( int j = 2; j < num_frames; j++ )
>
>      x264_slicetype_path( h, &a, frames, j, best_paths );
>
>
>
> Then in x264_slicetype_path, the possible paths are initialized and best
> costs are estimated over every path in the following loop
>
>
>
> for( int path = 0; path < num_paths; path++ )
>
>   {
>
>         int len = length - (path + 1);
>
>         memcpy( paths[idx], best_paths[len % (X264_BFRAME_MAX+1)], len );
>
>         memset( paths[idx]+len, 'B', path );
>
>         strcpy( paths[idx]+len+path, "P" );
>
>         int cost = x264_slicetype_path_cost( h, a, frames, paths[idx],
> best_cost );
>
>
>
>               …………….
>
>        }
>
>
>
> My doubt is, when looking the two loops, is not there are some paths
> iterated more than once redundantly? Since the number possible paths are
> considered the later loop in the available lookahead frames. Please correct
> me if I am wrong.

Yes, redundant work is performed.  However, x264 internally caches the
results of each frame cost analysis, so no actual extra analysis is
done, just extra path calculations.  The path calculations have an
utterly trivial CPU cost, so it's not worth bothering with extra logic
there.

Dark Shikari