473,883 Members | 2,607 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 6319
In <87************ @pfaff.stanford .edu> Ben Pfaff <bl*@cs.stanfor d.edu> writes:
ol*****@inspir e.net.nz (Old Wolf) writes:
> Does the Standard say that DBL_MAX must be a compile-time constant?

Yes. From C99 5.2.4.2.2:

The values given in the following list shall be replaced by
constant expressions with implementation-defined values that
are greater than or equal to those shown:

- maximum representable finite floating-point number, (1 - b-p)bemax
FLT_MAX 1E+37
DBL_MAX 1E+37
LDBL_MAX 1E+37


BCC 5.x has never made any pretense at C99 compatibility.


I was planning to reply that practically the same text was in
C90, but in fact my "final draft" copy here doesn't say that
these must be constant expressions.


It *explicitly* allows them not to:

Of the values in the <float.h> header, FLT_RADIX shall be a
constant expression suitable for use in #if preprocessing directives;
all other values need not be constant expressions.
^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^ ^^^^

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 14 '05 #71

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

Similar topics

0
1816
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
3904
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
2715
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
5577
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
1685
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
1798
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
1652
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
9933
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
9786
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,...
0
10734
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
10836
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,...
0
10407
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
1
7962
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
7114
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
5982
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4607
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

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.