rangecoder.c 3.79 KB
Newer Older
Michael Niedermayer's avatar
Michael Niedermayer committed
1 2 3 4
/*
 * Range coder
 * Copyright (c) 2004 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

Michael Niedermayer's avatar
Michael Niedermayer committed
22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
/**
 * @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 "rangecoder.h"
38
#include "bytestream.h"
Michael Niedermayer's avatar
Michael Niedermayer committed
39 40 41


void ff_init_range_encoder(RangeCoder *c, uint8_t *buf, int buf_size){
42
    c->bytestream_start=
Michael Niedermayer's avatar
Michael Niedermayer committed
43 44 45 46 47 48 49 50 51 52
    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){
53 54
    /* cast to avoid compiler warning */
    ff_init_range_encoder(c, (uint8_t *) buf, buf_size);
Michael Niedermayer's avatar
Michael Niedermayer committed
55

56
    c->low = bytestream_get_be16(&c->bytestream);
Michael Niedermayer's avatar
Michael Niedermayer committed
57 58 59 60 61
}

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 69 70 71 72 73

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

    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;
74

Michael Niedermayer's avatar
Michael Niedermayer committed
75 76 77
        p+= ((one-p)*factor + one/2) >> 32;
        last_p8= p8;
    }
78

Michael Niedermayer's avatar
Michael Niedermayer committed
79
    for(i=256-max_p; i<=max_p; i++){
80
        if(c->one_state[i])
Michael Niedermayer's avatar
Michael Niedermayer committed
81 82 83 84 85 86 87 88 89
            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;
    }
90

91
    for(i=1; i<255; i++)
Michael Niedermayer's avatar
Michael Niedermayer committed
92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
        c->zero_state[i]= 256-c->one_state[256-i];
}

/**
 *
 * @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;
}

112
#ifdef TEST
Michael Niedermayer's avatar
Michael Niedermayer committed
113
#define SIZE 10240
114
#undef random
Diego Biurrun's avatar
Diego Biurrun committed
115
int main(void){
Michael Niedermayer's avatar
Michael Niedermayer committed
116 117 118 119 120
    RangeCoder c;
    uint8_t b[9*SIZE];
    uint8_t r[9*SIZE];
    int i;
    uint8_t state[10]= {0};
121

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

Michael Niedermayer's avatar
Michael Niedermayer committed
125 126 127 128 129
    memset(state, 128, sizeof(state));

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

Michael Niedermayer's avatar
Michael Niedermayer committed
131 132 133 134 135 136
    for(i=0; i<SIZE; i++){
START_TIMER
        put_rac(&c, state, r[i]&1);
STOP_TIMER("put_rac")
    }

137
    ff_rac_terminate(&c);
138

Michael Niedermayer's avatar
Michael Niedermayer committed
139
    ff_init_range_decoder(&c, b, SIZE);
140

Michael Niedermayer's avatar
Michael Niedermayer committed
141
    memset(state, 128, sizeof(state));
142

Michael Niedermayer's avatar
Michael Niedermayer committed
143 144 145 146 147 148
    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")
    }
149

Michael Niedermayer's avatar
Michael Niedermayer committed
150 151
    return 0;
}
152
#endif /* TEST */