Class: Omnizip::Algorithms::LZMA::LengthCoder

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

Overview

SDK-compatible length encoder/decoder

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

  • Lengths 0-7: choice=0, 3 bits from low tree
  • Lengths 8-15: choice=1, choice2=0, 3 bits from mid tree
  • Lengths 16+: choice=1, choice2=1, 8 bits from high tree

Position state is used to select which low/mid tree to use, providing context-dependent compression.

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_pos_states) ⇒ LengthCoder

Initialize the length coder

Parameters:

  • num_pos_states (Integer) —

    Number of position states (1 << pb)



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

def initialize(num_pos_states)
  @num_pos_states = num_pos_states
  @choice = BitModel.new
  @choice2 = BitModel.new

  # Low trees: one per position state, 8 symbols each
  # Tree needs 2^(num_bits+1) models: 2^4 = 16 for 3-bit tree
  @low = Array.new(num_pos_states) do
    Array.new(1 << (NUM_LEN_LOW_BITS + 1)) { BitModel.new }
  end

  # Mid trees: one per position state, 8 symbols each
  # Tree needs 2^(num_bits+1) models: 2^4 = 16 for 3-bit tree
  @mid = Array.new(num_pos_states) do
    Array.new(1 << (NUM_LEN_MID_BITS + 1)) { BitModel.new }
  end

  # High tree: shared across all position states, 256 symbols
  # Tree needs 2^(num_bits+1) models: 2^9 = 512 for 8-bit tree
  @high = Array.new(1 << (NUM_LEN_HIGH_BITS + 1)) { BitModel.new }
end

Instance Method Details

#decode(range_decoder, pos_state) ⇒ Integer

Decode a match length using SDK-compatible decoding

Parameters:

  • range_decoder (RangeDecoder) —

    The range decoder

  • pos_state (Integer) —

    Position state for tree selection

Returns:

  • (Integer) —

    Decoded length value (before adding MATCH_LEN_MIN)



96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
# File 'lib/omnizip/algorithms/lzma/length_coder.rb', line 96

def decode(range_decoder, pos_state)
  choice_bit = range_decoder.decode_bit(@choice)

  if choice_bit.zero?
    # Low tree
    decode_tree(range_decoder, @low[pos_state],
                NUM_LEN_LOW_BITS)
  elsif range_decoder.decode_bit(@choice2).zero?
    # Mid tree
    LEN_LOW_SYMBOLS +
      decode_tree(range_decoder, @mid[pos_state], NUM_LEN_MID_BITS)
  else
    # High tree
    LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS +
      decode_tree(range_decoder, @high, NUM_LEN_HIGH_BITS)
  end
end

#encode(range_encoder, length, pos_state) ⇒ void

This method returns an undefined value.

Encode a match length using SDK-compatible encoding

Parameters:

  • range_encoder (RangeEncoder) —

    The range encoder

  • length (Integer) —

    Length value (already subtracted MATCH_LEN_MIN)

  • pos_state (Integer) —

    Position state for tree selection



69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
# File 'lib/omnizip/algorithms/lzma/length_coder.rb', line 69

def encode(range_encoder, length, pos_state)
  if length < LEN_LOW_SYMBOLS
    # 0-7: Use low tree
    range_encoder.encode_bit(@choice, 0)
    encode_tree(range_encoder, @low[pos_state], length,
                NUM_LEN_LOW_BITS)
  elsif length < LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS
    # 8-15: Use mid tree
    range_encoder.encode_bit(@choice, 1)
    range_encoder.encode_bit(@choice2, 0)
    encode_tree(range_encoder, @mid[pos_state],
                length - LEN_LOW_SYMBOLS, NUM_LEN_MID_BITS)
  else
    # 16+: Use high tree
    range_encoder.encode_bit(@choice, 1)
    range_encoder.encode_bit(@choice2, 1)
    encode_tree(range_encoder, @high,
                length - LEN_LOW_SYMBOLS - LEN_MID_SYMBOLS,
                NUM_LEN_HIGH_BITS)
  end
end

#reset_models ⇒ void

This method returns an undefined value.

Reset probability models to initial values

Called during state reset (control >= 0xA0) to reset the length coder's probability models. This matches XZ Utils behavior.



120
121
122
123
124
125
126
127
128
129
130
131
132
133
 
# File 'lib/omnizip/algorithms/lzma/length_coder.rb', line 120

def reset_models
  @choice.reset
  @choice2.reset

  @low.each do |state_models|
    state_models.each(&:reset)
  end

  @mid.each do |state_models|
    state_models.each(&:reset)
  end

  @high.each(&:reset)
end