contrib/xz/src/liblzma/rangecoder/range_decoder.h

   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 bool
  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 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) \
  56 do { \
  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) \
  64 do { \
  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) \
  82 do { \
  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) \
 114 do { \
 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) \
 123 do { \
 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) \
 135 do { \
 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) \
 166 do { \
 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