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
32#include "libavutil/common.h"
33#include "libavutil/avassert.h"
34
35typedef struct RangeCoder {
36    int low;
37    int range;
38    int outstanding_count;
39    int outstanding_byte;
40    uint8_t zero_state[256];
41    uint8_t one_state[256];
42    uint8_t *bytestream_start;
43    uint8_t *bytestream;
44    uint8_t *bytestream_end;
45} RangeCoder;
46
47void ff_init_range_encoder(RangeCoder *c, uint8_t *buf, int buf_size);
48void ff_init_range_decoder(RangeCoder *c, const uint8_t *buf, int buf_size);
49int ff_rac_terminate(RangeCoder *c);
50void ff_build_rac_states(RangeCoder *c, int factor, int max_p);
51
52static inline void renorm_encoder(RangeCoder *c)
53{
54    // FIXME: optimize
55    while (c->range < 0x100) {
56        if (c->outstanding_byte < 0) {
57            c->outstanding_byte = c->low >> 8;
58        } else if (c->low <= 0xFF00) {
59            *c->bytestream++ = c->outstanding_byte;
60            for (; c->outstanding_count; c->outstanding_count--)
61                *c->bytestream++ = 0xFF;
62            c->outstanding_byte = c->low >> 8;
63        } else if (c->low >= 0x10000) {
64            *c->bytestream++ = c->outstanding_byte + 1;
65            for (; c->outstanding_count; c->outstanding_count--)
66                *c->bytestream++ = 0x00;
67            c->outstanding_byte = (c->low >> 8) & 0xFF;
68        } else {
69            c->outstanding_count++;
70        }
71
72        c->low     = (c->low & 0xFF) << 8;
73        c->range <<= 8;
74    }
75}
76
77static inline int get_rac_count(RangeCoder *c)
78{
79    int x = c->bytestream - c->bytestream_start + c->outstanding_count;
80    if (c->outstanding_byte >= 0)
81        x++;
82    return 8 * x - av_log2(c->range);
83}
84
85static inline void put_rac(RangeCoder *c, uint8_t *const state, int bit)
86{
87    int range1 = (c->range * (*state)) >> 8;
88
89    av_assert2(*state);
90    av_assert2(range1 < c->range);
91    av_assert2(range1 > 0);
92    if (!bit) {
93        c->range -= range1;
94        *state    = c->zero_state[*state];
95    } else {
96        c->low  += c->range - range1;
97        c->range = range1;
98        *state   = c->one_state[*state];
99    }
100
101    renorm_encoder(c);
102}
103
104static inline void refill(RangeCoder *c)
105{
106    if (c->range < 0x100) {
107        c->range <<= 8;
108        c->low   <<= 8;
109        if (c->bytestream < c->bytestream_end)
110            c->low += c->bytestream[0];
111        c->bytestream++;
112    }
113}
114
115static inline int get_rac(RangeCoder *c, uint8_t *const state)
116{
117    int range1 = (c->range * (*state)) >> 8;
118    int av_unused one_mask;
119
120    c->range -= range1;
121#if 1
122    if (c->low < c->range) {
123        *state = c->zero_state[*state];
124        refill(c);
125        return 0;
126    } else {
127        c->low  -= c->range;
128        *state   = c->one_state[*state];
129        c->range = range1;
130        refill(c);
131        return 1;
132    }
133#else
134    one_mask = (c->range - c->low - 1) >> 31;
135
136    c->low   -= c->range & one_mask;
137    c->range += (range1 - c->range) & one_mask;
138
139    *state = c->zero_state[(*state) + (256 & one_mask)];
140
141    refill(c);
142
143    return one_mask & 1;
144#endif
145}
146
147#endif /* AVCODEC_RANGECODER_H */
148