Class: Omnizip::Algorithms::LZMA::XzEncoderFast

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

Overview

XZ Utils-compatible fast mode encoder

Implements greedy heuristics from lzma_encoder_optimum_fast.c. Uses 1-position lookahead to decide between literals and matches. No price calculation - relies on simple heuristics for speed.

Based on: xz/src/liblzma/lzma/lzma_encoder_optimum_fast.c

Constant Summary collapse

REPS =

Number of rep distances (REPS constant)

4
LITERAL_MARKER =

Literal marker (matches XZ Utils UINT32_MAX)

0xFFFFFFFF

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

Instance Method Summary collapse

Constructor Details

#initialize(mf, encoder, models, state, nice_len: 32, lc: 3, lp: 0, pb: 2) ⇒ XzEncoderFast

Initialize fast mode encoder

Parameters:

  • mf (XzMatchFinderAdapter) —

    Match finder

  • encoder (XzBufferedRangeEncoder) —

    Range encoder

  • models (XzProbabilityModels) —

    Probability models

  • state (XzState) —

    LZMA state machine

  • nice_len (Integer) (defaults to: 32) —

    Nice match length (default 32)

  • lc (Integer) (defaults to: 3) —

    Literal context bits (default 3)

  • lp (Integer) (defaults to: 0) —

    Literal position bits (default 0)

  • pb (Integer) (defaults to: 2) —

    Position bits (default 2)



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

def initialize(mf, encoder, models, state, nice_len: 32, lc: 3, lp: 0,
                                           pb: 2)
  @mf = mf
  @encoder = encoder
  @models = models
  @state = state
  @nice_len = nice_len
  @lc = lc
  @lp = lp
  @pb = pb

  # Rep distances (last 4 match distances)
  # Initialize to 0 to prevent false matches before first normal match
  @reps = [0, 0, 0, 0]

  # Lookahead cache (for read_ahead == 1 optimization)
  @read_ahead = 0
  @longest_match_length = 0
  @matches_count = 0
  @cached_matches = []

  # Track previous byte for literal context
  @prev_byte = 0
end

Instance Attribute Details

#reps ⇒ Object (readonly)

Returns the value of attribute reps.



42
43
44
 
# File 'lib/omnizip/algorithms/lzma/xz_encoder_fast.rb', line 42

def reps
  @reps
end

Instance Method Details

#bytes_for_decode ⇒ Integer

Return bytes needed for decoding (excludes flush padding)

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



50
51
52
 
# File 'lib/omnizip/algorithms/lzma/xz_encoder_fast.rb', line 50

def bytes_for_decode
  @encoder.bytes_for_decode
end

#encode_literal(symbol) ⇒ Object

Encode literal symbol

Parameters:

  • symbol (Integer) —

    Byte value to encode



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

def encode_literal(symbol)
  pos_state = @mf.pos & ((1 << @pb) - 1)

  # Encode is_match bit (0 for literal)
  prob_is_match = @models.is_match[@state.value][pos_state]
  @encoder.queue_bit(prob_is_match, 0)

  # Get literal subcoder BASE index (XZ Utils literal_subcoder macro)
  # The subcoder is a flat array of 768 probability models
  literal_base = get_literal_base(@mf.pos, @prev_byte)

  if @state.literal_state?
    # Normal literal (8-bit tree)
    encode_normal_literal(literal_base, symbol)
  else
    # Matched literal (compare with match byte at rep0)
    match_byte = @mf.get_byte(-@reps[0]) # reps[0] is 0-based offset
    encode_matched_literal(literal_base, match_byte, symbol)
  end

  # Update state and prev_byte
  @state.update_literal
  @prev_byte = symbol
end

#encode_normal_match(distance, length) ⇒ Object

Encode normal match

Parameters:

  • distance (Integer) —

    Match distance (0-based)

  • length (Integer) —

    Match length (>= 2)



313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
 
# File 'lib/omnizip/algorithms/lzma/xz_encoder_fast.rb', line 313

