#if !defined  HAVE_FCSR_H__
#define       HAVE_FCSR_H__
// This file is part of the FXT library.
// Copyright (C) 2010 Joerg Arndt
// License: GNU General Public License version 3 or later,
// see the file COPYING.txt in the main directory.

#include "fxttypes.h"
#include "bits/bithigh.h"


class fcsr
// Feedback Carry Shift Register (FCSR)
// Produces a shift register sequence (SRS)
// generated by  a_k mod c where
// c should be a prime that has the primitive root 2
// We have  a_k = a_0 * 2^k (mod c)  [by default a_0=1]
// The period of the FCSR is the order of two mod c
// ( ==c-1 if c is prime with primitive root 2)
{
public:
    ulong a_;     // internal state (a_0*2**k modulo c),  1 <= a < c
    ulong w_;     // word of the SRS,  1 <= w <= mask
    ulong c_;     // a prime with primitive root 2, e.g. 37 = 1..1.1
    ulong mask_;  // mask  e.g. (with above)    mask == 63 == 111111

public:
    fcsr(ulong c)
    {
        c_ = c;
        const ulong h = highest_one(c_);
        mask_ = ( h | (h-1) );
//        a_ = h;  w_ = h;  // valid combination, a_0==h
        set_a(1);
    }

    ~fcsr()  { ; }

    ulong next()
    {
        a_ <<= 1;                   // a *= 2
        if ( a_ > c_ )  a_ -= c_;   // reduce mod c
        // todo: check for overflow

        // update w:
        w_ <<= 1;
        w_ |= (a_ & 1);
        w_ &= mask_;

        return w_;
    }

    void next_w()
    // produce the next word w
    // 1 <= w <= mask_
    {
        ulong t = c_;
        while ( (t>>=1) )  next();
    }

    void set_a(ulong a)
    {
        w_ = 0;
        ulong t = c_;
        while ( (t>>=1) )
        {
            if ( 0==(a & 1) )  a >>= 1;
            else
            {
                // a = (a + c_) >> 1; // might overflow
                a = (a & c_) + ((a ^ c_) >> 1);
            }
        }
        a_ = a;
        next_w();
    }

    ulong get_a()  const  { return a_; }
    ulong get_w()  const  { return w_; }

//    ulong max_period()  const  { return c_ - 1; }
};
// -------------------------


#endif  // !defined HAVE_FCSR_H__