深入探讨用位掩码代替分支(1):利用带符号移位生成掩码
几年前我写了一篇“优化分支代码——避免跳转指令堵塞流水线”(http://www.52php.cn/article/p-etmlkbgq-uh.html)。因当时是整理笔记,有些粗略。这几年又有了新的心得,故决定深入探讨,顺便回答网友评论。 housisong(http://blog.csdn.net/housisong)提到了用利用带符号移位生成掩码—— 这是一个很好的思路,避免了状态寄存器访问。 没有带符号移位运算符,问题不大。现在主流编程语言大多支持带符号移位。比如微软打造了VB.Net,支持带符号移位。 其中有一个思路就是利用减法,将“与特定整数的比较”转换为“与0的比较”。但这样做有时会产生溢出,导致运算结果不正确 或抛出异常(当检查整数溢出异常时)。如果再做溢出处理的话,增加了复杂度、影响效率。 因图像处理中最常用的带符号类型是16位整数,所以我在这里采用16位带符号整数(signed short),在计算掩码时应右移15位。
1.1 与0比较 我们先热身一下,回顾一下与0比较时的掩码算法—— 加一个取反运算符后,可以得到这样的掩码—— 如先对n求负,可以得到这样的掩码—— 再加一个取反运算符后,可以得到这样的掩码——
上面的式子虽然是与0比较,但因式中没有写0,理解起来有点吃力。于是现在将0补上—— 观察上式,我们可以将0替换为任意整数X—— 因为现在是任意整数X,在进行减法运算时有可能产生溢出。
在编写图像处理程序时,经常出现RGB值超过[0,255]范围的情况。这时,得做饱和处理,将越界数值饱和到边界,即这样的代码: 现在我们将利用位运算,来优化这样的代码。 2.1 “<0”时的处理 我们可以利用与运算将数值修正为0,应选用【“>=0”时全1,“<0”时全0】的掩码。语句为—— 将其整理为一条表达式—— 因为该式没有用到减法,所以当n为任意值时都不会溢出。 2.2 “>255”时的处理 我们可以利用或运算,将超过范围的数值修正为全1。再将其与0xFF进行与运算,将超过范围的数值修正为255,这是根据255(0xFF)正好是低8位。 怎么判断超过范围呢?有三种策略—— 因现在为了避免状态寄存器,不能利用比较语句,只能利用前面的位掩码算法。列出三种策略是为了找到效率最高的方案。 进过对比后发现,判断“>X”的运算量最少,所以我们应选择策略A。语句为—— 将其整理为一条表达式—— 注意该式仅在n大于等于0时有效。 2.3 饱和处理 现在开始考虑实际的饱和处理,即将“<0”的修正为0,又将“>255”的修正为255。 先整理一下上面的成果—— 因“>255”处理在n小于0时无效,而“<0”处理在任何时候有效。所以我们可以先进行>255”处理,再进行“<0”处理,以屏蔽中间的错误值。语句为—— 分析—— 由于我们一般是将结果保存到一个BYTE型变量中,进行一次强制类型转换就行了,不需要“& 0xFF”——
在实际运用,上述代码比较长不易维护。可以将其封装为宏,并顺便推广一下—— bits代表限制多少位,如BYTE就是8——
测试代码如下—— // 用位掩码做饱和处理.用求负生成掩码 #define LIMITSU_FAST(n,bits) ( (n) & -((n) >= 0) | -((n) >= (1<<(bits))) ) #define LIMITSU_SAFE(n,bits) ( (LIMITSU_FAST(n,bits)) & ((1<<(bits)) - 1) ) #define LIMITSU_BYTE(n) ((BYTE)(LIMITSU_FAST(n,8))) // 用位掩码做饱和处理.用带符号右移生成掩码 //#define LIMITSW_FAST(n,bits) ( (n) & ~((signed short)(n) >> 15) | ((signed short)((1<<(bits)) - 1 - (n)) >> 15) ) #define LIMITSW_FAST(n,bits) ( ( (n) | ((signed short)((1<<(bits)) - 1 - (n)) >> 15) ) & ~((signed short)(n) >> 15) ) #define LIMITSW_SAFE(n,bits)) & ((1<<(bits)) - 1) ) #define LIMITSW_BYTE(n) ((BYTE)(LIMITSW_FAST(n,8))) signed short buf[0x10000]; // 将数值放在数组中,避免编译器过度优化 int main(int argc,char* argv[]) { int i; // 循环变量(32位) signed short n; // 当前数值 signed short m; // 临时变量 BYTE by0; // 用if分支做饱和处理 BYTE by1; // 用位掩码做饱和处理.用求负生成掩码 BYTE by2; // 用位掩码做饱和处理.用带符号右移生成掩码 //printf("Hello World!n"); printf("== noifCheck ==n"); // 初始化buf for(i=0; i<0x10000; ++i) { buf[i] = (signed short)(i - 0x8000); //printf("%dn",buf[i]); } // 检查 “<0”处理 printf("[Test: less0]n"); for(i=0; i<0x8100; ++i) // [-32768,255] //for(i=0x7FFE; i<=0x8002; ++i) // [-2,2] { // 加载数值 n = buf[i]; // 用if分支做饱和处理 m = n; if (m < 0) m = 0; by0 = (BYTE)m; // 用位掩码做饱和处理.用求负生成掩码 by1 = (BYTE)(n & -(n >= 0)); if (by1 != by0) printf("[Error] 1.1 neg: [%d] %d!=%dn",n,by0,by1); // 验证 // 用位掩码做饱和处理.用带符号右移生成掩码 by2 = (BYTE)(n & ~((signed short)n >> 15)); if (by2 != by0) printf("[Error] 1.2 sar: [%d] %d!=%dn",by2); // 验证 } // 检查 “>255”处理 printf("[Test: great255]n"); for(i=0x8000; i<0x10000; ++i) // [0,32767] //for(i=0x80FE; i<=0x8102; ++i) // [254,258] { // 加载数值 n = buf[i]; // 用if分支做饱和处理 m = n; if (m > 255) m = 255; by0 = (BYTE)m; // 用位掩码做饱和处理.用求负生成掩码 by1 = (BYTE)(n | -(n >= 256) ); if (by1 != by0) printf("[Error] 2.1 neg: [%d] %d!=%dn",by1); // 验证 // 用位掩码做饱和处理.用带符号右移生成掩码 by2 = (BYTE)(n | ((signed short)(255-n) >> 15)); if (by2 != by0) printf("[Error] 2.2 sar: [%d] %d!=%dn",by2); // 验证 } // 检查 饱和处理 printf("[Test: saturation]n"); for(i=0; i<0x10000; ++i) // [-32768,32767] //for(i=0x7FFE; i<=0x8102; ++i) // [-2,258] { // 加载数值 n = buf[i]; // 用if分支做饱和处理 m = n; if (m < 0) m = 0; else if (m > 255) m = 255; by0 = (BYTE)m; // 用位掩码做饱和处理.用求负生成掩码 by1 = LIMITSU_BYTE(n); if (by1 != by0) printf("[Error] 3.1 neg: [%d] %d!=%dn",by1); // 验证 // 用位掩码做饱和处理.用求负生成掩码 by2 = LIMITSW_BYTE(n); if (by2 != by0) printf("[Error] 3.2 sar: [%d] %d!=%dn",by2); // 验证 } return 0; }
测试结果—— 全部通过! (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |