frame.c 31.9 KB
Newer Older
Laurent Aimar's avatar
Laurent Aimar committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
/*****************************************************************************
 * frame.c: h264 encoder library
 *****************************************************************************
 * Copyright (C) 2003 Laurent Aimar
 * $Id: frame.c,v 1.1 2004/06/03 19:27:06 fenrir Exp $
 *
 * Authors: Laurent Aimar <fenrir@via.ecp.fr>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111, USA.
 *****************************************************************************/

#include <stdio.h>
#include <string.h>
26
#ifndef _MSC_VER
27
#include <unistd.h>
28
#endif
Laurent Aimar's avatar
Laurent Aimar committed
29 30 31

#include "common.h"

32 33 34
#define PADH 32
#define PADV 32

Laurent Aimar's avatar
Laurent Aimar committed
35 36
x264_frame_t *x264_frame_new( x264_t *h )
{
37
    x264_frame_t *frame = x264_malloc( sizeof(x264_frame_t) );
38
    int i, j;
Laurent Aimar's avatar
Laurent Aimar committed
39

40
    int i_mb_count = h->mb.i_mb_count;
Laurent Aimar's avatar
Laurent Aimar committed
41 42
    int i_stride;
    int i_lines;
43
    int i_padv = PADV << h->param.b_interlaced;
Laurent Aimar's avatar
Laurent Aimar committed
44

45 46
    if( !frame ) return NULL;

47 48
    memset( frame, 0, sizeof(x264_frame_t) );

Laurent Aimar's avatar
Laurent Aimar committed
49
    /* allocate frame data (+64 for extra data for me) */
50 51 52 53
    i_stride = ( ( h->param.i_width  + 15 ) & -16 )+ 2*PADH;
    i_lines  = ( ( h->param.i_height + 15 ) & -16 );
    if( h->param.b_interlaced )
        i_lines = ( i_lines + 31 ) & -32;
Laurent Aimar's avatar
Laurent Aimar committed
54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

    frame->i_plane = 3;
    for( i = 0; i < 3; i++ )
    {
        int i_divh = 1;
        int i_divw = 1;
        if( i > 0 )
        {
            if( h->param.i_csp == X264_CSP_I420 )
                i_divh = i_divw = 2;
            else if( h->param.i_csp == X264_CSP_I422 )
                i_divw = 2;
        }
        frame->i_stride[i] = i_stride / i_divw;
        frame->i_lines[i] = i_lines / i_divh;
69
        CHECKED_MALLOC( frame->buffer[i],
70 71
                        frame->i_stride[i] * ( frame->i_lines[i] + 2*i_padv / i_divh ) );

Laurent Aimar's avatar
Laurent Aimar committed
72
        frame->plane[i] = ((uint8_t*)frame->buffer[i]) +
73
                          frame->i_stride[i] * i_padv / i_divh + PADH / i_divw;
Laurent Aimar's avatar
Laurent Aimar committed
74 75 76 77 78 79
    }
    frame->i_stride[3] = 0;
    frame->i_lines[3] = 0;
    frame->buffer[3] = NULL;
    frame->plane[3] = NULL;

80 81 82
    frame->filtered[0] = frame->plane[0];
    for( i = 0; i < 3; i++ )
    {
83
        CHECKED_MALLOC( frame->buffer[4+i],
84
                        frame->i_stride[0] * ( frame->i_lines[0] + 2*i_padv ) );
85
        frame->filtered[i+1] = ((uint8_t*)frame->buffer[4+i]) +
86
                                frame->i_stride[0] * i_padv + PADH;
87 88
    }

89
    if( h->frames.b_have_lowres )
90
    {
91
        frame->i_stride_lowres = frame->i_stride[0]/2 + PADH;
92 93 94
        frame->i_lines_lowres = frame->i_lines[0]/2;
        for( i = 0; i < 4; i++ )
        {
95 96 97 98
            CHECKED_MALLOC( frame->buffer_lowres[i],
                            frame->i_stride_lowres * ( frame->i_lines[0]/2 + 2*i_padv ) );
            frame->lowres[i] = ((uint8_t*)frame->buffer_lowres[i]) +
                                frame->i_stride_lowres * i_padv + PADH;
99
        }
100
    }
101

102 103
    if( h->param.analyse.i_me_method == X264_ME_ESA )
    {
104 105 106
        CHECKED_MALLOC( frame->buffer[7],
                        2 * frame->i_stride[0] * (frame->i_lines[0] + 2*i_padv) * sizeof(uint16_t) );
        frame->integral = (uint16_t*)frame->buffer[7] + frame->i_stride[0] * i_padv + PADH;
107 108
    }

Laurent Aimar's avatar
Laurent Aimar committed
109 110 111
    frame->i_poc = -1;
    frame->i_type = X264_TYPE_AUTO;
    frame->i_qpplus1 = 0;
112 113
    frame->i_pts = -1;
    frame->i_frame = -1;
114
    frame->i_frame_num = -1;
Loren Merritt's avatar
Loren Merritt committed
115
    frame->i_lines_completed = -1;
Laurent Aimar's avatar
Laurent Aimar committed
116

117 118 119
    CHECKED_MALLOC( frame->mb_type, i_mb_count * sizeof(int8_t));
    CHECKED_MALLOC( frame->mv[0], 2*16 * i_mb_count * sizeof(int16_t) );
    CHECKED_MALLOC( frame->ref[0], 4 * i_mb_count * sizeof(int8_t) );
120 121
    if( h->param.i_bframe )
    {
122 123
        CHECKED_MALLOC( frame->mv[1], 2*16 * i_mb_count * sizeof(int16_t) );
        CHECKED_MALLOC( frame->ref[1], 4 * i_mb_count * sizeof(int8_t) );
124 125 126 127 128 129 130
    }
    else
    {
        frame->mv[1]  = NULL;
        frame->ref[1] = NULL;
    }

131 132
    CHECKED_MALLOC( frame->i_row_bits, i_lines/16 * sizeof(int) );
    CHECKED_MALLOC( frame->i_row_qp, i_lines/16 * sizeof(int) );
133 134
    for( i = 0; i < h->param.i_bframe + 2; i++ )
        for( j = 0; j < h->param.i_bframe + 2; j++ )
135
            CHECKED_MALLOC( frame->i_row_satds[i][j], i_lines/16 * sizeof(int) );
136

137 138 139
    pthread_mutex_init( &frame->mutex, NULL );
    pthread_cond_init( &frame->cv, NULL );

Laurent Aimar's avatar
Laurent Aimar committed
140
    return frame;
141 142 143 144

fail:
    x264_frame_delete( frame );
    return NULL;
Laurent Aimar's avatar
Laurent Aimar committed
145 146 147 148
}

