Using Subtables

Subtables are used for large source tables. Internally, VLC decoding is done by table lookups. A straightforward approach would be to have one lookup of a lookup table of size 2L, where L is the maximum number of code bits. This approach however is proven to be memory inefficient. Therefore, subtables are used to balance the memory and the lookup speed. Using subtables reduces the memory size but increases the number of lookups. The greater is the number of subtables, the smaller is the structure size but the number of decoding operations increases. A table structure of this kind provides the optimal ratio between the table redundancy and the number of decoding operations. Each subtable works on some numbers of bits out of L. In the ippiVCHuffmanInitAlloc_32s and ippiVCHuffmanInitAllocRL_32s functions subtables sizes are specified manually. Any combinations of subtables are possible as long as their sum adds up to L.

Consider an example of VLC decoding. The table below gives the codes and their values.

Example of VLC Decoding  
Code     Value
0 A
1100 B
101 C
1110 D
100 E
11110 F
11111 G
1101 H

First, let us consider decoding when subtables are not used. In this case, the source table should look as follows:

static Ipp32s Table[]=
{
5,                           // The maximum length of code
1,                           // The total number of all subtables
5,                           // The size of 1 subtable
1,                           // The number of 1-bit codes
0/*0*/,A,                    // code1, value1
0,                           // The number of 2-bit codes
2                            // The number of 3-bit codes
5/*101*/,C,                  // code1, value1
4/*100*/,E,                  // code2, value2
3                            // The number of 4-bit codes
12/*1100*/,B,                // code1, value1
14/*1110*/,D,                // code2, value2
13/*1101*/,H,                // code3, value3
2                            // The number of 4-bit codes
30/*11110*/,F,               // code1, value1
31/*11111*/,G,               // code2, value2
-1
};
 

The function ippiVCHuffmanInitAlloc_32s is used to form a structure that contains the following data:

Structure Data For a Case With One Subtable  
Code (length=5) Value Length
00000 A 1
00000 A 1
... ...  
01111 A 1
10100 C 3
10101 C 3
10110 C 3
10111 C 3
10000 E 3
10000 E 3
10000 E 3
10000 E 3
11000 B 4
11001 B 4
11100 D 4
11101 D 4
11010 H 4
11011 H 4
11110 F 5
11111 G 5

In process of decoding, 5 bits are extracted from the bitstream. They are used to find a corresponding code in the above table and matching value and length. (5-Length) bits are returned to the bitstream.

Now, consider an example when two subtables are used for decoding. The source table structure will look as follows: static Ipp32s Table[]=
{
5, // The maximum length of code
2, // The total number of all subtables
3, // The size of subtable 1
2, // The size of subtable 2
1, // The number of 1-bit codes
0/*0*/,A, // code1, value1
0, // The number of 2-bit codes
2 // The number of 3-bit codes
5/*101*/,C, // code1, value1
4/*100*/,E, // code2, value2
3 // The number of 4-bit codes
12/*1100*/,B, // code1, value1
14/*1110*/,D, // code2, value2
13/*1101*/,H, // code3, value3
2 // The number of 4-bit codes
30/*11110*/,F, // code1, value1
31/*11111*/,G, // code2, value2
-1
};
 

The function ippiVCHuffmanInitAlloc_32s is used to form a structure that contains two subtables:

VLC Subtables



Subtable 1 contains the values with the code length that does not exceed 3. Subtable 2 contains the values with the code length that exceeds 3, with the corresponding code consisting of 3-bit code from Subtable 1 and 2-bit code from Subtable 2.

In process of decoding 3 bits are extracted from the bitstream. They are used to find a corresponding code in Subtable 1. The matching value and length are found if the code is other than 100 or 111. (3-Length) bits are returned to the bitstream. Otherwise, two more bits are extracted from the bitstream to find respective value and length in Subtable 2 and (2-Length) bits are returned to the bitstream afterwards.

ppBitStream and pOffset Parameters

Before decoding and applying the Intel IPP functions, all bytes in each 32-bit double word in the bit stream must be flipped (see the figure below) to improve performance of decoding functions.

Flipping of Bytes



The parameters ppBitStream and pOffset define start position for a subsequent code: current element of the array and position in this element. These parameters are updated by function.

ppBitStream

Double pointer to the current position in the bitstream.

pOffset

Pointer to the offset between the bit that **ppBitStream points to and the start of the code.

See the figure below for an example of getting one code from the bitstream.

Getting One Code From Bitstream



Optimization Notice

The Intel® Integrated Performance Primitives (Intel® IPP) library contains functions that are more highly optimized for Intel microprocessors than for other microprocessors. While the functions in the Intel® IPP library offer optimizations for both Intel and Intel-compatible microprocessors, depending on your code and other factors, you will likely get extra performance on Intel microprocessors.

While the paragraph above describes the basic optimization approach for the Intel® IPP library as a whole, the library may or may not be optimized to the same degree for non-Intel microprocessors for optimizations that are not unique to Intel microprocessors. These optimizations include Intel® Streaming SIMD Extensions 2 (Intel® SSE2), Intel® Streaming SIMD Extensions 3 (Intel® SSE3), and Supplemental Streaming SIMD Extensions 3 (Intel® SSSE3) instruction sets and other optimizations. Intel does not guarantee the availability, functionality, or effectiveness of any optimization on microprocessors not manufactured by Intel. Microprocessor-dependent optimizations in this product are intended for use with Intel microprocessors.

Intel recommends that you evaluate other library products to determine which best meets your requirements.

The VLC functions are used in the decoders included into Intel® IPP Samples. See the introduction to Video Coding.


Submit feedback on this help topic

Copyright © 2000 - 2010, Intel Corporation. All rights reserved.