e4f066e445b69978f9d047e80902b2645002f8d6
[libav.git] / libavcodec / lagarithrac.h
1 /*
2 * Lagarith range decoder
3 * Copyright (c) 2009 Nathan Caldwell <saintdev (at) gmail.com>
4 * Copyright (c) 2009 David Conrad
5 *
6 * This file is part of Libav.
7 *
8 * Libav 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 * Libav 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 Libav; 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 * Lagarith range decoder
26 * @author Nathan Caldwell
27 * @author David Conrad
28 */
29
30 #ifndef AVCODEC_LAGARITHRAC_H
31 #define AVCODEC_LAGARITHRAC_H
32
33 #include <stdint.h>
34 #include "libavutil/common.h"
35 #include "libavutil/intreadwrite.h"
36 #include "avcodec.h"
37 #include "get_bits.h"
38
39 typedef struct lag_rac {
40 AVCodecContext *avctx;
41 unsigned low;
42 unsigned range;
43 unsigned scale; /**< Number of bits of precision in range. */
44 unsigned hash_shift; /**< Number of bits to shift to calculate hash for radix search. */
45
46 const uint8_t *bytestream_start; /**< Start of input bytestream. */
47 const uint8_t *bytestream; /**< Current position in input bytestream. */
48 const uint8_t *bytestream_end; /**< End position of input bytestream. */
49
50 uint32_t prob[258]; /**< Table of cumulative probability for each symbol. */
51 uint8_t range_hash[256]; /**< Hash table mapping upper byte to approximate symbol. */
52 } lag_rac;
53
54 void ff_lag_rac_init(lag_rac *l, GetBitContext *gb, int length);
55
56 /* TODO: Optimize */
57 static inline void lag_rac_refill(lag_rac *l)
58 {
59 while (l->range <= 0x800000) {
60 l->low <<= 8;
61 l->range <<= 8;
62 l->low |= 0xff & (AV_RB16(l->bytestream) >> 1);
63 if (l->bytestream < l->bytestream_end)
64 l->bytestream++;
65 }
66 }
67
68 /**
69 * Decode a single byte from the compressed plane described by *l.
70 * @param l pointer to lag_rac for the current plane
71 * @return next byte of decoded data
72 */
73 static inline uint8_t lag_get_rac(lag_rac *l)
74 {
75 unsigned range_scaled, low_scaled, div;
76 int val;
77 uint8_t shift;
78
79 lag_rac_refill(l);
80
81 range_scaled = l->range >> l->scale;
82
83 if (l->low < range_scaled * l->prob[255]) {
84 /* val = 0 is frequent enough to deserve a shortcut */
85 if (l->low < range_scaled * l->prob[1]) {
86 val = 0;
87 } else {
88 /* FIXME __builtin_clz is ~20% faster here, but not allowed in generic code. */
89 shift = 30 - av_log2(range_scaled);
90 div = ((range_scaled << shift) + (1 << 23) - 1) >> 23;
91 /* low>>24 ensures that any cases too big for exact FASTDIV are
92 * under- rather than over-estimated
93 */
94 low_scaled = FASTDIV(l->low - (l->low >> 24), div);
95 shift -= l->hash_shift;
96 shift &= 31;
97 low_scaled = (low_scaled << shift) | (low_scaled >> (32 - shift));
98 /* low_scaled is now a lower bound of low/range_scaled */
99 val = l->range_hash[(uint8_t) low_scaled];
100 while (l->low >= range_scaled * l->prob[val + 1])
101 val++;
102 }
103
104 l->range = range_scaled * (l->prob[val + 1] - l->prob[val]);
105 } else {
106 val = 255;
107 l->range -= range_scaled * l->prob[255];
108 }
109
110 if (!l->range)
111 l->range = 0x80;
112
113 l->low -= range_scaled * l->prob[val];
114
115 return val;
116 }
117
118
119 #endif /* AVCODEC_LAGARITHRAC_H */