void x264_frame_delete( x264_frame_t *frame )
{
149
    int i, j;
150
    for( i = 0; i < 8; i++ )
151
        x264_free( frame->buffer[i] );
152 153
    for( i = 0; i < 4; i++ )
        x264_free( frame->buffer_lowres[i] );
154 155 156 157 158
    for( i = 0; i < X264_BFRAME_MAX+2; i++ )
        for( j = 0; j < X264_BFRAME_MAX+2; j++ )
            x264_free( frame->i_row_satds[i][j] );
    x264_free( frame->i_row_bits );
    x264_free( frame->i_row_qp );
159
    x264_free( frame->mb_type );
160 161 162 163
    x264_free( frame->mv[0] );
    x264_free( frame->mv[1] );
    x264_free( frame->ref[0] );
    x264_free( frame->ref[1] );
164 165
    pthread_mutex_destroy( &frame->mutex );
    pthread_cond_destroy( &frame->cv );
Laurent Aimar's avatar
Laurent Aimar committed
166 167 168 169 170
    x264_free( frame );
}

void x264_frame_copy_picture( x264_t *h, x264_frame_t *dst, x264_picture_t *src )
{
171
    int i_csp = src->img.i_csp & X264_CSP_MASK;
Laurent Aimar's avatar
Laurent Aimar committed
172 173 174 175
    dst->i_type     = src->i_type;
    dst->i_qpplus1  = src->i_qpplus1;
    dst->i_pts      = src->i_pts;

176 177 178 179
    if( i_csp <= X264_CSP_NONE  || i_csp >= X264_CSP_MAX )
        x264_log( h, X264_LOG_ERROR, "Arg invalid CSP\n" );
    else
        h->csp.convert[i_csp]( &h->mc, dst, &src->img, h->param.i_width, h->param.i_height );
Laurent Aimar's avatar
Laurent Aimar committed
180 181 182 183
}



Loren Merritt's avatar
Loren Merritt committed
184
static void plane_expand_border( uint8_t *pix, int i_stride, int i_width, int i_height, int i_padh, int i_padv, int b_pad_top, int b_pad_bottom )
185 186 187 188 189 190
{
#define PPIXEL(x, y) ( pix + (x) + (y)*i_stride )
    int y;
    for( y = 0; y < i_height; y++ )
    {
        /* left band */
191
        memset( PPIXEL(-i_padh, y), PPIXEL(0, y)[0], i_padh );
192
        /* right band */
193
        memset( PPIXEL(i_width, y), PPIXEL(i_width-1, y)[0], i_padh );
194 195
    }
    /* upper band */
Loren Merritt's avatar
Loren Merritt committed
196
    if( b_pad_top )
197 198
    for( y = 0; y < i_padv; y++ )
        memcpy( PPIXEL(-i_padh, -y-1), PPIXEL(-i_padh, 0), i_width+2*i_padh );
199
    /* lower band */
Loren Merritt's avatar
Loren Merritt committed
200
    if( b_pad_bottom )
201 202
    for( y = 0; y < i_padv; y++ )
        memcpy( PPIXEL(-i_padh, i_height+y), PPIXEL(-i_padh, i_height-1), i_width+2*i_padh );
203 204 205
#undef PPIXEL
}

Loren Merritt's avatar
Loren Merritt committed
206
void x264_frame_expand_border( x264_t *h, x264_frame_t *frame, int mb_y, int b_end )
Laurent Aimar's avatar
Laurent Aimar committed
207
{
208
    int i;
Loren Merritt's avatar
Loren Merritt committed
209 210 211
    int b_start = !mb_y;
    if( mb_y & h->sh.b_mbaff )
        return;
Laurent Aimar's avatar
Laurent Aimar committed
212 213
    for( i = 0; i < frame->i_plane; i++ )
    {
214 215
        int stride = frame->i_stride[i];
        int width = 16*h->sps->i_mb_width >> !!i;
Loren Merritt's avatar
Loren Merritt committed
216
        int height = (b_end ? 16*(h->sps->i_mb_height - mb_y) >> h->sh.b_mbaff : 16) >> !!i;
217 218
        int padh = PADH >> !!i;
        int padv = PADV >> !!i;
Loren Merritt's avatar
Loren Merritt committed
219 220 221 222 223
        // buffer: 2 chroma, 3 luma (rounded to 4) because deblocking goes beyond the top of the mb
        uint8_t *pix = frame->plane[i] + X264_MAX(0, (16*mb_y-4)*stride >> !!i);
        if( b_end && !b_start )
            height += 4 >> (!!i + h->sh.b_mbaff);
        if( h->sh.b_mbaff )
224
        {
Loren Merritt's avatar
Loren Merritt committed
225 226
            plane_expand_border( pix, stride*2, width, height, padh, padv, b_start, b_end );
            plane_expand_border( pix+stride, stride*2, width, height, padh, padv, b_start, b_end );
227 228 229
        }
        else
        {
Loren Merritt's avatar
Loren Merritt committed
230
            plane_expand_border( pix, stride, width, height, padh, padv, b_start, b_end );
231
        }
Laurent Aimar's avatar
Laurent Aimar committed
232 233 234
    }
}

