// This is an implementation of the MT19937 algorithm, which produces uniformly-distributed 32 bit
// integers. These integers are /pif_LongInt/Unsigned32 objects.

#define pRMT_Set(p, I)  MT[2*((p)+1)-1] = I._GetBlock(2); MT[2*((p)+1)] = I._GetBlock(1);
#define pRMT_Get(p, I)  I._SetBlock(2, MT[2*((p)+1)-1]); I._SetBlock(1, MT[2*((p)+1)]);

pif_Random/Mersenne32
    var
        const
            // These constants and their names are specified by the MT19937 algorithm, so refer
            // to it for details. Pairs of the form (x2,x1) indicate a single 32 bit in broken up
            // into two groups. E.g., if x2 = 0xABCD and x1 = 0xEF01, then the original specification
            // had a single 32 bit in x = 0xABCDEF01. That is, x2 will always be the more significant
            // end, and x1 will be the least-significant one.
            w  = 32
            n  = 624
            m  = 397
            r  = 31

            a2 = 0x9908
            a1 = 0xB0DF

            u  = 11
            // d2 = 0xFFFF        (x & ((d2 << 16) | d1)) == x, so this step won't be performed.
            // d1 = 0xFFFF

            s  = 7
            b2 = 0x9D2C
            b1 = 0x5680

            t  = 15
            c2 = 0xEFC6
            c1 = 0x0000

            l  = 18

            f2 = 0x6C07
            f1 = 0x8965

            // lower_mask = (1 << r) - 1
            lower_mask2 = 0x7FFF
            lower_mask1 = 0xFFFF

            // upper_mask = lowest w bits of ~( (lower_mask2 << 16) | lower_mask1)
            upper_mask2 = 0x8000
            upper_mask1 = 0x0000

        index = n+1
        list/MT // Stores the state of the PRNG.

        pif_LongInt/Unsigned32
            Int // Most recently-extracted integer.
            Seed

    New(...)
        // Takes arguments in the pif_Arithmetic format. This argument is passed directly to the Int
        // object, which will process it instead of this method.

        Int = new

        if(args.len == 0)
            // If no seed is provided, then we seed with PRNG with world.timeofday.
            Seed = new(world.timeofday)
        else
            // Anything else we pass. This means that passing null is treated like passing 0.
            Seed = new(arglist(args))

        MT = new
        MT.len = 2*n // 2*n = 2*624. We do this, because the array will store a pair of 16 bit
                     // integers that are combined for the Int object to use.

        Seed.SetModeFlag(Seed.NEW_OBJECT, 0)
        Int.SetModeFlag(Int.NEW_OBJECT, 0)

        _Initialize(Seed)
        _Extract()

        return src

    proc
        /*
         * "Private" methods.
         */

        _Initialize(pif_LongInt/Unsigned32/Seed)
            var
                s2
                s1


            // MT[0] := seed
            pRMT_Set(0, Seed)

            for(var/i = 1 to n-1)
                s2 = Seed._GetBlock(2)
                s1 = Seed._GetBlock(1)

                // MT[i] := lowest w bits of (f * (MT[i-1] xor (MT[i-1] >> (w-2))) + i)
                Seed >>= w-2
                Seed.BitwiseXor(s2, s1)
                Seed.Multiply(f2, f1)
                Seed += i

                pRMT_Set(i, Seed)

            return 1

        _Extract()
            // Extracts the next 32 bit unsigned integer and stores it.

            if(index >= n)
                _Twist()

            // int y := MT[index]
            pRMT_Get(index, Int)
            var
                Int2 = Int._GetBlock(2)
                Int1 = Int._GetBlock(1)

            // y := y xor ((y >> u) and d)
            Int >>= u
            Int.BitwiseXor(Int2, Int1)

            Int2 = Int._GetBlock(2)
            Int1 = Int._GetBlock(1)

            // y := y xor ((y << s) and b)
            Int <<= s
            Int.BitwiseAnd(b2, b1)
            Int.BitwiseXor(Int2, Int1)

            Int2 = Int._GetBlock(2)
            Int1 = Int._GetBlock(1)

            // y := y xor ((y << t) and c)
            Int <<= t
            Int.BitwiseAnd(c2, c1)
            Int.BitwiseXor(Int2, Int1)

            Int2 = Int._GetBlock(2)
            Int1 = Int._GetBlock(1)

            // y := y xor (y >> l)
            Int >>= l
            Int.BitwiseXor(Int2, Int1)

            index ++
            return 1

        _Twist()
            // Generates the next n (i.e., 624) integer values from the MT recurrence.

            var/pif_LongInt/Unsigned32
                X  = new
                XA = new

            X.SetModeFlag(X.NEW_OBJECT, 0)
            XA.SetModeFlag(XA.NEW_OBJECT, 0)

            for(var/i = 0 to n-1)

                // int x := (MT[i] and upper_mask) + (MT[(i+1) mod n] and lower_mask)
                pRMT_Get(i, X)
                pRMT_Get((i+1) % n, XA)

                X.BitwiseAnd(upper_mask2, upper_mask1)
                XA.BitwiseAnd(lower_mask2, lower_mask1)
                X.Add(XA)

                // int xA := x >> 1
                XA.Set(X)
                XA >>= 1

                if((X.block_1 & 0x0001) == 1)
                    // xA := xA xor a
                    XA.BitwiseXor(a2, a1)

                // MT[i] := MT[(i + m) mod n] xor xA
                pRMT_Get((i+m) % n, X)
                XA ^= X
                pRMT_Set(i, XA)

            index = 0
            return 1

#undef  pRMT_Set
#undef  pRMT_Get

    /*
     * pif_Random method implementations.
     */

    Seed()
        return new Seed.type(Seed)

    Reset()
        return _Initialize(Seed)

    Step()
        return _Extract()

    GetSigned32()
        return new /pif_LongInt/Signed32(Seed)

    GetUnsigned32()
        return new /pif_LongInt/Unsigned32(Seed)

    GetFloat()
        var/pif_LongInt/Unsigned32/U = new(Int)

        // U &= 16777215. This assures that 0 <= U < 1677216.
        U &= 0x00FFFFFF
        return U.ToFloat() / 16777216

    GetBool()
        return Int.block_1 & 1

    NextSigned32()
        . = GetSigned32()
        Step()

    NextUnsigned32()
        . = GetUnsigned32()
        Step()

    NextFloat()
        . = GetFloat()
        Step()

    NextBool()
        . = GetBool()
        Step()