Class: Omnizip::Algorithms::LZMA::LiteralEncoder

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

Overview

Literal byte encoder

This class is responsible for encoding literal bytes using probability models. It supports two modes:

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

The matched mode improves compression when a literal follows a match, by using the corresponding byte from the match as context for probability modeling.

Single Responsibility: Literal byte encoding only

Examples:

Unmatched encoding

encoder = LiteralEncoder.new
encoder.encode_unmatched(byte, lit_state, range_encoder, models)

Matched encoding (SDK mode)

encoder = LiteralEncoder.new
encoder.encode_matched(byte, match_byte, lit_state, range_encoder, 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

Constructor Details

#initialize(lc = 3) ⇒ LiteralEncoder

Initialize the literal encoder

Default to 3 for compatibility

Parameters:

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

    Literal context bits (0-8)



54
55
56
 
# File 'lib/omnizip/algorithms/lzma/literal_encoder.rb', line 54

def initialize(lc = 3)
  @lc = lc
end

Instance Method Details

#encode_matched(byte, match_byte, pos, prev_byte, lc, literal_mask, range_encoder, models) ⇒ void

This method returns an undefined value.

Encode literal byte in matched mode (SDK feature)

This mode uses a byte from the dictionary (the "match byte") as context for encoding the literal. This improves compression when the literal follows a match, as the match byte provides additional predictive information.

Direct port from XZ Utils literal_matched() in lzma_encoder.c:22-41

Parameters:

  • byte (Integer) —

    Byte value to encode (0-255)

  • match_byte (Integer) —

    Corresponding byte from dictionary

  • pos (Integer) —

    Current position in stream

  • prev_byte (Integer) —

    Previous byte value

  • lc (Integer) —

    Literal context bits (0-8)

  • literal_mask (Integer) —

    Literal mask for context calculation

  • range_encoder (RangeEncoder) —

    Range encoder instance

  • models (Array<BitModel>) —

    Literal probability models



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

def encode_matched(byte, match_byte, pos, prev_byte, lc, literal_mask,
range_encoder, models)
  # Direct port of xz's literal_matched
  # static inline void
  # literal_matched(lzma_range_encoder *rc, probability *subcoder,
  #     uint32_t match_byte, uint32_t symbol)
  # {
  #   uint32_t offset = 0x100;
  #   symbol += UINT32_C(1) << 8;
  #
  #   do {
  #     match_byte <<= 1;
  #     const uint32_t match_bit = match_byte & offset;
  #     const uint32_t subcoder_index
  #           = offset + match_bit + (symbol >> 8);
  #     const uint32_t bit = (symbol >> 7) & 1;
  #     rc_bit(rc, &subcoder[subcoder_index], bit);
  #
  #     symbol <<= 1;
  #     offset &= ~(match_byte ^ symbol);
  #
  #   } while (symbol < (UINT32_C(1) << 16));
  # }

  # Calculate base_offset using XZ Utils formula (same as encode_unmatched)
  # (((pos << 8) + prev_byte) & literal_mask) << lc
  context = (((pos << 8) + prev_byte) & literal_mask)
  base_offset = 3 * (context << lc)

  offset = 0x100
  symbol = byte + (1 << 8) # symbol += UINT32_C(1) << 8

  loop do
    # match_byte <<= 1;
    match_byte <<= 1

    # const uint32_t match_bit = match_byte & offset;
    match_bit = match_byte & offset

    # const uint32_t subcoder_index = offset + match_bit + (symbol >> 8);
    subcoder_index = base_offset + offset + match_bit + (symbol >> 8)

    # const uint32_t bit = (symbol >> 7) & 1;
    bit = (symbol >> 7) & 1

    # rc_bit(rc, &subcoder[subcoder_index], bit);
    range_encoder.encode_bit(models[subcoder_index], bit)

    # symbol <<= 1;
    symbol <<= 1

    # offset &= ~(match_byte ^ symbol);
    offset &= ~(match_byte ^ symbol)

    # } while (symbol < (UINT32_C(1) << 16));
    break if symbol >= (1 << 16)
  end
end

#encode_unmatched(byte, pos, prev_byte, lc, literal_mask, range_encoder, models) ⇒ void

This method returns an undefined value.

Encode literal byte in unmatched mode

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

XZ Utils literal_subcoder macro (from lzma_common.h:141-145):

((probs) + 3 * (((((pos) << 8) + (prev_byte)) & (literal_mask)) << (lc))

Parameters:

  • byte (Integer) —

    Byte value to encode (0-255)

  • pos (Integer) —

    Current position in stream

  • prev_byte (Integer) —

    Previous byte value

  • lc (Integer) —

    Literal context bits (0-8)

  • literal_mask (Integer) —

    Literal mask for context calculation

  • range_encoder (RangeEncoder) —

    Range encoder instance

  • models (Array<BitModel>) —

    Literal probability models



75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/omnizip/algorithms/lzma/literal_encoder.rb', line 75

def encode_unmatched(byte, pos, prev_byte, lc, literal_mask,
range_encoder, models)
  # Calculate base_offset using XZ Utils formula
  # (((pos << 8) + prev_byte) & literal_mask) << lc
  context = (((pos << 8) + prev_byte) & literal_mask)
  base_offset = 3 * (context << lc)
  model_index = 1
  bit_count = 8

  loop do
    # const uint32_t bit = (symbol >> --bit_count) & 1;
    bit_count -= 1
    bit = (byte >> bit_count) & 1

    # rc_bit(rc, &probs[model_index], bit);
    range_encoder.encode_bit(models[base_offset + model_index], bit)

    # model_index = (model_index << 1) + bit;
    model_index = (model_index << 1) + bit

    break if bit_count.zero?
  end
end