import std.numeric

class Xor128
    - x : uint
    , y : uint
    , z : uint
    , w : uint

    init(@x, @y, @z, @w)
    end

    init
        @x := __builtin_read_cycle_counter()
        @y := __builtin_read_cycle_counter()
        @z := __builtin_read_cycle_counter()
        @w := __builtin_read_cycle_counter()
    end

    func new_seed(seeds)
        @x = seeds[0u % seeds.size]
        @y = seeds[1u % seeds.size]
        @z = seeds[2u % seeds.size]
        @w = seeds[3u % seeds.size]
    end

    func gen
        t := @x ^ (@x << 11u)
        w := @w
        @x = @y
        @y = @z
        @z = @w
        @w = (w ^ (w << 19u)) ^ (t ^ (t << 8u))
        ret @w
    end
end

class LCG
    seed : int

    init(@seed)
    end

    init
        @seed := __builtin_read_cycle_counter()
    end

    func new_seed(seeds)
        @seed = 0
        i := 0u
        for i < seeds.size
            @seed ^= seeds[i]
            i += 1u
        end
    end

    func gen
        x := @seed
        high := x / 127773
        low := x % 127773
        var t := 16807 * low - 2836 * high

        if t <= 0
            t += 0x7fffffff
        end

        @seed = t
        ret t
    end
end

class Mt19937
    mt, mti
    n, m
    matrix_a
    upper_mask
    lower_mask

    init(seeds)
        @mt := new [uint]{624u, 0u}
        @mti := 625u
        @n := 624u
        @m := 397u
        @matrix_a := 0x9908b0dfu
        @upper_mask := 0x80000000u
        @lower_mask := 0x7fffffffu
        @init_by_array(seeds)
    end

    init
        @mt := new [uint]{624u, 0u}
        @mti := 625u
        @n := 624u
        @m := 397u
        @matrix_a := 0x9908b0dfu
        @upper_mask := 0x80000000u
        @lower_mask := 0x7fffffffu
        @init_by_array([
                    __builtin_read_cycle_counter(),
                    __builtin_read_cycle_counter(),
                    __builtin_read_cycle_counter(),
                ])
    end

    func new_seed(seeds)
        @init_by_array(seeds)
    end

  - func init_genrand(s)
        @mt[0u] = s
        @mti = 1u
        for @mti < @n
            @mt[@mti] = 1812433253u * (@mt[@mti-1u] ^ (@mt[@mti-1u] >> 30u)) + @mti
            @mti += 1u
        end
    end

  - func init_by_array(init_key) : ()
        key_len := init_key.size
        @init_genrand(19650218u)

        var i := 1u
        var j := 0u
        var k := if @n > key_len then @n else key_len end

        for k > 0u
            @mt[i] = @mt[i] ^ (@mt[i-1u] ^ (@mt[i-1u] >> 30u) * 1664525u) + init_key[j] + j
            i += 1u
            j += 1u

            if i >= @n
                @mt[0u] = @mt[@n-1u]
                i = 1u
            end

            if j >= key_len
                j = 0u
            end

            k -= 1u
        end

        k = @n - 1u

        for k > 0u
            @mt[i] = @mt[i] ^ (@mt[i-1u] ^ (@mt[i-1u] >> 30u) * 1566083941u) - i
            i += 1u
            if i >= @n
                @mt[0u] = @mt[@n-1u]
                i = 1u
            end

            k -= 1u
        end

        @mt[0u] = 0x80000000u
    end

    func gen
        var y : uint

        if @mti >= @n
            mag01 := [0u, @matrix_a]

            @init_genrand(5489u) if @mti == @n + 1u

            var kk := 0u

            for kk < @n - @m
                y = (@mt[kk] & @upper_mask) | (@mt[kk+1u] & @lower_mask)
                @mt[kk] = (@mt[kk+@m] ^ (y >> 1u)) ^ mag01[y % 2u]
                kk += 1u
            end

            for kk < @n - 1u
                y = (@mt[kk] & @upper_mask) | (@mt[kk+1u] & @lower_mask)
                @mt[kk] = (@mt[kk+@m-@n] ^ (y >> 1u)) ^ mag01[y % 2u]
                kk += 1u
            end

            y = (@mt[@n-1u] & @upper_mask) | (@mt[0u] & @lower_mask)
            @mt[@n-1u] = (@mt[@m-1u] ^ (y >> 1u)) ^ mag01[y % 2u]
            @mti = 0u
        end

        y = @mt[@mti]
        @mti += 1u

        y = y ^ (y >> 11u)
        y = y ^ ((y << 7u) & 0x9d2c5680u)
        y = y ^ ((y << 15u) & 0xefc60000u)
        y = y ^ (y >> 18u)

        ret y
    end
end

class Random
    generator

    init(@generator)
    end

    init
        @generator := new Mt19937{[0x123u, 0x234u, 0x345u, 0x456u]}
    end

    func new_seed(seeds)
        @generator.new_seed(seeds)
    end

    func gen
        ret @generator.gen
    end
end

func main
    test := -> n, r do
        n.println
        5.times do
            r.gen.println
        end
        println("")
    end

    begin
        r := new Random{new LCG{1}}
        "LCG".test r
    end

    begin
        r := new Random{new Xor128{123456789u, 362436069u, 521288629u, 88675123u}}
        "Xor128".test r
    end

    begin
        r := new Random{new Mt19937{[0x123u, 0x234u, 0x345u, 0x456u]}}
        "Mt19937".test r
    end
end