cabac.c 7.86 KB
Newer Older
Michael Niedermayer's avatar
Michael Niedermayer committed
1 2 3 4
/*
 * H.26L/H.264/AVC/JVT/14496-10/... encoder/decoder
 * Copyright (c) 2003 Michael Niedermayer <michaelni@gmx.at>
 *
5 6 7
 * This file is part of FFmpeg.
 *
 * FFmpeg is free software; you can redistribute it and/or
Michael Niedermayer's avatar
Michael Niedermayer committed
8 9
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
10
 * version 2.1 of the License, or (at your option) any later version.
Michael Niedermayer's avatar
Michael Niedermayer committed
11
 *
12
 * FFmpeg is distributed in the hope that it will be useful,
Michael Niedermayer's avatar
Michael Niedermayer committed
13 14 15 16 17
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
18
 * License along with FFmpeg; if not, write to the Free Software
19
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
Michael Niedermayer's avatar
Michael Niedermayer committed
20 21 22 23 24 25 26 27 28
 */

/**
 * @file cabac.c
 * Context Adaptive Binary Arithmetic Coder.
 */

#include <string.h>

29
#include "libavutil/common.h"
30
#include "bitstream.h"
Michael Niedermayer's avatar
Michael Niedermayer committed
31 32
#include "cabac.h"

33
static const uint8_t lps_range[64][4]= {
Michael Niedermayer's avatar
Michael Niedermayer committed
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
{128,176,208,240}, {128,167,197,227}, {128,158,187,216}, {123,150,178,205},
{116,142,169,195}, {111,135,160,185}, {105,128,152,175}, {100,122,144,166},
{ 95,116,137,158}, { 90,110,130,150}, { 85,104,123,142}, { 81, 99,117,135},
{ 77, 94,111,128}, { 73, 89,105,122}, { 69, 85,100,116}, { 66, 80, 95,110},
{ 62, 76, 90,104}, { 59, 72, 86, 99}, { 56, 69, 81, 94}, { 53, 65, 77, 89},
{ 51, 62, 73, 85}, { 48, 59, 69, 80}, { 46, 56, 66, 76}, { 43, 53, 63, 72},
{ 41, 50, 59, 69}, { 39, 48, 56, 65}, { 37, 45, 54, 62}, { 35, 43, 51, 59},
{ 33, 41, 48, 56}, { 32, 39, 46, 53}, { 30, 37, 43, 50}, { 29, 35, 41, 48},
{ 27, 33, 39, 45}, { 26, 31, 37, 43}, { 24, 30, 35, 41}, { 23, 28, 33, 39},
{ 22, 27, 32, 37}, { 21, 26, 30, 35}, { 20, 24, 29, 33}, { 19, 23, 27, 31},
{ 18, 22, 26, 30}, { 17, 21, 25, 28}, { 16, 20, 23, 27}, { 15, 19, 22, 25},
{ 14, 18, 21, 24}, { 14, 17, 20, 23}, { 13, 16, 19, 22}, { 12, 15, 18, 21},
{ 12, 14, 17, 20}, { 11, 14, 16, 19}, { 11, 13, 15, 18}, { 10, 12, 15, 17},
{ 10, 12, 14, 16}, {  9, 11, 13, 15}, {  9, 11, 12, 14}, {  8, 10, 12, 14},
{  8,  9, 11, 13}, {  7,  9, 11, 12}, {  7,  9, 10, 12}, {  7,  8, 10, 11},
{  6,  8,  9, 11}, {  6,  7,  9, 10}, {  6,  7,  8,  9}, {  2,  2,  2,  2},
};

52
uint8_t ff_h264_mlps_state[4*64];
53
uint8_t ff_h264_lps_range[4*2*64];
54 55
uint8_t ff_h264_lps_state[2*64];
uint8_t ff_h264_mps_state[2*64];
56

57
static const uint8_t mps_state[64]= {
Michael Niedermayer's avatar
Michael Niedermayer committed
58 59 60 61 62 63 64 65 66 67
  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,26,27,28,29,30,31,32,
 33,34,35,36,37,38,39,40,
 41,42,43,44,45,46,47,48,
 49,50,51,52,53,54,55,56,
 57,58,59,60,61,62,62,63,
};

