Class: Omnizip::Algorithms::LZMA::LiteralDecoder

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

Overview

Literal byte decoder

This class is responsible for decoding literal bytes using probability models. It supports two modes matching the encoder:

  1. Unmatched mode: Simple 8-bit decoding
  2. Matched mode: Uses match byte for context (SDK feature)

The decoder must perfectly mirror the encoder's decisions about which probability models to use.

Single Responsibility: Literal byte decoding only

Examples:

Unmatched decoding

decoder = LiteralDecoder.new
byte = decoder.decode_unmatched(lit_state, range_decoder, models)

Matched decoding (SDK mode)

decoder = LiteralDecoder.new
byte = decoder.decode_matched(match_byte, lit_state, range_decoder, models)

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

Instance Method Details

#decode_matched(match_byte, lit_state, lc, range_decoder, models) ⇒ Integer

Decode literal byte in matched mode (SDK feature)

This mode uses a byte from the dictionary (the "match byte") as context for decoding the literal. The decoder must use the same probability model selection as the encoder.

SDK algorithm (from LzmaDec.c):

  • Processes bits in pairs (match bit, literal bit)
  • Uses match bit to select probability model
  • Offset updates based on DECODED bit, not match bit (XZ Utils rc_matched_literal)
  • Switches to unmatched mode when bits diverge

Parameters:

  • match_byte (Integer) —

    Corresponding byte from dictionary

  • lit_state (Integer) —

    Literal context value (0-7 for lc=3, unshifted)

  • lc (Integer) —

    Literal context bits (unused, kept for compatibility)

  • range_decoder (RangeDecoder) —

    Range decoder instance

  • models (Array<BitModel>) —

    Literal probability models

Returns:

  • (Integer) —

    Decoded byte value (0-255)



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

def decode_matched(match_byte, lit_state, lc, range_decoder, models)
  base_offset = 3 * (lit_state << lc)
  symbol = 1
  # XZ Utils: uint32_t t_match_byte = (match_byte);
  # IMPORTANT: Do NOT OR with 0x100 - start with just match_byte!
  # The offset mechanism handles the bit selection.
  match_sym = match_byte
  # XZ Utils: offset starts at 0x100 and is updated based on DECODED bits
  # See: /Users/mulgogi/src/external/xz/src/liblzma/rangecoder/range_decoder.h:342-357
  offset = 0x100

  # SDK matched literal decoding algorithm
  # Process bits while match byte provides context
  loop do
    # XZ Utils pattern: t_match_byte <<= 1; t_match_bit = t_match_byte & t_offset;
    # IMPORTANT: Shift FIRST, then extract the bit!
    # Shift match symbol (brings next bit into position 8)
    match_sym <<= 1

    # Extract current bit from match symbol
    # XZ Utils: t_match_bit = t_match_byte & t_offset
    # IMPORTANT: This is not just checking if non-zero! The result is used directly:
    # - If the bit is 1: t_match_bit = t_offset (e.g., 0x100)
    # - If the bit is 0: t_match_bit = 0
    # This value is used in model_index calculation AND offset updates
    match_bit = match_sym & offset

    # Calculate model index: XZ Utils formula is t_subcoder_index = t_offset + t_match_bit + symbol
    # where t_offset is updated based on PREVIOUS decoded bit, t_match_bit is from match byte
    model_index = base_offset + offset + match_bit + symbol

    # Decode literal bit
    bit = range_decoder.decode_bit(models[model_index])

    # Update offset based on DECODED bit (XZ Utils pattern)
    # IMPORTANT: XZ Utils rc_bit macro updates symbol BEFORE running the action!
    # So we must update symbol FIRST, then use it for offset calculation.
    # XZ Utils pattern:
    # - bit=0: symbol <<= 1; t_offset &= ~t_match_bit
    # - bit=1: symbol = (symbol << 1) + 1; t_offset &= t_match_bit
    # We can simplify this to:
    # - If bit=0: offset &= ~match_bit
    # - If bit=1: offset &= match_bit

    if bit.zero?
      # Clear the match_bit from offset
      offset &= ~match_bit
      # Update symbol (shift left, add 0)
      symbol <<= 1
    else
      # Keep only the match_bit in offset
      offset &= match_bit
      # Update symbol (shift left, add 1)
      symbol = (symbol << 1) | 1
    end

    # If bits diverge, switch to unmatched mode
    if (match_bit.positive? ? 1 : 0) != bit
      # Continue in unmatched mode for remaining bits
      break if symbol >= 0x100

      return decode_unmatched_tail(symbol, base_offset, lc,
                                   range_decoder, models)
    end

    # Done when symbol reaches 0x100
    break if symbol >= 0x100
  end

  symbol - 0x100
end

#decode_unmatched(lit_state, lc, range_decoder, models) ⇒ Integer

Decode literal byte in unmatched mode

This is the standard LZMA literal decoding where each bit is decoded using probability models based on the partial symbol value.

Parameters:

  • lit_state (Integer) —

    Literal context value (0-7 for lc=3, unshifted)

  • lc (Integer) —

    Literal context bits (unused, kept for compatibility)

  • range_decoder (RangeDecoder) —

    Range decoder instance

  • models (Array<BitModel>) —

    Literal probability models

Returns:

  • (Integer) —

    Decoded byte value (0-255)



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

def decode_unmatched(lit_state, lc, range_decoder, models)
  # XZ Utils literal_subcoder returns: probs + 3 * (context_value << lc)
  # where context_value = (((pos << 8) + prev_byte) & literal_mask)
  # Our lit_state is context_value (unshifted)
  # IMPORTANT: Shift BEFORE multiplying by 3 (XZ Utils formula order)
  base_offset = 3 * (lit_state << lc)

  # Start with symbol = 1
  # We build it up bit by bit until it reaches 0x100
  symbol = 1

  # Decode 8 bits to build the symbol from 1 to 0x100
  while symbol < 0x100
    # Model index based on current symbol value
    model_index = base_offset + symbol

    # Decode next bit
    bit = range_decoder.decode_bit(models[model_index])

    # Update symbol: shift left and add bit
    symbol = (symbol << 1) | bit
  end

  # Symbol is now in range 0x100-0x1FF
  # Extract the byte value by subtracting 0x100
  symbol - 0x100
end