1207753Smm/////////////////////////////////////////////////////////////////////////////// 2207753Smm// 3207753Smm/// \file range_decoder.h 4207753Smm/// \brief Range Decoder 5207753Smm/// 6207753Smm// Authors: Igor Pavlov 7207753Smm// Lasse Collin 8207753Smm// 9207753Smm// This file has been put into the public domain. 10207753Smm// You can do whatever you want with this file. 11207753Smm// 12207753Smm/////////////////////////////////////////////////////////////////////////////// 13207753Smm 14207753Smm#ifndef LZMA_RANGE_DECODER_H 15207753Smm#define LZMA_RANGE_DECODER_H 16207753Smm 17207753Smm#include "range_common.h" 18207753Smm 19207753Smm 20207753Smmtypedef struct { 21207753Smm uint32_t range; 22207753Smm uint32_t code; 23207753Smm uint32_t init_bytes_left; 24207753Smm} lzma_range_decoder; 25207753Smm 26207753Smm 27207753Smm/// Reads the first five bytes to initialize the range decoder. 28207753Smmstatic inline bool 29207753Smmrc_read_init(lzma_range_decoder *rc, const uint8_t *restrict in, 30207753Smm size_t *restrict in_pos, size_t in_size) 31207753Smm{ 32207753Smm while (rc->init_bytes_left > 0) { 33207753Smm if (*in_pos == in_size) 34207753Smm return false; 35207753Smm 36207753Smm rc->code = (rc->code << 8) | in[*in_pos]; 37207753Smm ++*in_pos; 38207753Smm --rc->init_bytes_left; 39207753Smm } 40207753Smm 41207753Smm return true; 42207753Smm} 43207753Smm 44207753Smm 45207753Smm/// Makes local copies of range decoder and *in_pos variables. Doing this 46207753Smm/// improves speed significantly. The range decoder macros expect also 47207753Smm/// variables `in' and `in_size' to be defined. 48207753Smm#define rc_to_local(range_decoder, in_pos) \ 49207753Smm lzma_range_decoder rc = range_decoder; \ 50207753Smm size_t rc_in_pos = (in_pos); \ 51207753Smm uint32_t rc_bound 52207753Smm 53207753Smm 54207753Smm/// Stores the local copes back to the range decoder structure. 55207753Smm#define rc_from_local(range_decoder, in_pos) \ 56207753Smmdo { \ 57207753Smm range_decoder = rc; \ 58207753Smm in_pos = rc_in_pos; \ 59207753Smm} while (0) 60207753Smm 61207753Smm 62207753Smm/// Resets the range decoder structure. 63207753Smm#define rc_reset(range_decoder) \ 64207753Smmdo { \ 65207753Smm (range_decoder).range = UINT32_MAX; \ 66207753Smm (range_decoder).code = 0; \ 67207753Smm (range_decoder).init_bytes_left = 5; \ 68207753Smm} while (0) 69207753Smm 70207753Smm 71207753Smm/// When decoding has been properly finished, rc.code is always zero unless 72207753Smm/// the input stream is corrupt. So checking this can catch some corrupt 73207753Smm/// files especially if they don't have any other integrity check. 74207753Smm#define rc_is_finished(range_decoder) \ 75207753Smm ((range_decoder).code == 0) 76207753Smm 77207753Smm 78207753Smm/// Read the next input byte if needed. If more input is needed but there is 79207753Smm/// no more input available, "goto out" is used to jump out of the main 80207753Smm/// decoder loop. 81207753Smm#define rc_normalize(seq) \ 82207753Smmdo { \ 83207753Smm if (rc.range < RC_TOP_VALUE) { \ 84207753Smm if (unlikely(rc_in_pos == in_size)) { \ 85207753Smm coder->sequence = seq; \ 86207753Smm goto out; \ 87207753Smm } \ 88207753Smm rc.range <<= RC_SHIFT_BITS; \ 89207753Smm rc.code = (rc.code << RC_SHIFT_BITS) | in[rc_in_pos++]; \ 90207753Smm } \ 91207753Smm} while (0) 92207753Smm 93207753Smm 94207753Smm/// Start decoding a bit. This must be used together with rc_update_0() 95207753Smm/// and rc_update_1(): 96207753Smm/// 97207753Smm/// rc_if_0(prob, seq) { 98207753Smm/// rc_update_0(prob); 99207753Smm/// // Do something 100207753Smm/// } else { 101207753Smm/// rc_update_1(prob); 102207753Smm/// // Do something else 103207753Smm/// } 104207753Smm/// 105207753Smm#define rc_if_0(prob, seq) \ 106207753Smm rc_normalize(seq); \ 107207753Smm rc_bound = (rc.range >> RC_BIT_MODEL_TOTAL_BITS) * (prob); \ 108207753Smm if (rc.code < rc_bound) 109207753Smm 110207753Smm 111207753Smm/// Update the range decoder state and the used probability variable to 112207753Smm/// match a decoded bit of 0. 113207753Smm#define rc_update_0(prob) \ 114207753Smmdo { \ 115207753Smm rc.range = rc_bound; \ 116207753Smm prob += (RC_BIT_MODEL_TOTAL - (prob)) >> RC_MOVE_BITS; \ 117207753Smm} while (0) 118207753Smm 119207753Smm 120207753Smm/// Update the range decoder state and the used probability variable to 121207753Smm/// match a decoded bit of 1. 122207753Smm#define rc_update_1(prob) \ 123207753Smmdo { \ 124207753Smm rc.range -= rc_bound; \ 125207753Smm rc.code -= rc_bound; \ 126207753Smm prob -= (prob) >> RC_MOVE_BITS; \ 127207753Smm} while (0) 128207753Smm 129207753Smm 130207753Smm/// Decodes one bit and runs action0 or action1 depending on the decoded bit. 131207753Smm/// This macro is used as the last step in bittree reverse decoders since 132207753Smm/// those don't use "symbol" for anything else than indexing the probability 133207753Smm/// arrays. 134207753Smm#define rc_bit_last(prob, action0, action1, seq) \ 135207753Smmdo { \ 136207753Smm rc_if_0(prob, seq) { \ 137207753Smm rc_update_0(prob); \ 138207753Smm action0; \ 139207753Smm } else { \ 140207753Smm rc_update_1(prob); \ 141207753Smm action1; \ 142207753Smm } \ 143207753Smm} while (0) 144207753Smm 145207753Smm 146207753Smm/// Decodes one bit, updates "symbol", and runs action0 or action1 depending 147207753Smm/// on the decoded bit. 148207753Smm#define rc_bit(prob, action0, action1, seq) \ 149207753Smm rc_bit_last(prob, \ 150207753Smm symbol <<= 1; action0, \ 151207753Smm symbol = (symbol << 1) + 1; action1, \ 152207753Smm seq); 153207753Smm 154207753Smm 155207753Smm/// Like rc_bit() but add "case seq:" as a prefix. This makes the unrolled 156207753Smm/// loops more readable because the code isn't littered with "case" 157207753Smm/// statements. On the other hand this also makes it less readable, since 158207753Smm/// spotting the places where the decoder loop may be restarted is less 159207753Smm/// obvious. 160207753Smm#define rc_bit_case(prob, action0, action1, seq) \ 161207753Smm case seq: rc_bit(prob, action0, action1, seq) 162207753Smm 163207753Smm 164207753Smm/// Decode a bit without using a probability. 165207753Smm#define rc_direct(dest, seq) \ 166207753Smmdo { \ 167207753Smm rc_normalize(seq); \ 168207753Smm rc.range >>= 1; \ 169207753Smm rc.code -= rc.range; \ 170207753Smm rc_bound = UINT32_C(0) - (rc.code >> 31); \ 171207753Smm rc.code += rc.range & rc_bound; \ 172207753Smm dest = (dest << 1) + (rc_bound + 1); \ 173207753Smm} while (0) 174207753Smm 175207753Smm 176207753Smm// NOTE: No macros are provided for bittree decoding. It seems to be simpler 177207753Smm// to just write them open in the code. 178207753Smm 179207753Smm#endif 180