randint.c

Absolute File Name:

/home/opencoverage/opencoverage/guest-scripts/coreutils/src/gl/lib/randint.c

Line

Source

Count

/* Generate random integers.

This program is free software: you can redistribute it and/or modify

it under the terms of the GNU General Public License as published by

the Free Software Foundation, either version 3 of the License, or

(at your option) any later version.

This program 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 General Public License for more details.

You should have received a copy of the GNU General Public License

along with this program. If not, see <https://www.gnu.org/licenses/>. */

/* Written by Paul Eggert. */

#include <config.h>

#include "randint.h"

#include <errno.h>

#include <limits.h>

#include <stdlib.h>

#include <string.h>

#if TEST

# include <inttypes.h>

# include <stdio.h>

int

main (int argc, char **argv)

{

randint i;

randint n = strtoumax (argv[1], NULL, 10);

randint choices = strtoumax (argv[2], NULL, 10);

char const *name = argv[3];

struct randint_source *ints = randint_all_new (name, SIZE_MAX);

for (i = 0; i < n; i++)

printf ("%"PRIuMAX"\n", randint_choose (ints, choices));

return (randint_all_free (ints) == 0 ? EXIT_SUCCESS : EXIT_FAILURE);

}

#endif

#include "xalloc.h"

/* A source of random data for generating random integers. */

struct randint_source

{

/* The source of random bytes. */

struct randread_source *source;

/* RANDNUM is a buffered random integer, whose information has not

yet been delivered to the caller. It is uniformly distributed in

the range 0 <= RANDNUM <= RANDMAX. If RANDMAX is zero, then

RANDNUM must be zero (and in some sense it is not really

"random"). */

randint randnum;

randint randmax;

};

/* Create a new randint_source from SOURCE. */

struct randint_source *

randint_new (struct randread_source *source)

{

struct randint_source *s = xmalloc (sizeof *s);

s->source = source;

s->randnum = s->randmax = 0;

return s;

executed 640 times by 6 tests: return s;

Executed by:

cp
ln
mktemp
mv
shred
shuf

640

}

/* Create a new randint_source by creating a randread_source from

NAME and ESTIMATED_BYTES. Return NULL (setting errno) if

unsuccessful. */

struct randint_source *

randint_all_new (char const *name, size_t bytes_bound)

{

struct randread_source *source = randread_new (name, bytes_bound);

return (source ? randint_new (source) : NULL);

executed 640 times by 6 tests: return (source ? randint_new (source) : ((void *)0) );

Executed by:

cp
ln
mktemp
mv
shred
shuf

640

}

/* Return the random data source of *S. */

struct randread_source *

randint_get_source (struct randint_source const *s)

{

return s->source;

executed 25 times by 1 test: return s->source;

Executed by:

shred

}

/* HUGE_BYTES is true on hosts hosts where randint and unsigned char

have the same width and where shifting by the word size therefore

100

has undefined behavior. */

101

enum { HUGE_BYTES = RANDINT_MAX == UCHAR_MAX };

102

103

/* Return X shifted left by CHAR_BIT bits. */

104

static inline randint shift_left (randint x)

105

{

106

return HUGE_BYTES ? 0 : x << CHAR_BIT;

executed 19431 times by 6 tests: return HUGE_BYTES ? 0 : x << 8;

Executed by:

cp
ln
mktemp
mv
shred
shuf

19431

}

/* Consume random data from *S to generate a random number in the range

0 .. GENMAX. */

randint

randint_genmax (struct randint_source *s, randint genmax)

115

