BS (MDEC Bitstream Data)

Compressed image data that MDEC and libpress decode.

Overview

BS is the image data format used by MDEC and libpress. Original MDEC image data is a series of 24-bit RGB images arranged over time, and each image is called a frame. A frame is a multiple of 16 pixels wide by a multiple of 16 pixels tall, and a source of any other size needs additional processing. Because MDEC does not use correlations between frames, each frame can be processed independently.¹²

Macroblocks

MDEC treats each frame as a collection of small regions of 16x16 pixels, which are called macroblocks. A 320x240 image, for example, is split into 16x16 macroblocks and each macroblock is then compressed. MDEC writes the decoded results back to main memory as macroblocks, and the CPU and the GPU reconstruct the frame from them.¹

When encoding, the pixels of a frame are reordered so that each macroblock is unified. The encoder orders the macroblocks vertically from the top left. This reduces the number of times the frame buffer transfer command (LoadImage) is executed during playback.²

Color Space Conversion

MDEC performs its internal processing in the YCbCr color system, so RGB macroblocks must be converted to YCbCr. This process is called CSC (Color Space Conversion). It can be understood as a coordinate transformation in the three-dimensional space formed by the R, G and B components. MDEC converts YCbCr to RGB with the following matrix:³

The inverse of this matrix is used to convert from RGB to YCbCr, and the MOVCONV encoder uses it:³

Physically, Y is the luminance signal and Cb and Cr are the color-difference signals. The PlayStation converts the RGB frame buffer to YCbCr for its video (S terminal) output, and the monitor converts the signal back to RGB. Because so many color space conversions are performed, the final color can differ from the expected color through gamma correction or the conversion matrices.³

Blocks

The luminance signal generally needs higher resolution than the color-difference signals. The color-difference data is therefore reduced to 1/4 (1/2 in x and 1/2 in y), while Y is split into four 8x8 blocks. A 16x16 macroblock consequently becomes two color-difference blocks and four luminance blocks, and each 8x8 unit is called a block. The blocks are arranged in the following order:⁴

The color-difference blocks can be reduced by taking only the even-numbered points, but elements at or over 1/4 of the sampling frequency are then carried over as aliasing noise. MOVCONV instead averages four adjacent points, which acts as a two-dimensional lowpass filter and gives better results. Some aliasing still remains, and a filter with more dimensions would need more encoding time.⁴

Block Offset

In 8-bit YCbCr, Y ranges from 0 to 255 while Cb and Cr range from -128 to +127. To unify the ranges of the luminance and color-difference blocks, 128 is subtracted from every luminance value. During decoding MDEC checks whether a block is a luminance block and, if it is, adds 128 to return the value to its original range.⁵

Encoding

DCT

DCT (Discrete Cosine Transformation) is applied to each block of the macroblock. It is an orthogonal transformation Y = P x X x Pt of the 8x8 block X, where P x Pt is the unit matrix. IDCT is therefore DCT with P replaced by its transpose.⁵

Physically, DCT is a frequency transformation. Element (0,0) of the result is the DC element and equals the average of the block. The other elements are AC elements whose frequency rises to the right and down. In natural images the values grow smaller toward the bottom right, and compression with DCT takes advantage of this tendency.⁶

Quantization

After DCT each element is quantized by dividing it by the product of its quantization table (Q table) entry and QUANT, which sets the quantization step for the whole block. DC elements are not affected by QUANT. MDEC currently uses the same table for luminance and color-difference blocks:⁶

The table values increase toward the bottom right because high-frequency elements need less accuracy than low-frequency elements. A large QUANT loses more data and lowers the image quality after decoding. However, it also increases the number of zero elements and therefore decreases the size of the run-level data.⁶⁷

Zig-zag Transformation

The quantized block is numbered one-dimensionally in zig-zag order, and quantization and the zig-zag transformation are performed together. The order starts from the low-frequency elements, so more zero elements fall toward the end of the series and run-level compression becomes easier. The scan order is as follows:⁷

Run-level Data

Runlevel Code

Zig-zag ordered blocks tend to contain sequences of zeros, so the data is compressed by combining runs of zeros. This is called runlevel conversion. Each code is a pair (run, level), in which run is the number of zeros before a value and level is the value of the element. An actual runlevel code has 16 bits:⁸

The first code of a block always has a run of 0, even when the DC element is 0. The quantization step (QUANT) is therefore always placed in the run field of the first code, and its level field holds the DC coefficient. Runlevel codes are transferred two to a 32-bit word.⁸

NOP

The number of runlevel pairs varies from block to block. (run, level) = (63, 128) = 0xfe00 is therefore inserted after the final pair of each block as a NOP. A NOP ends the block, and the remaining elements of the block are 0. A NOP between blocks is skipped, and when two NOPs appear in the middle of a block the second is skipped.⁹

RL Data