Loren Merritt's avatar
Loren Merritt committed
235
void x264_frame_expand_border_filtered( x264_t *h, x264_frame_t *frame, int mb_y, int b_end )
236 237 238
{
    /* during filtering, 8 extra pixels were filtered on each edge. 
       we want to expand border from the last filtered pixel */
Loren Merritt's avatar
Loren Merritt committed
239
    int b_start = !mb_y;
240
    int stride = frame->i_stride[0];
Loren Merritt's avatar
Loren Merritt committed
241 242
    int width = 16*h->sps->i_mb_width + 16;
    int height = b_end ? (16*(h->sps->i_mb_height - mb_y) >> h->sh.b_mbaff) + 16 : 16;
243 244
    int padh = PADH - 8;
    int padv = PADV - 8;
245
    int i;
246
    for( i = 1; i < 4; i++ )
247
    {
Loren Merritt's avatar
Loren Merritt committed
248 249 250
        // buffer: 8 luma, to match the hpel filter
        uint8_t *pix = frame->filtered[i] + (16*mb_y - (8 << h->sh.b_mbaff)) * stride - 8;
        if( h->sh.b_mbaff )
251
        {
Loren Merritt's avatar
Loren Merritt committed
252 253
            plane_expand_border( pix, stride*2, width, height, padh, padv, b_start, b_end );
            plane_expand_border( pix+stride, stride*2, width, height, padh, padv, b_start, b_end );
254 255 256
        }
        else
        {
Loren Merritt's avatar
Loren Merritt committed
257
            plane_expand_border( pix, stride, width, height, padh, padv, b_start, b_end );
258 259
        }
    }
260 261
}

262
void x264_frame_expand_border_lowres( x264_frame_t *frame )
263
{
264
    int i;
265
    for( i = 0; i < 4; i++ )
Loren Merritt's avatar
Loren Merritt committed
266
        plane_expand_border( frame->lowres[i], frame->i_stride_lowres, frame->i_stride_lowres - 2*PADH, frame->i_lines_lowres, PADH, PADV, 1, 1 );
267 268
}

Loren Merritt's avatar
Loren Merritt committed
269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288
void x264_frame_expand_border_mod16( x264_t *h, x264_frame_t *frame )
{
    int i, y;
    for( i = 0; i < frame->i_plane; i++ )
    {
        int i_subsample = i ? 1 : 0;
        int i_width = h->param.i_width >> i_subsample;
        int i_height = h->param.i_height >> i_subsample;
        int i_padx = ( h->sps->i_mb_width * 16 - h->param.i_width ) >> i_subsample;
        int i_pady = ( h->sps->i_mb_height * 16 - h->param.i_height ) >> i_subsample;

        if( i_padx )
        {
            for( y = 0; y < i_height; y++ )
                memset( &frame->plane[i][y*frame->i_stride[i] + i_width],
                         frame->plane[i][y*frame->i_stride[i] + i_width - 1],
                         i_padx );
        }
        if( i_pady )
        {
289
            //FIXME interlace? or just let it pad using the wrong field
Loren Merritt's avatar
Loren Merritt committed
290
            for( y = i_height; y < i_height + i_pady; y++ )
Loren Merritt's avatar
Loren Merritt committed
291 292 293 294 295 296 297
                memcpy( &frame->plane[i][y*frame->i_stride[i]],
                        &frame->plane[i][(i_height-1)*frame->i_stride[i]],
                        i_width + i_padx );
        }
    }
}

298

299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340
/* cavlc + 8x8 transform stores nnz per 16 coeffs for the purpose of
 * entropy coding, but per 64 coeffs for the purpose of deblocking */
void munge_cavlc_nnz_row( x264_t *h, int mb_y, uint8_t (*buf)[16] )
{
    uint32_t (*src)[6] = (uint32_t(*)[6])h->mb.non_zero_count + mb_y * h->sps->i_mb_width;
    int8_t *transform = h->mb.mb_transform_size + mb_y * h->sps->i_mb_width;
    int x;
    for( x=0; x<h->sps->i_mb_width; x++ )
    {
        memcpy( buf+x, src+x, 16 );
        if( transform[x] )
        {
            if( src[x][0] ) src[x][0] = 0x01010101;
            if( src[x][1] ) src[x][1] = 0x01010101;
            if( src[x][2] ) src[x][2] = 0x01010101;
            if( src[x][3] ) src[x][3] = 0x01010101;
        }
    }
}

static void restore_cavlc_nnz_row( x264_t *h, int mb_y, uint8_t (*buf)[16] )
{
    uint8_t (*dst)[24] = h->mb.non_zero_count + mb_y * h->sps->i_mb_width;
    int x;
    for( x=0; x<h->sps->i_mb_width; x++ )
        memcpy( dst+x, buf+x, 16 );
}

static void munge_cavlc_nnz( x264_t *h, int mb_y, uint8_t (*buf)[16], void (*func)(x264_t*, int, uint8_t (*)[16]) )
{
    func( h, mb_y, buf );
    if( mb_y > 0 )
        func( h, mb_y-1, buf + h->sps->i_mb_width );
    if( h->sh.b_mbaff )
    {
        func( h, mb_y+1, buf + h->sps->i_mb_width * 2 );
        if( mb_y > 0 )
            func( h, mb_y-2, buf + h->sps->i_mb_width * 3 );
    }
}


341
/* Deblocking filter */
Laurent Aimar's avatar
Laurent Aimar committed
342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382

static const int i_alpha_table[52] =
{
     0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
     0,  0,  0,  0,  0,  0,  4,  4,  5,  6,
     7,  8,  9, 10, 12, 13, 15, 17, 20, 22,
    25, 28, 32, 36, 40, 45, 50, 56, 63, 71,
    80, 90,101,113,127,144,162,182,203,226,
    255, 255
};
static const int i_beta_table[52] =
{
     0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
     0,  0,  0,  0,  0,  0,  2,  2,  2,  3,
     3,  3,  3,  4,  4,  4,  6,  6,  7,  7,
     8,  8,  9,  9, 10, 10, 11, 11, 12, 12,
    13, 13, 14, 14, 15, 15, 16, 16, 17, 17,
    18, 18
};
static const int i_tc0_table[52][3] =
{
    { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 },
    { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 },
    { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 1 },
    { 0, 0, 1 }, { 0, 0, 1 }, { 0, 0, 1 }, { 0, 1, 1 }, { 0, 1, 1 }, { 1, 1, 1 },
    { 1, 1, 1 }, { 1, 1, 1 }, { 1, 1, 1 }, { 1, 1, 2 }, { 1, 1, 2 }, { 1, 1, 2 },
    { 1, 1, 2 }, { 1, 2, 3 }, { 1, 2, 3 }, { 2, 2, 3 }, { 2, 2, 4 }, { 2, 3, 4 },
    { 2, 3, 4 }, { 3, 3, 5 }, { 3, 4, 6 }, { 3, 4, 6 }, { 4, 5, 7 }, { 4, 5, 8 },
    { 4, 6, 9 }, { 5, 7,10 }, { 6, 8,11 }, { 6, 8,13 }, { 7,10,14 }, { 8,11,16 },
    { 9,12,18 }, {10,13,20 }, {11,15,23 }, {13,17,25 }
};