{

116

struct randread_source *source = s->source;

117

randint randnum = s->randnum;

118

randint randmax = s->randmax;

119

randint choices = genmax + 1;

while (1)

{

if (randmax < genmax)

randmax < genmax	Description
TRUE	evaluated 6144 times by 6 tests Evaluated by: cp ln mktemp mv shred shuf
FALSE	evaluated 4211 times by 6 tests Evaluated by: cp ln mktemp mv shred shuf

4211-6144

124

{

125

/* Calculate how many input bytes will be needed, and read

the bytes. */

size_t i = 0;

randint rmax = randmax;

130

unsigned char buf[sizeof randnum];

{

rmax = shift_left (rmax) + UCHAR_MAX;

135

i++;

136

}

executed 6477 times by 6 tests: end of block

Executed by:

cp
ln
mktemp
mv
shred
shuf

6477

137

while (rmax < genmax);

rmax < genmax	Description
TRUE	evaluated 333 times by 1 test Evaluated by: shuf
FALSE	evaluated 6144 times by 6 tests Evaluated by: cp ln mktemp mv shred shuf

333-6144

138

139

randread (source, buf, i);

140

141

/* Increase RANDMAX by appending random bytes to RANDNUM and

142

UCHAR_MAX to RANDMAX until RANDMAX is no less than

143

GENMAX. This may lose up to CHAR_BIT bits of information

144

if (HUGE_BYTES ? 0 : RANDINT_MAX >> CHAR_BIT) < GENMAX,

145

but it is not worth the programming hassle of saving

146

these bits since GENMAX is rarely that large in practice. */

i = 0;

{

randnum = shift_left (randnum) + buf[i];

153

randmax = shift_left (randmax) + UCHAR_MAX;

154

i++;

155

}

executed 6477 times by 6 tests: end of block

Executed by:

cp
ln
mktemp
mv
shred
shuf

6477

156

while (randmax < genmax);

randmax < genmax	Description
TRUE	evaluated 333 times by 1 test Evaluated by: shuf
FALSE	evaluated 6144 times by 6 tests Evaluated by: cp ln mktemp mv shred shuf

333-6144

157

}

executed 6144 times by 6 tests: end of block

Executed by:

cp
ln
mktemp
mv
shred
shuf

6144

158

159

if (randmax == genmax)

randmax == genmax	Description
TRUE	evaluated 79 times by 2 tests Evaluated by: shred shuf
FALSE	evaluated 10276 times by 6 tests Evaluated by: cp ln mktemp mv shred shuf

79-10276

160

{

161

s->randnum = s->randmax = 0;

162

return randnum;

executed 79 times by 2 tests: return randnum;

Executed by:

shred
shuf

}

else

{

/* GENMAX < RANDMAX, so attempt to generate a random number

167

by taking RANDNUM modulo GENMAX+1. This will choose

168

fairly so long as RANDNUM falls within an integral

169

multiple of GENMAX+1; otherwise, LAST_USABLE_CHOICE < RANDNUM,

170

so discard this attempt and try again.

171

172

Since GENMAX cannot be RANDINT_MAX, CHOICES cannot be

173

zero and there is no need to worry about dividing by

174

zero. */

175

176

randint excess_choices = randmax - genmax;

177

randint unusable_choices = excess_choices % choices;

178

randint last_usable_choice = randmax - unusable_choices;

179

randint reduced_randnum = randnum % choices;

180

181

if (randnum <= last_usable_choice)

randnum <= last_usable_choice	Description
TRUE	evaluated 9538 times by 6 tests Evaluated by: cp ln mktemp mv shred shuf
FALSE	evaluated 738 times by 5 tests Evaluated by: cp ln mktemp mv shuf

738-9538

182

{

183

s->randnum = randnum / choices;

184

s->randmax = excess_choices / choices;

185

return reduced_randnum;

executed 9538 times by 6 tests: return reduced_randnum;

Executed by:

cp
ln
mktemp
mv
shred
shuf

9538

186

}

187

188

/* Retry, but retain the randomness from the fact that RANDNUM fell

189

into the range LAST_USABLE_CHOICE+1 .. RANDMAX. */

190

randnum = reduced_randnum;

191

randmax = unusable_choices - 1;

192

}

executed 738 times by 5 tests: end of block

Executed by:

cp
ln
mktemp
mv
shuf

738

193

}

194

}

never executed: end of block

195

196

/* Clear *S so that it no longer contains undelivered random data. */

197

198

void

199

randint_free (struct randint_source *s)

200

{

201

explicit_bzero (s, sizeof *s);

202

free (s);

203

}

executed 620 times by 5 tests: end of block

Executed by:

cp
ln
mktemp
mv
shred

620

204

205

/* Likewise, but also clear the underlying randread object. Return

206

0 if successful, -1 (setting errno) otherwise. */

207

208

int

209

randint_all_free (struct randint_source *s)

210

{

211

int r = randread_free (s->source);

int e = errno;

randint_free (s);

errno = e;

return r;

executed 620 times by 5 tests: return r;

Executed by:

cp
ln
mktemp
mv
shred

620

216

}

Generated by Squish Coco 4.1.2