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 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 * 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/intreadwrite.h"
35#include "avcodec.h"
36#include "get_bits.h"
37
38typedef struct lag_rac {
39    AVCodecContext *avctx;
40    unsigned low;
41    unsigned range;
42    unsigned scale;             /**< Number of bits of precision in range. */
43    unsigned hash_shift;        /**< Number of bits to shift to calculate hash for radix search. */
44
45    const uint8_t *bytestream_start;  /**< Start of input bytestream. */
46    const uint8_t *bytestream;        /**< Current position in input bytestream. */
47    const uint8_t *bytestream_end;    /**< End position of input bytestream. */
48
49    int overread;
50#define MAX_OVERREAD 4
51
52    uint32_t prob[258];         /**< Table of cumulative probability for each symbol. */
53    uint8_t  range_hash[1024];   /**< Hash table mapping upper byte to approximate symbol. */
54} lag_rac;
55
56void ff_lag_rac_init(lag_rac *l, GetBitContext *gb, int length);
57
58/* TODO: Optimize */
59static inline void lag_rac_refill(lag_rac *l)
60{
61    while (l->range <= 0x800000) {
62        l->low   <<= 8;
63        l->range <<= 8;
64        l->low |= 0xff & (AV_RB16(l->bytestream) >> 1);
65        if (l->bytestream < l->bytestream_end)
66            l->bytestream++;
67        else
68            l->overread++;
69    }
70}
71
72/**
73 * Decode a single byte from the compressed plane described by *l.
74 * @param l pointer to lag_rac for the current plane
75 * @return next byte of decoded data
76 */
77static inline uint8_t lag_get_rac(lag_rac *l)
78{
79    unsigned range_scaled, low_scaled;
80    int val;
81
82    lag_rac_refill(l);
83
84    range_scaled = l->range >> l->scale;
85
86    if (l->low < range_scaled * l->prob[255]) {
87        /* val = 0 is frequent enough to deserve a shortcut */
88        if (l->low < range_scaled * l->prob[1]) {
89            val = 0;
90        } else {
91            low_scaled = l->low / (range_scaled<<(l->hash_shift));
92
93            val = l->range_hash[low_scaled];
94            while (l->low >= range_scaled * l->prob[val + 1])
95                val++;
96        }
97
98        l->range = range_scaled * (l->prob[val + 1] - l->prob[val]);
99    } else {
100        val = 255;
101        l->range -= range_scaled * l->prob[255];
102    }
103
104    if (!l->range)
105        l->range = 0x80;
106
107    l->low -= range_scaled * l->prob[val];
108
109    return val;
110}
111
112
113#endif /* AVCODEC_LAGARITHRAC_H */
114