Clever Geek Handbook

Rewrite the code without branches

I have the following function:

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

And I would like it to be overwritten without ifs

, as a built-in function that converts 38

to 0,38

or 65497

given input

, and only uses standard bit convolution operations.

The point is not that the compiler could inline a function, or a function that could be fast, but simply get rid of the branches and be constant time, no matter what is input

.

The first one if

is simple:

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

but I'm having trouble finding an easy way to do this conditional negation.

+3


source to share


5 answers


7 operations and no multiplications, based on njuffa's comment:

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


Demo

+2


source


Use table lookup.



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


source


To have guaranteed execution times and balanced code, you need to switch to assembler. Since the MSP430 assembler is not that complicated, this won't be a problem. Note that things like multiplication are most likely done by a function that has no constant runtime.

There is little point in avoiding branches. Instead, you should balance the execution paths, for example, use NOP (no operation). The MSP430 User Manual includes command synchronization. Note that timing is fixed, which differs from larger processors like ARM where it depends on pipeline and memory timing.

General note. Doing time with cpu cycles is bad in most cases. Modern MCUs like the MSP430 provide internal timers and connections to other peripherals like the ADC for triggering, for example. conversions with very accurate times. They can generate an interrupt so that the processor can prepare the next value or read a sample without worrying about code execution time (as long as it doesn't take too long).

CPU usage for such prohibitions like interrupts as they will delete any time. This makes maintaining such a system a nightmare.

+3


source


If I read your code correctly, it says this:

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;
}

Feel free to get rid of the variables. They are for readability only.

+2


source


This should work.

#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);
}
+2


source






More articles:


All Articles