mtwist.c

symbian下ffmpeg编程。。废了好大劲下下来的！。

#ifndef lint
static char Rcs_Id[] =
    "$Id: mtwist.c,v 1.19 2003/09/11 05:55:19 geoff Exp $";
#endif

/*
 * C library functions for generating pseudorandom numbers using the
 * Mersenne Twist algorithm.  See M. Matsumoto and T. Nishimura,
 * "Mersenne Twister: A 623-Dimensionally Equidistributed Uniform
 * Pseudo-Random Number Generator", ACM Transactions on Modeling and
 * Computer Simulation, Vol. 8, No. 1, January 1998, pp 3--30.
 *
 * The Web page on the Mersenne Twist algorithm is at:
 *
 * http://www.math.keio.ac.jp/~matumoto/emt.html
 *
 * These functions were written by Geoffrey H. Kuenning, Claremont, CA.
 *
 * IMPORTANT NOTE: the Makefile must define two machine-specific
 * variables to get optimum features and performance:
 *
 *	MT_NO_INLINE	should be defined if the compiler doesn't support
 *			the "inline" keyword.
 *	MT_NO_LONGLONG	should be defined if the compiler doesn't support a
 *			"long long" type for 64-bit integers
 *	MT_MACHINE_BITS	must be either 32 or 64, reflecting the natural
 *			size of the processor registers.  If undefined, it
 *			will default to 32.
 *
 * The first two variables above are defined in an inverted sense
 * because I expect that most compilers will support inline and
 * long-long.  By inverting the sense, this common case will require
 * no special compiler flags.
 *
 * IMPORTANT NOTE: this software assumes that the inherent width of a
 * "long" is 32 bits.  If you are running on a machine that uses
 * 64-bit longs, some of the declarations and code will have to be
 * modified.
 *
 * This software is based on LGPL-ed code by Takuji Nishimura.  It has
 * also been heavily influenced by code written by Shawn Cokus, and
 * somewhat influenced by code written by Richard J. Wagner.  It is
 * therefore also distributed under the LGPL:
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public License
 * as published by the Free Software Foundation; either version 2 of
 * the License, or (at your option) any later version.
 *
 * This library 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
 * Library General Public License for more details.  You should have
 * received a copy of the GNU Library General Public License along
 * with this library; if not, write to the Free Foundation, Inc., 59
 * Temple Place, Suite 330, Boston, MA 02111-1307 USA
 *
 * $Log: mtwist.c,v $
 * Revision 1.19  2003/09/11 05:55:19  geoff
 * Get rid of some minor compiler warnings.
 *
 * Revision 1.18  2003/09/11 05:50:53  geoff
 * Don't #define inline to nothing, since that breaks standard include
 * files.  Instead, use MT_INLINE as a synonym.
 *
 * Revision 1.17  2002/10/31 22:07:10  geoff
 * Make WIN32 detection work with GCC as well as MS C
 *
 * Revision 1.16  2002/10/31 22:04:59  geoff
 * Fix a typo in the WIN32 option
 *
 * Revision 1.15  2002/10/31 06:01:43  geoff
 * Incorporate Joseph Brill's Windows-portability changes
 *
 * Revision 1.14  2002/10/30 07:39:53  geoff
 * Reintroduce the old seeding functions (so that old code will still
 * produce the same results), and give the new versions new names.
 *
 * Revision 1.13  2002/10/30 01:08:26  geoff
 * Switch to M&T's new initialization method
 *
 * Revision 1.12  2001/06/18 05:40:12  geoff
 * Prefix the compile options with MT_.
 *
 * Revision 1.11  2001/06/14 10:26:59  geoff
 * Invert the sense of the #define flags so that the default is the
 * normal case (if gcc is normal!).  Also default MT_MACHINE_BITS to 32.
 *
 * Revision 1.10  2001/06/14 10:10:38  geoff
 * Move the RNG functions into the header file so they can be inlined.
 * Add saving/loading of state.  Add a function that marks the PRNG as
 * initialized while also calculating critical constants.  Run the
 * refresh routine whenever seed32 is called.  Add functions to seed
 * based on /dev/random or the time.
 *
 * Revision 1.9  2001/06/11 10:00:04  geoff
 * Major changes to improve flexibility and performance, and to prepare
 * for inlining.  This code is about as fast as it can get without
 * inlining the various PRNG functions.  Add seed/goodseed/bestseed for
 * seeding from random start values.  Add the refresh routine a la Cokus,
 * but optimize it by unrolling loops.  Change getstate to return a
 * complete state pointer, since knowing the position in the state vector
 * is critical to restoring state.  Add more macros to improve
 * readability.  Rename certain macros in preparation for inlining.  Get
 * rid of leftover optimizer-bug stuff.  Stop using mtwist_guts.h;
 * instead use direct code (via macros) and the refresh function.
 *
 * Revision 1.8  2001/04/23 08:36:03  geoff
 * Move the #defined code into a header file to ease stepping with a debugger.
 *
 * Revision 1.7  2001/04/23 08:00:13  geoff
 * Add code to work around optimizer bug
 *
 * Revision 1.6  2001/04/14 01:33:32  geoff
 * Clarify the license
 *
 * Revision 1.5  2001/04/09 08:45:00  geoff
 * Rename default_state to mt_default_state, and make it global so that
 * the random-distribution code can use it.
 *
 * Revision 1.4  2001/04/07 23:24:11  geoff
 * My guess in the commentary for the last delta was right: it's faster
 * on a x86 to convert the two halves of the PRN to double, multiplying
 * them by the appropriate value to scale them, and then add them as
 * doubles.  I suspect the reason is that there is no instruction to
 * convert a 64-bit value directly to a double, so the work of building
 * the long long (which isn't easy anyway, without assembly access) is
 * worse than wasted.  So add support for MT_MACHINE_BITS, and only go
 * the via-long-long route on a true 64-bit machine.
 *
 * Revision 1.3  2001/04/07 23:09:38  geoff
 * Get rid of MT_INLINE.  Convert all of the code to use preprocessor
 * macros for the guts of the PRNG code.  Take advantage of the
 * conversion to get rid of unnecessary calls initialization tests.  Also
 * clean up the generation of long-double pseudorandom numbers on
 * machines that have the long long type (by converting first to a long
 * long, then to a double, saving one floating-point operation).  The
 * latter change might be a mistake on 32-bit machines.  The code is now
 * much faster as a result of macro-izing.
 *
 * Revision 1.2  2001/04/07 22:21:41  geoff
 * Make the long-double code a hair faster by always having a 64-bit
 * conversion constant.  Add commentary to the PRNG loop.
 *
 * Revision 1.1  2001/04/07 09:43:41  geoff
 * Initial revision
 *
 */

