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