Iterative Fast Forward 1D DCT-II on MSIL

• Download source - 46.4 KB

Introduction

Three years ago, I published a simple article Iterative Fast 1D Forward DCT about fast forward 1D Discreet Cosine Transformation II (DCT-II) which is well known as simply "the DCT" and is used like core of the JPEG, MJPEG or MPEG.

Some time ago, I faced the problem of adapting this code for C#. At the time of development, I have decided to write the implementation which uses .NET Emit class and generates code on MSIL at runtime.

Background

I had the task to create a simple program for processing of live speech on C#. I had decided to write the program in C# and was faced with the problem of projection the time domain on the frequency with different "window": 8, 16, 32, 64 and 128 samples. I used my old code from Iterative Fast 1D Forward DCT and ported it in C#. However, after some time, I memorized the amazing book "Beautiful Code" - Edited by Andy Oram and Greg Wilson, especially the article of the Charles Petzold about generating dynamical code for processing images on C# by classes from namespace System.Reflection.Emit. The article describes how to unroll the code of the "for" and "while" for huge massive data with variable length. I have decided that this tip suits my task perfectly, because I did not want to unroll DCT for all processing "windows", and had thinking to expend the amount of them. I decided that it would be better if the program generates the code for fixed length of each "window" at starting time.

Using the Code

The code is implemented in class CollectionForward1DDCT_II. It has three methods:

• slowForward1DDCT_II(double[] block) - The implementation of classical forward 1D DCT-II which can be found on the Wikipedia site. The complexity of this method is O(N²).
• fastForward1DDCT_II(double[] block) - The implementation of my previous development forward 1D DCT-II which can be found on Iterative Fast 1D Forward DCT. The complexity of this method is O(N*log(N)).
• bool DynamicILFastForward1DDCT_II(double[] block) - The implementation of new code on MSIL. It returns bool state for checking state creating code on MSIL at runtime.

The code of the method bool DynamicILFastForward1DDCT_II(double[] block) is presented in the next listing:

public static bool DynamicILFastForward1DDCT_II(double[] block)
{
    DynamicMethod method;

    uint length = (uint)block.Length;

    if (dic.ContainsKey(length))
    {
        method = dic[length];
    }
    else
    {
        method = createILFastForward1DDCT_II((uint)block.Length);

        if (method == null) return false;

        dic[length] = method;
    }

    method.Invoke(method, new object[] { block });

    return true;
}    

This method returns false if it is not possible to generate code MSIL in method private static DynamicMethod createILFastForward1DDCT_II(uint length) it returns false and does not make computing. If it returns true, then the generated DynamicalMethod is collected in associative set - Dictionary<uint, DynamicMethod> and the created code is invoked:

method.Invoke(method, new object[] { block }); 

This way allows to generate and save the methods for the specific length of the block and use it many times. This code can be rewritten for generating the methods for the specific length of block at any time.

Points of Interest

For getting the most effective implementation of the forward 1D DCT-II, the code which is generated in this class includes the result of the cosine as constant numerical value. It allows to get implementation which is close for hardware with direct implementation of the trigonometric functions.

History

• 31st May, 2014: Initial version