Class: Omnizip::Algorithms::LZMA::XzBufferedRangeEncoder

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

Overview

XZ Utils-compatible buffered range encoder

This encoder queues symbols for deferred encoding, matching XZ Utils' architecture. This enables:

  • Price calculation without actual encoding
  • Optimal parsing with lookahead
  • Output size limiting for LZMA2

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

Defined Under Namespace

Classes: Probability, SymbolEntry

Constant Summary collapse

RC_BIT_0 =

Symbol types (matching XZ Utils enum)

:bit_0
RC_BIT_1 = 
:bit_1
RC_DIRECT_0 = 
:direct_0
RC_DIRECT_1 = 
:direct_1
RC_FLUSH = 
:flush
RC_SYMBOLS_MAX =

Maximum symbols that can be queued

53

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, #range

Instance Method Summary collapse

Constructor Details

#initialize(output_stream) ⇒ XzBufferedRangeEncoder

Initialize buffered range encoder

Parameters:

  • output_stream (IO) —

    The output stream for encoded bytes



68
69
70
71
72
73
74
75
76
77
78
79
 
# File 'lib/omnizip/algorithms/lzma/xz_buffered_range_encoder.rb', line 68

def initialize(output_stream)
  super
  @cache = 0
  @cache_size = 1 # XZ starts with 1, not 0
  @out_total = 0

  # Symbol queue
  @symbols = []
  @probs = []
  @count = 0
  @pos = 0
end

Instance Attribute Details

#count ⇒ Object (readonly)

Returns the value of attribute count.



56
57
58
 
# File 'lib/omnizip/algorithms/lzma/xz_buffered_range_encoder.rb', line 56

def count
  @count
end

#out_total ⇒ Object (readonly)

Returns the value of attribute out_total.



56
57
58
 
# File 'lib/omnizip/algorithms/lzma/xz_buffered_range_encoder.rb', line 56

def out_total
  @out_total
end

Instance Method Details

#bytes_for_decode ⇒ Integer

Return bytes needed for decoding

Returns:

  • (Integer) —

    Number of bytes decoder will consume



61
62
63
 
# File 'lib/omnizip/algorithms/lzma/xz_buffered_range_encoder.rb', line 61

def bytes_for_decode
  @out_total
end

#encode_symbols(out, out_pos, out_size) ⇒ Boolean

Encode all queued symbols to output

Parameters:

  • out (IO, String) —

    Output buffer

  • out_pos (Integer) —

    Current output position

  • out_size (Integer) —

    Output buffer size

Returns:

  • (Boolean) —

    True if output buffer filled before encoding complete



139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
 
# File 'lib/omnizip/algorithms/lzma/xz_buffered_range_encoder.rb', line 139

def encode_symbols(out, out_pos, out_size)
  while @pos < @count
    symbol = @symbols[@pos]

    # Check if this is a flush symbol BEFORE normalization
    is_flush = (symbol == RC_FLUSH)

    # Normalize if range too small (skip during flush mode)
    # Important: normalization may need multiple iterations and buffer fills
    while @range < TOP && !is_flush
      # Try to write a byte
      if shift_low_buffered(out, out_pos, out_size)
        # Buffer full - update range anyway so we make progress on next call
        @range <<= 8
        return true
      end

      # Successfully shifted, update range
      @range <<= 8
    end

    # Track whether we should increment @pos after the case statement
    increment_pos = true

    # Encode current symbol
    case symbol
    when RC_BIT_0
      prob = @probs[@pos]
      bound = (@range >> 11) * prob.value

      @range = bound
      # XZ Utils inline probability update for bit=0
      prob.value += (BIT_MODEL_TOTAL - prob.value) >> MOVE_BITS
    when RC_BIT_1
      prob = @probs[@pos]
      bound = (@range >> 11) * prob.value

      @low += bound
      @range -= bound
      # XZ Utils inline probability update for bit=1
      prob.value -= prob.value >> MOVE_BITS
    when RC_DIRECT_0
      # Direct bit 0: @range >>= 1 (matches XZ Utils rc_direct pattern where dest += 0)
      @range >>= 1
    when RC_DIRECT_1
      # Direct bit 1: @range >>= 1; @low += @range (matches XZ Utils rc_direct pattern)
      @range >>= 1
      @low += @range
    when RC_FLUSH
      # Prevent further normalization (XZ Utils sets range to UINT32_MAX)
      @range = 0xFFFFFFFF

      # CRITICAL: XZ Utils processes ALL remaining flush symbols in a tight loop
      # before resetting. The loop does: do { rc_shift_low } while (++rc->pos < rc->count)
      # This means it processes the current flush symbol, increments pos, then
      # checks if there are more symbols to process.
      loop do
        # XZ Utils behavior: when low=0 and cache=0, no useful bytes can be written
        # We consume the RC_FLUSH symbol but don't write output
        # After writing cache+carry, if no new cache value and cache_size=0, we're done
        low32 = @low & 0xFFFFFFFF
        high = @low >> 32
        (low32 >> 24) & 0xFF

        # If low and cache are both zero, and cache_size is 0 or 1, we're done
        # (cache_size will be 1 after setting new_cache, or 0 if it was 0 and new_cache is 0)
        break if low32.zero? && high.zero? && @cache.zero? && @cache_size <= 1

        # Process this flush symbol (write one byte)
        if shift_low_buffered(out, out_pos, out_size)
          # Buffer full - pause and resume later
          return true
        end

        # Increment position (matches ++rc->pos in XZ Utils)
        @pos += 1

        # Check if we should continue (matches ++rc->pos < rc->count in XZ Utils)
        # Continue while there are more symbols AND the next symbol is also RC_FLUSH
        break unless @pos < @count && @symbols[@pos] == RC_FLUSH
      end

      # After all flush symbols processed, reset encoder state (like XZ Utils)
      reset
      @count = 0
      # Don't increment @pos again - it was already incremented in the loop
      increment_pos = false
    end

    # Increment position for non-flush symbols (flush symbols increment in the loop)
    @pos += 1 if increment_pos
  end

  # All symbols encoded (flush returns early with @count = 0)
  @count = 0
  @pos = 0
  false
