module

CrImage::WEBP::HuffmanEncoder

HuffmanEncoder builds Huffman trees and generates codes for entropy encoding.

Implements canonical Huffman coding with depth limiting for WebP. Supports both simple codes (1-2 symbols) and full Huffman trees with meta-Huffman encoding of code lengths.

Constants

CODE_LENGTH_ORDER = [17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

Code length order for meta-Huffman encoding (WebP specification)

Class methods

build_codes(histogram : Array(Int32), max_depth : Int32 = 15) : Array(HuffmanCode)

Builds Huffman codes from a frequency histogram with maximum depth limit.

Constructs optimal Huffman tree, computes code depths, limits depths to max_depth, and generates canonical codes.

Parameters:

  • histogram : Frequency count for each symbol
  • max_depth : Maximum code length (default: 15)

Returns: Array of HuffmanCode indexed by symbol

Special cases:

  • Empty histogram: Returns all zero-depth codes
  • Single symbol: Returns depth -1 (handled by simple code format)
Source
write_codes(writer : BitWriter, codes : Array(HuffmanCode)) : Nil

Writes Huffman codes to bitstream using simple or complex encoding.

Chooses between simple code format (1-2 symbols) and full Huffman encoding with meta-Huffman code lengths.

Simple format: Used when 1-2 symbols with values < 256 Complex format: Uses meta-Huffman to encode code lengths

Source
write_full_huffman_code(writer : BitWriter, codes : Array(HuffmanCode)) : Nil

Writes full Huffman code using meta-Huffman encoding.

Encodes code lengths using a separate Huffman tree (meta-Huffman), then writes the actual code lengths. This two-level approach compresses the code length data.

Source