src/liblzma/rangecoder/range_encoder.h

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       range_encoder.h
   4 /// \brief      Range Encoder
   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_ENCODER_H
  22 #define LZMA_RANGE_ENCODER_H
  23
  24 #include "range_common.h"
  25
  26
  27 typedef struct {
  28         uint64_t low;
  29         uint32_t range;
  30         uint32_t cache_size;
  31         uint8_t cache;
  32 } lzma_range_encoder;
  33
  34
  35 /// Resets the range encoder structure.
  36 #define rc_reset(rc) \
  37 do { \
  38         (rc).low = 0; \
  39         (rc).range = UINT32_MAX; \
  40         (rc).cache_size = 1; \
  41         (rc).cache = 0; \
  42 } while (0)
  43
  44
  45 //////////////////
  46 // Bit encoding //
  47 //////////////////
  48
  49 // These macros expect that the following variables are defined:
  50 //  - lzma_range_encoder rc;
  51 //  - uint8_t *out;
  52 //  - size_t out_pos_local;  // Local copy of *out_pos
  53 //  - size_t size_out;
  54 //
  55 // Macros pointing to these variables are also needed:
  56 //  - uint8_t rc_buffer[]; // Don't use a pointer, must be real array!
  57 //  - size_t rc_buffer_size;
  58
  59
  60 // Combined from NRangeCoder::CEncoder::Encode()
  61 // and NRangeCoder::CEncoder::UpdateModel().
  62 #define bit_encode(prob, symbol) \
  63 do { \
  64         probability rc_prob = prob; \
  65         const uint32_t rc_bound \
  66                         = (rc.range >> BIT_MODEL_TOTAL_BITS) * rc_prob; \
  67         if ((symbol) == 0) { \
  68                 rc.range = rc_bound; \
  69                 rc_prob += (BIT_MODEL_TOTAL - rc_prob) >> MOVE_BITS; \
  70         } else { \
  71                 rc.low += rc_bound; \
  72                 rc.range -= rc_bound; \
  73                 rc_prob -= rc_prob >> MOVE_BITS; \
  74         } \
  75         prob = rc_prob; \
  76         rc_normalize(); \
  77 } while (0)
  78
  79
  80 // Optimized version of bit_encode(prob, 0)
  81 #define bit_encode_0(prob) \
  82 do { \
  83         probability rc_prob = prob; \
  84         rc.range = (rc.range >> BIT_MODEL_TOTAL_BITS) * rc_prob; \
  85         rc_prob += (BIT_MODEL_TOTAL - rc_prob) >> MOVE_BITS; \
  86         prob = rc_prob; \
  87         rc_normalize(); \
  88 } while (0)
  89
  90
  91 // Optimized version of bit_encode(prob, 1)
  92 #define bit_encode_1(prob) \
  93 do { \
  94         probability rc_prob = prob; \
  95         const uint32_t rc_bound = (rc.range >> BIT_MODEL_TOTAL_BITS) \
  96                         * rc_prob; \
  97         rc.low += rc_bound; \
  98         rc.range -= rc_bound; \
  99         rc_prob -= rc_prob >> MOVE_BITS; \
 100         prob = rc_prob; \
 101         rc_normalize(); \
 102 } while (0)
 103
 104
 105 ///////////////////////
 106 // Bit tree encoding //
 107 ///////////////////////
 108
 109 #define bittree_encode(probs, bit_levels, symbol) \
 110 do { \
 111         uint32_t model_index = 1; \
 112         for (int32_t bit_index = bit_levels - 1; \
 113                         bit_index >= 0; --bit_index) { \
 114                 const uint32_t bit = ((symbol) >> bit_index) & 1; \
 115                 bit_encode((probs)[model_index], bit); \
 116                 model_index = (model_index << 1) | bit; \
 117         } \
 118 } while (0)
 119
 120
 121 #define bittree_reverse_encode(probs, bit_levels, symbol) \
 122 do { \
 123         uint32_t model_index = 1; \
 124         for (uint32_t bit_index = 0; bit_index < bit_levels; ++bit_index) { \
 125                 const uint32_t bit = ((symbol) >> bit_index) & 1; \
 126                 bit_encode((probs)[model_index], bit); \
 127                 model_index = (model_index << 1) | bit; \
 128         } \
 129 } while (0)
 130
 131
 132 /////////////////
 133 // Direct bits //
 134 /////////////////
 135
 136 #define rc_encode_direct_bits(value, num_total_bits) \
 137 do { \
 138         for (int32_t rc_i = (num_total_bits) - 1; rc_i >= 0; --rc_i) { \
 139                 rc.range >>= 1; \
 140                 if ((((value) >> rc_i) & 1) == 1) \
 141                         rc.low += rc.range; \
 142                 rc_normalize(); \
 143         } \
 144 } while (0)
 145
 146
 147 //////////////////
 148 // Buffer "I/O" //
 149 //////////////////
 150
 151 // Calls rc_shift_low() to write out a byte if needed.
 152 #define rc_normalize() \
 153 do { \
 154         if (rc.range < TOP_VALUE) { \
 155                 rc.range <<= SHIFT_BITS; \
 156                 rc_shift_low(); \
 157         } \
 158 } while (0)
 159
 160
 161 // Flushes all the pending output.
 162 #define rc_flush() \
 163         for (int32_t rc_i = 0; rc_i < 5; ++rc_i) \
 164                 rc_shift_low()
 165
 166
 167 // Writes the compressed data to next_out.
 168 // TODO: Notation change?
 169 //       (uint32_t)(0xFF000000)  =>  ((uint32_t)(0xFF) << TOP_BITS)
 170 // TODO: Another notation change?
 171 //       rc.low = (uint32_t)(rc.low) << SHIFT_BITS;
 172 //       =>
 173 //       rc.low &= TOP_VALUE - 1;
 174 //       rc.low <<= SHIFT_BITS;
 175 #define rc_shift_low() \
 176 do { \
 177         if ((uint32_t)(rc.low) < (uint32_t)(0xFF000000) \
 178                         || (uint32_t)(rc.low >> 32) != 0) { \
 179                 uint8_t rc_temp = rc.cache; \
 180                 do { \
 181                         rc_write_byte(rc_temp + (uint8_t)(rc.low >> 32)); \
 182                         rc_temp = 0xFF; \
 183                 } while(--rc.cache_size != 0); \
 184                 rc.cache = (uint8_t)((uint32_t)(rc.low) >> 24); \
 185         } \
 186         ++rc.cache_size; \
 187         rc.low = (uint32_t)(rc.low) << SHIFT_BITS; \
 188 } while (0)
 189
 190
 191 // Write one byte of compressed data to *next_out. Updates out_pos_local.
 192 // If out_pos_local == out_size, the byte is appended to rc_buffer.
 193 #define rc_write_byte(b) \
 194 do { \
 195         if (out_pos_local == out_size) { \
 196                 rc_buffer[rc_buffer_size++] = (uint8_t)(b); \
 197                 assert(rc_buffer_size < sizeof(rc_buffer)); \
 198         } else { \
 199                 assert(rc_buffer_size == 0); \
 200                 out[out_pos_local++] = (uint8_t)(b); \
 201         } \
 202 } while (0)
 203
 204
 205 //////////////////
 206 // Price macros //
 207 //////////////////
 208
 209 // These macros expect that the following variables are defined:
 210 //  - uint32_t lzma_rc_prob_prices;
 211
 212 #define bit_get_price(prob, symbol) \
 213         lzma_rc_prob_prices[((((prob) - (symbol)) ^ (-(symbol))) \
 214                         & (BIT_MODEL_TOTAL - 1)) >> MOVE_REDUCING_BITS]
 215
 216
 217 #define bit_get_price_0(prob) \
 218         lzma_rc_prob_prices[(prob) >> MOVE_REDUCING_BITS]
 219
 220
 221 #define bit_get_price_1(prob) \
 222         lzma_rc_prob_prices[(BIT_MODEL_TOTAL - (prob)) >> MOVE_REDUCING_BITS]
 223
 224
 225 // Adds price to price_target. TODO Optimize/Cleanup?
 226 #define bittree_get_price(price_target, probs, bit_levels, symbol) \
 227 do { \
 228         uint32_t bittree_symbol = (symbol) | (UINT32_C(1) << bit_levels); \
 229         while (bittree_symbol != 1) { \
 230                 price_target += bit_get_price((probs)[bittree_symbol >> 1], \
 231                                 bittree_symbol & 1); \
 232                 bittree_symbol >>= 1; \
 233         } \
 234 } while (0)
 235
 236
 237 // Adds price to price_target.
 238 #define bittree_reverse_get_price(price_target, probs, bit_levels, symbol) \
 239 do { \
 240         uint32_t model_index = 1; \
 241         for (uint32_t bit_index = 0; bit_index < bit_levels; ++bit_index) { \
 242                 const uint32_t bit = ((symbol) >> bit_index) & 1; \
 243                 price_target += bit_get_price((probs)[model_index], bit); \
 244                 model_index = (model_index << 1) | bit; \
 245         } \
 246 } while (0)
 247
 248
 249 //////////////////////
 250 // Global variables //
 251 //////////////////////
 252
 253 // Probability prices used by *_get_price() macros. This is initialized
 254 // by lzma_rc_init() and is not modified later.
 255 extern uint32_t lzma_rc_prob_prices[BIT_MODEL_TOTAL >> MOVE_REDUCING_BITS];
 256
 257
 258 ///////////////
 259 // Functions //
 260 ///////////////
 261
 262 /// Initializes lzma_rc_prob_prices[]. This needs to be called only once.
 263 extern void lzma_rc_init(void);
 264
 265
 266 #endif