68
static const uint8_t lps_state[64]= {
Michael Niedermayer's avatar
Michael Niedermayer committed
69 70 71 72 73 74 75 76 77
  0, 0, 1, 2, 2, 4, 4, 5,
  6, 7, 8, 9, 9,11,11,12,
 13,13,15,15,16,16,18,18,
 19,19,21,21,22,22,23,24,
 24,25,26,26,27,27,28,29,
 29,30,30,30,31,32,32,33,
 33,33,34,34,35,35,35,36,
 36,36,37,37,37,38,38,63,
};
78 79
#if 0
const uint8_t ff_h264_norm_shift_old[128]= {
80
 7,6,5,5,4,4,4,4,3,3,3,3,3,3,3,3,
81
 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
Michael Niedermayer's avatar
Michael Niedermayer committed
82 83
 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
84 85 86 87
 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,0,0,0,0,0,0,0,0,0,0,0,
Michael Niedermayer's avatar
Michael Niedermayer committed
88
};
89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
#endif
const uint8_t ff_h264_norm_shift[512]= {
 9,8,7,7,6,6,6,6,5,5,5,5,5,5,5,5,
 4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
 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,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,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,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,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,
};
Michael Niedermayer's avatar
Michael Niedermayer committed
112

Michael Niedermayer's avatar
Michael Niedermayer committed
113 114 115 116 117
/**
 *
 * @param buf_size size of buf in bits
 */
void ff_init_cabac_encoder(CABACContext *c, uint8_t *buf, int buf_size){
118
    init_put_bits(&c->pb, buf, buf_size);
Michael Niedermayer's avatar
Michael Niedermayer committed
119 120 121 122 123 124 125

    c->low= 0;
    c->range= 0x1FE;
    c->outstanding_count= 0;
#ifdef STRICT_LIMITS
    c->sym_count =0;
#endif
126

Michael Niedermayer's avatar
Michael Niedermayer committed
127 128 129 130 131 132 133
    c->pb.bit_left++; //avoids firstBitFlag
}

/**
 *
 * @param buf_size size of buf in bits
 */
134
void ff_init_cabac_decoder(CABACContext *c, const uint8_t *buf, int buf_size){
135
    c->bytestream_start=
Michael Niedermayer's avatar
Michael Niedermayer committed
136
    c->bytestream= buf;
Michael Niedermayer's avatar
Michael Niedermayer committed
137
    c->bytestream_end= buf + buf_size;
Michael Niedermayer's avatar
Michael Niedermayer committed
138

Michael Niedermayer's avatar
Michael Niedermayer committed
139 140 141 142 143 144 145
#if CABAC_BITS == 16
    c->low =  (*c->bytestream++)<<18;
    c->low+=  (*c->bytestream++)<<10;
#else
    c->low =  (*c->bytestream++)<<10;
#endif
    c->low+= ((*c->bytestream++)<<2) + 2;
146
    c->range= 0x1FE;
Michael Niedermayer's avatar
Michael Niedermayer committed
147 148
}

149
void ff_init_cabac_states(CABACContext *c){
Michael Niedermayer's avatar
Michael Niedermayer committed
150
    int i, j;
151

152
    for(i=0; i<64; i++){
Michael Niedermayer's avatar
Michael Niedermayer committed
153
        for(j=0; j<4; j++){ //FIXME check if this is worth the 1 shift we save
154 155
            ff_h264_lps_range[j*2*64+2*i+0]=
            ff_h264_lps_range[j*2*64+2*i+1]= lps_range[i][j];
Michael Niedermayer's avatar
Michael Niedermayer committed
156 157
        }

158
        ff_h264_mlps_state[128+2*i+0]=
159
        ff_h264_mps_state[2*i+0]= 2*mps_state[i]+0;
160
        ff_h264_mlps_state[128+2*i+1]=
161
        ff_h264_mps_state[2*i+1]= 2*mps_state[i]+1;
Michael Niedermayer's avatar
Michael Niedermayer committed
162

163
        if( i ){
164
#ifdef BRANCHLESS_CABAC_DECODER
165 166
            ff_h264_mlps_state[128-2*i-1]= 2*lps_state[i]+0;
            ff_h264_mlps_state[128-2*i-2]= 2*lps_state[i]+1;
167
        }else{
168 169
            ff_h264_mlps_state[128-2*i-1]= 1;
            ff_h264_mlps_state[128-2*i-2]= 0;
170
#else
171 172
            ff_h264_lps_state[2*i+0]= 2*lps_state[i]+0;
            ff_h264_lps_state[2*i+1]= 2*lps_state[i]+1;
Michael Niedermayer's avatar
Michael Niedermayer committed
173
        }else{
174 175
            ff_h264_lps_state[2*i+0]= 1;
            ff_h264_lps_state[2*i+1]= 0;
176
#endif
Michael Niedermayer's avatar
Michael Niedermayer committed
177 178 179 180
        }
    }
}

181
#ifdef TEST
182
#undef random
Michael Niedermayer's avatar
Michael Niedermayer committed
183
#define SIZE 10240
Michael Niedermayer's avatar
Michael Niedermayer committed
184 185

#include "avcodec.h"
186
#include "cabac.h"
Michael Niedermayer's avatar
Michael Niedermayer committed
187