/* From ffmpeg */
static inline int clip_uint8( int a )
{
    if (a&(~255))
        return (-a)>>31;
    else
        return a;
}

Loren Merritt's avatar
Loren Merritt committed
383
static inline void deblock_luma_c( uint8_t *pix, int xstride, int ystride, int alpha, int beta, int8_t *tc0 )
Laurent Aimar's avatar
Laurent Aimar committed
384 385
{
    int i, d;
Loren Merritt's avatar
Loren Merritt committed
386 387 388
    for( i = 0; i < 4; i++ ) {
        if( tc0[i] < 0 ) {
            pix += 4*ystride;
Laurent Aimar's avatar
Laurent Aimar committed
389 390
            continue;
        }
Loren Merritt's avatar
Loren Merritt committed
391 392 393 394 395 396 397 398
        for( d = 0; d < 4; d++ ) {
            const int p2 = pix[-3*xstride];
            const int p1 = pix[-2*xstride];
            const int p0 = pix[-1*xstride];
            const int q0 = pix[ 0*xstride];
            const int q1 = pix[ 1*xstride];
            const int q2 = pix[ 2*xstride];
   
Loren Merritt's avatar
Loren Merritt committed
399 400 401
            if( abs( p0 - q0 ) < alpha &&
                abs( p1 - p0 ) < beta &&
                abs( q1 - q0 ) < beta ) {
Loren Merritt's avatar
Loren Merritt committed
402 403 404 405
   
                int tc = tc0[i];
                int delta;
   
Loren Merritt's avatar
Loren Merritt committed
406
                if( abs( p2 - p0 ) < beta ) {
Loren Merritt's avatar
Loren Merritt committed
407 408
                    pix[-2*xstride] = p1 + x264_clip3( (( p2 + ((p0 + q0 + 1) >> 1)) >> 1) - p1, -tc0[i], tc0[i] );
                    tc++; 
Laurent Aimar's avatar
Laurent Aimar committed
409
                }
Loren Merritt's avatar
Loren Merritt committed
410
                if( abs( q2 - q0 ) < beta ) {
Loren Merritt's avatar
Loren Merritt committed
411 412
                    pix[ 1*xstride] = q1 + x264_clip3( (( q2 + ((p0 + q0 + 1) >> 1)) >> 1) - q1, -tc0[i], tc0[i] );
                    tc++;
Laurent Aimar's avatar
Laurent Aimar committed
413
                }
Loren Merritt's avatar
Loren Merritt committed
414 415 416 417
    
                delta = x264_clip3( (((q0 - p0 ) << 2) + (p1 - q1) + 4) >> 3, -tc, tc );
                pix[-1*xstride] = clip_uint8( p0 + delta );    /* p0' */
                pix[ 0*xstride] = clip_uint8( q0 - delta );    /* q0' */
Laurent Aimar's avatar
Laurent Aimar committed
418
            }
Loren Merritt's avatar
Loren Merritt committed
419
            pix += ystride;
Laurent Aimar's avatar
Laurent Aimar committed
420 421 422
        }
    }
}
Loren Merritt's avatar
Loren Merritt committed
423 424 425 426 427 428 429 430
static void deblock_v_luma_c( uint8_t *pix, int stride, int alpha, int beta, int8_t *tc0 )
{
    deblock_luma_c( pix, stride, 1, alpha, beta, tc0 ); 
}
static void deblock_h_luma_c( uint8_t *pix, int stride, int alpha, int beta, int8_t *tc0 )
{
    deblock_luma_c( pix, 1, stride, alpha, beta, tc0 );
}
Laurent Aimar's avatar
Laurent Aimar committed
431

Loren Merritt's avatar
Loren Merritt committed
432
static inline void deblock_chroma_c( uint8_t *pix, int xstride, int ystride, int alpha, int beta, int8_t *tc0 )
Laurent Aimar's avatar
Laurent Aimar committed
433 434
{
    int i, d;
Loren Merritt's avatar
Loren Merritt committed
435 436 437 438
    for( i = 0; i < 4; i++ ) {
        const int tc = tc0[i];
        if( tc <= 0 ) {
            pix += 2*ystride;
Laurent Aimar's avatar
Laurent Aimar committed
439 440
            continue;
        }
Loren Merritt's avatar
Loren Merritt committed
441 442 443 444 445 446
        for( d = 0; d < 2; d++ ) {
            const int p1 = pix[-2*xstride];
            const int p0 = pix[-1*xstride];
            const int q0 = pix[ 0*xstride];
            const int q1 = pix[ 1*xstride];

Loren Merritt's avatar
Loren Merritt committed
447 448 449
            if( abs( p0 - q0 ) < alpha &&
                abs( p1 - p0 ) < beta &&
                abs( q1 - q0 ) < beta ) {
Loren Merritt's avatar
Loren Merritt committed
450 451 452 453

                int delta = x264_clip3( (((q0 - p0 ) << 2) + (p1 - q1) + 4) >> 3, -tc, tc );
                pix[-1*xstride] = clip_uint8( p0 + delta );    /* p0' */
                pix[ 0*xstride] = clip_uint8( q0 - delta );    /* q0' */
Laurent Aimar's avatar
Laurent Aimar committed
454
            }
Loren Merritt's avatar
Loren Merritt committed
455
            pix += ystride;
Laurent Aimar's avatar
Laurent Aimar committed
456 457 458
        }
    }
}
Loren Merritt's avatar
Loren Merritt committed
459 460 461 462 463 464 465 466
static void deblock_v_chroma_c( uint8_t *pix, int stride, int alpha, int beta, int8_t *tc0 )
{   
    deblock_chroma_c( pix, stride, 1, alpha, beta, tc0 );
}
static void deblock_h_chroma_c( uint8_t *pix, int stride, int alpha, int beta, int8_t *tc0 )
{   
    deblock_chroma_c( pix, 1, stride, alpha, beta, tc0 );
}
Laurent Aimar's avatar
Laurent Aimar committed
467

