473,890 Members | 1,346 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

RFC: clc-compliant pseudo-random number generator

One issue that comes up fairly often around here is the poor
quality of the pseudo-random number generators supplied with many
C implementations . As a result, we have to recommend things like
using the high-order bits returned by rand() instead of the
low-order bits, avoiding using rand() for anything that wants
decently random numbers, not using rand() if you want more than
approx. UINT_MAX total different sequences, and so on.

So I wrote some PRNG code that uses RC4, with a seed of up to 256
bytes. Here it is. I believe it is clc-compliant. Comments on
this and anything else are welcome.

----------------------------------------------------------------------
/*
* prng.c - Portable, ISO C90 and C99 compliant high-quality
* pseudo-random number generator based on the alleged RC4
* cipher. This PRNG should be suitable for most general-purpose
* uses. Not recommended for cryptographic or financial
* purposes. Not thread-safe.
*/

/*
* Copyright (c) 2004 Ben Pfaff <bl*@cs.stanfor d.edu>.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or
* without modification, are permitted provided that the
* following conditions are met:
*
* 1. Redistributions of source code must retain the above
* copyright notice, this list of conditions and the following
* disclaimer.
*
* 2. Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials
* provided with the distribution.
*
* 3. The author's and contributors' names may not be used to
* endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS
* IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
* FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
* SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
* INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
* OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
* THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
* OF SUCH DAMAGE.
*
*/

#include "prng.h"
#include <assert.h>
#include <float.h>
#include <limits.h>
#include <math.h>
#include <time.h>

/* RC4-based pseudo-random state. */
static unsigned char s[256];
static int s_i, s_j;

/* Nonzero if PRNG has been seeded. */
static int seeded;

/* Take advantage of inlining if possible. */
#if __STDC_VERSION_ _ >= 199901L
#define INLINE inline
#else
#define INLINE
#endif

/* Swap bytes. */
static INLINE void
swap_byte (unsigned char *a, unsigned char *b)
{
unsigned char t = *a;
*a = *b;
*b = t;
}

/* If KEY is non-null and SIZE is nonzero, seeds the
pseudo-random number generator based on the SIZE bytes in BUF.
At most the first 256 bytes of BUF are used. If KEY is a null
pointer and SIZE is zero, seeds the pseudo-random number
generator based on the current time.

If this function is not called by the user before any prng_get
function, it is called automatically to obtain a time-based
seed. */
void
prng_seed (const void *key_, size_t size)
{
const unsigned char *key = key_;
size_t key_idx;
int i, j;

assert ((key != NULL && size > 0) || (key == NULL && size == 0));

if (key == NULL)
{
static time_t t;

t = (t == 0) ? time (NULL) : t + 1;
key = (void *) &t;
size = sizeof t;
}

for (i = 0; i < 256; i++)
s[i] = i;
for (key_idx = 0, i = j = 0; i < 256; i++)
{
j = (j + s[i] + key[key_idx]) & 255;
swap_byte (s + i, s + j);
if (++key_idx >= size)
key_idx = 0;
}

s_i = s_j = 0;
seeded = 1;
}

/* Returns a pseudo-random integer in the range [0,255]. */
unsigned char
prng_get_octet (void)
{
if (!seeded)
prng_seed (NULL, 0);

s_i = (s_i + 1) & 255;
s_j = (s_j + s[s_i]) & 255;
swap_byte (s + s_i, s + s_j);

return s[(s[s_i] + s[s_j]) & 255];
}

/* Returns a pseudo-random integer in the range [0,UCHAR_MAX]. */
unsigned char
prng_get_byte (void)
{
if (UCHAR_MAX == 255)
{
/* Normal case for 8-bit bytes. */
return prng_get_octet ();
}
else
{
/* Handle oversize bytes. */
unsigned byte = prng_get_octet ();
unsigned done = 255;
while ((unsigned char) done != UCHAR_MAX)
{
byte = (byte << 8) | prng_get_octet ();
done = (done << 8) | 255;
}
return byte;
}
}