end

#forget ⇒ Object

Forget queued symbols (e.g., when output limit reached)



239
240
241
242
243
 
# File 'lib/omnizip/algorithms/lzma/xz_buffered_range_encoder.rb', line 239

def forget
  raise "Cannot forget with partial encoding" unless @pos.zero?

  @count = 0
end

#none? ⇒ Boolean

Check if there are no queued symbols

Returns:

  • (Boolean) —

    True if no symbols queued



255
256
257
 
# File 'lib/omnizip/algorithms/lzma/xz_buffered_range_encoder.rb', line 255

def none?
  @count.zero?
end

#pending ⇒ Integer

Get number of pending output bytes

Returns:

  • (Integer) —

    Pending bytes count



248
249
250
 
# File 'lib/omnizip/algorithms/lzma/xz_buffered_range_encoder.rb', line 248

def pending
  @cache_size + 5 - 1
end

#queue_bit(prob, bit) ⇒ Object

Queue a bit for encoding (deferred)

Parameters:

  • prob (BitModel) —

    Probability model

  • bit (Integer) —

    Bit value (0 or 1)



99
100
101
102
103
104
105
 
# File 'lib/omnizip/algorithms/lzma/xz_buffered_range_encoder.rb', line 99

def queue_bit(prob, bit)
  raise "Symbol buffer overflow" if @count >= RC_SYMBOLS_MAX

  @symbols[@count] = bit.zero? ? RC_BIT_0 : RC_BIT_1
  @probs[@count] = prob
  @count += 1
end

#queue_direct_bits(value, num_bits) ⇒ Object

Queue direct bits for encoding (deferred)

Parameters:

  • value (Integer) —

    Value to encode

  • num_bits (Integer) —

    Number of bits



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

def queue_direct_bits(value, num_bits)
  num_bits.downto(1) do |i|
    bit = (value >> (i - 1)) & 1
    raise "Symbol buffer overflow" if @count >= RC_SYMBOLS_MAX

    @symbols[@count] = bit.zero? ? RC_DIRECT_0 : RC_DIRECT_1
    @probs[@count] = nil
    @count += 1
  end
end

#queue_flush ⇒ Object

Queue flush operation



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

def queue_flush
  5.times do
    raise "Symbol buffer overflow" if @count >= RC_SYMBOLS_MAX

    @symbols[@count] = RC_FLUSH
    @probs[@count] = nil
    @count += 1
  end
end

#reset ⇒ Object

Reset encoder to initial state NOTE: @out_total is NOT reset here - it tracks cumulative output across chunks and should only be initialized in initialize()



84
85
86
87
88
89
90
91
92
93
 
# File 'lib/omnizip/algorithms/lzma/xz_buffered_range_encoder.rb', line 84

def reset
  @low = 0
  @cache_size = 1
  @range = 0xFFFFFFFF
  @cache = 0
  @count = 0
  @pos = 0
  @symbols.clear
  @probs.clear
end