Loren Merritt's avatar
Loren Merritt committed
468
static inline void deblock_luma_intra_c( uint8_t *pix, int xstride, int ystride, int alpha, int beta )
Laurent Aimar's avatar
Laurent Aimar committed
469
{
Loren Merritt's avatar
Loren Merritt committed
470 471 472 473 474 475 476 477 478
    int d;
    for( d = 0; d < 16; d++ ) {
        const int p2 = pix[-3*xstride];
        const int p1 = pix[-2*xstride];
        const int p0 = pix[-1*xstride];
        const int q0 = pix[ 0*xstride];
        const int q1 = pix[ 1*xstride];
        const int q2 = pix[ 2*xstride];

Loren Merritt's avatar
Loren Merritt committed
479 480 481
        if( abs( p0 - q0 ) < alpha &&
            abs( p1 - p0 ) < beta &&
            abs( q1 - q0 ) < beta ) {
Loren Merritt's avatar
Loren Merritt committed
482

Loren Merritt's avatar
Loren Merritt committed
483 484
            if(abs( p0 - q0 ) < ((alpha >> 2) + 2) ){
                if( abs( p2 - p0 ) < beta)
Laurent Aimar's avatar
Laurent Aimar committed
485
                {
Loren Merritt's avatar
Loren Merritt committed
486 487 488 489 490 491 492 493
                    const int p3 = pix[-4*xstride];
                    /* p0', p1', p2' */
                    pix[-1*xstride] = ( p2 + 2*p1 + 2*p0 + 2*q0 + q1 + 4 ) >> 3;
                    pix[-2*xstride] = ( p2 + p1 + p0 + q0 + 2 ) >> 2;
                    pix[-3*xstride] = ( 2*p3 + 3*p2 + p1 + p0 + q0 + 4 ) >> 3;
                } else {
                    /* p0' */
                    pix[-1*xstride] = ( 2*p1 + p0 + q1 + 2 ) >> 2;
Laurent Aimar's avatar
Laurent Aimar committed
494
                }
Loren Merritt's avatar
Loren Merritt committed
495
                if( abs( q2 - q0 ) < beta)
Laurent Aimar's avatar
Laurent Aimar committed
496
                {
Loren Merritt's avatar
Loren Merritt committed
497 498 499 500 501 502 503 504
                    const int q3 = pix[3*xstride];
                    /* q0', q1', q2' */
                    pix[0*xstride] = ( p1 + 2*p0 + 2*q0 + 2*q1 + q2 + 4 ) >> 3;
                    pix[1*xstride] = ( p0 + q0 + q1 + q2 + 2 ) >> 2;
                    pix[2*xstride] = ( 2*q3 + 3*q2 + q1 + q0 + p0 + 4 ) >> 3;
                } else {
                    /* q0' */
                    pix[0*xstride] = ( 2*q1 + q0 + p1 + 2 ) >> 2;
Laurent Aimar's avatar
Laurent Aimar committed
505
                }
Loren Merritt's avatar
Loren Merritt committed
506 507 508 509
            }else{
                /* p0', q0' */
                pix[-1*xstride] = ( 2*p1 + p0 + q1 + 2 ) >> 2;
                pix[ 0*xstride] = ( 2*q1 + q0 + p1 + 2 ) >> 2;
Laurent Aimar's avatar
Laurent Aimar committed
510 511
            }
        }
Loren Merritt's avatar
Loren Merritt committed
512
        pix += ystride;
Laurent Aimar's avatar
Laurent Aimar committed
513 514
    }
}
Loren Merritt's avatar
Loren Merritt committed
515 516 517 518 519 520 521 522
static void deblock_v_luma_intra_c( uint8_t *pix, int stride, int alpha, int beta )
{   
    deblock_luma_intra_c( pix, stride, 1, alpha, beta );
}
static void deblock_h_luma_intra_c( uint8_t *pix, int stride, int alpha, int beta )
{   
    deblock_luma_intra_c( pix, 1, stride, alpha, beta );
}
Laurent Aimar's avatar
Laurent Aimar committed
523

Loren Merritt's avatar
Loren Merritt committed
524 525 526 527 528 529 530 531 532
static inline void deblock_chroma_intra_c( uint8_t *pix, int xstride, int ystride, int alpha, int beta )
{   
    int d; 
    for( d = 0; d < 8; d++ ) {
        const int p1 = pix[-2*xstride];
        const int p0 = pix[-1*xstride];
        const int q0 = pix[ 0*xstride];
        const int q1 = pix[ 1*xstride];

Loren Merritt's avatar
Loren Merritt committed
533 534 535
        if( abs( p0 - q0 ) < alpha &&
            abs( p1 - p0 ) < beta &&
            abs( q1 - q0 ) < beta ) {
Loren Merritt's avatar
Loren Merritt committed
536 537 538

            pix[-1*xstride] = (2*p1 + p0 + q1 + 2) >> 2;   /* p0' */
            pix[ 0*xstride] = (2*q1 + q0 + p1 + 2) >> 2;   /* q0' */
Laurent Aimar's avatar
Laurent Aimar committed
539 540
        }

Loren Merritt's avatar
Loren Merritt committed
541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567
        pix += ystride;
    }
}
static void deblock_v_chroma_intra_c( uint8_t *pix, int stride, int alpha, int beta )
{   
    deblock_chroma_intra_c( pix, stride, 1, alpha, beta );
}
static void deblock_h_chroma_intra_c( uint8_t *pix, int stride, int alpha, int beta )
{   
    deblock_chroma_intra_c( pix, 1, stride, alpha, beta );
}

static inline void deblock_edge( x264_t *h, uint8_t *pix, int i_stride, int bS[4], int i_qp, int b_chroma,
                                 x264_deblock_inter_t pf_inter, x264_deblock_intra_t pf_intra )
{
    int i;
    const int index_a = x264_clip3( i_qp + h->sh.i_alpha_c0_offset, 0, 51 );
    const int alpha = i_alpha_table[index_a];
    const int beta  = i_beta_table[x264_clip3( i_qp + h->sh.i_beta_offset, 0, 51 )];

    if( bS[0] < 4 ) {
        int8_t tc[4]; 
        for(i=0; i<4; i++)
            tc[i] = (bS[i] ? i_tc0_table[index_a][bS[i] - 1] : -1) + b_chroma;
        pf_inter( pix, i_stride, alpha, beta, tc );
    } else {
        pf_intra( pix, i_stride, alpha, beta );
Laurent Aimar's avatar
Laurent Aimar committed
568 569 570
    }
}

