{"id":219,"date":"2006-03-12T14:56:05","date_gmt":"2006-03-12T22:56:05","guid":{"rendered":"http:\/\/multimedia.cx\/eggs\/?p=219"},"modified":"2006-03-12T15:07:44","modified_gmt":"2006-03-12T23:07:44","slug":"aac-puzzles","status":"publish","type":"post","link":"https:\/\/multimedia.cx\/eggs\/aac-puzzles\/","title":{"rendered":"AAC Puzzles"},"content":{"rendered":"

You thought those Pickover puzzles<\/a> were inane? Well, you were right. But it does help to keep a programmer sharp on pure computer science skills. One reason I have been having such a good time reverse engineering the FAAD2<\/a> source is because it represents a bunch of little puzzles. Only they’re considerably more straightforward and grounded in reality than the Pickover puzzles. If these puzzles were on a Pickover calendar page, they would be worded along the lines of, <\/p>\n

“There are 8,192 numbers stored in a table called iq_table. 0, 1, 2.5198420997897464, 4.3267487109222245, all the way up to 165113.4940829452. What is the common property that connects all of these numbers?”\n<\/p><\/blockquote>\n

The answer (thanks to Jindrich Makovicka for pointing this out on the ffmpeg-devel list) is that each number is its index (0..8191) raised to an exponent of 4\/3: iq_table[index] = index4\/3<\/sup>. Here are some more puzzles:<\/p>\n

<\/p>\n

Split an 8-bit quantity into an exponent (top 6 bits) and fraction (bottom 2 bits). Multiply number<\/em> by quantities from 2 tables indexed by the fraction and the exponent:<\/p>\n

\r\n  number *= pow2sf_tab[exponent];\r\n  number *= pow2_table[fraction];\r\n<\/pre>\n
pow2sf_tab is defined as:<\/p>\n
\r\n  foreach i in -25..38\r\n    pow2sf_tab[i] = 2i<\/sup>\r\n<\/pre>\n
while pow2_table is defined as:<\/p>\n
\r\n  foreach i in 0..3\r\n    pow2_table[i] = 2i\/4<\/sup>\r\n<\/pre>\n
Question: What is the distilled mathematical operation that is being performed on number<\/em>?<\/p>\n
As mentioned previously<\/a>, I am writing a new AAC spec<\/a>. Part of that process is gathering up all of the Huffman tables and formatting them in such a way that they can be easily imported into FFmpeg<\/a>. There are a 12 different hardcoded Huffman tables in use in AAC decoding. Tables 1..10 are used for coding quads or pairs of spectral coefficients. I’m not entirely sure what table 11 is for yet. Then there is a scalefactor Huffman table. Based on the specific table, FAAD2 uses 2 different methods for decoding. For 5 of the tables (3, 5, 7, 9, and scalefactors), FAAD2 uses a textbook tree-based Huffman decoder. The remainder of the spectral coefficient tables use a more efficient table-based approach.<\/p>\n
I have written 2 different programs (1 for scalefactors and 1 for tables 3, 5, 7, and 9) to convert the binary tree tables to tables that FFmpeg can more easily use (converted tables are available in the MultimediaWiki<\/a>). I decided to make this AAC documentation more of a community effort. That, and I’m too lazy to finish solving this particular problem so I am throwing it out there to see if someone else wants to do it while I work on the new spec some more. The challenge is to convert Huffman tables 1, 2, 4, 6, 8, and 10 to the { codeword, code length, data }<\/em> format that FFmpeg will be able to use.<\/p>\n
The codebooks are here<\/a>. For example, Huffman table 1 is in hcb_1.h. It has 2 tables: hcb1_1[] and hcb1_2[]. The step 1 table contains data sets such as:<\/p>\n
\r\n  ...\r\n    { \/*       *\/ 0, 0 },\r\n    { \/* 10000 *\/ 1, 0 },\r\n  ...\r\n <\/pre>\n
The first number is offset while the second number denotes extrabits. The step 2 table contains data such as:<\/p>\n
\r\n  ...\r\n    { 5,  1,  0,  0,  0 },\r\n    { 5, -1,  0,  0,  0 },\r\n  ...\r\n<\/pre>\n
The first number represents the total number of bits in the codeword and the next 4 numbers are the components of the spectral coefficient quad. The method for decoding based on these tables is:<\/p>\n