range_encoder.h File Reference

Range Encoder. More...

#include "range_common.h"
#include "price.h"

Go to the source code of this file.

Classes
struct	lzma_range_encoder

Macros
#define	RC_SYMBOLS_MAX   58

Functions
static void	rc_reset (lzma_range_encoder *rc)
static void	rc_bit (lzma_range_encoder *rc, probability *prob, uint32_t bit)
static void	rc_bittree (lzma_range_encoder *rc, probability *probs, uint32_t bit_count, uint32_t symbol)
static void	rc_bittree_reverse (lzma_range_encoder *rc, probability *probs, uint32_t bit_count, uint32_t symbol)
static void	rc_direct (lzma_range_encoder *rc, uint32_t value, uint32_t bit_count)
static void	rc_flush (lzma_range_encoder *rc)
static bool	rc_shift_low (lzma_range_encoder *rc, uint8_t *out, size_t *out_pos, size_t out_size)
static bool	rc_encode (lzma_range_encoder *rc, uint8_t *out, size_t *out_pos, size_t out_size)
static uint64_t	rc_pending (const lzma_range_encoder *rc)

Detailed Description

Range Encoder.

Definition in file range_encoder.h.

Macro Definition Documentation

RC_SYMBOLS_MAX

#define RC_SYMBOLS_MAX   58

Maximum number of symbols that can be put pending into lzma_range_encoder structure between calls to lzma_rc_encode(). For LZMA, 52+5 is enough (match with big distance and length followed by range encoder flush).

Definition at line 24 of file range_encoder.h.

Function Documentation

rc_bit()

static void rc_bit ( lzma_range_encoder *  rc, probability *  prob, uint32_t  bit  )

inlinestatic

Definition at line 67 of file range_encoder.h.

{
    rc->symbols[rc->count] = bit;
    rc->probs[rc->count] = prob;
    ++rc->count;
}

References bit, lzma_range_encoder::count, lzma_range_encoder::probs, and lzma_range_encoder::symbols.

Referenced by rc_bittree(), and rc_bittree_reverse().

rc_bittree()

static void rc_bittree ( lzma_range_encoder *  rc, probability *  probs, uint32_t  bit_count, uint32_t  symbol  )

inlinestatic

Definition at line 76 of file range_encoder.h.

{
    uint32_t model_index = 1;
 
    do {
        const uint32_t bit = (symbol >> --bit_count) & 1;
        rc_bit(rc, &probs[model_index], bit);
        model_index = (model_index << 1) + bit;
    } while (bit_count != 0);
}

References bit, and rc_bit().

Referenced by encode_init(), length(), literal(), and match().

rc_bittree_reverse()

static void rc_bittree_reverse ( lzma_range_encoder *  rc, probability *  probs, uint32_t  bit_count, uint32_t  symbol  )

inlinestatic

Definition at line 90 of file range_encoder.h.

{
    uint32_t model_index = 1;
 
    do {
        const uint32_t bit = symbol & 1;
        symbol >>= 1;
        rc_bit(rc, &probs[model_index], bit);
        model_index = (model_index << 1) + bit;
    } while (--bit_count != 0);
}

References bit, and rc_bit().

Referenced by match().

rc_direct()

static void rc_direct ( lzma_range_encoder *  rc, uint32_t  value, uint32_t  bit_count  )

inlinestatic

Definition at line 105 of file range_encoder.h.

{
    do {
        rc->symbols[rc->count++]
                = RC_DIRECT_0 + ((value >> --bit_count) & 1);
    } while (bit_count != 0);
}

References lzma_range_encoder::count, lzma_range_encoder::symbols, and value.

rc_encode()

static bool rc_encode ( lzma_range_encoder *  rc, uint8_t *  out, size_t *  out_pos, size_t  out_size  )

inlinestatic

Definition at line 150 of file range_encoder.h.

