《代码之美》（八）－－图像处理中的即时代码生成

Charles Petzold

通常，我们把代码和数据区别对待。但对于机器而言，代码和数据本质上其实是一样的——不过是一堆字节码而已。

在Windows1.0里面，有一个图形函数叫做BitBlt，意即“Bit block transfer（位块传输）”。它将一个矩形像素块传输到另一个地方，比如把一个位图拷贝到显示器上。在这个拷贝过程中，我们希望加上一些其它功能，比 如在传输过程中对每个像素求逆（即黑变白，浅灰变深灰，绿变绛红等）。BitBlt（和StretchBlt）实现的光栅操作涉及了三个对象：源，目标和 模式（画刷），因此也被称为三元光栅操作。一共有256种光栅操作，下面是用C语言实现的一个版本，其中S为源，D为目标，P为画刷：

for (y = 0; y < cy; y++)
for (x = 0; x < cx; x++)
{
    switch (rop)
    {
    case 0x00:
        D[y][x] = 0x00;
        break;
    ...
    case 0x60:
        D[y][x] = (D[y][x] ^ S[y][x]) & P[y][x];
        break;
    ...
    case 0xFF:
        D[y][x] = 0xFF;
        break;
    }
}

上面的代码省略了大部份的操作，但它确实包含256个case。因为它操作的是位图，如今一台廉价数码相机的位图都能包含百万级像素，所以将大大的switch语句放入在这个双重循环体里，性能将会很差，为此，可以把双重循环移到每个case子句中：

switch (rop)
{
case 0x00:
    for (y = 0; y < cy; y++)
    for (x = 0; x < cx; x++)
        D[y][x] = 0x00;
        break;
    ...
case 0x60:
    for (y = 0; y < cy; y++)
    for (x = 0; x < cx; x++)
        D[y][x] = (D[y][x] ^ S[y][x]) & P[y][x];
        break;
    ...
case 0xFF:
    for (y = 0; y < cy; y++)
    for (x = 0; x < cx; x++)
        D[y][x] = 0xFF;
        break;
    }
}

这样虽然代码看上去有些丑陋，但性能却得到很大的提高。（博主：书上并没有说明为什么这样做可以提升性能，但我分析原因如下：1、省去了百万次的跳转（到 switch表中的某项）的操作；2、每次for循环同样对应着一次跳转操作，如果for包含着switch语句，那么跳转操作要跨过整个switch 表，但如果把for循环局限在case子句中的话，跳转操作只需跨过case子句，这样可以减少内存页面失效的可能性。）

BitBlt操作是Windows里极其重要的函数，所以是尽可能地让它快，为此，微软的天才程序员想出了一种“比汇编还快”的手法：BitBlt包含一 个“迷你”编译器，基于参数中给定的特定的光栅操作，在栈上建立起一个由8086机器代码构成的子进程，然后执行它。这个即时建立起来的由机器代码构成的 子进程不需要switch，而只需要对每个像素执行给定的光栅操作即可。

 

过滤器是一个矩阵，它用如下方式来处理源位图中的所有像素：把过滤器的中心与当前处理的像素重合，再将源位图中与过滤器重叠的所有的像素根据过滤器中的元素值，计算出目标位图中对应的像素的值。它的C语言实现如下：

for (yDestination = 0; yDestination < cyBitmap; yDestination++)
for (xDestination = 0; xDestination < cxBitmap; xDestination++)
{
    double pixelsAccum = 0;
    double filterAccum = 0;

    for (yFilter = 0; yFilter < cyFilter; yFilter++)
    for (xFilter = 0; xFilter < cxFilter; xFilter++)
    {
        int ySource = yDestination + yFilter - cyFilter/2;
        int xSource = xDestination + xFilter - cxFilter/2;

        if (ySource >= 0 && ySource < cyBitmap && xSource >= 0 && xSource < cxBitmap)
        {
            pixelsAccum += F[yFilter][xFilter] * S[ySource][xSource];
            filterAccum += F[yFilter][xFilter];
        }
    }
    if (filterAccum != 0)
        pixelAccum /= filterAccum;

    if (pixelsAccum < 0)
        D[yDestination][xDestination] = 0;
    else if (pixelsAccum > 255)
        D[yDestination][xDestination] = 255;
    else
        D[yDestination][xDestination] = (unsigned char) pixelsAccum;
}

