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 // Allow #including this file even if RC_TEMP_BUFFER_SIZE isn't defined.
  28 #ifdef RC_BUFFER_SIZE
  29 typedef struct {
  30         uint64_t low;
  31         uint32_t range;
  32         uint32_t cache_size;
  33         uint8_t cache;
  34         uint8_t buffer[RC_BUFFER_SIZE];
  35         size_t buffer_size;
  36 } lzma_range_encoder;
  37 #endif
  38
  39
  40 /// Makes local copies of range encoder variables.
  41 #define rc_to_local(rc) \
  42         uint64_t rc_low = (rc).low; \
  43         uint32_t rc_range = (rc).range; \
  44         uint32_t rc_cache_size = (rc).cache_size; \
  45         uint8_t rc_cache = (rc).cache; \
  46         uint8_t *rc_buffer = (rc).buffer; \
  47         size_t rc_buffer_size = (rc).buffer_size
  48
  49 /// Stores the local copes back to the range encoder structure.
  50 #define rc_from_local(rc) \
  51 do { \
  52         (rc).low = rc_low; \
  53         (rc).range = rc_range; \
  54         (rc).cache_size = rc_cache_size; \
  55         (rc).cache = rc_cache; \
  56         (rc).buffer_size = rc_buffer_size; \
  57 } while (0)
  58
  59 /// Resets the range encoder structure.
  60 #define rc_reset(rc) \
  61 do { \
  62         (rc).low = 0; \
  63         (rc).range = 0xFFFFFFFF; \
  64         (rc).cache_size = 1; \
  65         (rc).cache = 0; \
  66         (rc).buffer_size = 0; \
  67 } while (0)
  68
  69
  70 //////////////////
  71 // Bit encoding //
  72 //////////////////
  73
  74 // These macros expect that the following variables are defined:
  75 //  - uint64_t  rc_low;
  76 //  - uint32_t  rc_range;
  77 //  - uint8_t   rc_cache;
  78 //  - uint32_t  rc_cache_size;
  79 //  - uint8_t   *out;
  80 //  - size_t    out_pos_local;  // Local copy of *out_pos
  81 //  - size_t    size_out;
  82
  83
  84 // Combined from NRangeCoder::CEncoder::Encode()
  85 // and NRangeCoder::CEncoder::UpdateModel().
  86 #define bit_encode(prob, symbol) \
  87 do { \
  88         probability rc_prob = prob; \
  89         const uint32_t rc_bound \
  90                         = (rc_range >> BIT_MODEL_TOTAL_BITS) * rc_prob; \
  91         if ((symbol) == 0) { \
  92                 rc_range = rc_bound; \
  93                 rc_prob += (BIT_MODEL_TOTAL - rc_prob) >> MOVE_BITS; \
  94         } else { \
  95                 rc_low += rc_bound; \
  96                 rc_range -= rc_bound; \
  97                 rc_prob -= rc_prob >> MOVE_BITS; \
  98         } \
  99         prob = rc_prob; \
 100         rc_normalize(); \
 101 } while (0)
 102
 103
 104 // Optimized version of bit_encode(prob, 0)
 105 #define bit_encode_0(prob) \
 106 do { \
 107         probability rc_prob = prob; \
 108         rc_range = (rc_range >> BIT_MODEL_TOTAL_BITS) * rc_prob; \
 109         rc_prob += (BIT_MODEL_TOTAL - rc_prob) >> MOVE_BITS; \
 110         prob = rc_prob; \
 111         rc_normalize(); \
 112 } while (0)
 113
 114
 115 // Optimized version of bit_encode(prob, 1)
 116 #define bit_encode_1(prob) \
 117 do { \
 118         probability rc_prob = prob; \
 119         const uint32_t rc_bound = (rc_range >> BIT_MODEL_TOTAL_BITS) \
 120                         * rc_prob; \
 121         rc_low += rc_bound; \
 122         rc_range -= rc_bound; \
 123         rc_prob -= rc_prob >> MOVE_BITS; \
 124         prob = rc_prob; \
 125         rc_normalize(); \
 126 } while (0)
 127
 128
 129 ///////////////////////
 130 // Bit tree encoding //
 131 ///////////////////////
 132
 133 #define bittree_encode(probs, bit_levels, symbol) \
 134 do { \
 135         uint32_t model_index = 1; \
 136         for (int32_t bit_index = bit_levels - 1; \
 137                         bit_index >= 0; --bit_index) { \
 138                 const uint32_t bit = ((symbol) >> bit_index) & 1; \
 139                 bit_encode((probs)[model_index], bit); \
 140                 model_index = (model_index << 1) | bit; \
 141         } \
 142 } while (0)
 143
 144
 145 #define bittree_reverse_encode(probs, bit_levels, symbol) \
 146 do { \
 147         uint32_t model_index = 1; \
 148         for (uint32_t bit_index = 0; bit_index < bit_levels; ++bit_index) { \
 149                 const uint32_t bit = ((symbol) >> bit_index) & 1; \
 150                 bit_encode((probs)[model_index], bit); \
 151                 model_index = (model_index << 1) | bit; \
 152         } \
 153 } while (0)
 154
 155
 156 /////////////////
 157 // Direct bits //
 158 /////////////////
 159
 160 #define rc_encode_direct_bits(value, num_total_bits) \
 161 do { \
 162         for (int32_t rc_i = (num_total_bits) - 1; rc_i >= 0; --rc_i) { \
 163                 rc_range >>= 1; \
 164                 if ((((value) >> rc_i) & 1) == 1) \
 165                         rc_low += rc_range; \
 166                 rc_normalize(); \
 167         } \
 168 } while (0)
 169
 170
 171 //////////////////
 172 // Buffer "I/O" //
 173 //////////////////
 174
 175 // Calls rc_shift_low() to write out a byte if needed.
 176 #define rc_normalize() \
 177 do { \
 178         if (rc_range < TOP_VALUE) { \
 179                 rc_range <<= SHIFT_BITS; \
 180                 rc_shift_low(); \
 181         } \
 182 } while (0)
 183
 184
 185 // Flushes all the pending output.
 186 #define rc_flush() \
 187         for (int32_t rc_i = 0; rc_i < 5; ++rc_i) \
 188                 rc_shift_low()
 189
 190
 191 // Writes the compressed data to next_out.
 192 // TODO: Notation change?
 193 //       (uint32_t)(0xFF000000)  =>  ((uint32_t)(0xFF) << TOP_BITS)
 194 // TODO: Another notation change?
 195 //       rc_low = (uint32_t)(rc_low) << SHIFT_BITS;
 196 //       =>
 197 //       rc_low &= TOP_VALUE - 1;
 198 //       rc_low <<= SHIFT_BITS;
 199 #define rc_shift_low() \
 200 do { \
 201         if ((uint32_t)(rc_low) < (uint32_t)(0xFF000000) \
 202                         || (uint32_t)(rc_low >> 32) != 0) { \
 203                 uint8_t rc_temp = rc_cache; \
 204                 do { \
 205                         rc_write_byte(rc_temp + (uint8_t)(rc_low >> 32)); \
 206                         rc_temp = 0xFF; \
 207                 } while(--rc_cache_size != 0); \
 208                 rc_cache = (uint8_t)((uint32_t)(rc_low) >> 24); \
 209         } \
 210         ++rc_cache_size; \
 211         rc_low = (uint32_t)(rc_low) << SHIFT_BITS; \
 212 } while (0)
 213
 214
 215 // Write one byte of compressed data to *next_out. Updates out_pos_local.
 216 // If out_pos_local == out_size, the byte is appended to rc_buffer.
 217 #define rc_write_byte(b) \
 218 do { \
 219         if (out_pos_local == out_size) { \
 220                 rc_buffer[rc_buffer_size++] = (uint8_t)(b); \
 221                 assert(rc_buffer_size < RC_BUFFER_SIZE); \
 222         } else { \
 223                 assert(rc_buffer_size == 0); \
 224                 out[out_pos_local++] = (uint8_t)(b); \
 225         } \
 226 } while (0)
 227
 228
 229 //////////////////
 230 // Price macros //
 231 //////////////////
 232
 233 // These macros expect that the following variables are defined:
 234 //  - uint32_t lzma_rc_prob_prices;
 235
 236 #define bit_get_price(prob, symbol) \
 237         lzma_rc_prob_prices[((((prob) - (symbol)) ^ (-(symbol))) \
 238                         & (BIT_MODEL_TOTAL - 1)) >> MOVE_REDUCING_BITS]
 239
 240
 241 #define bit_get_price_0(prob) \
 242         lzma_rc_prob_prices[(prob) >> MOVE_REDUCING_BITS]
 243
 244
 245 #define bit_get_price_1(prob) \
 246         lzma_rc_prob_prices[(BIT_MODEL_TOTAL - (prob)) >> MOVE_REDUCING_BITS]
 247
 248
 249 // Adds price to price_target. TODO Optimize/Cleanup?
 250 #define bittree_get_price(price_target, probs, bit_levels, symbol) \
 251 do { \
 252         uint32_t bittree_symbol = (symbol) | (UINT32_C(1) << bit_levels); \
 253         while (bittree_symbol != 1) { \
 254                 price_target += bit_get_price((probs)[bittree_symbol >> 1], \
 255                                 bittree_symbol & 1); \
 256                 bittree_symbol >>= 1; \
 257         } \
 258 } while (0)
 259
 260
 261 // Adds price to price_target.
 262 #define bittree_reverse_get_price(price_target, probs, bit_levels, symbol) \
 263 do { \
 264         uint32_t model_index = 1; \
 265         for (uint32_t bit_index = 0; bit_index < bit_levels; ++bit_index) { \
 266                 const uint32_t bit = ((symbol) >> bit_index) & 1; \
 267                 price_target += bit_get_price((probs)[model_index], bit); \
 268                 model_index = (model_index << 1) | bit; \
 269         } \
 270 } while (0)
 271
 272
 273 //////////////////////
 274 // Global variables //
 275 //////////////////////
 276
 277 // Probability prices used by *_get_price() macros. This is initialized
 278 // by lzma_rc_init() and is not modified later.
 279 extern uint32_t lzma_rc_prob_prices[BIT_MODEL_TOTAL >> MOVE_REDUCING_BITS];
 280
 281
 282 ///////////////
 283 // Functions //
 284 ///////////////
 285
 286 /// Initializes lzma_rc_prob_prices[]. This needs to be called only once.
 287 extern void lzma_rc_init(void);
 288
 289
 290 #ifdef RC_BUFFER_SIZE
 291 /// Flushes data from rc->temp[] to out[] as much as possible. If everything
 292 /// cannot be flushed, returns true; false otherwise.
 293 static inline bool
 294 rc_flush_buffer(lzma_range_encoder *rc,
 295                 uint8_t *out, size_t *out_pos, size_t out_size)
 296 {
 297         if (rc->buffer_size > 0) {
 298                 const size_t out_avail = out_size - *out_pos;
 299                 if (rc->buffer_size > out_avail) {
 300                         memcpy(out + *out_pos, rc->buffer, out_avail);
 301                         *out_pos += out_avail;
 302                         rc->buffer_size -= out_avail;
 303                         memmove(rc->buffer, rc->buffer + out_avail,
 304                                         rc->buffer_size);
 305                         return true;
 306                 }
 307
 308                 memcpy(out + *out_pos, rc->buffer, rc->buffer_size);
 309                 *out_pos += rc->buffer_size;
 310                 rc->buffer_size = 0;
 311         }
 312
 313         return false;
 314 }
 315 #endif
 316
 317 #endif