Module: PureJPEG::Huffman

Defined in:
lib/pure_jpeg/huffman/tables.rb,
lib/pure_jpeg/huffman/decoder.rb,
lib/pure_jpeg/huffman/encoder.rb

Defined Under Namespace

Classes: DecodeTable, Encoder, FrequencyCounter

Constant Summary collapse

DC_LUMINANCE_BITS =

Standard Huffman tables from JPEG Annex K. Each table is defined by bits (number of codes of each length 1-16) and values (the symbol for each code, in order).

[0, 1, 5, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0].freeze
DC_LUMINANCE_VALUES = 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11].freeze
AC_LUMINANCE_BITS = 
[0, 2, 1, 3, 3, 2, 4, 3, 5, 5, 4, 4, 0, 0, 1, 0x7D].freeze
AC_LUMINANCE_VALUES = 
[
  0x01, 0x02, 0x03, 0x00, 0x04, 0x11, 0x05, 0x12,
  0x21, 0x31, 0x41, 0x06, 0x13, 0x51, 0x61, 0x07,
  0x22, 0x71, 0x14, 0x32, 0x81, 0x91, 0xA1, 0x08,
  0x23, 0x42, 0xB1, 0xC1, 0x15, 0x52, 0xD1, 0xF0,
  0x24, 0x33, 0x62, 0x72, 0x82, 0x09, 0x0A, 0x16,
  0x17, 0x18, 0x19, 0x1A, 0x25, 0x26, 0x27, 0x28,
  0x29, 0x2A, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39,
  0x3A, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49,
  0x4A, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59,
  0x5A, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69,
  0x6A, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79,
  0x7A, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x89,
  0x8A, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98,
  0x99, 0x9A, 0xA2, 0xA3, 0xA4, 0xA5, 0xA6, 0xA7,
  0xA8, 0xA9, 0xAA, 0xB2, 0xB3, 0xB4, 0xB5, 0xB6,
  0xB7, 0xB8, 0xB9, 0xBA, 0xC2, 0xC3, 0xC4, 0xC5,
  0xC6, 0xC7, 0xC8, 0xC9, 0xCA, 0xD2, 0xD3, 0xD4,
  0xD5, 0xD6, 0xD7, 0xD8, 0xD9, 0xDA, 0xE1, 0xE2,
  0xE3, 0xE4, 0xE5, 0xE6, 0xE7, 0xE8, 0xE9, 0xEA,
  0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7, 0xF8,
  0xF9, 0xFA
].freeze
DC_CHROMINANCE_BITS = 
[0, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0].freeze
DC_CHROMINANCE_VALUES = 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11].freeze
AC_CHROMINANCE_BITS = 
[0, 2, 1, 2, 4, 4, 3, 4, 7, 5, 4, 4, 0, 1, 2, 0x77].freeze
AC_CHROMINANCE_VALUES = 
[
  0x00, 0x01, 0x02, 0x03, 0x11, 0x04, 0x05, 0x21,
  0x31, 0x06, 0x12, 0x41, 0x51, 0x07, 0x61, 0x71,
  0x13, 0x22, 0x32, 0x81, 0x08, 0x14, 0x42, 0x91,
  0xA1, 0xB1, 0xC1, 0x09, 0x23, 0x33, 0x52, 0xF0,
  0x15, 0x62, 0x72, 0xD1, 0x0A, 0x16, 0x24, 0x34,
  0xE1, 0x25, 0xF1, 0x17, 0x18, 0x19, 0x1A, 0x26,
  0x27, 0x28, 0x29, 0x2A, 0x35, 0x36, 0x37, 0x38,
  0x39, 0x3A, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48,
  0x49, 0x4A, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58,
  0x59, 0x5A, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68,
  0x69, 0x6A, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78,
  0x79, 0x7A, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
  0x88, 0x89, 0x8A, 0x92, 0x93, 0x94, 0x95, 0x96,
  0x97, 0x98, 0x99, 0x9A, 0xA2, 0xA3, 0xA4, 0xA5,
  0xA6, 0xA7, 0xA8, 0xA9, 0xAA, 0xB2, 0xB3, 0xB4,
  0xB5, 0xB6, 0xB7, 0xB8, 0xB9, 0xBA, 0xC2, 0xC3,
  0xC4, 0xC5, 0xC6, 0xC7, 0xC8, 0xC9, 0xCA, 0xD2,
  0xD3, 0xD4, 0xD5, 0xD6, 0xD7, 0xD8, 0xD9, 0xDA,
  0xE2, 0xE3, 0xE4, 0xE5, 0xE6, 0xE7, 0xE8, 0xE9,
  0xEA, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7, 0xF8,
  0xF9, 0xFA
].freeze

Class Method Summary collapse

Class Method Details

.build_table(bits, values) ⇒ Object

Build a lookup table: symbol -> [code, code_length] from the bits/values specification. Returns an Array indexed by symbol value for O(1) lookup.



68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/pure_jpeg/huffman/tables.rb', line 68

def self.build_table(bits, values)
  table = Array.new(256)
  code = 0
  k = 0

  16.times do |i|
    bits[i].times do
      table[values[k]] = [code, i + 1]
      k += 1
      code += 1
    end
    code <<= 1
  end

  table
end

.optimize_table(frequencies) ⇒ Object

Build a JPEG canonical Huffman table definition from symbol frequencies. Returns [bits, values], where bits has 16 entries for code lengths 1..16.



87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
# File 'lib/pure_jpeg/huffman/tables.rb', line 87

def self.optimize_table(frequencies)
  lengths = build_code_lengths(frequencies)
  counts = length_counts(lengths)
  trim_counts_to_jpeg_limit!(counts)

  symbols = (0...256).select { |symbol| frequencies[symbol].positive? }
  symbols.sort_by! { |symbol| [-frequencies[symbol], symbol] }

  bits = Array.new(16, 0)
  values = []
  index = 0

  1.upto(16) do |length|
    count = counts[length]
    bits[length - 1] = count
    count.times do
      values << symbols[index]
      index += 1
    end
  end

  [bits.freeze, values.freeze]
end