RL data combines all the runlevel blocks required for decoding. It has a one-word header and a footer that maintains 32-word boundaries. The blocks are in the order Cb, Cr, Y0, Y1, Y2, Y3, so six blocks make one macroblock and the number of blocks must be a multiple of 6. The header word has the following format:⁹

The data size must be a multiple of 32. Consequently a footer of NOPs is added as padding to make the data a fixed length.⁹

The RL data syntax on page 1-20 lists QUANT and RUN as 5 bits. Figures 12 and 13 on page 1-18 give them as 6 bits.⁸¹⁰

VLC

VLC (Variable Length Coding) is based on Huffman coding, which is a reversible compression with a fixed dictionary (code book). Words with a high probability of occurrence are assigned shorter codes. For example, (run, level) = (0, 1) occurs often and is assigned a 2-bit code, while (23, 1) occurs rarely and is assigned 14 bits.¹⁰¹¹

The best code book differs with the image source. To simplify things, libpress prepares a single standard code book that is based on the runlevel distribution of a typical natural image. Applications such as animation, whose distribution differs from natural images, would need different code books.¹¹

Word boundaries are not significant in the coded data. Because byte ordering on the PlayStation is little endian, coded bit sequences are ordered starting with the low-order bits, and code sequences packed in this way are called bitstreams. A runlevel code that is not in the code book is coded as the escape code 000001 followed by an FLC (fixed-length code).¹¹

VLC decoding is performed in software, while MDEC decodes the run-level data in hardware. The two are therefore generally run as a pipeline to decrease processing time. In the library DecDCTvlc() performs VLC decoding, and DecDCTin() and DecDCTout() perform the DCT processing.¹¹

AC Code Book

The VLC code book is compatible with the one used in MPEG. In the table below the final bit s of each code is the sign of the level. It is 0 for a positive level and 1 for a negative level. EOB is the code for a NOP (0xfe00).¹¹¹²

FLC Code

ESC is followed by a fixed-length code. The run is 6 bits and runs from 000000 for 0 to 111111 for 63. Levels from -127 to 127 take 8 bits in two's complement form. Levels from -256 to -128 and from 128 to 255 take 16 bits:¹³

BS Format

RL data on which the VLC transformation has been performed is called BS data. The BS format is made up of bitstreams in which the header and the blocks are coded. All blocks in the current BS format are assumed to have the same quantization step, so QUANT is stored only once in the two-word header:¹¹

A block contains a 10-bit DC element followed by the bitstream of the AC run-levels, and block boundaries are not necessarily on word boundaries. The RL footer padding is not included in BS data, so DecDCTvlc() adds the footer automatically when it decodes. BS data also does not hold the frame size or the frame rate. These settings must be given to the program in other ways.¹¹¹⁴

Decoding the DC Component

The first 10 bits of a block are the DC value as a fixed code. In the manual's example the bits 1111 0000 11 have the MSB set, so the DC value is negative and equals -60. For a color-difference block this is the DC value as is. For a luminance block an offset of 128 is added, and the example therefore gives 68 (-60 + 128). This value is the average luminance of that 8x8 area.¹⁴¹⁵

Versions

Versions 2 and 3 of the BS format decode the DC component in different ways:¹⁵

Version 3 codes the difference from the DC component of the previous block. The bit width of the difference is VLC coded, and the coded width is followed by the difference value itself. Luminance and color-difference blocks use different tables for the width:¹⁵¹⁶

The Huffman coding of the DC component in version 3 improves the compression ratio but increases the processing time. Version 2 should therefore be used where CPU time can be a bottleneck. In both versions the DC value 511 (0x1ff) is END_OF_FRAME.¹⁶

Decoding Speed

The maximum MDEC decompression speed is 9000 macroblocks per second, which equals 30 frames of 320x240 images per second. The speed does not depend on the compression ratio, so the playback frame rate is in inverse proportion to the resolution:¹⁶

In practice the CPU performs the VLC decoding in the background, and other heavy CPU work can make it the bottleneck. The CD-ROM transfers 150 KB/sec at standard speed and 300 KB/sec at double speed. At double speed, 30 frames per second therefore needs a bitstream of 10 KB or less per frame (300 KB / 30):¹⁶

Image Quality

Noise at the image input stage is the biggest factor in the quality of playback, so image sources must be at least 24-bit images. Block noise in 16x16 pixel units comes from the Cb and Cr blocks, and it is conspicuous when the coded noise changes between frames.¹⁷

Such changes occur when the quantization step varies between adjacent frames. When BS data is interleaved with audio sectors, the data size of each frame varies and the quantization step varies with it. Sources with many static areas, such as animation backgrounds, must consequently be encoded with fixed sectors.¹⁷

Playback in 24-bit mode generally gives better results than playback in 16-bit mode. This is because a standard encoder truncates the low-order bits when going from 24 to 16 bits.¹²

References