diff options
Diffstat (limited to 'src')
32 files changed, 2050 insertions, 378 deletions
diff --git a/src/Makefile.am b/src/Makefile.am index f8d81e5..e73b2bf 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -252,8 +252,12 @@ libknots_la_SOURCES = \ common/ref.c \ common/errors.h \ common/errors.c \ - common/WELL1024a.h \ - common/WELL1024a.c \ + common/dSFMT.h \ + common/dSFMT-params.h \ + common/dSFMT-params521.h \ + common/dSFMT.c \ + common/prng.h \ + common/prng.c \ common/fdset.h \ common/fdset.c \ common/fdset_poll.h \ diff --git a/src/Makefile.in b/src/Makefile.in index d144a8d..f2d122c 100644 --- a/src/Makefile.in +++ b/src/Makefile.in @@ -80,8 +80,8 @@ libknots_la_DEPENDENCIES = @LIBOBJS@ am_libknots_la_OBJECTS = slab.lo malloc.lo tap.lo lists.lo base32.lo \ print.lo dynamic-array.lo skip-list.lo base32hex.lo \ general-tree.lo evqueue.lo evsched.lo acl.lo sockaddr.lo \ - crc.lo ref.lo errors.lo WELL1024a.lo fdset.lo fdset_poll.lo \ - fdset_kqueue.lo fdset_epoll.lo + crc.lo ref.lo errors.lo dSFMT.lo prng.lo fdset.lo \ + fdset_poll.lo fdset_kqueue.lo fdset_epoll.lo libknots_la_OBJECTS = $(am_libknots_la_OBJECTS) am__installdirs = "$(DESTDIR)$(libexecdir)" "$(DESTDIR)$(sbindir)" \ "$(DESTDIR)$(man8dir)" @@ -575,8 +575,12 @@ libknots_la_SOURCES = \ common/ref.c \ common/errors.h \ common/errors.c \ - common/WELL1024a.h \ - common/WELL1024a.c \ + common/dSFMT.h \ + common/dSFMT-params.h \ + common/dSFMT-params521.h \ + common/dSFMT.c \ + common/prng.h \ + common/prng.c \ common/fdset.h \ common/fdset.c \ common/fdset_poll.h \ @@ -837,7 +841,6 @@ mostlyclean-compile: distclean-compile: -rm -f *.tab.c -@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/WELL1024a.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/acl.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/acl_tests.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/base32.Plo@am__quote@ @@ -849,6 +852,7 @@ distclean-compile: @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/crc.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/cuckoo-hash-table.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/cuckoo_tests.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/dSFMT.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/da_tests.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/ddns.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/debug.Plo@am__quote@ @@ -902,6 +906,7 @@ distclean-compile: @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/parser-descriptor.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/parser-util.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/print.Plo@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/prng.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/process.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/query.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/query_tests.Po@am__quote@ @@ -1443,12 +1448,19 @@ errors.lo: common/errors.c @AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ @am__fastdepCC_FALSE@ $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o errors.lo `test -f 'common/errors.c' || echo '$(srcdir)/'`common/errors.c -WELL1024a.lo: common/WELL1024a.c -@am__fastdepCC_TRUE@ $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT WELL1024a.lo -MD -MP -MF $(DEPDIR)/WELL1024a.Tpo -c -o WELL1024a.lo `test -f 'common/WELL1024a.c' || echo '$(srcdir)/'`common/WELL1024a.c -@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/WELL1024a.Tpo $(DEPDIR)/WELL1024a.Plo -@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='common/WELL1024a.c' object='WELL1024a.lo' libtool=yes @AMDEPBACKSLASH@ +dSFMT.lo: common/dSFMT.c +@am__fastdepCC_TRUE@ $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT dSFMT.lo -MD -MP -MF $(DEPDIR)/dSFMT.Tpo -c -o dSFMT.lo `test -f 'common/dSFMT.c' || echo '$(srcdir)/'`common/dSFMT.c +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/dSFMT.Tpo $(DEPDIR)/dSFMT.Plo +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='common/dSFMT.c' object='dSFMT.lo' libtool=yes @AMDEPBACKSLASH@ @AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ -@am__fastdepCC_FALSE@ $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o WELL1024a.lo `test -f 'common/WELL1024a.c' || echo '$(srcdir)/'`common/WELL1024a.c +@am__fastdepCC_FALSE@ $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o dSFMT.lo `test -f 'common/dSFMT.c' || echo '$(srcdir)/'`common/dSFMT.c + +prng.lo: common/prng.c +@am__fastdepCC_TRUE@ $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT prng.lo -MD -MP -MF $(DEPDIR)/prng.Tpo -c -o prng.lo `test -f 'common/prng.c' || echo '$(srcdir)/'`common/prng.c +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/prng.Tpo $(DEPDIR)/prng.Plo +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='common/prng.c' object='prng.lo' libtool=yes @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o prng.lo `test -f 'common/prng.c' || echo '$(srcdir)/'`common/prng.c fdset.lo: common/fdset.c @am__fastdepCC_TRUE@ $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT fdset.lo -MD -MP -MF $(DEPDIR)/fdset.Tpo -c -o fdset.lo `test -f 'common/fdset.c' || echo '$(srcdir)/'`common/fdset.c diff --git a/src/common/LICENSE.txt b/src/common/LICENSE.txt new file mode 100644 index 0000000..15e3bef --- /dev/null +++ b/src/common/LICENSE.txt @@ -0,0 +1,29 @@ +Copyright (c) 2007, 2008 Mutsuo Saito, Makoto Matsumoto and Hiroshima +University. All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + copyright notice, this list of conditions and the following + disclaimer in the documentation and/or other materials provided + with the distribution. + * Neither the name of the Hiroshima University nor the names of + its contributors may be used to endorse or promote products + derived from this software without specific prior written + permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. diff --git a/src/common/WELL1024a.c b/src/common/WELL1024a.c deleted file mode 100644 index 0d1526b..0000000 --- a/src/common/WELL1024a.c +++ /dev/null @@ -1,133 +0,0 @@ -/* ***************************************************************************** */ -/* Copyright: Francois Panneton and Pierre L'Ecuyer, University of Montreal */ -/* Makoto Matsumoto, Hiroshima University */ -/* Notice: This code can be used freely for personal, academic, */ -/* or non-commercial purposes. For commercial purposes, */ -/* please contact P. L'Ecuyer at: lecuyer@iro.UMontreal.ca */ -/* ***************************************************************************** */ - -#include <pthread.h> -#include <string.h> -#include <stdlib.h> -#include <time.h> -#include <sys/time.h> -#include <stdio.h> - -#include "WELL1024a.h" - -#define W 32 -#define M1 3 -#define M2 24 -#define M3 10 - -#define MAT0POS(t,v) (v^(v>>t)) -#define MAT0NEG(t,v) (v^(v<<(-(t)))) -#define Identity(v) (v) - -#define V0(s) (s)->state[(s)->i ] -#define VM1(s) (s)->state[((s)->i+M1) & 0x0000001fU] -#define VM2(s) (s)->state[((s)->i+M2) & 0x0000001fU] -#define VM3(s) (s)->state[((s)->i+M3) & 0x0000001fU] -#define VRm1(s) (s)->state[((s)->i+31) & 0x0000001fU] -#define newV0(s) (s)->state[((s)->i+31) & 0x0000001fU] -#define newV1(s) (s)->state[(s)->i ] - -#define FACT 2.32830643653869628906e-10 - -rngstate_t* InitWELLRNG1024a (unsigned *init) { - - rngstate_t *s = malloc(sizeof(rngstate_t)); - if (s == 0) { - return 0; - } - - s->i = 0; - for (int j = 0; j < WELL1024_WIDTH; j++) - s->state[j] = init[j]; - return s; -} - -double WELLRNG1024a (rngstate_t* s) { - unsigned z0 = VRm1(s); - unsigned z1 = Identity(V0(s)) ^ MAT0POS (8, VM1(s)); - unsigned z2 = MAT0NEG (-19, VM2(s)) ^ MAT0NEG(-14,VM3(s)); - newV1(s) = z1 ^ z2; - newV0(s) = MAT0NEG (-11,z0) ^ MAT0NEG(-7,z1) ^ MAT0NEG(-13,z2) ; - s->i = (s->i + 31) & 0x0000001fU; - return ((double) s->state[s->i] * FACT); -} - -/*! \brief TLS unique key for each thread seed. */ -static pthread_key_t tls_prng_key; -static pthread_once_t tls_prng_once = PTHREAD_ONCE_INIT; - -static void tls_prng_deinit(void *ptr) -{ - free(ptr); -} - -static void tls_prng_deinit_main() -{ - tls_prng_deinit(pthread_getspecific(tls_prng_key)); -} - -static void tls_prng_init() -{ - (void) pthread_key_create(&tls_prng_key, tls_prng_deinit); - atexit(tls_prng_deinit_main); // Main thread cleanup -} - -double tls_rand() -{ - /* Setup PRNG state for current thread. */ - (void)pthread_once(&tls_prng_once, tls_prng_init); - - /* Create PRNG state if not exists. */ - rngstate_t* s = pthread_getspecific(tls_prng_key); - if (!s) { - /* Initialize seed from system PRNG generator. */ - unsigned init[WELL1024_WIDTH]; - FILE *fp = fopen("/dev/urandom", "r"); - if (fp == NULL) { - fp = fopen("/dev/random", "r"); - } - if (fp == NULL) { - fprintf(stderr, "error: PRNG: cannot seed from " - "/dev/urandom, seeding from local time\n"); - struct timeval tv; - if (gettimeofday(&tv, NULL) == 0) { - memcpy(init, &tv, sizeof(struct timeval)); - } else { - /* Last resort. */ - time_t tm = time(NULL); - memcpy(init, &tm, sizeof(time_t)); - } - } else { - for (unsigned i = 0; i < WELL1024_WIDTH; ++i) { - int rc = fread(&init[i], sizeof(unsigned), 1, fp); - rc = rc; - } - fclose(fp); - } - - /* Initialize PRNG state. */ - s = InitWELLRNG1024a(init); - (void)pthread_setspecific(tls_prng_key, s); - } - - return WELLRNG1024a(s); -} - -void tls_seed_set(unsigned init[WELL1024_WIDTH]) -{ - /* Initialize new PRNG state if not exists. */ - rngstate_t* s = pthread_getspecific(tls_prng_key); - if (!s) { - s = InitWELLRNG1024a(init); - (void)pthread_setspecific(tls_prng_key, s); - } else { - /* Reset PRNG state if exists. */ - memcpy(s->state, init, sizeof(unsigned) * WELL1024_WIDTH); - s->i = 0; - } -} diff --git a/src/common/WELL1024a.h b/src/common/WELL1024a.h deleted file mode 100644 index 04bf1a1..0000000 --- a/src/common/WELL1024a.h +++ /dev/null @@ -1,32 +0,0 @@ -/* ***************************************************************************** */ -/* Copyright: Francois Panneton and Pierre L'Ecuyer, University of Montreal */ -/* Makoto Matsumoto, Hiroshima University */ -/* Notice: This code can be used freely for personal, academic, */ -/* or non-commercial purposes. For commercial purposes, */ -/* please contact P. L'Ecuyer at: lecuyer@iro.UMontreal.ca */ -/* ***************************************************************************** */ - -#define WELL1024_WIDTH 32 /* 128 bytes */ - -typedef struct { - unsigned i; - unsigned state[WELL1024_WIDTH]; -} rngstate_t; - -rngstate_t* InitWELLRNG1024a (unsigned *init); -double WELLRNG1024a (rngstate_t* s); - -/*! - * \brief Get pseudorandom number from PRNG initialized in thread-local storage. - * - * No need for initialization, TLS will take care of it. - * - * \retval Pseudorandom number. - */ -double tls_rand(); - -/*! - * \brief Set PRNG seed in thread-local storage to requested value. - * - */ -void tls_seed_set(unsigned init[WELL1024_WIDTH]); diff --git a/src/common/dSFMT-params.h b/src/common/dSFMT-params.h new file mode 100644 index 0000000..c779d8a --- /dev/null +++ b/src/common/dSFMT-params.h @@ -0,0 +1,89 @@ +#include <config.h> + +#ifndef DSFMT_PARAMS_H +#define DSFMT_PARAMS_H + +#include "dSFMT.h" + +/*---------------------- + the parameters of DSFMT + following definitions are in dSFMT-paramsXXXX.h file. + ----------------------*/ +/** the pick up position of the array. +#define DSFMT_POS1 122 +*/ + +/** the parameter of shift left as four 32-bit registers. +#define DSFMT_SL1 18 + */ + +/** the parameter of shift right as four 32-bit registers. +#define DSFMT_SR1 12 +*/ + +/** A bitmask, used in the recursion. These parameters are introduced + * to break symmetry of SIMD. +#define DSFMT_MSK1 (uint64_t)0xdfffffefULL +#define DSFMT_MSK2 (uint64_t)0xddfecb7fULL +*/ + +/** These definitions are part of a 128-bit period certification vector. +#define DSFMT_PCV1 UINT64_C(0x00000001) +#define DSFMT_PCV2 UINT64_C(0x00000000) +*/ + +#define DSFMT_LOW_MASK UINT64_C(0x000FFFFFFFFFFFFF) +#define DSFMT_HIGH_CONST UINT64_C(0x3FF0000000000000) +#define DSFMT_SR 12 + +/* for sse2 */ +#if defined(HAVE_SSE2) + #define SSE2_SHUFF 0x1b +#elif defined(HAVE_ALTIVEC) + #if defined(__APPLE__) /* For OSX */ + #define ALTI_SR (vector unsigned char)(4) + #define ALTI_SR_PERM \ + (vector unsigned char)(15,0,1,2,3,4,5,6,15,8,9,10,11,12,13,14) + #define ALTI_SR_MSK \ + (vector unsigned int)(0x000fffffU,0xffffffffU,0x000fffffU,0xffffffffU) + #define ALTI_PERM \ + (vector unsigned char)(12,13,14,15,8,9,10,11,4,5,6,7,0,1,2,3) + #else + #define ALTI_SR {4} + #define ALTI_SR_PERM {15,0,1,2,3,4,5,6,15,8,9,10,11,12,13,14} + #define ALTI_SR_MSK {0x000fffffU,0xffffffffU,0x000fffffU,0xffffffffU} + #define ALTI_PERM {12,13,14,15,8,9,10,11,4,5,6,7,0,1,2,3} + #endif +#endif + +#if DSFMT_MEXP == 521 + #include "dSFMT-params521.h" +#elif DSFMT_MEXP == 1279 + #include "dSFMT-params1279.h" +#elif DSFMT_MEXP == 2203 + #include "dSFMT-params2203.h" +#elif DSFMT_MEXP == 4253 + #include "dSFMT-params4253.h" +#elif DSFMT_MEXP == 11213 + #include "dSFMT-params11213.h" +#elif DSFMT_MEXP == 19937 + #include "dSFMT-params19937.h" +#elif DSFMT_MEXP == 44497 + #include "dSFMT-params44497.h" +#elif DSFMT_MEXP == 86243 + #include "dSFMT-params86243.h" +#elif DSFMT_MEXP == 132049 + #include "dSFMT-params132049.h" +#elif DSFMT_MEXP == 216091 + #include "dSFMT-params216091.h" +#else +#ifdef __GNUC__ + #error "DSFMT_MEXP is not valid." + #undef DSFMT_MEXP +#else + #undef DSFMT_MEXP +#endif + +#endif + +#endif /* DSFMT_PARAMS_H */ diff --git a/src/common/dSFMT-params521.h b/src/common/dSFMT-params521.h new file mode 100644 index 0000000..f771dc1 --- /dev/null +++ b/src/common/dSFMT-params521.h @@ -0,0 +1,40 @@ +#ifndef DSFMT_PARAMS521_H +#define DSFMT_PARAMS521_H + +/* #define DSFMT_N 4 */ +/* #define DSFMT_MAXDEGREE 544 */ +#define DSFMT_POS1 3 +#define DSFMT_SL1 25 +#define DSFMT_MSK1 UINT64_C(0x000fbfefff77efff) +#define DSFMT_MSK2 UINT64_C(0x000ffeebfbdfbfdf) +#define DSFMT_MSK32_1 0x000fbfefU +#define DSFMT_MSK32_2 0xff77efffU +#define DSFMT_MSK32_3 0x000ffeebU +#define DSFMT_MSK32_4 0xfbdfbfdfU +#define DSFMT_FIX1 UINT64_C(0xcfb393d661638469) +#define DSFMT_FIX2 UINT64_C(0xc166867883ae2adb) +#define DSFMT_PCV1 UINT64_C(0xccaa588000000000) +#define DSFMT_PCV2 UINT64_C(0x0000000000000001) +#define DSFMT_IDSTR "dSFMT2-521:3-25:fbfefff77efff-ffeebfbdfbfdf" + + +/* PARAMETERS FOR ALTIVEC */ +#if defined(__APPLE__) /* For OSX */ + #define ALTI_SL1 (vector unsigned int)(1, 1, 1, 1) + #define ALTI_SL1_PERM \ + (vector unsigned char)(3,4,5,6,7,29,29,29,11,12,13,14,15,0,1,2) + #define ALTI_SL1_MSK \ + (vector unsigned int)(0xffffffffU,0xfe000000U,0xffffffffU,0xfe000000U) + #define ALTI_MSK (vector unsigned int)(DSFMT_MSK32_1, \ + DSFMT_MSK32_2, DSFMT_MSK32_3, DSFMT_MSK32_4) +#else /* For OTHER OSs(Linux?) */ + #define ALTI_SL1 {1, 1, 1, 1} + #define ALTI_SL1_PERM \ + {3,4,5,6,7,29,29,29,11,12,13,14,15,0,1,2} + #define ALTI_SL1_MSK \ + {0xffffffffU,0xfe000000U,0xffffffffU,0xfe000000U} + #define ALTI_MSK \ + {DSFMT_MSK32_1, DSFMT_MSK32_2, DSFMT_MSK32_3, DSFMT_MSK32_4} +#endif + +#endif /* DSFMT_PARAMS521_H */ diff --git a/src/common/dSFMT.c b/src/common/dSFMT.c new file mode 100644 index 0000000..090bb80 --- /dev/null +++ b/src/common/dSFMT.c @@ -0,0 +1,734 @@ +/** + * @file dSFMT.c + * @brief double precision SIMD-oriented Fast Mersenne Twister (dSFMT) + * based on IEEE 754 format. + * + * @author Mutsuo Saito (Hiroshima University) + * @author Makoto Matsumoto (Hiroshima University) + * + * Copyright (C) 2007,2008 Mutsuo Saito, Makoto Matsumoto and Hiroshima + * University. All rights reserved. + * + * The new BSD License is applied to this software, see LICENSE.txt + */ +#include <stdio.h> +#include <string.h> +#include <stdlib.h> +#include "dSFMT-params.h" + +/** dsfmt internal state vector */ +dsfmt_t dsfmt_global_data; +/** dsfmt mexp for check */ +static const int dsfmt_mexp = DSFMT_MEXP; + +/*---------------- + STATIC FUNCTIONS + ----------------*/ +inline static uint32_t ini_func1(uint32_t x); +inline static uint32_t ini_func2(uint32_t x); +inline static void gen_rand_array_c1o2(dsfmt_t *dsfmt, w128_t *array, + int size); +inline static void gen_rand_array_c0o1(dsfmt_t *dsfmt, w128_t *array, + int size); +inline static void gen_rand_array_o0c1(dsfmt_t *dsfmt, w128_t *array, + int size); +inline static void gen_rand_array_o0o1(dsfmt_t *dsfmt, w128_t *array, + int size); +inline static int idxof(int i); +static void initial_mask(dsfmt_t *dsfmt); +static void period_certification(dsfmt_t *dsfmt); + +#if defined(HAVE_SSE2) +# include <emmintrin.h> +/** mask data for sse2 */ +static __m128i sse2_param_mask; +/** 1 in 64bit for sse2 */ +static __m128i sse2_int_one; +/** 2.0 double for sse2 */ +static __m128d sse2_double_two; +/** -1.0 double for sse2 */ +static __m128d sse2_double_m_one; + +static void setup_const(void); +#endif + +/** + * This function simulate a 32-bit array index overlapped to 64-bit + * array of LITTLE ENDIAN in BIG ENDIAN machine. + */ +#if defined(DSFMT_BIG_ENDIAN) +inline static int idxof(int i) { + return i ^ 1; +} +#else +inline static int idxof(int i) { + return i; +} +#endif + +/** + * This function represents the recursion formula. + * @param r output + * @param a a 128-bit part of the internal state array + * @param b a 128-bit part of the internal state array + * @param lung a 128-bit part of the internal state array + */ +#if defined(HAVE_ALTIVEC) +inline static void do_recursion(w128_t *r, w128_t *a, w128_t * b, + w128_t *lung) { + const vector unsigned char sl1 = ALTI_SL1; + const vector unsigned char sl1_perm = ALTI_SL1_PERM; + const vector unsigned int sl1_msk = ALTI_SL1_MSK; + const vector unsigned char sr1 = ALTI_SR; + const vector unsigned char sr1_perm = ALTI_SR_PERM; + const vector unsigned int sr1_msk = ALTI_SR_MSK; + const vector unsigned char perm = ALTI_PERM; + const vector unsigned int msk1 = ALTI_MSK; + vector unsigned int w, x, y, z; + + z = a->s; + w = lung->s; + x = vec_perm(w, (vector unsigned int)perm, perm); + y = vec_perm(z, sl1_perm, sl1_perm); + y = vec_sll(y, sl1); + y = vec_and(y, sl1_msk); + w = vec_xor(x, b->s); + w = vec_xor(w, y); + x = vec_perm(w, (vector unsigned int)sr1_perm, sr1_perm); + x = vec_srl(x, sr1); + x = vec_and(x, sr1_msk); + y = vec_and(w, msk1); + z = vec_xor(z, y); + r->s = vec_xor(z, x); + lung->s = w; +} +#elif defined(HAVE_SSE2) +/** + * This function setup some constant variables for SSE2. + */ +static void setup_const(void) { + static int first = 1; + if (!first) { + return; + } + sse2_param_mask = _mm_set_epi32(DSFMT_MSK32_3, DSFMT_MSK32_4, + DSFMT_MSK32_1, DSFMT_MSK32_2); + sse2_int_one = _mm_set_epi32(0, 1, 0, 1); + sse2_double_two = _mm_set_pd(2.0, 2.0); + sse2_double_m_one = _mm_set_pd(-1.0, -1.0); + first = 0; +} + +/** + * This function represents the recursion formula. + * @param r output 128-bit + * @param a a 128-bit part of the internal state array + * @param b a 128-bit part of the internal state array + * @param d a 128-bit part of the internal state array (I/O) + */ +inline static void do_recursion(w128_t *r, w128_t *a, w128_t *b, w128_t *u) { + __m128i v, w, x, y, z; + + x = a->si; + z = _mm_slli_epi64(x, DSFMT_SL1); + y = _mm_shuffle_epi32(u->si, SSE2_SHUFF); + z = _mm_xor_si128(z, b->si); + y = _mm_xor_si128(y, z); + + v = _mm_srli_epi64(y, DSFMT_SR); + w = _mm_and_si128(y, sse2_param_mask); + v = _mm_xor_si128(v, x); + v = _mm_xor_si128(v, w); + r->si = v; + u->si = y; +} +#else /* standard C */ +/** + * This function represents the recursion formula. + * @param r output 128-bit + * @param a a 128-bit part of the internal state array + * @param b a 128-bit part of the internal state array + * @param lung a 128-bit part of the internal state array (I/O) + */ +inline static void do_recursion(w128_t *r, w128_t *a, w128_t * b, + w128_t *lung) { + uint64_t t0, t1, L0, L1; + + t0 = a->u[0]; + t1 = a->u[1]; + L0 = lung->u[0]; + L1 = lung->u[1]; + lung->u[0] = (t0 << DSFMT_SL1) ^ (L1 >> 32) ^ (L1 << 32) ^ b->u[0]; + lung->u[1] = (t1 << DSFMT_SL1) ^ (L0 >> 32) ^ (L0 << 32) ^ b->u[1]; + r->u[0] = (lung->u[0] >> DSFMT_SR) ^ (lung->u[0] & DSFMT_MSK1) ^ t0; + r->u[1] = (lung->u[1] >> DSFMT_SR) ^ (lung->u[1] & DSFMT_MSK2) ^ t1; +} +#endif + +#if defined(HAVE_SSE2) +/** + * This function converts the double precision floating point numbers which + * distribute uniformly in the range [1, 2) to those which distribute uniformly + * in the range [0, 1). + * @param w 128bit stracture of double precision floating point numbers (I/O) + */ +inline static void convert_c0o1(w128_t *w) { + w->sd = _mm_add_pd(w->sd, sse2_double_m_one); +} + +/** + * This function converts the double precision floating point numbers which + * distribute uniformly in the range [1, 2) to those which distribute uniformly + * in the range (0, 1]. + * @param w 128bit stracture of double precision floating point numbers (I/O) + */ +inline static void convert_o0c1(w128_t *w) { + w->sd = _mm_sub_pd(sse2_double_two, w->sd); +} + +/** + * This function converts the double precision floating point numbers which + * distribute uniformly in the range [1, 2) to those which distribute uniformly + * in the range (0, 1). + * @param w 128bit stracture of double precision floating point numbers (I/O) + */ +inline static void convert_o0o1(w128_t *w) { + w->si = _mm_or_si128(w->si, sse2_int_one); + w->sd = _mm_add_pd(w->sd, sse2_double_m_one); +} +#else /* standard C and altivec */ +/** + * This function converts the double precision floating point numbers which + * distribute uniformly in the range [1, 2) to those which distribute uniformly + * in the range [0, 1). + * @param w 128bit stracture of double precision floating point numbers (I/O) + */ +inline static void convert_c0o1(w128_t *w) { + w->d[0] -= 1.0; + w->d[1] -= 1.0; +} + +/** + * This function converts the double precision floating point numbers which + * distribute uniformly in the range [1, 2) to those which distribute uniformly + * in the range (0, 1]. + * @param w 128bit stracture of double precision floating point numbers (I/O) + */ +inline static void convert_o0c1(w128_t *w) { + w->d[0] = 2.0 - w->d[0]; + w->d[1] = 2.0 - w->d[1]; +} + +/** + * This function converts the double precision floating point numbers which + * distribute uniformly in the range [1, 2) to those which distribute uniformly + * in the range (0, 1). + * @param w 128bit stracture of double precision floating point numbers (I/O) + */ +inline static void convert_o0o1(w128_t *w) { + w->u[0] |= 1; + w->u[1] |= 1; + w->d[0] -= 1.0; + w->d[1] -= 1.0; +} +#endif + +/** + * This function fills the user-specified array with double precision + * floating point pseudorandom numbers of the IEEE 754 format. + * @param dsfmt dsfmt state vector. + * @param array an 128-bit array to be filled by pseudorandom numbers. + * @param size number of 128-bit pseudorandom numbers to be generated. + */ +inline static void gen_rand_array_c1o2(dsfmt_t *dsfmt, w128_t *array, + int size) { + int i, j; + w128_t lung; + + lung = dsfmt->status[DSFMT_N]; + do_recursion(&array[0], &dsfmt->status[0], &dsfmt->status[DSFMT_POS1], + &lung); + for (i = 1; i < DSFMT_N - DSFMT_POS1; i++) { + do_recursion(&array[i], &dsfmt->status[i], + &dsfmt->status[i + DSFMT_POS1], &lung); + } + for (; i < DSFMT_N; i++) { + do_recursion(&array[i], &dsfmt->status[i], + &array[i + DSFMT_POS1 - DSFMT_N], &lung); + } + for (; i < size - DSFMT_N; i++) { + do_recursion(&array[i], &array[i - DSFMT_N], + &array[i + DSFMT_POS1 - DSFMT_N], &lung); + } + for (j = 0; j < 2 * DSFMT_N - size; j++) { + dsfmt->status[j] = array[j + size - DSFMT_N]; + } + for (; i < size; i++, j++) { + do_recursion(&array[i], &array[i - DSFMT_N], + &array[i + DSFMT_POS1 - DSFMT_N], &lung); + dsfmt->status[j] = array[i]; + } + dsfmt->status[DSFMT_N] = lung; +} + +/** + * This function fills the user-specified array with double precision + * floating point pseudorandom numbers of the IEEE 754 format. + * @param dsfmt dsfmt state vector. + * @param array an 128-bit array to be filled by pseudorandom numbers. + * @param size number of 128-bit pseudorandom numbers to be generated. + */ +inline static void gen_rand_array_c0o1(dsfmt_t *dsfmt, w128_t *array, + int size) { + int i, j; + w128_t lung; + + lung = dsfmt->status[DSFMT_N]; + do_recursion(&array[0], &dsfmt->status[0], &dsfmt->status[DSFMT_POS1], + &lung); + for (i = 1; i < DSFMT_N - DSFMT_POS1; i++) { + do_recursion(&array[i], &dsfmt->status[i], + &dsfmt->status[i + DSFMT_POS1], &lung); + } + for (; i < DSFMT_N; i++) { + do_recursion(&array[i], &dsfmt->status[i], + &array[i + DSFMT_POS1 - DSFMT_N], &lung); + } + for (; i < size - DSFMT_N; i++) { + do_recursion(&array[i], &array[i - DSFMT_N], + &array[i + DSFMT_POS1 - DSFMT_N], &lung); + convert_c0o1(&array[i - DSFMT_N]); + } + for (j = 0; j < 2 * DSFMT_N - size; j++) { + dsfmt->status[j] = array[j + size - DSFMT_N]; + } + for (; i < size; i++, j++) { + do_recursion(&array[i], &array[i - DSFMT_N], + &array[i + DSFMT_POS1 - DSFMT_N], &lung); + dsfmt->status[j] = array[i]; + convert_c0o1(&array[i - DSFMT_N]); + } + for (i = size - DSFMT_N; i < size; i++) { + convert_c0o1(&array[i]); + } + dsfmt->status[DSFMT_N] = lung; +} + +/** + * This function fills the user-specified array with double precision + * floating point pseudorandom numbers of the IEEE 754 format. + * @param dsfmt dsfmt state vector. + * @param array an 128-bit array to be filled by pseudorandom numbers. + * @param size number of 128-bit pseudorandom numbers to be generated. + */ +inline static void gen_rand_array_o0o1(dsfmt_t *dsfmt, w128_t *array, + int size) { + int i, j; + w128_t lung; + + lung = dsfmt->status[DSFMT_N]; + do_recursion(&array[0], &dsfmt->status[0], &dsfmt->status[DSFMT_POS1], + &lung); + for (i = 1; i < DSFMT_N - DSFMT_POS1; i++) { + do_recursion(&array[i], &dsfmt->status[i], + &dsfmt->status[i + DSFMT_POS1], &lung); + } + for (; i < DSFMT_N; i++) { + do_recursion(&array[i], &dsfmt->status[i], + &array[i + DSFMT_POS1 - DSFMT_N], &lung); + } + for (; i < size - DSFMT_N; i++) { + do_recursion(&array[i], &array[i - DSFMT_N], + &array[i + DSFMT_POS1 - DSFMT_N], &lung); + convert_o0o1(&array[i - DSFMT_N]); + } + for (j = 0; j < 2 * DSFMT_N - size; j++) { + dsfmt->status[j] = array[j + size - DSFMT_N]; + } + for (; i < size; i++, j++) { + do_recursion(&array[i], &array[i - DSFMT_N], + &array[i + DSFMT_POS1 - DSFMT_N], &lung); + dsfmt->status[j] = array[i]; + convert_o0o1(&array[i - DSFMT_N]); + } + for (i = size - DSFMT_N; i < size; i++) { + convert_o0o1(&array[i]); + } + dsfmt->status[DSFMT_N] = lung; +} + +/** + * This function fills the user-specified array with double precision + * floating point pseudorandom numbers of the IEEE 754 format. + * @param dsfmt dsfmt state vector. + * @param array an 128-bit array to be filled by pseudorandom numbers. + * @param size number of 128-bit pseudorandom numbers to be generated. + */ +inline static void gen_rand_array_o0c1(dsfmt_t *dsfmt, w128_t *array, + int size) { + int i, j; + w128_t lung; + + lung = dsfmt->status[DSFMT_N]; + do_recursion(&array[0], &dsfmt->status[0], &dsfmt->status[DSFMT_POS1], + &lung); + for (i = 1; i < DSFMT_N - DSFMT_POS1; i++) { + do_recursion(&array[i], &dsfmt->status[i], + &dsfmt->status[i + DSFMT_POS1], &lung); + } + for (; i < DSFMT_N; i++) { + do_recursion(&array[i], &dsfmt->status[i], + &array[i + DSFMT_POS1 - DSFMT_N], &lung); + } + for (; i < size - DSFMT_N; i++) { + do_recursion(&array[i], &array[i - DSFMT_N], + &array[i + DSFMT_POS1 - DSFMT_N], &lung); + convert_o0c1(&array[i - DSFMT_N]); + } + for (j = 0; j < 2 * DSFMT_N - size; j++) { + dsfmt->status[j] = array[j + size - DSFMT_N]; + } + for (; i < size; i++, j++) { + do_recursion(&array[i], &array[i - DSFMT_N], + &array[i + DSFMT_POS1 - DSFMT_N], &lung); + dsfmt->status[j] = array[i]; + convert_o0c1(&array[i - DSFMT_N]); + } + for (i = size - DSFMT_N; i < size; i++) { + convert_o0c1(&array[i]); + } + dsfmt->status[DSFMT_N] = lung; +} + +/** + * This function represents a function used in the initialization + * by init_by_array + * @param x 32-bit integer + * @return 32-bit integer + */ +static uint32_t ini_func1(uint32_t x) { + return (x ^ (x >> 27)) * (uint32_t)1664525UL; +} + +/** + * This function represents a function used in the initialization + * by init_by_array + * @param x 32-bit integer + * @return 32-bit integer + */ +static uint32_t ini_func2(uint32_t x) { + return (x ^ (x >> 27)) * (uint32_t)1566083941UL; +} + +/** + * This function initializes the internal state array to fit the IEEE + * 754 format. + * @param dsfmt dsfmt state vector. + */ +static void initial_mask(dsfmt_t *dsfmt) { + int i; + uint64_t *psfmt; + + psfmt = &dsfmt->status[0].u[0]; + for (i = 0; i < DSFMT_N * 2; i++) { + psfmt[i] = (psfmt[i] & DSFMT_LOW_MASK) | DSFMT_HIGH_CONST; + } +} + +/** + * This function certificate the period of 2^{SFMT_MEXP}-1. + * @param dsfmt dsfmt state vector. + */ +static void period_certification(dsfmt_t *dsfmt) { + uint64_t pcv[2] = {DSFMT_PCV1, DSFMT_PCV2}; + uint64_t tmp[2]; + uint64_t inner; + int i; +#if (DSFMT_PCV2 & 1) != 1 + int j; + uint64_t work; +#endif + + tmp[0] = (dsfmt->status[DSFMT_N].u[0] ^ DSFMT_FIX1); + tmp[1] = (dsfmt->status[DSFMT_N].u[1] ^ DSFMT_FIX2); + + inner = tmp[0] & pcv[0]; + inner ^= tmp[1] & pcv[1]; + for (i = 32; i > 0; i >>= 1) { + inner ^= inner >> i; + } + inner &= 1; + /* check OK */ + if (inner == 1) { + return; + } + /* check NG, and modification */ +#if (DSFMT_PCV2 & 1) == 1 + dsfmt->status[DSFMT_N].u[1] ^= 1; +#else + for (i = 1; i >= 0; i--) { + work = 1; + for (j = 0; j < 64; j++) { + if ((work & pcv[i]) != 0) { + dsfmt->status[DSFMT_N].u[i] ^= work; + return; + } + work = work << 1; + } + } +#endif + return; +} + +/*---------------- + PUBLIC FUNCTIONS + ----------------*/ +/** + * This function returns the identification string. The string shows + * the Mersenne exponent, and all parameters of this generator. + * @return id string. + */ +const char *dsfmt_get_idstring(void) { + return DSFMT_IDSTR; +} + +/** + * This function returns the minimum size of array used for \b + * fill_array functions. + * @return minimum size of array used for fill_array functions. + */ +int dsfmt_get_min_array_size(void) { + return DSFMT_N64; +} + +/** + * This function fills the internal state array with double precision + * floating point pseudorandom numbers of the IEEE 754 format. + * @param dsfmt dsfmt state vector. + */ +void dsfmt_gen_rand_all(dsfmt_t *dsfmt) { + int i; + w128_t lung; + + lung = dsfmt->status[DSFMT_N]; + do_recursion(&dsfmt->status[0], &dsfmt->status[0], + &dsfmt->status[DSFMT_POS1], &lung); + for (i = 1; i < DSFMT_N - DSFMT_POS1; i++) { + do_recursion(&dsfmt->status[i], &dsfmt->status[i], + &dsfmt->status[i + DSFMT_POS1], &lung); + } + for (; i < DSFMT_N; i++) { + do_recursion(&dsfmt->status[i], &dsfmt->status[i], + &dsfmt->status[i + DSFMT_POS1 - DSFMT_N], &lung); + } + dsfmt->status[DSFMT_N] = lung; +} + +/** + * This function generates double precision floating point + * pseudorandom numbers which distribute in the range [1, 2) to the + * specified array[] by one call. The number of pseudorandom numbers + * is specified by the argument \b size, which must be at least (SFMT_MEXP + * / 128) * 2 and a multiple of two. The function + * get_min_array_size() returns this minimum size. The generation by + * this function is much faster than the following fill_array_xxx functions. + * + * For initialization, init_gen_rand() or init_by_array() must be called + * before the first call of this function. This function can not be + * used after calling genrand_xxx functions, without initialization. + * + * @param dsfmt dsfmt state vector. + * @param array an array where pseudorandom numbers are filled + * by this function. The pointer to the array must be "aligned" + * (namely, must be a multiple of 16) in the SIMD version, since it + * refers to the address of a 128-bit integer. In the standard C + * version, the pointer is arbitrary. + * + * @param size the number of 64-bit pseudorandom integers to be + * generated. size must be a multiple of 2, and greater than or equal + * to (SFMT_MEXP / 128) * 2. + * + * @note \b memalign or \b posix_memalign is available to get aligned + * memory. Mac OSX doesn't have these functions, but \b malloc of OSX + * returns the pointer to the aligned memory block. + */ +void dsfmt_fill_array_close1_open2(dsfmt_t *dsfmt, double array[], int size) { + assert(size % 2 == 0); + assert(size >= DSFMT_N64); + gen_rand_array_c1o2(dsfmt, (w128_t *)array, size / 2); +} + +/** + * This function generates double precision floating point + * pseudorandom numbers which distribute in the range (0, 1] to the + * specified array[] by one call. This function is the same as + * fill_array_close1_open2() except the distribution range. + * + * @param dsfmt dsfmt state vector. + * @param array an array where pseudorandom numbers are filled + * by this function. + * @param size the number of pseudorandom numbers to be generated. + * see also \sa fill_array_close1_open2() + */ +void dsfmt_fill_array_open_close(dsfmt_t *dsfmt, double array[], int size) { + assert(size % 2 == 0); + assert(size >= DSFMT_N64); + gen_rand_array_o0c1(dsfmt, (w128_t *)array, size / 2); +} + +/** + * This function generates double precision floating point + * pseudorandom numbers which distribute in the range [0, 1) to the + * specified array[] by one call. This function is the same as + * fill_array_close1_open2() except the distribution range. + * + * @param array an array where pseudorandom numbers are filled + * by this function. + * @param dsfmt dsfmt state vector. + * @param size the number of pseudorandom numbers to be generated. + * see also \sa fill_array_close1_open2() + */ +void dsfmt_fill_array_close_open(dsfmt_t *dsfmt, double array[], int size) { + assert(size % 2 == 0); + assert(size >= DSFMT_N64); + gen_rand_array_c0o1(dsfmt, (w128_t *)array, size / 2); +} + +/** + * This function generates double precision floating point + * pseudorandom numbers which distribute in the range (0, 1) to the + * specified array[] by one call. This function is the same as + * fill_array_close1_open2() except the distribution range. + * + * @param dsfmt dsfmt state vector. + * @param array an array where pseudorandom numbers are filled + * by this function. + * @param size the number of pseudorandom numbers to be generated. + * see also \sa fill_array_close1_open2() + */ +void dsfmt_fill_array_open_open(dsfmt_t *dsfmt, double array[], int size) { + assert(size % 2 == 0); + assert(size >= DSFMT_N64); + gen_rand_array_o0o1(dsfmt, (w128_t *)array, size / 2); +} + +#if defined(__INTEL_COMPILER) +# pragma warning(disable:981) +#endif +/** + * This function initializes the internal state array with a 32-bit + * integer seed. + * @param dsfmt dsfmt state vector. + * @param seed a 32-bit integer used as the seed. + * @param mexp caller's mersenne expornent + */ +void dsfmt_chk_init_gen_rand(dsfmt_t *dsfmt, uint32_t seed, int mexp) { + int i; + uint32_t *psfmt; + + /* make sure caller program is compiled with the same MEXP */ + if (mexp != dsfmt_mexp) { + fprintf(stderr, "DSFMT_MEXP doesn't match with dSFMT.c\n"); + exit(1); + } + psfmt = &dsfmt->status[0].u32[0]; + psfmt[idxof(0)] = seed; + for (i = 1; i < (DSFMT_N + 1) * 4; i++) { + psfmt[idxof(i)] = 1812433253UL + * (psfmt[idxof(i - 1)] ^ (psfmt[idxof(i - 1)] >> 30)) + i; + } + initial_mask(dsfmt); + period_certification(dsfmt); + dsfmt->idx = DSFMT_N64; +#if defined(HAVE_SSE2) + setup_const(); +#endif +} + +/** + * This function initializes the internal state array, + * with an array of 32-bit integers used as the seeds + * @param dsfmt dsfmt state vector. + * @param init_key the array of 32-bit integers, used as a seed. + * @param key_length the length of init_key. + * @param mexp caller's mersenne expornent + */ +void dsfmt_chk_init_by_array(dsfmt_t *dsfmt, uint32_t init_key[], + int key_length, int mexp) { + int i, j, count; + uint32_t r; + uint32_t *psfmt32; + int lag; + int mid; + int size = (DSFMT_N + 1) * 4; /* pulmonary */ + + /* make sure caller program is compiled with the same MEXP */ + if (mexp != dsfmt_mexp) { + fprintf(stderr, "DSFMT_MEXP doesn't match with dSFMT.c\n"); + exit(1); + } + if (size >= 623) { + lag = 11; + } else if (size >= 68) { + lag = 7; + } else if (size >= 39) { + lag = 5; + } else { + lag = 3; + } + mid = (size - lag) / 2; + + psfmt32 = &dsfmt->status[0].u32[0]; + memset(dsfmt->status, 0x8b, sizeof(dsfmt->status)); + if (key_length + 1 > size) { + count = key_length + 1; + } else { + count = size; + } + r = ini_func1(psfmt32[idxof(0)] ^ psfmt32[idxof(mid % size)] + ^ psfmt32[idxof((size - 1) % size)]); + psfmt32[idxof(mid % size)] += r; + r += key_length; + psfmt32[idxof((mid + lag) % size)] += r; + psfmt32[idxof(0)] = r; + count--; + for (i = 1, j = 0; (j < count) && (j < key_length); j++) { + r = ini_func1(psfmt32[idxof(i)] + ^ psfmt32[idxof((i + mid) % size)] + ^ psfmt32[idxof((i + size - 1) % size)]); + psfmt32[idxof((i + mid) % size)] += r; + r += init_key[j] + i; + psfmt32[idxof((i + mid + lag) % size)] += r; + psfmt32[idxof(i)] = r; + i = (i + 1) % size; + } + for (; j < count; j++) { + r = ini_func1(psfmt32[idxof(i)] + ^ psfmt32[idxof((i + mid) % size)] + ^ psfmt32[idxof((i + size - 1) % size)]); + psfmt32[idxof((i + mid) % size)] += r; + r += i; + psfmt32[idxof((i + mid + lag) % size)] += r; + psfmt32[idxof(i)] = r; + i = (i + 1) % size; + } + for (j = 0; j < size; j++) { + r = ini_func2(psfmt32[idxof(i)] + + psfmt32[idxof((i + mid) % size)] + + psfmt32[idxof((i + size - 1) % size)]); + psfmt32[idxof((i + mid) % size)] ^= r; + r -= i; + psfmt32[idxof((i + mid + lag) % size)] ^= r; + psfmt32[idxof(i)] = r; + i = (i + 1) % size; + } + initial_mask(dsfmt); + period_certification(dsfmt); + dsfmt->idx = DSFMT_N64; +#if defined(HAVE_SSE2) + setup_const(); +#endif +} +#if defined(__INTEL_COMPILER) +# pragma warning(default:981) +#endif diff --git a/src/common/dSFMT.h b/src/common/dSFMT.h new file mode 100644 index 0000000..f1aa9bd --- /dev/null +++ b/src/common/dSFMT.h @@ -0,0 +1,625 @@ +/** + * @file dSFMT.h + * + * @brief double precision SIMD oriented Fast Mersenne Twister(dSFMT) + * pseudorandom number generator based on IEEE 754 format. + * + * @author Mutsuo Saito (Hiroshima University) + * @author Makoto Matsumoto (Hiroshima University) + * + * Copyright (C) 2007, 2008 Mutsuo Saito, Makoto Matsumoto and + * Hiroshima University. All rights reserved. + * + * The new BSD License is applied to this software. + * see LICENSE.txt + * + * @note We assume that your system has inttypes.h. If your system + * doesn't have inttypes.h, you have to typedef uint32_t and uint64_t, + * and you have to define PRIu64 and PRIx64 in this file as follows: + * @verbatim + typedef unsigned int uint32_t + typedef unsigned long long uint64_t + #define PRIu64 "llu" + #define PRIx64 "llx" +@endverbatim + * uint32_t must be exactly 32-bit unsigned integer type (no more, no + * less), and uint64_t must be exactly 64-bit unsigned integer type. + * PRIu64 and PRIx64 are used for printf function to print 64-bit + * unsigned int and 64-bit unsigned int in hexadecimal format. + */ + +#include <config.h> + +#ifndef DSFMT_H +#define DSFMT_H + +#include <stdio.h> +#include <assert.h> + +#if !defined(DSFMT_MEXP) +#ifdef __GNUC__ + #warning "DSFMT_MEXP is not defined. I assume DSFMT_MEXP is 19937." +#endif + #define DSFMT_MEXP 19937 +#endif +/*----------------- + BASIC DEFINITIONS + -----------------*/ +/* Mersenne Exponent. The period of the sequence + * is a multiple of 2^DSFMT_MEXP-1. + * #define DSFMT_MEXP 19937 */ +/** DSFMT generator has an internal state array of 128-bit integers, + * and N is its size. */ +#define DSFMT_N ((DSFMT_MEXP - 128) / 104 + 1) +/** N32 is the size of internal state array when regarded as an array + * of 32-bit integers.*/ +#define DSFMT_N32 (DSFMT_N * 4) +/** N64 is the size of internal state array when regarded as an array + * of 64-bit integers.*/ +#define DSFMT_N64 (DSFMT_N * 2) + +#if !defined(DSFMT_BIG_ENDIAN) +# if defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) +# if __BYTE_ORDER == __BIG_ENDIAN +# define DSFMT_BIG_ENDIAN 1 +# endif +# elif defined(_BYTE_ORDER) && defined(_BIG_ENDIAN) +# if _BYTE_ORDER == _BIG_ENDIAN +# define DSFMT_BIG_ENDIAN 1 +# endif +# elif defined(__BYTE_ORDER__) && defined(__BIG_ENDIAN__) +# if __BYTE_ORDER__ == __BIG_ENDIAN__ +# define DSFMT_BIG_ENDIAN 1 +# endif +# elif defined(BYTE_ORDER) && defined(BIG_ENDIAN) +# if BYTE_ORDER == BIG_ENDIAN +# define DSFMT_BIG_ENDIAN 1 +# endif +# elif defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN) \ + || defined(__BIG_ENDIAN__) || defined(BIG_ENDIAN) +# define DSFMT_BIG_ENDIAN 1 +# endif +#endif + +#if defined(DSFMT_BIG_ENDIAN) && defined(__amd64) +# undef DSFMT_BIG_ENDIAN +#endif + +#if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) +# include <inttypes.h> +#elif defined(_MSC_VER) || defined(__BORLANDC__) +# if !defined(DSFMT_UINT32_DEFINED) && !defined(SFMT_UINT32_DEFINED) +typedef unsigned int uint32_t; +typedef unsigned __int64 uint64_t; +# define UINT64_C(v) (v ## ui64) +# define DSFMT_UINT32_DEFINED +# if !defined(inline) +# define inline __inline +# endif +# endif +#else +# include <inttypes.h> +# if !defined(inline) +# if defined(__GNUC__) +# define inline __inline__ +# else +# define inline +# endif +# endif +#endif + +#ifndef PRIu64 +# if defined(_MSC_VER) || defined(__BORLANDC__) +# define PRIu64 "I64u" +# define PRIx64 "I64x" +# else +# define PRIu64 "llu" +# define PRIx64 "llx" +# endif +#endif + +#ifndef UINT64_C +# define UINT64_C(v) (v ## ULL) +#endif + +/*------------------------------------------ + 128-bit SIMD like data type for standard C + ------------------------------------------*/ +#if defined(HAVE_ALTIVEC) +# if !defined(__APPLE__) +# include <altivec.h> +# endif +/** 128-bit data structure */ +union W128_T { + vector unsigned int s; + uint64_t u[2]; + uint32_t u32[4]; + double d[2]; +}; + +#elif defined(HAVE_SSE2) +# include <emmintrin.h> + +/** 128-bit data structure */ +union W128_T { + __m128i si; + __m128d sd; + uint64_t u[2]; + uint32_t u32[4]; + double d[2]; +}; +#else /* standard C */ +/** 128-bit data structure */ +union W128_T { + uint64_t u[2]; + uint32_t u32[4]; + double d[2]; +}; +#endif + +/** 128-bit data type */ +typedef union W128_T w128_t; + +/** the 128-bit internal state array */ +struct DSFMT_T { + w128_t status[DSFMT_N + 1]; + int idx; +}; +typedef struct DSFMT_T dsfmt_t; + +/** dsfmt internal state vector */ +extern dsfmt_t dsfmt_global_data; +/** dsfmt mexp for check */ +extern const int dsfmt_global_mexp; + +void dsfmt_gen_rand_all(dsfmt_t *dsfmt); +void dsfmt_fill_array_open_close(dsfmt_t *dsfmt, double array[], int size); +void dsfmt_fill_array_close_open(dsfmt_t *dsfmt, double array[], int size); +void dsfmt_fill_array_open_open(dsfmt_t *dsfmt, double array[], int size); +void dsfmt_fill_array_close1_open2(dsfmt_t *dsfmt, double array[], int size); +void dsfmt_chk_init_gen_rand(dsfmt_t *dsfmt, uint32_t seed, int mexp); +void dsfmt_chk_init_by_array(dsfmt_t *dsfmt, uint32_t init_key[], + int key_length, int mexp); +const char *dsfmt_get_idstring(void); +int dsfmt_get_min_array_size(void); + +#if defined(__GNUC__) +# define DSFMT_PRE_INLINE inline static +# define DSFMT_PST_INLINE __attribute__((always_inline)) +#elif defined(_MSC_VER) && _MSC_VER >= 1200 +# define DSFMT_PRE_INLINE __forceinline static +# define DSFMT_PST_INLINE +#else +# define DSFMT_PRE_INLINE inline static +# define DSFMT_PST_INLINE +#endif +DSFMT_PRE_INLINE uint32_t dsfmt_genrand_uint32(dsfmt_t *dsfmt) DSFMT_PST_INLINE; +DSFMT_PRE_INLINE double dsfmt_genrand_close1_open2(dsfmt_t *dsfmt) + DSFMT_PST_INLINE; +DSFMT_PRE_INLINE double dsfmt_genrand_close_open(dsfmt_t *dsfmt) + DSFMT_PST_INLINE; +DSFMT_PRE_INLINE double dsfmt_genrand_open_close(dsfmt_t *dsfmt) + DSFMT_PST_INLINE; +DSFMT_PRE_INLINE double dsfmt_genrand_open_open(dsfmt_t *dsfmt) + DSFMT_PST_INLINE; +DSFMT_PRE_INLINE uint32_t dsfmt_gv_genrand_uint32(void) DSFMT_PST_INLINE; +DSFMT_PRE_INLINE double dsfmt_gv_genrand_close1_open2(void) DSFMT_PST_INLINE; +DSFMT_PRE_INLINE double dsfmt_gv_genrand_close_open(void) DSFMT_PST_INLINE; +DSFMT_PRE_INLINE double dsfmt_gv_genrand_open_close(void) DSFMT_PST_INLINE; +DSFMT_PRE_INLINE double dsfmt_gv_genrand_open_open(void) DSFMT_PST_INLINE; +DSFMT_PRE_INLINE void dsfmt_gv_fill_array_open_close(double array[], int size) + DSFMT_PST_INLINE; +DSFMT_PRE_INLINE void dsfmt_gv_fill_array_close_open(double array[], int size) + DSFMT_PST_INLINE; +DSFMT_PRE_INLINE void dsfmt_gv_fill_array_open_open(double array[], int size) + DSFMT_PST_INLINE; +DSFMT_PRE_INLINE void dsfmt_gv_fill_array_close1_open2(double array[], int size) + DSFMT_PST_INLINE; +DSFMT_PRE_INLINE void dsfmt_gv_init_gen_rand(uint32_t seed) DSFMT_PST_INLINE; +DSFMT_PRE_INLINE void dsfmt_gv_init_by_array(uint32_t init_key[], + int key_length) DSFMT_PST_INLINE; +DSFMT_PRE_INLINE void dsfmt_init_gen_rand(dsfmt_t *dsfmt, uint32_t seed) + DSFMT_PST_INLINE; +DSFMT_PRE_INLINE void dsfmt_init_by_array(dsfmt_t *dsfmt, uint32_t init_key[], + int key_length) DSFMT_PST_INLINE; + +/** + * This function generates and returns unsigned 32-bit integer. + * This is slower than SFMT, only for convenience usage. + * dsfmt_init_gen_rand() or dsfmt_init_by_array() must be called + * before this function. + * @param dsfmt dsfmt internal state date + * @return double precision floating point pseudorandom number + */ +inline static uint32_t dsfmt_genrand_uint32(dsfmt_t *dsfmt) { + uint32_t r; + uint64_t *psfmt64 = &dsfmt->status[0].u[0]; + + if (dsfmt->idx >= DSFMT_N64) { + dsfmt_gen_rand_all(dsfmt); + dsfmt->idx = 0; + } + r = psfmt64[dsfmt->idx++] & 0xffffffffU; + return r; +} + +/** + * This function generates and returns double precision pseudorandom + * number which distributes uniformly in the range [1, 2). This is + * the primitive and faster than generating numbers in other ranges. + * dsfmt_init_gen_rand() or dsfmt_init_by_array() must be called + * before this function. + * @param dsfmt dsfmt internal state date + * @return double precision floating point pseudorandom number + */ +inline static double dsfmt_genrand_close1_open2(dsfmt_t *dsfmt) { + double r; + double *psfmt64 = &dsfmt->status[0].d[0]; + + if (dsfmt->idx >= DSFMT_N64) { + dsfmt_gen_rand_all(dsfmt); + dsfmt->idx = 0; + } + r = psfmt64[dsfmt->idx++]; + return r; +} + +/** + * This function generates and returns unsigned 32-bit integer. + * This is slower than SFMT, only for convenience usage. + * dsfmt_gv_init_gen_rand() or dsfmt_gv_init_by_array() must be called + * before this function. This function uses \b global variables. + * @return double precision floating point pseudorandom number + */ +inline static uint32_t dsfmt_gv_genrand_uint32(void) { + return dsfmt_genrand_uint32(&dsfmt_global_data); +} + +/** + * This function generates and returns double precision pseudorandom + * number which distributes uniformly in the range [1, 2). + * dsfmt_gv_init_gen_rand() or dsfmt_gv_init_by_array() must be called + * before this function. This function uses \b global variables. + * @return double precision floating point pseudorandom number + */ +inline static double dsfmt_gv_genrand_close1_open2(void) { + return dsfmt_genrand_close1_open2(&dsfmt_global_data); +} + +/** + * This function generates and returns double precision pseudorandom + * number which distributes uniformly in the range [0, 1). + * dsfmt_init_gen_rand() or dsfmt_init_by_array() must be called + * before this function. + * @param dsfmt dsfmt internal state date + * @return double precision floating point pseudorandom number + */ +inline static double dsfmt_genrand_close_open(dsfmt_t *dsfmt) { + return dsfmt_genrand_close1_open2(dsfmt) - 1.0; +} + +/** + * This function generates and returns double precision pseudorandom + * number which distributes uniformly in the range [0, 1). + * dsfmt_gv_init_gen_rand() or dsfmt_gv_init_by_array() must be called + * before this function. This function uses \b global variables. + * @return double precision floating point pseudorandom number + */ +inline static double dsfmt_gv_genrand_close_open(void) { + return dsfmt_gv_genrand_close1_open2() - 1.0; +} + +/** + * This function generates and returns double precision pseudorandom + * number which distributes uniformly in the range (0, 1]. + * dsfmt_init_gen_rand() or dsfmt_init_by_array() must be called + * before this function. + * @param dsfmt dsfmt internal state date + * @return double precision floating point pseudorandom number + */ +inline static double dsfmt_genrand_open_close(dsfmt_t *dsfmt) { + return 2.0 - dsfmt_genrand_close1_open2(dsfmt); +} + +/** + * This function generates and returns double precision pseudorandom + * number which distributes uniformly in the range (0, 1]. + * dsfmt_gv_init_gen_rand() or dsfmt_gv_init_by_array() must be called + * before this function. This function uses \b global variables. + * @return double precision floating point pseudorandom number + */ +inline static double dsfmt_gv_genrand_open_close(void) { + return 2.0 - dsfmt_gv_genrand_close1_open2(); +} + +/** + * This function generates and returns double precision pseudorandom + * number which distributes uniformly in the range (0, 1). + * dsfmt_init_gen_rand() or dsfmt_init_by_array() must be called + * before this function. + * @param dsfmt dsfmt internal state date + * @return double precision floating point pseudorandom number + */ +inline static double dsfmt_genrand_open_open(dsfmt_t *dsfmt) { + double *dsfmt64 = &dsfmt->status[0].d[0]; + union { + double d; + uint64_t u; + } r; + + if (dsfmt->idx >= DSFMT_N64) { + dsfmt_gen_rand_all(dsfmt); + dsfmt->idx = 0; + } + r.d = dsfmt64[dsfmt->idx++]; + r.u |= 1; + return r.d - 1.0; +} + +/** + * This function generates and returns double precision pseudorandom + * number which distributes uniformly in the range (0, 1). + * dsfmt_gv_init_gen_rand() or dsfmt_gv_init_by_array() must be called + * before this function. This function uses \b global variables. + * @return double precision floating point pseudorandom number + */ +inline static double dsfmt_gv_genrand_open_open(void) { + return dsfmt_genrand_open_open(&dsfmt_global_data); +} + +/** + * This function generates double precision floating point + * pseudorandom numbers which distribute in the range [1, 2) to the + * specified array[] by one call. This function is the same as + * dsfmt_fill_array_close1_open2() except that this function uses + * \b global variables. + * @param array an array where pseudorandom numbers are filled + * by this function. + * @param size the number of pseudorandom numbers to be generated. + * see also \sa dsfmt_fill_array_close1_open2() + */ +inline static void dsfmt_gv_fill_array_close1_open2(double array[], int size) { + dsfmt_fill_array_close1_open2(&dsfmt_global_data, array, size); +} + +/** + * This function generates double precision floating point + * pseudorandom numbers which distribute in the range (0, 1] to the + * specified array[] by one call. This function is the same as + * dsfmt_gv_fill_array_close1_open2() except the distribution range. + * This function uses \b global variables. + * @param array an array where pseudorandom numbers are filled + * by this function. + * @param size the number of pseudorandom numbers to be generated. + * see also \sa dsfmt_fill_array_close1_open2() and \sa + * dsfmt_gv_fill_array_close1_open2() + */ +inline static void dsfmt_gv_fill_array_open_close(double array[], int size) { + dsfmt_fill_array_open_close(&dsfmt_global_data, array, size); +} + +/** + * This function generates double precision floating point + * pseudorandom numbers which distribute in the range [0, 1) to the + * specified array[] by one call. This function is the same as + * dsfmt_gv_fill_array_close1_open2() except the distribution range. + * This function uses \b global variables. + * @param array an array where pseudorandom numbers are filled + * by this function. + * @param size the number of pseudorandom numbers to be generated. + * see also \sa dsfmt_fill_array_close1_open2() \sa + * dsfmt_gv_fill_array_close1_open2() + */ +inline static void dsfmt_gv_fill_array_close_open(double array[], int size) { + dsfmt_fill_array_close_open(&dsfmt_global_data, array, size); +} + +/** + * This function generates double precision floating point + * pseudorandom numbers which distribute in the range (0, 1) to the + * specified array[] by one call. This function is the same as + * dsfmt_gv_fill_array_close1_open2() except the distribution range. + * This function uses \b global variables. + * @param array an array where pseudorandom numbers are filled + * by this function. + * @param size the number of pseudorandom numbers to be generated. + * see also \sa dsfmt_fill_array_close1_open2() \sa + * dsfmt_gv_fill_array_close1_open2() + */ +inline static void dsfmt_gv_fill_array_open_open(double array[], int size) { + dsfmt_fill_array_open_open(&dsfmt_global_data, array, size); +} + +/** + * This function initializes the internal state array with a 32-bit + * integer seed. + * @param dsfmt dsfmt state vector. + * @param seed a 32-bit integer used as the seed. + */ +inline static void dsfmt_init_gen_rand(dsfmt_t *dsfmt, uint32_t seed) { + dsfmt_chk_init_gen_rand(dsfmt, seed, DSFMT_MEXP); +} + +/** + * This function initializes the internal state array with a 32-bit + * integer seed. This function uses \b global variables. + * @param seed a 32-bit integer used as the seed. + * see also \sa dsfmt_init_gen_rand() + */ +inline static void dsfmt_gv_init_gen_rand(uint32_t seed) { + dsfmt_init_gen_rand(&dsfmt_global_data, seed); +} + +/** + * This function initializes the internal state array, + * with an array of 32-bit integers used as the seeds. + * @param dsfmt dsfmt state vector + * @param init_key the array of 32-bit integers, used as a seed. + * @param key_length the length of init_key. + */ +inline static void dsfmt_init_by_array(dsfmt_t *dsfmt, uint32_t init_key[], + int key_length) { + dsfmt_chk_init_by_array(dsfmt, init_key, key_length, DSFMT_MEXP); +} + +/** + * This function initializes the internal state array, + * with an array of 32-bit integers used as the seeds. + * This function uses \b global variables. + * @param init_key the array of 32-bit integers, used as a seed. + * @param key_length the length of init_key. + * see also \sa dsfmt_init_by_array() + */ +inline static void dsfmt_gv_init_by_array(uint32_t init_key[], int key_length) { + dsfmt_init_by_array(&dsfmt_global_data, init_key, key_length); +} + +#if !defined(DSFMT_DO_NOT_USE_OLD_NAMES) +DSFMT_PRE_INLINE const char *get_idstring(void) DSFMT_PST_INLINE; +DSFMT_PRE_INLINE int get_min_array_size(void) DSFMT_PST_INLINE; +DSFMT_PRE_INLINE void init_gen_rand(uint32_t seed) DSFMT_PST_INLINE; +DSFMT_PRE_INLINE void init_by_array(uint32_t init_key[], int key_length) + DSFMT_PST_INLINE; +DSFMT_PRE_INLINE double genrand_close1_open2(void) DSFMT_PST_INLINE; +DSFMT_PRE_INLINE double genrand_close_open(void) DSFMT_PST_INLINE; +DSFMT_PRE_INLINE double genrand_open_close(void) DSFMT_PST_INLINE; +DSFMT_PRE_INLINE double genrand_open_open(void) DSFMT_PST_INLINE; +DSFMT_PRE_INLINE void fill_array_open_close(double array[], int size) + DSFMT_PST_INLINE; +DSFMT_PRE_INLINE void fill_array_close_open(double array[], int size) + DSFMT_PST_INLINE; +DSFMT_PRE_INLINE void fill_array_open_open(double array[], int size) + DSFMT_PST_INLINE; +DSFMT_PRE_INLINE void fill_array_close1_open2(double array[], int size) + DSFMT_PST_INLINE; + +/** + * This function is just the same as dsfmt_get_idstring(). + * @return id string. + * see also \sa dsfmt_get_idstring() + */ +inline static const char *get_idstring(void) { + return dsfmt_get_idstring(); +} + +/** + * This function is just the same as dsfmt_get_min_array_size(). + * @return minimum size of array used for fill_array functions. + * see also \sa dsfmt_get_min_array_size() + */ +inline static int get_min_array_size(void) { + return dsfmt_get_min_array_size(); +} + +/** + * This function is just the same as dsfmt_gv_init_gen_rand(). + * @param seed a 32-bit integer used as the seed. + * see also \sa dsfmt_gv_init_gen_rand(), \sa dsfmt_init_gen_rand(). + */ +inline static void init_gen_rand(uint32_t seed) { + dsfmt_gv_init_gen_rand(seed); +} + +/** + * This function is just the same as dsfmt_gv_init_by_array(). + * @param init_key the array of 32-bit integers, used as a seed. + * @param key_length the length of init_key. + * see also \sa dsfmt_gv_init_by_array(), \sa dsfmt_init_by_array(). + */ +inline static void init_by_array(uint32_t init_key[], int key_length) { + dsfmt_gv_init_by_array(init_key, key_length); +} + +/** + * This function is just the same as dsfmt_gv_genrand_close1_open2(). + * @return double precision floating point number. + * see also \sa dsfmt_genrand_close1_open2() \sa + * dsfmt_gv_genrand_close1_open2() + */ +inline static double genrand_close1_open2(void) { + return dsfmt_gv_genrand_close1_open2(); +} + +/** + * This function is just the same as dsfmt_gv_genrand_close_open(). + * @return double precision floating point number. + * see also \sa dsfmt_genrand_close_open() \sa + * dsfmt_gv_genrand_close_open() + */ +inline static double genrand_close_open(void) { + return dsfmt_gv_genrand_close_open(); +} + +/** + * This function is just the same as dsfmt_gv_genrand_open_close(). + * @return double precision floating point number. + * see also \sa dsfmt_genrand_open_close() \sa + * dsfmt_gv_genrand_open_close() + */ +inline static double genrand_open_close(void) { + return dsfmt_gv_genrand_open_close(); +} + +/** + * This function is just the same as dsfmt_gv_genrand_open_open(). + * @return double precision floating point number. + * see also \sa dsfmt_genrand_open_open() \sa + * dsfmt_gv_genrand_open_open() + */ +inline static double genrand_open_open(void) { + return dsfmt_gv_genrand_open_open(); +} + +/** + * This function is juset the same as dsfmt_gv_fill_array_open_close(). + * @param array an array where pseudorandom numbers are filled + * by this function. + * @param size the number of pseudorandom numbers to be generated. + * see also \sa dsfmt_gv_fill_array_open_close(), \sa + * dsfmt_fill_array_close1_open2(), \sa + * dsfmt_gv_fill_array_close1_open2() + */ +inline static void fill_array_open_close(double array[], int size) { + dsfmt_gv_fill_array_open_close(array, size); +} + +/** + * This function is juset the same as dsfmt_gv_fill_array_close_open(). + * @param array an array where pseudorandom numbers are filled + * by this function. + * @param size the number of pseudorandom numbers to be generated. + * see also \sa dsfmt_gv_fill_array_close_open(), \sa + * dsfmt_fill_array_close1_open2(), \sa + * dsfmt_gv_fill_array_close1_open2() + */ +inline static void fill_array_close_open(double array[], int size) { + dsfmt_gv_fill_array_close_open(array, size); +} + +/** + * This function is juset the same as dsfmt_gv_fill_array_open_open(). + * @param array an array where pseudorandom numbers are filled + * by this function. + * @param size the number of pseudorandom numbers to be generated. + * see also \sa dsfmt_gv_fill_array_open_open(), \sa + * dsfmt_fill_array_close1_open2(), \sa + * dsfmt_gv_fill_array_close1_open2() + */ +inline static void fill_array_open_open(double array[], int size) { + dsfmt_gv_fill_array_open_open(array, size); +} + +/** + * This function is juset the same as dsfmt_gv_fill_array_close1_open2(). + * @param array an array where pseudorandom numbers are filled + * by this function. + * @param size the number of pseudorandom numbers to be generated. + * see also \sa dsfmt_fill_array_close1_open2(), \sa + * dsfmt_gv_fill_array_close1_open2() + */ +inline static void fill_array_close1_open2(double array[], int size) { + dsfmt_gv_fill_array_close1_open2(array, size); +} +#endif /* DSFMT_DO_NOT_USE_OLD_NAMES */ + +#endif /* DSFMT_H */ diff --git a/src/common/fdset_kqueue.c b/src/common/fdset_kqueue.c index b0daa33..c7199ae 100644 --- a/src/common/fdset_kqueue.c +++ b/src/common/fdset_kqueue.c @@ -14,6 +14,8 @@ along with this program. If not, see <http://www.gnu.org/licenses/>. */ +#include <config.h> + #ifdef HAVE_KQUEUE #include <stdint.h> diff --git a/src/common/prng.c b/src/common/prng.c new file mode 100644 index 0000000..ca87b0d --- /dev/null +++ b/src/common/prng.c @@ -0,0 +1,93 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + 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 <http://www.gnu.org/licenses/>. + */ + +#include <stdint.h> +#include <stdlib.h> +#include <string.h> +#include <pthread.h> +#include <time.h> +#include <sys/time.h> + +#include "prng.h" +#include "dSFMT.h" + +/*! \brief TLS unique key for each thread seed. */ +static pthread_key_t tls_prng_key; +static pthread_once_t tls_prng_once = PTHREAD_ONCE_INIT; + +static void tls_prng_deinit(void *ptr) +{ + free(ptr); +} + +static void tls_prng_deinit_main() +{ + tls_prng_deinit(pthread_getspecific(tls_prng_key)); +} + +static void tls_prng_init() +{ + (void) pthread_key_create(&tls_prng_key, tls_prng_deinit); + atexit(tls_prng_deinit_main); // Main thread cleanup +} + +double tls_rand() +{ + /* Setup PRNG state for current thread. */ + (void)pthread_once(&tls_prng_once, tls_prng_init); + + /* Create PRNG state if not exists. */ + dsfmt_t* s = pthread_getspecific(tls_prng_key); + if (!s) { + /* Initialize seed from system PRNG generator. */ + uint32_t seed = 0; + FILE *fp = fopen("/dev/urandom", "r"); + if (fp == NULL) { + fp = fopen("/dev/random", "r"); + } + if (fp != NULL) { + if (fread(&seed, sizeof(uint32_t), 1, fp) != 1) { + fclose(fp); + fp = NULL; + } + } + if (fp == NULL) { + fprintf(stderr, "error: PRNG: cannot seed from " + "/dev/urandom, seeding from local time\n"); + struct timeval tv; + if (gettimeofday(&tv, NULL) == 0) { + seed = (uint32_t)(tv.tv_sec ^ tv.tv_usec); + } else { + /* Last resort. */ + seed = (uint32_t)time(NULL); + } + } else { + fclose(fp); + } + + /* Initialize PRNG state. */ + s = malloc(sizeof(dsfmt_t)); + if (s == NULL) { + fprintf(stderr, "error: PRNG: not enough memory\n"); + return .0; + } else { + dsfmt_init_gen_rand(s, seed); + (void)pthread_setspecific(tls_prng_key, s); + } + } + + return dsfmt_genrand_close_open(s); +} diff --git a/src/common/prng.h b/src/common/prng.h new file mode 100644 index 0000000..9f17a78 --- /dev/null +++ b/src/common/prng.h @@ -0,0 +1,41 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + 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 <http://www.gnu.org/licenses/>. + */ +/*! + * \file prng.h + * + * \author Marek Vavrusa <marek.vavrusa@nic.cz> + * + * \brief Pseudo-random number generator interface. + * + * Interface for accessing underlying PRNG. + * + * \addtogroup common_lib + * @{ + */ + +#ifndef _KNOTD_PRNG_H_ +#define _KNOTD_PRNG_H_ + +/*! + * \brief Get pseudorandom number from PRNG initialized in thread-local storage. + * + * No need for initialization, TLS will take care of it. + * + * \retval Pseudorandom number. + */ +double tls_rand(); + +#endif //_KNOTD_ACL_H_ diff --git a/src/config.h.in b/src/config.h.in index 521adb8..8fe63ce 100644 --- a/src/config.h.in +++ b/src/config.h.in @@ -9,6 +9,9 @@ /* Enable verbose debugging messages. */ #undef DEBUG_ENABLE_VERBOSE +/* DSFMT parameters. */ +#undef DSFMT_MEXP + /* recvmmsg enabled */ #undef ENABLE_RECVMMSG diff --git a/src/knot/server/tcp-handler.c b/src/knot/server/tcp-handler.c index 2fdc354..71452e9 100644 --- a/src/knot/server/tcp-handler.c +++ b/src/knot/server/tcp-handler.c @@ -28,7 +28,7 @@ #include "common/sockaddr.h" #include "common/skip-list.h" #include "common/fdset.h" -#include "common/WELL1024a.h" +#include "common/prng.h" #include "knot/common.h" #include "knot/server/tcp-handler.h" #include "knot/server/xfr-handler.h" diff --git a/src/knot/server/xfr-handler.c b/src/knot/server/xfr-handler.c index cec3f53..bc55434 100644 --- a/src/knot/server/xfr-handler.c +++ b/src/knot/server/xfr-handler.c @@ -39,7 +39,7 @@ #include "libknot/util/error.h" #include "libknot/tsig-op.h" #include "common/evsched.h" -#include "common/WELL1024a.h" +#include "common/prng.h" /* Constants */ #define XFR_BUFFER_SIZE 65535 /*! Do not change this - maximum value for UDP packet length. */ diff --git a/src/knot/server/zones.c b/src/knot/server/zones.c index bd23c7d..8616ebd 100644 --- a/src/knot/server/zones.c +++ b/src/knot/server/zones.c @@ -17,7 +17,7 @@ #include <sys/stat.h> #include "common/lists.h" -#include "common/WELL1024a.h" +#include "common/prng.h" #include "libknot/dname.h" #include "libknot/util/wire.h" #include "knot/zone/zone-dump-text.h" diff --git a/src/knot/zone/zone-dump-text.c b/src/knot/zone/zone-dump-text.c index 2c86d20..8ce0441 100644 --- a/src/knot/zone/zone-dump-text.c +++ b/src/knot/zone/zone-dump-text.c @@ -49,6 +49,7 @@ #include <netdb.h> #include "libknot/libknot.h" +#include "knot/other/error.h" #include "libknot/common.h" #include "common/skip-list.h" #include "common/base32hex.h" @@ -310,6 +311,25 @@ char *rdata_dname_to_string(knot_rdata_item_t item) return knot_dname_to_str(item.dname); } +char *rdata_binary_dname_to_string(knot_rdata_item_t item) +{ + if (item.raw_data == NULL) { + return NULL; + } + /* Create new dname frow raw data - probably the easiest way. */ + knot_dname_t *dname = knot_dname_new_from_wire((uint8_t *)(item.raw_data + 1), + item.raw_data[0], NULL); + if (dname == NULL) { + return NULL; + } + + /* Create string. */ + char *str = knot_dname_to_str(dname); + knot_dname_free(&dname); + + return str; +} + char *rdata_dns_name_to_string(knot_rdata_item_t item) { return knot_dname_to_str(item.dname); @@ -328,14 +348,13 @@ static char *rdata_txt_data_to_string(const uint8_t *data) * 3 because: opening '"', closing '"', and \0 at the end. * Times 2 because string can be all "double chars". */ - size_t current_length = sizeof(char) * (length * 2 + 3); + size_t current_length = sizeof(char) * (length * 2 + 4); char *ret = malloc(current_length); if (ret == NULL) { ERR_ALLOC_FAILED; return NULL; } - memset(ret, 0, sizeof(char) * (length * 2 + 3)); - + memset(ret, 0, current_length); strcat(ret, "\""); @@ -368,7 +387,7 @@ static char *rdata_txt_data_to_string(const uint8_t *data) char *rdata_text_to_string(knot_rdata_item_t item) { uint16_t size = item.raw_data[0]; - char *ret = malloc(sizeof(char) * size * 2) ; + char *ret = malloc(sizeof(char) * size * 2 + 1) ; if (ret == NULL) { ERR_ALLOC_FAILED; return NULL; @@ -589,10 +608,22 @@ char *rdata_hexlen_to_string(knot_rdata_item_t item) char *rdata_nsap_to_string(knot_rdata_item_t item) { - char *ret = malloc(sizeof(char) * (rdata_item_size(item) + 3)); + char *ret = malloc(sizeof(char) * ((rdata_item_size(item) * 2) + 7)); + if (ret == NULL) { + ERR_ALLOC_FAILED; + return NULL; + } + + memset(ret, 0, sizeof(char) * ((rdata_item_size(item) * 2) + 7)); + + /* String is already terminated. */ memcpy(ret, "0x", strlen("0x")); char *converted = hex_to_string(rdata_item_data(item), rdata_item_size(item)); + if (converted == NULL) { + return NULL; + } + strcat(ret, converted); free(converted); return ret; @@ -767,11 +798,7 @@ char *rdata_ipsecgateway_to_string(knot_rdata_item_t item, return NULL; } memset(ret, 0, sizeof(char) * 4); - memcpy(ret, ".", 4); -/* ret[0] = '\"'; - ret[1] = '.'; - ret[2] = '\"'; - ret[3] = '\0'; */ + memcpy(ret, "\".\"", 4); return ret; } case IPSECKEY_IP4: @@ -779,7 +806,7 @@ char *rdata_ipsecgateway_to_string(knot_rdata_item_t item, case IPSECKEY_IP6: return rdata_aaaa_to_string(item); case IPSECKEY_DNAME: - return rdata_dname_to_string(item); + return rdata_binary_dname_to_string(item); default: return NULL; } @@ -885,6 +912,9 @@ char *rdata_unknown_to_string(knot_rdata_item_t item) char *ret = malloc(sizeof(char) * (2 * rdata_item_size(item) + strlen("\\# ") + U16_MAX_STR_LEN + 1)); + if (ret == NULL) { + return NULL; + } memcpy(ret, "\\# \0", strlen("\\# \0")); snprintf(ret + strlen("\\# "), strlen("\\# ") + U16_MAX_STR_LEN + 1, "%lu ", @@ -941,12 +971,13 @@ char *rdata_item_to_string(knot_rdata_zoneformat_t type, void (*function)(knot_node_t *node, void *data), void *data); */ -void rdata_dump_text(const knot_rdata_t *rdata, uint16_t type, FILE *f, +int rdata_dump_text(const knot_rdata_t *rdata, uint16_t type, FILE *f, const knot_rrset_t *rrset) { knot_rrtype_descriptor_t *desc = knot_rrtype_descriptor_by_type(type); char *item_str = NULL; + assert(rdata->count <= desc->length); for (int i = 0; i < rdata->count; i++) { /* Workaround for IPSec gateway. */ if (desc->zoneformat[i] == KNOT_RDATA_ZF_IPSECGATEWAY) { @@ -961,14 +992,23 @@ void rdata_dump_text(const knot_rdata_t *rdata, uint16_t type, FILE *f, rdata_item_to_string(KNOT_RDATA_ZF_UNKNOWN, rdata->items[i]); } + + if (item_str == NULL) { + /* Fatal error. */ + return KNOTD_ERROR; + } + if (i != rdata->count - 1) { fprintf(f, "%s ", item_str); } else { fprintf(f, "%s", item_str); } + free(item_str); } fprintf(f, "\n"); + + return KNOTD_EOK; } void dump_rrset_header(const knot_rrset_t *rrset, FILE *f) @@ -981,28 +1021,40 @@ void dump_rrset_header(const knot_rrset_t *rrset, FILE *f) fprintf(f, "%-5s ", knot_rrtype_to_string(rrset->type)); } -void rrsig_set_dump_text(knot_rrset_t *rrsig, FILE *f) +int rrsig_set_dump_text(knot_rrset_t *rrsig, FILE *f) { dump_rrset_header(rrsig, f); knot_rdata_t *tmp = rrsig->rdata; while (tmp->next != rrsig->rdata) { - rdata_dump_text(tmp, KNOT_RRTYPE_RRSIG, f, rrsig); + int ret = rdata_dump_text(tmp, KNOT_RRTYPE_RRSIG, f, rrsig); + if (ret != KNOTD_EOK) { + return KNOTD_ERROR; + } + dump_rrset_header(rrsig, f); tmp = tmp->next; } - rdata_dump_text(tmp, KNOT_RRTYPE_RRSIG, f, rrsig); + int ret = rdata_dump_text(tmp, KNOT_RRTYPE_RRSIG, f, rrsig); + if (ret != KNOTD_EOK) { + return KNOTD_ERROR; + } + + return KNOTD_EOK; } -void rrset_dump_text(const knot_rrset_t *rrset, FILE *f) +int rrset_dump_text(const knot_rrset_t *rrset, FILE *f) { dump_rrset_header(rrset, f); knot_rdata_t *tmp = rrset->rdata; while (tmp->next != rrset->rdata) { - rdata_dump_text(tmp, rrset->type, f, rrset); + int ret = rdata_dump_text(tmp, rrset->type, f, rrset); + if (ret != KNOTD_EOK) { + return ret; + } dump_rrset_header(rrset, f); tmp = tmp->next; } @@ -1012,6 +1064,8 @@ void rrset_dump_text(const knot_rrset_t *rrset, FILE *f) if (rrsig_set != NULL) { rrsig_set_dump_text(rrsig_set, f); } + + return KNOTD_EOK; } struct dump_param { @@ -1019,7 +1073,7 @@ struct dump_param { const knot_dname_t *origin; }; -void apex_node_dump_text(knot_node_t *node, FILE *f) +int apex_node_dump_text(knot_node_t *node, FILE *f) { knot_rrset_t dummy_rrset; dummy_rrset.type = KNOT_RRTYPE_SOA; @@ -1027,18 +1081,26 @@ void apex_node_dump_text(knot_node_t *node, FILE *f) (knot_rrset_t *)gen_tree_find(node->rrset_tree, &dummy_rrset); assert(tmp_rrset); - rrset_dump_text(tmp_rrset, f); + int ret = rrset_dump_text(tmp_rrset, f); + if (ret != KNOTD_EOK) { + return ret; + } const knot_rrset_t **rrsets = knot_node_rrsets(node); for (int i = 0; i < node->rrset_count; i++) { if (rrsets[i]->type != KNOT_RRTYPE_SOA) { - rrset_dump_text(rrsets[i], f); + ret = rrset_dump_text(rrsets[i], f); + if (ret != KNOTD_EOK) { + return ret; + } } } free(rrsets); + + return KNOTD_EOK; } void node_dump_text(knot_node_t *node, void *data) @@ -1058,7 +1120,7 @@ void node_dump_text(knot_node_t *node, void *data) knot_node_rrsets(node); for (int i = 0; i < node->rrset_count; i++) { - rrset_dump_text(rrsets[i], f); + rrset_dump_text(rrsets[i], f); } free(rrsets); diff --git a/src/libknot/dname.h b/src/libknot/dname.h index c0e3f35..9efcffe 100644 --- a/src/libknot/dname.h +++ b/src/libknot/dname.h @@ -29,6 +29,7 @@ #include <stdint.h> #include <string.h> +#include <stdio.h> #include "common/ref.h" struct knot_node; @@ -390,17 +391,13 @@ unsigned int knot_dname_get_id(const knot_dname_t *dname); static inline void knot_dname_retain(knot_dname_t *dname) { if (dname) { ref_retain(&dname->ref); -// char *name = knot_dname_to_str(dname); -// printf("retain: %s %p %d\n", name, dname, dname->ref.count); -// free(name); - } } /*#define knot_dname_retain(d) \ knot_dname_retain_((d));\ if ((d))\ - printf("dname_retain: %s() at %s:%d, %p refcount=%zu\n",\ + fprintf(stderr, "dname_retain: %s() at %s:%d, %p refcount=%zu\n",\ __func__, __FILE__, __LINE__, d, (d)->ref.count) */ /*! @@ -410,16 +407,13 @@ static inline void knot_dname_retain(knot_dname_t *dname) { */ static inline void knot_dname_release(knot_dname_t *dname) { if (dname) { -// char *name = knot_dname_to_str(dname); -// printf("releasing: %p %s %d\n", dname, name, dname->ref.count - 1); -// free(name); ref_release(&dname->ref); } } /*#define knot_dname_release(d) \ if ((d))\ - printf("dname_release: %s() at %s:%d, %p refcount=%zu\n",\ + fprintf(stderr, "dname_release: %s() at %s:%d, %p refcount=%zu\n",\ __func__, __FILE__, __LINE__, d, (d)->ref.count-1);\ knot_dname_release_((d)) */ diff --git a/src/libknot/nameserver/name-server.c b/src/libknot/nameserver/name-server.c index f353ee7..a4e4ae7 100644 --- a/src/libknot/nameserver/name-server.c +++ b/src/libknot/nameserver/name-server.c @@ -178,7 +178,7 @@ static knot_rrset_t *ns_synth_from_wildcard( * \param rrset RRSet to check (and possibly replace). */ static void ns_check_wildcard(const knot_dname_t *name, knot_packet_t *resp, - const knot_rrset_t **rrset) + knot_rrset_t **rrset) { assert(name != NULL); assert(resp != NULL); @@ -216,14 +216,14 @@ static void ns_check_wildcard(const knot_dname_t *name, knot_packet_t *resp, * \return KNOT_ENOMEM * \return KNOT_ESPACE */ -static int ns_add_rrsigs(const knot_rrset_t *rrset, knot_packet_t *resp, +static int ns_add_rrsigs(knot_rrset_t *rrset, knot_packet_t *resp, const knot_dname_t *name, int (*add_rrset_to_resp)(knot_packet_t *, - const knot_rrset_t *, - int, int, int), + knot_rrset_t *, + int, int, int, int), int tc) { - const knot_rrset_t *rrsigs; + knot_rrset_t *rrsigs; dbg_ns("Adding RRSIGs for RRSet, type: %s.\n", knot_rrtype_to_string(knot_rrset_type(rrset))); @@ -237,11 +237,11 @@ static int ns_add_rrsigs(const knot_rrset_t *rrset, knot_packet_t *resp, if (DNSSEC_ENABLED && knot_query_dnssec_requested(knot_packet_query(resp)) - && (rrsigs = knot_rrset_rrsigs(rrset)) != NULL) { + && (rrsigs = knot_rrset_get_rrsigs(rrset)) != NULL) { if (name != NULL) { ns_check_wildcard(name, resp, &rrsigs); } - return add_rrset_to_resp(resp, rrsigs, tc, 0, 0); + return add_rrset_to_resp(resp, rrsigs, tc, 0, 0, 1); } return KNOT_EOK; @@ -264,15 +264,15 @@ static void ns_follow_cname(const knot_node_t **node, const knot_dname_t **qname, knot_packet_t *resp, int (*add_rrset_to_resp)(knot_packet_t *, - const knot_rrset_t *, - int, int, int), + knot_rrset_t *, + int, int, int, int), int tc) { dbg_ns("Resolving CNAME chain...\n"); - const knot_rrset_t *cname_rrset; + knot_rrset_t *cname_rrset; while (*node != NULL - && (cname_rrset = knot_node_rrset(*node, KNOT_RRTYPE_CNAME)) + && (cname_rrset = knot_node_get_rrset(*node, KNOT_RRTYPE_CNAME)) != NULL) { /* put the CNAME record to answer, but replace the possible wildcard name with qname */ @@ -282,19 +282,19 @@ static void ns_follow_cname(const knot_node_t **node, dbg_ns("CNAME RRSet: %p, owner: %p\n", cname_rrset, cname_rrset->owner); - const knot_rrset_t *rrset = cname_rrset; + knot_rrset_t *rrset = cname_rrset; // ignoring other than the first record if (knot_dname_is_wildcard(knot_node_owner(*node))) { /* if wildcard node, we must copy the RRSet and replace its owner */ rrset = ns_synth_from_wildcard(cname_rrset, *qname); - knot_packet_add_tmp_rrset(resp, (knot_rrset_t *)rrset); - add_rrset_to_resp(resp, rrset, tc, 0, 0); + knot_packet_add_tmp_rrset(resp, rrset); + add_rrset_to_resp(resp, rrset, tc, 0, 0, 1); ns_add_rrsigs(cname_rrset, resp, *qname, add_rrset_to_resp, tc); } else { - add_rrset_to_resp(resp, rrset, tc, 0, 0); + add_rrset_to_resp(resp, rrset, tc, 0, 0, 1); ns_add_rrsigs(rrset, resp, *qname, add_rrset_to_resp, tc); } @@ -350,13 +350,13 @@ dbg_ns_exec( switch (type) { case KNOT_RRTYPE_ANY: { dbg_ns("Returning all RRTYPES.\n"); - const knot_rrset_t **rrsets = knot_node_rrsets(node); + knot_rrset_t **rrsets = knot_node_get_rrsets(node); if (rrsets == NULL) { break; } int i = 0; int ret = 0; - const knot_rrset_t *rrset; + knot_rrset_t *rrset; while (i < knot_node_rrset_count(node)) { assert(rrsets[i] != NULL); rrset = rrsets[i]; @@ -366,7 +366,7 @@ dbg_ns_exec( ns_check_wildcard(name, resp, &rrset); ret = knot_response_add_rrset_answer(resp, rrset, 1, - 0, 0); + 0, 0, 1); if (ret >= 0 && (added += 1) && (ret = ns_add_rrsigs(rrset, resp, name, knot_response_add_rrset_answer, 1)) @@ -387,16 +387,16 @@ dbg_ns_exec( } case KNOT_RRTYPE_RRSIG: { dbg_ns("Returning all RRSIGs.\n"); - const knot_rrset_t **rrsets = knot_node_rrsets(node); + knot_rrset_t **rrsets = knot_node_get_rrsets(node); if (rrsets == NULL) { break; } int i = 0; int ret = 0; - const knot_rrset_t *rrset; + knot_rrset_t *rrset; while (i < knot_node_rrset_count(node)) { assert(rrsets[i] != NULL); - rrset = knot_rrset_rrsigs(rrsets[i]); + rrset = knot_rrset_get_rrsigs(rrsets[i]); if (rrset == NULL) { ++i; @@ -405,7 +405,7 @@ dbg_ns_exec( ns_check_wildcard(name, resp, &rrset); ret = knot_response_add_rrset_answer(resp, rrset, 1, - 0, 0); + 0, 0, 1); if (ret < 0) { break; @@ -419,14 +419,14 @@ dbg_ns_exec( } default: { int ret = 0; - const knot_rrset_t *rrset = knot_node_rrset(node, type); - const knot_rrset_t *rrset2 = rrset; + knot_rrset_t *rrset = knot_node_get_rrset(node, type); + knot_rrset_t *rrset2 = rrset; if (rrset != NULL) { dbg_ns("Found RRSet of type %s\n", knot_rrtype_to_string(type)); ns_check_wildcard(name, resp, &rrset2); ret = knot_response_add_rrset_answer(resp, rrset2, 1, - 0, 0); + 0, 0, 1); if (ret >= 0 && (added += 1) && (ret = ns_add_rrsigs(rrset, resp, name, knot_response_add_rrset_answer, 1)) > 0) { @@ -490,7 +490,7 @@ static void ns_put_additional_for_rrset(knot_packet_t *resp, // assert(!knot_node_is_old(node)); } - const knot_rrset_t *rrset_add; + knot_rrset_t *rrset_add; if (node != NULL) { dbg_ns_exec( @@ -510,26 +510,26 @@ dbg_ns_exec( // A RRSet dbg_ns("A RRSets...\n"); - rrset_add = knot_node_rrset(node, KNOT_RRTYPE_A); + rrset_add = knot_node_get_rrset(node, KNOT_RRTYPE_A); if (rrset_add != NULL) { dbg_ns("Found A RRsets.\n"); - const knot_rrset_t *rrset_add2 = rrset_add; + knot_rrset_t *rrset_add2 = rrset_add; ns_check_wildcard(dname, resp, &rrset_add2); knot_response_add_rrset_additional( - resp, rrset_add2, 0, 1, 0); + resp, rrset_add2, 0, 1, 0, 1); ns_add_rrsigs(rrset_add, resp, dname, knot_response_add_rrset_additional, 0); } // AAAA RRSet dbg_ns("AAAA RRSets...\n"); - rrset_add = knot_node_rrset(node, KNOT_RRTYPE_AAAA); + rrset_add = knot_node_get_rrset(node, KNOT_RRTYPE_AAAA); if (rrset_add != NULL) { dbg_ns("Found AAAA RRsets.\n"); - const knot_rrset_t *rrset_add2 = rrset_add; + knot_rrset_t *rrset_add2 = rrset_add; ns_check_wildcard(dname, resp, &rrset_add2); knot_response_add_rrset_additional( - resp, rrset_add2, 0, 1, 0); + resp, rrset_add2, 0, 1, 0, 1); ns_add_rrsigs(rrset_add, resp, dname, knot_response_add_rrset_additional, 0); } @@ -601,11 +601,11 @@ static void ns_put_additional(knot_packet_t *resp) static void ns_put_authority_ns(const knot_zone_contents_t *zone, knot_packet_t *resp) { - const knot_rrset_t *ns_rrset = knot_node_rrset( + knot_rrset_t *ns_rrset = knot_node_get_rrset( knot_zone_contents_apex(zone), KNOT_RRTYPE_NS); if (ns_rrset != NULL) { - knot_response_add_rrset_authority(resp, ns_rrset, 0, 1, 0); + knot_response_add_rrset_authority(resp, ns_rrset, 0, 1, 0, 1); ns_add_rrsigs(ns_rrset, resp, knot_node_owner( knot_zone_contents_apex(zone)), knot_response_add_rrset_authority, 1); @@ -622,7 +622,7 @@ static void ns_put_authority_ns(const knot_zone_contents_t *zone, static int ns_put_authority_soa(const knot_zone_contents_t *zone, knot_packet_t *resp) { - const knot_rrset_t *soa_rrset = knot_node_rrset( + knot_rrset_t *soa_rrset = knot_node_get_rrset( knot_zone_contents_apex(zone), KNOT_RRTYPE_SOA); assert(soa_rrset != NULL); @@ -640,7 +640,7 @@ static int ns_put_authority_soa(const knot_zone_contents_t *zone, assert(soa_rrset != NULL); - int ret = knot_response_add_rrset_authority(resp, soa_rrset, 0, 0, 0); + int ret = knot_response_add_rrset_authority(resp, soa_rrset, 0, 0, 0, 1); if (ret == KNOT_EOK) { ret = ns_add_rrsigs(soa_rrset, resp, knot_node_owner(knot_zone_contents_apex(zone)), @@ -701,14 +701,13 @@ static void ns_put_nsec3_from_node(const knot_node_t *node, assert(DNSSEC_ENABLED && knot_query_dnssec_requested(knot_packet_query(resp))); - const knot_rrset_t *rrset = knot_node_rrset(node, - KNOT_RRTYPE_NSEC3); + knot_rrset_t *rrset = knot_node_get_rrset(node, KNOT_RRTYPE_NSEC3); assert(rrset != NULL); - int res = knot_response_add_rrset_authority(resp, rrset, 1, 1, 0); + int res = knot_response_add_rrset_authority(resp, rrset, 1, 1, 0, 1); // add RRSIG for the RRSet - if (res == 0 && (rrset = knot_rrset_rrsigs(rrset)) != NULL) { - knot_response_add_rrset_authority(resp, rrset, 1, 0, 0); + if (res == 0 && (rrset = knot_rrset_get_rrsigs(rrset)) != NULL) { + knot_response_add_rrset_authority(resp, rrset, 1, 0, 0, 1); } } @@ -958,16 +957,16 @@ static void ns_put_nsec_nsec3_nodata(const knot_node_t *node, return; } - const knot_node_t *nsec3_node = knot_node_nsec3_node(node, 1); - const knot_rrset_t *rrset = NULL; - if ((rrset = knot_node_rrset(node, KNOT_RRTYPE_NSEC)) != NULL + knot_node_t *nsec3_node = knot_node_get_nsec3_node(node, 1); + knot_rrset_t *rrset = NULL; + if ((rrset = knot_node_get_rrset(node, KNOT_RRTYPE_NSEC)) != NULL || (nsec3_node != NULL && (rrset = - knot_node_rrset(nsec3_node, KNOT_RRTYPE_NSEC3)) != NULL)) { - knot_response_add_rrset_authority(resp, rrset, 1, 0, 0); + knot_node_get_rrset(nsec3_node, KNOT_RRTYPE_NSEC3)) != NULL)) { + knot_response_add_rrset_authority(resp, rrset, 1, 0, 0, 1); // add RRSIG for the RRSet - if ((rrset = knot_rrset_rrsigs(rrset)) != NULL) { + if ((rrset = knot_rrset_get_rrsigs(rrset)) != NULL) { knot_response_add_rrset_authority(resp, rrset, 1, - 0, 0); + 0, 0, 1); } } } @@ -996,7 +995,7 @@ static int ns_put_nsec_nxdomain(const knot_dname_t *qname, const knot_node_t *closest_encloser, knot_packet_t *resp) { - const knot_rrset_t *rrset = NULL; + knot_rrset_t *rrset = NULL; // check if we have previous; if not, find one using the tree if (previous == NULL) { @@ -1016,7 +1015,7 @@ static int ns_put_nsec_nxdomain(const knot_dname_t *qname, free(name); // 1) NSEC proving that there is no node with the searched name - rrset = knot_node_rrset(previous, KNOT_RRTYPE_NSEC); + rrset = knot_node_get_rrset(previous, KNOT_RRTYPE_NSEC); if (rrset == NULL) { // no NSEC records //return NS_ERR_SERVFAIL; @@ -1024,10 +1023,10 @@ static int ns_put_nsec_nxdomain(const knot_dname_t *qname, } - knot_response_add_rrset_authority(resp, rrset, 1, 0, 0); - rrset = knot_rrset_rrsigs(rrset); + knot_response_add_rrset_authority(resp, rrset, 1, 0, 0, 1); + rrset = knot_rrset_get_rrsigs(rrset); assert(rrset != NULL); - knot_response_add_rrset_authority(resp, rrset, 1, 0, 0); + knot_response_add_rrset_authority(resp, rrset, 1, 0, 0, 1); // 2) NSEC proving that there is no wildcard covering the name // this is only different from 1) if the wildcard would be @@ -1060,12 +1059,12 @@ static int ns_put_nsec_nxdomain(const knot_dname_t *qname, knot_dname_free(&wildcard); if (prev_new != previous) { - rrset = knot_node_rrset(prev_new, KNOT_RRTYPE_NSEC); + rrset = knot_node_get_rrset(prev_new, KNOT_RRTYPE_NSEC); assert(rrset != NULL); - knot_response_add_rrset_authority(resp, rrset, 1, 0, 0); - rrset = knot_rrset_rrsigs(rrset); + knot_response_add_rrset_authority(resp, rrset, 1, 0, 0, 1); + rrset = knot_rrset_get_rrsigs(rrset); assert(rrset != NULL); - knot_response_add_rrset_authority(resp, rrset, 1, 0, 0); + knot_response_add_rrset_authority(resp, rrset, 1, 0, 0, 1); } return KNOT_EOK; @@ -1236,14 +1235,14 @@ static void ns_put_nsec_wildcard(const knot_zone_contents_t *zone, assert(previous != NULL); } - const knot_rrset_t *rrset = - knot_node_rrset(previous, KNOT_RRTYPE_NSEC); + knot_rrset_t *rrset = + knot_node_get_rrset(previous, KNOT_RRTYPE_NSEC); if (rrset != NULL) { // NSEC proving that there is no node with the searched name - knot_response_add_rrset_authority(resp, rrset, 1, 0, 0); - rrset = knot_rrset_rrsigs(rrset); + knot_response_add_rrset_authority(resp, rrset, 1, 0, 0, 1); + rrset = knot_rrset_get_rrsigs(rrset); assert(rrset != NULL); - knot_response_add_rrset_authority(resp, rrset, 1, 0, 0); + knot_response_add_rrset_authority(resp, rrset, 1, 0, 0, 1); } } @@ -1360,13 +1359,13 @@ static inline int ns_referral(const knot_node_t *node, node = knot_node_parent(node, 1); } - const knot_rrset_t *rrset = knot_node_rrset(node, KNOT_RRTYPE_NS); + knot_rrset_t *rrset = knot_node_get_rrset(node, KNOT_RRTYPE_NS); assert(rrset != NULL); // TODO: wildcards?? //ns_check_wildcard(name, resp, &rrset); - knot_response_add_rrset_authority(resp, rrset, 1, 0, 0); + knot_response_add_rrset_authority(resp, rrset, 1, 0, 0, 1); ns_add_rrsigs(rrset, resp, node->owner, knot_response_add_rrset_authority, 1); @@ -1377,10 +1376,10 @@ static inline int ns_referral(const knot_node_t *node, dbg_ns("DS records: %p\n", knot_node_rrset(node, KNOT_RRTYPE_DS)); if (DNSSEC_ENABLED && knot_query_dnssec_requested(knot_packet_query(resp))) { - rrset = knot_node_rrset(node, KNOT_RRTYPE_DS); + rrset = knot_node_get_rrset(node, KNOT_RRTYPE_DS); if (rrset != NULL) { knot_response_add_rrset_authority(resp, rrset, 1, 0, - 0); + 0, 1); ns_add_rrsigs(rrset, resp, node->owner, knot_response_add_rrset_authority, 1); } else { @@ -1401,15 +1400,15 @@ static inline int ns_referral(const knot_node_t *node, &node, qname, resp); } } else { - const knot_rrset_t *nsec = knot_node_rrset( + knot_rrset_t *nsec = knot_node_get_rrset( node, KNOT_RRTYPE_NSEC); if (nsec) { /*! \todo Check return value? */ knot_response_add_rrset_authority( - resp, nsec, 1, 1, 0); + resp, nsec, 1, 1, 0, 1); if ((nsec = knot_rrset_rrsigs(nsec)) != NULL) { - knot_response_add_rrset_authority(resp, nsec, 1, - 1, 0); + knot_response_add_rrset_authority( + resp, nsec, 1, 1, 0, 1); } } } @@ -1586,7 +1585,7 @@ static int ns_dname_is_too_long(const knot_rrset_t *dname_rrset, * \param qname Searched name. * \param resp Response. */ -static void ns_process_dname(const knot_rrset_t *dname_rrset, +static void ns_process_dname(knot_rrset_t *dname_rrset, const knot_dname_t *qname, knot_packet_t *resp) { @@ -1598,7 +1597,7 @@ dbg_ns_exec( // TODO: check the number of RRs in the RRSet?? // put the DNAME RRSet into the answer - knot_response_add_rrset_answer(resp, dname_rrset, 1, 0, 0); + knot_response_add_rrset_answer(resp, dname_rrset, 1, 0, 0, 1); ns_add_rrsigs(dname_rrset, resp, qname, knot_response_add_rrset_answer, 1); @@ -1610,7 +1609,7 @@ dbg_ns_exec( // synthetize CNAME (no way to tell that client supports DNAME) knot_rrset_t *synth_cname = ns_cname_from_dname(dname_rrset, qname); // add the synthetized RRSet to the Answer - knot_response_add_rrset_answer(resp, synth_cname, 1, 0, 0); + knot_response_add_rrset_answer(resp, synth_cname, 1, 0, 0, 1); // no RRSIGs for this RRSet @@ -1629,10 +1628,10 @@ dbg_ns_exec( */ static void ns_add_dnskey(const knot_node_t *apex, knot_packet_t *resp) { - const knot_rrset_t *rrset = - knot_node_rrset(apex, KNOT_RRTYPE_DNSKEY); + knot_rrset_t *rrset = + knot_node_get_rrset(apex, KNOT_RRTYPE_DNSKEY); if (rrset != NULL) { - knot_response_add_rrset_additional(resp, rrset, 0, 0, 0); + knot_response_add_rrset_additional(resp, rrset, 0, 0, 0, 1); ns_add_rrsigs(rrset, resp, apex->owner, knot_response_add_rrset_additional, 0); } @@ -1732,7 +1731,7 @@ have_node: if (find_ret == KNOT_ZONE_NAME_NOT_FOUND) { // DNAME? - const knot_rrset_t *dname_rrset = knot_node_rrset( + knot_rrset_t *dname_rrset = knot_node_get_rrset( closest_encloser, KNOT_RRTYPE_DNAME); if (dname_rrset != NULL) { ns_process_dname(dname_rrset, qname, resp); @@ -2151,7 +2150,7 @@ dbg_ns_exec( return; } - const knot_rrset_t **rrsets = knot_node_rrsets(node); + knot_rrset_t **rrsets = knot_node_get_rrsets(node); if (rrsets == NULL) { params->ret = KNOT_ENOMEM; return; @@ -2159,7 +2158,7 @@ dbg_ns_exec( int i = 0; int ret = 0; - const knot_rrset_t *rrset = NULL; + knot_rrset_t *rrset = NULL; while (i < knot_node_rrset_count(node)) { assert(rrsets[i] != NULL); rrset = rrsets[i]; @@ -2174,7 +2173,7 @@ rrset: } ret = knot_response_add_rrset_answer(params->xfr->response, - rrset, 0, 0, 1); + rrset, 0, 0, 1, 0); if (ret == KNOT_ESPACE) { // TODO: send the packet and clean the structure @@ -2195,7 +2194,7 @@ rrset: } // we can send the RRSets in any order, so add the RRSIGs now - rrset = knot_rrset_rrsigs(rrset); + rrset = knot_rrset_get_rrsigs(rrset); rrsigs: if (rrset == NULL) { ++i; @@ -2203,7 +2202,7 @@ rrsigs: } ret = knot_response_add_rrset_answer(params->xfr->response, - rrset, 0, 0, 1); + rrset, 0, 0, 1, 0); if (ret == KNOT_ESPACE) { // TODO: send the packet and clean the structure @@ -2258,7 +2257,7 @@ static int ns_axfr_from_zone(knot_zone_contents_t *zone, knot_ns_xfr_t *xfr) */ // retrieve SOA - must be send as first and last RR - const knot_rrset_t *soa_rrset = knot_node_rrset( + knot_rrset_t *soa_rrset = knot_node_get_rrset( knot_zone_contents_apex(zone), KNOT_RRTYPE_SOA); if (soa_rrset == NULL) { // some really serious error @@ -2268,17 +2267,18 @@ static int ns_axfr_from_zone(knot_zone_contents_t *zone, knot_ns_xfr_t *xfr) int ret; // add SOA RR to the response - ret = knot_response_add_rrset_answer(xfr->response, soa_rrset, 0, 0, 1); + ret = knot_response_add_rrset_answer(xfr->response, soa_rrset, 0, 0, 1, + 0); if (ret != KNOT_EOK) { // something is really wrong return KNOT_ERROR; } // add the SOA's RRSIG - const knot_rrset_t *rrset = knot_rrset_rrsigs(soa_rrset); + knot_rrset_t *rrset = knot_rrset_get_rrsigs(soa_rrset); if (rrset != NULL && (ret = knot_response_add_rrset_answer(xfr->response, rrset, - 0, 0, 1)) != KNOT_EOK) { + 0, 0, 1, 0)) != KNOT_EOK) { // something is really wrong, these should definitely fit in return KNOT_ERROR; } @@ -2302,7 +2302,8 @@ static int ns_axfr_from_zone(knot_zone_contents_t *zone, knot_ns_xfr_t *xfr) */ // try to add the SOA to the response again (last RR) - ret = knot_response_add_rrset_answer(xfr->response, soa_rrset, 0, 0, 1); + ret = knot_response_add_rrset_answer(xfr->response, soa_rrset, 0, 0, 1, + 0); if (ret == KNOT_ESPACE) { // if there is not enough space, send the response and @@ -2315,7 +2316,7 @@ static int ns_axfr_from_zone(knot_zone_contents_t *zone, knot_ns_xfr_t *xfr) } ret = knot_response_add_rrset_answer(xfr->response, - soa_rrset, 0, 0, 1); + soa_rrset, 0, 0, 1, 0); if (ret != KNOT_EOK) { return KNOT_ERROR; } @@ -2331,17 +2332,17 @@ static int ns_axfr_from_zone(knot_zone_contents_t *zone, knot_ns_xfr_t *xfr) /*----------------------------------------------------------------------------*/ -static int ns_ixfr_put_rrset(knot_ns_xfr_t *xfr, const knot_rrset_t *rrset) +static int ns_ixfr_put_rrset(knot_ns_xfr_t *xfr, knot_rrset_t *rrset) { int res = knot_response_add_rrset_answer(xfr->response, rrset, - 0, 0, 0); + 0, 0, 0, 0); if (res == KNOT_ESPACE) { knot_response_set_rcode(xfr->response, KNOT_RCODE_NOERROR); /*! \todo Probably rename the function. */ ns_xfr_send_and_clear(xfr, knot_ns_tsig_required(xfr->packet_nr)); res = knot_response_add_rrset_answer(xfr->response, - rrset, 0, 0, 0); + rrset, 0, 0, 0, 0); } if (res != KNOT_EOK) { @@ -2408,13 +2409,13 @@ static int ns_ixfr_from_zone(knot_ns_xfr_t *xfr) knot_changesets_t *chgsets = (knot_changesets_t *)xfr->data; knot_zone_contents_t *contents = knot_zone_get_contents(xfr->zone); assert(contents); - const knot_rrset_t *zone_soa = - knot_node_rrset(knot_zone_contents_apex(contents), - KNOT_RRTYPE_SOA); + knot_rrset_t *zone_soa = + knot_node_get_rrset(knot_zone_contents_apex(contents), + KNOT_RRTYPE_SOA); // 4) put the zone SOA as the first Answer RR int res = knot_response_add_rrset_answer(xfr->response, zone_soa, 0, - 0, 0); + 0, 0, 0); if (res != KNOT_EOK) { dbg_ns("IXFR query cannot be answered: %s.\n", knot_strerror(res)); diff --git a/src/libknot/packet/response.c b/src/libknot/packet/response.c index e6f89d0..ed16e2f 100644 --- a/src/libknot/packet/response.c +++ b/src/libknot/packet/response.c @@ -987,8 +987,9 @@ int knot_response_add_opt(knot_packet_t *resp, /*----------------------------------------------------------------------------*/ int knot_response_add_rrset_answer(knot_packet_t *response, - const knot_rrset_t *rrset, int tc, - int check_duplicates, int compr_cs) + knot_rrset_t *rrset, int tc, + int check_duplicates, int compr_cs, + int rotate) { if (response == NULL || rrset == NULL) { return KNOT_EBADARG; @@ -1024,6 +1025,12 @@ int knot_response_add_rrset_answer(knot_packet_t *response, if (rrs >= 0) { response->header.ancount += rrs; + + if (rotate) { + // do round-robin rotation of the RRSet + knot_rrset_rotate(rrset); + } + return KNOT_EOK; } @@ -1033,8 +1040,9 @@ int knot_response_add_rrset_answer(knot_packet_t *response, /*----------------------------------------------------------------------------*/ int knot_response_add_rrset_authority(knot_packet_t *response, - const knot_rrset_t *rrset, int tc, - int check_duplicates, int compr_cs) + knot_rrset_t *rrset, int tc, + int check_duplicates, int compr_cs, + int rotate) { if (response == NULL || rrset == NULL) { return KNOT_EBADARG; @@ -1066,6 +1074,12 @@ int knot_response_add_rrset_authority(knot_packet_t *response, if (rrs >= 0) { response->header.nscount += rrs; + + if (rotate) { + // do round-robin rotation of the RRSet + knot_rrset_rotate(rrset); + } + return KNOT_EOK; } @@ -1075,8 +1089,9 @@ int knot_response_add_rrset_authority(knot_packet_t *response, /*----------------------------------------------------------------------------*/ int knot_response_add_rrset_additional(knot_packet_t *response, - const knot_rrset_t *rrset, int tc, - int check_duplicates, int compr_cs) + knot_rrset_t *rrset, int tc, + int check_duplicates, int compr_cs, + int rotate) { if (response == NULL || rrset == NULL) { return KNOT_EBADARG; @@ -1114,6 +1129,12 @@ int knot_response_add_rrset_additional(knot_packet_t *response, if (rrs >= 0) { response->header.arcount += rrs; + + if (rotate) { + // do round-robin rotation of the RRSet + knot_rrset_rotate(rrset); + } + return KNOT_EOK; } diff --git a/src/libknot/packet/response.h b/src/libknot/packet/response.h index 38bd9a8..d76c10c 100644 --- a/src/libknot/packet/response.h +++ b/src/libknot/packet/response.h @@ -115,8 +115,9 @@ int knot_response_add_opt(knot_packet_t *resp, * \retval KNOT_ESPACE */ int knot_response_add_rrset_answer(knot_packet_t *response, - const knot_rrset_t *rrset, int tc, - int check_duplicates, int compr_cs); + knot_rrset_t *rrset, int tc, + int check_duplicates, int compr_cs, + int rotate); /*! * \brief Adds a RRSet to the Authority section of the response. @@ -135,8 +136,9 @@ int knot_response_add_rrset_answer(knot_packet_t *response, * \retval KNOT_ESPACE */ int knot_response_add_rrset_authority(knot_packet_t *response, - const knot_rrset_t *rrset, int tc, - int check_duplicates, int compr_cs); + knot_rrset_t *rrset, int tc, + int check_duplicates, int compr_cs, + int rotate); /*! * \brief Adds a RRSet to the Additional section of the response. @@ -155,8 +157,9 @@ int knot_response_add_rrset_authority(knot_packet_t *response, * \retval KNOT_ESPACE */ int knot_response_add_rrset_additional(knot_packet_t *response, - const knot_rrset_t *rrset, int tc, - int check_duplicates, int compr_cs); + knot_rrset_t *rrset, int tc, + int check_duplicates, int compr_cs, + int rotate); /*! * \brief Sets the RCODE of the response. diff --git a/src/libknot/rrset.c b/src/libknot/rrset.c index f037716..44282fd 100644 --- a/src/libknot/rrset.c +++ b/src/libknot/rrset.c @@ -625,6 +625,13 @@ int knot_rrset_shallow_copy(const knot_rrset_t *from, knot_rrset_t **to) /*----------------------------------------------------------------------------*/ +void knot_rrset_rotate(knot_rrset_t *rrset) +{ + rrset->rdata = rrset->rdata->next; +} + +/*----------------------------------------------------------------------------*/ + void knot_rrset_free(knot_rrset_t **rrset) { if (rrset == NULL || *rrset == NULL) { diff --git a/src/libknot/rrset.h b/src/libknot/rrset.h index e13cbba..b5c11dc 100644 --- a/src/libknot/rrset.h +++ b/src/libknot/rrset.h @@ -254,6 +254,14 @@ int knot_rrset_deep_copy(const knot_rrset_t *from, knot_rrset_t **to); /*! \todo Add unit test. */ int knot_rrset_shallow_copy(const knot_rrset_t *from, knot_rrset_t **to); +/*! \brief Does round-robin rotation of the RRSet. + * + * \note This is not thread-safe. If two threads call this function, the RRSet + * may rotate twice, or not rotate at all. This is not a big issue though. + * In future we may replace this with some per-thread counter. + */ +void knot_rrset_rotate(knot_rrset_t *rrset); + /*! * \brief Destroys the RRSet structure. * diff --git a/src/libknot/updates/xfr-in.c b/src/libknot/updates/xfr-in.c index b1feddb..4a7e9ba 100644 --- a/src/libknot/updates/xfr-in.c +++ b/src/libknot/updates/xfr-in.c @@ -1476,7 +1476,7 @@ static void xfrin_rollback_update(knot_zone_contents_t *contents, } // discard new RRSets - for (int i = 0; i < changes->old_rrsets_count; ++i) { + for (int i = 0; i < changes->new_rrsets_count; ++i) { knot_rrset_deep_free(&changes->new_rrsets[i], 0, 1, 0); } diff --git a/src/libknot/util/descriptor.c b/src/libknot/util/descriptor.c index fa94c24..e6a0377 100644 --- a/src/libknot/util/descriptor.c +++ b/src/libknot/util/descriptor.c @@ -243,9 +243,72 @@ static knot_rrtype_descriptor_t { KNOT_RDATA_WF_BINARY }, { KNOT_RDATA_ZF_UNKNOWN }, true }, /* 42 */ - { KNOT_RRTYPE_APL, "APL", 1, - { KNOT_RDATA_WF_APL }, - { KNOT_RDATA_ZF_APL }, false }, + { KNOT_RRTYPE_APL, "APL", 64, + { KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL, + KNOT_RDATA_WF_APL, KNOT_RDATA_WF_APL }, + { KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL, + KNOT_RDATA_ZF_APL, KNOT_RDATA_ZF_APL }, + false }, /* 43 */ { KNOT_RRTYPE_DS, "DS", 4, { KNOT_RDATA_WF_SHORT, KNOT_RDATA_WF_BYTE, diff --git a/src/libknot/util/utils.c b/src/libknot/util/utils.c index 17b33a7..04e12c5 100644 --- a/src/libknot/util/utils.c +++ b/src/libknot/util/utils.c @@ -22,7 +22,7 @@ #include "common.h" #include "util/utils.h" -#include "common/WELL1024a.h" +#include "common/prng.h" /*----------------------------------------------------------------------------*/ diff --git a/src/libknot/zone/node.c b/src/libknot/zone/node.c index 1d2f938..61ef3e4 100644 --- a/src/libknot/zone/node.c +++ b/src/libknot/zone/node.c @@ -245,7 +245,7 @@ const knot_rrset_t *knot_node_rrset(const knot_node_t *node, /*----------------------------------------------------------------------------*/ -knot_rrset_t *knot_node_get_rrset(knot_node_t *node, uint16_t type) +knot_rrset_t *knot_node_get_rrset(const knot_node_t *node, uint16_t type) { knot_rrset_t rrset; rrset.type = type; @@ -324,26 +324,7 @@ knot_rrset_t **knot_node_get_rrsets(const knot_node_t *node) const knot_rrset_t **knot_node_rrsets(const knot_node_t *node) { - //knot_node_dump((knot_node_t *)node, (void*)1); - if (node->rrset_count == 0) { - return NULL; - } - - knot_rrset_t **rrsets = (knot_rrset_t **)malloc( - node->rrset_count * sizeof(knot_rrset_t *)); - CHECK_ALLOC_LOG(rrsets, NULL); - struct knot_node_save_rrset_arg args; - args.array = rrsets; - args.count = 0; - - gen_tree_apply_inorder(node->rrset_tree, save_rrset_to_array, - &args); - - assert(args.count == node->rrset_count); - assert(args.count); - - return (const knot_rrset_t **)rrsets; - + return (const knot_rrset_t **)knot_node_get_rrsets(node); } /*----------------------------------------------------------------------------*/ @@ -461,8 +442,8 @@ void knot_node_set_previous(knot_node_t *node, knot_node_t *prev) /*----------------------------------------------------------------------------*/ -const knot_node_t *knot_node_nsec3_node(const knot_node_t *node, - int check_version) +knot_node_t *knot_node_get_nsec3_node(const knot_node_t *node, + int check_version) { knot_node_t *nsec3_node = node->nsec3_node; if (nsec3_node == NULL) { @@ -486,6 +467,14 @@ const knot_node_t *knot_node_nsec3_node(const knot_node_t *node, /*----------------------------------------------------------------------------*/ +const knot_node_t *knot_node_nsec3_node(const knot_node_t *node, + int check_version) +{ + return knot_node_get_nsec3_node(node, check_version); +} + +/*----------------------------------------------------------------------------*/ + void knot_node_set_nsec3_node(knot_node_t *node, knot_node_t *nsec3_node) { node->nsec3_node = nsec3_node; diff --git a/src/libknot/zone/node.h b/src/libknot/zone/node.h index fcb612d..eb0d242 100644 --- a/src/libknot/zone/node.h +++ b/src/libknot/zone/node.h @@ -168,7 +168,7 @@ const knot_rrset_t *knot_node_rrset(const knot_node_t *node, * \return RRSet from node \a node having type \a type, or NULL if no such * RRSet exists in this node. */ -knot_rrset_t *knot_node_get_rrset(knot_node_t *node, uint16_t type); +knot_rrset_t *knot_node_get_rrset(const knot_node_t *node, uint16_t type); knot_rrset_t *knot_node_remove_rrset(knot_node_t *node, uint16_t type); @@ -272,8 +272,21 @@ void knot_node_set_previous(knot_node_t *node, knot_node_t *prev); * and the name of the zone \a node belongs to). * \retval NULL if the NSEC3 node is not set. */ +knot_node_t *knot_node_get_nsec3_node(const knot_node_t *node, + int check_version); + +/*! + * \brief Returns the NSEC3 node corresponding to the given node. + * + * \param node Node to get the NSEC3 node for. + * + * \return NSEC3 node corresponding to \a node (i.e. node with owner name + * created by concatenating the hash of owner domain name of \a node + * and the name of the zone \a node belongs to). + * \retval NULL if the NSEC3 node is not set. + */ const knot_node_t *knot_node_nsec3_node(const knot_node_t *node, - int check_version); + int check_version); /*! * \brief Sets the corresponding NSEC3 node of the given node. diff --git a/src/tests/libknot/libknot/tsig_tests.c b/src/tests/libknot/libknot/tsig_tests.c index 284579f..e8cab14 100644 --- a/src/tests/libknot/libknot/tsig_tests.c +++ b/src/tests/libknot/libknot/tsig_tests.c @@ -177,7 +177,7 @@ static int test_knot_tsig_sign() knot_packet_set_max_size(packet, 2048); if ((ret = knot_response_add_rrset_answer(packet, ns_rrset, - 0, 0, 0)) != KNOT_EOK) { + 0, 0, 0, 0)) != KNOT_EOK) { diag("Could not add rrset to packet!" " %s\n", knot_strerror(ret)); /* No point in continuing. */ diff --git a/src/zcompile/parser-util.c b/src/zcompile/parser-util.c index e7733ef..9e2e999 100644 --- a/src/zcompile/parser-util.c +++ b/src/zcompile/parser-util.c @@ -1463,14 +1463,16 @@ uint16_t * zparser_conv_services(const char *protostr, char *servicestr) char *sp = 0; while ((word = strtok_r(servicestr, sep, &sp))) { - struct servent *service; + struct servent *service = NULL; int port; service = getservbyname(word, proto->p_name); if (service) { /* Note: ntohs not ntohl! Strange but true. */ port = ntohs((uint16_t) service->s_port); +// printf("assigned port %d\n", port); } else { +// printf("else\n"); char *end; port = strtol(word, &end, 10); if (*end != '\0') { @@ -1479,7 +1481,7 @@ uint16_t * zparser_conv_services(const char *protostr, char *servicestr) " protocol '%s'", word, protostr); parser->error_occurred = KNOTDZCOMPILE_EBRDATA; - continue; + return NULL; } } @@ -1491,6 +1493,7 @@ uint16_t * zparser_conv_services(const char *protostr, char *servicestr) max_port = port; } } + servicestr = NULL; } r = alloc_rdata(sizeof(uint8_t) + max_port / 8 + 1); @@ -1502,7 +1505,7 @@ uint16_t * zparser_conv_services(const char *protostr, char *servicestr) p = (uint8_t *)(r + 1); *p = proto->p_proto; - memcpy(p + 1, bitmap, *r); + memcpy(p + 1, bitmap, *r - 1); return r; } @@ -2334,6 +2337,10 @@ void zadd_rdata_wireformat(uint16_t *data) */ void zadd_rdata_txt_wireformat(uint16_t *data, int first) { + if (data == NULL) { + parser->error_occurred = KNOTDZCOMPILE_EBRDATA; + return; + } dbg_zp("Adding text!\n"); // hex_print(data + 1, data[0]); knot_rdata_item_t *rd; @@ -2358,6 +2365,10 @@ void zadd_rdata_txt_wireformat(uint16_t *data, int first) rd = &parser->temporary_items[parser->rdata_count-1]; } + if (rd == NULL || rd->raw_data == NULL) { + return; + } + if ((size_t)rd->raw_data[0] + (size_t)data[0] > 65535) { zc_error_prev_line("too large rdata element"); return; diff --git a/src/zcompile/zcompile.c b/src/zcompile/zcompile.c index ec3cbe2..7038cd4 100644 --- a/src/zcompile/zcompile.c +++ b/src/zcompile/zcompile.c @@ -626,9 +626,6 @@ int zone_read(const char *name, const char *zonefile, const char *outfile, dbg_zp("zone dumped.\n"); } - /* This is *almost* unnecessary */ - knot_zone_deep_free(&(parser->current_zone), 1); - fflush(stdout); totalerrors += parser->errors; zparser_free(); diff --git a/src/zcompile/zparser.y b/src/zcompile/zparser.y index 6f081e5..c43b968 100644 --- a/src/zcompile/zparser.y +++ b/src/zcompile/zparser.y @@ -270,7 +270,6 @@ line: NL // printf("Current rrset name: %p (%s)\n", parser->current_rrset->owner->name, // knot_dname_to_str(parser->current_rrset->owner)); -// getchar(); // knot_dname_release(parser->current_rrset->owner); @@ -329,7 +328,7 @@ rr: owner classttl type_and_rdata // printf("new owner assigned: %p\n", $1); parser->current_rrset->type = $3; } - ; + ; owner: dname sp { @@ -341,7 +340,7 @@ owner: dname sp // knot_dname_release(parser->prev_dname); } parser->prev_dname = $1;//knot_dname_deep_copy($1); -// knot_dname_retain(parser->prev_dname); + knot_dname_retain(parser->prev_dname); $$ = $1; } | PREV @@ -394,7 +393,6 @@ dname: abs_dname $$ = knot_dname_cat($1, parser->origin->owner); // printf("leak: %s\n", knot_dname_to_str($$)); -// getchar(); } } ; @@ -1335,6 +1333,7 @@ rdata_rrsig: STR sp STR sp STR sp STR sp STR sp STR $15.len));*/ knot_dname_t *dname = knot_dname_new_from_wire((uint8_t *)$15.str, $15.len, NULL); + knot_dname_retain(dname); if (dname == NULL) { parser->error_occurred = KNOTDZCOMPILE_ENOMEM; } else { @@ -1365,7 +1364,7 @@ rdata_nsec: wire_dname nsec_seq knot_dname_t *dname = knot_dname_new_from_wire((uint8_t *)$1.str, $1.len, NULL); - + knot_dname_retain(dname); free($1.str); knot_dname_cat(dname, parser->root_domain); @@ -1458,8 +1457,8 @@ rdata_ipsec_base: STR sp STR sp STR sp dotted_str if(strlen($7.str) == 0) zc_error_prev_line("IPSECKEY must specify" "gateway name"); - name = knot_dname_new_from_wire((uint8_t*)$7.str + 1, - strlen($7.str + 1), + name = knot_dname_new_from_str($7.str, + strlen($7.str), NULL); if(!name) { zc_error_prev_line("IPSECKEY bad gateway" @@ -1470,21 +1469,15 @@ rdata_ipsec_base: STR sp STR sp STR sp dotted_str 1); YYABORT; } - if($7.str[strlen($7.str)-1] != '.') { - knot_dname_t* tmpd = - knot_dname_new_from_wire(name->name, - name->size, - NULL); - if (tmpd == NULL) { - zc_error_prev_line("Could not create dname!"); - knot_rrset_deep_free(&(parser->current_rrset), - 0, 0, 0); - knot_zone_deep_free(&(parser->current_zone), - 1); + + if(!knot_dname_is_fqdn(name)) { + assert(parser->origin); + name = knot_dname_cat(name, + parser->origin->owner); + if (name == NULL) { + zc_error_prev_line("Cannot concatenete dnames, probably run out of memory!\n"); YYABORT; } - name = knot_dname_cat(tmpd, - knot_node_parent(parser->origin, 0)->owner); } free($1.str); @@ -1492,7 +1485,8 @@ rdata_ipsec_base: STR sp STR sp STR sp dotted_str free($5.str); free($7.str); - uint8_t* dncpy = malloc(sizeof(uint8_t) * name->size); + uint16_t* dncpy = malloc(sizeof(uint8_t) * name->size + 2); + dncpy[0] = name->size; if (dncpy == NULL) { ERR_ALLOC_FAILED; knot_rrset_deep_free(&(parser->current_rrset), @@ -1501,9 +1495,10 @@ rdata_ipsec_base: STR sp STR sp STR sp dotted_str 1); YYABORT; } - memcpy(dncpy, name->name, name->size); - zadd_rdata_wireformat((uint16_t *)dncpy); - //knot_dname_free(&name); + + memcpy((uint8_t *)(dncpy + 1), name->name, name->size); + zadd_rdata_wireformat(dncpy); + knot_dname_free(&name); break; default: zc_error_prev_line("unknown IPSECKEY gateway type"); @@ -1581,6 +1576,7 @@ zparser_type *zparser_create() return NULL; } + knot_dname_retain(result->root_domain); return result; } |