golomb rice code cleanup / simplify (~0.5% compression gain and slightly faster)
[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 (ffv1).
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
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{
202         buf >>= 32 - limit - esc_len;
203         LAST_SKIP_BITS(re, gb, esc_len + limit);
204         CLOSE_READER(re, gb);
205     
206         return buf + limit - 1;
207     }
208 }
209
210 /**
211  * read unsigned golomb rice code (jpegls).
212  */
213 static inline int get_ur_golomb_jpegls(GetBitContext *gb, int k, int limit, int esc_len){
214     unsigned int buf;
215     int log;
216     
217     OPEN_READER(re, gb);
218     UPDATE_CACHE(re, gb);
219     buf=GET_CACHE(re, gb);
220
221     log= av_log2(buf);
222     
223     if(log > 31-12){
224         buf >>= log - k;
225         buf += (30-log)<<k;
226         LAST_SKIP_BITS(re, gb, 32 + k - log);
227         CLOSE_READER(re, gb);
228     
229         return buf;
230     }else{
231         int i;
232         for(i=0; SHOW_UBITS(re, gb, 1) == 0; i++){
233             LAST_SKIP_BITS(re, gb, 1);
234             UPDATE_CACHE(re, gb);
235         }
236         SKIP_BITS(re, gb, 1);
237
238         if(i < limit - 1){
239             if(k){
240                 buf = SHOW_UBITS(re, gb, k);
241                 LAST_SKIP_BITS(re, gb, k);
242             }else{
243                 buf=0;
244             }
245
246             CLOSE_READER(re, gb);
247             return buf + (i<<k);
248         }else if(i == limit - 1){
249             buf = SHOW_UBITS(re, gb, esc_len);
250             LAST_SKIP_BITS(re, gb, esc_len);
251             CLOSE_READER(re, gb);
252     
253             return buf + 1;
254         }else
255             return -1;
256     }
257 }
258
259 #ifdef TRACE
260
261 static inline int get_ue(GetBitContext *s, char *file, char *func, int line){
262     int show= show_bits(s, 24);
263     int pos= get_bits_count(s);
264     int i= get_ue_golomb(s);
265     int len= get_bits_count(s) - pos;
266     int bits= show>>(24-len);
267     
268     print_bin(bits, len);
269     
270     printf("%5d %2d %3d ue  @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
271     
272     return i;
273 }
274
275 static inline int get_se(GetBitContext *s, char *file, char *func, int line){
276     int show= show_bits(s, 24);
277     int pos= get_bits_count(s);
278     int i= get_se_golomb(s);
279     int len= get_bits_count(s) - pos;
280     int bits= show>>(24-len);
281     
282     print_bin(bits, len);
283     
284     printf("%5d %2d %3d se  @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
285     
286     return i;
287 }
288
289 static inline int get_te(GetBitContext *s, int r, char *file, char *func, int line){
290     int show= show_bits(s, 24);
291     int pos= get_bits_count(s);
292     int i= get_te0_golomb(s, r);
293     int len= get_bits_count(s) - pos;
294     int bits= show>>(24-len);
295     
296     print_bin(bits, len);
297     
298     printf("%5d %2d %3d te  @%5d in %s %s:%d\n", bits, len, i, pos, file, func, line);
299     
300     return i;
301 }
302
303 #define get_ue_golomb(a) get_ue(a, __FILE__, __PRETTY_FUNCTION__, __LINE__)
304 #define get_se_golomb(a) get_se(a, __FILE__, __PRETTY_FUNCTION__, __LINE__)
305 #define get_te_golomb(a, r) get_te(a, r, __FILE__, __PRETTY_FUNCTION__, __LINE__)
306 #define get_te0_golomb(a, r) get_te(a, r, __FILE__, __PRETTY_FUNCTION__, __LINE__)
307
308 #endif
309
310 /**
311  * write unsigned exp golomb code.
312  */
313 static inline void set_ue_golomb(PutBitContext *pb, int i){
314     int e;
315     
316     assert(i>=0);
317
318 #if 0
319     if(i=0){
320         put_bits(pb, 1, 1);
321         return;
322     }
323 #endif
324     if(i<256)
325         put_bits(pb, ff_ue_golomb_len[i], i+1);
326     else{
327         e= av_log2(i+1);
328     
329         put_bits(pb, 2*e+1, i+1);
330     }
331 }
332
333 /**
334  * write truncated unsigned exp golomb code.
335  */
336 static inline void set_te_golomb(PutBitContext *pb, int i, int range){
337     assert(range >= 1);
338     assert(i<=range);
339
340     if(range==2) put_bits(pb, 1, i^1);
341     else         set_ue_golomb(pb, i);
342 }
343
344 /**
345  * write signed exp golomb code.
346  */
347 static inline void set_se_golomb(PutBitContext *pb, int i){
348 #if 0 
349     if(i<=0) i= -2*i;
350     else     i=  2*i-1;
351 #elif 1
352     i= 2*i-1;
353     if(i<0) i^= -1; //FIXME check if gcc does the right thing
354 #else
355     i= 2*i-1;
356     i^= (i>>31);
357 #endif
358     set_ue_golomb(pb, i);
359 }
360
361 /**
362  * write unsigned golomb rice code (ffv1).
363  */
364 static inline void set_ur_golomb(PutBitContext *pb, int i, int k, int limit, int esc_len){
365     int e;
366     
367     assert(i>=0);
368     
369     e= i>>k;
370     if(e<limit){
371         put_bits(pb, e + k + 1, (1<<k) + (i&((1<<k)-1)));
372     }else{
373         put_bits(pb, limit + esc_len, i - limit + 1);
374     }
375 }
376
377 /**
378  * write unsigned golomb rice code (jpegls).
379  */
380 static inline void set_ur_golomb_jpegls(PutBitContext *pb, int i, int k, int limit, int esc_len){
381     int e;
382     
383     assert(i>=0);
384     
385     e= (i>>k) + 1;
386     if(e<limit){
387         put_bits(pb, e, 1);
388         put_bits(pb, k, i&((1<<k)-1));
389     }else{
390         put_bits(pb, limit  , 1);
391         put_bits(pb, esc_len, i - 1);
392     }
393 }