1207753Smm/////////////////////////////////////////////////////////////////////////////// 2207753Smm// 3207753Smm/// \file range_encoder.h 4207753Smm/// \brief Range Encoder 5207753Smm/// 6207753Smm// Authors: Igor Pavlov 7207753Smm// Lasse Collin 8207753Smm// 9207753Smm// This file has been put into the public domain. 10207753Smm// You can do whatever you want with this file. 11207753Smm// 12207753Smm/////////////////////////////////////////////////////////////////////////////// 13207753Smm 14207753Smm#ifndef LZMA_RANGE_ENCODER_H 15207753Smm#define LZMA_RANGE_ENCODER_H 16207753Smm 17207753Smm#include "range_common.h" 18207753Smm#include "price.h" 19207753Smm 20207753Smm 21207753Smm/// Maximum number of symbols that can be put pending into lzma_range_encoder 22207753Smm/// structure between calls to lzma_rc_encode(). For LZMA, 52+5 is enough 23207753Smm/// (match with big distance and length followed by range encoder flush). 24207753Smm#define RC_SYMBOLS_MAX 58 25207753Smm 26207753Smm 27207753Smmtypedef struct { 28207753Smm uint64_t low; 29207753Smm uint64_t cache_size; 30207753Smm uint32_t range; 31207753Smm uint8_t cache; 32207753Smm 33207753Smm /// Number of symbols in the tables 34207753Smm size_t count; 35207753Smm 36207753Smm /// rc_encode()'s position in the tables 37207753Smm size_t pos; 38207753Smm 39207753Smm /// Symbols to encode 40207753Smm enum { 41207753Smm RC_BIT_0, 42207753Smm RC_BIT_1, 43207753Smm RC_DIRECT_0, 44207753Smm RC_DIRECT_1, 45207753Smm RC_FLUSH, 46207753Smm } symbols[RC_SYMBOLS_MAX]; 47207753Smm 48207753Smm /// Probabilities associated with RC_BIT_0 or RC_BIT_1 49207753Smm probability *probs[RC_SYMBOLS_MAX]; 50207753Smm 51207753Smm} lzma_range_encoder; 52207753Smm 53207753Smm 54207753Smmstatic inline void 55207753Smmrc_reset(lzma_range_encoder *rc) 56207753Smm{ 57207753Smm rc->low = 0; 58207753Smm rc->cache_size = 1; 59207753Smm rc->range = UINT32_MAX; 60207753Smm rc->cache = 0; 61207753Smm rc->count = 0; 62207753Smm rc->pos = 0; 63207753Smm} 64207753Smm 65207753Smm 66207753Smmstatic inline void 67207753Smmrc_bit(lzma_range_encoder *rc, probability *prob, uint32_t bit) 68207753Smm{ 69207753Smm rc->symbols[rc->count] = bit; 70207753Smm rc->probs[rc->count] = prob; 71207753Smm ++rc->count; 72207753Smm} 73207753Smm 74207753Smm 75207753Smmstatic inline void 76207753Smmrc_bittree(lzma_range_encoder *rc, probability *probs, 77207753Smm uint32_t bit_count, uint32_t symbol) 78207753Smm{ 79207753Smm uint32_t model_index = 1; 80207753Smm 81207753Smm do { 82207753Smm const uint32_t bit = (symbol >> --bit_count) & 1; 83207753Smm rc_bit(rc, &probs[model_index], bit); 84207753Smm model_index = (model_index << 1) + bit; 85207753Smm } while (bit_count != 0); 86207753Smm} 87207753Smm 88207753Smm 89207753Smmstatic inline void 90207753Smmrc_bittree_reverse(lzma_range_encoder *rc, probability *probs, 91207753Smm uint32_t bit_count, uint32_t symbol) 92207753Smm{ 93207753Smm uint32_t model_index = 1; 94207753Smm 95207753Smm do { 96207753Smm const uint32_t bit = symbol & 1; 97207753Smm symbol >>= 1; 98207753Smm rc_bit(rc, &probs[model_index], bit); 99207753Smm model_index = (model_index << 1) + bit; 100207753Smm } while (--bit_count != 0); 101207753Smm} 102207753Smm 103207753Smm 104207753Smmstatic inline void 105207753Smmrc_direct(lzma_range_encoder *rc, 106207753Smm uint32_t value, uint32_t bit_count) 107207753Smm{ 108207753Smm do { 109207753Smm rc->symbols[rc->count++] 110207753Smm = RC_DIRECT_0 + ((value >> --bit_count) & 1); 111207753Smm } while (bit_count != 0); 112207753Smm} 113207753Smm 114207753Smm 115207753Smmstatic inline void 116207753Smmrc_flush(lzma_range_encoder *rc) 117207753Smm{ 118207753Smm for (size_t i = 0; i < 5; ++i) 119207753Smm rc->symbols[rc->count++] = RC_FLUSH; 120207753Smm} 121207753Smm 122207753Smm 123207753Smmstatic inline bool 124207753Smmrc_shift_low(lzma_range_encoder *rc, 125207753Smm uint8_t *out, size_t *out_pos, size_t out_size) 126207753Smm{ 127207753Smm if ((uint32_t)(rc->low) < (uint32_t)(0xFF000000) 128207753Smm || (uint32_t)(rc->low >> 32) != 0) { 129207753Smm do { 130207753Smm if (*out_pos == out_size) 131207753Smm return true; 132207753Smm 133207753Smm out[*out_pos] = rc->cache + (uint8_t)(rc->low >> 32); 134207753Smm ++*out_pos; 135207753Smm rc->cache = 0xFF; 136207753Smm 137207753Smm } while (--rc->cache_size != 0); 138207753Smm 139207753Smm rc->cache = (rc->low >> 24) & 0xFF; 140207753Smm } 141207753Smm 142207753Smm ++rc->cache_size; 143207753Smm rc->low = (rc->low & 0x00FFFFFF) << RC_SHIFT_BITS; 144207753Smm 145207753Smm return false; 146207753Smm} 147207753Smm 148207753Smm 149207753Smmstatic inline bool 150207753Smmrc_encode(lzma_range_encoder *rc, 151207753Smm uint8_t *out, size_t *out_pos, size_t out_size) 152207753Smm{ 153207753Smm assert(rc->count <= RC_SYMBOLS_MAX); 154207753Smm 155207753Smm while (rc->pos < rc->count) { 156207753Smm // Normalize 157207753Smm if (rc->range < RC_TOP_VALUE) { 158207753Smm if (rc_shift_low(rc, out, out_pos, out_size)) 159207753Smm return true; 160207753Smm 161207753Smm rc->range <<= RC_SHIFT_BITS; 162207753Smm } 163207753Smm 164207753Smm // Encode a bit 165207753Smm switch (rc->symbols[rc->pos]) { 166207753Smm case RC_BIT_0: { 167207753Smm probability prob = *rc->probs[rc->pos]; 168207753Smm rc->range = (rc->range >> RC_BIT_MODEL_TOTAL_BITS) 169207753Smm * prob; 170207753Smm prob += (RC_BIT_MODEL_TOTAL - prob) >> RC_MOVE_BITS; 171207753Smm *rc->probs[rc->pos] = prob; 172207753Smm break; 173207753Smm } 174207753Smm 175207753Smm case RC_BIT_1: { 176207753Smm probability prob = *rc->probs[rc->pos]; 177207753Smm const uint32_t bound = prob * (rc->range 178207753Smm >> RC_BIT_MODEL_TOTAL_BITS); 179207753Smm rc->low += bound; 180207753Smm rc->range -= bound; 181207753Smm prob -= prob >> RC_MOVE_BITS; 182207753Smm *rc->probs[rc->pos] = prob; 183207753Smm break; 184207753Smm } 185207753Smm 186207753Smm case RC_DIRECT_0: 187207753Smm rc->range >>= 1; 188207753Smm break; 189207753Smm 190207753Smm case RC_DIRECT_1: 191207753Smm rc->range >>= 1; 192207753Smm rc->low += rc->range; 193207753Smm break; 194207753Smm 195207753Smm case RC_FLUSH: 196207753Smm // Prevent further normalizations. 197207753Smm rc->range = UINT32_MAX; 198207753Smm 199207753Smm // Flush the last five bytes (see rc_flush()). 200207753Smm do { 201207753Smm if (rc_shift_low(rc, out, out_pos, out_size)) 202207753Smm return true; 203207753Smm } while (++rc->pos < rc->count); 204207753Smm 205207753Smm // Reset the range encoder so we are ready to continue 206207753Smm // encoding if we weren't finishing the stream. 207207753Smm rc_reset(rc); 208207753Smm return false; 209207753Smm 210207753Smm default: 211207753Smm assert(0); 212207753Smm break; 213207753Smm } 214207753Smm 215207753Smm ++rc->pos; 216207753Smm } 217207753Smm 218207753Smm rc->count = 0; 219207753Smm rc->pos = 0; 220207753Smm 221207753Smm return false; 222207753Smm} 223207753Smm 224207753Smm 225207753Smmstatic inline uint64_t 226207753Smmrc_pending(const lzma_range_encoder *rc) 227207753Smm{ 228207753Smm return rc->cache_size + 5 - 1; 229207753Smm} 230207753Smm 231207753Smm#endif 232