LCOV - code coverage report
Current view: top level - lib - randint.c (source / functions) Hit Total Coverage
Test: coreutils.info Lines: 52 52 100.0 %
Date: 2018-01-30 Functions: 7 7 100.0 %

          Line data    Source code
       1             : /* Generate random integers.
       2             : 
       3             :    Copyright (C) 2006 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 <http://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             : 
      34             : int
      35             : main (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             : #ifndef MAX
      54             : # define MAX(a,b) ((a) < (b) ? (b) : (a))
      55             : #endif
      56             : 
      57             : /* A source of random data for generating random integers.  */
      58             : struct randint_source
      59             : {
      60             :   /* The source of random bytes.  */
      61             :   struct randread_source *source;
      62             : 
      63             :   /* RANDNUM is a buffered random integer, whose information has not
      64             :      yet been delivered to the caller.  It is uniformly distributed in
      65             :      the range 0 <= RANDNUM <= RANDMAX.  If RANDMAX is zero, then
      66             :      RANDNUM must be zero (and in some sense it is not really
      67             :      "random").  */
      68             :   randint randnum;
      69             :   randint randmax;
      70             : };
      71             : 
      72             : /* Create a new randint_source from SOURCE.  */
      73             : 
      74             : struct randint_source *
      75         103 : randint_new (struct randread_source *source)
      76             : {
      77         103 :   struct randint_source *s = xmalloc (sizeof *s);
      78         103 :   s->source = source;
      79         103 :   s->randnum = s->randmax = 0;
      80         103 :   return s;
      81             : }
      82             : 
      83             : /* Create a new randint_source by creating a randread_source from
      84             :    NAME and ESTIMATED_BYTES.  Return NULL (setting errno) if
      85             :    unsuccessful.  */
      86             : 
      87             : struct randint_source *
      88         105 : randint_all_new (char const *name, size_t bytes_bound)
      89             : {
      90         105 :   struct randread_source *source = randread_new (name, bytes_bound);
      91         105 :   return (source ? randint_new (source) : NULL);
      92             : }
      93             : 
      94             : /* Return the random data source of *S.  */
      95             : 
      96             : struct randread_source *
      97          22 : randint_get_source (struct randint_source const *s)
      98             : {
      99          22 :   return s->source;
     100             : }
     101             : 
     102             : /* HUGE_BYTES is true on hosts hosts where randint and unsigned char
     103             :    have the same width and where shifting by the word size therefore
     104             :    has undefined behavior.  */
     105             : enum { HUGE_BYTES = RANDINT_MAX == UCHAR_MAX };
     106             : 
     107             : /* Return X shifted left by CHAR_BIT bits.  */
     108        1156 : static inline randint shift_left (randint x)
     109             : {
     110        1156 :   return HUGE_BYTES ? 0 : x << CHAR_BIT;
     111             : }
     112             : 
     113             : /* Return X shifted right by CHAR_BIT bits.  */
     114             : static inline randint
     115             : shift_right (randint x)
     116             : {
     117             :   return HUGE_BYTES ? 0 : x >> CHAR_BIT;
     118             : }
     119             : 
     120             : 
     121             : /* Consume random data from *S to generate a random number in the range
     122             :    0 .. GENMAX.  */
     123             : 
     124             : randint
     125         747 : randint_genmax (struct randint_source *s, randint genmax)
     126             : {
     127         747 :   struct randread_source *source = s->source;
     128         747 :   randint randnum = s->randnum;
     129         747 :   randint randmax = s->randmax;
     130         747 :   randint choices = genmax + 1;
     131             : 
     132             :   for (;;)
     133             :     {
     134         827 :       if (randmax < genmax)
     135             :         {
     136             :           /* Calculate how many input bytes will be needed, and read
     137             :              the bytes.  */
     138             : 
     139         386 :           size_t i = 0;
     140         386 :           randint rmax = randmax;
     141             :           unsigned char buf[sizeof randnum];
     142             : 
     143             :           do
     144             :             {
     145         386 :               rmax = shift_left (rmax) + UCHAR_MAX;
     146         386 :               i++;
     147             :             }
     148         386 :           while (rmax < genmax);
     149             : 
     150         386 :           randread (source, buf, i);
     151             : 
     152             :           /* Increase RANDMAX by appending random bytes to RANDNUM and
     153             :              UCHAR_MAX to RANDMAX until RANDMAX is no less than
     154             :              GENMAX.  This may lose up to CHAR_BIT bits of information
     155             :              if shift_right (RANDINT_MAX) < GENMAX, but it is not
     156             :              worth the programming hassle of saving these bits since
     157             :              GENMAX is rarely that large in practice.  */
     158             : 
     159         385 :           i = 0;
     160             : 
     161             :           do
     162             :             {
     163         385 :               randnum = shift_left (randnum) + buf[i];
     164         385 :               randmax = shift_left (randmax) + UCHAR_MAX;
     165         385 :               i++;
     166             :             }
     167         385 :           while (randmax < genmax);
     168             :         }
     169             : 
     170         786 :       if (randmax == genmax)
     171             :         {
     172          43 :           s->randnum = s->randmax = 0;
     173          43 :           return randnum;
     174             :         }
     175             :       else
     176             :         {
     177             :           /* GENMAX < RANDMAX, so attempt to generate a random number
     178             :              by taking RANDNUM modulo GENMAX+1.  This will choose
     179             :              fairly so long as RANDNUM falls within an integral
     180             :              multiple of GENMAX+1; otherwise, LAST_USABLE_CHOICE < RANDNUM,
     181             :              so discard this attempt and try again.
     182             : 
     183             :              Since GENMAX cannot be RANDINT_MAX, CHOICES cannot be
     184             :              zero and there is no need to worry about dividing by
     185             :              zero.  */
     186             : 
     187         743 :           randint excess_choices = randmax - genmax;
     188         743 :           randint unusable_choices = excess_choices % choices;
     189         743 :           randint last_usable_choice = randmax - unusable_choices;
     190         743 :           randint reduced_randnum = randnum % choices;
     191             : 
     192         743 :           if (randnum <= last_usable_choice)
     193             :             {
     194         703 :               s->randnum = randnum / choices;
     195         703 :               s->randmax = excess_choices / choices;
     196         703 :               return reduced_randnum;
     197             :             }
     198             : 
     199             :           /* Retry, but retain the randomness from the fact that RANDNUM fell
     200             :              into the range LAST_USABLE_CHOICE+1 .. RANDMAX.  */
     201          40 :           randnum = reduced_randnum;
     202          40 :           randmax = unusable_choices - 1;
     203             :         }
     204             :     }
     205             : }
     206             : 
     207             : /* Clear *S so that it no longer contains undelivered random data.  */
     208             : 
     209             : void
     210          76 : randint_free (struct randint_source *s)
     211             : {
     212          76 :   memset (s, 0, sizeof *s);
     213          76 :   free (s);
     214          76 : }
     215             : 
     216             : /* Likewise, but also clear the underlying randread object.  Return
     217             :    0 if successful, -1 (setting errno) otherwise.  */
     218             : 
     219             : int
     220          76 : randint_all_free (struct randint_source *s)
     221             : {
     222          76 :   int r = randread_free (s->source);
     223          76 :   int e = errno;
     224          76 :   randint_free (s);
     225          76 :   errno = e;
     226          76 :   return r;
     227             : }

Generated by: LCOV version 1.10