Resulting problems for a Java decoder implementation

some interesting aspects

io tool

Because of the bitwise nature of the MPEG stream a good io-tool is necessary to grab the next n bits and make them to be an integer with correct sign(!!!). This is a problem in Java because there isn't any unsigned type. The actual implementation works with a ring buffer and a shift register. The ring buffer offers the ability to "unget" some bytes. It is structured as Java - array with read- and write- "pointer". The size of the ring buffer is 8K. The hope is a fast loading of the MPEG source which ordinarily comes via network. From Version 1.11 on the ring buffer is substituted by a DataInputStream on top of a BufferedInputStream. This slightly speeds up the decoding process. Because the longest VLC is smaller than 32 bits the shift register is constituted as a long type value. By definition it is 64 bits long an so it is always possible to grab as much as bits from ring buffer as the longest VLC value has bits. A bit "pointer" shows the actual bit position.

The io tool is a Java class and there is only one instance.

How to decode the VLCs?

Because variable length codes (VLCs) are the "normal" case in MPEG a good VLC decoder is necessary. In other implementations it is written as an array with 2ⁿ entries, where n is the length of the longest VLC. So the decoder grabs always n bits knowing that some of them belong already to the next information field. The array is made such that the right value appears independent of the suffix not belonging to the VLC. A second entry in the array gives the number of bits of the VLC. Now the decoder knows: the rest belongs to the next information field.

Although this implementation is very fast it has a disadvantage: The array must contain 2ⁿ entries. Because the longest DCT value is 16 bit long the table would have 65536 entries. That is possible in C and C++. But some experiences with a Java inline FLC/FLI player show that WWW browsers allocate a relative small memory space. To avoid "out of memory space" errors I used another implementation.

Because the VLC is prefix free it can be regarded as a tree:

If you follow the weighted edges you get the VLC code by concatenating the weights to a bit string. Every leave is associated with the value belonging to this bit string. The figure above shows the same VLC as in the tables above.

I decided to implement the VLC decoder following this model. A two-dimensional array is established:

private static int vlc_vals[][] = {
	{1, 5, 0}, {-1, -1, 3}, {-1, -1, 5}, {-1, -1, 9},
	{3, -1, 0}, {2, 4, 0}, {-1, 5, 0}  
};

The entries correspond to the nodes of the VLC tree completed by an anchor node. The first component of each node is the index of the next node if the next bit is zero. The second component is the index of the next node if the next bit is one. In leave nodes these values are -1 that means NULL. If the node is a leave node it contains the value as last parameter. In intermediate nodes this value is set to zero.

Thus, the decoder works as follows:

public int[] decode(int max_length, int tab[][], io_tool mpeg_stream) {
	int idx1 = 0, idx = 0;
	max_length++;
	int maske = (1 << max_length);
	int bits = mpeg_stream.get_bits(max_length);

	while (idx != -1) {
		maske >>> 1;
		idx1 = idx;
		idx = ((bits & maske) != 0) ? tab[idx][1] : tab[idx][0];
		max_length--;
	}
	mpeg_stream.unget_bits(max_length + 1);
	return(tab[idx1]);
}

The calling method supports the maximum length of the code and the table to be consulted. The third parameter is the io-tool already associated with the MPEG stream. First the decoder increments the length because he must read one bit more to recognize the end of VLC code. Then he constructs a mask with only the highest bit set to one and grabs "max_length" bits from MPEG stream. Now the decoder traces along the edges until the index becomes -1. Important is to "unget" the bits not belonging to the VLC.

To return the "pointer" to the array entry instead of the value is advantageous because sometimes more than one value is associated with one VLC code. So the calling method can decide to use a fourth or a fifth value.

I implemented a test version with some debug messages. This implementation shows that the average loop count of the while loop above is 4.5 loops. So I think this implementation is a good compromise between memory size and speed.

How to implement the inverse cosine transform (IDCT)

You cannot implement the IDCT following the formula:

because this implies 45056 multiplications 12288 additions and 8192 calls of the cosine function. To implement the IDCT:

• Try to multi-use temporary intermediate results!
• Do not use float or double arithmetics! Instead of a integer arithmetic with virtual decimal point is applicable.
• And don't call any cosine function! The formula can be reordered such, that only constants appear as arguments of the cosine. These constants can be computed at compile time.

In contrast to the known libjpeg.a I used a 2D-discrete Fourier transform algorithm which ist described here.

Back to Java-inline-MPEG-Player