-------------------------------------------------------------------------------
--
-- A Linear Congruential Generator (LCG)
--
-------------------------------------------------------------------------------

package LCG (sysLCG) where
import FIFO


--import GetPut
class Put c where
    put    :: c a -> a -> Action

class Get c where
    get    :: c a -> a
    drop   :: c a -> Action

instance Put FIFO where
    put f x  = f.enq x

instance Get FIFO where
    get f    = f.first
    drop f   = f.deq
{-

Linear congruential generators are of the form x(n) = a * x(n-1) + b
mod M.  A good discussion of this type is in the text by Press et al.
These are by far the most common form in use, and have periods in the
range 10^6 to 10^9 when using 32 bit words.  Unfortunately, they have
some unpleasant properties.  When taken in pairs, triplets, or
n-tuples, the random values often fall on only a few planes in
n-space.  Using a shuffle box can break up this uniformity.  For more
information on the problems associated with linear congruential
generators, see Marsaglia 1968, Marsaglia 1993 and Sullivan 1993.

Truncated LCGs attempt the eliminate some weakness by not revealing
all the bits of the LCG at each stage, only some of the bits.

Also see http://world.std.com/~franl/crypto/random-numbers.html
which says:

The general form of a linear congruential generator is:

        SEED = (A * SEED + C) mod M

        X = SEED/M

The user supplies an initial integer value for SEED.  On each call to
the random number generator a new value of SEED is calculated by taking
the current value of SEED, multiplying by A, adding C, and taking the
remainder MOD M of the result.  The new value of SEED is an integer
between 0 and M-1.  This new value of SEED is then converted into a
floating point value between 0 inclusive and 1 exclusive by dividing
SEED by M.  The result X is returned as a floating point random number
in the range [0,1).

First note some obvious properties of sequences generated by this method:

    1.  The modulus M is an upper bound on the number of different values
        SEED can take on.

    2.  If the new value of SEED is the same as one we had before,
        the sequence will begin to repeat itself in a cyclic
        manner.

    3.  All sequences generated by a linear congruential formula will
        eventually enter a cycle which repeats itself endlessly.

A good linear congruential formula will generate a long sequence of
numbers before repeating itself.  The maximum length a sequence can
possibly be before repeating itself is M, the modulus.  This is because
there are only M different possible values SEED can take on.  A linear
congruential formula will generate a sequence of maximum length M if and
only if the following three conditions are met (See Knuth for a proof of
this theorem):

      i)  C is relatively prime to M;
     ii)  B = (A - 1) is a multiple of P, for every prime P dividing M;
    iii)  B = (A - 1) is a multiple of 4, if M is a multiple of 4.

-}

-----------
-- TYPES --
-----------

-- This state mechanism is purely so that we can get an initial seed
-- whenever the system is reset, rather than having a preset seed.
-- If we opt for a preset seed, then this state and the "seedFifo"
-- can go away.
data StateType = Waiting | Running | Done
               deriving (Eq,Bits)


---------
-- LCG --
---------

-- n is the seed type
-- m is the extracted value type
interface RandGen n m =
    seed :: n -> Action
    -- rest is like a FIFO
    ldeq :: Action
    lfirst :: m

instance Get (RandGen n) where
    get l = l.lfirst
    drop l = l.ldeq

-- n is how big the generator is and
-- m is how many bits we get out
-- m must be <= n
mkLCG :: (Add l m n) => UInt n -> UInt n -> Module (RandGen (UInt n) (UInt m))
mkLCG a b =
    module
        x :: Reg (UInt n)
        x <- mkRegU

        state :: Reg (StateType)
        state <- mkReg Waiting

        rules
            when state == Running
              ==> let
                      -- the "mod M" is implicit
                      x' = a * x + b
                  in  action
                        x := x'
                        state := Done

        interface
            seed s = action
                        x := s
                        state := Running
                when state == Waiting
            ldeq = state := Waiting
                when state == Done
            lfirst = truncate x
                when state == Done


------------------
-- SAMPLE USAGE --
------------------

-- This choice of A and B satisfies the three conditions given in the
-- discussion at the top, for M = 2^32.  This, however, does not give
-- a truncated LCG.  (For that, simply change the second parameter of
-- RandGen to a smaller number!  Yay type system!)

-- Note that we had to make the multiplier an argument to mkLCG
-- because if it's implemented in verilog, then it isn't
-- parameterizable (in the size of the inputs and outputs).
-- We could, however, have defined a multiplier module which
-- can be instantiated for different sizes, if we really wanted
-- to preserve some elegance in exchange for not having total
-- control over the internals of the multiplier.

sysLCG :: Module Empty
sysLCG =
    module
        lcg :: RandGen (UInt 32) (UInt 20)
        lcg <- mkLCG 69069 1
        started :: Reg Bool
        started <- mkReg False
        rules
          "init":
            when not started
             ==> action { lcg.seed 12345; started := True }