Class: Omnizip::Algorithms::LZMA::XzRangeEncoder

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

Overview

XZ Utils-compatible range encoder (direct port)

This is a direct port of the XZ Utils range encoder implementation to ensure exact algorithmic compatibility with XZ Utils output.

Constant Summary collapse

SHIFT_BITS =

Range encoder constants (matching XZ Utils range_common.h)

8
TOP_BITS =

RC_SHIFT_BITS

24
TOP =

RC_TOP_BITS

0x01000000
BIT_MODEL_TOTAL_BITS =

2^24

11
BIT_MODEL_TOTAL =

2^11

2048
RC_BIT_0 =

Symbol types (matching XZ Utils enum)

0
RC_BIT_1 = 
1
RC_DIRECT_0 = 
2
RC_DIRECT_1 = 
3
RC_FLUSH = 
4
RC_SYMBOLS_MAX =

Maximum symbols that can be queued

53

Constants included from Constants

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(output_stream) ⇒ XzRangeEncoder

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/xz_range_encoder_exact.rb', line 40

def initialize(output_stream)
  @stream = output_stream
  # Initialize @out_total BEFORE calling reset
  @out_total = 0
  reset
end

Instance Attribute Details

#cache ⇒ Object (readonly)

Returns the value of attribute cache.



35
36
37
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder_exact.rb', line 35

def cache
  @cache
end

#cache_size ⇒ Object (readonly)

Returns the value of attribute cache_size.



35
36
37
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder_exact.rb', line 35

def cache_size
  @cache_size
end

#count ⇒ Object (readonly)

Returns the value of attribute count.



35
36
37
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder_exact.rb', line 35

def count
  @count
end

#low ⇒ Object (readonly)

Returns the value of attribute low.



35
36
37
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder_exact.rb', line 35

def low
  @low
end

#out_total ⇒ Object (readonly)

Returns the value of attribute out_total.



35
36
37
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder_exact.rb', line 35

def out_total
  @out_total
end

#range ⇒ Object (readonly)

Returns the value of attribute range.



35
36
37
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder_exact.rb', line 35

def range
  @range
end

Instance Method Details

#bit(prob, bit) ⇒ Object Also known as: queue_bit

Queue a bit for encoding (matches XZ Utils rc_bit)

Parameters:

  • prob (Probability) —

    Probability model

  • bit (Integer) —

    Bit value (0 or 1)



75
76
77
78
79
80
81
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder_exact.rb', line 75

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

  @symbols[@count] = bit
  @probs[@count] = prob
  @count += 1
end

#bittree(probs, bit_count, symbol) ⇒ Object Also known as: queue_bittree

Queue bittree encoding (matches XZ Utils rc_bittree)

Parameters:

  • probs (Array<Probability>) —

    Probability array

  • bit_count (Integer) —

    Number of bits

  • symbol (Integer) —

    Symbol to encode



89
90
91
92
93
94
95
96
97
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder_exact.rb', line 89

def bittree(probs, bit_count, symbol)
  model_index = 1

  bit_count.times do
    bit = (symbol >> (bit_count -= 1)) & 1
    bit(probs[model_index], bit)
    model_index = (model_index << 1) | bit
  end
end

#bittree_reverse(probs, bit_count, symbol) ⇒ Object Also known as: queue_bittree_reverse

Queue bittree encoding in reverse (matches XZ Utils rc_bittree_reverse)

Parameters:

  • probs (Array<Probability>) —

    Probability array

  • bit_count (Integer) —

    Number of bits

  • symbol (Integer) —

    Symbol to encode



104
105
106
107
108
109
110
111
112
113
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder_exact.rb', line 104

def bittree_reverse(probs, bit_count, symbol)
  model_index = 1

  bit_count.times do
    bit = symbol & 1
    symbol >>= 1
    bit(probs[model_index], bit)
    model_index = (model_index << 1) | bit
  end
end

#bytes_for_decode ⇒ Integer

Calculate pending output bytes

Returns:

  • (Integer) —

    Number of bytes decoder will consume



299
300
301
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder_exact.rb', line 299

def bytes_for_decode
  @out_total
end

#direct(value, bit_count) ⇒ Object

Queue direct bits (matches XZ Utils rc_direct)

Parameters:

  • value (Integer) —

    Value to encode

  • bit_count (Integer) —

    Number of bits



119
120
121
122
123
124
125
126
127
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder_exact.rb', line 119

def direct(value, bit_count)
  bit_count.times do
    raise "Symbol buffer overflow" if @count >= RC_SYMBOLS_MAX

    @symbols[@count] = RC_DIRECT_0 | ((value >> (bit_count -= 1)) & 1)
    @probs[@count] = nil
    @count += 1
  end
end

#encode(out, out_pos, out_size) ⇒ Boolean Also known as: encode_symbols

Encode all queued symbols to output (matches XZ Utils rc_encode)

Parameters:

  • out (IO, String) —

    Output buffer

  • out_pos (IntegerRef) —

    Current output position

  • out_size (Integer) —

    Output buffer size

Returns:

  • (Boolean) —

    True if output buffer filled before encoding complete



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
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder_exact.rb', line 161

