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 for (size_t i = 0; i < 5; ++i) 119 rc->symbols[rc->count++] = RC_FLUSH; 120 } 121 122 123 static inline bool 124 rc_shift_low(lzma_range_encoder *rc, 125 uint8_t *out, size_t *out_pos, size_t out_size) 126 { 127 if ((uint32_t)(rc->low) < (uint32_t)(0xFF000000) 128 || (uint32_t)(rc->low >> 32) != 0) { 129 do { 130 if (*out_pos == out_size) 131 return true; 132 133 out[*out_pos] = rc->cache + (uint8_t)(rc->low >> 32); 134 ++*out_pos; 135 rc->cache = 0xFF; 136 137 } while (--rc->cache_size != 0); 138 139 rc->cache = (rc->low >> 24) & 0xFF; 140 } 141 142 ++rc->cache_size; 143 rc->low = (rc->low & 0x00FFFFFF) << RC_SHIFT_BITS; 144 145 return false; 146 } 147 148 149 static inline bool 150 rc_encode(lzma_range_encoder *rc, 151 uint8_t *out, size_t *out_pos, size_t out_size) 152 { 153 assert(rc->count <= RC_SYMBOLS_MAX); 154 155 while (rc->pos < rc->count) { 156 // Normalize 157 if (rc->range < RC_TOP_VALUE) { 158 if (rc_shift_low(rc, out, out_pos, out_size)) 159 return true; 160 161 rc->range <<= RC_SHIFT_BITS; 162 } 163 164 // Encode a bit 165 switch (rc->symbols[rc->pos]) { 166 case RC_BIT_0: { 167 probability prob = *rc->probs[rc->pos]; 168 rc->range = (rc->range >> RC_BIT_MODEL_TOTAL_BITS) 169 * prob; 170 prob += (RC_BIT_MODEL_TOTAL - prob) >> RC_MOVE_BITS; 171 *rc->probs[rc->pos] = prob; 172 break; 173 } 174 175 case RC_BIT_1: { 176 probability prob = *rc->probs[rc->pos]; 177 const uint32_t bound = prob * (rc->range 178 >> RC_BIT_MODEL_TOTAL_BITS); 179 rc->low += bound; 180 rc->range -= bound; 181 prob -= prob >> RC_MOVE_BITS; 182 *rc->probs[rc->pos] = prob; 183 break; 184 } 185 186 case RC_DIRECT_0: 187 rc->range >>= 1; 188 break; 189 190 case RC_DIRECT_1: 191 rc->range >>= 1; 192 rc->low += rc->range; 193 break; 194 195 case RC_FLUSH: 196 // Prevent further normalizations. 197 rc->range = UINT32_MAX; 198 199 // Flush the last five bytes (see rc_flush()). 200 do { 201 if (rc_shift_low(rc, out, out_pos, out_size)) 202 return true; 203 } while (++rc->pos < rc->count); 204 205 // Reset the range encoder so we are ready to continue 206 // encoding if we weren't finishing the stream. 207 rc_reset(rc); 208 return false; 209 210 default: 211 assert(0); 212 break; 213 } 214 215 ++rc->pos; 216 } 217 218 rc->count = 0; 219 rc->pos = 0; 220 221 return false; 222 } 223 224 225 static inline uint64_t 226 rc_pending(const lzma_range_encoder *rc) 227 { 228 return rc->cache_size + 5 - 1; 229 } 230 231 #endif 232