1 ///////////////////////////////////////////////////////////////////////////////
3 /// \file range_decoder.h
4 /// \brief Range Decoder
6 // Authors: Igor Pavlov
9 // This file has been put into the public domain.
10 // You can do whatever you want with this file.
12 ///////////////////////////////////////////////////////////////////////////////
14 #ifndef LZMA_RANGE_DECODER_H
15 #define LZMA_RANGE_DECODER_H
17 #include "range_common.h"
23 uint32_t init_bytes_left;
27 /// Reads the first five bytes to initialize the range decoder.
29 rc_read_init(lzma_range_decoder *rc, const uint8_t *restrict in,
30 size_t *restrict in_pos, size_t in_size)
32 while (rc->init_bytes_left > 0) {
33 if (*in_pos == in_size)
36 rc->code = (rc->code << 8) | in[*in_pos];
38 --rc->init_bytes_left;
45 /// Makes local copies of range decoder and *in_pos variables. Doing this
46 /// improves speed significantly. The range decoder macros expect also
47 /// variables `in' and `in_size' to be defined.
48 #define rc_to_local(range_decoder, in_pos) \
49 lzma_range_decoder rc = range_decoder; \
50 size_t rc_in_pos = (in_pos); \
54 /// Stores the local copes back to the range decoder structure.
55 #define rc_from_local(range_decoder, in_pos) \
62 /// Resets the range decoder structure.
63 #define rc_reset(range_decoder) \
65 (range_decoder).range = UINT32_MAX; \
66 (range_decoder).code = 0; \
67 (range_decoder).init_bytes_left = 5; \
71 /// When decoding has been properly finished, rc.code is always zero unless
72 /// the input stream is corrupt. So checking this can catch some corrupt
73 /// files especially if they don't have any other integrity check.
74 #define rc_is_finished(range_decoder) \
75 ((range_decoder).code == 0)
78 /// Read the next input byte if needed. If more input is needed but there is
79 /// no more input available, "goto out" is used to jump out of the main
81 #define rc_normalize(seq) \
83 if (rc.range < RC_TOP_VALUE) { \
84 if (unlikely(rc_in_pos == in_size)) { \
85 coder->sequence = seq; \
88 rc.range <<= RC_SHIFT_BITS; \
89 rc.code = (rc.code << RC_SHIFT_BITS) | in[rc_in_pos++]; \
94 /// Start decoding a bit. This must be used together with rc_update_0()
95 /// and rc_update_1():
97 /// rc_if_0(prob, seq) {
98 /// rc_update_0(prob);
101 /// rc_update_1(prob);
102 /// // Do something else
105 #define rc_if_0(prob, seq) \
107 rc_bound = (rc.range >> RC_BIT_MODEL_TOTAL_BITS) * (prob); \
108 if (rc.code < rc_bound)
111 /// Update the range decoder state and the used probability variable to
112 /// match a decoded bit of 0.
113 #define rc_update_0(prob) \
115 rc.range = rc_bound; \
116 prob += (RC_BIT_MODEL_TOTAL - (prob)) >> RC_MOVE_BITS; \
120 /// Update the range decoder state and the used probability variable to
121 /// match a decoded bit of 1.
122 #define rc_update_1(prob) \
124 rc.range -= rc_bound; \
125 rc.code -= rc_bound; \
126 prob -= (prob) >> RC_MOVE_BITS; \
130 /// Decodes one bit and runs action0 or action1 depending on the decoded bit.
131 /// This macro is used as the last step in bittree reverse decoders since
132 /// those don't use "symbol" for anything else than indexing the probability
134 #define rc_bit_last(prob, action0, action1, seq) \
136 rc_if_0(prob, seq) { \
146 /// Decodes one bit, updates "symbol", and runs action0 or action1 depending
147 /// on the decoded bit.
148 #define rc_bit(prob, action0, action1, seq) \
150 symbol <<= 1; action0, \
151 symbol = (symbol << 1) + 1; action1, \
155 /// Like rc_bit() but add "case seq:" as a prefix. This makes the unrolled
156 /// loops more readable because the code isn't littered with "case"
157 /// statements. On the other hand this also makes it less readable, since
158 /// spotting the places where the decoder loop may be restarted is less
160 #define rc_bit_case(prob, action0, action1, seq) \
161 case seq: rc_bit(prob, action0, action1, seq)
164 /// Decode a bit without using a probability.
165 #define rc_direct(dest, seq) \
169 rc.code -= rc.range; \
170 rc_bound = UINT32_C(0) - (rc.code >> 31); \
171 rc.code += rc.range & rc_bound; \
172 dest = (dest << 1) + (rc_bound + 1); \
176 // NOTE: No macros are provided for bittree decoding. It seems to be simpler
177 // to just write them open in the code.