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