Class: Omnizip::Algorithms::LZMA::DistanceCoder

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

Overview

SDK-compatible distance encoder/decoder

This class implements the LZMA SDK's distance encoding scheme:

  • Slot 0-3: Direct encoding (no extra bits)
  • Slot 4-13: Slot + 1-5 direct bits
  • Slot 14+: Slot + fixed bits + aligned bits

The slot categorizes distances into ranges, and extra bits specify the exact position within that 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 Method Summary collapse

Constructor Details

#initialize(num_len_to_pos_states) ⇒ DistanceCoder

Initialize the distance coder

Parameters:

  • num_len_to_pos_states (Integer) —

    Number of length states for slot selection



41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
# File 'lib/omnizip/algorithms/lzma/distance_coder.rb', line 41

def initialize(num_len_to_pos_states)
  @num_len_to_pos_states = num_len_to_pos_states

  # Slot encoders: one per length state, 128 models each
  # Tree needs 2^(num_bits+1) models for a 6-bit tree: indices 1-127
  # This matches the tree decode algorithm which accesses up to index 127
  @slot_encoders = Array.new(num_len_to_pos_states) do
    Array.new(1 << (NUM_DIST_SLOT_BITS + 1)) { BitModel.new }
  end

  # Position encoders for slots 4-13
  # SDK convention: size = NUM_FULL_DISTANCES - END_POS_MODEL_INDEX = 128 - 14 = 114
  # Indexed by: base - slot - 1 (matches LZMA SDK and XZ Utils)
  @pos_encoders = Array.new(NUM_FULL_DISTANCES - END_POS_MODEL_INDEX) do
    BitModel.new
  end

  # Aligned encoder for slots 14+ (4-bit aligned)
  # Tree needs 2^5 = 32 models for 4-bit tree
  @align_encoder = Array.new(1 << (DIST_ALIGN_BITS + 1)) do
    BitModel.new
  end

  # Precompute distance slot lookup table for fast encoding
  @slot_fast = Array.new(DIST_SLOT_FAST_LIMIT)
  init_slot_fast_table
end

Instance Method Details

#decode(range_decoder, len_state) ⇒ Integer

Decode a match distance using SDK-compatible decoding

Parameters:

  • range_decoder (RangeDecoder) —

    The range decoder

  • len_state (Integer) —

    Length state for slot selection

Returns:

  • (Integer) —

    Decoded distance value (before adding 1)



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

def decode(range_decoder, len_state)
  slot = decode_tree(range_decoder, @slot_encoders[len_state],
                     NUM_DIST_SLOT_BITS)

  # Decode extra bits based on slot
  if slot < START_POS_MODEL_INDEX
    # Slots 0-3: No extra bits
    slot
  else
    footer_bits = (slot >> 1) - 1

    if slot < END_POS_MODEL_INDEX
      # Slots 4-13: Use position encoders (reverse tree decoding)
      # SDK/XZ Utils convention: base_idx = base - slot - 1
      base = (2 | (slot & 1)) << footer_bits
      result = base + decode_reverse_tree(range_decoder,
                                          @pos_encoders,
                                          base - slot - 1,
                                          footer_bits)
    else
      # Slots 14+: Fixed direct bits + aligned bits
      # XZ Utils pattern (lzma_decoder.c:500-514):
      # - Start with rep0 = 2 + (slot & 1)
      # - Decode high_bits using rc_direct (builds up from starting value)
      # - Shift left by ALIGN_BITS
      # - Decode low_bits using aligned encoder
      # - Add symbol (slot) to final result

      footer_bits = (slot >> 1) - 1
      num_direct_bits = footer_bits - DIST_ALIGN_BITS

      # XZ Utils pattern for slot >= 14:
      # rep0 = 2 + (slot & 1)
      # rc_direct(rep0, num_direct_bits)
      # rep0 <<= ALIGN_BITS
      # rc_bittree_rev4(coder->pos_align)
      # IMPORTANT: slot value is NOT added to result
      # Reference: /Users/mulgogi/src/external/xz/src/liblzma/lzma/lzma_decoder.c:507-512
      result = 2 + (slot & 1)

      # Use decode_direct_bits_with_base to match XZ Utils rc_direct
      # rc_direct builds on the base value iteratively
      result = range_decoder.decode_direct_bits_with_base(
        num_direct_bits, result
      )

      # Decode low 4 bits using aligned encoder (reverse tree)
      low_bits = decode_reverse_tree(range_decoder,
                                     @align_encoder,
                                     0,
                                     DIST_ALIGN_BITS)

      # Final result: (result << 4) + low_bits
      # NOTE: slot value is NOT added (XZ Utils pattern - line 513 adds symbol for EOPM check only)
      result = (result << DIST_ALIGN_BITS) + low_bits
    end
    result
  end
end

#encode(range_encoder, distance, len_state) ⇒ void

This method returns an undefined value.

Encode a match distance using SDK-compatible encoding

Parameters:

  • range_encoder (RangeEncoder) —

    The range encoder

  • distance (Integer) —

    Distance value (already subtracted 1)

  • len_state (Integer) —

    Length state for slot selection



89
90
91
92
93
94
95
96
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
 
# File 'lib/omnizip/algorithms/lzma/distance_coder.rb', line 89

def encode(range_encoder, distance, len_state)
  slot = get_dist_slot(distance)

  # Encode the slot using the appropriate slot encoder
  encode_tree(range_encoder, @slot_encoders[len_state], slot,
              NUM_DIST_SLOT_BITS)

  # Encode extra bits based on slot
  if slot >= START_POS_MODEL_INDEX
    footer_bits = (slot >> 1) - 1
    base = (2 | (slot & 1)) << footer_bits

    if slot < END_POS_MODEL_INDEX
      # Slots 4-13: Use position encoders (reverse tree encoding)
      # SDK/XZ Utils convention: base_idx = base - slot - 1
      encode_reverse_tree(range_encoder,
                          @pos_encoders,
                          base - slot - 1,
                          distance - base,
                          footer_bits)
    else
      # Slots 14+: Fixed direct bits + aligned bits
      # Encode high bits as direct bits
      range_encoder.encode_direct_bits((distance - base) >> DIST_ALIGN_BITS,
                                       footer_bits - DIST_ALIGN_BITS)

      # Encode low 4 bits using aligned encoder (reverse tree)
      encode_reverse_tree(range_encoder,
                          @align_encoder,
                          0,
                          distance - base,
                          DIST_ALIGN_BITS)
    end
  end
end

#reset_models ⇒ void

This method returns an undefined value.

Reset all probability models in place

This method resets the bit models to their initial state. Called during state reset to reinitialize probability models.



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

def reset_models
  @slot_encoders.each do |len_state_models|
    len_state_models.each(&:reset)
  end
  @pos_encoders.each(&:reset)
  @align_encoder.each(&:reset)
end