cabac.c 6.7 KB
Newer Older
michaelni's avatar
CABAC  
michaelni 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
michaelni's avatar
CABAC  
michaelni 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.
michaelni's avatar
CABAC  
michaelni committed
11
 *
12
 * FFmpeg is distributed in the hope that it will be useful,
michaelni's avatar
CABAC  
michaelni 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
michaelni's avatar
CABAC  
michaelni committed
20 21 22 23 24 25 26 27 28 29 30
 *
 */

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

#include <string.h>

#include "common.h"
31
#include "bitstream.h"
michaelni's avatar
CABAC  
michaelni committed
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 63 64 65 66 67 68 69 70 71 72 73 74
#include "cabac.h"

const uint8_t ff_h264_lps_range[64][4]= {
{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},
};

const uint8_t ff_h264_mps_state[64]= {
  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,
};

const uint8_t ff_h264_lps_state[64]= {
  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,
};

michael's avatar
michael committed
75 76
const uint8_t ff_h264_norm_shift[128]= {
 7,6,5,5,4,4,4,4,3,3,3,3,3,3,3,3,
77
 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
michael's avatar
michael committed
78 79
 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,
michael's avatar
michael committed
80 81 82 83
 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 0,0,0,0,0,0,0,0,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's avatar
michael committed
84 85
};

michaelni's avatar
CABAC  
michaelni committed
86 87 88 89 90
/**
 *
 * @param buf_size size of buf in bits
 */
void ff_init_cabac_encoder(CABACContext *c, uint8_t *buf, int buf_size){
91
    init_put_bits(&c->pb, buf, buf_size);
michaelni's avatar
CABAC  
michaelni committed
92 93 94 95 96 97 98

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

michaelni's avatar
CABAC  
michaelni committed
100 101 102 103 104 105 106
    c->pb.bit_left++; //avoids firstBitFlag
}

/**
 *
 * @param buf_size size of buf in bits
 */
107
void ff_init_cabac_decoder(CABACContext *c, const uint8_t *buf, int buf_size){
108
    c->bytestream_start=
michaelni's avatar
CABAC  
michaelni committed
109
    c->bytestream= buf;
michael's avatar
michael committed
110
    c->bytestream_end= buf + buf_size;
michaelni's avatar
CABAC  
michaelni committed
111

michael's avatar
michael committed
112 113 114 115 116 117 118 119
#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;
    c->range= 0x1FE<<(CABAC_BITS + 1);
michaelni's avatar
CABAC  
michaelni committed
120 121
}

122
void ff_init_cabac_states(CABACContext *c, uint8_t const (*lps_range)[4],
michaelni's avatar
CABAC  
michaelni committed
123 124
                          uint8_t const *mps_state, uint8_t const *lps_state, int state_count){
    int i, j;
125

michaelni's avatar
CABAC  
michaelni committed
126 127
    for(i=0; i<state_count; i++){
        for(j=0; j<4; j++){ //FIXME check if this is worth the 1 shift we save
128 129
            c->lps_range[2*i+0][j+4]=
            c->lps_range[2*i+1][j+4]= lps_range[i][j];
michaelni's avatar
CABAC  
michaelni committed
130 131
        }

132 133
        c->mps_state[2*i+0]= 2*mps_state[i]+0;
        c->mps_state[2*i+1]= 2*mps_state[i]+1;
michaelni's avatar
CABAC  
michaelni committed
134

135
        if( i ){
136
#ifdef BRANCHLESS_CABAC_DECODER
137 138
            c->mps_state[-2*i-1]= 2*lps_state[i]+0; //FIXME yes this is not valid C but iam lazy, cleanup welcome
            c->mps_state[-2*i-2]= 2*lps_state[i]+1;
139
        }else{
140 141
            c->mps_state[-2*i-1]= 1;
            c->mps_state[-2*i-2]= 0;
142
#else
143 144
            c->lps_state[2*i+0]= 2*lps_state[i]+0;
            c->lps_state[2*i+1]= 2*lps_state[i]+1;
michaelni's avatar
CABAC  
michaelni committed
145
        }else{
146 147
            c->lps_state[2*i+0]= 1;
            c->lps_state[2*i+1]= 0;
148
#endif
michaelni's avatar
CABAC  
michaelni committed
149 150 151 152 153 154
        }
    }
}

#if 0 //selftest
#define SIZE 10240
michael's avatar
michael committed
155 156 157

#include "avcodec.h"

