How to implement 128-bit linear feedback shift register with byte element array in C

Question

I have an array as follows,

unsigned char A[16]

I am using this array to represent a 128-bit hardware register. Now I want to implement a linear feedback shift register (LFSR, Fibonacci implementation) using this long register. The polynomials (or tap) which connect to the feedback xnor gate of this LFSR are [128, 29, 27, 2, 1].

The implementation of a 16-bit LFSR (taps at [16, 14, 13, 11]) can be obtained from Wikipedia as the following.

  unsigned short lfsr = 0xACE1u;
  unsigned bit;

  unsigned rand()
  {
    bit  = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;
    return lfsr =  (lfsr >> 1) | (bit << 15);
  }

In my case, however, I need to shift bits from one byte element to another, e.g. the msb or A[0] need to be shift to the lsb of A1. What is minimum coding to do this shift? Thank you!

Answer 1

To calculate the bit to shift in you don't need to shift the whole array every time since you are only interested in one bit (note the & 1 at the end of the bit = line from Wikipedia).

The right shift amounts are:

128 - 128 =   0   => byte  0 bit 0
128 -  29 =  99   => byte 12 bit 3
128 -  27 = 101   => byte 12 bit 5
128 -   2 = 126   => byte 15 bit 6
128 -   1 = 127   => byte 15 bit 7

So,

bit = ((A[0] >> 0) 
    ^  (A[12] >> 3) 
    ^  (A[12] >> 5) 
    ^  (A[15] >> 6) 
    ^  (A[15) >> 7)) & 1;

Now, you really need to shift in the bit:

A[0] = (A[0] >> 1) | (A[1] << 7);
A[1] = (A[1] >> 1) | (A[2] << 7);
// and so on, until
A[14] = (A[14] >> 1) | (A[15] << 7);
A[15] = (A[15] >> 1) | (bit << 7);

You can make this a bit more efficient by using uint32_t or uint64_t instead of unsigned chars (depending on your processor word size), but the principle is the same.