Merge branch 'blender2.7'
[blender.git] / source / blender / blenlib / intern / rand.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
17  * All rights reserved.
18  */
19
20 /** \file \ingroup bli
21  */
22
23
24 #include <stdlib.h>
25 #include <string.h>
26 #include <math.h>
27 #include <time.h>
28
29 #include "MEM_guardedalloc.h"
30
31 #include "BLI_threads.h"
32 #include "BLI_rand.h"
33 #include "BLI_math.h"
34
35 /* defines BLI_INLINE */
36 #include "BLI_compiler_compat.h"
37
38 #include "BLI_sys_types.h"
39 #include "BLI_strict_flags.h"
40
41 #define MULTIPLIER  0x5DEECE66Dll
42 #define MASK        0x0000FFFFFFFFFFFFll
43 #define MASK_BYTES   2
44
45 #define ADDEND      0xB
46 #define LOWSEED     0x330E
47
48 extern unsigned char hash[];    // noise.c
49
50 /**
51  * Random Number Generator.
52  */
53 struct RNG {
54         uint64_t X;
55 };
56
57 RNG *BLI_rng_new(unsigned int seed)
58 {
59         RNG *rng = MEM_mallocN(sizeof(*rng), "rng");
60
61         BLI_rng_seed(rng, seed);
62
63         return rng;
64 }
65
66 /**
67  * A version of #BLI_rng_new that hashes the seed.
68  */
69 RNG *BLI_rng_new_srandom(unsigned int seed)
70 {
71         RNG *rng = MEM_mallocN(sizeof(*rng), "rng");
72
73         BLI_rng_srandom(rng, seed);
74
75         return rng;
76 }
77
78 void BLI_rng_free(RNG *rng)
79 {
80         MEM_freeN(rng);
81 }
82
83 void BLI_rng_seed(RNG *rng, unsigned int seed)
84 {
85         rng->X = (((uint64_t) seed) << 16) | LOWSEED;
86 }
87
88 /**
89  * Use a hash table to create better seed.
90  */
91 void BLI_rng_srandom(RNG *rng, unsigned int seed)
92 {
93         BLI_rng_seed(rng, seed + hash[seed & 255]);
94         seed = BLI_rng_get_uint(rng);
95         BLI_rng_seed(rng, seed + hash[seed & 255]);
96         seed = BLI_rng_get_uint(rng);
97         BLI_rng_seed(rng, seed + hash[seed & 255]);
98 }
99
100 BLI_INLINE void rng_step(RNG *rng)
101 {
102         rng->X = (MULTIPLIER * rng->X + ADDEND) & MASK;
103 }
104
105 void BLI_rng_get_char_n(RNG *rng, char *bytes, size_t bytes_len)
106 {
107         size_t last_len = 0;
108         size_t trim_len = bytes_len;
109
110 #define RAND_STRIDE (sizeof(rng->X) - MASK_BYTES)
111
112         if (trim_len > RAND_STRIDE) {
113                 last_len = trim_len % RAND_STRIDE;
114                 trim_len = trim_len - last_len;
115         }
116         else {
117                 trim_len = 0;
118                 last_len = bytes_len;
119         }
120
121         const char *data_src = (void *)&(rng->X);
122         size_t i = 0;
123         while (i != trim_len) {
124                 BLI_assert(i < trim_len);
125 #ifdef __BIG_ENDIAN__
126                 for (size_t j = (RAND_STRIDE + MASK_BYTES) - 1; j != MASK_BYTES - 1; j--)
127 #else
128                 for (size_t j = 0; j != RAND_STRIDE; j++)
129 #endif
130                 {
131                         bytes[i++] = data_src[j];
132                 }
133                 rng_step(rng);
134         }
135         if (last_len) {
136                 for (size_t j = 0; j != last_len; j++) {
137                         bytes[i++] = data_src[j];
138                 }
139         }
140
141 #undef RAND_STRIDE
142 }
143
144 int BLI_rng_get_int(RNG *rng)
145 {
146         rng_step(rng);
147         return (int) (rng->X >> 17);
148 }
149
150 unsigned int BLI_rng_get_uint(RNG *rng)
151 {
152         rng_step(rng);
153         return (unsigned int) (rng->X >> 17);
154 }
155
156 /**
157  * \return Random value (0..1), but never 1.0.
158  */
159 double BLI_rng_get_double(RNG *rng)
160 {
161         return (double) BLI_rng_get_int(rng) / 0x80000000;
162 }
163
164 /**
165  * \return Random value (0..1), but never 1.0.
166  */
167 float BLI_rng_get_float(RNG *rng)
168 {
169         return (float) BLI_rng_get_int(rng) / 0x80000000;
170 }
171
172 void BLI_rng_get_float_unit_v2(RNG *rng, float v[2])
173 {
174         float a = (float)(M_PI * 2.0) * BLI_rng_get_float(rng);
175         v[0] = cosf(a);
176         v[1] = sinf(a);
177 }
178
179 void BLI_rng_get_float_unit_v3(RNG *rng, float v[3])
180 {
181         float r;
182         v[2] = (2.0f * BLI_rng_get_float(rng)) - 1.0f;
183         if ((r = 1.0f - (v[2] * v[2])) > 0.0f) {
184                 float a = (float)(M_PI * 2.0) * BLI_rng_get_float(rng);
185                 r = sqrtf(r);
186                 v[0] = r * cosf(a);
187                 v[1] = r * sinf(a);
188         }
189         else {
190                 v[2] = 1.0f;
191         }
192 }
193
194 /**
195  * Generate a random point inside given tri.
196  */
197 void BLI_rng_get_tri_sample_float_v2(
198         RNG *rng, const float v1[2], const float v2[2], const float v3[2],
199         float r_pt[2])
200 {
201         float u = BLI_rng_get_float(rng);
202         float v = BLI_rng_get_float(rng);
203
204         float side_u[2], side_v[2];
205
206         if ((u + v) > 1.0f) {
207                 u = 1.0f - u;
208                 v = 1.0f - v;
209         }
210
211         sub_v2_v2v2(side_u, v2, v1);
212         sub_v2_v2v2(side_v, v3, v1);
213
214         copy_v2_v2(r_pt, v1);
215         madd_v2_v2fl(r_pt, side_u, u);
216         madd_v2_v2fl(r_pt, side_v, v);
217 }
218
219 void BLI_rng_shuffle_array(RNG *rng, void *data, unsigned int elem_size_i, unsigned int elem_tot)
220 {
221         const size_t elem_size = (size_t)elem_size_i;
222         unsigned int i = elem_tot;
223         void *temp;
224
225         if (elem_tot <= 1) {
226                 return;
227         }
228
229         temp = malloc(elem_size);
230
231         while (i--) {
232                 unsigned int j = BLI_rng_get_uint(rng) % elem_tot;
233                 if (i != j) {
234                         void *iElem = (unsigned char *)data + i * elem_size_i;
235                         void *jElem = (unsigned char *)data + j * elem_size_i;
236                         memcpy(temp, iElem, elem_size);
237                         memcpy(iElem, jElem, elem_size);
238                         memcpy(jElem, temp, elem_size);
239                 }
240         }
241
242         free(temp);
243 }
244
245 /**
246  * Simulate getting \a n random values.
247  *
248  * \note Useful when threaded code needs consistent values, independent of task division.
249  */
250 void BLI_rng_skip(RNG *rng, int n)
251 {
252         while (n--) {
253                 rng_step(rng);
254         }
255 }
256
257 /***/
258
259 /* fill an array with random numbers */
260 void BLI_array_frand(float *ar, int count, unsigned int seed)
261 {
262         RNG rng;
263
264         BLI_rng_srandom(&rng, seed);
265
266         for (int i = 0; i < count; i++) {
267                 ar[i] = BLI_rng_get_float(&rng);
268         }
269 }
270
271 float BLI_hash_frand(unsigned int seed)
272 {
273         RNG rng;
274
275         BLI_rng_srandom(&rng, seed);
276         return BLI_rng_get_float(&rng);
277 }
278
279 void BLI_array_randomize(void *data, unsigned int elem_size, unsigned int elem_tot, unsigned int seed)
280 {
281         RNG rng;
282
283         BLI_rng_seed(&rng, seed);
284         BLI_rng_shuffle_array(&rng, data, elem_size, elem_tot);
285 }
286
287 /* ********* for threaded random ************** */
288
289 static RNG rng_tab[BLENDER_MAX_THREADS];
290
291 void BLI_thread_srandom(int thread, unsigned int seed)
292 {
293         if (thread >= BLENDER_MAX_THREADS)
294                 thread = 0;
295
296         BLI_rng_seed(&rng_tab[thread], seed + hash[seed & 255]);
297         seed = BLI_rng_get_uint(&rng_tab[thread]);
298         BLI_rng_seed(&rng_tab[thread], seed + hash[seed & 255]);
299         seed = BLI_rng_get_uint(&rng_tab[thread]);
300         BLI_rng_seed(&rng_tab[thread], seed + hash[seed & 255]);
301 }
302
303 int BLI_thread_rand(int thread)
304 {
305         return BLI_rng_get_int(&rng_tab[thread]);
306 }
307
308 float BLI_thread_frand(int thread)
309 {
310         return BLI_rng_get_float(&rng_tab[thread]);
311 }
312
313 struct RNG_THREAD_ARRAY {
314         RNG rng_tab[BLENDER_MAX_THREADS];
315 };
316
317 RNG_THREAD_ARRAY *BLI_rng_threaded_new(void)
318 {
319         unsigned int i;
320         RNG_THREAD_ARRAY *rngarr = MEM_mallocN(sizeof(RNG_THREAD_ARRAY), "random_array");
321
322         for (i = 0; i < BLENDER_MAX_THREADS; i++) {
323                 BLI_rng_srandom(&rngarr->rng_tab[i], (unsigned int)clock());
324         }
325
326         return rngarr;
327 }
328
329 void BLI_rng_threaded_free(struct RNG_THREAD_ARRAY *rngarr)
330 {
331         MEM_freeN(rngarr);
332 }
333
334 int BLI_rng_thread_rand(RNG_THREAD_ARRAY *rngarr, int thread)
335 {
336         return BLI_rng_get_int(&rngarr->rng_tab[thread]);
337 }
338
339 /* ********* Low-discrepancy sequences ************** */
340
341 /* incremental halton sequence generator, from:
342  * "Instant Radiosity", Keller A. */
343 BLI_INLINE double halton_ex(double invprimes, double *offset)
344 {
345         double e = fabs((1.0 - *offset) - 1e-10);
346
347         if (invprimes >= e) {
348                 double lasth;
349                 double h = invprimes;
350
351                 do {
352                         lasth = h;
353                         h *= invprimes;
354                 } while (h >= e);
355
356                 *offset += ((lasth + h) - 1.0);
357         }
358         else {
359                 *offset += invprimes;
360         }
361
362         return *offset;
363 }
364
365 void BLI_halton_1D(unsigned int prime, double offset, int n, double *r)
366 {
367         const double invprime = 1.0 / (double)prime;
368
369         *r = 0.0;
370
371         for (int s = 0; s < n; s++) {
372                 *r = halton_ex(invprime, &offset);
373         }
374 }
375
376 void BLI_halton_2D(unsigned int prime[2], double offset[2], int n, double *r)
377 {
378         const double invprimes[2] = {1.0 / (double)prime[0], 1.0 / (double)prime[1]};
379
380         r[0] = r[1] = 0.0;
381
382         for (int s = 0; s < n; s++) {
383                 for (int i = 0; i < 2; i++) {
384                         r[i] = halton_ex(invprimes[i], &offset[i]);
385                 }
386         }
387 }
388
389 void BLI_halton_3D(unsigned int prime[3], double offset[3], int n, double *r)
390 {
391         const double invprimes[3] = {1.0 / (double)prime[0], 1.0 / (double)prime[1], 1.0 / (double)prime[2]};
392
393         r[0] = r[1] = r[2] = 0.0;
394
395         for (int s = 0; s < n; s++) {
396                 for (int i = 0; i < 3; i++) {
397                         r[i] = halton_ex(invprimes[i], &offset[i]);
398                 }
399         }
400 }
401
402 void BLI_halton_2D_sequence(unsigned int prime[2], double offset[2], int n, double *r)
403 {
404         const double invprimes[2] = {1.0 / (double)prime[0], 1.0 / (double)prime[1]};
405
406         for (int s = 0; s < n; s++) {
407                 for (int i = 0; i < 2; i++) {
408                         r[s * 2 + i] = halton_ex(invprimes[i], &offset[i]);
409                 }
410         }
411 }
412
413
414 /* From "Sampling with Hammersley and Halton Points" TT Wong
415  * Appendix: Source Code 1 */
416 BLI_INLINE double radical_inverse(unsigned int n)
417 {
418         double u = 0;
419
420         /* This reverse the bitwise representation
421          * around the decimal point. */
422         for (double p = 0.5; n; p *= 0.5, n >>= 1) {
423                 if (n & 1) {
424                         u += p;
425                 }
426         }
427
428         return u;
429 }
430
431 void BLI_hammersley_1D(unsigned int n, double *r)
432 {
433         *r = radical_inverse(n);
434 }
435
436 void BLI_hammersley_2D_sequence(unsigned int n, double *r)
437 {
438         for (unsigned int s = 0; s < n; s++) {
439                 r[s * 2 + 0] = (double)(s + 0.5) / (double)n;
440                 r[s * 2 + 1] = radical_inverse(s);
441         }
442 }