michaelni's avatar
CABAC  
michaelni committed
158 159 160
int main(){
    CABACContext c;
    uint8_t b[9*SIZE];
michaelni's avatar
michaelni committed
161
    uint8_t r[9*SIZE];
michaelni's avatar
CABAC  
michaelni committed
162
    int i;
michaelni's avatar
michaelni committed
163
    uint8_t state[10]= {0};
164

michaelni's avatar
CABAC  
michaelni committed
165 166
    ff_init_cabac_encoder(&c, b, SIZE);
    ff_init_cabac_states(&c, ff_h264_lps_range, ff_h264_mps_state, ff_h264_lps_state, 64);
167

michaelni's avatar
CABAC  
michaelni committed
168
    for(i=0; i<SIZE; i++){
michaelni's avatar
michaelni committed
169
        r[i]= random()%7;
michaelni's avatar
CABAC  
michaelni committed
170
    }
171

michaelni's avatar
CABAC  
michaelni committed
172 173
    for(i=0; i<SIZE; i++){
START_TIMER
michaelni's avatar
michaelni committed
174
        put_cabac_bypass(&c, r[i]&1);
michaelni's avatar
CABAC  
michaelni committed
175 176
STOP_TIMER("put_cabac_bypass")
    }
177

michaelni's avatar
CABAC  
michaelni committed
178 179
    for(i=0; i<SIZE; i++){
START_TIMER
michaelni's avatar
michaelni committed
180
        put_cabac(&c, state, r[i]&1);
michaelni's avatar
CABAC  
michaelni committed
181 182 183
STOP_TIMER("put_cabac")
    }

michaelni's avatar
michaelni committed
184 185 186 187
    for(i=0; i<SIZE; i++){
START_TIMER
        put_cabac_u(&c, state, r[i], 6, 3, i&1);
STOP_TIMER("put_cabac_u")
188
    }
michaelni's avatar
michaelni committed
189 190 191

    for(i=0; i<SIZE; i++){
START_TIMER
michaelni's avatar
michaelni committed
192
        put_cabac_ueg(&c, state, r[i], 3, 0, 1, 2);
michaelni's avatar
michaelni committed
193
STOP_TIMER("put_cabac_ueg")
194 195
    }

michaelni's avatar
CABAC  
michaelni committed
196
    put_cabac_terminate(&c, 1);
197

michaelni's avatar
CABAC  
michaelni committed
198
    ff_init_cabac_decoder(&c, b, SIZE);
199

michaelni's avatar
michaelni committed
200
    memset(state, 0, sizeof(state));
201

michaelni's avatar
CABAC  
michaelni committed
202 203
    for(i=0; i<SIZE; i++){
START_TIMER
michaelni's avatar
michaelni committed
204
        if( (r[i]&1) != get_cabac_bypass(&c) )
michael's avatar
michael committed
205
            av_log(NULL, AV_LOG_ERROR, "CABAC bypass failure at %d\n", i);
michaelni's avatar
CABAC  
michaelni committed
206 207
STOP_TIMER("get_cabac_bypass")
    }
208

michaelni's avatar
CABAC  
michaelni committed
209 210
    for(i=0; i<SIZE; i++){
START_TIMER
michaelni's avatar
michaelni committed
211
        if( (r[i]&1) != get_cabac(&c, state) )
michael's avatar
michael committed
212
            av_log(NULL, AV_LOG_ERROR, "CABAC failure at %d\n", i);
michaelni's avatar
CABAC  
michaelni committed
213 214
STOP_TIMER("get_cabac")
    }
michael's avatar
michael committed
215
#if 0
michaelni's avatar
michaelni committed
216 217 218
    for(i=0; i<SIZE; i++){
START_TIMER
        if( r[i] != get_cabac_u(&c, state, (i&1) ? 6 : 7, 3, i&1) )
michael's avatar
michael committed
219
            av_log(NULL, AV_LOG_ERROR, "CABAC unary (truncated) binarization failure at %d\n", i);
michaelni's avatar
michaelni committed
220 221 222 223 224 225
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's avatar
michael committed
226
            av_log(NULL, AV_LOG_ERROR, "CABAC unary (truncated) binarization failure at %d\n", i);
michaelni's avatar
michaelni committed
227 228
STOP_TIMER("get_cabac_ueg")
    }
michael's avatar
michael committed
229
#endif
michaelni's avatar
CABAC  
michaelni committed
230
    if(!get_cabac_terminate(&c))
michael's avatar
michael committed
231
        av_log(NULL, AV_LOG_ERROR, "where's the Terminator?\n");
232

michaelni's avatar
CABAC  
michaelni committed
233 234 235 236
    return 0;
}

#endif