radiance · Radiance self-hosting compiler

test/tests/prog.mersenne.rad 5.2 KiB raw

//! returns: 0
//! Mersenne Twister PRNG with statistical testing.

const N: u32 = 624;
const M: u32 = 397;
const MATRIX_A: u32 = 0x9908B0DF;
const UPPER_MASK: u32 = 0x80000000;
const LOWER_MASK: u32 = 0x7FFFFFFF;

record MtState {
    mt: *mut [u32],
    mti: u32,
}

fn mtInit(s: *mut MtState, seed: u32) {
    s.mt[0] = seed;
    let mut i: u32 = 1;
    while i < N {
        let prev: u32 = s.mt[i - 1];
        let xored: u32 = prev ^ (prev >> 30);

        let lo: u32 = xored & 0xFFFF;
        let hi: u32 = xored >> 16;
        let c: u32 = 1812433253;
        let clo: u32 = c & 0xFFFF;
        let chi: u32 = c >> 16;

        let ll: u32 = clo * lo;
        let lh: u32 = clo * hi;
        let hl: u32 = chi * lo;

        let result: u32 = ll + ((lh + hl) << 16) + i;
        s.mt[i] = result;
        i += 1;
    }
    s.mti = N;
}

fn generateNumbers(s: *mut MtState) {
    let mut i: u32 = 0;

    while i < N - M {
        let y: u32 = (s.mt[i] & UPPER_MASK) | (s.mt[i + 1] & LOWER_MASK);
        let mut mag: u32 = 0;
        if y & 1 == 1 {
            mag = MATRIX_A;
        }
        s.mt[i] = s.mt[i + M] ^ (y >> 1) ^ mag;
        i += 1;
    }

    while i < N - 1 {
        let y: u32 = (s.mt[i] & UPPER_MASK) | (s.mt[i + 1] & LOWER_MASK);
        let mut mag: u32 = 0;
        if y & 1 == 1 {
            mag = MATRIX_A;
        }
        s.mt[i] = s.mt[i + M - N] ^ (y >> 1) ^ mag;
        i += 1;
    }

    let y: u32 = (s.mt[N - 1] & UPPER_MASK) | (s.mt[0] & LOWER_MASK);
    let mut mag: u32 = 0;
    if y & 1 == 1 {
        mag = MATRIX_A;
    }
    s.mt[N - 1] = s.mt[M - 1] ^ (y >> 1) ^ mag;

    s.mti = 0;
}

fn mtNext(s: *mut MtState) -> u32 {
    if s.mti >= N {
        generateNumbers(s);
    }

    let mut y: u32 = s.mt[s.mti];
    s.mti += 1;

    y ^= (y >> 11);
    y ^= ((y << 7) & 0x9D2C5680);
    y ^= ((y << 15) & 0xEFC60000);
    y ^= (y >> 18);

    return y;
}

fn testKnownSequence(s: *mut MtState) -> i32 {
    mtInit(s, 1);

    let v0: u32 = mtNext(s);
    assert v0 == 1791095845;

    let v1: u32 = mtNext(s);
    assert v1 == 4282876139;

    let v2: u32 = mtNext(s);
    assert v2 == 3093770124;

    let v3: u32 = mtNext(s);
    assert v3 == 4005303368;

    let v4: u32 = mtNext(s);
    assert v4 == 491263;

    return 0;
}

fn testDeterminism(s: *mut MtState) -> i32 {
    mtInit(s, 42);

    let mut first: [u32; 10] = [0; 10];
    let mut i: u32 = 0;
    while i < 10 {
        first[i] = mtNext(s);
        i += 1;
    }

    mtInit(s, 42);

    i = 0;
    while i < 10 {
        let v: u32 = mtNext(s);
        if v != first[i] { return i as i32 + 1; }
        i += 1;
    }

    return 0;
}

fn testDifferentSeeds(s: *mut MtState) -> i32 {
    mtInit(s, 1);
    let a: u32 = mtNext(s);

    mtInit(s, 2);
    let b: u32 = mtNext(s);

    mtInit(s, 3);
    let c: u32 = mtNext(s);

    assert a != b;
    assert b != c;
    assert a != c;

    return 0;
}

fn testChiSquared(s: *mut MtState) -> i32 {
    mtInit(s, 12345);

    const NUM_BINS: u32 = 16;
    const NUM_SAMPLES: u32 = 1600;
    const EXPECTED: u32 = 100;

    let mut bins: [u32; 16] = [0; 16];

    let mut i: u32 = 0;
    while i < NUM_SAMPLES {
        let val: u32 = mtNext(s);
        let bin: u32 = val >> 28;
        bins[bin] += 1;
        i += 1;
    }

    let mut chi2Scaled: u32 = 0;
    let mut b: u32 = 0;
    while b < NUM_BINS {
        let obs: i32 = bins[b] as i32;
        let exp: i32 = EXPECTED as i32;
        let diff: i32 = obs - exp;
        chi2Scaled += (diff * diff) as u32;
        b += 1;
    }

    assert chi2Scaled <= 5000;

    b = 0;
    while b < NUM_BINS {
        assert bins[b] != 0;
        b += 1;
    }

    b = 0;
    while b < NUM_BINS {
        assert bins[b] <= NUM_SAMPLES / 2;
        b += 1;
    }

    return 0;
}

