Linear Feedback Shift Register efficiency

2
votes

I have the following code implement a shift action of a linear feedback shift register:

public int DoShift()
{
    //Find new top bit
    int feedback = Contents & tapSequence;
    int newBit = 0;
    for(int i = 1; i <= length; i++)
    {
        newBit = 1 & (newBit ^ feedback);
        feedback >>= 1;
    }
    //Remember falloff, shift register, add new bit
    int result = Contents & 1;
    Contents >>= 1;
    Contents += newBit << (length - 1);
    return result;
}

where

  • Contents is the current contents of the register
  • tapSequence is the XOR tap sequence, where a 1 represents a tapped bit and a 0 represents an untapped bit.
  • length is the number of bits the register has.

However, having run a CPU usage test, this function takes up as much as 60% of my runtime (for what I thought would've been a fairly lightweight method). Is there a more efficient way to write this? Is there a way to XOR the contents of an int with its own bits (so as to do away with the for loop)?

2
c#bit-manipulationshift-register
Do you really need signed numbers? Maybe the sign extension on the right shift is causing more hits than expected? Did you do a release compile? Running it out of the debugger? Can you break out of the for loop early? Change it to a while loop somehow? - Brannon
newBit is basically the parity of feedback. Take a look here to find some alternatives to the loop. Btw, the last Contents += can be expressed as a bitwise OR because newBit is just one bit. - Nico Schertler
Signal numbers? I assume you refer to the tap sequence...can't think of a better implementation for it. No release compile, just running it with the VS debug tools. I suppose it could be broken once feedback == 0, I'll add that. Why would changing to a while loop help? - LeftRight92
Hadn't thought of it like parity, thanks for the link, will have a dig. Would Contents = Contents ^ (newBit << (length - 1)) be more efficient then? - LeftRight92
It might. But you would have to measure for a definite answer. Btw, I would arrange the bits in the opposite direction (so coefficients of lower exponents correspond to less significant bits). But that's just a question of taste. - Nico Schertler

2 Answers

1
votes

Try this:

public int DoShift()
{
    int newBit = 1 << (length - 1); // you can save it as class member
    int result = Contents & 1;
    int feedback = Contents & tapSequence;
    Contents >>= 1;
    while(feedback != 0) {
      feedback &= feedback - 1;
      Contents ^= newBit;
    }
    return result;
}

In addition, exist more efficient approach, named "reversed LSFR". It's idea - apply tapSequence to whole register just once, if result is 1.

See example: https://en.wikipedia.org/wiki/Linear_feedback_shift_register

1
votes

Have gone with the following solution:

public int DoShift()
{
    //Remember falloff, shift register, add new bit
    int result = Contents & 1;
    Contents = (Contents >> 1) ^ 
        ((CountBits(Contents & tapSequence) % 2) << (length - 1));
    return result;
}

//Brian Kernighan method of counting bits
public static int CountBits(int value)
{
    int count = 0;
    while (value != 0)
    {
        count++;
        value &= value - 1;
    }
    return count;
}

Additionally, I may also attempt some to run elements of the broader programme in parallel.