1 ///////////////////////////////////////////////////////////////////////////////
3 /// \file range_decoder.h
4 /// \brief Range Decoder
6 // Copyright (C) 1999-2006 Igor Pavlov
7 // Copyright (C) 2007 Lasse Collin
9 // This library is free software; you can redistribute it and/or
10 // modify it under the terms of the GNU Lesser General Public
11 // License as published by the Free Software Foundation; either
12 // version 2.1 of the License, or (at your option) any later version.
14 // This library is distributed in the hope that it will be useful,
15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 // Lesser General Public License for more details.
19 ///////////////////////////////////////////////////////////////////////////////
21 #ifndef LZMA_RANGE_DECODER_H
22 #define LZMA_RANGE_DECODER_H
24 #include "range_common.h"
30 uint32_t init_bytes_left;
34 /// Reads the first five bytes to initialize the range decoder.
36 rc_read_init(lzma_range_decoder *rc, const uint8_t *restrict in,
37 size_t *restrict in_pos, size_t in_size)
39 while (rc->init_bytes_left > 0) {
40 if (*in_pos == in_size)
43 rc->code = (rc->code << 8) | in[*in_pos];
45 --rc->init_bytes_left;
52 /// Makes local copies of range decoder and *in_pos variables. Doing this
53 /// improves speed significantly. The range decoder macros expect also
54 /// variables `in' and `in_size' to be defined.
55 #define rc_to_local(range_decoder, in_pos) \
56 lzma_range_decoder rc = range_decoder; \
57 size_t rc_in_pos = (in_pos); \
61 /// Stores the local copes back to the range decoder structure.
62 #define rc_from_local(range_decoder, in_pos) \
69 /// Resets the range decoder structure.
70 #define rc_reset(range_decoder) \
72 (range_decoder).range = UINT32_MAX; \
73 (range_decoder).code = 0; \
74 (range_decoder).init_bytes_left = 5; \
78 /// When decoding has been properly finished, rc.code is always zero unless
79 /// the input stream is corrupt. So checking this can catch some corrupt
80 /// files especially if they don't have any other integrity check.
81 #define rc_is_finished(range_decoder) \
82 ((range_decoder).code == 0)
85 /// Read the next input byte if needed. If more input is needed but there is
86 /// no more input available, "goto out" is used to jump out of the main
88 #define rc_normalize(seq) \
90 if (rc.range < RC_TOP_VALUE) { \
91 if (unlikely(rc_in_pos == in_size)) { \
92 coder->sequence = seq; \
95 rc.range <<= RC_SHIFT_BITS; \
96 rc.code = (rc.code << RC_SHIFT_BITS) | in[rc_in_pos++]; \
101 /// Start decoding a bit. This must be used together with rc_update_0()
102 /// and rc_update_1():
104 /// rc_if_0(prob, seq) {
105 /// rc_update_0(prob);
108 /// rc_update_1(prob);
109 /// // Do something else
112 #define rc_if_0(prob, seq) \
114 rc_bound = (rc.range >> RC_BIT_MODEL_TOTAL_BITS) * (prob); \
115 if (rc.code < rc_bound)
118 /// Update the range decoder state and the used probability variable to
119 /// match a decoded bit of 0.
120 #define rc_update_0(prob) \
122 rc.range = rc_bound; \
123 prob += (RC_BIT_MODEL_TOTAL - (prob)) >> RC_MOVE_BITS; \
127 /// Update the range decoder state and the used probability variable to
128 /// match a decoded bit of 1.
129 #define rc_update_1(prob) \
131 rc.range -= rc_bound; \
132 rc.code -= rc_bound; \
133 prob -= (prob) >> RC_MOVE_BITS; \
137 /// Decodes one bit and runs action0 or action1 depending on the decoded bit.
138 /// This macro is used as the last step in bittree reverse decoders since
139 /// those don't use "symbol" for anything else than indexing the probability
141 #define rc_bit_last(prob, action0, action1, seq) \
143 rc_if_0(prob, seq) { \
153 /// Decodes one bit, updates "symbol", and runs action0 or action1 depending
154 /// on the decoded bit.
155 #define rc_bit(prob, action0, action1, seq) \
157 symbol <<= 1; action0, \
158 symbol = (symbol << 1) + 1; action1, \
162 /// Like rc_bit() but add "case seq:" as a prefix. This makes the unrolled
163 /// loops more readable because the code isn't littered with "case"
164 /// statements. On the other hand this also makes it less readable, since
165 /// spotting the places where the decoder loop may be restarted is less
167 #define rc_bit_case(prob, action0, action1, seq) \
168 case seq: rc_bit(prob, action0, action1, seq)
171 /// Decode a bit without using a probability.
172 #define rc_direct(dest, seq) \
176 rc.code -= rc.range; \
177 rc_bound = UINT32_C(0) - (rc.code >> 31); \
178 rc.code += rc.range & rc_bound; \
179 dest = (dest << 1) + (rc_bound + 1); \
183 // NOTE: No macros are provided for bittree decoding. It seems to be simpler
184 // to just write them open in the code.