src/liblzma/rangecoder/range_encoder.h

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       range_encoder.h
   4 /// \brief      Range Encoder
   5 ///
   6 //  Authors:    Igor Pavlov
   7 //              Lasse Collin
   8 //
   9 //  This file has been put into the public domain.
  10 //  You can do whatever you want with this file.
  11 //
  12 ///////////////////////////////////////////////////////////////////////////////
  13
  14 #ifndef LZMA_RANGE_ENCODER_H
  15 #define LZMA_RANGE_ENCODER_H
  16
  17 #include "range_common.h"
  18 #include "price.h"
  19
  20
  21 /// Maximum number of symbols that can be put pending into lzma_range_encoder
  22 /// structure between calls to lzma_rc_encode(). For LZMA, 52+5 is enough
  23 /// (match with big distance and length followed by range encoder flush).
  24 #define RC_SYMBOLS_MAX 58
  25
  26
  27 typedef struct {
  28         uint64_t low;
  29         uint64_t cache_size;
  30         uint32_t range;
  31         uint8_t cache;
  32
  33         /// Number of symbols in the tables
  34         size_t count;
  35
  36         /// rc_encode()'s position in the tables
  37         size_t pos;
  38
  39         /// Symbols to encode
  40         enum {
  41                 RC_BIT_0,
  42                 RC_BIT_1,
  43                 RC_DIRECT_0,
  44                 RC_DIRECT_1,
  45                 RC_FLUSH,
  46         } symbols[RC_SYMBOLS_MAX];
  47
  48         /// Probabilities associated with RC_BIT_0 or RC_BIT_1
  49         probability *probs[RC_SYMBOLS_MAX];
  50
  51 } lzma_range_encoder;
  52
  53
  54 static inline void
  55 rc_reset(lzma_range_encoder *rc)
  56 {
  57         rc->low = 0;
  58         rc->cache_size = 1;
  59         rc->range = UINT32_MAX;
  60         rc->cache = 0;
  61         rc->count = 0;
  62         rc->pos = 0;
  63 }
  64
  65
  66 static inline void
  67 rc_bit(lzma_range_encoder *rc, probability *prob, uint32_t bit)
  68 {
  69         rc->symbols[rc->count] = bit;
  70         rc->probs[rc->count] = prob;
  71         ++rc->count;
  72 }
  73
  74
  75 static inline void
  76 rc_bittree(lzma_range_encoder *rc, probability *probs,
  77                 uint32_t bit_count, uint32_t symbol)
  78 {
  79         uint32_t model_index = 1;
  80
  81         do {
  82                 const uint32_t bit = (symbol >> --bit_count) & 1;
  83                 rc_bit(rc, &probs[model_index], bit);
  84                 model_index = (model_index << 1) + bit;
  85         } while (bit_count != 0);
  86 }
  87
  88
  89 static inline void
  90 rc_bittree_reverse(lzma_range_encoder *rc, probability *probs,
  91                 uint32_t bit_count, uint32_t symbol)
  92 {
  93         uint32_t model_index = 1;
  94
  95         do {
  96                 const uint32_t bit = symbol & 1;
  97                 symbol >>= 1;
  98                 rc_bit(rc, &probs[model_index], bit);
  99                 model_index = (model_index << 1) + bit;
 100         } while (--bit_count != 0);
 101 }
 102
 103
 104 static inline void
 105 rc_direct(lzma_range_encoder *rc,
 106                 uint32_t value, uint32_t bit_count)
 107 {
 108         do {
 109                 rc->symbols[rc->count++]
 110                                 = RC_DIRECT_0 + ((value >> --bit_count) & 1);
 111         } while (bit_count != 0);
 112 }
 113
 114
 115 static inline void
 116 rc_flush(lzma_range_encoder *rc)
 117 {
 118         size_t i;
 119         for (i = 0; i < 5; ++i)
 120                 rc->symbols[rc->count++] = RC_FLUSH;
 121 }
 122
 123
 124 static inline bool
 125 rc_shift_low(lzma_range_encoder *rc,
 126                 uint8_t *out, size_t *out_pos, size_t out_size)
 127 {
 128         if ((uint32_t)(rc->low) < (uint32_t)(0xFF000000)
 129                         || (uint32_t)(rc->low >> 32) != 0) {
 130                 do {
 131                         if (*out_pos == out_size)
 132                                 return true;
 133
 134                         out[*out_pos] = rc->cache + (uint8_t)(rc->low >> 32);
 135                         ++*out_pos;
 136                         rc->cache = 0xFF;
 137
 138                 } while (--rc->cache_size != 0);
 139
 140                 rc->cache = (rc->low >> 24) & 0xFF;
 141         }
 142
 143         ++rc->cache_size;
 144         rc->low = (rc->low & 0x00FFFFFF) << RC_SHIFT_BITS;
 145
 146         return false;
 147 }
 148
 149
 150 static inline bool
 151 rc_encode(lzma_range_encoder *rc,
 152                 uint8_t *out, size_t *out_pos, size_t out_size)
 153 {
 154         assert(rc->count <= RC_SYMBOLS_MAX);
 155
 156         while (rc->pos < rc->count) {
 157                 // Normalize
 158                 if (rc->range < RC_TOP_VALUE) {
 159                         if (rc_shift_low(rc, out, out_pos, out_size))
 160                                 return true;
 161
 162                         rc->range <<= RC_SHIFT_BITS;
 163                 }
 164
 165                 // Encode a bit
 166                 switch (rc->symbols[rc->pos]) {
 167                 case RC_BIT_0: {
 168                         probability prob = *rc->probs[rc->pos];
 169                         rc->range = (rc->range >> RC_BIT_MODEL_TOTAL_BITS)
 170                                         * prob;
 171                         prob += (RC_BIT_MODEL_TOTAL - prob) >> RC_MOVE_BITS;
 172                         *rc->probs[rc->pos] = prob;
 173                         break;
 174                 }
 175
 176                 case RC_BIT_1: {
 177                         probability prob = *rc->probs[rc->pos];
 178                         const uint32_t bound = prob * (rc->range
 179                                         >> RC_BIT_MODEL_TOTAL_BITS);
 180                         rc->low += bound;
 181                         rc->range -= bound;
 182                         prob -= prob >> RC_MOVE_BITS;
 183                         *rc->probs[rc->pos] = prob;
 184                         break;
 185                 }
 186
 187                 case RC_DIRECT_0:
 188                         rc->range >>= 1;
 189                         break;
 190
 191                 case RC_DIRECT_1:
 192                         rc->range >>= 1;
 193                         rc->low += rc->range;
 194                         break;
 195
 196                 case RC_FLUSH:
 197                         // Prevent further normalizations.
 198                         rc->range = UINT32_MAX;
 199
 200                         // Flush the last five bytes (see rc_flush()).
 201                         do {
 202                                 if (rc_shift_low(rc, out, out_pos, out_size))
 203                                         return true;
 204                         } while (++rc->pos < rc->count);
 205
 206                         // Reset the range encoder so we are ready to continue
 207                         // encoding if we weren't finishing the stream.
 208                         rc_reset(rc);
 209                         return false;
 210
 211                 default:
 212                         assert(0);
 213                         break;
 214                 }
 215
 216                 ++rc->pos;
 217         }
 218
 219         rc->count = 0;
 220         rc->pos = 0;
 221
 222         return false;
 223 }
 224
 225
 226 static inline uint64_t
 227 rc_pending(const lzma_range_encoder *rc)
 228 {
 229         return rc->cache_size + 5 - 1;
 230 }
 231
 232 #endif