/* Fills BUF with SIZE pseudo-random bytes. */
void
prng_get_bytes (void *buf_, size_t size)
{
unsigned char *buf;

for (buf = buf_; size-- > 0; buf++)
*buf = prng_get_byte ();
}

/* Returns a pseudo-random unsigned long in the range [0,
ULONG_MAX]. */
unsigned long
prng_get_ulong (void)
{
unsigned long ulng = prng_get_octet ();
unsigned long done = 255;

while (done != ULONG_MAX)
{
ulng = (ulng << 8) | prng_get_octet ();
done = (done << 8) | 255;
}

return ulng;
}

/* Returns a pseudo-random long in the range [0, LONG_MAX]. */
long
prng_get_long (void)
{
for (;;)
{
unsigned ulng = prng_get_ulong ();
if (ulng <= LONG_MAX)
return ulng;
}
}

/* Returns a pseudo-random unsigned int in the range [0,
UINT_MAX]. */
unsigned
prng_get_uint (void)
{
unsigned uint = prng_get_octet ();
unsigned done = 255;

while (done != UINT_MAX)
{
uint = (uint << 8) | prng_get_octet ();
done = (done << 8) | 255;
}

return uint;
}

/* Returns a pseudo-random int in the range [0, INT_MAX]. */
int
prng_get_int (void)
{
for (;;)
{
unsigned uint = prng_get_uint ();
if (uint <= INT_MAX)
return uint;
}
}

/* Returns a pseudo-random floating-point number from the uniform
distribution with range [0,1). */
double
prng_get_double (void)
{
for (;;)
{
unsigned long ulng = prng_get_ulong ();
if (ulng != ULONG_MAX)
return (double) ulng / ULONG_MAX;
}
}

/* Returns a pseudo-random floating-point number from the
distribution with mean 0 and standard deviation 1. (Multiply
the result by the desired standard deviation, then add the
desired mean.) */
double
prng_get_double _normal (void)
{
/* Knuth, _The Art of Computer Programming_, Vol. 2, 3.4.1C,
Algorithm P. */
static double next_normal = DBL_MAX;
double this_normal;

if (next_normal != DBL_MAX)
{
this_normal = next_normal;
next_normal = DBL_MAX;
}
else
{
double v1, v2, s;

do
{
double u1 = prng_get_double ();
double u2 = prng_get_double ();
v1 = 2.0 * u1 - 1.0;
v2 = 2.0 * u2 - 1.0;
s = v1 * v1 + v2 * v2;
}
while (s >= 1);

this_normal = v1 * sqrt (-2. * log (s) / s);
next_normal = v2 * sqrt (-2. * log (s) / s);
}

return this_normal;
}
----------------------------------------------------------------------
#ifndef PRNG_H_INCLUDED
#define PRNG_H_INCLUDED

#include <stddef.h>

void prng_seed (const void *, size_t);
unsigned char prng_get_octet (void);
unsigned char prng_get_byte (void);
void prng_get_bytes (void *, size_t);
unsigned long prng_get_ulong (void);
long prng_get_long (void);
unsigned prng_get_uint (void);
int prng_get_int (void);
double prng_get_double (void);
double prng_get_double _normal (void);

#endif /* prng.h */
----------------------------------------------------------------------
--
"There's only one thing that will make them stop hating you.
And that's being so good at what you do that they can't ignore you.
I told them you were the best. Now you damn well better be."
--Orson Scott Card, _Ender's Game_
Nov 14 '05
70 6321
In <87************ @pfaff.stanford .edu> Ben Pfaff <bl*@cs.stanfor d.edu> writes:
/* Take advantage of inlining if possible. */
#if __STDC_VERSION_ _ >= 199901L


Any use of __STDC_VERSION_ _ invokes undefined behaviour in a C90
implementation. Such an implementation can use it as a magic
identifier during preprocessing (e.g. the preprocessor's nasal demon
generator ;-) or simply define it as a macro with a value greater
than 199901L.

If you want clc-compliance, drop it.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 14 '05 #21
"E. Robert Tisdale" wrote:

