What do these two parts of libavcodec/h263data.h do exactly?

Question

Below are two segments of code from the FFMPEG library, specifically located here: libavcodec/h263data.h (http://ffmpeg.org/doxygen/0.6/h263data_8h-source.html).

I would like to know more about how these two segments operate in the larger context of the codec library. Below, after these examples, I describe my understanding thus far and provide two clearer questions that I would like answers on.

Thank you for any help!

EXAMPLE 1

00035 /* intra MCBPC, mb_type = (intra), then (intraq) */
00036 const uint8_t ff_h263_intra_MCBPC_code[9] = { 1, 1, 2, 3, 1, 1, 2, 3, 1 };
00037 const uint8_t ff_h263_intra_MCBPC_bits[9] = { 1, 3, 3, 3, 4, 6, 6, 6, 9 };

AND EXAMPLE 2

00039 /* inter MCBPC, mb_type = (inter), (intra), (interq), (intraq), (inter4v) */
00040 /* Changed the tables for interq and inter4v+q, following the standard ** Juanjo ** */
00041 const uint8_t ff_h263_inter_MCBPC_code[28] = {
00042     1, 3, 2, 5,
00043     3, 4, 3, 3,
00044     3, 7, 6, 5,
00045     4, 4, 3, 2,
00046     2, 5, 4, 5,
00047     1, 0, 0, 0, /* Stuffing */
00048     2, 12, 14, 15,
00049 };

I understand that we're looking at a small part of the larger library of compression algorithms that affect orthogonal schemes, which predict the “correct,” or more aptly put, "original" inter- or intra-motion vectors, which are represented here in the names "ff_h263_inter_MCBPC_code," "ff_h263_intra_MCBPC_code," and "ff_h263_intra_MCBPC_bits."

I know that the names in these two blocks of code demarcate the following:

1. const refers to the declaration of a read only variable that can still be used outside of its scope like any other variable. The difference, stated in another way, is that the values in this array cannot be changed by any methods called outside of itself.

2. uint8_t is an unsigned integer with a length of 8 bits that is part of a C99 standard, which is called "fixed width integer types." This particular type, an “exact width integer,” computes a range of signed or unsigned bits with a minimum value of 0 and a maximum value of 8, (i.e., the 8x8 macroblocks), which guarantees this number of bits across platforms, whether, let's say, 32-bit or 64-bit operating systems. (I researched this bit here: “Fixed width integer types” http://en.wikipedia.org/wiki/Stdint.h#stdint.h)

3. MCBPC refers to Macroblock Type & Coded Block Pattern for Chrominance, but I don't fully understand the exact role of these particular arrays are in the scheme of the file and libavcodec. I understand more conceptually, than I do the details/number values defined in these examples.

So, considering this, here's what I would like to know more about:

1. Is my understanding, thus far, off in any way?

2. Can someone help breakdown what each code segment does? more specifically, what do these number values signify/do in each case?

3. What does "Stuffing" mean?

Thank you, again, for any help in this matter!

Answer 1

Let's start with this pair of arrays since it's shorter:

const uint8_t ff_h263_intra_MCBPC_code[9] = { 1, 1, 2, 3, 1, 1, 2, 3, 1 };
const uint8_t ff_h263_intra_MCBPC_bits[9] = { 1, 3, 3, 3, 4, 6, 6, 6, 9 };

FFmpeg feeds these into this function in ituh263dec.c:

INIT_VLC_STATIC(&ff_h263_intra_MCBPC_vlc, INTRA_MCBPC_VLC_BITS, 9,
         ff_h263_intra_MCBPC_bits, 1, 1,
         ff_h263_intra_MCBPC_code, 1, 1, 72);

FFmpeg uses these pairs of bits/codes arrays to set up variable length codes (VLCs), a.k.a. Huffman codes. In this case, the function will initialize a data structure named ff_h263_intra_MCBPC_vlc. The fact that there are 9 items in each array means that there are 9 possible values (0..8). the first item is code 1 and 1 bit long. The second item is also code 1 but has a length of 3. That means, in binary, it is 001. Let's expand this out:

value  code  bitcount  bits
  0      1       1     1
  1      1       3     001
  2      2       3     010
  3      3       3     011
  4      1       4     0001
  5      1       6     000001
  6      2       6     000010
  7      3       6     000011
  8      1       9     000000001

The decoder will be able to leverage the ff_h263_intra_MCBPC_vlc data structure by feeding the bitstream into it and getting a value back out, ranging from (0..8), then consuming somewhere between (1..9) bits from the stream.

As for your question: What does "Stuffing" mean?, note that in both the codes and bits arrays, there are entries that are 0-- i.e., the code is 0 and it's 0 bits long. Those are invalid values. Since these arrays have 28 values ranging from (0..27). This means that 21, 22, and 23 can't be represented.

I hope I've answered your questions about the mechanics of how FFmpeg handles these arrays (and I hope that was the main substance of your query).

Pretty Picture Time:

Huffman/VLC codes are usually illustrated using trees. Starting from the top, a 0 travels to the left and a 1 travels to the right. When you get reach a leaf node, you have decoded a value.