rangecoder.h 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
/**
 * @file rangecoder.h
 * Range coder.
 */

27 28
#ifndef FFMPEG_RANGECODER_H
#define FFMPEG_RANGECODER_H
29

30 31
#include <stdint.h>
#include <assert.h>
32
#include "libavutil/common.h"
33

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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
typedef struct RangeCoder{
    int low;
    int range;
    int outstanding_count;
    int outstanding_byte;
    uint8_t zero_state[256];
    uint8_t  one_state[256];
    uint8_t *bytestream_start;
    uint8_t *bytestream;
    uint8_t *bytestream_end;
}RangeCoder;

void ff_init_range_encoder(RangeCoder *c, uint8_t *buf, int buf_size);
void ff_init_range_decoder(RangeCoder *c, const uint8_t *buf, int buf_size);
int ff_rac_terminate(RangeCoder *c);
void ff_build_rac_states(RangeCoder *c, int factor, int max_p);

static inline void renorm_encoder(RangeCoder *c){
    //FIXME optimize
    while(c->range < 0x100){
        if(c->outstanding_byte < 0){
            c->outstanding_byte= c->low>>8;
        }else if(c->low <= 0xFF00){
            *c->bytestream++ = c->outstanding_byte;
            for(;c->outstanding_count; c->outstanding_count--)
                *c->bytestream++ = 0xFF;
            c->outstanding_byte= c->low>>8;
        }else if(c->low >= 0x10000){
            *c->bytestream++ = c->outstanding_byte + 1;
            for(;c->outstanding_count; c->outstanding_count--)
                *c->bytestream++ = 0x00;
            c->outstanding_byte= (c->low>>8) & 0xFF;
        }else{
            c->outstanding_count++;
        }
69

Michael Niedermayer's avatar
Michael Niedermayer committed
70 71 72 73 74
        c->low = (c->low & 0xFF)<<8;
        c->range <<= 8;
    }
}

75 76 77 78 79 80 81
static inline int get_rac_count(RangeCoder *c){
    int x= c->bytestream - c->bytestream_start + c->outstanding_count;
    if(c->outstanding_byte >= 0)
        x++;
    return 8*x - av_log2(c->range);
}

Michael Niedermayer's avatar
Michael Niedermayer committed
82 83 84 85 86 87 88 89 90 91 92 93 94 95
static inline void put_rac(RangeCoder *c, uint8_t * const state, int bit){
    int range1= (c->range * (*state)) >> 8;

    assert(*state);
    assert(range1 < c->range);
    assert(range1 > 0);
    if(!bit){
        c->range -= range1;
        *state= c->zero_state[*state];
    }else{
        c->low += c->range - range1;
        c->range = range1;
        *state= c->one_state[*state];
    }
96

Michael Niedermayer's avatar
Michael Niedermayer committed
97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
    renorm_encoder(c);
}

static inline void refill(RangeCoder *c){
    if(c->range < 0x100){
        c->range <<= 8;
        c->low <<= 8;
        if(c->bytestream < c->bytestream_end)
            c->low+= c->bytestream[0];
        c->bytestream++;
    }
}

static inline int get_rac(RangeCoder *c, uint8_t * const state){
    int range1= (c->range * (*state)) >> 8;
112
    int av_unused one_mask;
113

Michael Niedermayer's avatar
Michael Niedermayer committed
114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
    c->range -= range1;
#if 1
    if(c->low < c->range){
        *state= c->zero_state[*state];
        refill(c);
        return 0;
    }else{
        c->low -= c->range;
        *state= c->one_state[*state];
        c->range = range1;
        refill(c);
        return 1;
    }
#else
    one_mask= (c->range - c->low-1)>>31;
129

Michael Niedermayer's avatar
Michael Niedermayer committed
130 131
    c->low -= c->range & one_mask;
    c->range += (range1 - c->range) & one_mask;
132

Michael Niedermayer's avatar
Michael Niedermayer committed
133
    *state= c->zero_state[(*state) + (256&one_mask)];
134

Michael Niedermayer's avatar
Michael Niedermayer committed
135 136 137 138 139 140
    refill(c);

    return one_mask&1;
#endif
}

141
#endif /* FFMPEG_RANGECODER_H */