fn testRegeneration(s: *mut MtState) -> i32 {
    mtInit(s, 7);

    let mut last: u32 = 0;
    let mut i: u32 = 0;
    while i < 700 {
        last = mtNext(s);
        i += 1;
    }

    mtInit(s, 7);
    let mut last2: u32 = 0;
    i = 0;
    while i < 700 {
        last2 = mtNext(s);
        i += 1;
    }

    assert last == last2;

    let mut more: u32 = 0;
    i = 0;
    while i < 700 {
        more = mtNext(s);
        i += 1;
    }
    assert more != 0;

    return 0;
}

fn testBitCoverage(s: *mut MtState) -> i32 {
    mtInit(s, 999);

    let mut orAll: u32 = 0;
    let mut andAll: u32 = 0xFFFFFFFF;

    let mut i: u32 = 0;
    while i < 200 {
        let v: u32 = mtNext(s);
        orAll |= v;
        andAll &= v;
        i += 1;
    }

    assert orAll == 0xFFFFFFFF;
    assert andAll != 0xFFFFFFFF;
    assert andAll == 0;

    return 0;
}

@default fn main() -> i32 {
    let mut mt: [u32; 624] = [0; 624];
    let mut s: MtState = MtState {
        mt: &mut mt[..],
        mti: 625,
    };

    let r1: i32 = testKnownSequence(&mut s);
    if r1 != 0 { return 10 + r1; }

    let r2: i32 = testDeterminism(&mut s);
    if r2 != 0 { return 20 + r2; }

    let r3: i32 = testDifferentSeeds(&mut s);
    if r3 != 0 { return 30 + r3; }

    let r4: i32 = testChiSquared(&mut s);
    if r4 != 0 { return 40 + r4; }

    let r5: i32 = testRegeneration(&mut s);
    if r5 != 0 { return 50 + r5; }

    let r6: i32 = testBitCoverage(&mut s);
    if r6 != 0 { return 60 + r6; }

    return 0;
}

