Class: Omnizip::Algorithms::LZMA::XzPriceCalculator

Inherits:
Object
  • Object
show all
Includes:
Constants
Defined in:
lib/omnizip/algorithms/lzma/xz_price_calculator.rb

Overview

XZ Utils-compatible price calculator

Calculates the cost (in price units) of encoding symbols using probability models. Prices are based on logarithmic probabilities: price = -log2(probability) * scale_factor

Uses precomputed tables for efficiency, matching XZ Utils exactly.

Based on: xz/src/liblzma/rangecoder/price.h

Constant Summary collapse

PRICE_SHIFT_BITS =

Price scale factor (matches XZ Utils)

4
PRICE_SCALE = 
1 << PRICE_SHIFT_BITS
BIT_MODEL_TOTAL_LOCAL =

BIT_MODEL_TOTAL = 2^11 = 2048 (from Constants, but define locally for clarity)

0x800
BIT_MODEL_TOTAL_BITS = 
11
PRICE_TABLE_SIZE =

Number of entries in price table

BIT_MODEL_TOTAL_LOCAL >> PRICE_SHIFT_BITS
PRICE_TABLE =

Precomputed logarithmic price table Each entry represents -log2(i/BIT_MODEL_TOTAL) * PRICE_SCALE

precompute_price_table.freeze

Constants included from Constants

Constants::BIT_MODEL_TOTAL, Constants::COMPRESSION_LEVEL_DEFAULT, Constants::COMPRESSION_LEVEL_MAX, Constants::COMPRESSION_LEVEL_MIN, Constants::DICT_SIZE_MAX, Constants::DICT_SIZE_MIN, Constants::DIST_ALIGN_BITS, Constants::DIST_ALIGN_SIZE, Constants::DIST_SLOT_FAST_LIMIT, Constants::END_POS_MODEL_INDEX, Constants::EOS_MARKER, Constants::INIT_PROBS, Constants::LEN_HIGH_SYMBOLS, Constants::LEN_LOW_SYMBOLS, Constants::LEN_MID_SYMBOLS, Constants::LIT_SIZE_MAX, Constants::MATCH_LEN_MAX, Constants::MATCH_LEN_MIN, Constants::MOVE_BITS, Constants::NUM_DIRECT_BITS, Constants::NUM_DIST_SLOTS, Constants::NUM_DIST_SLOT_BITS, Constants::NUM_FULL_DISTANCES, Constants::NUM_LEN_HIGH_BITS, Constants::NUM_LEN_LOW_BITS, Constants::NUM_LEN_MID_BITS, Constants::NUM_LEN_TO_POS_STATES, Constants::NUM_LIT_CONTEXT_BITS_MAX, Constants::NUM_LIT_POS_BITS_MAX, Constants::NUM_POS_BITS_MAX, Constants::NUM_STATES, Constants::POS_STATES_MAX, Constants::START_POS_MODEL_INDEX, Constants::TOP

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.bit_price(prob, bit) ⇒ Integer

Calculate price for encoding a single bit

Parameters:

  • prob (Integer) —

    Probability model value (0..BIT_MODEL_TOTAL)

  • bit (Integer) —

    Bit value (0 or 1)

Returns:

  • (Integer) —

    Price in price units



35
36
37
38
39
40
41
42
43
 
# File 'lib/omnizip/algorithms/lzma/xz_price_calculator.rb', line 35

def bit_price(prob, bit)
  if bit.zero?
    # Price for encoding 0
    PRICE_TABLE[prob >> PRICE_SHIFT_BITS]
  else
    # Price for encoding 1
    PRICE_TABLE[(BIT_MODEL_TOTAL_LOCAL - prob) >> PRICE_SHIFT_BITS]
  end
end

.bittree_price(probs, num_bits, symbol) ⇒ Integer

Calculate price for encoding a symbol using bit tree

A bit tree encodes a symbol by encoding its bits from MSB to LSB, using probability models indexed by the partial symbol value.

Parameters:

  • probs (Array<BitModel>) —

    Probability models for tree

  • num_bits (Integer) —

    Number of bits in symbol

  • symbol (Integer) —

    Symbol value to encode

Returns:

  • (Integer) —

    Total price in price units



54
55
56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/omnizip/algorithms/lzma/xz_price_calculator.rb', line 54

def bittree_price(probs, num_bits, symbol)
  price = 0
  symbol |= (1 << num_bits) # Add sentinel bit

  # Encode bits from MSB to LSB
  (num_bits - 1).downto(0) do |i|
    bit = (symbol >> i) & 1
    model_idx = symbol >> (i + 1)
    price += bit_price(probs[model_idx].probability, bit)
  end

  price
