Class: Omnizip::Algorithms::LZMA::RangeEncoder

Inherits:
RangeCoder
  • Object
show all
Defined in:
lib/omnizip/algorithms/lzma/range_encoder.rb

Overview

Range encoder for LZMA compression

This is a direct port of XZ Utils' range encoder implementation for guaranteed byte-for-byte compatibility.

The encoder maintains a range [low, low+range) and subdivides it proportionally based on symbol probabilities.

Constant Summary

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

Instance Attribute Summary

Attributes inherited from RangeCoder

#low, #range

Instance Method Summary collapse

Constructor Details

#initialize(output_stream) ⇒ RangeEncoder

Initialize the range encoder

Parameters:

  • output_stream (IO) —

    The output stream for encoded bytes



40
41
42
43
44
45
 
# File 'lib/omnizip/algorithms/lzma/range_encoder.rb', line 40

def initialize(output_stream)
  super
  @cache = 0
  @cache_size = 1 # XZ Utils initializes to 1, not 0
  @pre_flush_pos = 0
end

Instance Method Details

#bytes_for_decode ⇒ Integer

Return bytes needed for decoding

For LZMA2: returns pre-flush position (excludes 5-byte flush padding) For regular LZMA: returns full output size

Returns:

  • (Integer) —

    Number of bytes decoder will consume



143
144
145
 
# File 'lib/omnizip/algorithms/lzma/range_encoder.rb', line 143

def bytes_for_decode
  @pre_flush_pos || @stream.pos
end

#encode_bit(model, bit) ⇒ void

This method returns an undefined value.

Encode a single bit using a probability model

Ported from XZ Utils rc_encode() - RC_BIT_0 and RC_BIT_1 cases. The key is that normalization happens BEFORE encoding the bit.

IMPORTANT: We must emulate 32-bit unsigned arithmetic by masking after each operation, since Ruby's integers are arbitrary precision.

Parameters:

  • model (BitModel) —

    The probability model for this bit

  • bit (Integer) —

    The bit value (0 or 1)



58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/omnizip/algorithms/lzma/range_encoder.rb', line 58

def encode_bit(model, bit)
  # Normalize BEFORE encoding (matches XZ Utils)
  normalize

  prob = model.probability

  if bit.zero?
    # RC_BIT_0: shrink range to lower portion
    # rc->range = (rc->range >> 11) * prob
    # Emulate 32-bit unsigned multiplication with truncation
    @range = ((@range >> 11) * prob) & 0xFFFFFFFF
  else
    # RC_BIT_1: add bound to low, shrink range to upper portion
    # const uint32_t bound = prob * (rc->range >> 11)
    # rc->low += bound
    # rc->range -= bound
    bound = prob * (@range >> 11)
    @low = (@low + bound) & 0xFFFFFFFFFFFFFFFF # low can grow beyond 32 bits
    @range = (@range - bound) & 0xFFFFFFFF
  end

  # Update probability model based on the bit value
  # This matches the decoder's update behavior (proper OOP symmetry)
  model.update(bit)
end

#encode_direct_bits(value, num_bits) ⇒ void

This method returns an undefined value.

Encode bits directly without using probability model

Used for encoding values with uniform distribution. Emulates 32-bit unsigned arithmetic.

Parameters:

  • value (Integer) —

    The value to encode

  • num_bits (Integer) —

    Number of bits to encode



92
93
94
95
96
97
98
99
 
# File 'lib/omnizip/algorithms/lzma/range_encoder.rb', line 92

def encode_direct_bits(value, num_bits)
  num_bits.downto(1) do |i|
    normalize
    @range = (@range >> 1) & 0xFFFFFFFF
    bit = (value >> (i - 1)) & 1
    @low = (@low + @range) & 0xFFFFFFFFFFFFFFFF if bit == 1
  end
end

#encode_freq(cum_freq, freq, total_freq) ⇒ void

This method returns an undefined value.

Encode a symbol using cumulative frequency range

This is used by PPMd for encoding symbols based on their frequency distribution in the current context.

Parameters:

  • cum_freq (Integer) —

    Cumulative frequency up to this symbol

  • freq (Integer) —

    Frequency of this symbol

  • total_freq (Integer) —

    Total frequency of all symbols in context



110
111
112
113
114
115
116
117
118
 
# File 'lib/omnizip/algorithms/lzma/range_encoder.rb', line 110

def encode_freq(cum_freq, freq, total_freq)
  normalize
  range_freq = @range / total_freq
  low_bound = range_freq * cum_freq
  high_bound = range_freq * (cum_freq + freq)

  @low = (@low + low_bound) & 0xFFFFFFFFFFFFFFFF
  @range = (high_bound - low_bound) & 0xFFFFFFFF
end

#flush ⇒ void

This method returns an undefined value.

Flush remaining bytes to output stream

Ported from XZ Utils rc_flush().



125
126
127
128
129
130
131
132
133
134
135
 
# File 'lib/omnizip/algorithms/lzma/range_encoder.rb', line 125

def flush
  # Store position BEFORE flush for LZMA2 compatibility
  # The decoder only needs bytes up to this point
  @pre_flush_pos = @stream.pos

  # Prevent further normalizations
  @range = 0xFFFFFFFF

  # Flush 5 bytes (see rc_flush() in xz)
  5.times { shift_low }
end