summaryrefslogtreecommitdiffstats
path: root/lib/rng.go
blob: 6f573248474e8b7b963aa35bf001a13aae35cd45 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
// Copyright © 2021 rsiddharth <s@ricketyspace.net>
// SPDX-License-Identifier: ISC

package lib

// MT19937 coefficients.
var mtCoefW uint32 = 32
var mtCoefN uint32 = 624
var mtCoefM uint32 = 397
var mtCoefR uint32 = 31
var mtCoefA uint32 = 0x9908B0DF
var mtCoefU uint32 = 11
var mtCoefD uint32 = 0xFFFFFFFF
var mtCoefS uint32 = 7
var mtCoefB uint32 = 0x9D2C5680
var mtCoefT uint32 = 15
var mtCoefC uint32 = 0xEFC60000
var mtCoefL uint32 = 18

var mtF uint32 = 1812433253

// MT19937 instance struct
type MTRand struct {
	genSt       [624]uint32
	index       uint32
	initialized bool
}

// Stores state of MT19937 generator.
var mtGenSt []uint32 = make([]uint32, mtCoefN)
var mtIndex uint32 = mtCoefN + 1

var mtLowerMask uint32 = (1 << mtCoefR) - 1
var mtUpperMask uint32 = 0xFFFFFFFF & (^mtLowerMask)

func (r *MTRand) Seed(s uint32) {
	r.index = mtCoefN
	r.genSt[0] = s
	for i := uint32(1); i < mtCoefN; i++ {
		r.genSt[i] = (0xFFFFFFFF &
			(mtF*(r.genSt[i-1]^(r.genSt[i-1]>>(mtCoefW-2))) + i))
	}
	r.initialized = true
}

func MTSeed(seed uint32) {
	mtIndex = mtCoefN
	mtGenSt[0] = seed
	for i := uint32(1); i < mtCoefN; i++ {
		mtGenSt[i] = (0xFFFFFFFF &
			(mtF*(mtGenSt[i-1]^(mtGenSt[i-1]>>(mtCoefW-2))) + i))
	}
}

func (r *MTRand) Extract() uint32 {
	if !r.initialized || r.index >= mtCoefN {
		if !r.initialized {
			r.Seed(5489)
		}
		r.twist()
	}

	y := r.genSt[r.index]
	y = y ^ ((y >> mtCoefU) & mtCoefD)
	y = y ^ ((y << mtCoefS) & mtCoefB)
	y = y ^ ((y << mtCoefT) & mtCoefC)
	y = y ^ (y >> mtCoefL)

	r.index = r.index + 1

	y = 0xFFFFFFFF & y
	return y
}

func MTExtract() uint32 {
	if mtIndex >= mtCoefN {
		if mtIndex > mtCoefN {
			MTSeed(5489)
		}
		mtTwist()
	}

	y := mtGenSt[mtIndex]
	y = y ^ ((y >> mtCoefU) & mtCoefD)
	y = y ^ ((y << mtCoefS) & mtCoefB)
	y = y ^ ((y << mtCoefT) & mtCoefC)
	y = y ^ (y >> mtCoefL)

	mtIndex = mtIndex + 1

	r := 0xFFFFFFFF & y
	return r
}

func (r *MTRand) twist() {
	for i := uint32(0); i < mtCoefN-1; i++ {
		x := (r.genSt[i] & mtUpperMask) +
			(r.genSt[(i+1)%mtCoefN] & mtLowerMask)
		xA := x >> 1
		if x%2 != 0 { // lowest bit of x is 1
			xA = xA ^ mtCoefA
		}
		r.genSt[i] = r.genSt[(i+mtCoefM)%mtCoefN] ^ xA
	}
	r.index = 0
}

func mtTwist() {
	for i := uint32(0); i < mtCoefN-1; i++ {
		x := (mtGenSt[i] & mtUpperMask) +
			(mtGenSt[(i+1)%mtCoefN] & mtLowerMask)
		xA := x >> 1
		if x%2 != 0 { // lowest bit of x is 1
			xA = xA ^ mtCoefA
		}
		mtGenSt[i] = mtGenSt[(i+mtCoefM)%mtCoefN] ^ xA
	}
	mtIndex = 0
}