Ben Pfaff wrote:
E. Robert Tisdale writes:
Why is your pseudo random number generator "better" than rand()?

Is it faster than rand()?

Have you run any performance benchmarks against rand()?

I forgot to mention in my original article that I don't feel
obligated to answer questions from wackos.


Your PRNG is a dog isn't it Ben?

My guess is that it's so slow that there are no practical uses for it.


If speed is the criterion of goodness for pseudo-
random number generators, this one should win:

#define RAND() 0

You might also be interested in my super-fast versions
of the trigonometric functions:

#define SIN(x) ( (x), 0 )
#define COS(x) ( (x), 0 )
...

.... and in my blindingly fast memory management implementation:

#define MALLOC(bytes) ( (bytes), 0 )
#define CALLOC(bytes) ( (bytes), 0 )
#define REALLOC(ptr,byt es) ( (ptr), (bytes), 0 )
#define FREE(ptr) (void)(ptr)

--
Er*********@sun .com
Nov 14 '05 #22
Eric Sosman <Er*********@su n.com> scribbled the following:
"E. Robert Tisdale" wrote:
Ben Pfaff wrote:
> E. Robert Tisdale writes:
>>Why is your pseudo random number generator "better" than rand()?
>>
>>Is it faster than rand()?
>>
>>Have you run any performance benchmarks against rand()?
>
> I forgot to mention in my original article that I don't feel
> obligated to answer questions from wackos.
Your PRNG is a dog isn't it Ben?

My guess is that it's so slow that there are no practical uses for it.

If speed is the criterion of goodness for pseudo-
random number generators, this one should win: #define RAND() 0 You might also be interested in my super-fast versions
of the trigonometric functions: #define SIN(x) ( (x), 0 )
#define COS(x) ( (x), 0 )
... ... and in my blindingly fast memory management implementation: #define MALLOC(bytes) ( (bytes), 0 )
#define CALLOC(bytes) ( (bytes), 0 )
This implementation might be blindingly fast, but it does not follow
the specification. It should be:

#define CALLOC(number, bytes) ( (number), (bytes), 0 )
#define REALLOC(ptr,byt es) ( (ptr), (bytes), 0 )
#define FREE(ptr) (void)(ptr)


