CODEWITHSUNDEEP
jpeg
DrPhill
DrPhill

Reputation: 632

Order of values in JPG DHT

I am writing a JPEG parser/modifier/unparser. First, to make sure we are using the same terninology I include
a definition adapted from a very useful source

DHT( Define Huffman Table) marker:



       Field             Size                              Description

  Marker Identifier    2 bytes   0xff, 0xc4 to identify DHT marker
  Length               2 bytes   This specify length of Huffman table
  HT information       1 byte    bit 0..3 : number of HT (0..3, otherwise error) 
                                 bit 4     : type of HT, 0 = DC table, 1 = AC table
                                 bit 5..7 : not used, must be 0
  Number of Symbols    16 bytes  Number of symbols with codes of length 1..16,
                                 the sum(n) of these bytes is the total number of 
                                 codes, which must be <= 256

  Symbols              n bytes   Table containing the symbols in order of 
                                 increasing code length ( n = total number of 
                                 codes ).

My Question: The Symbols must be ordered by increasing code length. But within each code length do they have to be ordered (eg by increasing value).

The reason I ask is that my table generated from frequencies collected from the AC scan data yields the right bit lengths, but they are not in increasing value order within the tree (when read in depth-first traversal order). I need to order these and regenerate the tree to get the same bit pattern as when I write and read my table.

I suspect that this is because in my write routine I specifically order the Symbols by bit length then value. If ordering by value is unnecessary I can remove the overhead (in code and at runtime).

Upvotes: 0

Views: 416

Answers (1)

user3344003
user3344003

Reputation: 21627

The codes are implicitly ordered by increasing value. The DHT marker only specifies the number of codes of each length. The procedure in the JPEG standard describes how to generate the actual Huffman code for each value.

Upvotes: 1

Related Questions