Linear-feedback shift register implementation

Question

I want to implement a Linear-feedback shift register for the following polynomial x^24 + x^23 + x^22 + x^20 + x^19 + x^18 + x^17 + x^16 + x^15 + x^13 + x^12 + x^8 + x^7 + x^6 + 1, relying on what can be found here with the associated C code:

https://en.wikipedia.org/wiki/Linear-feedback_shift_register#Fibonacci_LFSRs

I have used uint32_t for all my data types and lfsr is set to start_state when the function is called. The central lines in the function are:

bit = ((lfsr >> 7) ^ (lfsr >> 8) ^ (lfsr >> 9) ^ (lfsr >> 11) ^ (lfsr >> 12) ^ (lfsr >> 13) ^ (lfsr >> 14) ^ (lfsr >> 15) ^ (lfsr >> 16) ^ (lfsr >> 18) ^ (lfsr >> 19) ^ (lfsr >> 23) ^ (lfsr >> 24) ^ (lfsr >> 25))& 1u;

lfsr = (lfsr >> 1) | (bit << 31);

But this can't fit, because I have as condition do{...} while (lfsr != start_state ); so that correspondingly after about 17 million runs the function should be finished, but it just keeps running permanently, which is why my mapping of the polynomial to the 32 bit sequence can't fit. What am I doing wrong here?

I added the minimal example.

void lfsr_fib(uint32_t lfsr)
{
    uint32_t bit;

    uint32_t compareNr = 0;

    do
    {

        /*
        polynomial: x^24 + x^23 + x^22 + x^20 + x^19 + x^18 + x^17 + x^16 + x^15 + x^13 + x^12 + x^8 + x^7 + x^6 + 1
        */


        bit = ((lfsr >> 7) ^ (lfsr >> 8) ^ (lfsr >> 9) ^ (lfsr >> 11) ^ (lfsr >> 12) ^ (lfsr >> 13) ^ (lfsr >> 14) ^ (lfsr >> 15) ^ (lfsr >> 16) ^ (lfsr >> 18) ^ (lfsr >> 19) ^ (lfsr >> 23) ^ (lfsr >> 24) ^ (lfsr >> 25))& 1u;

        lfsr = (lfsr >> 1) | (bit << 31);
   

        ++period;
        printf("%d\n", period);

    } while (lfsr != start_state );


}

Update:

My teacher announced that he made a mistake. The start_value has 32 bit which he actually wanted to be 24 bit.

Now he gave us the tip to use the 32 bit start value and replace lfsr = (lfsr >> 1) | (bit << 31); by lfsr = (lfsr >> 1) | (bit << 24);.

Answer 1

I want the polynomial in my comment, which seems to be the one @stark pointed out. This way seems to assume the lsb left and the msb right, so that we shift everything onto the msb's positon and xor it. –  Rico1990

I did the polynomial in your comment, but it did not work (seemed to loop infinitely).

I looked at the wikipedia page, and changed the rightmost term from + 1 to + lfsr per the wiki.

That did work (I'm guessing it's correct because it stopped).

---

Here is the restructured code:

#include <stdio.h>
#include <stdint.h>

#define B(_s) \
    (lfsr >> _s)

void
lfsr_fib(uint32_t lfsr)
{
    uint32_t bit;

    uint32_t start_state = lfsr;
    uint32_t compareNr = 0;

#if BIG
    uint64_t period = 0;
#else
    uint32_t period = 0;
#endif

    do {

        /*
           polynomial: x^24 + x^23 + x^22 + x^20 + x^19 + x^18 + x^17 + x^16 +
            x^15 + x^13 + x^12 + x^8 + x^7 + x^6 + 1 */

        // original code:
#if 0
        bit = ((lfsr >> 7) ^ (lfsr >> 8) ^ (lfsr >> 9) ^ (lfsr >> 11) ^
            (lfsr >> 12) ^ (lfsr >> 13) ^ (lfsr >> 14) ^ (lfsr >> 15) ^
            (lfsr >> 16) ^ (lfsr >> 18) ^ (lfsr >> 19) ^ (lfsr >> 23) ^
            (lfsr >> 24) ^ (lfsr >> 25)) & 1u;
#endif

        // recoding direct from above comment:
#if 0
        bit = B(24) + B(23) + B(22) + B(20) + B(19) + B(18) + B(17) + B(16) +
            B(15) + B(13) + B(12) + B(8) + B(7) + B(6) + 1;
#endif

        // changed final term from "1" to "B(0)" per wiki page:
#if 1
        bit = B(24) + B(23) + B(22) + B(20) + B(19) + B(18) + B(17) + B(16) +
            B(15) + B(13) + B(12) + B(8) + B(7) + B(6) + B(0);
#endif

        lfsr = (lfsr >> 1) | (bit << 31);

        ++period;

        if (period == 0) {
            printf("WRAP\n");
            break;
        }
    } while (lfsr != start_state);

#if BIG
    printf("%8.8llX/%llu\n", period, period);
#else
    printf("%8.8X/%u\n", period, period);
#endif
}