--
/-- Joona Palaste (pa*****@cc.hel sinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"Hasta la Vista, Abie!"
- Bart Simpson
Nov 14 '05 #23
Joona I Palaste wrote:

Eric Sosman <Er*********@su n.com> scribbled the following:
... and in my blindingly fast memory management implementation:

#define MALLOC(bytes) ( (bytes), 0 )
#define CALLOC(bytes) ( (bytes), 0 )


This implementation might be blindingly fast, but it does not follow
the specification. It should be:

#define CALLOC(number, bytes) ( (number), (bytes), 0 )


Thanks for the correction; I'll issue a patch immediately.
Watch for the CERT advisory.

(Can you tell that I don't use calloc() much?)

--
Er*********@sun .com
Nov 14 '05 #24

In article <7f************ *************** *****@4ax.com>, Kevin D. Quitt <KQ**********@I EEIncUNMUNG.com > writes:
Without casting asparagus on your effort, a paper in my archive from an
unknown source:

Most RNGs work by keeping a certain number, say k, of the most recently
generated integers, then return the next integer as a function of those
k. ...


That's an article posted by George Marsaglia to comp.lang.c on 13 May 2003.
(I kept a copy of it as well; it's a nice piece.)

On 3 April 2003 George posted another article on CMWC (Complementary
Multiply with Carry) PRNGs which was also quite interesting.

--
Michael Wojcik mi************@ microfocus.com

A coding theorist is someone who doesn't think Alice is crazy. -- John Gordon
Nov 14 '05 #25
Dan Pop wrote:
In <87************ @pfaff.stanford .edu> Ben Pfaff <bl*@cs.stanfor d.edu> writes:
/* Take advantage of inlining if possible. */
#if __STDC_VERSION_ _ >= 199901L


Any use of __STDC_VERSION_ _ invokes undefined behaviour in a C90
implementation. (...) If you want clc-compliance, drop it.


In particular since it's only used for swap_byte(), which is
only used a few places that just as well can use

#define SWAP_BYTE(x, y) \
{ \
unsigned char tmp__SWAP_BYTE = (x); \
(x) = (y); \
(y) = tmp__SWAP_BYTE; \
}

(Yes, I know you could put do...while(0) around it so it will 'expect'
to be followed by a semicolon, but I think the while(0) gives a warning
with some compilers. There is no need to do that in this code.)

--
Hallvard
Nov 14 '05 #26
In message <bu**********@s unnews.cern.ch>
Da*****@cern.ch (Dan Pop) wrote:
In <87************ @pfaff.stanford .edu> Ben Pfaff <bl*@cs.stanfor d.edu> writes:
/* Take advantage of inlining if possible. */
#if __STDC_VERSION_ _ >= 199901L


Any use of __STDC_VERSION_ _ invokes undefined behaviour in a C90
implementation. Such an implementation can use it as a magic
identifier during preprocessing (e.g. the preprocessor's nasal demon
generator ;-) or simply define it as a macro with a value greater
than 199901L.


Ok, thanks for the DeathStation programming advice.

On a more practical note, what WOULD a reasonable value for a compiler in C90
mode to set __STDC_VERSION_ _ to, if it wanted to set it? (One reason for
wanting to set it might be to avoid warnings about it being an undefined
identifier treated as 0 in #if).

Presumably 1990xxL would make sense, but what is "xx"? Which month was C90
published (or reached whichever stage was equivalent to 199409/199901)? I
suppose 199000L would be safe whatever.

--
Kevin Bracey, Principal Software Engineer
Tematic Ltd Tel: +44 (0) 1223 503464
182-190 Newmarket Road Fax: +44 (0) 1223 503458
Cambridge, CB5 8HE, United Kingdom WWW: http://www.tematic.com/
Nov 14 '05 #27
Joona I Palaste <pa*****@cc.hel sinki.fi> writes:
Ben Pfaff <bl*@cs.stanfor d.edu> scribbled the following:
I'm intentionally not trying to make it cryptographical ly secure.
The goal is to be a better rand() for simulations etc., not to be
useful for cryptography. My comment at the top was intended to
say that, but perhaps it should be more prominent.


Why are you not trying to make it cryptographical ly secure? To avoid
it being classified as a weapon by the US army? =)


Because if I intend it to be cryptographical ly secure, then a bug
is an important security hole. If I don't, a bug just means that
the output is less random. I prefer to leave cryptography to the
cryptographers.
--
int main(void){char p[]="ABCDEFGHIJKLM NOPQRSTUVWXYZab cdefghijklmnopq rstuvwxyz.\
\n",*q="kl BIcNBFr.NKEzjwC IxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+= strchr(p,*q++)-p;if(i>=(int)si zeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}
Nov 14 '05 #28
Da*****@cern.ch (Dan Pop) writes:
In <87************ @pfaff.stanford .edu> Ben Pfaff <bl*@cs.stanfor d.edu> writes:
/* Take advantage of inlining if possible. */
#if __STDC_VERSION_ _ >= 199901L


Any use of __STDC_VERSION_ _ invokes undefined behaviour in a C90
implementation. Such an implementation can use it as a magic
identifier during preprocessing (e.g. the preprocessor's nasal demon
generator ;-) or simply define it as a macro with a value greater
than 199901L.


Only an actively malicious compiler would do so. I'm not too
interested in those.
--
"Given that computing power increases exponentially with time,
algorithms with exponential or better O-notations
are actually linear with a large constant."
--Mike Lee
Nov 14 '05 #29
Ben Pfaff <bl*@cs.stanfor d.edu> scribbled the following:
Joona I Palaste <pa*****@cc.hel sinki.fi> writes:
Ben Pfaff <bl*@cs.stanfor d.edu> scribbled the following:
I'm intentionally not trying to make it cryptographical ly secure.
The goal is to be a better rand() for simulations etc., not to be
useful for cryptography. My comment at the top was intended to
say that, but perhaps it should be more prominent.
Why are you not trying to make it cryptographical ly secure? To avoid
it being classified as a weapon by the US army? =)

Because if I intend it to be cryptographical ly secure, then a bug
is an important security hole. If I don't, a bug just means that
the output is less random. I prefer to leave cryptography to the
cryptographers.


So if it happens to be cryptographical ly secure anyway, good for it, but
you won't be losing sleep if it doesn't?

--
/-- Joona Palaste (pa*****@cc.hel sinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"This is a personnel commuter."
- Train driver in Scientific American
Nov 14 '05 #30

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

0
1817
by: C. Titus Brown | last post by:
Hi all, just spent some time playing with cookielib in Python 2.4, trying to get the cookielib example to work with my mailman admindb page. The problem was that cookies weren't getting saved. The issue turned out to be that mailman sends out RFC 2965 cookies, which are by default rejected by cookielib. I don't remotely pretend to understand the issues involved; hence my post ;).
1
3905
by: praba kar | last post by:
Dear All, In Php we can print RFC 2822 formatted date by date('r') with parameter r. Then it will print the below format date. "Thu, 7 Apr 2005 01:46:36 -0300". I want to print same RFC 2822 format in python. Is it possible in python? . If possible kindly mention the function related to print RFC format date
47
2718
by: Jeff Relf | last post by:
Hi All, I plan on using the following C++ code to create nodes with unlimited children: // I would like to declare NodeT like this, // but it won't compile because Lnk_T is not defined yet. struct NodeT { Lnk_T Lnk ; };
3
5578
by: Dan | last post by:
Hi, I'm trying to call an RFC from a vb web service. I have created the proxy object with no worries but the return table always returns an error even when I get success running the RFC inside SAP. I login to the GUI under my own username but all the rfcs go through one rfc user. Before I go to the authorisations people, does this sounds like a permissions problem at the SAP end or has anyone else experienced problems like these? I...
2
1686
by: Nospam | last post by:
Powware Visual Programming is the world's first environment for creating software using the Powware Visual Programming Language on the Tablet PC. Be one of the first in the world to experience visual programming on the Tablet PC. Download a pre-release version and let us know what you think. This is a Request For Comments (RFC) to you, the programming community. Your feedback and input is important. Download Powware Visual...
1
1995
by: Alf P. Steinbach | last post by:
* Adam, in clc++m: > I have an unfortunate case where a single class wants to derive from two > existing classes: > > struct A { virtual long fun() = 0; }; > struct B { virtual bool fun() = 0; }; > struct Unfortunate : public A, public B { ??? }; I already answered this one (the exact same message text), apparently to Adam's satisfaction, in .
4
1799
by: Arild Hystad | last post by:
Hi, for some days now, I haven't been able to reach the clc-wiki. Is it terminated, moved or do I have a network problem? My bookmark says it is at http://clc-wiki.net/wiki/. Is this correct? -- Arild Hystad
2
1611
by: runner7 | last post by:
Can anyone tell me where the RFC definition syntax is documented? I am referring to such things as the use of <...>, , 1*, etc. I find this sort of thing in the RFC's for POP3, MIME, etc.
3
1654
by: Nindi | last post by:
On comp.lang.c++.moderated http://groups.google.co.uk/group/comp.lang.c++.moderated/browse_thread/thread/8250715711da7760?hl=en the following question was posted ------------------------------------------------------------------------------------------------------- Is this standard conformant to type cast ::opearator delete to a function of type (void (*)(void*)); Is not operator delete already a function of this type?
13
1744
by: Richard Heathfield | last post by:
I was recently asked about that old "K&R Answers" site I tried to maintain a few years back before Real Life got in the way. I directed the enquirer (who had expressed an interest in helping to maintain it) to http://clc-wiki.net/wiki/ which had taken the weight of that task off my hands. This morning I received an email from my correspondent, saying the site appeared to be dead. I tried to connect to it myself just a moment ago, and...
0
9980
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9826
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
1
10925
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
1
8018
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
7172
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
5855
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
6061
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4682
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
3
3283
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.