src/rand.cpp

   1 /* $Id: rand.cpp 25033 2007-10-04 07:21:02Z frank $ */
   2 /** @file
   3  * innotek Portable Runtime - Random Number
   4  */
   5
   6 /*
   7  * Copyright (C) 2006-2007 innotek GmbH
   8  *
   9  * This file is part of VirtualBox Open Source Edition (OSE), as
  10  * available from http://www.virtualbox.org. This file is free software;
  11  * you can redistribute it and/or modify it under the terms of the GNU
  12  * General Public License as published by the Free Software Foundation,
  13  * in version 2 as it comes in the "COPYING" file of the VirtualBox OSE
  14  * distribution. VirtualBox OSE is distributed in the hope that it will
  15  * be useful, but WITHOUT ANY WARRANTY of any kind.
  16  */
  17
  18
  19 /*******************************************************************************
  20 *   Header Files                                                               *
  21 *******************************************************************************/
  22 #include "rand.h"
  23 #include "time.h"
  24 #include "asm.h"
  25 #include "const_defines.h"
  26 #include "func_defines.h"
  27 #include <errno.h>
  28 #include <sys/stat.h>
  29 #include <sys/types.h>
  30 #include <sys/ioctl.h>
  31 #include <sys/fcntl.h>
  32 #include <fcntl.h>
  33 # include <unistd.h>
  34 # include <sys/time.h>
  35
  36
  37 /*******************************************************************************
  38 *   Global Variables                                                           *
  39 *******************************************************************************/
  40 /** Lazy init. */
  41 static volatile bool    g_fInitialized = false;
  42 /** The context variable for the fallback path. */
  43 static uint32_t         g_u32Ctx;
  44 /** File handle of /dev/random. */
  45 static int g_fhDevRandom = -1;
  46
  47
  48 /*******************************************************************************
  49 *   Internal Functions                                                         *
  50 *******************************************************************************/
  51 static uint32_t rtRandGenBytesFallbackU31(uint32_t *pCtx);
  52
  53
  54 /**
  55  * Lazy initialization of the native and fallback random byte sources.
  56  *
  57  */
  58 static void rtRandLazyInit(void)
  59 {
  60     /*
  61      * Seed the fallback random code.
  62      */
  63     g_u32Ctx = (uint32_t)(ASMReadTSC() >> 8);
  64
  65     /*
  66      * Call host specific init.
  67      */
  68     rtRandLazyInitNative();
  69     g_fInitialized = true;
  70 }
  71
  72
  73 /**
  74  * Internal wrapper for the native and generic random byte methods.
  75  *
  76  * @param   pv  Where to store the random bytes.
  77  * @param   cb  Number of bytes to generate.
  78  */
  79 static void rtRandGenBytes(void *pv, size_t cb)
  80 {
  81     Assert(cb);
  82     if (RT_UNLIKELY(!g_fInitialized))
  83         rtRandLazyInit();
  84
  85     int rc = rtRandGenBytesNative(pv, cb);
  86     if (RT_FAILURE(rc))
  87         rtRandGenBytesFallback(pv, cb);
  88 }
  89
  90
  91 /**
  92  * Fills a buffer with random bytes.
  93  *
  94  * @param   pv  Where to store the random bytes.
  95  * @param   cb  Number of bytes to generate.
  96  */
  97 void RTRandBytes(void *pv, size_t cb)
  98 {
  99     if (cb)
 100         rtRandGenBytes(pv, cb);
 101 }
 102
 103
 104 /**
 105  * Generate a 32-bit signed random number in the set [i32First..i32Last].
 106  *
 107  * @returns The random number.
 108  * @param   i32First    First number in the set.
 109  * @param   i32Last     Last number in the set.
 110  */
 111 int32_t RTRandS32Ex(int32_t i32First, int32_t i32Last)
 112 {
 113     /* get 4 random bytes. */
 114     union
 115     {
 116         uint32_t    off;
 117         uint8_t     ab[4];
 118     } u;
 119     rtRandGenBytes(&u.ab, sizeof(u));
 120
 121
 122     /* squeeze it into the requested range. */
 123     uint32_t offLast = i32Last - i32First;
 124     if (u.off > offLast)
 125     {
 126         do
 127         {
 128             u.off >>= 1;
 129         } while (u.off > offLast);
 130     }
 131     return i32First + u.off;
 132 }
 133
 134
 135 /**
 136  * Generate a 32-bit signed random number.
 137  *
 138  * @returns The random number.
 139  */
 140 int32_t RTRandS32(void)
 141 {
 142     return RTRandS32Ex(INT32_MIN, INT32_MAX);
 143 }
 144
 145
 146 /**
 147  * Generate a 32-bit unsigned random number in the set [u32First..u32Last].
 148  *
 149  * @returns The random number.
 150  * @param   u32First    First number in the set.
 151  * @param   u32Last     Last number in the set.
 152  */
 153 uint32_t RTRandU32Ex(uint32_t u32First, uint32_t u32Last)
 154 {
 155     /* get 4 random bytes. */
 156     union
 157     {
 158         uint32_t    off;
 159         uint8_t     ab[4];
 160     } u;
 161     rtRandGenBytes(&u.ab, sizeof(u));
 162
 163
 164     /* squeeze it into the requested range. */
 165     const uint32_t offLast = u32Last - u32First;
 166     if (u.off > offLast)
 167     {
 168         do
 169         {
 170             u.off >>= 1;
 171         } while (u.off > offLast);
 172     }
 173     return u32First + u.off;
 174 }
 175
 176
 177 /**
 178  * Generate a 32-bit unsigned random number.
 179  *
 180  * @returns The random number.
 181  */
 182 uint32_t RTRandU32(void)
 183 {
 184     return RTRandU32Ex(0, UINT32_MAX);
 185 }
 186
 187
 188 /**
 189  * Generate a 32-bit signed random number in the set [i32First..i32Last].
 190  *
 191  * @returns The random number.
 192  * @param   i32First    First number in the set.
 193  * @param   i32Last     Last number in the set.
 194  */
 195 int64_t RTRandS64Ex(int64_t i64First, int64_t i64Last)
 196 {
 197     /* get 8 random bytes. */
 198     union
 199     {
 200         uint64_t    off;
 201         uint8_t     ab[8];
 202     } u;
 203     rtRandGenBytes(&u.ab, sizeof(u));
 204
 205     /* squeeze it into the requested range. */
 206     uint64_t offLast = i64Last - i64First;
 207     if (u.off > offLast)
 208     {
 209         do
 210         {
 211             u.off >>= 1;
 212         } while (u.off > offLast);
 213     }
 214     return i64First + u.off;
 215 }
 216
 217
 218 /**
 219  * Generate a 64-bit signed random number.
 220  *
 221  * @returns The random number.
 222  */
 223 int64_t RTRandS64(void)
 224 {
 225     return RTRandS64Ex(INT64_MIN, INT64_MAX);
 226 }
 227
 228
 229 /**
 230  * Generate a 64-bit unsigned random number in the set [u64First..u64Last].
 231  *
 232  * @returns The random number.
 233  * @param   u64First    First number in the set.
 234  * @param   u64Last     Last number in the set.
 235  */
 236 uint64_t RTRandU64Ex(uint64_t u64First, uint64_t u64Last)
 237 {
 238     /* get 8 random bytes. */
 239     union
 240     {
 241         uint64_t    off;
 242         uint8_t     ab[8];
 243     } u;
 244     rtRandGenBytes(&u.ab, sizeof(u));
 245
 246     /* squeeze it into the requested range. */
 247     const uint64_t offLast = u64Last - u64First;
 248     if (u.off > offLast)
 249     {
 250         do
 251         {
 252             u.off >>= 1;
 253         } while (u.off > offLast);
 254     }
 255     return u64First + u.off;
 256 }
 257
 258
 259 /**
 260  * Generate a 64-bit unsigned random number.
 261  *
 262  * @returns The random number.
 263  */
 264 uint64_t RTRandU64(void)
 265 {
 266     return RTRandU64Ex(0, UINT64_MAX);
 267 }
 268
 269
 270 /**
 271  * Fallback random byte source.
 272  *
 273  * @param   pv  Where to store the random bytes.
 274  * @param   cb  Number of bytes to generate.
 275  */
 276 void rtRandGenBytesFallback(void *pv, size_t cb)
 277 {
 278     uint8_t *pb = (uint8_t *)pv;
 279     for (unsigned i = 0;; i++)
 280     {
 281         uint32_t u32 = rtRandGenBytesFallbackU31(&g_u32Ctx);
 282
 283         *pb++ = (uint8_t)u32;
 284         if (!--cb)
 285             break;
 286
 287         u32 >>= 8;
 288         *pb++ = (uint8_t)u32;
 289         if (!--cb)
 290             break;
 291
 292         u32 >>= 8;
 293         *pb++ = (uint8_t)u32;
 294         if (!--cb)
 295             break;
 296
 297         /* Is this really a good idea? */
 298         /*if (!(i % 3))
 299         {
 300             if (i)
 301                 RTThreadYield();
 302             *pb++ = (uint8_t)ASMReadTSC();
 303             if (!--cb)
 304                 break;
 305         }*/
 306     }
 307
 308 }
 309
 310
 311 /*-
 312  * Copyright (c) 1990, 1993
 313  *      The Regents of the University of California.  All rights reserved.
 314  *
 315  * Redistribution and use in source and binary forms, with or without
 316  * modification, are permitted provided that the following conditions
 317  * are met:
 318  * 1. Redistributions of source code must retain the above copyright
 319  *    notice, this list of conditions and the following disclaimer.
 320  * 2. Redistributions in binary form must reproduce the above copyright
 321  *    notice, this list of conditions and the following disclaimer in the
 322  *    documentation and/or other materials provided with the distribution.
 323  * 4. Neither the name of the University nor the names of its contributors
 324  *    may be used to endorse or promote products derived from this software
 325  *    without specific prior written permission.
 326  *
 327  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 328  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 329  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 330  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 331  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 332  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 333  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 334  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 335  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 336  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 337  * SUCH DAMAGE.
 338  */
 339
 340 /* The core of:
 341 __FBSDID("$FreeBSD: /repoman/r/ncvs/src/lib/libc/stdlib/rand.c,v 1.16 2007/01/09 00:28:10 imp Exp $");
 342 */
 343
 344 /**
 345  * Generates an unsigned 31 bit pseudo random number.
 346  *
 347  * @returns pseudo random number.
 348  * @param   pCtx    The context.
 349  */
 350 static uint32_t rtRandGenBytesFallbackU31(uint32_t *pCtx)
 351 {
 352     /*
 353      * Compute x = (7^5 * x) mod (2^31 - 1)
 354      * without overflowing 31 bits:
 355      *      (2^31 - 1) = 127773 * (7^5) + 2836
 356      *
 357      * From "Random number generators: good ones are hard to find",  Park and
 358      * Miller, Communications of the ACM, vol. 31, no. 10, October 1988, p. 1195.
 359      */
 360     uint32_t Ctx = *pCtx;
 361     if (!Ctx) /* must not be zero. */
 362         Ctx = 0x20070212;
 363     uint32_t Hi = Ctx / 127773;
 364     uint32_t Lo = Ctx % 127773;
 365     int32_t x = 16807 * Lo  -  2836 * Hi;
 366     if (x < 0)
 367         x += INT32_MAX;
 368     *pCtx = x;
 369     return x % INT32_MAX;
 370 }
 371
 372 void rtRandLazyInitNative(void)
 373 {
 374     if (g_fhDevRandom != -1)
 375         return;
 376
 377     int fh = open("/dev/urandom", O_RDONLY);
 378     if (fh <= 0)
 379         fh = open("/dev/random", O_RDONLY | O_NONBLOCK);
 380     if (fh >= 0)
 381     {
 382         fcntl(fh, F_SETFD, FD_CLOEXEC);
 383         g_fhDevRandom = fh;
 384     }
 385 }
 386
 387
 388 int rtRandGenBytesNative(void *pv, size_t cb)
 389 {
 390     int fh = g_fhDevRandom;
 391     if (fh == -1)
 392         return VERR_NOT_SUPPORTED;
 393
 394     ssize_t cbRead = read(fh, pv, cb);
 395     if ((size_t)cbRead != cb)
 396     {
 397         /*
 398          * Use the fallback for the remainder if /dev/urandom / /dev/random
 399          * is out to lunch.
 400          */
 401         if (cbRead <= 0)
 402             rtRandGenBytesFallback(pv, cb);
 403         else
 404         {
 405             AssertRelease((size_t)cbRead < cb);
 406             rtRandGenBytesFallback((uint8_t *)pv + cbRead, cb - cbRead);
 407         }
 408     }
 409     return VINF_SUCCESS;
 410 }