int
main(void)
{

    //lfsr_fib(0x1234);
    lfsr_fib(1u << 31 | 1);

    return 0;
}

---

In the code above, I've used cpp conditionals to denote old vs. new code:

#if 0
// old code
#else
// new code
#endif

#if 1
// new code
#endif

Note: this can be cleaned up by running the file through unifdef -k

---

Here is the program output:

0078BDC9/7912905

---

UPDATE:

Thank you for your answer. How does the restructured code satisfy the xor done in my code. Since the duration of one periodic cycle should be 16777215 I asked myself whether it is necessary to use that addition and xor deliver the same result mod 2, because your example is at least according to theory breaking to fast. –  Rico1990

A single bit add is the same as xor (xor is how ALUs do addition). So, they are the same in this context.

I'm not sure how you get 16777215 as the period. The period changes a bit, based on the initial value. The code below produces two different periods: 7912905 and 15825810

Here is an enhanced version of the code that allows more experimentation:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

// X -- select operation:
//   0 -- +
//   1 -- ^
#ifndef X
#define X   0
#endif

// Y -- select equation
//   0  -- original code:
//   1  -- original code refactored to use macros
//   2  -- recoding direct from above comment:
//   3  -- changed final term from "1" to "B(0)" per wiki page:
#ifndef Y
#define Y       3
#endif

// W -- number of bits to wrap/fail on
#ifndef W
#define W           28
#endif

#if X == 0
#define x +
#else
#define x ^
#endif
#undef X

#define B(_s) \
    (lfsr >> _s)

#define X(_s) \
    x B(_s)

#if (W < 32) || BIG
#define WMSK        ((1L << W) - 1)
#else
#define WMSK        ~0u
#endif

#if BIG
typedef uint64_t PER;
#define FMT16       "%16.16llX"
#define FMT10       "%-20llu"
#else
typedef uint32_t PER;
#define FMT16       "%8.8X"
#define FMT10       "%-10u"
#endif

int opt_R;
int opt_C;

char *
strbuf(void)
{
    static int idx = 0;
    static char buf[16][1024];
    char *bp = buf[idx];

    if (++idx >= 16)
        idx = 0;

    *bp = 0;

    return bp;
}

const char *
xprt(PER val,int what)
{
    char *buf = strbuf();
    char *bp = buf;

    switch (what) {
    case 1:
        bp += sprintf(bp,FMT16,val);
        break;
    case 2:
        bp += sprintf(bp,FMT10,val);
        break;
    default:
        bp += sprintf(bp,FMT16,val);
        bp += sprintf(bp,"/");
        bp += sprintf(bp,FMT10,val);
        break;
    }

    return buf;
}

struct period {
    PER period;
    PER count;
    struct period *next;
};
struct period *perlist;

void
store(PER period)
{
    struct period *prev = NULL;
    struct period *cur = perlist;

    for (;  cur != NULL;  cur = cur->next) {
        if (cur->period == period)
            break;
        prev = cur;
    }

    do {
        if (cur != NULL)
            break;

        cur = calloc(1,sizeof(*cur));
        cur->period = period;

        if (prev != NULL)
            prev->next = cur;
        else
            perlist = cur;
    } while (0);

    cur->count += 1;
}

PER
lfsr_fib(uint32_t start_state)
{
    uint32_t bit;
    uint32_t lfsr = start_state;
    PER period = 0;
    int bad = 0;

    printf("lfsr=%s",xprt(lfsr,1));

    do {

        /*
           polynomial: x^24 + x^23 + x^22 + x^20 + x^19 + x^18 + x^17 + x^16 +
            x^15 + x^13 + x^12 + x^8 + x^7 + x^6 + 1 */

        // NOTE: will optimize down to single/inlined case:
        switch (Y) {
        case 0:  // original code:
            bit = ((lfsr >> 7) ^ (lfsr >> 8) ^ (lfsr >> 9) ^ (lfsr >> 11) ^
                (lfsr >> 12) ^ (lfsr >> 13) ^ (lfsr >> 14) ^ (lfsr >> 15) ^
                (lfsr >> 16) ^ (lfsr >> 18) ^ (lfsr >> 19) ^ (lfsr >> 23) ^
                (lfsr >> 24) ^ (lfsr >> 25)) & 1u;
        break;

        case 1:  // original code refactored to use macros
            bit = 0 X(25) X(24) X(23) X(19) X(18) X(16) X(15) X(14) X(13) X(12)
                X(11) X(9) X(8) X(7);
            break;

        case 2:  // recoding direct from above comment:
            bit = B(24) x B(23) x B(22) x B(20) x B(19) x B(18) x B(17) x
                B(16) x B(15) x B(13) x B(12) x B(8) x B(7) x B(6) x 1;
            break;

        case 3:  // changed final term from "1" to "B(0)" per wiki page:
            bit = 0 X(24) X(23) X(22) X(20) X(19) X(18) X(17) X(16)
                X(15) X(13) X(12) X(8) X(7) X(6) X(0);
            break;
        }

        // NOTE: not necessary, but ...
        bit &= 1u;

        lfsr = (lfsr >> 1) | (bit << 31);

        ++period;

        bad = (period & WMSK) == 0;
        if (bad)
            break;
    } while (lfsr != start_state);

    if (bad) {
        printf(" FAIL\n");
        period = 0;
    }
    else
        printf(" period=%s\n",xprt(period,2));

    store(period);

    return period;
}

