rangecoder.h 3.9 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
 * @file
Michael Niedermayer's avatar
Michael Niedermayer committed
24 25 26
 * Range coder.
 */

27 28
#ifndef AVCODEC_RANGECODER_H
#define AVCODEC_RANGECODER_H
29

30
#include <stdint.h>
31

32
#include "libavutil/common.h"
33
#include "libavutil/avassert.h"
34

35
typedef struct RangeCoder {
Michael Niedermayer's avatar
Michael Niedermayer committed
36 37 38 39 40
    int low;
    int range;
    int outstanding_count;
    int outstanding_byte;
    uint8_t zero_state[256];
41
    uint8_t one_state[256];
Michael Niedermayer's avatar
Michael Niedermayer committed
42 43 44
    uint8_t *bytestream_start;
    uint8_t *bytestream;
    uint8_t *bytestream_end;
45
} RangeCoder;
Michael Niedermayer's avatar
Michael Niedermayer committed
46 47 48 49 50 51

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

52 53 54 55 56 57 58
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) {
Michael Niedermayer's avatar
Michael Niedermayer committed
59
            *c->bytestream++ = c->outstanding_byte;
60
            for (; c->outstanding_count; c->outstanding_count--)
Michael Niedermayer's avatar
Michael Niedermayer committed
61
                *c->bytestream++ = 0xFF;
62 63
            c->outstanding_byte = c->low >> 8;
        } else if (c->low >= 0x10000) {
Michael Niedermayer's avatar
Michael Niedermayer committed
64
            *c->bytestream++ = c->outstanding_byte + 1;
65
            for (; c->outstanding_count; c->outstanding_count--)
Michael Niedermayer's avatar
Michael Niedermayer committed
66
                *c->bytestream++ = 0x00;
67 68
            c->outstanding_byte = (c->low >> 8) & 0xFF;
        } else {
Michael Niedermayer's avatar
Michael Niedermayer committed
69 70
            c->outstanding_count++;
        }
71

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

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

85 86 87
static inline void put_rac(RangeCoder *c, uint8_t *const state, int bit)
{
    int range1 = (c->range * (*state)) >> 8;
Michael Niedermayer's avatar
Michael Niedermayer committed
88

89 90 91
    av_assert2(*state);
    av_assert2(range1 < c->range);
    av_assert2(range1 > 0);
92
    if (!bit) {
Michael Niedermayer's avatar
Michael Niedermayer committed
93
        c->range -= range1;
94 95 96
        *state    = c->zero_state[*state];
    } else {
        c->low  += c->range - range1;
Michael Niedermayer's avatar
Michael Niedermayer committed
97
        c->range = range1;
98
        *state   = c->one_state[*state];
Michael Niedermayer's avatar
Michael Niedermayer committed
99
    }
100

Michael Niedermayer's avatar
Michael Niedermayer committed
101 102 103
    renorm_encoder(c);
}

104 105 106
static inline void refill(RangeCoder *c)
{
    if (c->range < 0x100) {
Michael Niedermayer's avatar
Michael Niedermayer committed
107
        c->range <<= 8;
108 109 110
        c->low   <<= 8;
        if (c->bytestream < c->bytestream_end)
            c->low += c->bytestream[0];
Michael Niedermayer's avatar
Michael Niedermayer committed
111 112 113 114
        c->bytestream++;
    }
}

115 116 117
static inline int get_rac(RangeCoder *c, uint8_t *const state)
{
    int range1 = (c->range * (*state)) >> 8;
118

Michael Niedermayer's avatar
Michael Niedermayer committed
119 120
    c->range -= range1;
#if 1
121 122
    if (c->low < c->range) {
        *state = c->zero_state[*state];
Michael Niedermayer's avatar
Michael Niedermayer committed
123 124
        refill(c);
        return 0;
125 126 127
    } else {
        c->low  -= c->range;
        *state   = c->one_state[*state];
Michael Niedermayer's avatar
Michael Niedermayer committed
128 129 130 131 132
        c->range = range1;
        refill(c);
        return 1;
    }
#else
133 134
    {
        int one_mask one_mask = (c->range - c->low - 1) >> 31;
135

136 137
        c->low   -=           c->range  & one_mask;
        c->range += (range1 - c->range) & one_mask;
138

139 140
        *state = c->zero_state[(*state) + (256 & one_mask)];
    }
Michael Niedermayer's avatar
Michael Niedermayer committed
141 142
    refill(c);

143
    return one_mask & 1;
Michael Niedermayer's avatar
Michael Niedermayer committed
144 145 146
#endif
}

147
#endif /* AVCODEC_RANGECODER_H */