{
    assert(rc->count <= RC_SYMBOLS_MAX);
 
    while (rc->pos < rc->count) {
        // Normalize
        if (rc->range < RC_TOP_VALUE) {
            if (rc_shift_low(rc, out, out_pos, out_size))
                return true;
 
            rc->range <<= RC_SHIFT_BITS;
        }
 
        // Encode a bit
        switch (rc->symbols[rc->pos]) {
        case RC_BIT_0: {
            probability prob = *rc->probs[rc->pos];
            rc->range = (rc->range >> RC_BIT_MODEL_TOTAL_BITS)
                    * prob;
            prob += (RC_BIT_MODEL_TOTAL - prob) >> RC_MOVE_BITS;
            *rc->probs[rc->pos] = prob;
            break;
        }
 
        case RC_BIT_1: {
            probability prob = *rc->probs[rc->pos];
            const uint32_t bound = prob * (rc->range
                    >> RC_BIT_MODEL_TOTAL_BITS);
            rc->low += bound;
            rc->range -= bound;
            prob -= prob >> RC_MOVE_BITS;
            *rc->probs[rc->pos] = prob;
            break;
        }
 
        case RC_DIRECT_0:
            rc->range >>= 1;
            break;
 
        case RC_DIRECT_1:
            rc->range >>= 1;
            rc->low += rc->range;
            break;
 
        case RC_FLUSH:
            // Prevent further normalizations.
            rc->range = UINT32_MAX;
 
            // Flush the last five bytes (see rc_flush()).
            do {
                if (rc_shift_low(rc, out, out_pos, out_size))
                    return true;
            } while (++rc->pos < rc->count);
 
            // Reset the range encoder so we are ready to continue
            // encoding if we weren't finishing the stream.
            rc_reset(rc);
            return false;
 
        default:
            assert(0);
            break;
        }
 
        ++rc->pos;
    }
 
    rc->count = 0;
    rc->pos = 0;
 
    return false;
}

References assert(), lzma_range_encoder::count, lzma_range_encoder::low, out, out_pos, lzma_range_encoder::pos, lzma_range_encoder::probs, lzma_range_encoder::range, RC_BIT_MODEL_TOTAL, RC_BIT_MODEL_TOTAL_BITS, RC_MOVE_BITS, rc_reset(), RC_SHIFT_BITS, rc_shift_low(), RC_SYMBOLS_MAX, RC_TOP_VALUE, lzma_range_encoder::symbols, and UINT32_MAX.

Referenced by lzma_lzma_encode().

rc_flush()

static void rc_flush ( lzma_range_encoder *  rc )

inlinestatic

Definition at line 116 of file range_encoder.h.

{
    for (size_t i = 0; i < 5; ++i)
        rc->symbols[rc->count++] = RC_FLUSH;
}

References lzma_range_encoder::count, i, and lzma_range_encoder::symbols.

Referenced by lzma_lzma_encode().

rc_pending()

static uint64_t rc_pending ( const lzma_range_encoder *  rc )

inlinestatic

Definition at line 226 of file range_encoder.h.

{
    return rc->cache_size + 5 - 1;
}

References lzma_range_encoder::cache_size.

Referenced by lzma_lzma_encode().

rc_reset()

static void rc_reset ( lzma_range_encoder *  rc )

inlinestatic

Definition at line 55 of file range_encoder.h.

{
    rc->low = 0;
    rc->cache_size = 1;
    rc->range = UINT32_MAX;
    rc->cache = 0;
    rc->count = 0;
    rc->pos = 0;
}

References lzma_range_encoder::cache, lzma_range_encoder::cache_size, lzma_range_encoder::count, lzma_range_encoder::low, lzma_range_encoder::pos, lzma_range_encoder::range, and UINT32_MAX.

Referenced by rc_encode().

rc_shift_low()

static bool rc_shift_low ( lzma_range_encoder *  rc, uint8_t *  out, size_t *  out_pos, size_t  out_size  )

inlinestatic

Definition at line 124 of file range_encoder.h.

{
    if ((uint32_t)(rc->low) < (uint32_t)(0xFF000000)
            || (uint32_t)(rc->low >> 32) != 0) {
        do {
            if (*out_pos == out_size)
                return true;
 
            out[*out_pos] = rc->cache + (uint8_t)(rc->low >> 32);
            ++*out_pos;
            rc->cache = 0xFF;
 
        } while (--rc->cache_size != 0);
 
        rc->cache = (rc->low >> 24) & 0xFF;
    }
 
    ++rc->cache_size;
    rc->low = (rc->low & 0x00FFFFFF) << RC_SHIFT_BITS;
 
    return false;
}

References lzma_range_encoder::cache, lzma_range_encoder::cache_size, lzma_range_encoder::low, out, out_pos, and RC_SHIFT_BITS.

Referenced by rc_encode().