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

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!

Solution

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.