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