Statistics
| Branch: | Revision:

ffmpeg / libavcodec / lagarithrac.h @ 2912e87a

History | View | Annotate | Download (3.75 KB)

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 libavcodec/lagarithrac.h
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 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
    l->low -= range_scaled * l->prob[val];
111

    
112
    return val;
113
}
114

    
115

    
116
#endif /* AVCODEC_LAGARITHRAC_H */