rangecoder.c 4.42 KB
Newer Older
Michael Niedermayer's avatar
Michael Niedermayer committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
/*
 * Range coder
 * Copyright (c) 2004 Michael Niedermayer <michaelni@gmx.at>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library 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
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
17
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
Michael Niedermayer's avatar
Michael Niedermayer committed
18 19
 *
 */
20

Michael Niedermayer's avatar
Michael Niedermayer committed
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
/**
 * @file rangecoder.c
 * Range coder.
 * based upon
 *    "Range encoding: an algorithm for removing redundancy from a digitised
 *                     message.
 *     G. N. N. Martin                  Presented in March 1979 to the Video &
 *                                      Data Recording Conference,
 *     IBM UK Scientific Center         held in Southampton July 24-27 1979."
 *
 */

#include <string.h>

#include "avcodec.h"
#include "common.h"
#include "rangecoder.h"


void ff_init_range_encoder(RangeCoder *c, uint8_t *buf, int buf_size){
41
    c->bytestream_start=
Michael Niedermayer's avatar
Michael Niedermayer committed
42 43 44 45 46 47 48 49 50 51
    c->bytestream= buf;
    c->bytestream_end= buf + buf_size;

    c->low= 0;
    c->range= 0xFF00;
    c->outstanding_count= 0;
    c->outstanding_byte= -1;
}

void ff_init_range_decoder(RangeCoder *c, const uint8_t *buf, int buf_size){
52 53
    /* cast to avoid compiler warning */
    ff_init_range_encoder(c, (uint8_t *) buf, buf_size);
Michael Niedermayer's avatar
Michael Niedermayer committed
54 55 56 57 58 59 60 61

    c->low =(*c->bytestream++)<<8;
    c->low+= *c->bytestream++;
}

void ff_build_rac_states(RangeCoder *c, int factor, int max_p){
    const int64_t one= 1LL<<32;
    int64_t p;
62
    int last_p8, p8, i;
Michael Niedermayer's avatar
Michael Niedermayer committed
63 64 65 66 67 68

    memset(c->zero_state, 0, sizeof(c->zero_state));
    memset(c-> one_state, 0, sizeof(c-> one_state));

#if 0
    for(i=1; i<256; i++){
69
        if(c->one_state[i])
Michael Niedermayer's avatar
Michael Niedermayer committed
70
            continue;
71

Michael Niedermayer's avatar
Michael Niedermayer committed
72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
        p= (i*one + 128) >> 8;
        last_p8= i;
        for(;;){
            p+= ((one-p)*factor + one/2) >> 32;
            p8= (256*p + one/2) >> 32; //FIXME try without the one
            if(p8 <= last_p8) p8= last_p8+1;
            if(p8 > max_p) p8= max_p;
            if(p8 < last_p8)
                break;
            c->one_state[last_p8]=     p8;
            if(p8 == last_p8)
                break;
            last_p8= p8;
        }
    }
#endif
#if 1
    last_p8= 0;
    p= one/2;
    for(i=0; i<128; i++){
        p8= (256*p + one/2) >> 32; //FIXME try without the one
        if(p8 <= last_p8) p8= last_p8+1;
        if(last_p8 && last_p8<256 && p8<=max_p)
            c->one_state[last_p8]= p8;
96

Michael Niedermayer's avatar
Michael Niedermayer committed
97 98 99 100 101
        p+= ((one-p)*factor + one/2) >> 32;
        last_p8= p8;
    }
#endif
    for(i=256-max_p; i<=max_p; i++){
102
        if(c->one_state[i])
Michael Niedermayer's avatar
Michael Niedermayer committed
103 104 105 106 107 108 109 110 111
            continue;

        p= (i*one + 128) >> 8;
        p+= ((one-p)*factor + one/2) >> 32;
        p8= (256*p + one/2) >> 32; //FIXME try without the one
        if(p8 <= i) p8= i+1;
        if(p8 > max_p) p8= max_p;
        c->one_state[    i]=     p8;
    }
112

113
    for(i=1; i<255; i++)
Michael Niedermayer's avatar
Michael Niedermayer committed
114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145
        c->zero_state[i]= 256-c->one_state[256-i];
#if 0
    for(i=0; i<256; i++)
        av_log(NULL, AV_LOG_DEBUG, "%3d %3d\n", i, c->one_state[i]);
#endif
}

/**
 *
 * @return the number of bytes written
 */
int ff_rac_terminate(RangeCoder *c){
    c->range=0xFF;
    c->low +=0xFF;
    renorm_encoder(c);
    c->range=0xFF;
    renorm_encoder(c);

    assert(c->low   == 0);
    assert(c->range >= 0x100);

    return c->bytestream - c->bytestream_start;
}

#if 0 //selftest
#define SIZE 10240
int main(){
    RangeCoder c;
    uint8_t b[9*SIZE];
    uint8_t r[9*SIZE];
    int i;
    uint8_t state[10]= {0};
146

Michael Niedermayer's avatar
Michael Niedermayer committed
147 148
    ff_init_range_encoder(&c, b, SIZE);
    ff_build_rac_states(&c, 0.05*(1LL<<32), 128+64+32+16);
149

Michael Niedermayer's avatar
Michael Niedermayer committed
150 151 152 153 154
    memset(state, 128, sizeof(state));

    for(i=0; i<SIZE; i++){
        r[i]= random()%7;
    }
155 156


Michael Niedermayer's avatar
Michael Niedermayer committed
157 158 159 160 161 162 163
    for(i=0; i<SIZE; i++){
START_TIMER
        put_rac(&c, state, r[i]&1);
STOP_TIMER("put_rac")
    }

    ff_put_rac_terminate(&c);
164

Michael Niedermayer's avatar
Michael Niedermayer committed
165
    ff_init_range_decoder(&c, b, SIZE);
166

Michael Niedermayer's avatar
Michael Niedermayer committed
167
    memset(state, 128, sizeof(state));
168

Michael Niedermayer's avatar
Michael Niedermayer committed
169 170 171 172 173 174
    for(i=0; i<SIZE; i++){
START_TIMER
        if( (r[i]&1) != get_rac(&c, state) )
            av_log(NULL, AV_LOG_DEBUG, "rac failure at %d\n", i);
STOP_TIMER("get_rac")
    }
175

Michael Niedermayer's avatar
Michael Niedermayer committed
176 177 178 179
    return 0;
}

#endif