From 88c05279e142ff97db82c30f4f3936b1ea5eb22a Mon Sep 17 00:00:00 2001 From: Nick Bowler Date: Tue, 8 Feb 2022 22:30:48 -0500 Subject: [PATCH] Remove randomdecl test dependency on GSL. It's a bit silly for a test application to depend on this huge library just for random number generation. We can just directly incorporate a simple RNG implementation which should be plenty good enough for this purpose. --- Makefile.am | 13 ++--- configure.ac | 13 +---- m4/cstring.m4 | 66 --------------------- m4/dxutils.m4 | 78 ------------------------- m4/gsl.m4 | 74 ------------------------ m4/strings.m4 | 3 - test/declgen.c | 97 ++++++++++--------------------- test/declgen.h | 35 ++++++++---- test/randomdecl.c | 10 ++-- test/rng.c | 143 ++++++++++++++++++++++++++++++++++++++++++++++ test/test.h | 26 +++++++++ 11 files changed, 234 insertions(+), 324 deletions(-) delete mode 100644 m4/cstring.m4 delete mode 100644 m4/dxutils.m4 delete mode 100644 m4/gsl.m4 delete mode 100644 m4/strings.m4 create mode 100644 test/rng.c diff --git a/Makefile.am b/Makefile.am index 081c183..3d6107a 100644 --- a/Makefile.am +++ b/Makefile.am @@ -1,4 +1,4 @@ -# Copyright © 2011-2013, 2019-2021 Nick Bowler +# Copyright © 2011-2013, 2019-2022 Nick Bowler # # License WTFPL2: Do What The Fuck You Want To Public License, version 2. # This is free software: you are free to do what the fuck you want to. @@ -16,8 +16,6 @@ AM_CPPFLAGS = -I$(top_builddir)/src -I$(top_srcdir)/src \ -DBISON_LOCALEDIR=\"$(BISON_LOCALEDIR)\" \ -DLOCALEDIR=\"$(localedir)\" -AM_CFLAGS = $(GSL_CFLAGS) - MAINTAINERCLEANFILES = src/scan.c src/scan.h src/scan.stamp \ src/parse.c src/parse.h src/parse.stamp @@ -66,17 +64,14 @@ libmain_a_SOURCES = src/cdecl99.c src/options.h $(libmain_a_OBJECTS): $(gnulib_headers) $(libmain_a_OBJECTS): src/options.h -check_PROGRAMS = test/crossparse test/normalize +check_PROGRAMS = test/crossparse test/normalize test/randomdecl check_LIBRARIES = libtest.a -libtest_a_SOURCES = test/testlib.c common/src/help.c +libtest_a_SOURCES = test/testlib.c test/rng.c common/src/help.c $(libtest_a_OBJECTS): $(gnulib_headers) -if HAVE_GSL -check_PROGRAMS += test/randomdecl test_randomdecl_SOURCES = test/randomdecl.c test/declgen.c -test_randomdecl_LDADD = libtest.a libcdecl.la libgnu.la $(GSL_LIBS) +test_randomdecl_LDADD = libtest.a libcdecl.la libgnu.la $(test_randomdecl_OBJECTS): $(gnulib_headers) -endif test_crossparse_LDADD = libtest.a libcdecl.la libgnu.la $(test_crossparse_OBJECTS): $(gnulib_headers) diff --git a/configure.ac b/configure.ac index bd07f46..506e295 100644 --- a/configure.ac +++ b/configure.ac @@ -1,4 +1,4 @@ -dnl Copyright © 2011-2013, 2020-2021 Nick Bowler +dnl Copyright © 2011-2013, 2020-2022 Nick Bowler dnl dnl License WTFPL2: Do What The Fuck You Want To Public License, version 2. dnl This is free software: you are free to do what the fuck you want to. @@ -82,17 +82,6 @@ AC_SUBST([BISON_COMPAT]) AH_TOP([#include ]) AH_BOTTOM([#include ]) -AC_ARG_WITH([gsl], - [AS_HELP_STRING([--with-gsl], - [specify whether to build test programs requiring the GNU Scientific Library. [default=auto]] - )], [with_gsl=$withval], [with_gsl=auto]) - -AS_CASE([$with_gsl], - [no], [have_gsl=no], - [yes], [DX_CHECK_GSL([1.0], [have_gsl=yes])], - [DX_CHECK_GSL([1.0], [have_gsl=yes], [have_gsl=no])]) -AM_CONDITIONAL([HAVE_GSL], [test x"$have_gsl" = x"yes"]) - AC_CONFIG_TESTDIR([.], [test:.]) DX_PROG_AUTOTEST AM_CONDITIONAL([HAVE_AUTOTEST], [test x"$dx_cv_autotest_works" = x"yes"]) diff --git a/m4/cstring.m4 b/m4/cstring.m4 deleted file mode 100644 index 9973f68..0000000 --- a/m4/cstring.m4 +++ /dev/null @@ -1,66 +0,0 @@ -dnl Copyright © 2011 Nick Bowler -dnl -dnl License WTFPL2: Do What The Fuck You Want To Public License, version 2. -dnl This is free software: you are free to do what the fuck you want to. -dnl There is NO WARRANTY, to the extent permitted by law. - -m4_define([_DX_COMPUTE_C_STRING_PROG], [AC_LANG_PROGRAM([dnl -#include -#include -$2 -char thestr@<:@@:>@ = $1; -char padstr@<:@@:>@ = "\n!&?~" $1 "~?&!\n"; -], [dnl -size_t i; -FILE *f = fopen("conftest.out", "w"); -if (!f) - return EXIT_FAILURE; -for (i = 0; i < sizeof thestr; i++) { - if (*(thestr+i) == '\n') - *(thestr+i) = ' '; -} -fprintf(f, "%s\n", thestr); -return 0; -])]) - -AC_DEFUN([_DX_COMPUTE_C_STRING_NORUN], [dnl -AC_REQUIRE([DX_PROG_STRINGS]) -if test x"$STRINGS" = x""; then - AC_MSG_WARN([strings is recommended for cross compilation]) - dx_c_strings=cat -else - dx_c_strings="$STRINGS -n 1" -fi -dnl else -AC_COMPILE_IFELSE([_DX_COMPUTE_C_STRING_PROG([$2], [$3])], [dnl - $dx_c_strings conftest.$OBJEXT | sed -n '/^!&?~/ { - t top - :top - s/^!&?~\(.*\)~?&!$/\1/p - t - N - s/\n/ /g - t top - }' > conftest.out - if read $1 < conftest.out; then :; else - AC_MSG_ERROR([failed to extract string due to cross compilation.]) - fi -], [dnl - ifelse([$4], [], [:], [$4])]) -dnl fi -]) - -dnl DX_COMPUTE_C_STRING(variable, string, [prologue], [action-if-failed]) -dnl -dnl Assigns the value of a C string literal specified by string to the shell -dnl variable specified by variable. Any newlines in the string are converted -dnl to spaces. In a cross compilation environment, it works by scanning a -dnl compiled object file. -AC_DEFUN([DX_COMPUTE_C_STRING], [dnl -AC_LANG_PUSH([C]) -AC_RUN_IFELSE([_DX_COMPUTE_C_STRING_PROG([$2], [$3])], - [read $1 < conftest.out], - [ifelse([$4], [], [:], [$4])], - [_DX_COMPUTE_C_STRING_NORUN([$1], [$2], [$3], [$4])]) -AC_LANG_POP([C]) -]) diff --git a/m4/dxutils.m4 b/m4/dxutils.m4 deleted file mode 100644 index 2f976d3..0000000 --- a/m4/dxutils.m4 +++ /dev/null @@ -1,78 +0,0 @@ -dnl Copyright © 2010-2011 Nick Bowler -dnl -dnl License WTFPL2: Do What The Fuck You Want To Public License, version 2. -dnl This is free software: you are free to do what the fuck you want to. -dnl There is NO WARRANTY, to the extent permitted by law. - -m4_pattern_forbid([^_?DX_]) - -dnl DX_PKG_CONFIG(env-base, [pkg-id], [pkg-help]) -AC_DEFUN([DX_PKG_CONFIG], [dnl -AC_ARG_VAR(m4_toupper([$1])[_CFLAGS], [C compiler flags for ]ifelse( - [$3], [], [$1], [$3]))dnl -AC_ARG_VAR(m4_toupper([$1])[_LIBS], [linker flags for ]ifelse( - [$3], [], [$1], [$3]))dnl - -ifelse([$2], [], [], [dnl -AC_REQUIRE([PKG_PROG_PKG_CONFIG])dnl -if test x"$PKG_CONFIG" != x; then - AC_MSG_CHECKING([pkg-config database for $2]) - pkg_failed=no - _PKG_CONFIG(m4_tolower([$1])[_cflags], [cflags], [$2]) - _PKG_CONFIG(m4_tolower([$1])[_libs], [libs], [$2]) - if test x$pkg_failed = xyes; then - errors=`$PKG_CONFIG --errors-to-stdout --print-errors $2` - echo "$errors" >&AS_MESSAGE_LOG_FD - AC_MSG_RESULT([no]) - else - AC_MSG_RESULT([yes]) - fi -fi])]) - -dnl _DX_CHECK_LIB(env-base, check-func, [cflags], [libs], [test]) -AC_DEFUN([_DX_CHECK_LIB], [dnl -if test x"$dx_cv_[]m4_tolower([$1])_found" = x"no"; then -if ifelse([$5], [], [:], [$5]); then - CFLAGS="$3 $dx_old_cflags" - LIBS="$4 $dx_old_libs" - - $2([dnl - dx_cv_[]m4_tolower([$1])_found="yes" - dx_cv_[]m4_tolower([$1])_cflags="$3" - dx_cv_[]m4_tolower([$1])_libs="$4" - ]) -fi -fi -]) - -dnl DX_CHECK_LIB_EXT(env-base, message, check-func, -dnl [[[cflags1],[libs1],[test1]],[[cflags2],[libs2],[test2]],...]) -AC_DEFUN([DX_CHECK_LIB_EXT], [dnl -AC_LANG_PUSH([C]) -dx_old_cflags=$CFLAGS -dx_old_libs=$LIBS - -AC_CACHE_CHECK([$2], [dx_cv_]m4_tolower([$1])[_found], [dnl -AC_CACHE_VAL([dx_cv_]m4_tolower([$1])[_libs], [dnl -AC_CACHE_VAL([dx_cv_]m4_tolower([$1])[_cflags], [dnl - dx_cv_[]m4_tolower([$1])_found=no - m4_foreach([dx_tuple], [$4], [_DX_CHECK_LIB([$1], [$3], dx_tuple)]) -])])]) - -if test x"$dx_cv_[]m4_tolower([$1])_found" = x"yes"; then - m4_toupper([$1])_CFLAGS=$dx_cv_[]m4_tolower([$1])_cflags - m4_toupper([$1])_LIBS=$dx_cv_[]m4_tolower([$1])_libs - AC_SUBST(m4_toupper([$1])[_CFLAGS]) - AC_SUBST(m4_toupper([$1])[_LIBS]) -fi - -CFLAGS=$dx_old_cflags -LIBS=$dx_old_libs -AC_LANG_POP([C]) -]) - -dnl DX_CHECK_LIB(env-base, message, test-program, -dnl [[[cflags1],[libs1],[test1]],[[cflags2],[libs2],[test2]],...]) -AC_DEFUN([DX_CHECK_LIB], [dnl - DX_CHECK_LIB_EXT([$1], [$2], [m4_curry([AC_LINK_IFELSE], [$3])], [$4]) -]) diff --git a/m4/gsl.m4 b/m4/gsl.m4 deleted file mode 100644 index 781fed5..0000000 --- a/m4/gsl.m4 +++ /dev/null @@ -1,74 +0,0 @@ -dnl Copyright © 2009-2011 Nick Bowler -dnl -dnl License WTFPL2: Do What The Fuck You Want To Public License, version 2. -dnl This is free software: you are free to do what the fuck you want to. -dnl There is NO WARRANTY, to the extent permitted by law. - -AC_DEFUN([_DX_CHECK_GSL_TEST], [dnl - DX_COMPUTE_C_STRING([gsl_version], [GSL_VERSION], [dnl -#include -], [gsl_version=0]) - - AS_VERSION_COMPARE([$gsl_version], [$1], - [gsl_version_ok=no], - [gsl_version_ok=yes], - [gsl_version_ok=yes]) - - if test x"$gsl_version_ok" = x"yes"; then - AC_LINK_IFELSE([AC_LANG_PROGRAM([dnl -#include -#include -], [dnl -double m1buf@<:@16@:>@, m2buf@<:@16@:>@, m3buf@<:@16@:>@; - -gsl_matrix_view m1 = gsl_matrix_view_array(m1buf, 4, 4); -gsl_matrix_view m2 = gsl_matrix_view_array(m2buf, 4, 4); -gsl_matrix_view m3 = gsl_matrix_view_array(m3buf, 4, 4); - -gsl_matrix_set_identity(&m1.matrix); -gsl_matrix_set_identity(&m2.matrix); -gsl_blas_dgemm(CblasNoTrans, CblasNoTrans, 1, &m1.matrix, &m2.matrix, - 0, &m3.matrix); - -return 0; -])], [$2]) - fi -]) - -dnl DX_CHECK_GSL([min-version], [action-if-found], [action-if-not-found]) -AC_DEFUN([DX_CHECK_GSL], [dnl -DX_PKG_CONFIG([gsl], [gsl], [GSL]) -AC_ARG_VAR([GSL_CONFIG], [path to gsl-config binary]) -AC_PATH_PROG([GSL_CONFIG], [gsl-config]) - -if test x"$GSL_CONFIG" != x; then - gsl_config_cflags=`$GSL_CONFIG --cflags` - gsl_config_libs=`$GSL_CONFIG --libs` -fi - -DX_CHECK_LIB_EXT([gsl], - [for GSL version at least ifelse([$1], [], [1.0], [$1])], - [m4_curry([_DX_CHECK_GSL_TEST], [ifelse([$1], [], [1.0], [$1])])], - [dnl - [[$GSL_CFLAGS], [$GSL_LIBS]], - [[$pkg_cv_gsl_cflags], [$pkg_cv_gsl_libs], - [test x"$pkg_failed" != x"yes"]], - [[$gsl_config_cflags], [$gsl_config_libs], - [test x"$SDL_CONFIG" != x""]], - ]) - -if test x"$dx_cv_gsl_found" = x"yes"; then - ifelse([$2], [], [:], [$2]) -else - ifelse([$3], [], [AC_MSG_FAILURE([dnl -GSL version at least ifelse([$1], [], [1.0], [$1]) is required. The -latest version can be optained from http://gnu.org/software/gsl/. - -If GSL is installed but was not found by this configure script, consider -adjusting GSL_CFLAGS, GSL_LIBS and/or GSL_CONFIG as necessary. - -If pkg-config is installed, it may help to adjust PKG_CONFIG_PATH -if GSL is installed in a non-standard prefix. -])], [$3]) -fi -]) diff --git a/m4/strings.m4 b/m4/strings.m4 deleted file mode 100644 index 6b0f269..0000000 --- a/m4/strings.m4 +++ /dev/null @@ -1,3 +0,0 @@ -AC_DEFUN([DX_PROG_STRINGS], [dnl -AC_CHECK_TOOL([STRINGS], [strings]) -]) diff --git a/test/declgen.c b/test/declgen.c index c02613a..c59e86c 100644 --- a/test/declgen.c +++ b/test/declgen.c @@ -1,6 +1,6 @@ /* * Generate random C declarations for testing. - * Copyright © 2011 Nick Bowler + * Copyright © 2012, 2021-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 @@ -24,34 +24,29 @@ #include #include #include -#include #include "declgen.h" #include "cdecl.h" #include "test.h" -struct gen_rng { - gsl_rng *rng; -}; - /* * Generate a random identifier. We arbitrarily pick 10 as the largest * possible. Avoid generating keywords, including the English ones, by * excluding the letters t, o, a and n. Reserved words are OK. */ -char *gen_identifier(struct gen_rng *rng) +char *gen_identifier(struct test_rng *rng) { static const char valid[59] = "_bcdefghijklmpqrsuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"; char *str; size_t n; - n = gsl_rng_uniform_int(rng->rng, 10)+1; + n = test_rng_uniform_int(rng, 10)+1; str = malloc_nofail(n+1); /* Exclude 10 digits from the first character. */ - str[0] = valid[gsl_rng_uniform_int(rng->rng, sizeof valid - 10)]; + str[0] = valid[test_rng_uniform_int(rng, sizeof valid - 10)]; for (size_t i = 1; i < n; i++) - str[i] = valid[gsl_rng_uniform_int(rng->rng, sizeof valid)]; + str[i] = valid[test_rng_uniform_int(rng, sizeof valid)]; str[n] = 0; return str; @@ -64,18 +59,18 @@ char *gen_identifier(struct gen_rng *rng) * qualifier is chosen uniformly at random from the set of possibilities: * const, volatile and, if restrictqual is true, restrict. */ -struct cdecl_declspec *gen_qualifiers(struct gen_rng *rng, bool restrictqual) +struct cdecl_declspec *gen_qualifiers(struct test_rng *rng, bool restrictqual) { struct cdecl_declspec *s = NULL, *p; - while (gsl_rng_uniform(rng->rng) < 0.5) { + while (test_rng_uniform(rng) < 0.5) { p = s; s = malloc_nofail(sizeof *s); *s = (struct cdecl_declspec) { .next = p, }; - switch (gsl_rng_uniform_int(rng->rng, 2+restrictqual)) { + switch (test_rng_uniform_int(rng, 2+restrictqual)) { case 0: s->type = CDECL_QUAL_CONST; break; @@ -97,11 +92,11 @@ struct cdecl_declspec *gen_qualifiers(struct gen_rng *rng, bool restrictqual) * Generate random function specifiers. Like qualifiers, function specifiers * can appear multiple times. */ -struct cdecl_declspec *gen_funcspecs(struct gen_rng *rng) +struct cdecl_declspec *gen_funcspecs(struct test_rng *rng) { struct cdecl_declspec *s = NULL, *p; - while (gsl_rng_uniform(rng->rng) < 0.5) { + while (test_rng_uniform(rng) < 0.5) { p = s; s = malloc_nofail(sizeof *s); @@ -119,11 +114,11 @@ struct cdecl_declspec *gen_funcspecs(struct gen_rng *rng) * true, then the only possible storage-class specifier is "register". * Otherwise, a specifier type will be selected uniformly at random. */ -struct cdecl_declspec *gen_storspecs(struct gen_rng *rng, bool registeronly) +struct cdecl_declspec *gen_storspecs(struct test_rng *rng, bool registeronly) { struct cdecl_declspec *s; - if (gsl_rng_uniform(rng->rng) < 0.5) + if (test_rng_uniform(rng) < 0.5) return NULL; s = malloc_nofail(sizeof *s); @@ -134,7 +129,7 @@ struct cdecl_declspec *gen_storspecs(struct gen_rng *rng, bool registeronly) if (registeronly) return s; - switch (gsl_rng_uniform_int(rng->rng, 5)) { + switch (test_rng_uniform_int(rng, 5)) { case 0: s->type = CDECL_STOR_TYPEDEF; break; case 1: s->type = CDECL_STOR_REGISTER; break; case 2: s->type = CDECL_STOR_STATIC; break; @@ -152,13 +147,12 @@ struct cdecl_declspec *gen_storspecs(struct gen_rng *rng, bool registeronly) */ #include "typegen.h" -struct cdecl_declspec *gen_typespecs(struct gen_rng *rng, bool voidtype) +struct cdecl_declspec *gen_typespecs(struct test_rng *rng, bool voidtype) { struct cdecl_declspec *specs; retry: - specs = gen_raw_typespecs(gsl_rng_uniform_int(rng->rng, - GEN_TOTAL_TYPES)); + specs = gen_raw_typespecs(test_rng_uniform_int(rng, GEN_TOTAL_TYPES)); switch (specs->type) { /* void is not always valid, so we might need to pick again. */ @@ -183,7 +177,7 @@ retry: } struct cdecl_declspec * -gen_randomize_specs(struct gen_rng *rng, struct cdecl_declspec *specs) +gen_randomize_specs(struct test_rng *rng, struct cdecl_declspec *specs) { struct cdecl_declspec **p; size_t n = 0; @@ -207,7 +201,7 @@ gen_randomize_specs(struct gen_rng *rng, struct cdecl_declspec *specs) struct cdecl_declspec *tmp; size_t r; - r = gsl_rng_uniform_int(rng->rng, n-i); + r = test_rng_uniform_int(rng, n-i); tmp = p[i]; p[i] = p[r+i]; p[r+i] = tmp; @@ -241,7 +235,7 @@ gen_randomize_specs(struct gen_rng *rng, struct cdecl_declspec *specs) * be generated by this function: use gen_qualifiers directly. */ struct cdecl_declspec * -gen_declspecs(struct gen_rng *rng, unsigned flags) +gen_declspecs(struct test_rng *rng, unsigned flags) { struct cdecl_declspec *s, *p; @@ -263,13 +257,13 @@ gen_declspecs(struct gen_rng *rng, unsigned flags) return gen_randomize_specs(rng, s); } -static uintmax_t gen_uintmax(struct gen_rng *rng) +static uintmax_t gen_uintmax(struct test_rng *rng) { unsigned char tmp; uintmax_t ret = 0; for (size_t i = 0; i < sizeof ret; i++) { - tmp = gsl_rng_uniform_int(rng->rng, UCHAR_MAX+1); + tmp = test_rng_uniform_int(rng, UCHAR_MAX+1); ret <<= CHAR_BIT; ret |= tmp; } @@ -281,12 +275,12 @@ static uintmax_t gen_uintmax(struct gen_rng *rng) * Generate a random array declarator, selecting one of four possibilities * uniformly at random. */ -static void gen_array(struct gen_rng *rng, struct cdecl_declarator *d) +static void gen_array(struct test_rng *rng, struct cdecl_declarator *d) { d->type = CDECL_DECL_ARRAY; d->u.array = (struct cdecl_array){0}; - switch (gsl_rng_uniform_int(rng->rng, 4)) { + switch (test_rng_uniform_int(rng, 4)) { case 0: d->u.array.vla = malloc_nofail(1); d->u.array.vla[0] = 0; @@ -306,12 +300,12 @@ static void gen_array(struct gen_rng *rng, struct cdecl_declarator *d) } /* Generate a function declarator. */ -static void gen_function(struct gen_rng *rng, struct cdecl_declarator *d) +static void gen_function(struct test_rng *rng, struct cdecl_declarator *d) { d->type = CDECL_DECL_FUNCTION; d->u.function.parameters = NULL; - while (gsl_rng_uniform(rng->rng) < 0.5) { + while (test_rng_uniform(rng) < 0.5) { unsigned flags = GEN_ONLY_REGISTER | GEN_NO_FUNCTION; struct cdecl *param; @@ -330,8 +324,8 @@ static void gen_function(struct gen_rng *rng, struct cdecl_declarator *d) } if (d->u.function.parameters) { - d->u.function.variadic = gsl_rng_uniform(rng->rng) < 0.5; - } else if (gsl_rng_uniform(rng->rng) < 0.5) { + d->u.function.variadic = test_rng_uniform(rng) < 0.5; + } else if (test_rng_uniform(rng) < 0.5) { struct cdecl *param; /* We will never generate (void) above; do it here. */ @@ -358,13 +352,13 @@ static void gen_function(struct gen_rng *rng, struct cdecl_declarator *d) * are ultimately terminated by either a null declarator or an identifier, * selected uniformly at random. */ -struct cdecl_declarator *gen_declarators(struct gen_rng *rng) +struct cdecl_declarator *gen_declarators(struct test_rng *rng) { struct cdecl_declarator *d, *p; unsigned limit = 3; d = malloc_nofail(sizeof *d); - if (gsl_rng_uniform(rng->rng) < 0.5) { + if (test_rng_uniform(rng) < 0.5) { *d = (struct cdecl_declarator) { .type = CDECL_DECL_NULL, }; @@ -375,14 +369,14 @@ struct cdecl_declarator *gen_declarators(struct gen_rng *rng) }; } - while (gsl_rng_uniform(rng->rng) < 0.5) { + while (test_rng_uniform(rng) < 0.5) { p = d; d = malloc_nofail(sizeof *d); *d = (struct cdecl_declarator) { .child = p, }; - switch (gsl_rng_uniform_int(rng->rng, limit)) { + switch (test_rng_uniform_int(rng, limit)) { case 0: d->type = CDECL_DECL_POINTER; d->u.pointer = (struct cdecl_pointer) { @@ -412,37 +406,6 @@ struct cdecl_declarator *gen_declarators(struct gen_rng *rng) return d; } -struct gen_rng *gen_alloc_rng(const char *seed_str) -{ - unsigned long seed; - struct gen_rng *rng; - char *end; - - errno = 0; - seed = strtoul(seed_str, &end, 0); - if (*end != 0) { - fprintf(stderr, "%s: invalid seed\n", seed_str); - return NULL; - } else if (errno != 0) { - fprintf(stderr, "%s: invalid seed: %s\n", - seed_str, strerror(errno)); - return NULL; - } - - rng = malloc_nofail(sizeof *rng); - rng->rng = gsl_rng_alloc(gsl_rng_mt19937); - gsl_rng_set(rng->rng, seed); - - return rng; -} - -void gen_free_rng(struct gen_rng *rng) -{ - if (rng) - gsl_rng_free(rng->rng); - free(rng); -} - static void gen_free_parameters(struct cdecl *x) { struct cdecl *p; diff --git a/test/declgen.h b/test/declgen.h index 414f04e..ff40b90 100644 --- a/test/declgen.h +++ b/test/declgen.h @@ -1,8 +1,24 @@ +/* + * Generate random C declarations for testing. + * Copyright © 2012, 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 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 . + */ + #ifndef CDECL_DECLGEN_H_ #define CDECL_DECLGEN_H_ -struct gen_rng; - enum { GEN_NO_FUNCTION = 0x01, GEN_NO_STORAGE = 0x02, @@ -10,15 +26,14 @@ enum { GEN_ONLY_REGISTER = 0x08, }; -struct cdecl_declspec *gen_qualifiers(struct gen_rng *rng, _Bool pointer); -struct cdecl_declspec *gen_typespecs(struct gen_rng *rng, _Bool novoid); -struct cdecl_declspec *gen_randomize_specs(struct gen_rng *rng, - struct cdecl_declspec *specs); -struct cdecl_declspec *gen_declspecs(struct gen_rng *rng, unsigned flags); -struct cdecl_declarator *gen_declarators(struct gen_rng *rng); +struct test_rng; -struct gen_rng *gen_alloc_rng(const char *seed); -void gen_free_rng(struct gen_rng *rng); +struct cdecl_declspec *gen_qualifiers(struct test_rng *rng, _Bool pointer); +struct cdecl_declspec *gen_typespecs(struct test_rng *rng, _Bool novoid); +struct cdecl_declspec *gen_randomize_specs(struct test_rng *rng, + struct cdecl_declspec *specs); +struct cdecl_declspec *gen_declspecs(struct test_rng *rng, unsigned flags); +struct cdecl_declarator *gen_declarators(struct test_rng *rng); void gen_free_declspecs(struct cdecl_declspec *x); void gen_free_declarators(struct cdecl_declarator *x); diff --git a/test/randomdecl.c b/test/randomdecl.c index c9f4e41..9e9271e 100644 --- a/test/randomdecl.c +++ b/test/randomdecl.c @@ -1,6 +1,6 @@ /* * Generate random C declarations for testing. - * 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 @@ -61,7 +61,7 @@ static void print_help(void) test_print_options(lopts); } -static struct cdecl *random_decl(struct gen_rng *rng) +static struct cdecl *random_decl(struct test_rng *rng) { struct cdecl *decl; unsigned flags = 0; @@ -85,7 +85,7 @@ static struct cdecl *random_decl(struct gen_rng *rng) int main(int argc, char **argv) { const char *seed = "", *count_str = NULL; - struct gen_rng *rng; + struct test_rng *rng; struct cdecl *decl; unsigned long count = 0; int opt, mode = MODE_CDECL; @@ -124,7 +124,7 @@ int main(int argc, char **argv) return EXIT_FAILURE; } - rng = gen_alloc_rng(seed); + rng = test_rng_alloc(seed); if (!rng) return EXIT_FAILURE; @@ -142,7 +142,7 @@ int main(int argc, char **argv) free(decl); } - gen_free_rng(rng); + test_rng_free(rng); return EXIT_SUCCESS; } diff --git a/test/rng.c b/test/rng.c new file mode 100644 index 0000000..884d981 --- /dev/null +++ b/test/rng.c @@ -0,0 +1,143 @@ +/* + * 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 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 . + * + * This implementation is adapted from xoshiro256+ and splitmix64 + * by David Blackman and Sebastiano Vigna, originally distributed + * under the Creative Commons Zero public domain dedication. + */ + +#include +#include +#include +#include +#include +#include +#include +#include + +#include "test.h" + +#define B64(x) ((x) & 0xffffffffffffffff) + +struct test_rng { + unsigned long long state[4]; +}; + +/* Rotate val left by n bits. The behaviour is undefined if n is zero. */ +static unsigned long long rot_left64(unsigned long long val, int n) +{ + return B64( (val << n) | (val >> (64 - n)) ); +} + +static unsigned long long xoshiro256p(unsigned long long *s) +{ + unsigned long long ret = s[0]; + unsigned long long t; + + t = B64(s[1] << 17); + + s[2] ^= s[0]; + s[3] ^= s[1]; + s[1] ^= s[2]; + s[0] ^= s[3]; + s[2] ^= t; + s[3] = rot_left64(s[3], 45); + + return ret; +} + +static unsigned long long splitmix64(unsigned long long *state) +{ + unsigned long long z; + + z = B64(*state += 0x9e3779b97f4a7c15); + z = B64((z ^ (z >> 30)) * 0xbf58476d1ce4e5b9); + z = B64((z ^ (z >> 27)) * 0x94d049bb133111eb); + + return z ^ (z >> 31); +} + +struct test_rng *test_rng_alloc(const char *seed_str) +{ + unsigned long long seed; + struct test_rng *rng; + char *end; + + errno = 0; + seed = strtoull(seed_str, &end, 0); + if (*end != 0) { + fprintf(stderr, "%s: invalid seed\n", seed_str); + return NULL; + } else if (errno != 0) { + fprintf(stderr, "%s: invalid seed: %s\n", + seed_str, strerror(errno)); + return NULL; + } + + rng = malloc_nofail(sizeof *rng); + rng->state[0] = splitmix64(&seed); + rng->state[1] = splitmix64(&seed); + rng->state[2] = splitmix64(&seed); + rng->state[3] = splitmix64(&seed); + + return rng; +} + +void test_rng_free(struct test_rng *rng) +{ + free(rng); +} + +#define BITS_PER_FP_DIGIT ( FLT_RADIX < 4 ? 1 \ + : FLT_RADIX < 8 ? 2 \ + : FLT_RADIX < 16 ? 3 \ + : FLT_RADIX < 32 ? 4 \ + : 5 ) + +double test_rng_uniform(struct test_rng *rng) +{ + unsigned long long val = xoshiro256p(rng->state); + int prec = MIN(64, DBL_MANT_DIG*BITS_PER_FP_DIGIT); + + return ldexp(val >> (64-prec), -prec); +} + +/* Calculate the least power of two greater than val, minus 1. */ +static unsigned rng_mask(unsigned val) +{ + val |= val >> 1; + val |= val >> 2; + val |= val >> 4; + val |= val >> 8; + + if (UINT_MAX >= 65536) + val |= val >> 16; + + return val; +} + +unsigned test_rng_uniform_int(struct test_rng *rng, unsigned max) +{ + unsigned mask = rng_mask(max-1); + unsigned long long val; + + do { + val = ( xoshiro256p(rng->state) >> 32 ) & mask; + } while (val >= max); + + return val; +} diff --git a/test/test.h b/test/test.h index c1be21a..5ffe291 100644 --- a/test/test.h +++ b/test/test.h @@ -27,10 +27,14 @@ # define _(x) (x) #endif +#define MIN(a, b) ((a) < (b) ? (a) : (b)) + struct cdecl_declspec; struct option; struct cdecl; +struct test_rng; + void *malloc_nofail(size_t size); void *realloc_nofail(void *ptr, size_t size); void test_print_specifiers(struct cdecl_declspec *spec); @@ -42,4 +46,26 @@ bool strict_strtoul(unsigned long *val, const char *str, int base); void test_print_version(const char *program); void test_print_options(const struct option *lopts); +/* + * Allocate a new random number generator with the given seed string (which + * should normally be a command-line argument). The string is parsed as an + * integer value as if by strtoull with a base of 0. + */ +struct test_rng *test_rng_alloc(const char *seed); + +/* + * Free the random number generator rng. + */ +void test_rng_free(struct test_rng *rng); + +/* + * Return a random value uniformly on the half-open interval [0,1) + */ +double test_rng_uniform(struct test_rng *rng); + +/* + * Return a random integer uniformly on the closed interval [0, limit-1] + */ +unsigned test_rng_uniform_int(struct test_rng *rng, unsigned limit); + #endif -- 2.43.2