#ifdef _WIN32
#undef WIN32
#define WIN32
#endif /* _WIN32 */

#include <stdio.h>
#include <stdlib.h>
#ifdef WIN32
#include <sys/timeb.h>
#else /* WIN32 */
#include <sys/time.h>
#endif /* WIN32 */

/*
 * Before we include the Mersenne Twist header file, we must do a bit
 * of magic setup.  The code for actual random-number generation
 * resides in that file rather than here.  We need to arrange for the
 * code to be compiled into this .o file, either because inlines
 * aren't supported or because somebody might want to take a pointer
 * to a function.  We do so with a couple of careful #defines.
 */
#undef MT_NO_INLINE			/* Ask for code to be compiled */
#define MT_INLINE			/* Disable the inline keyword */
#define MT_EXTERN			/* Generate real code for functions */

#include "mtwist.h"

/*
 * Table of contents:
 */
void			mts_mark_initialized(mt_state* state);
					/* Mark a PRNG state as initialized */
void			mts_seed32(mt_state* state, unsigned long seed);
					/* Set random seed for any generator */
void			mts_seed32new(mt_state* state, unsigned long seed);
					/* Set random seed for any generator */
void			mts_seedfull(mt_state* state,
			  unsigned long seeds[MT_STATE_SIZE]);
					/* Set complicated seed for any gen. */
void			mts_seed(mt_state* state);
					/* Choose seed from random input */
void			mts_goodseed(mt_state* state);
					/* Choose seed from more random */
					/* ..input than mts_seed */
static void		mts_devseed(mt_state* state, char* seed_dev);
					/* Choose seed from a device */
void			mts_bestseed(mt_state* state);
					/* Choose seed from extremely random */
					/* ..input (can be *very* slow) */
