（十八）macroblock-tree算法实现1：x264_ma

x264_macroblock_tree函数的源码如下：

static void x264_macroblock_tree( x264_t *h, x264_mb_analysis_t *a, x264_frame_t **frames, int num_frames, int b_intra )
{
    int idx = !b_intra;
    int last_nonb, cur_nonb = 1;
    int bframes = 0;

    x264_emms();
    float total_duration = 0.0;
    for( int j = 0; j <= num_frames; j++ )
        total_duration += frames[j]->f_duration;
    float average_duration = total_duration / (num_frames + 1);

    int i = num_frames;

    if( b_intra )
        x264_slicetype_frame_cost( h, a, frames, 0, 0, 0 );  //计算帧内损耗

    while( i > 0 && IS_X264_TYPE_B( frames[i]->i_type ) ) //由后往前找到第一个非B帧
        i--;
    last_nonb = i;

    /* Lookaheadless MB-tree is not a theoretically distinct case; the same extrapolation could
     * be applied to the end of a lookahead buffer of any size.  However, it's most needed when
     * lookahead=0, so that's what's currently implemented. */
    if( !h->param.rc.i_lookahead )  //没有lookahead的情况，先忽略
    {
        if( b_intra )
        {
            memset( frames[0]->i_propagate_cost, 0, h->mb.i_mb_count * sizeof(uint16_t) );
            memcpy( frames[0]->f_qp_offset, frames[0]->f_qp_offset_aq, h->mb.i_mb_count * sizeof(float) );
            return;
        }
        XCHG( uint16_t*, frames[last_nonb]->i_propagate_cost, frames[0]->i_propagate_cost );
        memset( frames[0]->i_propagate_cost, 0, h->mb.i_mb_count * sizeof(uint16_t) );
    }
    else
    {
        if( last_nonb < idx )
            return;
        //将最后一个非B帧的i_propagate_cost设为0
        memset( frames[last_nonb]->i_propagate_cost, 0, h->mb.i_mb_count * sizeof(uint16_t) );
    }

    while( i-- > idx )  //由后往前遍历
    {
        cur_nonb = i;
        while( IS_X264_TYPE_B( frames[cur_nonb]->i_type ) && cur_nonb > 0 ) //当前非B帧
            cur_nonb--;
        if( cur_nonb < idx )
            break;
        x264_slicetype_frame_cost( h, a, frames, cur_nonb, last_nonb, last_nonb ); //计算当前非B帧与上一个非B帧的帧间损耗
        memset( frames[cur_nonb]->i_propagate_cost, 0, h->mb.i_mb_count * sizeof(uint16_t) ); //将当前非B帧的i_propagate_cost设为0
        bframes = last_nonb - cur_nonb - 1;  //两个非B帧之间B帧的数量
        if( h->param.i_bframe_pyramid && bframes > 1 ) //如果B帧数量大于1
        {
            int middle = (bframes + 1)/2 + cur_nonb;
            x264_slicetype_frame_cost( h, a, frames, cur_nonb, last_nonb, middle ); //计算middle与cur_nonb和last_nonb的帧间损耗
            memset( frames[middle]->i_propagate_cost, 0, h->mb.i_mb_count * sizeof(uint16_t) );
            while( i > cur_nonb )  //遍历剩余的B帧
            {
                int p0 = i > middle ? middle : cur_nonb;
                int p1 = i < middle ? middle : last_nonb;
                if( i != middle )
                {
                    x264_slicetype_frame_cost( h, a, frames, p0, p1, i );
                    x264_macroblock_tree_propagate( h, frames, average_duration, p0, p1, i, 0 ); //计算propagate
                }
                i--;
            }
            x264_macroblock_tree_propagate( h, frames, average_duration, cur_nonb, last_nonb, middle, 1 );
        }
        else  //如果cur_nonb和last_nonb之间没有或只有一个B帧
        {
            while( i > cur_nonb )
            {
                x264_slicetype_frame_cost( h, a, frames, cur_nonb, last_nonb, i );
                x264_macroblock_tree_propagate( h, frames, average_duration, cur_nonb, last_nonb, i, 0 );
                i--;
            }
        }
        x264_macroblock_tree_propagate( h, frames, average_duration, cur_nonb, last_nonb, last_nonb, 1 );
        last_nonb = cur_nonb;
    }

    if( !h->param.rc.i_lookahead )
    {
        x264_slicetype_frame_cost( h, a, frames, 0, last_nonb, last_nonb );
        x264_macroblock_tree_propagate( h, frames, average_duration, 0, last_nonb, last_nonb, 1 );
        XCHG( uint16_t*, frames[last_nonb]->i_propagate_cost, frames[0]->i_propagate_cost );
    }

    x264_macroblock_tree_finish( h, frames[last_nonb], average_duration, last_nonb );
    if( h->param.i_bframe_pyramid && bframes > 1 && !h->param.rc.i_vbv_buffer_size )
        x264_macroblock_tree_finish( h, frames[last_nonb+(bframes+1)/2], average_duration, 0 );
}

如注释所示，macroblock_tree是在lookahead数组中由后往前遍历的，它先找出两个非B帧的位置，然后就算出它们之间的每个B帧的编码损耗，并通过它们的依赖关系，就算出参考帧的传播信息（propagate_cost）。举了个例子帮助理解遍历顺序：

如图所示，假如lookahead数组有10帧图像，类型如图所示，由后往前遍历，得到当前非B帧为cur_nonb等于6，上一个非B帧last_nonb等于10，中间7，8，9都是B帧，首先计算middle（8）和cur_nonb和last_nonb的帧间编码的cost和propagate，然后计算9号合7号的cost和propagate，然后继续往下遍历....

propagate的计算主要是x264_macroblock_tree_propagate函数，在下一篇文章讲解。