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 } lzma_range_decoder;
  31
  32
  33 /// Makes local copies of range decoder variables.
  34 #define rc_to_local(rc) \
  35         uint32_t rc_range = (rc).range; \
  36         uint32_t rc_code = (rc).code; \
  37         uint32_t rc_bound
  38
  39 /// Stores the local copes back to the range decoder structure.
  40 #define rc_from_local(rc) \
  41 do {\
  42         (rc).range = rc_range; \
  43         (rc).code = rc_code; \
  44 } while (0)
  45
  46 /// Resets the range decoder structure.
  47 #define rc_reset(rc) \
  48 do { \
  49         (rc).range = UINT32_MAX; \
  50         (rc).code = 0; \
  51 } while (0)
  52
  53
  54 // All of the macros in this file expect the following variables being defined:
  55 //  - uint32_t rc_range;
  56 //  - uint32_t rc_code;
  57 //  - uint32_t rc_bound;   // Temporary variable
  58 //  - uint8_t  *in;
  59 //  - size_t   in_pos_local; // Local alias for *in_pos
  60
  61
  62 //////////////////
  63 // Buffer "I/O" //
  64 //////////////////
  65
  66 // Read the next byte of compressed data from buffer_in, if needed.
  67 #define rc_normalize() \
  68 do { \
  69         if (rc_range < TOP_VALUE) { \
  70                 rc_range <<= SHIFT_BITS; \
  71                 rc_code = (rc_code << SHIFT_BITS) | in[in_pos_local++]; \
  72         } \
  73 } while (0)
  74
  75
  76 //////////////////
  77 // Bit decoding //
  78 //////////////////
  79
  80 // Range decoder's DecodeBit() is splitted into three macros:
  81 //    if_bit_0(prob) {
  82 //        update_bit_0(prob)
  83 //        ...
  84 //    } else {
  85 //        update_bit_1(prob)
  86 //        ...
  87 //    }
  88
  89 #define if_bit_0(prob) \
  90         rc_normalize(); \
  91         rc_bound = (rc_range >> BIT_MODEL_TOTAL_BITS) * (prob); \
  92         if (rc_code < rc_bound)
  93
  94
  95 #define update_bit_0(prob) \
  96 do { \
  97         rc_range = rc_bound; \
  98         prob += (BIT_MODEL_TOTAL - (prob)) >> MOVE_BITS; \
  99 } while (0)
 100
 101
 102 #define update_bit_1(prob) \
 103 do { \
 104         rc_range -= rc_bound; \
 105         rc_code -= rc_bound; \
 106         prob -= (prob) >> MOVE_BITS; \
 107 } while (0)
 108
 109
 110 // Dummy versions don't update prob.
 111 #define update_bit_0_dummy() \
 112         rc_range = rc_bound
 113
 114
 115 #define update_bit_1_dummy() \
 116 do { \
 117         rc_range -= rc_bound; \
 118         rc_code -= rc_bound; \
 119 } while (0)
 120
 121
 122 ///////////////////////
 123 // Bit tree decoding //
 124 ///////////////////////
 125
 126 #define bittree_decode(target, probs, bit_levels) \
 127 do { \
 128         uint32_t model_index = 1; \
 129         for (uint32_t bit_index = (bit_levels); bit_index != 0; --bit_index) { \
 130                 if_bit_0((probs)[model_index]) { \
 131                         update_bit_0((probs)[model_index]); \
 132                         model_index <<= 1; \
 133                 } else { \
 134                         update_bit_1((probs)[model_index]); \
 135                         model_index = (model_index << 1) | 1; \
 136                 } \
 137         } \
 138         target += model_index - (1 << bit_levels); \
 139 } while (0)
 140
 141
 142 #define bittree_reverse_decode(target, probs, bit_levels) \
 143 do { \
 144         uint32_t model_index = 1; \
 145         for (uint32_t bit_index = 0; bit_index < bit_levels; ++bit_index) { \
 146                 if_bit_0((probs)[model_index]) { \
 147                         update_bit_0((probs)[model_index]); \
 148                         model_index <<= 1; \
 149                 } else { \
 150                         update_bit_1((probs)[model_index]); \
 151                         model_index = (model_index << 1) | 1; \
 152                         target += 1 << bit_index; \
 153                 } \
 154         } \
 155 } while (0)
 156
 157
 158 // Dummy versions don't update prob.
 159 #define bittree_decode_dummy(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_dummy(); \
 165                         model_index <<= 1; \
 166                 } else { \
 167                         update_bit_1_dummy(); \
 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_dummy(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_dummy(); \
 181                         model_index <<= 1; \
 182                 } else { \
 183                         update_bit_1_dummy(); \
 184                         model_index = (model_index << 1) | 1; \
 185                 } \
 186         } \
 187 } while (0)
 188
 189 #endif