1 ///////////////////////////////////////////////////////////////////////////////
2 //
3 /// \file range_decoder.h
4 /// \brief Range Decoder
5 ///
6 // Authors: Igor Pavlov
7 // Lasse Collin
8 //
9 // This file has been put into the public domain.
10 // You can do whatever you want with this file.
11 //
12 ///////////////////////////////////////////////////////////////////////////////
13
14 #ifndef LZMA_RANGE_DECODER_H
15 #define LZMA_RANGE_DECODER_H
16
17 #include "range_common.h"
18
19
20 typedef struct {
21 uint32_t range;
22 uint32_t code;
23 uint32_t init_bytes_left;
24 } lzma_range_decoder;
25
26
27 /// Reads the first five bytes to initialize the range decoder.
28 static inline lzma_ret
29 rc_read_init(lzma_range_decoder *rc, const uint8_t *restrict in,
30 size_t *restrict in_pos, size_t in_size)
31 {
32 while (rc->init_bytes_left > 0) {
33 if (*in_pos == in_size)
34 return LZMA_OK;
35
36 // The first byte is always 0x00. It could have been omitted
37 // in LZMA2 but it wasn't, so one byte is wasted in every
38 // LZMA2 chunk.
39 if (rc->init_bytes_left == 5 && in[*in_pos] != 0x00)
40 return LZMA_DATA_ERROR;
41
42 rc->code = (rc->code << 8) | in[*in_pos];
43 ++*in_pos;
44 --rc->init_bytes_left;
45 }
46
47 return LZMA_STREAM_END;
48 }
49
50
51 /// Makes local copies of range decoder and *in_pos variables. Doing this
52 /// improves speed significantly. The range decoder macros expect also
53 /// variables `in' and `in_size' to be defined.
54 #define rc_to_local(range_decoder, in_pos) \
55 lzma_range_decoder rc = range_decoder; \
56 size_t rc_in_pos = (in_pos); \
57 uint32_t rc_bound
58
59
60 /// Stores the local copes back to the range decoder structure.
61 #define rc_from_local(range_decoder, in_pos) \
62 do { \
63 range_decoder = rc; \
64 in_pos = rc_in_pos; \
65 } while (0)
66
67
68 /// Resets the range decoder structure.
69 #define rc_reset(range_decoder) \
70 do { \
71 (range_decoder).range = UINT32_MAX; \
72 (range_decoder).code = 0; \
73 (range_decoder).init_bytes_left = 5; \
74 } while (0)
75
76
77 /// When decoding has been properly finished, rc.code is always zero unless
78 /// the input stream is corrupt. So checking this can catch some corrupt
79 /// files especially if they don't have any other integrity check.
80 #define rc_is_finished(range_decoder) \
81 ((range_decoder).code == 0)
82
83
84 /// Read the next input byte if needed. If more input is needed but there is
85 /// no more input available, "goto out" is used to jump out of the main
86 /// decoder loop.
87 #define rc_normalize(seq) \
88 do { \
89 if (rc.range < RC_TOP_VALUE) { \
90 if (unlikely(rc_in_pos == in_size)) { \
91 coder->sequence = seq; \
92 goto out; \
93 } \
94 rc.range <<= RC_SHIFT_BITS; \
95 rc.code = (rc.code << RC_SHIFT_BITS) | in[rc_in_pos++]; \
96 } \
97 } while (0)
98
99
100 /// Start decoding a bit. This must be used together with rc_update_0()
101 /// and rc_update_1():
102 ///
103 /// rc_if_0(prob, seq) {
104 /// rc_update_0(prob);
105 /// // Do something
106 /// } else {
107 /// rc_update_1(prob);
108 /// // Do something else
109 /// }
110 ///
111 #define rc_if_0(prob, seq) \
112 rc_normalize(seq); \
113 rc_bound = (rc.range >> RC_BIT_MODEL_TOTAL_BITS) * (prob); \
114 if (rc.code < rc_bound)
115
116
117 /// Update the range decoder state and the used probability variable to
118 /// match a decoded bit of 0.
119 #define rc_update_0(prob) \
120 do { \
121 rc.range = rc_bound; \
122 prob += (RC_BIT_MODEL_TOTAL - (prob)) >> RC_MOVE_BITS; \
123 } while (0)
124
125
126 /// Update the range decoder state and the used probability variable to
127 /// match a decoded bit of 1.
128 #define rc_update_1(prob) \
129 do { \
130 rc.range -= rc_bound; \
131 rc.code -= rc_bound; \
132 prob -= (prob) >> RC_MOVE_BITS; \
133 } while (0)
134
135
136 /// Decodes one bit and runs action0 or action1 depending on the decoded bit.
137 /// This macro is used as the last step in bittree reverse decoders since
138 /// those don't use "symbol" for anything else than indexing the probability
139 /// arrays.
140 #define rc_bit_last(prob, action0, action1, seq) \
141 do { \
142 rc_if_0(prob, seq) { \
143 rc_update_0(prob); \
144 action0; \
145 } else { \
146 rc_update_1(prob); \
147 action1; \
148 } \
149 } while (0)
150
151
152 /// Decodes one bit, updates "symbol", and runs action0 or action1 depending
153 /// on the decoded bit.
154 #define rc_bit(prob, action0, action1, seq) \
155 rc_bit_last(prob, \
156 symbol <<= 1; action0, \
157 symbol = (symbol << 1) + 1; action1, \
158 seq);
159
160
161 /// Like rc_bit() but add "case seq:" as a prefix. This makes the unrolled
162 /// loops more readable because the code isn't littered with "case"
163 /// statements. On the other hand this also makes it less readable, since
164 /// spotting the places where the decoder loop may be restarted is less
165 /// obvious.
166 #define rc_bit_case(prob, action0, action1, seq) \
167 case seq: rc_bit(prob, action0, action1, seq)
168
169
170 /// Decode a bit without using a probability.
171 #define rc_direct(dest, seq) \
172 do { \
173 rc_normalize(seq); \
174 rc.range >>= 1; \
175 rc.code -= rc.range; \
176 rc_bound = UINT32_C(0) - (rc.code >> 31); \
177 rc.code += rc.range & rc_bound; \
178 dest = (dest << 1) + (rc_bound + 1); \
179 } while (0)
180
181
182 // NOTE: No macros are provided for bittree decoding. It seems to be simpler
183 // to just write them open in the code.
184
185 #endif