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 static inline bool
  35 rc_read_init(lzma_range_decoder *rc, const uint8_t *restrict in,
  36                 size_t *restrict in_pos, size_t in_size)
  37 {
  38         while (rc->init_bytes_left > 0) {
  39                 if (*in_pos == in_size)
  40                         return false;
  41
  42                 rc->code = (rc->code << 8) | in[*in_pos];
  43                 ++*in_pos;
  44                 --rc->init_bytes_left;
  45         }
  46
  47         return true;
  48 }
  49
  50
  51 /// Makes local copies of range decoder variables.
  52 #define rc_to_local(range_decoder) \
  53         lzma_range_decoder rc = range_decoder; \
  54         uint32_t rc_bound
  55
  56 /// Stores the local copes back to the range decoder structure.
  57 #define rc_from_local(range_decoder) \
  58         range_decoder = rc
  59
  60 /// Resets the range decoder structure.
  61 #define rc_reset(range_decoder) \
  62 do { \
  63         (range_decoder).range = UINT32_MAX; \
  64         (range_decoder).code = 0; \
  65         (range_decoder).init_bytes_left = 5; \
  66 } while (0)
  67
  68
  69 // All of the macros in this file expect the following variables being defined:
  70 //  - lzma_range_decoder range_decoder;
  71 //  - uint32_t rc_bound;   // Temporary variable
  72 //  - uint8_t *in;
  73 //  - size_t in_pos_local; // Local alias for *in_pos
  74
  75
  76 //////////////////
  77 // Buffer "I/O" //
  78 //////////////////
  79
  80 // Read the next byte of compressed data from buffer_in, if needed.
  81 #define rc_normalize() \
  82 do { \
  83         if (rc.range < TOP_VALUE) { \
  84                 rc.range <<= SHIFT_BITS; \
  85                 rc.code = (rc.code << SHIFT_BITS) | in[in_pos_local++]; \
  86         } \
  87 } while (0)
  88
  89
  90 //////////////////
  91 // Bit decoding //
  92 //////////////////
  93
  94 // Range decoder's DecodeBit() is splitted into three macros:
  95 //    if_bit_0(prob) {
  96 //        update_bit_0(prob)
  97 //        ...
  98 //    } else {
  99 //        update_bit_1(prob)
 100 //        ...
 101 //    }
 102
 103 #define if_bit_0(prob) \
 104         rc_normalize(); \
 105         rc_bound = (rc.range >> BIT_MODEL_TOTAL_BITS) * (prob); \
 106         if (rc.code < rc_bound)
 107
 108
 109 #define update_bit_0(prob) \
 110 do { \
 111         rc.range = rc_bound; \
 112         prob += (BIT_MODEL_TOTAL - (prob)) >> MOVE_BITS; \
 113 } while (0)
 114
 115
 116 #define update_bit_1(prob) \
 117 do { \
 118         rc.range -= rc_bound; \
 119         rc.code -= rc_bound; \
 120         prob -= (prob) >> MOVE_BITS; \
 121 } while (0)
 122
 123
 124 #define rc_decode_direct(dest, count) \
 125 do { \
 126         rc_normalize(); \
 127         rc.range >>= 1; \
 128         rc_bound = (rc.code - rc.range) >> 31; \
 129         rc.code -= rc.range & (rc_bound - 1); \
 130         dest = ((dest) << 1) | (1 - rc_bound);\
 131 } while (--count > 0)
 132
 133
 134 // Dummy versions don't update prob or dest.
 135 #define update_bit_0_dummy() \
 136         rc.range = rc_bound
 137
 138
 139 #define update_bit_1_dummy() \
 140 do { \
 141         rc.range -= rc_bound; \
 142         rc.code -= rc_bound; \
 143 } while (0)
 144
 145
 146 #define rc_decode_direct_dummy(count) \
 147 do { \
 148         rc_normalize(); \
 149         rc.range >>= 1; \
 150         rc_bound = (rc.code - rc.range) >> 31; \
 151         rc.code -= rc.range & (rc_bound - 1); \
 152 } while (--count > 0)
 153
 154
 155 ///////////////////////
 156 // Bit tree decoding //
 157 ///////////////////////
 158
 159 #define bittree_decode(target, probs, bit_levels) \
 160 do { \
 161         uint32_t model_index = 1; \
 162         for (uint32_t bit_index = (bit_levels); bit_index != 0; --bit_index) { \
 163                 if_bit_0((probs)[model_index]) { \
 164                         update_bit_0((probs)[model_index]); \
 165                         model_index <<= 1; \
 166                 } else { \
 167                         update_bit_1((probs)[model_index]); \
 168                         model_index = (model_index << 1) | 1; \
 169                 } \
 170         } \
 171         target += model_index - (1 << bit_levels); \
 172 } while (0)
 173
 174
 175 #define bittree_reverse_decode(target, probs, bit_levels) \
 176 do { \
 177         uint32_t model_index = 1; \
 178         for (uint32_t bit_index = 0; bit_index < bit_levels; ++bit_index) { \
 179                 if_bit_0((probs)[model_index]) { \
 180                         update_bit_0((probs)[model_index]); \
 181                         model_index <<= 1; \
 182                 } else { \
 183                         update_bit_1((probs)[model_index]); \
 184                         model_index = (model_index << 1) | 1; \
 185                         target += 1 << bit_index; \
 186                 } \
 187         } \
 188 } while (0)
 189
 190
 191 // Dummy versions don't update prob.
 192 #define bittree_decode_dummy(target, probs, bit_levels) \
 193 do { \
 194         uint32_t model_index = 1; \
 195         for (uint32_t bit_index = (bit_levels); bit_index != 0; --bit_index) { \
 196                 if_bit_0((probs)[model_index]) { \
 197                         update_bit_0_dummy(); \
 198                         model_index <<= 1; \
 199                 } else { \
 200                         update_bit_1_dummy(); \
 201                         model_index = (model_index << 1) | 1; \
 202                 } \
 203         } \
 204         target += model_index - (1 << bit_levels); \
 205 } while (0)
 206
 207
 208 #define bittree_reverse_decode_dummy(probs, bit_levels) \
 209 do { \
 210         uint32_t model_index = 1; \
 211         for (uint32_t bit_index = 0; bit_index < bit_levels; ++bit_index) { \
 212                 if_bit_0((probs)[model_index]) { \
 213                         update_bit_0_dummy(); \
 214                         model_index <<= 1; \
 215                 } else { \
 216                         update_bit_1_dummy(); \
 217                         model_index = (model_index << 1) | 1; \
 218                 } \
 219         } \
 220 } while (0)
 221
 222 #endif