void
title(const char *str)
{

    printf("\n");
    printf("%s:\n",str);
}

int
main(int argc,char **argv)
{

    --argc;
    ++argv;

    for (;  argc > 0;  --argc, ++argv) {
        char *cp = *argv;
        if (*cp != '-')
            break;

        cp += 2;
        switch (cp[-1]) {
        case 'C':
            opt_C = (*cp != 0) ? atoi(cp) : 100;
            break;

        case 'R':
            opt_R = (*cp != 0) ? atoi(cp) : 1;
            break;
        }
    }

    setbuf(stdout,NULL);
    printf("WMSK=%s\n",xprt(WMSK,3));
    printf("Y=%d\n",Y);

    title("static");
    lfsr_fib(1u << 31 | 1);
    lfsr_fib(1u << 31 | 0);
    lfsr_fib(0u << 31 | 0);
    lfsr_fib(0u << 31 | 1);
    lfsr_fib(0x1234);

    title("bitslide");
    for (uint32_t rhs = 0u;  rhs != 0x02;  rhs += 1) {
        for (uint32_t lhs = 1u;  lhs != 0;  lhs <<= 1)
            lfsr_fib(lhs | rhs);
    }

    if (opt_R) {
        if (opt_C <= 0)
            opt_C = 10;

        srand(opt_R);

        title("random");
        for (int tryno = 1;  tryno <= opt_C;  ++tryno) {
            uint32_t rval = rand();
            lfsr_fib(rval);
        }
    }

    // show final results
    title("counts");
    for (struct period *cur = perlist;  cur != NULL;  cur = cur->next)
        printf("period=%s count=%s\n",
            xprt(cur->period,2),xprt(cur->count,2));

    return 0;
}

Compiled with -DY=3 (others fail), and run with ./test -R -C100, here is the program output:

WMSK=0FFFFFFF/268435455
Y=3

static:
lfsr=80000001 period=7912905
lfsr=80000000 period=15825810
lfsr=00000000 period=1
lfsr=00000001 period=15825810
lfsr=00001234 period=7912905

bitslide:
lfsr=00000001 period=15825810
lfsr=00000002 period=15825810
lfsr=00000004 period=15825810
lfsr=00000008 period=15825810
lfsr=00000010 period=15825810
lfsr=00000020 period=15825810
lfsr=00000040 period=7912905
lfsr=00000080 period=15825810
lfsr=00000100 period=7912905
lfsr=00000200 period=7912905
lfsr=00000400 period=7912905
lfsr=00000800 period=7912905
lfsr=00001000 period=15825810
lfsr=00002000 period=7912905
lfsr=00004000 period=7912905
lfsr=00008000 period=15825810
lfsr=00010000 period=7912905
lfsr=00020000 period=15825810
lfsr=00040000 period=7912905
lfsr=00080000 period=15825810
lfsr=00100000 period=7912905
lfsr=00200000 period=7912905
lfsr=00400000 period=15825810
lfsr=00800000 period=7912905
lfsr=01000000 period=15825810
lfsr=02000000 period=15825810
lfsr=04000000 period=15825810
lfsr=08000000 period=15825810
lfsr=10000000 period=15825810
lfsr=20000000 period=15825810
lfsr=40000000 period=15825810
lfsr=80000000 period=15825810
lfsr=00000001 period=15825810
lfsr=00000003 period=7912905
lfsr=00000005 period=7912905
lfsr=00000009 period=7912905
lfsr=00000011 period=7912905
lfsr=00000021 period=7912905
lfsr=00000041 period=15825810
lfsr=00000081 period=7912905
lfsr=00000101 period=15825810
lfsr=00000201 period=15825810
lfsr=00000401 period=15825810
lfsr=00000801 period=15825810
lfsr=00001001 period=7912905
lfsr=00002001 period=15825810
lfsr=00004001 period=15825810
lfsr=00008001 period=7912905
lfsr=00010001 period=15825810
lfsr=00020001 period=7912905
lfsr=00040001 period=15825810
lfsr=00080001 period=7912905
lfsr=00100001 period=15825810
lfsr=00200001 period=15825810
lfsr=00400001 period=7912905
lfsr=00800001 period=15825810
lfsr=01000001 period=7912905
lfsr=02000001 period=7912905
lfsr=04000001 period=7912905
lfsr=08000001 period=7912905
lfsr=10000001 period=7912905
lfsr=20000001 period=7912905
lfsr=40000001 period=7912905
lfsr=80000001 period=7912905

