annotate lfg.c @ 992:a13125b5be3a libavutil

bswap: change ME to NE in macro names Other parts of FFmpeg use NE (native endian) rather than ME (machine). This makes it consistent.
author mru
date Sat, 10 Jul 2010 22:09:01 +0000
parents 3d83c38f150e
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
533
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
1 /*
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
2 * Lagged Fibonacci PRNG
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
3 * Copyright (c) 2008 Michael Niedermayer
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
4 *
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
5 * This file is part of FFmpeg.
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
6 *
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
7 * FFmpeg is free software; you can redistribute it and/or
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
8 * modify it under the terms of the GNU Lesser General Public
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
9 * License as published by the Free Software Foundation; either
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
10 * version 2.1 of the License, or (at your option) any later version.
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
11 *
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
12 * FFmpeg is distributed in the hope that it will be useful,
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
15 * Lesser General Public License for more details.
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
16 *
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
17 * You should have received a copy of the GNU Lesser General Public
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
18 * License along with FFmpeg; if not, write to the Free Software
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
20 */
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
21
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
22 #include <inttypes.h>
990
3d83c38f150e lfg: add missing includes
mru
parents: 873
diff changeset
23 #include <limits.h>
3d83c38f150e lfg: add missing includes
mru
parents: 873
diff changeset
24 #include <math.h>
533
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
25 #include "lfg.h"
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
26 #include "md5.h"
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
27 #include "intreadwrite.h"
873
4d9ad0ed07d0 Replace many includes of libavutil/common.h with what is actually needed
mru
parents: 798
diff changeset
28 #include "attributes.h"
533
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
29
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
30 void av_cold av_lfg_init(AVLFG *c, unsigned int seed){
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
31 uint8_t tmp[16]={0};
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
32 int i;
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
33
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
34 for(i=8; i<64; i+=4){
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
35 AV_WL32(tmp, seed); tmp[4]=i;
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
36 av_md5_sum(tmp, tmp, 16);
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
37 c->state[i ]= AV_RL32(tmp);
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
38 c->state[i+1]= AV_RL32(tmp+4);
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
39 c->state[i+2]= AV_RL32(tmp+8);
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
40 c->state[i+3]= AV_RL32(tmp+12);
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
41 }
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
42 c->index=0;
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
43 }
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
44
798
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
45 void av_bmg_get(AVLFG *lfg, double out[2])
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
46 {
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
47 double x1, x2, w;
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
48
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
49 do {
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
50 x1 = 2.0/UINT_MAX*av_lfg_get(lfg) - 1.0;
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
51 x2 = 2.0/UINT_MAX*av_lfg_get(lfg) - 1.0;
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
52 w = x1*x1 + x2*x2;
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
53 } while (w >= 1.0);
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
54
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
55 w = sqrt((-2.0 * log(w)) / w);
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
56 out[0] = x1 * w;
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
57 out[1] = x2 * w;
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
58 }
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
59
533
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
60 #ifdef TEST
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
61 #include "log.h"
873
4d9ad0ed07d0 Replace many includes of libavutil/common.h with what is actually needed
mru
parents: 798
diff changeset
62 #include "timer.h"
533
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
63
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
64 int main(void)
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
65 {
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
66 int x=0;
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
67 int i, j;
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
68 AVLFG state;
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
69
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
70 av_lfg_init(&state, 0xdeadbeef);
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
71 for (j = 0; j < 10000; j++) {
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
72 START_TIMER
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
73 for (i = 0; i < 624; i++) {
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
74 // av_log(NULL,AV_LOG_ERROR, "%X\n", av_lfg_get(&state));
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
75 x+=av_lfg_get(&state);
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
76 }
702
ef2c3d23d344 Fix reference to av_random where av_lfg_get was meant.
diego
parents: 533
diff changeset
77 STOP_TIMER("624 calls of av_lfg_get");
533
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
78 }
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
79 av_log(NULL, AV_LOG_ERROR, "final value:%X\n", x);
798
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
80
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
81 /* BMG usage example */
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
82 {
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
83 double mean = 1000;
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
84 double stddev = 53;
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
85
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
86 av_lfg_init(&state, 42);
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
87
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
88 for (i = 0; i < 1000; i += 2) {
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
89 double bmg_out[2];
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
90 av_bmg_get(&state, bmg_out);
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
91 av_log(NULL, AV_LOG_INFO,
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
92 "%f\n%f\n",
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
93 bmg_out[0] * stddev + mean,
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
94 bmg_out[1] * stddev + mean);
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
95 }
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
96 }
41da9d9d39b7 Implement av_bmg_next(), a Box-Muller Gaussian random generator.
stefano
parents: 702
diff changeset
97
533
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
98 return 0;
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
99 }
02617c39b8ff Simple lagged fibonacci PRNG.
michael
parents:
diff changeset
100 #endif