1

I need to remove as many if conditions as possible from the two functions below:

inline int inc_with_1bit_saturation(int counter)
{
    if (counter == 1)
        return --counter;
    return ++counter;
}

void branch_prediction_1bit_saturation(int* input, int* output, int size)
{
    int counter = 0;

    for (int i = 0; i < size; ++i)
    {
        if (input[i] != counter)
        {
            counter = inc_with_1bit_saturation(counter);
            output[i] = 0;
        }
        else output[i] = 1;
    }
}

How can I do that and what if branch is absolutely necessary and cannot be removed and which one can be replaced by simple bitwise operations or something like that?

Update 1

According to User JSF's great tip, the code is now looking like this:

void branch_prediction_1bit_saturation(int* input, int* output, int size)
{
    int counter = 0;

    for (int i = 0; i < size; ++i)
    {
        if (input[i] != counter)
        {
            counter = 1 - counter;
            output[i] = 0;
        }
        else output[i] = 1;
    }
}

Update 2

Thanks to Cantfindname, the code became like this:

void branch_prediction_1bit_saturation(int* input, int* output, int size)
{
    int counter = 0;

    for (int i = 0; i < size; ++i)
    {
        output[i] = counter == input[i];
        counter = output[i] * counter + (1 - output[i])*(1 - counter);
    }
}

And this completely solves the question.

Community
  • 1
  • 1
Denis Yakovenko
  • 3,241
  • 6
  • 48
  • 82
  • 5
    Your code `counter = inc_with_1bit_saturation(counter);` is a very inefficient way to do `counter=1-counter;` The `%2` approach in the first answer isn't great either. – JSF Jan 12 '16 at 16:01

3 Answers3

6

For the if statement inside the loop:

output[i] = (int)(input[i]==counter);
counter = output[i]*counter + (1-output[i])*(1-counter) //used JSF's trick

True converts to 1 and false to 0, according to this: bool to int conversion

Community
  • 1
  • 1
Cantfindname
  • 2,008
  • 1
  • 17
  • 30
  • 2
    Bitwise operators might be even faster: `counter = (output[i] & counter) | ((1-output[i]) & (1-counter));` – Sani Huttunen Jan 12 '16 at 16:22
  • 2
    or `!(counter ^ output[i])` maybe `1-(counter ^ output[i])` works better if the optimizer is less smart. `counter^=(1-output[i])` if the optimizer is really poor. – JSF Jan 12 '16 at 16:43
1

function inc_with_1bit_saturation is equivalent of modulo 2. So you can replace

counter = inc_with_1bit_saturation(counter);

With

counter = (counter+1) % 2;
Pavel Pája Halbich
  • 1,529
  • 2
  • 17
  • 22
  • 1
    @Samidamaru: Initial value is zero. Thus, it can be only incremented. Then it will get 1 and with next call will be decremented, so zero again. – Pavel Pája Halbich Jan 12 '16 at 16:00
  • 1
    indeed, realised and deleted my commented. (Though it is the behaviour of the other function resulting in this behaviour, the function itself does not perform modulo 2 ^^). – Samidamaru Jan 12 '16 at 16:02
  • 1
    It is much better to replace it with `counter = 1 - counter` (as suggested by @JSF) than by modulo operation. – SergeyA Jan 12 '16 at 16:11
1
void branch_prediction_1bit_saturation(int* input, int* output, int size) {

    int counter = 0;

    for (int i = 0; i < size; ++i)
    {
        output[i] = (int)!((!!input[i]) ^ counter);
        counter = (int)((!!input[i]) & counter) | ((!!input[i]) & !counter);
    }
}

A is logic input[i];

B is logic counter;

The truth table for input[i] != counter is:

A B

0 0 | 0 --> (0 & 0) | (0 & !0) = 0 | 0 = 0

0 1 | 0 --> (0 & 1) | (0 & !1) = 0 | 0 = 0

1 0 | 1 --> (1 & 0) | (1 & !0) = 0 | 1 = 1

1 1 | 1 --> (1 & 1) | (1 & !1) = 1 | 0 = 1

The truth table for output[i]

A B

0 0 | 1 --> !(0 ^ 0) = !(0) = 1

0 1 | 0 --> !(0 ^ 1) = !(1) = 0

1 0 | 0 --> !(1 ^ 0) = !(1) = 0

1 1 | 1 --> !(1 ^ 1) = !(0) = 1

:)

DanielVL
  • 249
  • 1
  • 5