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