end

.bittree_reverse_price(probs, num_bits, symbol) ⇒ Integer

Calculate price for encoding a symbol using reverse bit tree

A reverse bit tree encodes a symbol by encoding its bits from LSB to MSB, used for distance encoding.

Parameters:

  • probs (Array<BitModel>) —

    Probability models for tree

  • num_bits (Integer) —

    Number of bits in symbol

  • symbol (Integer) —

    Symbol value to encode

Returns:

  • (Integer) —

    Total price in price units



77
78
79
80
81
82
83
84
85
86
87
88
89
 
# File 'lib/omnizip/algorithms/lzma/xz_price_calculator.rb', line 77

def bittree_reverse_price(probs, num_bits, symbol)
  price = 0
  model_idx = 1

  # Encode bits from LSB to MSB
  num_bits.times do |i|
    bit = (symbol >> i) & 1
    price += bit_price(probs[model_idx].probability, bit)
    model_idx = (model_idx << 1) | bit
  end

  price
end

.direct_price(num_bits) ⇒ Integer

Calculate price for direct bits (uniform distribution)

Direct bits have no probability model, each bit costs the same.

Parameters:

  • num_bits (Integer) —

    Number of direct bits

Returns:

  • (Integer) —

    Total price in price units



97
98
99
100
 
# File 'lib/omnizip/algorithms/lzma/xz_price_calculator.rb', line 97

def direct_price(num_bits)
  # Each direct bit costs 64 units (price of 0.5 probability)
  num_bits << (PRICE_SHIFT_BITS + 2)
end

.precompute_price_table ⇒ Array<Integer>

Precompute logarithmic price table using Math.log2

Generates a table mapping probabilities to prices using the formula: price = -log2(i / BIT_MODEL_TOTAL) * PRICE_SCALE

Returns:

  • (Array<Integer>) —

    Precomputed price table



108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/omnizip/algorithms/lzma/xz_price_calculator.rb', line 108

def precompute_price_table
  table = Array.new(PRICE_TABLE_SIZE)

  PRICE_TABLE_SIZE.times do |i|
    if i.zero?
      # Handle zero probability case (maximum price)
      table[i] = 15 << PRICE_SHIFT_BITS
    else
      # Reconstruct probability from table index
      prob = (i << PRICE_SHIFT_BITS) + (PRICE_SCALE >> 1)
      probability = prob.to_f / BIT_MODEL_TOTAL_LOCAL

      # price = -log2(probability) * PRICE_SCALE
      price = (-Math.log2(probability) * PRICE_SCALE).round
      table[i] = price
    end
  end

  table
end

Instance Method Details

#bit_price(prob, bit) ⇒ Integer

Returns Price.

Parameters:

  • prob (Integer) —

    Probability value

  • bit (Integer) —

    Bit value

Returns:

  • (Integer) —

    Price



139
140
141
 
# File 'lib/omnizip/algorithms/lzma/xz_price_calculator.rb', line 139

def bit_price(prob, bit)
  self.class.bit_price(prob, bit)
end

#bittree_price(probs, num_bits, symbol) ⇒ Integer

Returns Price.

Parameters:

  • probs (Array<BitModel>) —

    Probability models

  • num_bits (Integer) —

    Number of bits

  • symbol (Integer) —

    Symbol value

Returns:

  • (Integer) —

    Price



147
148
149
 
# File 'lib/omnizip/algorithms/lzma/xz_price_calculator.rb', line 147

def bittree_price(probs, num_bits, symbol)
  self.class.bittree_price(probs, num_bits, symbol)
end

#bittree_reverse_price(probs, num_bits, symbol) ⇒ Integer

Returns Price.

Parameters:

  • probs (Array<BitModel>) —

    Probability models

  • num_bits (Integer) —

    Number of bits

  • symbol (Integer) —

    Symbol value

Returns:

  • (Integer) —

    Price



155
156
157
 
# File 'lib/omnizip/algorithms/lzma/xz_price_calculator.rb', line 155

def bittree_reverse_price(probs, num_bits, symbol)
  self.class.bittree_reverse_price(probs, num_bits, symbol)
end

#direct_price(num_bits) ⇒ Integer

Returns Price.

Parameters:

  • num_bits (Integer) —

    Number of direct bits

Returns:

  • (Integer) —

    Price



161
162
163
 
# File 'lib/omnizip/algorithms/lzma/xz_price_calculator.rb', line 161

def direct_price(num_bits)
  self.class.direct_price(num_bits)
end