1	//! returns: 0
2	//! Mersenne Twister PRNG with statistical testing.
3
4	const N: u32 = 624;
5	const M: u32 = 397;
6	const MATRIX_A: u32 = 0x9908B0DF;
7	const UPPER_MASK: u32 = 0x80000000;
8	const LOWER_MASK: u32 = 0x7FFFFFFF;
9
10	record MtState {
11	mt: *mut [u32],
12	mti: u32,
13	}
14
15	fn mtInit(s: *mut MtState, seed: u32) {
16	s.mt[0] = seed;
17	let mut i: u32 = 1;
18	while i < N {
19	let prev: u32 = s.mt[i - 1];
20	let xored: u32 = prev ^ (prev >> 30);
21
22	let lo: u32 = xored & 0xFFFF;
23	let hi: u32 = xored >> 16;
24	let c: u32 = 1812433253;
25	let clo: u32 = c & 0xFFFF;
26	let chi: u32 = c >> 16;
27
28	let ll: u32 = clo * lo;
29	let lh: u32 = clo * hi;
30	let hl: u32 = chi * lo;
31
32	let result: u32 = ll + ((lh + hl) << 16) + i;
33	s.mt[i] = result;
34	i += 1;
35	}
36	s.mti = N;
37	}
38
39	fn generateNumbers(s: *mut MtState) {
40	let mut i: u32 = 0;
41
42	while i < N - M {
43	let y: u32 = (s.mt[i] & UPPER_MASK) \| (s.mt[i + 1] & LOWER_MASK);
44	let mut mag: u32 = 0;
45	if y & 1 == 1 {
46	mag = MATRIX_A;
47	}
48	s.mt[i] = s.mt[i + M] ^ (y >> 1) ^ mag;
49	i += 1;
50	}
51
52	while i < N - 1 {
53	let y: u32 = (s.mt[i] & UPPER_MASK) \| (s.mt[i + 1] & LOWER_MASK);
54	let mut mag: u32 = 0;
55	if y & 1 == 1 {
56	mag = MATRIX_A;
57	}
58	s.mt[i] = s.mt[i + M - N] ^ (y >> 1) ^ mag;
59	i += 1;
60	}
61
62	let y: u32 = (s.mt[N - 1] & UPPER_MASK) \| (s.mt[0] & LOWER_MASK);
63	let mut mag: u32 = 0;
64	if y & 1 == 1 {
65	mag = MATRIX_A;
66	}
67	s.mt[N - 1] = s.mt[M - 1] ^ (y >> 1) ^ mag;
68
69	s.mti = 0;
70	}
71
72	fn mtNext(s: *mut MtState) -> u32 {
73	if s.mti >= N {
74	generateNumbers(s);
75	}
76
77	let mut y: u32 = s.mt[s.mti];
78	s.mti += 1;
79
80	y ^= (y >> 11);
81	y ^= ((y << 7) & 0x9D2C5680);
82	y ^= ((y << 15) & 0xEFC60000);
83	y ^= (y >> 18);
84
85	return y;
86	}
87
88	fn testKnownSequence(s: *mut MtState) -> i32 {
89	mtInit(s, 1);
90
91	let v0: u32 = mtNext(s);
92	assert v0 == 1791095845;
93
94	let v1: u32 = mtNext(s);
95	assert v1 == 4282876139;
96
97	let v2: u32 = mtNext(s);
98	assert v2 == 3093770124;
99
100	let v3: u32 = mtNext(s);
101	assert v3 == 4005303368;
102
103	let v4: u32 = mtNext(s);
104	assert v4 == 491263;
105
106	return 0;
107	}
108
109	fn testDeterminism(s: *mut MtState) -> i32 {
110	mtInit(s, 42);
111
112	let mut first: [u32; 10] = [0; 10];
113	let mut i: u32 = 0;
114	while i < 10 {
115	first[i] = mtNext(s);
116	i += 1;
117	}
118
119	mtInit(s, 42);
120
121	i = 0;
122	while i < 10 {
123	let v: u32 = mtNext(s);
124	if v != first[i] { return i as i32 + 1; }
125	i += 1;
126	}
127
128	return 0;
129	}
130
131	fn testDifferentSeeds(s: *mut MtState) -> i32 {
132	mtInit(s, 1);
133	let a: u32 = mtNext(s);
134
135	mtInit(s, 2);
136	let b: u32 = mtNext(s);
137
138	mtInit(s, 3);
139	let c: u32 = mtNext(s);
140
141	assert a != b;
142	assert b != c;
143	assert a != c;
144
145	return 0;
146	}
147
148	fn testChiSquared(s: *mut MtState) -> i32 {
149	mtInit(s, 12345);
150
151	const NUM_BINS: u32 = 16;
152	const NUM_SAMPLES: u32 = 1600;
153	const EXPECTED: u32 = 100;
154
155	let mut bins: [u32; 16] = [0; 16];
156
157	let mut i: u32 = 0;
158	while i < NUM_SAMPLES {
159	let val: u32 = mtNext(s);
160	let bin: u32 = val >> 28;
161	bins[bin] += 1;
162	i += 1;
163	}
164
165	let mut chi2Scaled: u32 = 0;
166	let mut b: u32 = 0;
167	while b < NUM_BINS {
168	let obs: i32 = bins[b] as i32;
169	let exp: i32 = EXPECTED as i32;
170	let diff: i32 = obs - exp;
171	chi2Scaled += (diff * diff) as u32;
172	b += 1;
173	}
174
175	assert chi2Scaled <= 5000;
176
177	b = 0;
178	while b < NUM_BINS {
179	assert bins[b] != 0;
180	b += 1;
181	}
182
183	b = 0;
184	while b < NUM_BINS {
185	assert bins[b] <= NUM_SAMPLES / 2;
186	b += 1;
187	}
188
189	return 0;
190	}
191
192	fn testRegeneration(s: *mut MtState) -> i32 {
193	mtInit(s, 7);
194
195	let mut last: u32 = 0;
196	let mut i: u32 = 0;
197	while i < 700 {
198	last = mtNext(s);
199	i += 1;
200	}
201
202	mtInit(s, 7);
203	let mut last2: u32 = 0;
204	i = 0;
205	while i < 700 {
206	last2 = mtNext(s);
207	i += 1;
208	}
209
210	assert last == last2;
211
212	let mut more: u32 = 0;
213	i = 0;
214	while i < 700 {
215	more = mtNext(s);
216	i += 1;
217	}
218	assert more != 0;
219
220	return 0;
221	}
222
223	fn testBitCoverage(s: *mut MtState) -> i32 {
224	mtInit(s, 999);
225
226	let mut orAll: u32 = 0;
227	let mut andAll: u32 = 0xFFFFFFFF;
228
229	let mut i: u32 = 0;
230	while i < 200 {
231	let v: u32 = mtNext(s);
232	orAll \|= v;
233	andAll &= v;
234	i += 1;
235	}
236
237	assert orAll == 0xFFFFFFFF;
238	assert andAll != 0xFFFFFFFF;
239	assert andAll == 0;
240
241	return 0;
242	}
243
244	@default fn main() -> i32 {
245	let mut mt: [u32; 624] = [0; 624];
246	let mut s: MtState = MtState {
247	mt: &mut mt[..],
248	mti: 625,
249	};
250
251	let r1: i32 = testKnownSequence(&mut s);
252	if r1 != 0 { return 10 + r1; }
253
254	let r2: i32 = testDeterminism(&mut s);
255	if r2 != 0 { return 20 + r2; }
256
257	let r3: i32 = testDifferentSeeds(&mut s);
258	if r3 != 0 { return 30 + r3; }
259
260	let r4: i32 = testChiSquared(&mut s);
261	if r4 != 0 { return 40 + r4; }
262
263	let r5: i32 = testRegeneration(&mut s);
264	if r5 != 0 { return 50 + r5; }
265
266	let r6: i32 = testBitCoverage(&mut s);
267	if r6 != 0 { return 60 + r6; }
268
269	return 0;
270	}