def encode_normal_match(distance, length)
  pos_state = @mf.pos & ((1 << @pb) - 1)

  # Encode is_match bit (1 for match)
  prob_is_match = @models.is_match[@state.value][pos_state]
  @encoder.queue_bit(prob_is_match, 1)

  # Encode is_rep bit (0 for normal match)
  prob_is_rep = @models.is_rep[@state.value]
  @encoder.queue_bit(prob_is_rep, 0)

  # Encode length
  encode_match_length(length, pos_state)

  # Encode distance
  encode_distance(distance, length)

  # Update state and prev_byte
  @state.update_match
  @prev_byte = @mf.get_byte(length - 1)
end

#encode_rep_match(rep_index, length) ⇒ Object

Encode rep match

Parameters:

  • rep_index (Integer) —

    Rep index (0-3)

  • length (Integer) —

    Match length (>= 2)



250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
 
# File 'lib/omnizip/algorithms/lzma/xz_encoder_fast.rb', line 250

def encode_rep_match(rep_index, length)
  pos_state = @mf.pos & ((1 << @pb) - 1)

  # Encode is_match bit (1 for match)
  prob_is_match = @models.is_match[@state.value][pos_state]
  @encoder.queue_bit(prob_is_match, 1)

  # Encode is_rep bit (1 for rep)
  prob_is_rep = @models.is_rep[@state.value]
  @encoder.queue_bit(prob_is_rep, 1)

  prob_is_rep0 = @models.is_rep0[@state.value]
  case rep_index
  when 0
    # rep0
    @encoder.queue_bit(prob_is_rep0, 0) # FIX: 0 means "yes, use rep0"

    prob_is_rep0_long = @models.is_rep0_long[@state.value][pos_state]
    if length == 1
      # Short rep (1 byte)
      @encoder.queue_bit(prob_is_rep0_long, 0)
      @state.update_short_rep
    else
      # Long rep0
      @encoder.queue_bit(prob_is_rep0_long, 1)
      encode_rep_length(length, pos_state)
      @state.update_long_rep
    end
  when 1
    # rep1
    @encoder.queue_bit(prob_is_rep0, 1)
    prob_is_rep1 = @models.is_rep1[@state.value]
    @encoder.queue_bit(prob_is_rep1, 0) # FIX: 0 means "yes, use rep1"
    encode_rep_length(length, pos_state)
    @state.update_long_rep
  when 2
    # rep2
    @encoder.queue_bit(prob_is_rep0, 1)
    prob_is_rep1 = @models.is_rep1[@state.value]
    @encoder.queue_bit(prob_is_rep1, 1)
    prob_is_rep2 = @models.is_rep2[@state.value]
    @encoder.queue_bit(prob_is_rep2, 0) # FIX: 0 means "yes, use rep2"
    encode_rep_length(length, pos_state)
    @state.update_long_rep
  else
    # rep3
    @encoder.queue_bit(prob_is_rep0, 1)
    prob_is_rep1 = @models.is_rep1[@state.value]
    @encoder.queue_bit(prob_is_rep1, 1)
    prob_is_rep2 = @models.is_rep2[@state.value]
    @encoder.queue_bit(prob_is_rep2, 1)
    encode_rep_length(length, pos_state)
    @state.update_long_rep
  end

  # Update prev_byte (last byte of match)
  @prev_byte = @mf.get_byte(length - 1)
end

#find_best_match ⇒ Array<Integer, Integer>

Find best match at current position using fast mode heuristics

Returns (back, len) where:

  • back = LITERAL_MARKER, len = 1: encode literal
  • back = 0..3, len >= 2: rep match (use reps)
  • back >= 4, len >= 2: normal match (distance = back - 4)

Returns:

  • (Array<Integer, Integer>) —

    [back, len]



97
98
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
128
129
130
131
132
133
134
135
136
137
138
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
 
# File 'lib/omnizip/algorithms/lzma/xz_encoder_fast.rb', line 97

