1/*
2 * Range coder
3 * Copyright (c) 2004 Michael Niedermayer <michaelni@gmx.at>
4 *
5 * This file is part of FFmpeg.
6 *
7 * FFmpeg is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
11 *
12 * FFmpeg is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15 * Lesser General Public License for more details.
16 *
17 * 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
20 */
21
22/**
23 * @file
24 * Range coder.
25 */
26
27#ifndef AVCODEC_RANGECODER_H
28#define AVCODEC_RANGECODER_H
29
30#include <stdint.h>
31#include <assert.h>
32#include "libavutil/common.h"
33
34typedef struct RangeCoder{
35    int low;
36    int range;
37    int outstanding_count;
38    int outstanding_byte;
39    uint8_t zero_state[256];
40    uint8_t  one_state[256];
41    uint8_t *bytestream_start;
42    uint8_t *bytestream;
43    uint8_t *bytestream_end;
44}RangeCoder;
45
46void ff_init_range_encoder(RangeCoder *c, uint8_t *buf, int buf_size);
47void ff_init_range_decoder(RangeCoder *c, const uint8_t *buf, int buf_size);
48int ff_rac_terminate(RangeCoder *c);
49void ff_build_rac_states(RangeCoder *c, int factor, int max_p);
50
51static inline void renorm_encoder(RangeCoder *c){
52    //FIXME optimize
53    while(c->range < 0x100){
54        if(c->outstanding_byte < 0){
55            c->outstanding_byte= c->low>>8;
56        }else if(c->low <= 0xFF00){
57            *c->bytestream++ = c->outstanding_byte;
58            for(;c->outstanding_count; c->outstanding_count--)
59                *c->bytestream++ = 0xFF;
60            c->outstanding_byte= c->low>>8;
61        }else if(c->low >= 0x10000){
62            *c->bytestream++ = c->outstanding_byte + 1;
63            for(;c->outstanding_count; c->outstanding_count--)
64                *c->bytestream++ = 0x00;
65            c->outstanding_byte= (c->low>>8) & 0xFF;
66        }else{
67            c->outstanding_count++;
68        }
69
70        c->low = (c->low & 0xFF)<<8;
71        c->range <<= 8;
72    }
73}
74
75static inline int get_rac_count(RangeCoder *c){
76    int x= c->bytestream - c->bytestream_start + c->outstanding_count;
77    if(c->outstanding_byte >= 0)
78        x++;
79    return 8*x - av_log2(c->range);
80}
81
82static inline void put_rac(RangeCoder *c, uint8_t * const state, int bit){
83    int range1= (c->range * (*state)) >> 8;
84
85    assert(*state);
86    assert(range1 < c->range);
87    assert(range1 > 0);
88    if(!bit){
89        c->range -= range1;
90        *state= c->zero_state[*state];
91    }else{
92        c->low += c->range - range1;
93        c->range = range1;
94        *state= c->one_state[*state];
95    }
96
97    renorm_encoder(c);
98}
99
100static inline void refill(RangeCoder *c){
101    if(c->range < 0x100){
102        c->range <<= 8;
103        c->low <<= 8;
104        if(c->bytestream < c->bytestream_end)
105            c->low+= c->bytestream[0];
106        c->bytestream++;
107    }
108}
109
110static inline int get_rac(RangeCoder *c, uint8_t * const state){
111    int range1= (c->range * (*state)) >> 8;
112    int av_unused one_mask;
113
114    c->range -= range1;
115#if 1
116    if(c->low < c->range){
117        *state= c->zero_state[*state];
118        refill(c);
119        return 0;
120    }else{
121        c->low -= c->range;
122        *state= c->one_state[*state];
123        c->range = range1;
124        refill(c);
125        return 1;
126    }
127#else
128    one_mask= (c->range - c->low-1)>>31;
129
130    c->low -= c->range & one_mask;
131    c->range += (range1 - c->range) & one_mask;
132
133    *state= c->zero_state[(*state) + (256&one_mask)];
134
135    refill(c);
136
137    return one_mask&1;
138#endif
139}
140
141#endif /* AVCODEC_RANGECODER_H */
142