Loren Merritt's avatar
Loren Merritt committed
571
void x264_frame_deblock_row( x264_t *h, int mb_y )
Laurent Aimar's avatar
Laurent Aimar committed
572 573 574
{
    const int s8x8 = 2 * h->mb.i_mb_stride;
    const int s4x4 = 4 * h->mb.i_mb_stride;
Loren Merritt's avatar
Loren Merritt committed
575
    const int b_interlaced = h->sh.b_mbaff;
576
    const int mvy_limit = 4 >> b_interlaced;
Loren Merritt's avatar
Loren Merritt committed
577
    int mb_x;
Laurent Aimar's avatar
Laurent Aimar committed
578

579 580 581 582
    int i_stride2[3] = { h->fdec->i_stride[0] << b_interlaced,
                         h->fdec->i_stride[1] << b_interlaced,
                         h->fdec->i_stride[2] << b_interlaced };

583 584 585
    if( !h->pps->b_cabac && h->pps->b_transform_8x8_mode )
        munge_cavlc_nnz( h, mb_y, h->mb.nnz_backup, munge_cavlc_nnz_row );

Loren Merritt's avatar
Loren Merritt committed
586
    for( mb_x = 0; mb_x < h->sps->i_mb_width; )
Laurent Aimar's avatar
Laurent Aimar committed
587 588 589 590
    {
        const int mb_xy  = mb_y * h->mb.i_mb_stride + mb_x;
        const int mb_8x8 = 2 * s8x8 * mb_y + 2 * mb_x;
        const int mb_4x4 = 4 * s4x4 * mb_y + 4 * mb_x;
591
        const int b_8x8_transform = h->mb.mb_transform_size[mb_xy];
Loren Merritt's avatar
Loren Merritt committed
592 593
        const int i_edge_end = (h->mb.type[mb_xy] == P_SKIP) ? 1 : 4;
        int i_edge, i_dir;
594

595 596 597 598 599 600 601 602 603 604
        int i_pix_y[3] = { 16*mb_y*h->fdec->i_stride[0] + 16*mb_x,
                            8*mb_y*h->fdec->i_stride[1] +  8*mb_x,
                            8*mb_y*h->fdec->i_stride[2] +  8*mb_x };
        if( b_interlaced && (mb_y&1) )
        {
            i_pix_y[0] -= 15*h->fdec->i_stride[0];
            i_pix_y[1] -=  7*h->fdec->i_stride[1];
            i_pix_y[2] -=  7*h->fdec->i_stride[2];
        }

605 606
        x264_prefetch_fenc( h, h->fdec, mb_x, mb_y );

Laurent Aimar's avatar
Laurent Aimar committed
607 608 609 610
        /* i_dir == 0 -> vertical edge
         * i_dir == 1 -> horizontal edge */
        for( i_dir = 0; i_dir < 2; i_dir++ )
        {
611
            int i_start = (i_dir ? (mb_y <= b_interlaced) : (mb_x == 0));
Laurent Aimar's avatar
Laurent Aimar committed
612 613
            int i_qp, i_qpn;

Loren Merritt's avatar
Loren Merritt committed
614
            for( i_edge = i_start; i_edge < i_edge_end; i_edge++ )
Laurent Aimar's avatar
Laurent Aimar committed
615
            {
Loren Merritt's avatar
Loren Merritt committed
616
                int mbn_xy, mbn_8x8, mbn_4x4;
Laurent Aimar's avatar
Laurent Aimar committed
617 618
                int bS[4];  /* filtering strength */

Loren Merritt's avatar
Loren Merritt committed
619 620 621 622 623 624 625
                if( b_8x8_transform && (i_edge&1) )
                    continue;

                mbn_xy  = i_edge > 0 ? mb_xy  : ( i_dir == 0 ? mb_xy  - 1 : mb_xy - h->mb.i_mb_stride );
                mbn_8x8 = i_edge > 0 ? mb_8x8 : ( i_dir == 0 ? mb_8x8 - 2 : mb_8x8 - 2 * s8x8 );
                mbn_4x4 = i_edge > 0 ? mb_4x4 : ( i_dir == 0 ? mb_4x4 - 4 : mb_4x4 - 4 * s4x4 );

626 627 628 629 630 631 632
                if( b_interlaced && i_edge == 0 && i_dir == 1 )
                {
                    mbn_xy -= h->mb.i_mb_stride;
                    mbn_8x8 -= 2 * s8x8;
                    mbn_4x4 -= 4 * s4x4;
                }

Laurent Aimar's avatar
Laurent Aimar committed
633 634 635
                /* *** Get bS for each 4px for the current edge *** */
                if( IS_INTRA( h->mb.type[mb_xy] ) || IS_INTRA( h->mb.type[mbn_xy] ) )
                {
636
                    bS[0] = bS[1] = bS[2] = bS[3] = ( i_edge == 0 && !(b_interlaced && i_dir) ? 4 : 3 );
Laurent Aimar's avatar
Laurent Aimar committed
637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652
                }
                else
                {
                    int i;
                    for( i = 0; i < 4; i++ )
                    {
                        int x  = i_dir == 0 ? i_edge : i;
                        int y  = i_dir == 0 ? i      : i_edge;
                        int xn = (x - (i_dir == 0 ? 1 : 0 ))&0x03;
                        int yn = (y - (i_dir == 0 ? 0 : 1 ))&0x03;

                        if( h->mb.non_zero_count[mb_xy][block_idx_xy[x][y]] != 0 ||
                            h->mb.non_zero_count[mbn_xy][block_idx_xy[xn][yn]] != 0 )
                        {
                            bS[i] = 2;
                        }
653
                        else
Laurent Aimar's avatar
Laurent Aimar committed
654
                        {
655 656 657 658 659 660 661 662 663 664 665 666 667
                            /* FIXME: A given frame may occupy more than one position in
                             * the reference list. So we should compare the frame numbers,
                             * not the indices in the ref list.
                             * No harm yet, as we don't generate that case.*/

                            int i8p= mb_8x8+(x/2)+(y/2)*s8x8;
                            int i8q= mbn_8x8+(xn/2)+(yn/2)*s8x8;
                            int i4p= mb_4x4+x+y*s4x4;
                            int i4q= mbn_4x4+xn+yn*s4x4;
                            int l;

                            bS[i] = 0;

Loren Merritt's avatar
Loren Merritt committed
668
                            for( l = 0; l < 1 + (h->sh.i_type == SLICE_TYPE_B); l++ )
Laurent Aimar's avatar
Laurent Aimar committed
669
                            {
670 671
                                if( h->mb.ref[l][i8p] != h->mb.ref[l][i8q] ||
                                    abs( h->mb.mv[l][i4p][0] - h->mb.mv[l][i4q][0] ) >= 4 ||
672
                                    abs( h->mb.mv[l][i4p][1] - h->mb.mv[l][i4q][1] ) >= mvy_limit )
673 674 675 676
                                {
                                    bS[i] = 1;
                                    break;
                                }
Laurent Aimar's avatar
Laurent Aimar committed
677 678 679 680 681 682 683 684 685 686 687 688 689
                            }
                        }
                    }
                }

                /* *** filter *** */
                /* Y plane */
                i_qp = h->mb.qp[mb_xy];
                i_qpn= h->mb.qp[mbn_xy];

                if( i_dir == 0 )
                {
                    /* vertical edge */
690 691
                    deblock_edge( h, &h->fdec->plane[0][i_pix_y[0] + 4*i_edge],
                                  i_stride2[0], bS, (i_qp+i_qpn+1) >> 1, 0,
Loren Merritt's avatar
Loren Merritt committed
692
                                  h->loopf.deblock_h_luma, h->loopf.deblock_h_luma_intra );
693
                    if( !(i_edge & 1) )
Laurent Aimar's avatar
Laurent Aimar committed
694 695 696 697
                    {
                        /* U/V planes */
                        int i_qpc = ( i_chroma_qp_table[x264_clip3( i_qp + h->pps->i_chroma_qp_index_offset, 0, 51 )] +
                                      i_chroma_qp_table[x264_clip3( i_qpn + h->pps->i_chroma_qp_index_offset, 0, 51 )] + 1 ) >> 1;
698 699
                        deblock_edge( h, &h->fdec->plane[1][i_pix_y[1] + 2*i_edge],
                                      i_stride2[1], bS, i_qpc, 1,
Loren Merritt's avatar
Loren Merritt committed
700
                                      h->loopf.deblock_h_chroma, h->loopf.deblock_h_chroma_intra );
701 702
                        deblock_edge( h, &h->fdec->plane[2][i_pix_y[2] + 2*i_edge],
                                      i_stride2[2], bS, i_qpc, 1,
Loren Merritt's avatar
Loren Merritt committed
703
                                      h->loopf.deblock_h_chroma, h->loopf.deblock_h_chroma_intra );
Laurent Aimar's avatar
Laurent Aimar committed
704 705 706 707 708
                    }
                }
                else
                {
                    /* horizontal edge */
709 710
                    deblock_edge( h, &h->fdec->plane[0][i_pix_y[0] + 4*i_edge*i_stride2[0]],
                                  i_stride2[0], bS, (i_qp+i_qpn+1) >> 1, 0,
Loren Merritt's avatar
Loren Merritt committed
711
                                  h->loopf.deblock_v_luma, h->loopf.deblock_v_luma_intra );
Laurent Aimar's avatar
Laurent Aimar committed
712
                    /* U/V planes */
713
                    if( !(i_edge & 1) )
Laurent Aimar's avatar
Laurent Aimar committed
714 715 716
                    {
                        int i_qpc = ( i_chroma_qp_table[x264_clip3( i_qp + h->pps->i_chroma_qp_index_offset, 0, 51 )] +
                                      i_chroma_qp_table[x264_clip3( i_qpn + h->pps->i_chroma_qp_index_offset, 0, 51 )] + 1 ) >> 1;
717 718
                        deblock_edge( h, &h->fdec->plane[1][i_pix_y[1] + 2*i_edge*i_stride2[1]],
                                      i_stride2[1], bS, i_qpc, 1,
Loren Merritt's avatar
Loren Merritt committed
719
                                      h->loopf.deblock_v_chroma, h->loopf.deblock_v_chroma_intra );
720 721
                        deblock_edge( h, &h->fdec->plane[2][i_pix_y[2] + 2*i_edge*i_stride2[2]],
                                      i_stride2[2], bS, i_qpc, 1,
Loren Merritt's avatar
Loren Merritt committed
722
                                      h->loopf.deblock_v_chroma, h->loopf.deblock_v_chroma_intra );
Laurent Aimar's avatar
Laurent Aimar committed
723 724 725 726 727
                    }
                }
            }
        }

728 729 730
        /* next mb */
        if( !b_interlaced || (mb_y&1) )
            mb_x++;
Loren Merritt's avatar
Loren Merritt committed
731
        mb_y ^= b_interlaced;
Laurent Aimar's avatar
Laurent Aimar committed
732
    }
733 734 735

    if( !h->pps->b_cabac && h->pps->b_transform_8x8_mode )
        munge_cavlc_nnz( h, mb_y, h->mb.nnz_backup, restore_cavlc_nnz_row );
Laurent Aimar's avatar
Laurent Aimar committed
736 737
}

