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-2008 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 /// Maximum number of symbols that can be put pending into lzma_range_encoder
  28 /// structure between calls to lzma_rc_encode(). For LZMA, 52+5 is enough
  29 /// (match with big distance and length followed by range encoder flush).
  30 #define RC_SYMBOLS_MAX 58
  31
  32
  33 typedef struct {
  34         uint64_t low;
  35         uint64_t cache_size;
  36         uint32_t range;
  37         uint8_t cache;
  38
  39         /// Number of symbols in the tables
  40         size_t count;
  41
  42         /// rc_encode()'s position in the tables
  43         size_t pos;
  44
  45         /// Symbols to encode
  46         enum {
  47                 RC_BIT_0,
  48                 RC_BIT_1,
  49                 RC_DIRECT_0,
  50                 RC_DIRECT_1,
  51                 RC_FLUSH,
  52         } symbols[RC_SYMBOLS_MAX];
  53
  54         /// Probabilities associated with RC_BIT_0 or RC_BIT_1
  55         probability *probs[RC_SYMBOLS_MAX];
  56
  57 } lzma_range_encoder;
  58
  59
  60 static inline void
  61 rc_reset(lzma_range_encoder *rc)
  62 {
  63         rc->low = 0;
  64         rc->cache_size = 1;
  65         rc->range = UINT32_MAX;
  66         rc->cache = 0;
  67         rc->count = 0;
  68         rc->pos = 0;
  69 }
  70
  71
  72 static inline void
  73 rc_bit(lzma_range_encoder *rc, probability *prob, uint32_t bit)
  74 {
  75         rc->symbols[rc->count] = bit;
  76         rc->probs[rc->count] = prob;
  77         ++rc->count;
  78 }
  79
  80
  81 static inline void
  82 rc_bittree(lzma_range_encoder *rc, probability *probs,
  83                 uint32_t bit_count, uint32_t symbol)
  84 {
  85         uint32_t model_index = 1;
  86
  87         do {
  88                 const uint32_t bit = (symbol >> --bit_count) & 1;
  89                 rc_bit(rc, &probs[model_index], bit);
  90                 model_index = (model_index << 1) | bit;
  91         } while (bit_count != 0);
  92 }
  93
  94
  95 static inline void
  96 rc_bittree_reverse(lzma_range_encoder *rc, probability *probs,
  97                 uint32_t bit_count, uint32_t symbol)
  98 {
  99         uint32_t model_index = 1;
 100
 101         do {
 102                 const uint32_t bit = symbol & 1;
 103                 symbol >>= 1;
 104                 rc_bit(rc, &probs[model_index], bit);
 105                 model_index = (model_index << 1) | bit;
 106         } while (--bit_count != 0);
 107 }
 108
 109
 110 static inline void
 111 rc_direct(lzma_range_encoder *rc,
 112                 uint32_t value, uint32_t bit_count)
 113 {
 114         do {
 115                 rc->symbols[rc->count++]
 116                                 = RC_DIRECT_0 + ((value >> --bit_count) & 1);
 117         } while (bit_count != 0);
 118 }
 119
 120
 121 static inline void
 122 rc_flush(lzma_range_encoder *rc)
 123 {
 124         for (size_t i = 0; i < 5; ++i)
 125                 rc->symbols[rc->count++] = RC_FLUSH;
 126 }
 127
 128
 129 static inline bool
 130 rc_shift_low(lzma_range_encoder *rc,
 131                 uint8_t *out, size_t *out_pos, size_t out_size)
 132 {
 133         if ((uint32_t)(rc->low) < (uint32_t)(0xFF000000)
 134                         || (uint32_t)(rc->low >> 32) != 0) {
 135                 do {
 136                         if (*out_pos == out_size)
 137                                 return true;
 138
 139                         out[*out_pos] = rc->cache + (uint8_t)(rc->low >> 32);
 140                         ++*out_pos;
 141                         rc->cache = 0xFF;
 142
 143                 } while (--rc->cache_size != 0);
 144
 145                 rc->cache = (rc->low >> 24) & 0xFF;
 146         }
 147
 148         ++rc->cache_size;
 149         rc->low = (rc->low & 0x00FFFFFF) << SHIFT_BITS;
 150
 151         return false;
 152 }
 153
 154
 155 static inline bool
 156 rc_encode(lzma_range_encoder *rc,
 157                 uint8_t *out, size_t *out_pos, size_t out_size)
 158 {
 159         while (rc->pos < rc->count) {
 160                 // Normalize
 161                 if (rc->range < TOP_VALUE) {
 162                         if (rc_shift_low(rc, out, out_pos, out_size))
 163                                 return true;
 164
 165                         rc->range <<= SHIFT_BITS;
 166                 }
 167
 168                 // Encode a bit
 169                 switch (rc->symbols[rc->pos]) {
 170                 case RC_BIT_0: {
 171                         probability prob = *rc->probs[rc->pos];
 172                         rc->range = (rc->range >> BIT_MODEL_TOTAL_BITS) * prob;
 173                         prob += (BIT_MODEL_TOTAL - prob) >> MOVE_BITS;
 174                         *rc->probs[rc->pos] = prob;
 175                         break;
 176                 }
 177
 178                 case RC_BIT_1: {
 179                         probability prob = *rc->probs[rc->pos];
 180                         const uint32_t bound = prob
 181                                         * (rc->range >> BIT_MODEL_TOTAL_BITS);
 182                         rc->low += bound;
 183                         rc->range -= bound;
 184                         prob -= prob >> MOVE_BITS;
 185                         *rc->probs[rc->pos] = prob;
 186                         break;
 187                 }
 188
 189                 case RC_DIRECT_0:
 190                         rc->range >>= 1;
 191                         break;
 192
 193                 case RC_DIRECT_1:
 194                         rc->range >>= 1;
 195                         rc->low += rc->range;
 196                         break;
 197
 198                 case RC_FLUSH:
 199                         // Prevent further normalizations.
 200                         rc->range = UINT32_MAX;
 201
 202                         // Flush the last five bytes (see rc_flush()).
 203                         do {
 204                                 if (rc_shift_low(rc, out, out_pos, out_size))
 205                                         return true;
 206                         } while (++rc->pos < rc->count);
 207
 208                         // Reset the range encoder so we are ready to continue
 209                         // encoding if we weren't finishing the stream.
 210                         rc_reset(rc);
 211                         return false;
 212
 213                 default:
 214                         assert(0);
 215                         break;
 216                 }
 217
 218                 ++rc->pos;
 219         }
 220
 221         rc->count = 0;
 222         rc->pos = 0;
 223
 224         return false;
 225 }
 226
 227
 228 static inline uint64_t
 229 rc_pending(const lzma_range_encoder *rc)
 230 {
 231         return rc->cache_size + 5 - 1;
 232 }
 233
 234
 235 ////////////
 236 // Prices //
 237 ////////////
 238
 239 #ifdef HAVE_SMALL
 240 /// Probability prices used by *_get_price() macros. This is initialized
 241 /// by lzma_rc_init() and is not modified later.
 242 extern uint32_t lzma_rc_prob_prices[BIT_MODEL_TOTAL >> MOVE_REDUCING_BITS];
 243
 244 /// Initializes lzma_rc_prob_prices[]. This needs to be called only once.
 245 extern void lzma_rc_init(void);
 246
 247 #else
 248 // Not building a size optimized version, so we use a precomputed
 249 // constant table.
 250 extern const uint32_t
 251 lzma_rc_prob_prices[BIT_MODEL_TOTAL >> MOVE_REDUCING_BITS];
 252
 253 #endif
 254
 255
 256 #define bit_get_price(prob, symbol) \
 257         lzma_rc_prob_prices[((((prob) - (symbol)) ^ (-(symbol))) \
 258                         & (BIT_MODEL_TOTAL - 1)) >> MOVE_REDUCING_BITS]
 259
 260
 261 #define bit_get_price_0(prob) \
 262         lzma_rc_prob_prices[(prob) >> MOVE_REDUCING_BITS]
 263
 264
 265 #define bit_get_price_1(prob) \
 266         lzma_rc_prob_prices[(BIT_MODEL_TOTAL - (prob)) >> MOVE_REDUCING_BITS]
 267
 268
 269 static inline uint32_t
 270 bittree_get_price(const probability *probs,
 271                 uint32_t bit_levels, uint32_t symbol)
 272 {
 273         uint32_t price = 0;
 274         symbol |= UINT32_C(1) << bit_levels;
 275
 276         do {
 277                 price += bit_get_price(probs[symbol >> 1], symbol & 1);
 278                 symbol >>= 1;
 279         } while (symbol != 1);
 280
 281         return price;
 282 }
 283
 284
 285 static inline uint32_t
 286 bittree_reverse_get_price(const probability *probs,
 287                 uint32_t bit_levels, uint32_t symbol)
 288 {
 289         uint32_t price = 0;
 290         uint32_t model_index = 1;
 291
 292         do {
 293                 const uint32_t bit = symbol & 1;
 294                 symbol >>= 1;
 295                 price += bit_get_price(probs[model_index], bit);
 296                 model_index = (model_index << 1) | bit;
 297         } while (--bit_levels != 0);
 298
 299         return price;
 300 }
 301
 302 #endif