如今我们不太使用汇编或C了，而是用更高级的语言，比如C#，所以我们尝试用C#来实现上面的过滤器。但是，C#的二维数组要用到方法调用，造成性能的损失。而C#的一维数组可以得到指令级的支持，所以我们使用一维数组来表示位图：

      void FilterMethodCS(byte[] src, byte[] dst, int stride, int bytesPerPixel)
      {
          int cBytes = src.Length;
          int cFilter = filter.Length;

          for (int iDst = 0; iDst < cBytes; iDst++)
          {
              double pixelsAccum = 0;
              double filterAccum - 0;
             for (int iFilter = 0; iFilter < cFilter; iFilter++)
             {
                 int yFilter = iFilter / cyFilter;
                 int xFilter = iFilter % cxFilter;
                 int iSrc = iDst + stride * (yFilter - cyFilter / 2) +
                        bytesPerPixel * (xFilter - cxFilter / 2);
                 if (iSrc >= 0 && iSrc < cBytes)
                 {
                     pixelsAccum += filter[iFilter] * src[iSrc];
                     filterAccum += filter[iFilter];
                 }
             }
             if (filterAccum != 0)
                 pixelsAccum /= filterAccum;
             dst[iDst] = pixelsAccum < 0 ? (byte)0 : (pixelsAccum > 255 ?
                         (byte)255 : (byte)pixelsAccum);
         }
     }

上面的代码执行起来比较慢，怎么让它快一些呢？怎么样对它进行优化呢？你可能会想直接用C#的中间语言编写，但真的可以写的比C#编译器生成的中间语言代 码还好吗？FilterMethodCS的真正问题在于它是一个泛化了的方法：它能够对任意大小的位图利用任意大小的过滤阵列。它的大量代码都是在循环和 索引。如果它不需要应对这样一般性的情况的话，其效率便可以大大提高了。比如，一个3乘3的过滤阵列：

F11	F12	F13
F21	F22	F23
F31	F32	F33

如果我们不用循环，而是直接硬编码：

// 过滤器元素F11
int iSrc = iDst - 4 * CX - 4;

if (iSrc >= 0 && iSrc < 4 * CX * CY)
{
    pixelsAccum += src[iSrc] * F11;
    filterAccum += F11;
}

// 过滤器元素F12
int iSrc = iDst - 4 * CX - 4;

if (iSrc >= 0 && iSrc < 4 * CX * CY)
{
    pixelsAccum += src[iSrc] * F12;
    filterAccum += F12;
}

// 过滤器元素F13到F32的过滤元素
...

// 过滤器元素F33
int iSrc = iDst - 4 * CX - 4;

if (iSrc >= 0 && iSrc < 4 * CX * CY)
{
    pixelsAccum += src[iSrc] * F33;
    filterAccum += F33;
}

由于我们事先并不知道过滤阵列的大小，所以我们不能用上面的“笨”方法。但换个角度想，我们可以学习BitBlt的经验，动态生成代码，再执行这些代码， 为此我们要使用到System.Reflection.Emit中的一组类。下面是FilterMethodCS的另一个版本的实现：

