Class: Omnizip::Algorithms::LZMA::RangeDecoder

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

Overview

Range decoder for LZMA decompression

This class implements the decoding side of arithmetic coding using integer range arithmetic. It decodes bits from the compressed byte stream based on their probability models.

The decoder mirrors the encoder's range subdivisions to extract the original bit values. It maintains a code value that represents the current position within the range.

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 collapse

Attributes inherited from RangeCoder

#low

Instance Method Summary collapse

Constructor Details

#initialize(input_stream) ⇒ RangeDecoder

Initialize the range decoder

Parameters:

  • input_stream (IO) —

    The input stream of encoded bytes



41
42
43
44
45
46
47
 
# File 'lib/omnizip/algorithms/lzma/range_decoder.rb', line 41

def initialize(input_stream)
  super
  @code = 0
  @initialization_complete = false
  @init_bytes_remaining = 5
  init_decoder
end

Instance Attribute Details

#code ⇒ Object (readonly)

Returns the value of attribute code.



36
37
38
 
# File 'lib/omnizip/algorithms/lzma/range_decoder.rb', line 36

def code
  @code
end

#init_bytes_remaining ⇒ Object (readonly)

Returns the value of attribute init_bytes_remaining.



36
37
38
 
# File 'lib/omnizip/algorithms/lzma/range_decoder.rb', line 36

def init_bytes_remaining
  @init_bytes_remaining
end

#range ⇒ Object (readonly)

Returns the value of attribute range.



36
37
38
 
# File 'lib/omnizip/algorithms/lzma/range_decoder.rb', line 36

def range
  @range
end

#stream ⇒ Object (readonly)

Returns the value of attribute stream.



36
37
38
 
# File 'lib/omnizip/algorithms/lzma/range_decoder.rb', line 36

def stream
  @stream
end

Instance Method Details

#decode_bit(model) ⇒ Integer

Decode a single bit using a probability model

This is the hottest method (~5 billion calls for a 600MB file). normalize() and model.update() are inlined to eliminate method dispatch.

Parameters:

  • model (BitModel) —

    The probability model for this bit

Returns:

  • (Integer) —

    The decoded bit value (0 or 1)



64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
# File 'lib/omnizip/algorithms/lzma/range_decoder.rb', line 64

def decode_bit(model)
  # Inline normalize: only the hot path (range < TOP check)
  # Init bytes are handled eagerly in reset(), not here
  if @range < 0x01000000
    @range <<= 8
    byte = @stream.getbyte
    if byte.nil?
      raise Omnizip::DecompressionError,
            "Truncated LZMA stream during range decoder normalization"
    end

    @code = ((@code << 8) | byte) & 0xFFFFFFFF
  end

  prob = model.probability
  bound = (@range >> 11) * prob

  if @code < bound
    @range = bound
    # Inline model.update(0): prob += (2048 - prob) >> 5
    model.probability = prob + ((2048 - prob) >> 5)
    0
  else
    @code -= bound
    @range -= bound
    # Inline model.update(1): prob -= prob >> 5
    model.probability = prob - (prob >> 5)
    1
  end
end

#decode_direct_bits(num_bits) ⇒ Integer

Decode bits directly without using probability model

Parameters:

  • num_bits (Integer) —

    Number of bits to decode

Returns:

  • (Integer) —

    The decoded value



99
100
101
102
103
104
105
106
107
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/range_decoder.rb', line 99

def decode_direct_bits(num_bits)
  result = 0

  num_bits.downto(1) do |_i|
    # Inline normalize
    if @range < 0x01000000
      @range <<= 8
      byte = @stream.getbyte
      if byte.nil?
        raise Omnizip::DecompressionError,
              "Truncated LZMA stream during range decoder normalization"
      end

      @code = ((@code << 8) | byte) & 0xFFFFFFFF
    end
    @range >>= 1

    bit = @code >= @range ? 1 : 0

    if bit == 1
      @code -= @range
      result = (result << 1) | 1
    else
      result = (result << 1) | 0
    end
  end

  result
end

#decode_direct_bits_with_base(num_bits, base) ⇒ Integer

Decode bits directly using a base value (XZ Utils rc_direct pattern)