random:
lfsr=6B8B4567 period=15825810
lfsr=327B23C6 period=15825810
lfsr=643C9869 period=15825810
lfsr=66334873 period=15825810
lfsr=74B0DC51 period=7912905
lfsr=19495CFF period=15825810
lfsr=2AE8944A period=15825810
lfsr=625558EC period=15825810
lfsr=238E1F29 period=15825810
lfsr=46E87CCD period=7912905
lfsr=3D1B58BA period=15825810
lfsr=507ED7AB period=7912905
lfsr=2EB141F2 period=7912905
lfsr=41B71EFB period=7912905
lfsr=79E2A9E3 period=7912905
lfsr=7545E146 period=15825810
lfsr=515F007C period=7912905
lfsr=5BD062C2 period=7912905
lfsr=12200854 period=7912905
lfsr=4DB127F8 period=7912905
lfsr=0216231B period=7912905
lfsr=1F16E9E8 period=7912905
lfsr=1190CDE7 period=7912905
lfsr=66EF438D period=15825810
lfsr=140E0F76 period=7912905
lfsr=3352255A period=15825810
lfsr=109CF92E period=7912905
lfsr=0DED7263 period=15825810
lfsr=7FDCC233 period=7912905
lfsr=1BEFD79F period=15825810
lfsr=41A7C4C9 period=15825810
lfsr=6B68079A period=15825810
lfsr=4E6AFB66 period=7912905
lfsr=25E45D32 period=7912905
lfsr=519B500D period=15825810
lfsr=431BD7B7 period=15825810
lfsr=3F2DBA31 period=7912905
lfsr=7C83E458 period=15825810
lfsr=257130A3 period=15825810
lfsr=62BBD95A period=7912905
lfsr=436C6125 period=7912905
lfsr=628C895D period=15825810
lfsr=333AB105 period=7912905
lfsr=721DA317 period=7912905
lfsr=2443A858 period=15825810
lfsr=2D1D5AE9 period=7912905
lfsr=6763845E period=7912905
lfsr=75A2A8D4 period=7912905
lfsr=08EDBDAB period=7912905
lfsr=79838CB2 period=15825810
lfsr=4353D0CD period=15825810
lfsr=0B03E0C6 period=7912905
lfsr=189A769B period=7912905
lfsr=54E49EB4 period=7912905
lfsr=71F32454 period=7912905
lfsr=2CA88611 period=15825810
lfsr=0836C40E period=7912905
lfsr=02901D82 period=7912905
lfsr=3A95F874 period=15825810
lfsr=08138641 period=7912905
lfsr=1E7FF521 period=15825810
lfsr=7C3DBD3D period=15825810
lfsr=737B8DDC period=15825810
lfsr=6CEAF087 period=15825810
lfsr=22221A70 period=7912905
lfsr=4516DDE9 period=7912905
lfsr=3006C83E period=15825810
lfsr=614FD4A1 period=15825810
lfsr=419AC241 period=7912905
lfsr=5577F8E1 period=15825810
lfsr=440BADFC period=7912905
lfsr=05072367 period=15825810
lfsr=3804823E period=15825810
lfsr=77465F01 period=7912905
lfsr=7724C67E period=7912905
lfsr=5C482A97 period=15825810
lfsr=2463B9EA period=7912905
lfsr=5E884ADC period=7912905
lfsr=51EAD36B period=7912905
lfsr=2D517796 period=7912905
lfsr=580BD78F period=7912905
lfsr=153EA438 period=15825810
lfsr=3855585C period=7912905
lfsr=70A64E2A period=15825810
lfsr=6A2342EC period=15825810
lfsr=2A487CB0 period=15825810
lfsr=1D4ED43B period=7912905
lfsr=725A06FB period=15825810
lfsr=2CD89A32 period=7912905
lfsr=57E4CCAF period=15825810
lfsr=7A6D8D3C period=7912905
lfsr=4B588F54 period=15825810
lfsr=542289EC period=15825810
lfsr=6DE91B18 period=7912905
lfsr=38437FDB period=15825810
lfsr=7644A45C period=7912905
lfsr=32FFF902 period=15825810
lfsr=684A481A period=15825810
lfsr=579478FE period=7912905
lfsr=749ABB43 period=7912905

counts:
period=7912905    count=86
period=15825810   count=82
period=1          count=1