Class: Omnizip::Algorithms::LZMA::XZRangeEncoder

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

Overview

Range Encoder ported from XZ Utils range_encoder.c

This class implements binary range coding, which is the core compression algorithm for LZMA. Range coding is a form of arithmetic coding that encodes bits into a compressed bitstream using probability models.

The encoder maintains a range [low, low+range) and narrows this range as bits are encoded. When the range becomes too small, it is normalized and output bytes are produced.

Ported from XZ Utils liblzma/range_encoder.c

Constant Summary collapse

TOP_VALUE = 
1 << 24
SHIFT_BITS = 
8
BIT_MODEL_TOTAL_BITS = 
11
BIT_MODEL_TOTAL = 
1 << BIT_MODEL_TOTAL_BITS

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(output) ⇒ XZRangeEncoder

Initialize a new range encoder

Parameters:

  • output (IO) —

    Output stream for compressed data



49
50
51
52
53
54
55
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder.rb', line 49

def initialize(output)
  @output = output
  @low = 0
  @range = 0xFFFFFFFF
  @cache = 0
  @cache_size = 1
end

Instance Attribute Details

#cache ⇒ Object (readonly)

Returns the value of attribute cache.



44
45
46
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder.rb', line 44

def cache
  @cache
end

#low ⇒ Object (readonly)

Returns the value of attribute low.



44
45
46
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder.rb', line 44

def low
  @low
end

#range ⇒ Object (readonly)

Returns the value of attribute range.



44
45
46
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder.rb', line 44

def range
  @range
end

Instance Method Details

#encode_bit(model, bit) ⇒ void

This method returns an undefined value.

Encode a single bit using probability model

This method encodes a bit (0 or 1) using an adaptive probability model. The probability model is updated after encoding to adapt to the input data statistics.

Ported from XZ Utils range_encoder.c rc_bit()

Parameters:

  • model (BitModel) —

    Probability model for this bit

  • bit (Integer) —

    Bit value to encode (0 or 1)



68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder.rb', line 68

def encode_bit(model, bit)
  prob = model.probability
  bound = (@range >> BIT_MODEL_TOTAL_BITS) * prob

  if bit.zero?
    @range = bound
  else
    @low += bound
    @range -= bound
  end

  normalize! if @range < TOP_VALUE

  # Update probability model based on bit value
  # Matches decoder behavior (proper OOP symmetry)
  model.update(bit)
end

#encode_bittree(models, num_bits, value) ⇒ void

This method returns an undefined value.

Encode multiple bits as a bittree

A bittree is a binary tree where each node has a probability model. This method encodes a value by traversing the tree from the root, encoding the bit at each node and following the corresponding branch.

Ported from XZ Utils range_encoder.c rc_bittree()

Parameters:

  • models (Array<BitModel>) —

    Array of probability models for tree nodes

  • num_bits (Integer) —

    Number of bits to encode

  • value (Integer) —

    Value to encode



98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder.rb', line 98

def encode_bittree(models, num_bits, value)
  index = 1
  bit = num_bits - 1

  while bit >= 0
    bit_value = (value >> bit) & 1
    encode_bit(models[index - 1], bit_value)
    index = (index << 1) | bit_value
    bit -= 1
  end
end

#encode_bittree_reverse(models, num_bits, value) ⇒ void

This method returns an undefined value.

Encode multiple bits as a reverse bittree

Similar to encode_bittree but processes bits in reverse order. This is used for certain LZMA encoding operations.

Ported from XZ Utils range_encoder.c rc_bittree_reverse()

Parameters:

  • models (Array<BitModel>) —

    Array of probability models for tree nodes

  • num_bits (Integer) —

    Number of bits to encode

  • value (Integer) —

    Value to encode



121
122
123
124
125
126
127
128
129
130
131
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder.rb', line 121

def encode_bittree_reverse(models, num_bits, value)
  index = 1
  bit = 0

  while bit < num_bits
    bit_value = (value >> bit) & 1
    encode_bit(models[index - 1], bit_value)
    index = (index << 1) | bit_value
    bit += 1
  end
end

#encode_direct(value) ⇒ void

This method returns an undefined value.

Encode a direct bit (without probability model)

This method encodes a bit with fixed 0.5 probability. Used for encoding values where no adaptive model is available.

Ported from XZ Utils range_encoder.c rc_direct()

Parameters:

  • value (Integer) —

    Value to encode (0 or 1)



142
143
144
145
146
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder.rb', line 142

def encode_direct(value)
  @range >>= 1
  @low += @range if value != 0
  normalize! if @range < TOP_VALUE
end

#flush! ⇒ void

This method returns an undefined value.

Flush pending data to output stream

This method flushes any remaining data in the range encoder to the output stream. This must be called before the encoder is discarded.

Ported from XZ Utils range_encoder.c rc_flush()



157
158
159
160
161
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder.rb', line 157

def flush!
  (5 - @cache_size).times do
    shift_low
  end
end