$(libmain_a_OBJECTS): $(gnulib_headers)
$(libmain_a_OBJECTS): src/options.h
-check_PROGRAMS = test/crossparse test/normalize test/randomdecl
+check_PROGRAMS = test/crossparse test/normalize test/randomdecl test/rng-test
check_LIBRARIES = libtest.a
libtest_a_SOURCES = test/testlib.c test/rng.c common/src/help.c
$(libtest_a_OBJECTS): $(gnulib_headers)
test_normalize_LDADD = src/output.lo src/normalize.lo $(TEST_LIBS)
$(test_normalize_OBJECTS): $(gnulib_headers)
+test_rng_test_LDADD = $(TEST_LIBS)
+$(test_rng_test_OBJECTS): $(gnulib_headers)
+EXTRA_DIST += test/xos256p.c
+
src/parse.lo: src/scan.h
src/scan.lo: src/parse.h
src/parse-decl.lo: src/scan.h src/parse.h src/typemap.h
/randomdecl
/crossparse
/normalize
+/rng-test
--- /dev/null
+/*
+ * Simple random number generator for testing.
+ * Copyright © 2022 Nick Bowler
+ *
+ * Directly compare the test lib RNG against the reference implementation.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <https://www.gnu.org/licenses/>.
+ */
+
+#include <config.h>
+#include <stdlib.h>
+
+#include "rng.c"
+#include "xos256p.c"
+
+int main(void)
+{
+ unsigned long long seed_state = 0xdeadbeeff00dcafe;
+ unsigned long long test_result, ref_result;
+ unsigned long long ref_state[4], test_state[4];
+ int i, ret = 0;
+
+ printf("1..200\n");
+ for (i = 0; i < 100; i++) {
+ s[0] = ref_state[0] = test_state[0] = splitmix64(&seed_state);
+ s[1] = ref_state[1] = test_state[1] = splitmix64(&seed_state);
+ s[2] = ref_state[2] = test_state[2] = splitmix64(&seed_state);
+ s[3] = ref_state[3] = test_state[3] = splitmix64(&seed_state);
+
+ ref_result = next();
+ test_result = xoshiro256p(test_state);
+
+ if (ref_result != test_result) {
+ printf("not ok %d rng output\n", 2*i+1);
+ printf("# Failed, unexpected result\n");
+ printf("# with initial state %llx %llx %llx %llx\n",
+ ref_state[0], ref_state[1],
+ ref_state[2], ref_state[3]);
+ printf("# received: %llx\n", test_result);
+ printf("# expected: %llx\n", ref_result);
+ ret = EXIT_FAILURE;
+ } else {
+ printf("ok %d rng output\n", 2*i+1);
+ }
+
+ if (s[0] != test_state[0] || s[1] != test_state[1]
+ || s[2] != test_state[2] || s[3] != test_state[3])
+ {
+ printf("not ok %d rng state update\n", 2*i+2);
+ printf("# Failed, state update differed\n");
+ printf("# with initial state %llx %llx %llx %llx\n",
+ ref_state[0], ref_state[1],
+ ref_state[2], ref_state[3]);
+ printf("# received: %llx %llx %llx %llx\n",
+ test_state[0], test_state[1],
+ test_state[2], test_state[3]);
+ printf("# expected: %llx %llx %llx %llx\n",
+ (unsigned long long)s[0],
+ (unsigned long long)s[1],
+ (unsigned long long)s[2],
+ (unsigned long long)s[3]);
+ ret = EXIT_FAILURE;
+ } else {
+ printf("ok %d rng state update\n", 2*i+2);
+ }
+ }
+
+ return ret;
+}
/*
- * Simple random number generator for testing.
- * Copyright © 2022 Nick Bowler
+ * Simple random number generator for testing.
+ * Copyright © 2022 Nick Bowler
*
- * This program is free software: you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation, either version 3 of the License, or
- * (at your option) any later version.
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
*
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
*
- * You should have received a copy of the GNU General Public License
- * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <https://www.gnu.org/licenses/>.
*
- * This implementation is adapted from xoshiro256+ and splitmix64
- * by David Blackman and Sebastiano Vigna, originally distributed
- * under the Creative Commons Zero public domain dedication.
+ * The RNG implementation is adapted from xoshiro256+ and splitmix64
+ * by David Blackman and Sebastiano Vigna, originally distributed under
+ * the Creative Commons Zero public domain dedication.
*/
#include <config.h>
static unsigned long long xoshiro256p(unsigned long long *s)
{
- unsigned long long ret = s[0];
- unsigned long long t;
+ unsigned long long tmp, ret;
- t = B64(s[1] << 17);
+ ret = B64(s[0] + s[3]);
+ tmp = B64(s[1] << 17);
s[2] ^= s[0];
s[3] ^= s[1];
s[1] ^= s[2];
s[0] ^= s[3];
- s[2] ^= t;
+ s[2] ^= tmp;
s[3] = rot_left64(s[3], 45);
return ret;
--- /dev/null
+/* Written in 2018 by David Blackman and Sebastiano Vigna (vigna@acm.org)
+
+To the extent possible under law, the author has dedicated all copyright
+and related and neighboring rights to this software to the public domain
+worldwide. This software is distributed without any warranty.
+
+See <http://creativecommons.org/publicdomain/zero/1.0/>. */
+
+#include <stdint.h>
+
+/* This is xoshiro256+ 1.0, our best and fastest generator for floating-point
+ numbers. We suggest to use its upper bits for floating-point
+ generation, as it is slightly faster than xoshiro256++/xoshiro256**. It
+ passes all tests we are aware of except for the lowest three bits,
+ which might fail linearity tests (and just those), so if low linear
+ complexity is not considered an issue (as it is usually the case) it
+ can be used to generate 64-bit outputs, too.
+
+ We suggest to use a sign test to extract a random Boolean value, and
+ right shifts to extract subsets of bits.
+
+ The state must be seeded so that it is not everywhere zero. If you have
+ a 64-bit seed, we suggest to seed a splitmix64 generator and use its
+ output to fill s. */
+
+
+static inline uint64_t rotl(const uint64_t x, int k) {
+ return (x << k) | (x >> (64 - k));
+}
+
+
+static uint64_t s[4];
+
+uint64_t next(void) {
+ const uint64_t result = s[0] + s[3];
+
+ const uint64_t t = s[1] << 17;
+
+ s[2] ^= s[0];
+ s[3] ^= s[1];
+ s[1] ^= s[2];
+ s[0] ^= s[3];
+
+ s[2] ^= t;
+
+ s[3] = rotl(s[3], 45);
+
+ return result;
+}
+
+
+/* This is the jump function for the generator. It is equivalent
+ to 2^128 calls to next(); it can be used to generate 2^128
+ non-overlapping subsequences for parallel computations. */
+
+void jump(void) {
+ static const uint64_t JUMP[] = { 0x180ec6d33cfd0aba, 0xd5a61266f0c9392c, 0xa9582618e03fc9aa, 0x39abdc4529b1661c };
+
+ uint64_t s0 = 0;
+ uint64_t s1 = 0;
+ uint64_t s2 = 0;
+ uint64_t s3 = 0;
+ for(int i = 0; i < sizeof JUMP / sizeof *JUMP; i++)
+ for(int b = 0; b < 64; b++) {
+ if (JUMP[i] & UINT64_C(1) << b) {
+ s0 ^= s[0];
+ s1 ^= s[1];
+ s2 ^= s[2];
+ s3 ^= s[3];
+ }
+ next();
+ }
+
+ s[0] = s0;
+ s[1] = s1;
+ s[2] = s2;
+ s[3] = s3;
+}
+
+
+/* This is the long-jump function for the generator. It is equivalent to
+ 2^192 calls to next(); it can be used to generate 2^64 starting points,
+ from each of which jump() will generate 2^64 non-overlapping
+ subsequences for parallel distributed computations. */
+
+void long_jump(void) {
+ static const uint64_t LONG_JUMP[] = { 0x76e15d3efefdcbbf, 0xc5004e441c522fb3, 0x77710069854ee241, 0x39109bb02acbe635 };
+
+ uint64_t s0 = 0;
+ uint64_t s1 = 0;
+ uint64_t s2 = 0;
+ uint64_t s3 = 0;
+ for(int i = 0; i < sizeof LONG_JUMP / sizeof *LONG_JUMP; i++)
+ for(int b = 0; b < 64; b++) {
+ if (LONG_JUMP[i] & UINT64_C(1) << b) {
+ s0 ^= s[0];
+ s1 ^= s[1];
+ s2 ^= s[2];
+ s3 ^= s[3];
+ }
+ next();
+ }
+
+ s[0] = s0;
+ s[1] = s1;
+ s[2] = s2;
+ s[3] = s3;
+}
-# Copyright © 2012, 2020 Nick Bowler
+# Copyright © 2012, 2020, 2022 Nick Bowler
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
AT_BANNER([Randomized tests])
+dnl Verify the RNG implementation
+AT_SETUP([xoshiro256p sanity])
+
+TEST_NEED_PROGRAM([rng-test])
+AT_CHECK([rng-test >out
+grep -v '^ok' out], [0], [1..200
+])
+
+AT_CLEANUP
+
dnl Verify that randomdecl actually produces all keywords and a variety
dnl of different declarations.
AT_SETUP([randomdecl sanity])
projects / cdecl99.git / commitdiff