def find_best_match
  # Get matches (use cached if lookahead was done)
  if @read_ahead.zero?
    len_main = @mf.find_matches
    matches_count = @mf.matches.size
  else
    # Use cached matches from previous lookahead
    len_main = @longest_match_length
    matches_count = @matches_count
    @read_ahead = 0
  end

  buf_avail = [@mf.available + 1, MATCH_LEN_MAX].min

  # Not enough input for match
  return [LITERAL_MARKER, 1] if buf_avail < 2

  # Check rep matches
  rep_len, rep_index = check_rep_matches(buf_avail)

  # Found long rep match - return immediately
  if rep_len >= @nice_len
    # Don't skip here - main loop handles it
    return [rep_index, rep_len]
  end

  # Found long normal match - return immediately
  if len_main >= @nice_len
    back_main = @mf.matches.last.dist - 1 + REPS # Convert to 0-based then add REPS offset
    # Don't skip here - main loop handles it
    return [back_main, len_main]
  end

  # Select best normal match using heuristics
  back_main = 0
  if len_main >= 2
    back_main = @mf.matches.last.dist

    # Apply change_pair heuristic: prefer closer distances
    while matches_count > 1 &&
        len_main == @mf.matches[matches_count - 2].len + 1
      prev_dist = @mf.matches[matches_count - 2].dist
      break unless change_pair?(prev_dist, back_main)

      matches_count -= 1
      len_main = @mf.matches[matches_count - 1].len
      back_main = @mf.matches[matches_count - 1].dist
    end

    # Reject short matches with far distances
    len_main = 1 if len_main == 2 && back_main >= 0x80
  end

  # Compare rep vs normal match
  # Prefer rep match if:
  # - rep_len + 1 >= len_main, OR
  # - rep_len + 2 >= len_main AND back_main > 512, OR
  # - rep_len + 3 >= len_main AND back_main > 32768
  if (rep_len >= 2) && ((rep_len + 1 >= len_main) ||
                        (rep_len + 2 >= len_main && back_main > (1 << 9)) ||
                        (rep_len + 3 >= len_main && back_main > (1 << 15)))
    # Don't skip here - main loop handles it
    return [rep_index, rep_len]
  end

  # No good match found
  return [LITERAL_MARKER, 1] if len_main < 2 || buf_avail <= 2

  # Lookahead: check next position for better match
  @longest_match_length = @mf.find_matches
  @matches_count = @mf.matches.size
  @read_ahead = 1

  if @longest_match_length >= 2
    new_dist = @mf.matches.last.dist

    # Encode literal if next position has better match
    if (@longest_match_length >= len_main && new_dist < back_main) ||
        (@longest_match_length == len_main + 1 && !change_pair?(
          back_main, new_dist
        )) ||
        (@longest_match_length > len_main + 1) ||
        (len_main.between?(3, @longest_match_length + 1) &&
         change_pair?(new_dist, back_main))
      return [LITERAL_MARKER, 1]
    end
  end

  # Check reps at next position (after lookahead)
  # Skip if all distances are 0 (uninitialized - before first normal match)
  unless @reps.all?(0)
    limit = [2, len_main - 1].max
    @reps.each do |rep_dist|
      if memcmp_at_offset(1, rep_dist, limit)
        return [LITERAL_MARKER, 1]
      end
    end
  end

  # Encode best normal match
  # Don't skip here - main loop handles it
  # back_main contains raw 1-based distance, convert to back value
  [back_main - 1 + REPS, len_main] # Convert to 0-based then add REPS offset
end

#update_reps_match(distance) ⇒ Object

Update rep distances after encoding match

Parameters:

  • distance (Integer) —

    Match distance (0-based)



205
206
207
 
# File 'lib/omnizip/algorithms/lzma/xz_encoder_fast.rb', line 205

def update_reps_match(distance)
  @reps = [distance, @reps[0], @reps[1], @reps[2]]
end

#update_reps_rep(rep_index) ⇒ Object

Update rep distances after encoding rep match

Parameters:

  • rep_index (Integer) —

    Rep index (0-3)



212
213
214
215
216
 
# File 'lib/omnizip/algorithms/lzma/xz_encoder_fast.rb', line 212

def update_reps_rep(rep_index)
  rep_dist = @reps[rep_index]
  @reps.delete_at(rep_index)
  @reps.unshift(rep_dist)
end