1/*
2 * exp golomb vlc stuff
3 * Copyright (c) 2003 Michael Niedermayer <michaelni@gmx.at>
4 * Copyright (c) 2004 Alex Beregszaszi
5 *
6 * This file is part of FFmpeg.
7 *
8 * FFmpeg is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
12 *
13 * FFmpeg is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16 * Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with FFmpeg; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
21 */
22
23/**
24 * @file
25 * @brief
26 *     exp golomb vlc stuff
27 * @author Michael Niedermayer <michaelni@gmx.at> and Alex Beregszaszi
28 */
29
30#ifndef AVCODEC_GOLOMB_H
31#define AVCODEC_GOLOMB_H
32
33#include <stdint.h>
34
35#include "get_bits.h"
36#include "put_bits.h"
37
38#define INVALID_VLC           0x80000000
39
40extern const uint8_t ff_golomb_vlc_len[512];
41extern const uint8_t ff_ue_golomb_vlc_code[512];
42extern const  int8_t ff_se_golomb_vlc_code[512];
43extern const uint8_t ff_ue_golomb_len[256];
44
45extern const uint8_t ff_interleaved_golomb_vlc_len[256];
46extern const uint8_t ff_interleaved_ue_golomb_vlc_code[256];
47extern const  int8_t ff_interleaved_se_golomb_vlc_code[256];
48extern const uint8_t ff_interleaved_dirac_golomb_vlc_code[256];
49
50/**
51 * read unsigned exp golomb code.
52 */
53static inline int get_ue_golomb(GetBitContext *gb)
54{
55    unsigned int buf;
56
57    OPEN_READER(re, gb);
58    UPDATE_CACHE(re, gb);
59    buf = GET_CACHE(re, gb);
60
61    if (buf >= (1 << 27)) {
62        buf >>= 32 - 9;
63        LAST_SKIP_BITS(re, gb, ff_golomb_vlc_len[buf]);
64        CLOSE_READER(re, gb);
65
66        return ff_ue_golomb_vlc_code[buf];
67    } else {
68        int log = 2 * av_log2(buf) - 31;
69        LAST_SKIP_BITS(re, gb, 32 - log);
70        CLOSE_READER(re, gb);
71        if (CONFIG_FTRAPV && log < 0) {
72            av_log(0, AV_LOG_ERROR, "Invalid UE golomb code\n");
73            return AVERROR_INVALIDDATA;
74        }
75        buf >>= log;
76        buf--;
77
78        return buf;
79    }
80}
81
82/**
83 * Read an unsigned Exp-Golomb code in the range 0 to UINT32_MAX-1.
84 */
85static inline unsigned get_ue_golomb_long(GetBitContext *gb)
86{
87    unsigned buf, log;
88
89    buf = show_bits_long(gb, 32);
90    log = 31 - av_log2(buf);
91    skip_bits_long(gb, log);
92
93    return get_bits_long(gb, log + 1) - 1;
94}
95
96/**
97 * read unsigned exp golomb code, constraint to a max of 31.
98 * the return value is undefined if the stored value exceeds 31.
99 */
100static inline int get_ue_golomb_31(GetBitContext *gb)
101{
102    unsigned int buf;
103
104    OPEN_READER(re, gb);
105    UPDATE_CACHE(re, gb);
106    buf = GET_CACHE(re, gb);
107
108    buf >>= 32 - 9;
109    LAST_SKIP_BITS(re, gb, ff_golomb_vlc_len[buf]);
110    CLOSE_READER(re, gb);
111
112    return ff_ue_golomb_vlc_code[buf];
113}
114
115static inline unsigned svq3_get_ue_golomb(GetBitContext *gb)
116{
117    uint32_t buf;
118
119    OPEN_READER(re, gb);
120    UPDATE_CACHE(re, gb);
121    buf = GET_CACHE(re, gb);
122
123    if (buf & 0xAA800000) {
124        buf >>= 32 - 8;
125        LAST_SKIP_BITS(re, gb, ff_interleaved_golomb_vlc_len[buf]);
126        CLOSE_READER(re, gb);
127
128        return ff_interleaved_ue_golomb_vlc_code[buf];
129    } else {
130        unsigned ret = 1;
131
132        do {
133            buf >>= 32 - 8;
134            LAST_SKIP_BITS(re, gb,
135                           FFMIN(ff_interleaved_golomb_vlc_len[buf], 8));
136
137            if (ff_interleaved_golomb_vlc_len[buf] != 9) {
138                ret <<= (ff_interleaved_golomb_vlc_len[buf] - 1) >> 1;
139                ret  |= ff_interleaved_dirac_golomb_vlc_code[buf];
140                break;
141            }
142            ret = (ret << 4) | ff_interleaved_dirac_golomb_vlc_code[buf];
143            UPDATE_CACHE(re, gb);
144            buf = GET_CACHE(re, gb);
145        } while (ret<0x8000000U && HAVE_BITS_REMAINING(re, gb));
146
147        CLOSE_READER(re, gb);
148        return ret - 1;
149    }
150}
151
152/**
153 * read unsigned truncated exp golomb code.
154 */
155static inline int get_te0_golomb(GetBitContext *gb, int range)
156{
157    av_assert2(range >= 1);
158
159    if (range == 1)
160        return 0;
161    else if (range == 2)
162        return get_bits1(gb) ^ 1;
163    else
164        return get_ue_golomb(gb);
165}
166
167/**
168 * read unsigned truncated exp golomb code.
169 */
170static inline int get_te_golomb(GetBitContext *gb, int range)
171{
172    av_assert2(range >= 1);
173
174    if (range == 2)
175        return get_bits1(gb) ^ 1;
176    else
177        return get_ue_golomb(gb);
178}
179
180/**
181 * read signed exp golomb code.
182 */
183static inline int get_se_golomb(GetBitContext *gb)
184{
185    unsigned int buf;
186
187    OPEN_READER(re, gb);
188    UPDATE_CACHE(re, gb);
189    buf = GET_CACHE(re, gb);
190
191    if (buf >= (1 << 27)) {
192        buf >>= 32 - 9;
193        LAST_SKIP_BITS(re, gb, ff_golomb_vlc_len[buf]);
194        CLOSE_READER(re, gb);
195
196        return ff_se_golomb_vlc_code[buf];
197    } else {
198        int log = av_log2(buf);
199        LAST_SKIP_BITS(re, gb, 31 - log);
200        UPDATE_CACHE(re, gb);
201        buf = GET_CACHE(re, gb);
202
203        buf >>= log;
204
205        LAST_SKIP_BITS(re, gb, 32 - log);
206        CLOSE_READER(re, gb);
207
208        if (buf & 1)
209            buf = -(buf >> 1);
210        else
211            buf = (buf >> 1);
212
213        return buf;
214    }
215}
216
217static inline int get_se_golomb_long(GetBitContext *gb)
218{
219    unsigned int buf = get_ue_golomb_long(gb);
220
221    if (buf & 1)
222        buf = (buf + 1) >> 1;
223    else
224        buf = -(buf >> 1);
225
226    return buf;
227}
228
229static inline int svq3_get_se_golomb(GetBitContext *gb)
230{
231    unsigned int buf;
232
233    OPEN_READER(re, gb);
234    UPDATE_CACHE(re, gb);
235    buf = GET_CACHE(re, gb);
236
237    if (buf & 0xAA800000) {
238        buf >>= 32 - 8;
239        LAST_SKIP_BITS(re, gb, ff_interleaved_golomb_vlc_len[buf]);
240        CLOSE_READER(re, gb);
241
242        return ff_interleaved_se_golomb_vlc_code[buf];
243    } else {
244        int log;
245        LAST_SKIP_BITS(re, gb, 8);
246        UPDATE_CACHE(re, gb);
247        buf |= 1 | (GET_CACHE(re, gb) >> 8);
248
249        if ((buf & 0xAAAAAAAA) == 0)
250            return INVALID_VLC;
251
252        for (log = 31; (buf & 0x80000000) == 0; log--)
253            buf = (buf << 2) - ((buf << log) >> (log - 1)) + (buf >> 30);
254
255        LAST_SKIP_BITS(re, gb, 63 - 2 * log - 8);
256        CLOSE_READER(re, gb);
257
258        return (signed) (((((buf << log) >> log) - 1) ^ -(buf & 0x1)) + 1) >> 1;
259    }
260}
261
262static inline int dirac_get_se_golomb(GetBitContext *gb)
263{
264    uint32_t ret = svq3_get_ue_golomb(gb);
265
266    if (ret) {
267        uint32_t buf;
268        OPEN_READER(re, gb);
269        UPDATE_CACHE(re, gb);
270        buf = SHOW_SBITS(re, gb, 1);
271        LAST_SKIP_BITS(re, gb, 1);
272        ret = (ret ^ buf) - buf;
273        CLOSE_READER(re, gb);
274    }
275
276    return ret;
277}
278
279/**
280 * read unsigned golomb rice code (ffv1).
281 */
282static inline int get_ur_golomb(GetBitContext *gb, int k, int limit,
283                                int esc_len)
284{
285    unsigned int buf;
286    int log;
287
288    OPEN_READER(re, gb);
289    UPDATE_CACHE(re, gb);
290    buf = GET_CACHE(re, gb);
291
292    log = av_log2(buf);
293
294    if (log > 31 - limit) {
295        buf >>= log - k;
296        buf  += (30 - log) << k;
297        LAST_SKIP_BITS(re, gb, 32 + k - log);
298        CLOSE_READER(re, gb);
299
300        return buf;
301    } else {
302        LAST_SKIP_BITS(re, gb, limit);
303        UPDATE_CACHE(re, gb);
304
305        buf = SHOW_UBITS(re, gb, esc_len);
306
307        LAST_SKIP_BITS(re, gb, esc_len);
308        CLOSE_READER(re, gb);
309
310        return buf + limit - 1;
311    }
312}
313
314/**
315 * read unsigned golomb rice code (jpegls).
316 */
317static inline int get_ur_golomb_jpegls(GetBitContext *gb, int k, int limit,
318                                       int esc_len)
319{
320    unsigned int buf;
321    int log;
322
323    OPEN_READER(re, gb);
324    UPDATE_CACHE(re, gb);
325    buf = GET_CACHE(re, gb);
326
327    log = av_log2(buf);
328
329    if (log - k >= 32 - MIN_CACHE_BITS + (MIN_CACHE_BITS == 32) &&
330        32 - log < limit) {
331        buf >>= log - k;
332        buf  += (30 - log) << k;
333        LAST_SKIP_BITS(re, gb, 32 + k - log);
334        CLOSE_READER(re, gb);
335
336        return buf;
337    } else {
338        int i;
339        for (i = 0; i < limit && SHOW_UBITS(re, gb, 1) == 0; i++) {
340            if (gb->size_in_bits <= re_index)
341                return -1;
342            LAST_SKIP_BITS(re, gb, 1);
343            UPDATE_CACHE(re, gb);
344        }
345        SKIP_BITS(re, gb, 1);
346
347        if (i < limit - 1) {
348            if (k) {
349                buf = SHOW_UBITS(re, gb, k);
350                LAST_SKIP_BITS(re, gb, k);
351            } else {
352                buf = 0;
353            }
354
355            CLOSE_READER(re, gb);
356            return buf + (i << k);
357        } else if (i == limit - 1) {
358            buf = SHOW_UBITS(re, gb, esc_len);
359            LAST_SKIP_BITS(re, gb, esc_len);
360            CLOSE_READER(re, gb);
361
362            return buf + 1;
363        } else
364            return -1;
365    }
366}
367
368/**
369 * read signed golomb rice code (ffv1).
370 */
371static inline int get_sr_golomb(GetBitContext *gb, int k, int limit,
372                                int esc_len)
373{
374    int v = get_ur_golomb(gb, k, limit, esc_len);
375
376    v++;
377    if (v & 1)
378        return v >> 1;
379    else
380        return -(v >> 1);
381
382//    return (v>>1) ^ -(v&1);
383}
384
385/**
386 * read signed golomb rice code (flac).
387 */
388static inline int get_sr_golomb_flac(GetBitContext *gb, int k, int limit,
389                                     int esc_len)
390{
391    int v = get_ur_golomb_jpegls(gb, k, limit, esc_len);
392    return (v >> 1) ^ -(v & 1);
393}
394
395/**
396 * read unsigned golomb rice code (shorten).
397 */
398static inline unsigned int get_ur_golomb_shorten(GetBitContext *gb, int k)
399{
400    return get_ur_golomb_jpegls(gb, k, INT_MAX, 0);
401}
402
403/**
404 * read signed golomb rice code (shorten).
405 */
406static inline int get_sr_golomb_shorten(GetBitContext *gb, int k)
407{
408    int uvar = get_ur_golomb_jpegls(gb, k + 1, INT_MAX, 0);
409    if (uvar & 1)
410        return ~(uvar >> 1);
411    else
412        return uvar >> 1;
413}
414
415#ifdef TRACE
416
417static inline int get_ue(GetBitContext *s, const char *file, const char *func,
418                         int line)
419{
420    int show = show_bits(s, 24);
421    int pos  = get_bits_count(s);
422    int i    = get_ue_golomb(s);
423    int len  = get_bits_count(s) - pos;
424    int bits = show >> (24 - len);
425
426    print_bin(bits, len);
427
428    av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d ue  @%5d in %s %s:%d\n",
429           bits, len, i, pos, file, func, line);
430
431    return i;
432}
433
434static inline int get_se(GetBitContext *s, const char *file, const char *func,
435                         int line)
436{
437    int show = show_bits(s, 24);
438    int pos  = get_bits_count(s);
439    int i    = get_se_golomb(s);
440    int len  = get_bits_count(s) - pos;
441    int bits = show >> (24 - len);
442
443    print_bin(bits, len);
444
445    av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d se  @%5d in %s %s:%d\n",
446           bits, len, i, pos, file, func, line);
447
448    return i;
449}
450
451static inline int get_te(GetBitContext *s, int r, char *file, const char *func,
452                         int line)
453{
454    int show = show_bits(s, 24);
455    int pos  = get_bits_count(s);
456    int i    = get_te0_golomb(s, r);
457    int len  = get_bits_count(s) - pos;
458    int bits = show >> (24 - len);
459
460    print_bin(bits, len);
461
462    av_log(NULL, AV_LOG_DEBUG, "%5d %2d %3d te  @%5d in %s %s:%d\n",
463           bits, len, i, pos, file, func, line);
464
465    return i;
466}
467
468#define get_ue_golomb(a) get_ue(a, __FILE__, __PRETTY_FUNCTION__, __LINE__)
469#define get_se_golomb(a) get_se(a, __FILE__, __PRETTY_FUNCTION__, __LINE__)
470#define get_te_golomb(a, r)  get_te(a, r, __FILE__, __PRETTY_FUNCTION__, __LINE__)
471#define get_te0_golomb(a, r) get_te(a, r, __FILE__, __PRETTY_FUNCTION__, __LINE__)
472
473#endif /* TRACE */
474
475/**
476 * write unsigned exp golomb code.
477 */
478static inline void set_ue_golomb(PutBitContext *pb, int i)
479{
480    av_assert2(i >= 0);
481
482#if 0
483    if (i = 0) {
484        put_bits(pb, 1, 1);
485        return;
486    }
487#endif
488    if (i < 256)
489        put_bits(pb, ff_ue_golomb_len[i], i + 1);
490    else {
491        int e = av_log2(i + 1);
492        put_bits(pb, 2 * e + 1, i + 1);
493    }
494}
495
496/**
497 * write truncated unsigned exp golomb code.
498 */
499static inline void set_te_golomb(PutBitContext *pb, int i, int range)
500{
501    av_assert2(range >= 1);
502    av_assert2(i <= range);
503
504    if (range == 2)
505        put_bits(pb, 1, i ^ 1);
506    else
507        set_ue_golomb(pb, i);
508}
509
510/**
511 * write signed exp golomb code. 16 bits at most.
512 */
513static inline void set_se_golomb(PutBitContext *pb, int i)
514{
515#if 0
516    if (i <= 0)
517        i = -2 * i;
518    else
519        i = 2 * i - 1;
520#elif 1
521    i = 2 * i - 1;
522    if (i < 0)
523        i ^= -1;    //FIXME check if gcc does the right thing
524#else
525    i  = 2 * i - 1;
526    i ^= (i >> 31);
527#endif
528    set_ue_golomb(pb, i);
529}
530
531/**
532 * write unsigned golomb rice code (ffv1).
533 */
534static inline void set_ur_golomb(PutBitContext *pb, int i, int k, int limit,
535                                 int esc_len)
536{
537    int e;
538
539    av_assert2(i >= 0);
540
541    e = i >> k;
542    if (e < limit)
543        put_bits(pb, e + k + 1, (1 << k) + (i & ((1 << k) - 1)));
544    else
545        put_bits(pb, limit + esc_len, i - limit + 1);
546}
547
548/**
549 * write unsigned golomb rice code (jpegls).
550 */
551static inline void set_ur_golomb_jpegls(PutBitContext *pb, int i, int k,
552                                        int limit, int esc_len)
553{
554    int e;
555
556    av_assert2(i >= 0);
557
558    e = (i >> k) + 1;
559    if (e < limit) {
560        while (e > 31) {
561            put_bits(pb, 31, 0);
562            e -= 31;
563        }
564        put_bits(pb, e, 1);
565        if (k)
566            put_sbits(pb, k, i);
567    } else {
568        while (limit > 31) {
569            put_bits(pb, 31, 0);
570            limit -= 31;
571        }
572        put_bits(pb, limit, 1);
573        put_bits(pb, esc_len, i - 1);
574    }
575}
576
577/**
578 * write signed golomb rice code (ffv1).
579 */
580static inline void set_sr_golomb(PutBitContext *pb, int i, int k, int limit,
581                                 int esc_len)
582{
583    int v;
584
585    v  = -2 * i - 1;
586    v ^= (v >> 31);
587
588    set_ur_golomb(pb, v, k, limit, esc_len);
589}
590
591/**
592 * write signed golomb rice code (flac).
593 */
594static inline void set_sr_golomb_flac(PutBitContext *pb, int i, int k,
595                                      int limit, int esc_len)
596{
597    int v;
598
599    v  = -2 * i - 1;
600    v ^= (v >> 31);
601
602    set_ur_golomb_jpegls(pb, v, k, limit, esc_len);
603}
604
605#endif /* AVCODEC_GOLOMB_H */
606