2 * Lagarith range decoder
3 * Copyright (c) 2009 Nathan Caldwell <saintdev (at) gmail.com>
4 * Copyright (c) 2009 David Conrad
6 * This file is part of Libav.
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.
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.
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
25 * Lagarith range decoder
26 * @author Nathan Caldwell
27 * @author David Conrad
30 #ifndef AVCODEC_LAGARITHRAC_H
31 #define AVCODEC_LAGARITHRAC_H
34 #include "libavutil/common.h"
35 #include "libavutil/intreadwrite.h"
39 typedef struct lag_rac
{
40 AVCodecContext
*avctx
;
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. */
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. */
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. */
54 void ff_lag_rac_init(lag_rac
*l
, GetBitContext
*gb
, int length
);
57 static inline void lag_rac_refill(lag_rac
*l
)
59 while (l
->range
<= 0x800000) {
62 l
->low
|= 0xff & (AV_RB16(l
->bytestream
) >> 1);
63 if (l
->bytestream
< l
->bytestream_end
)
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
73 static inline uint8_t lag_get_rac(lag_rac
*l
)
75 unsigned range_scaled
, low_scaled
, div
;
81 range_scaled
= l
->range
>> l
->scale
;
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]) {
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
94 low_scaled
= FASTDIV(l
->low
- (l
->low
>> 24), div
);
95 shift
-= l
->hash_shift
;
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])
104 l
->range
= range_scaled
* (l
->prob
[val
+ 1] - l
->prob
[val
]);
107 l
->range
-= range_scaled
* l
->prob
[255];
110 l
->low
-= range_scaled
* l
->prob
[val
];
116 #endif /* AVCODEC_LAGARITHRAC_H */