golomb rice codes
[ffmpeg.git] / libavcodec / golomb.h
1 /*
2  * exp golomb vlc stuff
3  * Copyright (c) 2003 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 golomb.h
23  * @brief 
24  *     exp golomb vlc stuff
25  * @author Michael Niedermayer <michaelni@gmx.at>
26  */
27
28 #define INVALID_VLC           0x80000000
29
30 extern const uint8_t ff_golomb_vlc_len[512];
31 extern const uint8_t ff_ue_golomb_vlc_code[512];
32 extern const  int8_t ff_se_golomb_vlc_code[512];
33 extern const uint8_t ff_ue_golomb_len[256];
34
35 extern const uint8_t ff_interleaved_golomb_vlc_len[256];
36 extern const uint8_t ff_interleaved_ue_golomb_vlc_code[256];
37 extern const  int8_t ff_interleaved_se_golomb_vlc_code[256];
38
39  
40  /**
41  * read unsigned exp golomb code.
42  */
43 static inline int get_ue_golomb(GetBitContext *gb){
44     unsigned int buf;
45     int log;
46     
47     OPEN_READER(re, gb);
48     UPDATE_CACHE(re, gb);
49     buf=GET_CACHE(re, gb);
50     
51     if(buf >= (1<<27)){
52         buf >>= 32 - 9;
53         LAST_SKIP_BITS(re, gb, ff_golomb_vlc_len[buf]);
54         CLOSE_READER(re, gb);
55     
56         return ff_ue_golomb_vlc_code[buf];
57     }else{
58         log= 2*av_log2(buf) - 31;
59         buf>>= log;
60         buf--;
61         LAST_SKIP_BITS(re, gb, 32 - log);
62         CLOSE_READER(re, gb);
63     
64         return buf;
65     }
66 }
67
68 static inline int svq3_get_ue_golomb(GetBitContext *gb){
69     uint32_t buf;
70     int log;
71
72     OPEN_READER(re, gb);
73     UPDATE_CACHE(re, gb);
74     buf=GET_CACHE(re, gb);
75     
76     if(buf&0xAA800000){
77         buf >>= 32 - 8;
78         LAST_SKIP_BITS(re, gb, ff_interleaved_golomb_vlc_len[buf]);
79         CLOSE_READER(re, gb);
80         
81         return ff_interleaved_ue_golomb_vlc_code[buf];
82     }else{
83         buf|=1;
84         if((buf & 0xAAAAAAAA) == 0)
85             return INVALID_VLC;
86
87         for(log=31; (buf & 0x80000000) == 0; log--){
88             buf = (buf << 2) - ((buf << log) >> (log - 1)) + (buf >> 30);
89         }
90
91         LAST_SKIP_BITS(re, gb, 63 - 2*log);
92         CLOSE_READER(re, gb);
93
94         return ((buf << log) >> log) - 1;
95     }
96 }
97
98 /**
99  * read unsigned truncated exp golomb code.
100  */
101 static inline int get_te0_golomb(GetBitContext *gb, int range){
102     assert(range >= 1);
103     
104     if(range==1)      return 0;
105     else if(range==2) return get_bits1(gb)^1;
106     else              return get_ue_golomb(gb);
107 }
108
109 /**
110  * read unsigned truncated exp golomb code.
111  */
112 static inline int get_te_golomb(GetBitContext *gb, int range){
113     assert(range >= 1);
114     
115     if(range==2) return get_bits1(gb)^1;
116     else         return get_ue_golomb(gb);
117 }
118
119
120 /**
121  * read signed exp golomb code.
122  */
123 static inline int get_se_golomb(GetBitContext *gb){
124     unsigned int buf;
125     int log;
126     
127     OPEN_READER(re, gb);
128     UPDATE_CACHE(re, gb);
129     buf=GET_CACHE(re, gb);
130     
131     if(buf >= (1<<27)){
132         buf >>= 32 - 9;
133         LAST_SKIP_BITS(re, gb, ff_golomb_vlc_len[buf]);
134         CLOSE_READER(re, gb);
135     
136         return ff_se_golomb_vlc_code[buf];
137     }else{
138         log= 2*av_log2(buf) - 31;
139         buf>>= log;
140         
141         LAST_SKIP_BITS(re, gb, 32 - log);
142         CLOSE_READER(re, gb);
143     
144         if(buf&1) buf= -(buf>>1);
145         else      buf=  (buf>>1);
146
147         return buf;
148     }
149 }
150
151 static inline int svq3_get_se_golomb(GetBitContext *gb){
152     unsigned int buf;
153     int log;
154
155     OPEN_READER(re, gb);
156     UPDATE_CACHE(re, gb);
157     buf=GET_CACHE(re, gb);
158
159     if(buf&0xAA800000){
160         buf >>= 32 - 8;
161         LAST_SKIP_BITS(re, gb, ff_interleaved_golomb_vlc_len[buf]);
162         CLOSE_READER(re, gb);
163         
164         return ff_interleaved_se_golomb_vlc_code[buf];
165     }else{
166         buf |=1;
167         if((buf & 0xAAAAAAAA) == 0)
168             return INVALID_VLC;
169
170         for(log=31; (buf & 0x80000000) == 0; log--){
171             buf = (buf << 2) - ((buf << log) >> (log - 1)) + (buf >> 30);
172         }
173
174         LAST_SKIP_BITS(re, gb, 63 - 2*log);
175         CLOSE_READER(re, gb);
176
177         return (signed) (((((buf << log) >> log) - 1) ^ -(buf & 0x1)) + 1) >> 1;
178     }
179 }
180
181 /**
182  * read unsigned golomb rice code.
183  */
184 static inline int get_ur_golomb(GetBitContext *gb, int k, int limit, int esc_len){
185     unsigned int buf;
186     int log;
187     
188     OPEN_READER(re, gb);
189     UPDATE_CACHE(re, gb);
190     buf=GET_CACHE(re, gb);
191
192     log= av_log2(buf);
193 //printf("buf:%X log:%d\n", buf, log);
194     if(log > 31-limit){
195         buf >>= log - k;
196         buf += (30-log)<<k;
197         LAST_SKIP_BITS(re, gb, 32 + k - log);
198         CLOSE_READER(re, gb);
199     
200         return buf;
201     }else if(log == 31-limit){
202         buf >>= log - esc_len;
203         buf -= 1<<esc_len;
204         LAST_SKIP_BITS(re, gb, esc_len + limit + 1);
205         CLOSE_READER(re, gb);
206     
207         return buf + 1;
208     }else
209         return -1;
210 }
211
212 #ifdef TRACE
213
214 static inline int get_ue(GetBitContext *s, char *file, char *func, int line){
215     int show= show_bits(s, 24);
216     int pos= get_bits_count(s);
217     int i= get_ue_golomb(s);
218     int len= get_bits_count(s) - pos;
219     int bits= show>>(24-len);
220     
221     print_bin(bits, len);
222     
223     printf("%5d %2d %3d ue  @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
224     
225     return i;
226 }
227
228 static inline int get_se(GetBitContext *s, char *file, char *func, int line){
229     int show= show_bits(s, 24);
230     int pos= get_bits_count(s);
231     int i= get_se_golomb(s);
232     int len= get_bits_count(s) - pos;
233     int bits= show>>(24-len);
234     
235     print_bin(bits, len);
236     
237     printf("%5d %2d %3d se  @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
238     
239     return i;
240 }
241
242 static inline int get_te(GetBitContext *s, int r, char *file, char *func, int line){
243     int show= show_bits(s, 24);
244     int pos= get_bits_count(s);
245     int i= get_te0_golomb(s, r);
246     int len= get_bits_count(s) - pos;
247     int bits= show>>(24-len);
248     
249     print_bin(bits, len);
250     
251     printf("%5d %2d %3d te  @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
252     
253     return i;
254 }
255
256 #define get_ue_golomb(a) get_ue(a, __FILE__, __PRETTY_FUNCTION__, __LINE__)
257 #define get_se_golomb(a) get_se(a, __FILE__, __PRETTY_FUNCTION__, __LINE__)
258 #define get_te_golomb(a, r) get_te(a, r, __FILE__, __PRETTY_FUNCTION__, __LINE__)
259 #define get_te0_golomb(a, r) get_te(a, r, __FILE__, __PRETTY_FUNCTION__, __LINE__)
260
261 #endif
262
263 /**
264  * write unsigned exp golomb code.
265  */
266 static inline void set_ue_golomb(PutBitContext *pb, int i){
267     int e;
268     
269     assert(i>=0);
270
271 #if 0
272     if(i=0){
273         put_bits(pb, 1, 1);
274         return;
275     }
276 #endif
277     if(i<256)
278         put_bits(pb, ff_ue_golomb_len[i], i+1);
279     else{
280         e= av_log2(i+1);
281     
282         put_bits(pb, 2*e+1, i+1);
283     }
284 }
285
286 /**
287  * write truncated unsigned exp golomb code.
288  */
289 static inline void set_te_golomb(PutBitContext *pb, int i, int range){
290     assert(range >= 1);
291     assert(i<=range);
292
293     if(range==2) put_bits(pb, 1, i^1);
294     else         set_ue_golomb(pb, i);
295 }
296
297 /**
298  * write signed exp golomb code.
299  */
300 static inline void set_se_golomb(PutBitContext *pb, int i){
301 #if 0 
302     if(i<=0) i= -2*i;
303     else     i=  2*i-1;
304 #elif 1
305     i= 2*i-1;
306     if(i<0) i^= -1; //FIXME check if gcc does the right thing
307 #else
308     i= 2*i-1;
309     i^= (i>>31);
310 #endif
311     set_ue_golomb(pb, i);
312 }
313
314 /**
315  * write unsigned golomb rice code.
316  */
317 static inline void set_ur_golomb(PutBitContext *pb, int i, int k, int limit, int esc_len){
318     int e;
319     
320     assert(i>=0);
321     
322     e= i>>k;
323     if(e<limit){
324         put_bits(pb, e + k + 1, (1<<k) + (i&((1<<k)-1)));
325     }else{
326 //    printf("set %08X, %d\n", (1<<esc_len) + i - 1, limit + esc_len + 1); 
327         put_bits(pb, limit + esc_len + 1, (1<<esc_len) + i - 1);
328 //        put_bits(pb, 1, limit + 1);
329 //        put_bits(pb, i - 1, esc_len);
330     }
331 }