void FilterMethodIL(byte[] src, byte[] dst, int stride, int bytesPerPixel)
{
    int cBytes = src.length;


    // 新建一个（由中间代码编写的）方法，它接受两个byte[]类型的参数，即src和dst。
    DynamicMethod dynameth = new DynamicMethod("Go", typeof(void), new Type[] { typeof(byte[]), typeof(byte[]) }, GetType());

    // 用于生成中间代码的类
    ILGenerator generator = dynameth.GetILGenerator();

    // 定义局部变量
    generator.DeclareLocal(typeof(int)); // 索引0 = iDst
    generator.DeclareLocal(typeof(double)); // 索引1 = pixelsAccum
    generator.DeclareLocal(typeof(double)); // 索引2 = filterAccum


    // 初始化iDst
    generator.Emit(OpCodes.Ldc_I4_0); // 把常数0压入栈中，它是四字节的整型值
     generator.Emit(OpCodes.Stloc_0); // 把栈顶元素(整型值0)赋给第0个局部变量（iDst），并弹出


    // labelTop:
    Label labelTop = generator.DefineLabel(); // 创建一个用于跳转指令的label
    generator.MarkLabel(labelTop); // 标记labelTop

    // 初始化pixelAccum和filterAccum
    generator.Emit(OpCodes.Ldc_R8, 0.0); // 把一个8字节的实数0.0压入栈顶
    generator.Emit(OpCodes.Dup); // 把栈顶元素（0.0）复制一个压入栈顶
    generator.Emit(OpCodes.Stloc_1); // 把栈顶元素（0.0）赋给第1个局部变量（pixelsAccum），并弹出
    generator.Emit(OpCodes.Stloc_2); // 把栈顶元素（0.0）赋给第2个局部变量（filterAccum），并弹出


    // 这里通过循环生成特定长度的中间代码
    for (int iFilter = 0; iFilter < filter.Length; iFilter++)
    {
        // 如果过滤阵列的当前元素为0，则不生成中间代码，即不做任何事
         if (filter[iFlter] == 0)
            continue;

        // 下面的运算结果可以直接写入到中间代码中
         int xFilter = iFilter % cxFilter;
        int yFilter = iFilter / cxFilter;
        int offset = stride * (yFilter - cyFilter / 2) + bytesPerPixels * (xFilter - cxFilter / 2);

        generator.Emit(OpCodes.Ldarg_0); // 把第0个参数（src数组）压入到栈顶

         // 下列的label将用于if...else if...分支
         Label labelLessThanZero = generator.DefineLabel();
        Label labelGreaterThan = generator.DefineLabel();
        Label labelLoopBottom = generator.DefineLabel();

        // 计算iDst + offset
        generator.Emit(OpCodes.Ldloc_0); // 将iDst压入栈
         generator.Emit(OpCodes.Ldc_I4, offset); // 将offset的值压入栈
         generator.Emit(OpCodes.Add); // 把iDst与offset从栈中弹出，并把它们相加，得到的和压入到栈顶
         generator.Emit(OpCodes.Dup); // 把相加的和复制两次
         generator.Emit(OpCodes.Dup);

        // if (iDst + offset >= 0)
        generator.Emit(OpCodes.Ldc_I4_0); // 把整型值0压入栈顶
         generator.Emit(OpCodes.Blt_S, labelLessThanZero); 将栈顶的两个元素弹出并进行比较，如果前者小于后者（iDst+offset < 0）则跳转到labelLessThanZero的位置。Blt_S=Branch-if-Less-Than，S表示跳转的偏移量小于256个字节

         // if (iDst + offset < cBytes)
        generator.Emit(OpCodes.Ldc_I4, cBytes);
        generator.Emit(Opcodes.Bge_S, labelGreaterThan); // 将栈顶的两个元素弹出并进行比较，如果前者大于等于后者(iDst+offset >= cBytes)则跳转到labelGraterThan的位置。

         // (double)src[iDst+offset]
        generator.Emit(OpCodes.Ldelem_U1); // 当前栈顶元素为iDst + offset的值，第二个元素为src数组。将这两个元素弹出，并取src[iDst+offset]的Unsingned的1字节的值压入栈顶。
        generator.Emit(OpCodes.Conv_R8); // 把栈顶元素转换并替换为一个8字节的浮点数。

        if (filter[iFilter] == 1)
        {
            // 乘数为1，保持栈顶的值
        }
        else if (filter[iFilter] == -1)
        {
            // 乘数为-1，栈顶值取负数
        }
        else
        {
            // (double)src[iDst+offset] * filter[iFilter]
            generator.Emit(OpCodes.Ldc_R8, filter[iFilter]);
            generator.Emit(OpCodes.Mul);
        }

        // pixelsAccum += src[iDst+offset] * filter[iFilter];
        generator.Emit(OpCodes.Ldloc_1); // 把局部变量pixelsAccum压入栈顶
        generator.Emit(OpCodes.Add); // 把pixelsAccum与(double)src[iDst+offset] * filter[iFilter]从栈中弹出并相加，把和压入栈顶
        generator.Emit(OpCodes.Stloc_1); // 把上面加法操作的和赋给局部变量pixelsAccum。


        // filterAccum += filter[iFilter];
        generator.Emit(OpCodes.Ldc_R8, filter[iFilter]); // 把filter[iFilter]压入栈顶
        generator.Emit(OpCodes.Ldloc_2); // 把局部变量filterAccum压入栈顶
        generator.Emit(OpCodes.Add); // 令filterAccum与filter[iFilter]相加
        generator.Emit(OpCodes.Stloc_2); // 把相加的和赋给filterAccum
        generator.Emit(OpCodes.Br, labelLoopBottom); // 跳转到labelLoopBottom的位置，即内循环的末尾，对应着FilterMethodCS的24行

        // if...else if的结束标签以及内循环末尾的标签
        generator.MarkLabel(labelLessThanZero); // labelLessThanZero:
        generator.Emit(OpCodes.Pop); // 当iDst+offset < 0时，栈顶用于与cByte比较的iDst+offset的值并未被使用，需要被清理。
        generator.MarkLabel(labelGreaterThan); // labelGreaterThan:
        generator.Emit(OpCodes.Pop); // 当iDst+offset < 0 或 iDst+offset >= cBytes时，清理用于数组取值的栈顶的iDst+offset值。
        generator.Emit(OpCodes.Pop); // 清理栈顶的src数组
        generator.MarkLabel(labelLoopBottom);



        generator.Emit(OpCodes.Ldarg_1); // dst数组压栈
        generator.Emit(OpCodes.Ldloc_0); // iDst压栈

        Label labelSkipDivide = generator.DefineLabel();
       Label labelCopyQutient = generator.DefineLabel();
       Label labelBlack = generator.DefineLabel();
       Label labelWhite = generator.DefineLabel();
       Label labelDone = generator.DefineLabel();

       generator.Emit(OpCodes.Ldloc_1); // pixelsAccum
       generator.Emit(OpCodes.Ldloc_2); // filterAccum
       generator.Emit(OpCodes.Dup); // 复制filterAccum
       generator.Emit(OpCodes.Ldc_R8, 0.0); 将0入栈
       generator.Emit(OpCodes.Beq_S, labelSkipDivide); // if (filterAccum != 0)

       generator.Emit(OpCodes.Div); // pixelsAccum / filterAccum
       generator.Emit(OpCodes.Br_S, labelCopyQuotient); // 跳转到labelCopyQuotient

       generator.MarkLabel(labelSkipDivide);
       generator.Emit(OpCodes.Pop); // 弹出filterAccum

       generator.MarkLabel(labelCopyQuotient);
       generator.Emit(OpCodes.Dup); // 当filterAccum不为0时，栈顶元素为pixelsAccum，当filterAccum为0时，栈顶元素为pixelsAccum/filterAccum。复制栈顶元素
        generator.Emit(OpCodes.Dup); // 再复制一次。

        generator.Emit(OpCodes.Ldc_R8, 0.0);
       generator.Emit(OpCodes.Blt_S, labelBlack); // if (pixelsAccum < 0)

       generator.Emit(OpCodes.Ldc_R8, 255.0);
       generator.Emit(OpCodes.Bgt_S, labelWhite); // if (pixelsAccum > 255.0)

       // if (pixcelsAccum >= 0 && pixcelsAccum <= 255)
       generator.Emit(OpCodes.Conv_U1); // 将pixelsAccum转换为unsigned的1字节的值
       generator.Emit(OpCodes.Br_S, labelDone);


       generator.MarkLabel(labelBlack);
       generator.Emit(OpCodes.Pop);
       generator.Emit(OpCodes.Pop);
       generator.Emit(OpCodes.Ldc_I4_S, 0); // pixelsAccum = 0
       generator.Emit(OpCodes.Br_S, labelDone);

       generator.MarkLabel(labelWhite);
       generator.Emit(OpCodes.Pop);
       generator.Emit(OpCodes.Ldc_I4_S, 255); // pixelsAccum = 255

       generator.MarkLabel(labelDone);
       generator.Emit(OpCodes.Stelem_I1); // dst[iDst] = pixelsAccum

       generator.Emit(OpCodes.Ldloc_0); // 将iDst入栈
       generator.Emit(OpCodes.Ldc_I4_1); // 将1入栈
       generator.Emit(OpCodes.Add); // iDst + 1入栈
       generator.Emit(OpCodes.Dup); // 复制iDst + 1
       generator.Emit(OpCodes.Stloc_0); // iDst = iDst +1
       generator.Emit(OpCodes.Ldc_I4, cBytes); // cBytes入栈
       generator.Emit(OpCodes.Blt, labelTop); // 如果iDst < cBytes，开始下一次循环。


       generator.Emit(OpCodes.Ret); // 返回


       // 调用生成的中间代码函数
       dynameth.Invoke(this, new object[] { src, dst });
   }
}

上面的代码的运行时间是之前FilterMethodCS的1/4。Charles认为虽然代码的外观不算漂亮，但对于一个算法来说，有办法能使它的耗时降到原来的1/4的话，那是非常漂亮的。

 

：1953年生，美国程序员，微软最有价值专家。代表作有《Programming Windows》等。