Class: Omnizip::Formats::Rar::Compression::LZ77Huffman::Encoder

Inherits:
Object
  • Object
show all
Defined in:
lib/omnizip/formats/rar/compression/lz77_huffman/encoder.rb

Overview

RAR LZ77+Huffman encoder

Implements compression using LZ77 string matching combined with Huffman coding for symbol encoding.

Simplified Huffman Tree Format (MVP)

This implementation uses a simplified tree format for portability and ease of implementation. The format differs from official RAR but maintains full compatibility between encoder and decoder.

Format Structure:

[16-bit num_symbols] [code_lengths...]
      2 bytes         512 × 4 bits = 256 bytes

Details:

  • Header: 16-bit number of symbols (always 512 for MVP)

    • 0-255: Literal bytes
    • 256: End-of-block marker
    • 257-511: LZ77 match symbols

  • Code Lengths: 4 bits per symbol × 512 symbols = 2048 bits

    • Each symbol gets a 4-bit code length (0-15)
    • Length 0 means symbol not used
    • Lengths build canonical Huffman tree

Trade-offs:

  • Fixed Overhead: 258 bytes (2 + 256) per block
  • Simplicity: Easy to implement and debug
  • Portability: Pure Ruby, no external dependencies
  • Compatibility: Encoder/decoder use identical format

Real RAR Format Differences:

Real RAR uses a more complex format with:

  • RLE compression of code lengths
  • Multiple Huffman tables (MC, LD, RC, LDD)
  • Adaptive tree updates
  • More efficient length encoding

The simplified format is sufficient for MVP and can be upgraded to full RAR format in future versions without breaking the API.

See Also:

Constant Summary collapse

LITERAL_SYMBOLS = 
(0..255)
END_OF_BLOCK = 
256
MATCH_SYMBOLS = 
(257..511)
MIN_MATCH_LENGTH = 
3
MAX_MATCH_LENGTH = 
257

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(output, _options = {}) ⇒ Encoder

Returns a new instance of Encoder.



64
65
66
67
68
69
70
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/encoder.rb', line 64

def initialize(output, _options = {})
  @output = output
  @bit_stream = BitStream.new(output, :write)
  @match_finder = MatchFinder.new
  @huffman_builder = HuffmanBuilder.new
  @compressed_size = 0
end

Instance Attribute Details

#compressed_size ⇒ Object (readonly)

Returns the value of attribute compressed_size.



62
63
64
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/encoder.rb', line 62

def compressed_size
  @compressed_size
end

Instance Method Details

#encode(input) ⇒ Object 



72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/encoder.rb', line 72

def encode(input)
  data = input.is_a?(String) ? input : input.read
  return 0 if data.empty?

  start_pos = @output.pos
  items = collect_items(data)
  codes = @huffman_builder.generate_codes
  write_huffman_tree(codes)

  items.each do |item|
    if item[:type] == :literal
      encode_literal(item[:value], codes)
    else
      encode_match(item[:offset], item[:length], codes)
    end
  end

  encode_symbol(END_OF_BLOCK, codes)
  @bit_stream.flush
  @compressed_size = @output.pos - start_pos
end