Loren Merritt's avatar
Loren Merritt committed
738 739 740 741 742 743 744
void x264_frame_deblock( x264_t *h )
{
    int mb_y;
    for( mb_y = 0; mb_y < h->sps->i_mb_height; mb_y += 1 + h->sh.b_mbaff )
        x264_frame_deblock_row( h, mb_y );
}

745
#ifdef HAVE_MMX
Loren Merritt's avatar
Loren Merritt committed
746 747 748 749 750 751 752 753
void x264_deblock_v_chroma_mmxext( uint8_t *pix, int stride, int alpha, int beta, int8_t *tc0 );
void x264_deblock_h_chroma_mmxext( uint8_t *pix, int stride, int alpha, int beta, int8_t *tc0 );
void x264_deblock_v_chroma_intra_mmxext( uint8_t *pix, int stride, int alpha, int beta );
void x264_deblock_h_chroma_intra_mmxext( uint8_t *pix, int stride, int alpha, int beta );

#ifdef ARCH_X86_64
void x264_deblock_v_luma_sse2( uint8_t *pix, int stride, int alpha, int beta, int8_t *tc0 );
void x264_deblock_h_luma_sse2( uint8_t *pix, int stride, int alpha, int beta, int8_t *tc0 );
Loren Merritt's avatar
Loren Merritt committed
754
#else
Loren Merritt's avatar
Loren Merritt committed
755 756 757 758 759 760 761 762 763
void x264_deblock_h_luma_mmxext( uint8_t *pix, int stride, int alpha, int beta, int8_t *tc0 );
void x264_deblock_v8_luma_mmxext( uint8_t *pix, int stride, int alpha, int beta, int8_t *tc0 );

