OpenCoverage

randint.c

Absolute File Name:/home/opencoverage/opencoverage/guest-scripts/coreutils/src/gl/lib/randint.c
Source codeSwitch to Preprocessed file
LineSourceCount
1/* Generate random integers.-
2-
3 Copyright (C) 2006-2018 Free Software Foundation, Inc.-
4-
5 This program is free software: you can redistribute it and/or modify-
6 it under the terms of the GNU General Public License as published by-
7 the Free Software Foundation, either version 3 of the License, or-
8 (at your option) any later version.-
9-
10 This program is distributed in the hope that it will be useful,-
11 but WITHOUT ANY WARRANTY; without even the implied warranty of-
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the-
13 GNU General Public License for more details.-
14-
15 You should have received a copy of the GNU General Public License-
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */-
17-
18/* Written by Paul Eggert. */-
19-
20#include <config.h>-
21-
22#include "randint.h"-
23-
24#include <errno.h>-
25#include <limits.h>-
26#include <stdlib.h>-
27#include <string.h>-
28-
29-
30#if TEST-
31# include <inttypes.h>-
32# include <stdio.h>-
33-
34int-
35main (int argc, char **argv)-
36{-
37 randint i;-
38 randint n = strtoumax (argv[1], NULL, 10);-
39 randint choices = strtoumax (argv[2], NULL, 10);-
40 char const *name = argv[3];-
41 struct randint_source *ints = randint_all_new (name, SIZE_MAX);-
42-
43 for (i = 0; i < n; i++)-
44 printf ("%"PRIuMAX"\n", randint_choose (ints, choices));-
45-
46 return (randint_all_free (ints) == 0 ? EXIT_SUCCESS : EXIT_FAILURE);-
47}-
48#endif-
49-
50-
51#include "xalloc.h"-
52-
53/* A source of random data for generating random integers. */-
54struct randint_source-
55{-
56 /* The source of random bytes. */-
57 struct randread_source *source;-
58-
59 /* RANDNUM is a buffered random integer, whose information has not-
60 yet been delivered to the caller. It is uniformly distributed in-
61 the range 0 <= RANDNUM <= RANDMAX. If RANDMAX is zero, then-
62 RANDNUM must be zero (and in some sense it is not really-
63 "random"). */-
64 randint randnum;-
65 randint randmax;-
66};-
67-
68/* Create a new randint_source from SOURCE. */-
69-
70struct randint_source *-
71randint_new (struct randread_source *source)-
72{-
73 struct randint_source *s = xmalloc (sizeof *s);-
74 s->source = source;-
75 s->randnum = s->randmax = 0;-
76 return s;
executed 640 times by 6 tests: return s;
Executed by:
  • cp
  • ln
  • mktemp
  • mv
  • shred
  • shuf
640
77}-
78-
79/* Create a new randint_source by creating a randread_source from-
80 NAME and ESTIMATED_BYTES. Return NULL (setting errno) if-
81 unsuccessful. */-
82-
83struct randint_source *-
84randint_all_new (char const *name, size_t bytes_bound)-
85{-
86 struct randread_source *source = randread_new (name, bytes_bound);-
87 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
88}-
89-
90/* Return the random data source of *S. */-
91-
92struct randread_source *-
93randint_get_source (struct randint_source const *s)-
94{-
95 return s->source;
executed 25 times by 1 test: return s->source;
Executed by:
  • shred
25
96}-
97-
98/* HUGE_BYTES is true on hosts hosts where randint and unsigned char-
99 have the same width and where shifting by the word size therefore-
100 has undefined behavior. */-
101enum { HUGE_BYTES = RANDINT_MAX == UCHAR_MAX };-
102-
103/* Return X shifted left by CHAR_BIT bits. */-
104static 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
107}-
108-
109-
110/* Consume random data from *S to generate a random number in the range-
111 0 .. GENMAX. */-
112-
113randint-
114randint_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;-
120-
121 while (1)-
122 {-
123 if (randmax < genmax)
randmax < genmaxDescription
TRUEevaluated 6144 times by 6 tests
Evaluated by:
  • cp
  • ln
  • mktemp
  • mv
  • shred
  • shuf
FALSEevaluated 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-
126 the bytes. */-
127-
128 size_t i = 0;-
129 randint rmax = randmax;-
130 unsigned char buf[sizeof randnum];-
131-
132 do-
133 {-
134 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 < genmaxDescription
TRUEevaluated 333 times by 1 test
Evaluated by:
  • shuf
FALSEevaluated 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. */-
147-
148 i = 0;-
149-
150 do-
151 {-
152 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 < genmaxDescription
TRUEevaluated 333 times by 1 test
Evaluated by:
  • shuf
FALSEevaluated 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 == genmaxDescription
TRUEevaluated 79 times by 2 tests
Evaluated by:
  • shred
  • shuf
FALSEevaluated 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
79
163 }-
164 else-
165 {-
166 /* 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_choiceDescription
TRUEevaluated 9538 times by 6 tests
Evaluated by:
  • cp
  • ln
  • mktemp
  • mv
  • shred
  • shuf
FALSEevaluated 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
0
195-
196/* Clear *S so that it no longer contains undelivered random data. */-
197-
198void-
199randint_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-
208int-
209randint_all_free (struct randint_source *s)-
210{-
211 int r = randread_free (s->source);-
212 int e = errno;-
213 randint_free (s);-
214 errno = e;-
215 return r;
executed 620 times by 5 tests: return r;
Executed by:
  • cp
  • ln
  • mktemp
  • mv
  • shred
620
216}-
Source codeSwitch to Preprocessed file

Generated by Squish Coco 4.1.2