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
20typedef 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.
28static inline bool
29rc_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 false;
35
36		rc->code = (rc->code << 8) | in[*in_pos];
37		++*in_pos;
38		--rc->init_bytes_left;
39	}
40
41	return true;
42}
43
44
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); \
51	uint32_t rc_bound
52
53
54/// Stores the local copes back to the range decoder structure.
55#define rc_from_local(range_decoder, in_pos) \
56do { \
57	range_decoder = rc; \
58	in_pos = rc_in_pos; \
59} while (0)
60
61
62/// Resets the range decoder structure.
63#define rc_reset(range_decoder) \
64do { \
65	(range_decoder).range = UINT32_MAX; \
66	(range_decoder).code = 0; \
67	(range_decoder).init_bytes_left = 5; \
68} while (0)
69
70
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)
76
77
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
80/// decoder loop.
81#define rc_normalize(seq) \
82do { \
83	if (rc.range < RC_TOP_VALUE) { \
84		if (unlikely(rc_in_pos == in_size)) { \
85			coder->sequence = seq; \
86			goto out; \
87		} \
88		rc.range <<= RC_SHIFT_BITS; \
89		rc.code = (rc.code << RC_SHIFT_BITS) | in[rc_in_pos++]; \
90	} \
91} while (0)
92
93
94/// Start decoding a bit. This must be used together with rc_update_0()
95/// and rc_update_1():
96///
97///     rc_if_0(prob, seq) {
98///         rc_update_0(prob);
99///         // Do something
100///     } else {
101///         rc_update_1(prob);
102///         // Do something else
103///     }
104///
105#define rc_if_0(prob, seq) \
106	rc_normalize(seq); \
107	rc_bound = (rc.range >> RC_BIT_MODEL_TOTAL_BITS) * (prob); \
108	if (rc.code < rc_bound)
109
110
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) \
114do { \
115	rc.range = rc_bound; \
116	prob += (RC_BIT_MODEL_TOTAL - (prob)) >> RC_MOVE_BITS; \
117} while (0)
118
119
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) \
123do { \
124	rc.range -= rc_bound; \
125	rc.code -= rc_bound; \
126	prob -= (prob) >> RC_MOVE_BITS; \
127} while (0)
128
129
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
133/// arrays.
134#define rc_bit_last(prob, action0, action1, seq) \
135do { \
136	rc_if_0(prob, seq) { \
137		rc_update_0(prob); \
138		action0; \
139	} else { \
140		rc_update_1(prob); \
141		action1; \
142	} \
143} while (0)
144
145
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) \
149	rc_bit_last(prob, \
150		symbol <<= 1; action0, \
151		symbol = (symbol << 1) + 1; action1, \
152		seq);
153
154
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
159/// obvious.
160#define rc_bit_case(prob, action0, action1, seq) \
161	case seq: rc_bit(prob, action0, action1, seq)
162
163
164/// Decode a bit without using a probability.
165#define rc_direct(dest, seq) \
166do { \
167	rc_normalize(seq); \
168	rc.range >>= 1; \
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); \
173} while (0)
174
175
176// NOTE: No macros are provided for bittree decoding. It seems to be simpler
177// to just write them open in the code.
178
179#endif
180