Parameters:

  • num_bits (Integer) —

    Number of bits to decode

  • base (Integer) —

    Base value to start from (2 or 3 for distances)

Returns:

  • (Integer) —

    The decoded value



159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
 
# File 'lib/omnizip/algorithms/lzma/range_decoder.rb', line 159

def decode_direct_bits_with_base(num_bits, base)
  result = base
  num_bits.times do |_i|
    result = (result << 1) + 1
    # Inline normalize
    if @range < 0x01000000
      @range <<= 8
      byte = @stream.getbyte
      if byte.nil?
        raise Omnizip::DecompressionError,
              "Truncated LZMA stream during range decoder normalization"
      end

      @code = ((@code << 8) | byte) & 0xFFFFFFFF
    end
    @range >>= 1

    bit = @code >= @range ? 1 : 0

    if bit == 1
      @code -= @range
    else
      result -= 1
    end
  end
  result
end

#decode_freq(total_freq) ⇒ Integer

Decode a cumulative frequency value (PPMd)

Parameters:

  • total_freq (Integer) —

    Total frequency of all symbols in context

Returns:

  • (Integer) —

    The cumulative frequency value



133
134
135
136
137
 
# File 'lib/omnizip/algorithms/lzma/range_decoder.rb', line 133

def decode_freq(total_freq)
  normalize
  range_freq = @range / total_freq
  @code / range_freq
end

#normalize ⇒ void

This method returns an undefined value.

Normalize the range when it becomes too small

Still needed for decode_freq() and other non-hot paths. The hot-path methods inline normalize directly.



222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
 
# File 'lib/omnizip/algorithms/lzma/range_decoder.rb', line 222

def normalize
  # Handle lazy initialization if needed (for non-hot paths)
  if @init_bytes_remaining.positive?
    while @init_bytes_remaining.positive?
      byte = @stream.getbyte
      if byte.nil?
        raise Omnizip::DecompressionError,
              "Truncated LZMA stream during range decoder initialization"
      end

      @code = ((@code << 8) | byte) & 0xFFFFFFFF
      @init_bytes_remaining -= 1
    end
  end

  if @range < TOP
    byte = read_byte
    @range <<= 8
    @code = ((@code << 8) | byte) & 0xFFFFFFFF
  end
end

#normalize_freq(cum_freq, freq, total_freq) ⇒ void

This method returns an undefined value.

Normalize after decoding a symbol with frequency

Parameters:

  • cum_freq (Integer) —

    Cumulative frequency of decoded symbol

  • freq (Integer) —

    Frequency of decoded symbol

  • total_freq (Integer) —

    Total frequency of all symbols



145
146
147
148
149
150
151
152
 
# File 'lib/omnizip/algorithms/lzma/range_decoder.rb', line 145

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

  @code -= low_bound
  @range = (high_bound - low_bound) & 0xFFFFFFFF
end

#read_init_bytes ⇒ void

This method returns an undefined value.

Eagerly read the 5 initialization bytes from the current stream. Must be called after the stream is set to the correct input.



203
204
205
206
207
208
209
210
211
212
213
214
 
# File 'lib/omnizip/algorithms/lzma/range_decoder.rb', line 203

def read_init_bytes
  while @init_bytes_remaining.positive?
    byte = @stream.getbyte
    if byte.nil?
      raise Omnizip::DecompressionError,
            "Truncated LZMA stream during range decoder initialization"
    end

    @code = ((@code << 8) | byte) & 0xFFFFFFFF
    @init_bytes_remaining -= 1
  end
end

#reset ⇒ void

This method returns an undefined value.

Reset the range decoder for a new chunk

Resets state only. Call read_init_bytes after the stream is set to the correct input.



193
194
195
196
197
 
# File 'lib/omnizip/algorithms/lzma/range_decoder.rb', line 193

def reset
  @range = 0xFFFFFFFF
  @code = 0
  @init_bytes_remaining = 5
end

#update_stream(new_stream) ⇒ void

This method returns an undefined value.

Update the input stream (for LZMA2 multi-chunk streams)

Parameters:

  • new_stream (IO) —

    New input stream



53
54
55
 
# File 'lib/omnizip/algorithms/lzma/range_decoder.rb', line 53

def update_stream(new_stream)
  @stream = new_stream
end