重写没有分支的代码

Question

我有以下功能：

uint16_t foo(uint8_t input)
{
     uint16_t N = 38;
     if (!(input&1))
     {
       N = 0;
     }
     else 
     {
        if ((input&2) >> 1)
        {
           N = ~N;
        }
     }
     return N;
}

我想在没有 ifs 的情况下重写它，就像一个将 38 转换为 0,38 或 65497 给定 input 的内联函数] 并且只使用标准的 C 位操作。

重点不在于编译器可以内联函数，或者函数要快，而只是为了摆脱分支并保持恒定时间，而不管 input 是什么。

第一个if很简单：

uint16_t c = ((input&1)^1)-1;
N &= c;

但是我很难找到一些简单的方法来进行条件否定。

Answer 1

使用 table 查找。

uint16_t foo(uint8_t input) {
    int index= input & 0x3;
    const uint16 table[4]= {0,~38,0,38};
    return table[index];
}

Answer 2

如果我以正确的方式阅读您的代码，它会显示以下内容：

uint16_t foo1(uint8_t input)
{
     uint16_t N = 38;

     uint16_t bit0 = input & 1;
     uint16_t nbit0 = bit0 ^ 1;
     uint16_t bit1 = (input & 2) >> 1;
     uint16_t nbit1 = bit1 ^ 1;

     N = nbit0 * ( bit1 * ~N + nbit1 * N);

     return N;
}

随意摆脱变量。它们只是为了便于阅读。

Answer 3

为了保证运行-time 和平衡的代码，必须使用汇编程序。由于 MSP430 汇编程序并不那么复杂，所以这不是什么大问题。请注意，乘法之类的事情可能由具有 not 常量运行-time.

的函数执行

避免分支没有什么意义。相反，您应该平衡执行路径，e.g.using NOP（无操作）。 MSP430 用户指南包括指令时序。请注意，时序是固定的，这与 ARM 等较大的 CPU 不同，它取决于流水线和内存时序。

一般说明：通过 CPU 个周期进行计时在大多数情况下不是一个好主意。 MSP430 等现代 MCU 提供内部定时器和与 ADC 等其他外设的连接以触发，例如转换具有高度准确的时间。它们可以生成中断，因此 CPU 可以准备下一个值或读取样本，而不用关心代码的运行时间（除非花费的时间太长）。

将CPU用于此类禁止实例中断，因为它们会破坏任何时序。这使得维护这样的系统成为一场噩梦。

Answer 4

这应该有效。

#include<stdio.h>

int main(){
    int input;
    scanf("%d", &input);
    int N = (input&1)*(((input&2)*32729)+(38+((input&2)>>1)));
    printf("%d\n", N);
}

Answer 5

7 次运算，没有乘法，基于 njuffa 的评论：

uint16_t bar(uint8_t input)
{
    return (0-(input&1)) & (38^(0-((input>>1)&1)));
}

Demo

重写没有分支的代码

Rewrite the code without branches

c

optimization

bit-manipulation

inline