**decode_tiles(sz - headerBytes)**, near the bottom. These functions are deeply nested, but by the end it will only be 4 levels so don't worry if it seems like each function leads to something else.

Here's what

**decode_tiles()**looks like.

Now we need to define some state variables. Open Notepad++ and begin by adding the lines tileCols, tileRows, MiRowStart, MiRowEnd, MiColStart, and MiColEnd. Save it as state.txt.

There are a few more to add. Just add the name (ie MiCols) and the end value, not the formulas. For example, you should have "MiCols 120".

MiCols = (FrameWidth + 7) >> 3 = 120

MiRows = (FrameHeight + 7) >> 3 = 68

Sb64Cols = (MiCols + 7) >> 3 = 15

Sb64Rows = (MiRows + 7) >> 3 = 9

We'll need to keep this updated as we go along because some future functions depend on these values and it's easy to find them at the beginning.

Now let's fill in the values. We'll start with tileCols and tileRows. They depend on log2 functions. For our image, we opted (in the uncompressed header) to leave the log2 values at 0 because 2 ^ 0 = 1 and we only want 1 tile. So, tileCols = 1 << 0 (1 left-shift 0), which equals 1. tileRows works the same way so it will also equal 1. Therefore, we have 1 tile column and 1 tile row for a total of 1 tile. Fill in tileCols and tileRows in the text file.

Do you see the nested FOR loops,