Diego Biurrun's avatar
Diego Biurrun committed
188
int main(void){
Michael Niedermayer's avatar
Michael Niedermayer committed
189 190
    CABACContext c;
    uint8_t b[9*SIZE];
191
    uint8_t r[9*SIZE];
Michael Niedermayer's avatar
Michael Niedermayer committed
192
    int i;
193
    uint8_t state[10]= {0};
194

Michael Niedermayer's avatar
Michael Niedermayer committed
195
    ff_init_cabac_encoder(&c, b, SIZE);
196
    ff_init_cabac_states(&c);
197

Michael Niedermayer's avatar
Michael Niedermayer committed
198
    for(i=0; i<SIZE; i++){
199
        r[i]= random()%7;
Michael Niedermayer's avatar
Michael Niedermayer committed
200
    }
201

Michael Niedermayer's avatar
Michael Niedermayer committed
202 203
    for(i=0; i<SIZE; i++){
START_TIMER
204
        put_cabac_bypass(&c, r[i]&1);
Michael Niedermayer's avatar
Michael Niedermayer committed
205 206
STOP_TIMER("put_cabac_bypass")
    }
207

Michael Niedermayer's avatar
Michael Niedermayer committed
208 209
    for(i=0; i<SIZE; i++){
START_TIMER
210
        put_cabac(&c, state, r[i]&1);
Michael Niedermayer's avatar
Michael Niedermayer committed
211 212 213
STOP_TIMER("put_cabac")
    }

214 215 216 217
    for(i=0; i<SIZE; i++){
START_TIMER
        put_cabac_u(&c, state, r[i], 6, 3, i&1);
STOP_TIMER("put_cabac_u")
218
    }
219 220 221

    for(i=0; i<SIZE; i++){
START_TIMER
Michael Niedermayer's avatar
Michael Niedermayer committed
222
        put_cabac_ueg(&c, state, r[i], 3, 0, 1, 2);
223
STOP_TIMER("put_cabac_ueg")
224 225
    }

Michael Niedermayer's avatar
Michael Niedermayer committed
226
    put_cabac_terminate(&c, 1);
227

Michael Niedermayer's avatar
Michael Niedermayer committed
228
    ff_init_cabac_decoder(&c, b, SIZE);
229

230
    memset(state, 0, sizeof(state));
231

Michael Niedermayer's avatar
Michael Niedermayer committed
232 233
    for(i=0; i<SIZE; i++){
START_TIMER
234
        if( (r[i]&1) != get_cabac_bypass(&c) )
Michael Niedermayer's avatar
Michael Niedermayer committed
235
            av_log(NULL, AV_LOG_ERROR, "CABAC bypass failure at %d\n", i);
Michael Niedermayer's avatar
Michael Niedermayer committed
236 237
STOP_TIMER("get_cabac_bypass")
    }
238

Michael Niedermayer's avatar
Michael Niedermayer committed
239 240
    for(i=0; i<SIZE; i++){
START_TIMER
241
        if( (r[i]&1) != get_cabac(&c, state) )
Michael Niedermayer's avatar
Michael Niedermayer committed
242
            av_log(NULL, AV_LOG_ERROR, "CABAC failure at %d\n", i);
Michael Niedermayer's avatar
Michael Niedermayer committed
243 244
STOP_TIMER("get_cabac")
    }
Michael Niedermayer's avatar
Michael Niedermayer committed
245
#if 0
246 247 248
    for(i=0; i<SIZE; i++){
START_TIMER
        if( r[i] != get_cabac_u(&c, state, (i&1) ? 6 : 7, 3, i&1) )
Michael Niedermayer's avatar
Michael Niedermayer committed
249
            av_log(NULL, AV_LOG_ERROR, "CABAC unary (truncated) binarization failure at %d\n", i);
250 251 252 253 254 255
STOP_TIMER("get_cabac_u")
    }

    for(i=0; i<SIZE; i++){
START_TIMER
        if( r[i] != get_cabac_ueg(&c, state, 3, 0, 1, 2))
Michael Niedermayer's avatar
Michael Niedermayer committed
256
            av_log(NULL, AV_LOG_ERROR, "CABAC unary (truncated) binarization failure at %d\n", i);
257 258
STOP_TIMER("get_cabac_ueg")
    }
Michael Niedermayer's avatar
Michael Niedermayer committed
259
#endif
Michael Niedermayer's avatar
Michael Niedermayer committed
260
    if(!get_cabac_terminate(&c))
Michael Niedermayer's avatar
Michael Niedermayer committed
261
        av_log(NULL, AV_LOG_ERROR, "where's the Terminator?\n");
262

Michael Niedermayer's avatar
Michael Niedermayer committed
263 264 265
    return 0;
}

266
#endif /* TEST */