src/liblzma/rangecoder/range_decoder.h

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       range_decoder.h
   4 /// \brief      Range Decoder
   5 //
   6 //  Copyright (C) 1999-2006 Igor Pavlov
   7 //  Copyright (C) 2007 Lasse Collin
   8 //
   9 //  This library is free software; you can redistribute it and/or
  10 //  modify it under the terms of the GNU Lesser General Public
  11 //  License as published by the Free Software Foundation; either
  12 //  version 2.1 of the License, or (at your option) any later version.
  13 //
  14 //  This library is distributed in the hope that it will be useful,
  15 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17 //  Lesser General Public License for more details.
  18 //
  19 ///////////////////////////////////////////////////////////////////////////////
  20
  21 #ifndef LZMA_RANGE_DECODER_H
  22 #define LZMA_RANGE_DECODER_H
  23
  24 #include "range_common.h"
  25
  26
  27 typedef struct {
  28         uint32_t range;
  29         uint32_t code;
  30         uint32_t init_bytes_left;
  31 } lzma_range_decoder;
  32
  33
  34 /// Reads the first five bytes to initialize the range decoder.
  35 static inline bool
  36 rc_read_init(lzma_range_decoder *rc, const uint8_t *restrict in,
  37                 size_t *restrict in_pos, size_t in_size)
  38 {
  39         while (rc->init_bytes_left > 0) {
  40                 if (*in_pos == in_size)
  41                         return false;
  42
  43                 rc->code = (rc->code << 8) | in[*in_pos];
  44                 ++*in_pos;
  45                 --rc->init_bytes_left;
  46         }
  47
  48         return true;
  49 }
  50
  51
  52 /// Makes local copies of range decoder and *in_pos variables. Doing this
  53 /// improves speed significantly. The range decoder macros expect also
  54 /// variables `in' and `in_size' to be defined.
  55 #define rc_to_local(range_decoder, in_pos) \
  56         lzma_range_decoder rc = range_decoder; \
  57         size_t rc_in_pos = (in_pos); \
  58         uint32_t rc_bound
  59
  60
  61 /// Stores the local copes back to the range decoder structure.
  62 #define rc_from_local(range_decoder, in_pos) \
  63 do { \
  64         range_decoder = rc; \
  65         in_pos = rc_in_pos; \
  66 } while (0)
  67
  68
  69 /// Resets the range decoder structure.
  70 #define rc_reset(range_decoder) \
  71 do { \
  72         (range_decoder).range = UINT32_MAX; \
  73         (range_decoder).code = 0; \
  74         (range_decoder).init_bytes_left = 5; \
  75 } while (0)
  76
  77
  78 /// When decoding has been properly finished, rc.code is always zero unless
  79 /// the input stream is corrupt. So checking this can catch some corrupt
  80 /// files especially if they don't have any other integrity check.
  81 #define rc_is_finished(range_decoder) \
  82         ((range_decoder).code == 0)
  83
  84
  85 /// Read the next input byte if needed. If more input is needed but there is
  86 /// no more input available, "goto out" is used to jump out of the main
  87 /// decoder loop.
  88 #define rc_normalize(seq) \
  89 do { \
  90         if (rc.range < RC_TOP_VALUE) { \
  91                 if (unlikely(rc_in_pos == in_size)) { \
  92                         coder->sequence = seq; \
  93                         goto out; \
  94                 } \
  95                 rc.range <<= RC_SHIFT_BITS; \
  96                 rc.code = (rc.code << RC_SHIFT_BITS) | in[rc_in_pos++]; \
  97         } \
  98 } while (0)
  99
 100
 101 /// Start decoding a bit. This must be used together with rc_update_0()
 102 /// and rc_update_1():
 103 ///
 104 ///     rc_if_0(prob, seq) {
 105 ///         rc_update_0(prob);
 106 ///         // Do something
 107 ///     } else {
 108 ///         rc_update_1(prob);
 109 ///         // Do something else
 110 ///     }
 111 ///
 112 #define rc_if_0(prob, seq) \
 113         rc_normalize(seq); \
 114         rc_bound = (rc.range >> RC_BIT_MODEL_TOTAL_BITS) * (prob); \
 115         if (rc.code < rc_bound)
 116
 117
 118 /// Update the range decoder state and the used probability variable to
 119 /// match a decoded bit of 0.
 120 #define rc_update_0(prob) \
 121 do { \
 122         rc.range = rc_bound; \
 123         prob += (RC_BIT_MODEL_TOTAL - (prob)) >> RC_MOVE_BITS; \
 124 } while (0)
 125
 126
 127 /// Update the range decoder state and the used probability variable to
 128 /// match a decoded bit of 1.
 129 #define rc_update_1(prob) \
 130 do { \
 131         rc.range -= rc_bound; \
 132         rc.code -= rc_bound; \
 133         prob -= (prob) >> RC_MOVE_BITS; \
 134 } while (0)
 135
 136
 137 /// Decodes one bit and runs action0 or action1 depending on the decoded bit.
 138 /// This macro is used as the last step in bittree reverse decoders since
 139 /// those don't use "symbol" for anything else than indexing the probability
 140 /// arrays.
 141 #define rc_bit_last(prob, action0, action1, seq) \
 142 do { \
 143         rc_if_0(prob, seq) { \
 144                 rc_update_0(prob); \
 145                 action0; \
 146         } else { \
 147                 rc_update_1(prob); \
 148                 action1; \
 149         } \
 150 } while (0)
 151
 152
 153 /// Decodes one bit, updates "symbol", and runs action0 or action1 depending
 154 /// on the decoded bit.
 155 #define rc_bit(prob, action0, action1, seq) \
 156         rc_bit_last(prob, \
 157                 symbol <<= 1; action0, \
 158                 symbol = (symbol << 1) + 1; action1, \
 159                 seq);
 160
 161
 162 /// Like rc_bit() but add "case seq:" as a prefix. This makes the unrolled
 163 /// loops more readable because the code isn't littered with "case"
 164 /// statements. On the other hand this also makes it less readable, since
 165 /// spotting the places where the decoder loop may be restarted is less
 166 /// obvious.
 167 #define rc_bit_case(prob, action0, action1, seq) \
 168         case seq: rc_bit(prob, action0, action1, seq)
 169
 170
 171 /// Decode a bit without using a probability.
 172 #define rc_direct(dest, seq) \
 173 do { \
 174         rc_normalize(seq); \
 175         rc.range >>= 1; \
 176         rc.code -= rc.range; \
 177         rc_bound = UINT32_C(0) - (rc.code >> 31); \
 178         rc.code += rc.range & rc_bound; \
 179         dest = (dest << 1) + (rc_bound + 1); \
 180 } while (0)
 181
 182
 183 // NOTE: No macros are provided for bittree decoding. It seems to be simpler
 184 // to just write them open in the code.
 185
 186 #endif