**for (tileRow = 0...**and

**for (tileCol = 0...**? Since we only have 1 tileCol and 1 tileRow, these will execute only once. Therefore, we can pretend these loops don't exist and just perform everything once.

The first thing being done is the statement

lastTile = (tileRow = tileRows - 1) AND (tileCol = tileCols - 1)

= (0 = 0) AND (0 = 0)

= (TRUE) AND (TRUE)

Both conditions are met, so lastTile will be TRUE. Now we look at the IF block,

**if (lastTile)**. Since lastTile is TRUE, all we have to do is

**tile_size = sz**. But don't worry about that statement. We can't know it right now anyway.

Skipping the ELSE block, we have the MiRow/MiCol statements. Let's start evaluating these.

**tileRow**and

**tileCol**will be 0.

MiRowStart = get_tile_offset( tileRow, MiRows, tile_rows_log2 )

MiRowEnd = get_tile_offset( tileRow + 1, MiRows, tile_rows_log2 )

MiColStart = get_tile_offset( tileCol, MiCols, tile_cols_log2 )

MiColEnd = get_tile_offset( tileCol + 1, MiCols, tile_cols_log2 )

Here's what get_tile_offset() looks like.

MiRowStart = 0

MiRowEnd = 68

MiColStart = 0

MiColEnd = 120

Copy and paste these values into your text file. You'll need them later on.

The next statement is

**init_bool(tile_size)**, but since we're encoding we don't worry about that. That's for decoders to do. What we will do, however, is start our boolean encoder once we have some values to write.

Finally, the exciting part:

**decode_tile()**. This is where our image data will go.

### decode_tile()

To decode the single tile in the image, we have 2 nested FOR loops. The outer loop iterates through Rows, and the inner loop iterates through Columns. In X/Y terms, the row is Y and the column is X. So, you can see that the outer loop runs through Y while the inner loop runs through X. These FOR loops increment in steps of 8 because the Mi series of variables represents 8-pixel increments. Incrementing these by 8 equates to incrementing by 64, the size of a superblock.

Inside the nested loops, we have clear_left_context(). This just says that every time we finish a horizontal line and jump back to the left, we have to forget everything about the previous line's left side. Notice that it's only inside the outer loop.

In the inner loop, we iterate through superblocks (64x64 blocks). That's what

**decode_partition(r, c, BLOCK_64X64)**does. Recall at the beginning how I said that VP9 images are broken into 64x64 superblocks. This is where that happens. Basically, this loop goes left-to-right from the top to the bottom, processing superblocks.
So for the first superblock, we'll be executing the statement

**decode_partition(0, 0, BLOCK_64X64)**.
These decoding functions are already nested pretty deep. Later I'll draw a diagram to show which functions we're running.

We can forget the first IF statement since it only applies to right or bottom edges of the image.

Add the following variables to your text file:

**num8x8**= 8

**halfBlock8x8**= 4

**hasRows**= true

**hasCols**= true

Now here's a hard part.

**partition**is a Tree, a binary tree specifically. A video on these is shown below. We need to encode a value that says we want**PARTITION_SPLIT**so we can split the superblock into 4 32x32 blocks. We could say**PARTITION_NONE**and it would still yield 4 32x32 blocks, but then they would share a prediction mode (smudge function) and for better compression, we want each block to specify its own prediction mode. Using**PARTITION_SPLIT**lets us choose on a per-block basis.I had trouble with this part, but fortunately Ronald Bultje explained it to me and I drew a diagram of what he described. Here's my drawing of what the partition binary tree should look like.

(Advanced theory, not necessary to continue)

Credit: Ronald Bultje, in a chat with me on Nov 29, 2017

Here's the

*decoding*side of this tree. I show it so we can work it backwards to encode.

The T[] array is the tree, which according to the spec is an array of integers. In this case it's

**partition_tree[]**which may be found in the spec PDF.

Notice that

**read_bool()**expects a probability,

**P(n >> 1)**. The >> is a logical shift of 1 bit, to the right. To find the probability to use when writing, we need to first run a complicated unnamed function (below).

To make a long story short,

**ctx**will equal 15 at the end.

When the tree decoding function (9.3.3 Tree decoding process, above) first runs,

**n**= 0. That means

**read_bool()**will use

**P(0 >> 1)**or just

**P(0)**as the probability. Let's derive

**P(0)**.

hasRows = 1 (true) and hasCols = 1 (true). FrameIsIntra = 1 (true). This means we'll get our probability from

**partition_probs[ctx][node2]**. We know that

**ctx**is 15 and

**node2**=

**node**= 0. So, we will retrieve the value

**partition_probs[15][0]**.

But there's a problem here. There's no such table as

**partition_probs**in the VP9 spec PDF. How will we get the number we need? It turns out that we will use

**default_partition_probs[15][0]**, since we decided before that we would just use default probabilities.

**default_partition_probs[15][0]**= 10. So, our function will be

**read_bool(10)**. This means we need to write a 1 to the bitstream with a probability of 10. Let's keep a running tally of our bits and their probabilities, since we can't stop to write them now.

Running tally of bits

1, p = 10

Because we wrote a 1,

**read_bool()**will return 1 when the video is decoded. Now refer to the binary tree shown above. Since we wrote a 1, we have a choice to write either 0 for a horizontal split (2 64x32's) or write another 1. We write another 1, and notice that we have to write just one more 1 to get Split.
Here are the passes the function will go through on the decode side:

- n starts at 0. At the end, n = 2, which equals T[0 + read_bool(P(0 >> 1))] = T[1]
- n starts at 2. At the end, n = 4, which equals T[2 + read_bool(P(2 >> 1))] = T[3]
- n starts at 4. At the end, n = 5, which equals T[4 + read_bool(P(4 >> 1))] = T[5]

Since T[5] = -

**PARTITION_SPLIT**(negative**PARTITION_SPLIT**) and the loop condition is that n is above 0, we exit the loop and return**PARTITION_SPLIT**without the negative sign. This means the**decode_partition()**function (section 6.4.3, shown near the beginning) now knows that we want the current superblock to be broken into 4 32x32 blocks. The**partition**variable in that function will equal**PARTITION_SPLIT**.
Before we start writing more bits, we need to know the probabilities to use. Notice that, during our tree loop,

**P(n >> 1)**was changing. First it was P(0), then P(1), then P(2). We know that**default_partition_probs[15][0]**= 10, but what about**default_partition_probs[15][1]**and**default_partition_probs[15][2]**? Well, those are 7 and 6, respectively. The designers knew that the chance of a 0 diminishes as we go further down the tree, so they set the default probabilities accordingly.
Now that we have our probabilities, let's add the bits to our list.

Running tally of bits

1, p = 10

1, p = 7

1, p = 6

That was quite a lot. So where are we? Now that we know how to tell the video player that we want 4 32x32 blocks, we can go back to section 6.4.3,

**decode_partition()**.
Just under

**partition**is**subsize = subsize_lookup[ partition][ bsize ]**. We know**partition**now, so we can plug it in.**bsize**is BLOCK_64X64. Basically,**subsize_lookup**lets us plug in a partition type along with our current block size and see how big the resulting block(s) would be. In our case,**subsize**will be 9 which corresponds to BLOCK_32X32.
Now we have a bunch of IF statements to go through. The first one checks if subsize is less than 8x8 or equal to 64x64. Neither of those is the case, so we move on to check if it's a horizontal split (64x32 in our case) and then we check if it's a vertical split (32x64 in our case). The ELSE block at the end of the IF statement reflects that if none of those conditions were met, which they weren't, then the only other possibility is a PARTITION_SPLIT.

Notice that inside the ELSE block, we have 4

**decode_partition()**statements. These are processed in raster order within the superblock. This means that superblocks are processed in raster order, and blocks within superblocks are processed the same way.
We're done here since we're calling

**decode_partition()**again. When a function calls itself, as**decode_partition()**is doing right now, it's called*recursion*. In this case we have to recursively call ourselves to decode each of the 4 32x32's. Now would be a good time for a diagram of where we are.
## No comments:

## Post a Comment