def encode(out, out_pos, out_size)
  raise "Symbol buffer overflow" if @count > RC_SYMBOLS_MAX

  skip_increment = false

  while @pos < @count
    # Normalize (matches XZ Utils exactly)
    if @range < TOP
      return true if shift_low(out, out_pos, out_size)

      @range <<= SHIFT_BITS
    end

    # Encode current symbol
    case @symbols[@pos]
    when RC_BIT_0
      prob = @probs[@pos]
      # XZ Utils: rc->range = (rc->range >> RC_BIT_MODEL_TOTAL_BITS) * prob
      @range = (@range >> BIT_MODEL_TOTAL_BITS) * prob.value
      # XZ Utils: prob += (RC_BIT_MODEL_TOTAL - prob) >> RC_MOVE_BITS
      prob.value += (BIT_MODEL_TOTAL - prob.value) >> MOVE_BITS
      @probs[@pos] = prob

    when RC_BIT_1
      prob = @probs[@pos]
      # XZ Utils: bound = prob * (rc->range >> RC_BIT_MODEL_TOTAL_BITS)
      bound = prob.value * (@range >> BIT_MODEL_TOTAL_BITS)
      @low += bound
      @range -= bound
      # XZ Utils: prob -= prob >> RC_MOVE_BITS
      prob.value -= prob.value >> MOVE_BITS
      @probs[@pos] = prob

    when RC_DIRECT_0
      @range >>= 1

    when RC_DIRECT_1
      @range >>= 1
      @low += @range

    when RC_FLUSH
      # Prevent further normalizations (XZ Utils behavior)
      @range = 0xFFFFFFFF

      # Flush the last five bytes (see rc_flush)
      begin
        return true if shift_low(out, out_pos, out_size)
      end while (@pos += 1) < @count

      # Reset the range encoder (matches XZ Utils)
      reset
      # CRITICAL: Skip the @pos increment at loop end because do-while already did it
      skip_increment = true
      break

    else
      raise "Unknown symbol type: #{@symbols[@pos]}"
    end

    @pos += 1 unless skip_increment
  end

  @count = 0
  @pos = 0

  false
end

#flush ⇒ Object Also known as: queue_flush

Queue flush operation (matches XZ Utils rc_flush)



130
131
132
133
134
135
136
137
138
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder_exact.rb', line 130

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

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

#forget ⇒ Object

Forget pending symbols (matches XZ Utils rc_forget)



65
66
67
68
69
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder_exact.rb', line 65

def forget
  raise "Cannot forget while encoding" if @pos != 0

  @count = 0
end

#none? ⇒ Boolean

Check if no symbols are queued

Returns:

  • (Boolean) —

    True if no symbols queued



151
152
153
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder_exact.rb', line 151

def none?
  @count.zero?
end

#pending ⇒ Integer

Get number of pending bytes (matches XZ Utils rc_pending)

Returns:

  • (Integer) —

    Number of pending output bytes



144
145
146
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder_exact.rb', line 144

def pending
  @cache_size + 5 - 1
end

#queue_direct_bits(value, num_bits) ⇒ Object

Adapter method: alias for direct (to match existing API)



279
280
281
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder_exact.rb', line 279

def queue_direct_bits(value, num_bits)
  direct(value, num_bits)
end

#reset ⇒ Object

Reset encoder to initial state (matches XZ Utils rc_reset)



48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder_exact.rb', line 48

def reset
  @low = 0
  @cache_size = 1 # CRITICAL: XZ starts with 1, not 0
  @range = 0xFFFFFFFF
  @cache = 0
  # CRITICAL: Reset @out_total to match XZ Utils behavior (line 63 of range_encoder.h)
  # This ensures bytes_for_decode returns the correct count
  @out_total = 0
  # NOTE: @pre_flush_out_total is NOT reset - it retains its value for bytes_for_decode
  # It will be reset to 0 when a new chunk starts (via initialize)
  @count = 0
  @pos = 0
  @symbols = Array.new(RC_SYMBOLS_MAX, 0)
  @probs = Array.new(RC_SYMBOLS_MAX, nil)
end

#shift_low(out, out_pos, out_size) ⇒ Boolean

Shift low bytes to output (matches XZ Utils rc_shift_low)

Parameters:

  • out (IO, String) —

    Output buffer

  • out_pos (IntegerRef) —

    Current output position

  • out_size (Integer) —

    Output buffer size

Returns:

  • (Boolean) —

    True if output buffer filled



235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
 
# File 'lib/omnizip/algorithms/lzma/xz_range_encoder_exact.rb', line 235

def shift_low(out, out_pos, out_size)
  # XZ Utils: if ((uint32_t)(rc->low) < (uint32_t)(0xFF000000) || (uint32_t)(rc->low >> 32) != 0)
  if (@low & 0xFFFFFFFF) < 0xFF000000 || (@low >> 32) != 0
    # XZ Utils: do { ... } while (--rc->cache_size != 0);
    while @cache_size.positive?
      return true if out_pos.value == out_size

      # XZ Utils: out[*out_pos] = rc->cache + (uint8_t)(rc->low >> 32)
      output_byte = @cache + ((@low >> 32) & 0xFF)

      if out.is_a?(String)
        out.setbyte(out_pos.value, output_byte)
      else
        out.putc(output_byte)
      end

      out_pos.value += 1
      @out_total += 1
      @cache = 0xFF

      @cache_size -= 1
    end

    # XZ Utils: rc->cache = (rc->low >> 24) & 0xFF
    @cache = (@low >> 24) & 0xFF
  end

  # XZ Utils: ++rc->cache_size; rc->low = (rc->low & 0x00FFFFFF) << RC_SHIFT_BITS
  @cache_size += 1
  @low = (@low & 0x00FFFFFF) << SHIFT_BITS

  false
end