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 186