void x264_deblock_v_luma_mmxext( uint8_t *pix, int stride, int alpha, int beta, int8_t *tc0 )
{
    x264_deblock_v8_luma_mmxext( pix,   stride, alpha, beta, tc0   );
    x264_deblock_v8_luma_mmxext( pix+8, stride, alpha, beta, tc0+2 );
}
#endif
Loren Merritt's avatar
Loren Merritt committed
764
#endif
Laurent Aimar's avatar
Laurent Aimar committed
765

Loren Merritt's avatar
Loren Merritt committed
766 767 768 769 770 771 772 773 774 775 776
void x264_deblock_init( int cpu, x264_deblock_function_t *pf )
{
    pf->deblock_v_luma = deblock_v_luma_c;
    pf->deblock_h_luma = deblock_h_luma_c;
    pf->deblock_v_chroma = deblock_v_chroma_c;
    pf->deblock_h_chroma = deblock_h_chroma_c;
    pf->deblock_v_luma_intra = deblock_v_luma_intra_c;
    pf->deblock_h_luma_intra = deblock_h_luma_intra_c;
    pf->deblock_v_chroma_intra = deblock_v_chroma_intra_c;
    pf->deblock_h_chroma_intra = deblock_h_chroma_intra_c;

777
#ifdef HAVE_MMX
Loren Merritt's avatar
Loren Merritt committed
778 779 780 781 782 783
    if( cpu&X264_CPU_MMXEXT )
    {
        pf->deblock_v_chroma = x264_deblock_v_chroma_mmxext;
        pf->deblock_h_chroma = x264_deblock_h_chroma_mmxext;
        pf->deblock_v_chroma_intra = x264_deblock_v_chroma_intra_mmxext;
        pf->deblock_h_chroma_intra = x264_deblock_h_chroma_intra_mmxext;
Laurent Aimar's avatar
Laurent Aimar committed
784

Loren Merritt's avatar
Loren Merritt committed
785 786 787 788 789 790 791 792 793 794 795
#ifdef ARCH_X86_64
        if( cpu&X264_CPU_SSE2 )
        {
            pf->deblock_v_luma = x264_deblock_v_luma_sse2;
            pf->deblock_h_luma = x264_deblock_h_luma_sse2;
        }
#else
        pf->deblock_v_luma = x264_deblock_v_luma_mmxext;
        pf->deblock_h_luma = x264_deblock_h_luma_mmxext;
#endif
    }
796
#endif
Loren Merritt's avatar
Loren Merritt committed
797
}
Laurent Aimar's avatar
Laurent Aimar committed
798

799 800 801 802

/* threading */

#ifdef HAVE_PTHREAD
803
void x264_frame_cond_broadcast( x264_frame_t *frame, int i_lines_completed )
804 805
{
    pthread_mutex_lock( &frame->mutex );
806
    frame->i_lines_completed = i_lines_completed;
807 808 809 810 811 812
    pthread_cond_broadcast( &frame->cv );
    pthread_mutex_unlock( &frame->mutex );
}

void x264_frame_cond_wait( x264_frame_t *frame, int i_lines_completed )
{
813 814 815 816
    pthread_mutex_lock( &frame->mutex );
    while( frame->i_lines_completed < i_lines_completed )
        pthread_cond_wait( &frame->cv, &frame->mutex );
    pthread_mutex_unlock( &frame->mutex );
817 818 819
}

#else
820
void x264_frame_cond_broadcast( x264_frame_t *frame, int i_lines_completed )
821 822 823 824 825
{}
void x264_frame_cond_wait( x264_frame_t *frame, int i_lines_completed )
{}
#endif

826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905

/* list operators */

void x264_frame_push( x264_frame_t **list, x264_frame_t *frame )
{
    int i = 0;
    while( list[i] ) i++;
    list[i] = frame;
}

x264_frame_t *x264_frame_pop( x264_frame_t **list )
{
    x264_frame_t *frame;
    int i = 0;
    assert( list[0] );
    while( list[i+1] ) i++;
    frame = list[i];
    list[i] = NULL;
    return frame;
}

void x264_frame_unshift( x264_frame_t **list, x264_frame_t *frame )
{
    int i = 0;
    while( list[i] ) i++;
    while( i-- )
        list[i+1] = list[i];
    list[0] = frame;
}

x264_frame_t *x264_frame_shift( x264_frame_t **list )
{
    x264_frame_t *frame = list[0];
    int i;
    for( i = 0; list[i]; i++ )
        list[i] = list[i+1];
    assert(frame);
    return frame;
}

void x264_frame_push_unused( x264_t *h, x264_frame_t *frame )
{
    assert( frame->i_reference_count > 0 );
    frame->i_reference_count--;
    if( frame->i_reference_count == 0 )
        x264_frame_push( h->frames.unused, frame );
    assert( h->frames.unused[ sizeof(h->frames.unused) / sizeof(*h->frames.unused) - 1 ] == NULL );
}

x264_frame_t *x264_frame_pop_unused( x264_t *h )
{
    x264_frame_t *frame;
    if( h->frames.unused[0] )
        frame = x264_frame_pop( h->frames.unused );
    else
        frame = x264_frame_new( h );
    assert( frame->i_reference_count == 0 );
    frame->i_reference_count = 1;
    return frame;
}

void x264_frame_sort( x264_frame_t **list, int b_dts )
{
    int i, b_ok;
    do {
        b_ok = 1;
        for( i = 0; list[i+1]; i++ )
        {
            int dtype = list[i]->i_type - list[i+1]->i_type;
            int dtime = list[i]->i_frame - list[i+1]->i_frame;
            int swap = b_dts ? dtype > 0 || ( dtype == 0 && dtime > 0 )
                             : dtime > 0;
            if( swap )
            {
                XCHG( x264_frame_t*, list[i], list[i+1] );
                b_ok = 0;
            }
        }
    } while( !b_ok );
}