void			mts_refresh(mt_state* state);
					/* Generate 624 more random values */
int			mts_savestate(FILE* statefile, mt_state* state);
					/* Save state to a file (ASCII) */
int			mts_loadstate(FILE* statefile, mt_state* state);
					/* Load state from a file (ASCII) */

void			mt_seed32(unsigned long seed);
					/* Set random seed for default gen. */
void			mt_seed32new(unsigned long seed);
					/* Set random seed for default gen. */
void			mt_seedfull(unsigned long seeds[MT_STATE_SIZE]);
					/* Set complicated seed for default */
void			mt_seed(void);	/* Choose seed from random input */
void			mt_goodseed(void);
					/* Choose seed from more random */
					/* ..input than mts_seed */
void			mt_bestseed(void);
					/* Choose seed from extremely random */
					/* ..input (can be *very* slow) */
extern mt_state*	mt_getstate(void);
					/* Get current state of default */
					/* ..generator */
int			mt_savestate(FILE* statefile);
					/* Save state to a file (ASCII) */
int			mt_loadstate(FILE* statefile);
					/* Load state from a file (ASCII) */


/*
 * The following values are fundamental parameters of the algorithm.
 * With the exception of the two masks, all of them were found
 * experimentally using methods described in Matsumoto and Nishimura's
 * paper.  They are exceedingly magic; don't change them.
 */

/* MT_STATE_SIZE is defined in the header file. */
#define RECURRENCE_OFFSET 397		/* Offset into state space for the */
					/* ..recurrence relation.  The */
					/* ..recurrence mashes together two */
					/* ..values that are separated by */
					/* ..this offset in the state */
					/* ..space. */
#define MATRIX_A	0x9908b0df	/* Constant vector A for the */
					/* ..recurrence relation.  The */
					/* ..mashed-together value is */
					/* ..multiplied by this vector to */
					/* ..get a new value that will be */
					/* ..stored into the state space. */

/*
 * Width of a long.  Don't change this even if your longs are 64 bits.
 */
#define BIT_WIDTH	32		/* Work with 32-bit words */

/*
 * Masks for extracting the bits to be mashed together.  The widths of these
 * masks are also fundamental parameters of the algorithm, determined
 * experimentally -- but of course the masks themselves are simply bit
 * selectors.
 */
#define UPPER_MASK	0x80000000	/* Most significant w-r bits */
#define LOWER_MASK	0x7fffffff	/* Least significant r bits */

/*
 * Macro to simplify code in the generation loop.  This function
 * combines the top bit of x with the bottom 31 bits of y.
 */
#define COMBINE_BITS(x, y) \
			(((x) & UPPER_MASK) | ((y) & LOWER_MASK))

/*
 * Another generation-simplification macro.  This one does the magic
 * scrambling function.
 */
#define MATRIX_MULTIPLY(original, new) \
			((original) ^ ((new) >> 1) \
			  ^ matrix_decider[(new) & 0x1])

/*
 * Parameters of Knuth's PRNG (Line 25, Table 1, p. 102 of "The Art of
 * Computer Programming, Vol. 2, 2nd ed, 1981).
 */
#define KNUTH_MULTIPLIER_OLD \
			69069

/*
 * Parameters of Knuth's PRNG (p. 106 of "The Art of Computer
 * Programming, Vol. 2, 3rd ed).
 */
#define KNUTH_MULTIPLIER_NEW \
			1812433253ul
#define KNUTH_SHIFT	30		// Even on a 64-bit machine!

/*
 * Default 32-bit random seed if mts_seed32 wasn't called
 */
#define DEFAULT_SEED32_OLD \
			4357
#define DEFAULT_SEED32_NEW \
			5489ul

/*
 * Where to get random numbers
 */
#define DEVRANDOM	"/dev/random"
#define DEVURANDOM	"/dev/urandom"

/*
 * Many applications need only a single PRNG, so it's a nuisance to have to
 * specify a state.  For those applications, we will provide a default
 * state, and functions to use it.
 */
mt_state		mt_default_state;

/*
 * To generate double-precision random numbers, we need to divide the result
 * of mts_lrand or mts_llrand by 2^32 or 2^64, respectively.  The quickest
 * way to do that on most machines is to multiply by the inverses of those
 * numbers.  However, I don't trust the compiler to correctly convert the