1/* 2 * Mersenne Twister PRNG algorithm 3 * Copyright (c) 2006 Ryan Martell 4 * Based on a C program for MT19937, with initialization improved 2002/1/26. 5 * Coded by Takuji Nishimura and Makoto Matsumoto. 6 * 7 * This file is part of FFmpeg. 8 * 9 * FFmpeg is free software; you can redistribute it and/or 10 * modify it under the terms of the GNU Lesser General Public 11 * License as published by the Free Software Foundation; either 12 * version 2.1 of the License, or (at your option) any later version. 13 * 14 * FFmpeg is distributed in the hope that it will be useful, 15 * but WITHOUT ANY WARRANTY; without even the implied warranty of 16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 17 * Lesser General Public License for more details. 18 * 19 * You should have received a copy of the GNU Lesser General Public 20 * License along with FFmpeg; if not, write to the Free Software 21 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 22 */ 23 24 25/** 26 * See http://en.wikipedia.org/wiki/Mersenne_twister 27 * for an explanation of this algorithm. 28 */ 29#include <stdio.h> 30#include "random.h" 31 32 33/* period parameters */ 34#define M 397 35#define A 0x9908b0df /* constant vector a */ 36#define UPPER_MASK 0x80000000 /* most significant w-r bits */ 37#define LOWER_MASK 0x7fffffff /* least significant r bits */ 38 39/** Initializes mt[AV_RANDOM_N] with a seed. */ 40void av_random_init(AVRandomState *state, unsigned int seed) 41{ 42 int index; 43 44 /* 45 This differs from the Wikipedia article. Source is from the 46 Makoto Matsumoto and Takuji Nishimura code, with the following comment: 47 */ 48 /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */ 49 /* In the previous versions, MSBs of the seed affect */ 50 /* only MSBs of the array mt[]. */ 51 state->mt[0] = seed & 0xffffffff; 52 for (index = 1; index < AV_RANDOM_N; index++) { 53 unsigned int prev= state->mt[index - 1]; 54 state->mt[index] = (1812433253UL * (prev ^ (prev>>30)) + index) & 0xffffffff; 55 } 56 state->index= index; // Will cause it to generate untempered numbers in the first iteration. 57} 58 59#if LIBAVUTIL_VERSION_MAJOR < 50 60void av_init_random(unsigned int seed, AVRandomState *state) 61{ 62 av_random_init(state, seed); 63} 64#endif 65 66/** Generates AV_RANDOM_N words at one time (which will then be tempered later). 67 * av_random calls this; you shouldn't. */ 68void av_random_generate_untempered_numbers(AVRandomState *state) 69{ 70 int kk; 71 unsigned int y; 72 73 for (kk = 0; kk < AV_RANDOM_N - M; kk++) { 74 y = (state->mt[kk] & UPPER_MASK) | (state->mt[kk + 1] & LOWER_MASK); 75 state->mt[kk] = state->mt[kk + M] ^ (y >> 1) ^ ((y&1)*A); 76 } 77 for (; kk < AV_RANDOM_N - 1; kk++) { 78 y = (state->mt[kk] & UPPER_MASK) | (state->mt[kk + 1] & LOWER_MASK); 79 state->mt[kk] = state->mt[kk + (M - AV_RANDOM_N)] ^ (y >> 1) ^ ((y&1)*A); 80 } 81 y = (state->mt[AV_RANDOM_N - 1] & UPPER_MASK) | (state->mt[0] & LOWER_MASK); 82 state->mt[AV_RANDOM_N - 1] = state->mt[M - 1] ^ (y >> 1) ^ ((y&1)*A); 83 state->index = 0; 84} 85 86#ifdef TEST 87#include "common.h" 88#include "log.h" 89int main(void) 90{ 91 int x=0; 92 int i, j; 93 AVRandomState state; 94 95 av_random_init(&state, 0xdeadbeef); 96 for (j = 0; j < 10000; j++) { 97 START_TIMER 98 for (i = 0; i < 624; i++) { 99 x+= av_random(&state); 100 } 101 STOP_TIMER("624 calls of av_random"); 102 } 103 av_log(NULL, AV_LOG_ERROR, "final value:%X\n", x); 104 return 0; 105} 106#endif 107