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