A system, apparatus, method, and article to process a flexible macroblock ordering and arbitrary slice ordering are described. The apparatus may include a video decoder. The video decoder includes a processor to store coding parameters of one or more neighboring macroblocks in a data buffer. The neighboring macroblocks are previously decoded macroblocks and are adjacent to a current macroblock. The processor is to store control parameters for each of the one or more neighboring macroblocks in the data buffer. The processor is to reconstruct coding parameters for the current macroblock using availability information associated with the neighboring macroblocks.