1 /* -*- Mode: c; c-basic-offset: 2 -*-
2 *
3 * rasqal_random.c - Rasqal RDF Query random functions
4 *
5 * Copyright (C) 2011, David Beckett http://www.dajobe.org/
6 *
7 * This package is Free Software and part of Redland http://librdf.org/
8 *
9 * It is licensed under the following three licenses as alternatives:
10 * 1. GNU Lesser General Public License (LGPL) V2.1 or any newer version
11 * 2. GNU General Public License (GPL) V2 or any newer version
12 * 3. Apache License, V2.0 or any newer version
13 *
14 * You may not use this file except in compliance with at least one of
15 * the above three licenses.
16 *
17 * See LICENSE.html or LICENSE.txt at the top of this package for the
18 * complete terms and further detail along with the license texts for
19 * the licenses in COPYING.LIB, COPYING and LICENSE-2.0.txt respectively.
20 *
21 *
22 */
23
24 #ifdef HAVE_CONFIG_H
25 #include <rasqal_config.h>
26 #endif
27
28 #ifdef WIN32
29 #include <win32_rasqal_config.h>
30 #endif
31
32 #ifdef HAVE_STDLIB_H
33 #include <stdlib.h>
34 #endif
35 #ifdef HAVE_STDINT_H
36 #include <stdint.h>
37 #endif
38 #ifdef HAVE_UNISTD_H
39 #include <unistd.h>
40 #endif
41 #ifdef HAVE_SYS_TIME_H
42 #include <sys/time.h>
43 #endif
44 #ifdef HAVE_TIME_H
45 #include <time.h>
46 #endif
47 #ifdef RANDOM_ALGO_GMP_RAND
48 #ifdef HAVE_GMP_H
49 #include <gmp.h>
50 #endif
51 #define RANDOM_ALGO_BITS 32
52 #endif
53 #ifdef RANDOM_ALGO_MTWIST
54 #include <mtwist_config.h>
55 #include <mtwist.h>
56 #endif
57
58 #include "rasqal.h"
59 #include "rasqal_internal.h"
60
61
62 #ifndef STANDALONE
63 /*
64 * rasqal_random_get_system_seed
65 * @random_object: evaluation context
66 *
67 * INTERNAL - get a 32 bit unsigned integer random seed based on system sources
68 *
69 * Return value: seed with only lower 32 bits valid
70 */
71 unsigned int
rasqal_random_get_system_seed(rasqal_world * world)72 rasqal_random_get_system_seed(rasqal_world *world)
73 {
74 /* SOURCE 1: processor clock ticks since process started */
75 uint32_t a = (uint32_t)clock();
76 /* SOURCE 2: unix time in seconds since epoch */
77 uint32_t b = (uint32_t)time(NULL);
78 uint32_t c;
79 #ifdef HAVE_UNISTD_H
80 /* SOURCE 3: process ID (on unix) */
81 c = RASQAL_GOOD_CAST(uint32_t, getpid());
82 #else
83 c = 0;
84 #endif
85
86 /* Mix seed sources using public domain code from
87 * http://www.burtleburtle.net/bob/c/lookup3.c
88 */
89
90 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
91
92 /* inlined mix(a, b, c) macro */
93 a -= c; a ^= rot(c, 4); c += b;
94 b -= a; b ^= rot(a, 6); a += c;
95 c -= b; c ^= rot(b, 8); b += a;
96 a -= c; a ^= rot(c,16); c += b;
97 b -= a; b ^= rot(a,19); /* a += c; */ /* CLANG: not needed because of below */
98 c -= b; c ^= rot(b, 4); /* b += a; */ /* CLANG: last calculation not needed */
99
100 /* Good as long as sizeof(unsigned int) >= sizeof(uint32_t) */
101 return RASQAL_GOOD_CAST(unsigned int, c);
102 }
103
104
105 /*
106 * rasqal_new_random:
107 * @world: world object
108 *
109 * INTERNAL - Constructor - create a new random number generator
110 *
111 * Return value: new rasqal_random or NULL on failure
112 */
113 rasqal_random*
rasqal_new_random(rasqal_world * world)114 rasqal_new_random(rasqal_world* world)
115 {
116 rasqal_random* r;
117
118 r = RASQAL_CALLOC(rasqal_random*, 1, sizeof(*r));
119 if(!r)
120 return NULL;
121
122 r->world = world;
123 #ifdef RANDOM_ALGO_RANDOM_R
124 r->data = RASQAL_CALLOC(struct random_data*,
125 1, sizeof(struct random_data));
126 if(!r->data) {
127 RASQAL_FREE(rasqal_random*, r);
128 return NULL;
129 }
130 #endif
131
132 #ifdef RANDOM_ALGO_GMP_RAND
133 r->data = RASQAL_CALLOC(gmp_randstate_t*, 1, sizeof(gmp_randstate_t));
134 gmp_randinit_default(*(gmp_randstate_t*)r->data);
135 #endif
136
137 #ifdef RANDOM_ALGO_MTWIST
138 r->data = mtwist_new();
139 #endif
140
141 if(r)
142 rasqal_random_seed(r, rasqal_random_get_system_seed(r->world));
143
144 return r;
145 }
146
147
148 /*
149 * rasqal_free_random:
150 * @random_object: evaluation context
151 *
152 * INTERNAL - Destructor - Destroy a random number generator
153 */
154 void
rasqal_free_random(rasqal_random * random_object)155 rasqal_free_random(rasqal_random *random_object)
156 {
157 #ifdef RANDOM_ALGO_RANDOM_R
158 if(random_object->data)
159 RASQAL_FREE(struct random_data*, random_object->data);
160 #endif
161
162 #ifdef RANDOM_ALGO_RANDOM
163 if(random_object->data)
164 setstate(RASQAL_GOOD_CAST(char*, random_object->data));
165 #endif
166
167 #ifdef RANDOM_ALGO_GMP_RAND
168 if(random_object->data)
169 RASQAL_FREE(gmp_randstate_t*, random_object->data);
170 #endif
171
172 #ifdef RANDOM_ALGO_MTWIST
173 mtwist_free((mtwist*)random_object->data);
174 #endif
175
176 RASQAL_FREE(rasqsal_random*, random_object);
177 }
178
179
180 /*
181 * rasqal_random_seed:
182 * @random_object: evaluation context
183 * @seed: 32 bits of seed
184 *
185 * INTERNAL - Initialize the random number generator with a seed
186 *
187 * Return value: non-0 on failure
188 */
189 int
rasqal_random_seed(rasqal_random * random_object,unsigned int seed)190 rasqal_random_seed(rasqal_random *random_object, unsigned int seed)
191 {
192 int rc = 0;
193
194 #ifdef RANDOM_ALGO_RANDOM_R
195 rc = initstate_r(seed, random_object->state, RASQAL_RANDOM_STATE_SIZE,
196 (struct random_data*)random_object->data);
197 #endif
198
199 #ifdef RANDOM_ALGO_RANDOM
200 random_object->data = (void*)initstate(seed,
201 random_object->state,
202 RASQAL_RANDOM_STATE_SIZE);
203 #endif
204
205 #ifdef RANDOM_ALGO_RAND_R
206 random_object->seed = seed;
207 #endif
208
209 #ifdef RANDOM_ALGO_RAND
210 srand(seed);
211 #endif
212
213 #ifdef RANDOM_ALGO_GMP_RAND
214 gmp_randseed_ui(*(gmp_randstate_t*)random_object->data, (unsigned long)seed);
215 #endif
216
217 #ifdef RANDOM_ALGO_MTWIST
218 mtwist_init((mtwist*)random_object->data, (unsigned long)seed);
219 #endif
220
221 return rc;
222 }
223
224
225 /*
226 * rasqal_random_irand:
227 * @random_object: evaluation context
228 *
229 * INTERNAL - Get a random int from the random number generator
230 *
231 * Return value: random integer in the range 0 to RAND_MAX inclusive; [0, RAND_MAX]
232 */
233 int
rasqal_random_irand(rasqal_random * random_object)234 rasqal_random_irand(rasqal_random *random_object)
235 {
236 int r;
237 #ifdef RANDOM_ALGO_RANDOM_R
238 int32_t result;
239 #endif
240 #ifdef RANDOM_ALGO_RANDOM
241 char *old_state;
242 #endif
243 #ifdef RANDOM_ALGO_GMP_RAND
244 mpz_t rand_max_gmp;
245 mpz_t iresult;
246 #endif
247
248 /* results of all these functions is an integer or long in the
249 * range 0...RAND_MAX inclusive
250 */
251
252 #ifdef RANDOM_ALGO_RANDOM_R
253 result = 0;
254 random_r((struct random_data*)random_object->data, &result);
255 /* Good if int is 32 bits or larger */
256 r = RASQAL_GOOD_CAST(int, result);
257 #endif
258
259 #ifdef RANDOM_ALGO_RANDOM
260 old_state = setstate(random_object->state);
261 r = RASQAL_GOOD_CAST(int, random());
262 setstate(old_state);
263 #endif
264
265 #ifdef RANDOM_ALGO_RAND_R
266 r = rand_r(&random_object->seed);
267 #endif
268
269 #ifdef RANDOM_ALGO_RAND
270 r = rand();
271 #endif
272
273 #ifdef RANDOM_ALGO_GMP_RAND
274 /* This could be init/cleared once in random state */
275 mpz_init_set_ui(rand_max_gmp, 1 + (unsigned long)RAND_MAX);
276
277 mpz_init(iresult);
278 mpz_urandomm(iresult, *(gmp_randstate_t*)random_object->data, rand_max_gmp);
279 /* cast from unsigned long to unsigned int; we know above that the max
280 * size is RAND_MAX so it will fit
281 */
282 r = RASQAL_GOOD_CAST(unsigned int, mpz_get_ui(iresult));
283 mpz_clear(iresult);
284
285 mpz_clear(rand_max_gmp);
286 #endif
287
288 #ifdef RANDOM_ALGO_MTWIST
289 /* cast from unsigned long to int but max size is RAND_MAX
290 * so it will fit
291 */
292 r = RASQAL_GOOD_CAST(int, mtwist_u32rand((mtwist*)random_object->data));
293 #endif
294
295 return r;
296 }
297
298
299 /*
300 * rasqal_random_drand:
301 * @random_object: evaluation context
302 *
303 * INTERNAL - Get a random double from the random number generator
304 *
305 * Return value: random double in the range 0.0 inclusive to 1.0 exclusive; [0.0, 1.0)
306 */
307 double
rasqal_random_drand(rasqal_random * random_object)308 rasqal_random_drand(rasqal_random *random_object)
309 {
310 #ifdef RANDOM_ALGO_GMP_RAND
311 mpf_t fresult;
312 #else
313 #ifdef RANDOM_ALGO_MTWIST
314 #else
315 int r;
316 #endif
317 #endif
318 double d;
319
320 #ifdef RANDOM_ALGO_GMP_RAND
321 mpf_init(fresult);
322 mpf_urandomb(fresult, *(gmp_randstate_t*)random_object->data,
323 RANDOM_ALGO_BITS);
324 d = mpf_get_d(fresult);
325 mpf_clear(fresult);
326 #else
327 #ifdef RANDOM_ALGO_MTWIST
328 d = mtwist_drand((mtwist*)random_object->data);
329 #else
330 r = rasqal_random_irand(random_object);
331 d = r / (double)(RAND_MAX + 1.0);
332 #endif
333 #endif
334
335 return d;
336 }
337
338
339 #endif /* not STANDALONE */
340
341
342 #ifdef STANDALONE
343 #include <stdio.h>
344
345 int main(int argc, char *argv[]);
346
347
348 #define NTESTS 20
349
350 int
main(int argc,char * argv[])351 main(int argc, char *argv[])
352 {
353 rasqal_world* world;
354 const char *program = rasqal_basename(argv[0]);
355 int failures = 0;
356 rasqal_random* r = NULL;
357 int test;
358
359 world = rasqal_new_world();
360 if(!world || rasqal_world_open(world)) {
361 fprintf(stderr, "%s: rasqal_world init failed\n", program);
362 failures++;
363 goto tidy;
364 }
365
366 r = rasqal_new_random(world);
367 if(!r) {
368 fprintf(stderr, "%s: rasqal_new_random() failed\n", program);
369 failures++;
370 goto tidy;
371 }
372
373 rasqal_random_seed(r, 54321);
374
375 for(test = 0; test < NTESTS; test++) {
376 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
377 int v;
378
379 v = rasqal_random_irand(r);
380 fprintf(stderr, "%s: Test %3d value: %10d\n", program, test, v);
381 #else
382 (void)rasqal_random_irand(r);
383 #endif
384 }
385
386 for(test = 0; test < NTESTS; test++) {
387 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
388 double d;
389
390 d = rasqal_random_drand(r);
391 fprintf(stderr, "%s: Test %3d value: %10f\n", program, test, d);
392 #else
393 (void)rasqal_random_drand(r);
394 #endif
395 }
396
397 tidy:
398 if(r)
399 rasqal_free_random(r);
400
401 rasqal_free_world(world);
402
403 return failures;
404 }
405 #endif /* STANDALONE */
406