diff options
Diffstat (limited to 'src/VBox/Runtime/common/rand')
| -rw-r--r-- | src/VBox/Runtime/common/rand/Makefile.kup | 0 | ||||
| -rw-r--r-- | src/VBox/Runtime/common/rand/rand.cpp | 176 | ||||
| -rw-r--r-- | src/VBox/Runtime/common/rand/randadv.cpp | 414 | ||||
| -rw-r--r-- | src/VBox/Runtime/common/rand/randparkmiller.cpp | 210 |
4 files changed, 800 insertions, 0 deletions
diff --git a/src/VBox/Runtime/common/rand/Makefile.kup b/src/VBox/Runtime/common/rand/Makefile.kup new file mode 100644 index 00000000..e69de29b --- /dev/null +++ b/src/VBox/Runtime/common/rand/Makefile.kup diff --git a/src/VBox/Runtime/common/rand/rand.cpp b/src/VBox/Runtime/common/rand/rand.cpp new file mode 100644 index 00000000..ef16b3a3 --- /dev/null +++ b/src/VBox/Runtime/common/rand/rand.cpp @@ -0,0 +1,176 @@ +/* $Id: rand.cpp $ */ +/** @file + * IPRT - Random Numbers. + */ + +/* + * Copyright (C) 2006-2020 Oracle Corporation + * + * This file is part of VirtualBox Open Source Edition (OSE), as + * available from http://www.virtualbox.org. This file is free software; + * you can redistribute it and/or modify it under the terms of the GNU + * General Public License (GPL) as published by the Free Software + * Foundation, in version 2 as it comes in the "COPYING" file of the + * VirtualBox OSE distribution. VirtualBox OSE is distributed in the + * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind. + * + * The contents of this file may alternatively be used under the terms + * of the Common Development and Distribution License Version 1.0 + * (CDDL) only, as it comes in the "COPYING.CDDL" file of the + * VirtualBox OSE distribution, in which case the provisions of the + * CDDL are applicable instead of those of the GPL. + * + * You may elect to license modified versions of this file under the + * terms and conditions of either the GPL or the CDDL or both. + */ + + +/********************************************************************************************************************************* +* Header Files * +*********************************************************************************************************************************/ +#include <iprt/rand.h> +#include "internal/iprt.h" + +#include <iprt/time.h> +#if defined(RT_ARCH_AMD64) || defined(RT_ARCH_X86) +# include <iprt/asm-amd64-x86.h> +#endif +#include <iprt/errcore.h> +#include <iprt/assert.h> +#include <iprt/thread.h> +#include <iprt/once.h> +#include "internal/rand.h" + + +/********************************************************************************************************************************* +* Global Variables * +*********************************************************************************************************************************/ +/** For lazily initializing of the random generator. */ +static RTONCE g_rtRandOnce = RTONCE_INITIALIZER; +/** The default random generator. */ +static RTRAND g_hRand = NIL_RTRAND; + + +/** + * Perform lazy initialization. + * + * @returns IPRT status code. + * @param pvUser Ignored. + */ +static DECLCALLBACK(int) rtRandInitOnce(void *pvUser) +{ + RTRAND hRand; + int rc = RTRandAdvCreateSystemFaster(&hRand); + if (RT_FAILURE(rc)) + rc = RTRandAdvCreateParkMiller(&hRand); + if (RT_SUCCESS(rc)) + { +#if defined(RT_ARCH_AMD64) || defined(RT_ARCH_X86) + RTRandAdvSeed(hRand, ASMReadTSC() >> 8); +#else + RTRandAdvSeed(hRand, RTTimeNanoTS() >> 8); +#endif + g_hRand = hRand; + } + else + AssertRC(rc); + + NOREF(pvUser); + return rc; +} + + +/** + * Termination counterpart to rtRandInitOnce. + * + * @returns IPRT status code. + * @param pvUser Ignored. + * @param fLazyCleanUpOk Set if we're terminating the process. + */ +static DECLCALLBACK(void) rtRandTermOnce(void *pvUser, bool fLazyCleanUpOk) +{ + if (!fLazyCleanUpOk) + { + RTRAND hRand = g_hRand; + g_hRand = NIL_RTRAND; + if (hRand != NIL_RTRAND) + { + int rc = RTRandAdvDestroy(hRand); + AssertRC(rc); + } + } + NOREF(pvUser); +} + + +RTDECL(void) RTRandBytes(void *pv, size_t cb) RT_NO_THROW_DEF +{ + RTOnceEx(&g_rtRandOnce, rtRandInitOnce, rtRandTermOnce, NULL); + RTRandAdvBytes(g_hRand, pv, cb); +} +RT_EXPORT_SYMBOL(RTRandBytes); + + +RTDECL(uint32_t) RTRandU32Ex(uint32_t u32First, uint32_t u32Last) RT_NO_THROW_DEF +{ + RTOnceEx(&g_rtRandOnce, rtRandInitOnce, rtRandTermOnce, NULL); + return RTRandAdvU32Ex(g_hRand, u32First, u32Last); +} +RT_EXPORT_SYMBOL(RTRandU32Ex); + + +RTDECL(uint32_t) RTRandU32(void) RT_NO_THROW_DEF +{ + RTOnceEx(&g_rtRandOnce, rtRandInitOnce, rtRandTermOnce, NULL); + return RTRandAdvU32(g_hRand); +} +RT_EXPORT_SYMBOL(RTRandU32); + + +RTDECL(int32_t) RTRandS32Ex(int32_t i32First, int32_t i32Last) RT_NO_THROW_DEF +{ + RTOnceEx(&g_rtRandOnce, rtRandInitOnce, rtRandTermOnce, NULL); + return RTRandAdvS32Ex(g_hRand, i32First, i32Last); +} +RT_EXPORT_SYMBOL(RTRandS32Ex); + + +RTDECL(int32_t) RTRandS32(void) RT_NO_THROW_DEF +{ + RTOnceEx(&g_rtRandOnce, rtRandInitOnce, rtRandTermOnce, NULL); + return RTRandAdvS32(g_hRand); +} +RT_EXPORT_SYMBOL(RTRandS32); + + +RTDECL(uint64_t) RTRandU64Ex(uint64_t u64First, uint64_t u64Last) RT_NO_THROW_DEF +{ + RTOnceEx(&g_rtRandOnce, rtRandInitOnce, rtRandTermOnce, NULL); + return RTRandAdvU64Ex(g_hRand, u64First, u64Last); +} +RT_EXPORT_SYMBOL(RTRandU64Ex); + + +RTDECL(uint64_t) RTRandU64(void) RT_NO_THROW_DEF +{ + RTOnceEx(&g_rtRandOnce, rtRandInitOnce, rtRandTermOnce, NULL); + return RTRandAdvU64(g_hRand); +} +RT_EXPORT_SYMBOL(RTRandU64); + + +RTDECL(int64_t) RTRandS64Ex(int64_t i64First, int64_t i64Last) RT_NO_THROW_DEF +{ + RTOnceEx(&g_rtRandOnce, rtRandInitOnce, rtRandTermOnce, NULL); + return RTRandAdvS64Ex(g_hRand, i64First, i64Last); +} +RT_EXPORT_SYMBOL(RTRandS64Ex); + + +RTDECL(int64_t) RTRandS64(void) RT_NO_THROW_DEF +{ + RTOnceEx(&g_rtRandOnce, rtRandInitOnce, rtRandTermOnce, NULL); + return RTRandAdvS32(g_hRand); +} +RT_EXPORT_SYMBOL(RTRandS64); + diff --git a/src/VBox/Runtime/common/rand/randadv.cpp b/src/VBox/Runtime/common/rand/randadv.cpp new file mode 100644 index 00000000..3ddf7a2d --- /dev/null +++ b/src/VBox/Runtime/common/rand/randadv.cpp @@ -0,0 +1,414 @@ +/* $Id: randadv.cpp $ */ +/** @file + * IPRT - Random Numbers, Generic Glue. + */ + +/* + * Copyright (C) 2008-2020 Oracle Corporation + * + * This file is part of VirtualBox Open Source Edition (OSE), as + * available from http://www.virtualbox.org. This file is free software; + * you can redistribute it and/or modify it under the terms of the GNU + * General Public License (GPL) as published by the Free Software + * Foundation, in version 2 as it comes in the "COPYING" file of the + * VirtualBox OSE distribution. VirtualBox OSE is distributed in the + * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind. + * + * The contents of this file may alternatively be used under the terms + * of the Common Development and Distribution License Version 1.0 + * (CDDL) only, as it comes in the "COPYING.CDDL" file of the + * VirtualBox OSE distribution, in which case the provisions of the + * CDDL are applicable instead of those of the GPL. + * + * You may elect to license modified versions of this file under the + * terms and conditions of either the GPL or the CDDL or both. + */ + + +/********************************************************************************************************************************* +* Header Files * +*********************************************************************************************************************************/ +#include <iprt/rand.h> +#include "internal/iprt.h" + +#include <iprt/mem.h> +#include <iprt/errcore.h> +#include <iprt/assert.h> +#include "internal/magics.h" +#include "internal/rand.h" + + +RTDECL(int) RTRandAdvDestroy(RTRAND hRand) RT_NO_THROW_DEF +{ + /* Validate. */ + if (hRand == NIL_RTRAND) + return VINF_SUCCESS; + PRTRANDINT pThis = hRand; + AssertPtrReturn(pThis, VERR_INVALID_HANDLE); + AssertReturn(pThis->u32Magic == RTRANDINT_MAGIC, VERR_INVALID_HANDLE); + + /* forward the call */ + return pThis->pfnDestroy(pThis); +} +RT_EXPORT_SYMBOL(RTRandAdvDestroy); + + +RTDECL(int) RTRandAdvSeed(RTRAND hRand, uint64_t u64Seed) RT_NO_THROW_DEF +{ + /* Validate. */ + PRTRANDINT pThis = hRand; + AssertPtrReturn(pThis, VERR_INVALID_HANDLE); + AssertReturn(pThis->u32Magic == RTRANDINT_MAGIC, VERR_INVALID_HANDLE); + + /* forward the call */ + return pThis->pfnSeed(pThis, u64Seed); +} +RT_EXPORT_SYMBOL(RTRandAdvSeed); + + +RTDECL(int) RTRandAdvSaveState(RTRAND hRand, char *pszState, size_t *pcbState) RT_NO_THROW_DEF +{ + /* Validate. */ + PRTRANDINT pThis = hRand; + AssertPtrReturn(pThis, VERR_INVALID_HANDLE); + AssertReturn(pThis->u32Magic == RTRANDINT_MAGIC, VERR_INVALID_HANDLE); + AssertPtrNull(pszState); + AssertPtr(pcbState); + + /* forward the call */ + return pThis->pfnSaveState(pThis, pszState, pcbState); +} +RT_EXPORT_SYMBOL(RTRandAdvSaveState); + + +RTDECL(int) RTRandAdvRestoreState(RTRAND hRand, char const *pszState) RT_NO_THROW_DEF +{ + /* Validate. */ + PRTRANDINT pThis = hRand; + AssertPtrReturn(pThis, VERR_INVALID_HANDLE); + AssertReturn(pThis->u32Magic == RTRANDINT_MAGIC, VERR_INVALID_HANDLE); + AssertPtr(pszState); + + /* forward the call */ + return pThis->pfnRestoreState(pThis, pszState); +} +RT_EXPORT_SYMBOL(RTRandAdvRestoreState); + + +RTDECL(void) RTRandAdvBytes(RTRAND hRand, void *pv, size_t cb) RT_NO_THROW_DEF +{ + /* Validate. */ + PRTRANDINT pThis = hRand; + AssertPtrReturnVoid(pThis); + AssertReturnVoid(pThis->u32Magic == RTRANDINT_MAGIC); + AssertPtr(pv); + + /* forward the call */ + return pThis->pfnGetBytes(pThis, (uint8_t *)pv, cb); +} +RT_EXPORT_SYMBOL(RTRandAdvBytes); + + +RTDECL(int32_t) RTRandAdvS32Ex(RTRAND hRand, int32_t i32First, int32_t i32Last) RT_NO_THROW_DEF +{ + /* Validate. */ + PRTRANDINT pThis = hRand; + AssertPtrReturn(pThis, INT32_MAX); + AssertReturn(pThis->u32Magic == RTRANDINT_MAGIC, INT32_MAX); + + /* wrap the call */ + return pThis->pfnGetU32(pThis, 0, i32Last - i32First) + i32First; +} +RT_EXPORT_SYMBOL(RTRandAdvS32Ex); + + +RTDECL(int32_t) RTRandAdvS32(RTRAND hRand) RT_NO_THROW_DEF +{ + /* Validate. */ + PRTRANDINT pThis = hRand; + AssertPtrReturn(pThis, INT32_MAX); + AssertReturn(pThis->u32Magic == RTRANDINT_MAGIC, INT32_MAX); + + /* wrap the call */ + return pThis->pfnGetU32(pThis, 0, UINT32_MAX) + INT32_MAX; +} +RT_EXPORT_SYMBOL(RTRandAdvS32); + + +RTDECL(uint32_t) RTRandAdvU32Ex(RTRAND hRand, uint32_t u32First, uint32_t u32Last) RT_NO_THROW_DEF +{ + /* Validate. */ + PRTRANDINT pThis = hRand; + AssertPtrReturn(pThis, UINT32_MAX); + AssertReturn(pThis->u32Magic == RTRANDINT_MAGIC, UINT32_MAX); + + /* forward the call */ + return pThis->pfnGetU32(pThis, u32First, u32Last); +} +RT_EXPORT_SYMBOL(RTRandAdvU32Ex); + + +RTDECL(uint32_t) RTRandAdvU32(RTRAND hRand) RT_NO_THROW_DEF +{ + /* Validate. */ + PRTRANDINT pThis = hRand; + AssertPtrReturn(pThis, UINT32_MAX); + AssertReturn(pThis->u32Magic == RTRANDINT_MAGIC, UINT32_MAX); + + /* forward the call */ + return pThis->pfnGetU32(pThis, 0, UINT32_MAX); +} +RT_EXPORT_SYMBOL(RTRandAdvU32); + + +RTDECL(int64_t) RTRandAdvS64Ex(RTRAND hRand, int64_t i64First, int64_t i64Last) RT_NO_THROW_DEF +{ + /* Validate. */ + PRTRANDINT pThis = hRand; + AssertPtrReturn(pThis, INT64_MAX); + AssertReturn(pThis->u32Magic == RTRANDINT_MAGIC, INT64_MAX); + + /* wrap the call */ + return pThis->pfnGetU64(pThis, 0, i64Last - i64First) + i64First; +} +RT_EXPORT_SYMBOL(RTRandAdvS64Ex); + + +RTDECL(int64_t) RTRandAdvS64(RTRAND hRand) RT_NO_THROW_DEF +{ + /* Validate. */ + PRTRANDINT pThis = hRand; + AssertPtrReturn(pThis, INT64_MAX); + AssertReturn(pThis->u32Magic == RTRANDINT_MAGIC, INT64_MAX); + + /* wrap the call */ + return pThis->pfnGetU64(pThis, 0, UINT64_MAX) + INT64_MAX; +} +RT_EXPORT_SYMBOL(RTRandAdvS64); + + +RTDECL(uint64_t) RTRandAdvU64Ex(RTRAND hRand, uint64_t u64First, uint64_t u64Last) RT_NO_THROW_DEF +{ + /* Validate. */ + PRTRANDINT pThis = hRand; + AssertPtrReturn(pThis, UINT64_MAX); + AssertReturn(pThis->u32Magic == RTRANDINT_MAGIC, UINT64_MAX); + + /* forward the call */ + return pThis->pfnGetU64(pThis, u64First, u64Last); +} +RT_EXPORT_SYMBOL(RTRandAdvU64Ex); + + +RTDECL(uint64_t) RTRandAdvU64(RTRAND hRand) RT_NO_THROW_DEF +{ + /* Validate. */ + PRTRANDINT pThis = hRand; + AssertPtrReturn(pThis, UINT64_MAX); + AssertReturn(pThis->u32Magic == RTRANDINT_MAGIC, UINT64_MAX); + + /* forward the call */ + return pThis->pfnGetU64(pThis, 0, UINT64_MAX); +} +RT_EXPORT_SYMBOL(RTRandAdvU64); + + +DECLHIDDEN(DECLCALLBACK(void)) rtRandAdvSynthesizeBytesFromU32(PRTRANDINT pThis, uint8_t *pb, size_t cb) +{ + while (cb > 0) + { + uint32_t u32 = pThis->pfnGetU32(pThis, 0, UINT32_MAX); + switch (cb) + { + case 4: + pb[3] = (uint8_t)(u32 >> 24); RT_FALL_THRU(); + case 3: + pb[2] = (uint8_t)(u32 >> 16); RT_FALL_THRU(); + case 2: + pb[1] = (uint8_t)(u32 >> 8); RT_FALL_THRU(); + case 1: + pb[0] = (uint8_t)u32; + return; /* done */ + + default: + pb[0] = (uint8_t)u32; + pb[1] = (uint8_t)(u32 >> 8); + pb[2] = (uint8_t)(u32 >> 16); + pb[3] = (uint8_t)(u32 >> 24); + break; + } + + /* advance */ + cb -= 4; + pb += 4; + } +} + + +DECLHIDDEN(DECLCALLBACK(void)) rtRandAdvSynthesizeBytesFromU64(PRTRANDINT pThis, uint8_t *pb, size_t cb) +{ + while (cb > 0) + { + uint64_t u64 = pThis->pfnGetU64(pThis, 0, UINT64_MAX); + switch (cb) + { + case 8: + pb[7] = (uint8_t)(u64 >> 56); RT_FALL_THRU(); + case 7: + pb[6] = (uint8_t)(u64 >> 48); RT_FALL_THRU(); + case 6: + pb[5] = (uint8_t)(u64 >> 40); RT_FALL_THRU(); + case 5: + pb[4] = (uint8_t)(u64 >> 32); RT_FALL_THRU(); + case 4: + pb[3] = (uint8_t)(u64 >> 24); RT_FALL_THRU(); + case 3: + pb[2] = (uint8_t)(u64 >> 16); RT_FALL_THRU(); + case 2: + pb[1] = (uint8_t)(u64 >> 8); RT_FALL_THRU(); + case 1: + pb[0] = (uint8_t)u64; + return; /* done */ + + default: + pb[0] = (uint8_t)u64; + pb[1] = (uint8_t)(u64 >> 8); + pb[2] = (uint8_t)(u64 >> 16); + pb[3] = (uint8_t)(u64 >> 24); + pb[4] = (uint8_t)(u64 >> 32); + pb[5] = (uint8_t)(u64 >> 40); + pb[6] = (uint8_t)(u64 >> 48); + pb[7] = (uint8_t)(u64 >> 56); + break; + } + + /* advance */ + cb -= 8; + pb += 8; + } +} + + +DECLHIDDEN(DECLCALLBACK(uint32_t)) rtRandAdvSynthesizeU32FromBytes(PRTRANDINT pThis, uint32_t u32First, uint32_t u32Last) +{ + union + { + uint32_t off; + uint8_t ab[5]; + } u; + + const uint32_t offLast = u32Last - u32First; + if (offLast == UINT32_MAX) + /* get 4 random bytes and return them raw. */ + pThis->pfnGetBytes(pThis, &u.ab[0], sizeof(u.off)); + else if (!(offLast & UINT32_C(0xf0000000))) + { + /* get 4 random bytes and do simple squeeze. */ + pThis->pfnGetBytes(pThis, &u.ab[0], sizeof(u.off)); + u.off %= offLast + 1; + u.off += u32First; + } + else + { + /* get 5 random bytes and do shifted squeeze. (this ain't perfect) */ + pThis->pfnGetBytes(pThis, &u.ab[0], sizeof(u.ab)); + u.off %= (offLast >> 4) + 1; + u.off <<= 4; + u.off |= u.ab[4] & 0xf; + if (u.off > offLast) + u.off = offLast; + u.off += u32First; + } + return u.off; +} + + +DECLHIDDEN(DECLCALLBACK(uint32_t)) rtRandAdvSynthesizeU32FromU64(PRTRANDINT pThis, uint32_t u32First, uint32_t u32Last) +{ + return (uint32_t)pThis->pfnGetU64(pThis, u32First, u32Last); +} + + +DECLHIDDEN(DECLCALLBACK(uint64_t)) rtRandAdvSynthesizeU64FromBytes(PRTRANDINT pThis, uint64_t u64First, uint64_t u64Last) +{ + union + { + uint64_t off; + uint32_t off32; + uint8_t ab[9]; + } u; + + const uint64_t offLast = u64Last - u64First; + if (offLast == UINT64_MAX) + /* get 8 random bytes and return them raw. */ + pThis->pfnGetBytes(pThis, &u.ab[0], sizeof(u.off)); + else if (!(offLast & UINT64_C(0xf000000000000000))) + { + /* get 8 random bytes and do simple squeeze. */ + pThis->pfnGetBytes(pThis, &u.ab[0], sizeof(u.off)); + u.off %= offLast + 1; + u.off += u64First; + } + else + { + /* get 9 random bytes and do shifted squeeze. (this ain't perfect) */ + pThis->pfnGetBytes(pThis, &u.ab[0], sizeof(u.ab)); + u.off %= (offLast >> 4) + 1; + u.off <<= 4; + u.off |= u.ab[8] & 0xf; + if (u.off > offLast) + u.off = offLast; + u.off += u64First; + } + return u.off; +} + + +DECLHIDDEN(DECLCALLBACK(uint64_t)) rtRandAdvSynthesizeU64FromU32(PRTRANDINT pThis, uint64_t u64First, uint64_t u64Last) +{ + uint64_t off = u64Last - u64First; + if (off <= UINT32_MAX) + return (uint64_t)pThis->pfnGetU32(pThis, 0, (uint32_t)off) + u64First; + + return ( (uint64_t)pThis->pfnGetU32(pThis, 0, UINT32_MAX) + | ((uint64_t)pThis->pfnGetU32(pThis, 0, (uint32_t)(off >> 32)) << 32)) + + u64First; +} + + +/** @copydoc RTRANDINT::pfnSeed */ +DECLHIDDEN(DECLCALLBACK(int)) rtRandAdvStubSeed(PRTRANDINT pThis, uint64_t u64Seed) +{ + NOREF(pThis); + NOREF(u64Seed); + return VERR_NOT_SUPPORTED; +} + + +/** @copydoc RTRANDINT::pfnSaveState */ +DECLHIDDEN(DECLCALLBACK(int)) rtRandAdvStubSaveState(PRTRANDINT pThis, char *pszState, size_t *pcbState) +{ + NOREF(pThis); + NOREF(pszState); + NOREF(pcbState); + return VERR_NOT_SUPPORTED; +} + + +/** @copydoc RTRANDINT::pfnRestoreState */ +DECLHIDDEN(DECLCALLBACK(int)) rtRandAdvStubRestoreState(PRTRANDINT pThis, char const *pszState) +{ + NOREF(pThis); + NOREF(pszState); + return VERR_NOT_SUPPORTED; +} + + +/** @copydoc RTRANDINT::pfnDestroy */ +DECLHIDDEN(DECLCALLBACK(int)) rtRandAdvDefaultDestroy(PRTRANDINT pThis) +{ + pThis->u32Magic = ~RTRANDINT_MAGIC; + RTMemFree(pThis); + return VINF_SUCCESS; +} + diff --git a/src/VBox/Runtime/common/rand/randparkmiller.cpp b/src/VBox/Runtime/common/rand/randparkmiller.cpp new file mode 100644 index 00000000..538e8748 --- /dev/null +++ b/src/VBox/Runtime/common/rand/randparkmiller.cpp @@ -0,0 +1,210 @@ +/* $Id: randparkmiller.cpp $ */ +/** @file + * IPRT - Random Numbers, Park-Miller Pseudo Random. + */ + +/* + * Copyright (C) 2008-2020 Oracle Corporation + * + * This file is part of VirtualBox Open Source Edition (OSE), as + * available from http://www.virtualbox.org. This file is free software; + * you can redistribute it and/or modify it under the terms of the GNU + * General Public License (GPL) as published by the Free Software + * Foundation, in version 2 as it comes in the "COPYING" file of the + * VirtualBox OSE distribution. VirtualBox OSE is distributed in the + * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind. + * + * The contents of this file may alternatively be used under the terms + * of the Common Development and Distribution License Version 1.0 + * (CDDL) only, as it comes in the "COPYING.CDDL" file of the + * VirtualBox OSE distribution, in which case the provisions of the + * CDDL are applicable instead of those of the GPL. + * + * You may elect to license modified versions of this file under the + * terms and conditions of either the GPL or the CDDL or both. + */ + + +/********************************************************************************************************************************* +* Header Files * +*********************************************************************************************************************************/ +#include <iprt/rand.h> +#include "internal/iprt.h" + +#include <iprt/asm-math.h> +#include <iprt/mem.h> +#include <iprt/string.h> +#include <iprt/errcore.h> +#include "internal/rand.h" +#include "internal/magics.h" + + + +DECLINLINE(uint32_t) rtRandParkMillerU31(uint32_t *pu32Ctx) +{ + /* + * Park-Miller random number generator: + * X2 = X1 * g mod n. + * + * We use the constants suggested by Park and Miller: + * n = 2^31 - 1 = INT32_MAX + * g = 7^5 = 16807 + * + * This will produce numbers in the range [0..INT32_MAX-1], which is + * almost 31-bits. We'll ignore the missing number for now and settle + * for just filling in the missing bit instead (the caller does this). + */ + uint32_t x1 = *pu32Ctx; + if (!x1) + x1 = 20080806; + /*uint32_t x2 = ((uint64_t)x1 * 16807) % INT32_MAX;*/ + uint32_t x2 = ASMModU64ByU32RetU32(ASMMult2xU32RetU64(x1, 16807), INT32_MAX); + return *pu32Ctx = x2; +} + + +/** @copydoc RTRANDINT::pfnGetU32 */ +static DECLCALLBACK(uint32_t) rtRandParkMillerGetU32(PRTRANDINT pThis, uint32_t u32First, uint32_t u32Last) +{ + uint32_t off; + uint32_t offLast = u32Last - u32First; + if (offLast == UINT32_MAX) + { + /* 30 + 2 bit (make up for the missing INT32_MAX value) */ + off = rtRandParkMillerU31(&pThis->u.ParkMiller.u32Ctx); + if (pThis->u.ParkMiller.cBits < 2) + { + pThis->u.ParkMiller.u32Bits = rtRandParkMillerU31(&pThis->u.ParkMiller.u32Ctx); + pThis->u.ParkMiller.cBits = 30; + } + off >>= 1; + off |= (pThis->u.ParkMiller.u32Bits & 3) << 30; + pThis->u.ParkMiller.u32Bits >>= 2; + pThis->u.ParkMiller.cBits -= 2; + } + else if (offLast == (uint32_t)INT32_MAX - 1) + /* The exact range. */ + off = rtRandParkMillerU31(&pThis->u.ParkMiller.u32Ctx); + else if (offLast < UINT32_C(0x07ffffff)) + { + /* Requested 23 or fewer bits, just lose the lower bit. */ + off = rtRandParkMillerU31(&pThis->u.ParkMiller.u32Ctx); + off >>= 1; + off %= (offLast + 1); + } + else + { + /* + * 30 + 6 bits. + */ + uint64_t off64 = rtRandParkMillerU31(&pThis->u.ParkMiller.u32Ctx); + if (pThis->u.ParkMiller.cBits < 6) + { + pThis->u.ParkMiller.u32Bits = rtRandParkMillerU31(&pThis->u.ParkMiller.u32Ctx); + pThis->u.ParkMiller.cBits = 30; + } + off64 >>= 1; + off64 |= (uint64_t)(pThis->u.ParkMiller.u32Bits & 0x3f) << 30; + pThis->u.ParkMiller.u32Bits >>= 6; + pThis->u.ParkMiller.cBits -= 6; + off = ASMModU64ByU32RetU32(off64, offLast + 1); + } + return off + u32First; +} + + +/** @copydoc RTRANDINT::pfnSeed */ +static DECLCALLBACK(int) rtRandParkMillerSeed(PRTRANDINT pThis, uint64_t u64Seed) +{ + pThis->u.ParkMiller.u32Ctx = (uint32_t)u64Seed; + pThis->u.ParkMiller.u32Bits = 0; + pThis->u.ParkMiller.cBits = 0; + return VINF_SUCCESS; +} + + +/** @copydoc RTRANDINT::pfnSaveState */ +static DECLCALLBACK(int) rtRandParkMillerSaveState(PRTRANDINT pThis, char *pszState, size_t *pcbState) +{ +#define RTRAND_PARKMILLER_STATE_SIZE (3+8+1+8+1+2+1+1) + + if (*pcbState < RTRAND_PARKMILLER_STATE_SIZE) + { + *pcbState = RTRAND_PARKMILLER_STATE_SIZE; + return VERR_BUFFER_OVERFLOW; + } + RTStrPrintf(pszState, *pcbState, "PM:%08RX32,%08RX32,%02x;", + pThis->u.ParkMiller.u32Ctx, + pThis->u.ParkMiller.u32Bits, + pThis->u.ParkMiller.cBits); + return VINF_SUCCESS; +} + + +/** @copydoc RTRANDINT::pfnRestoreState */ +static DECLCALLBACK(int) rtRandParkMillerRestoreState(PRTRANDINT pThis, char const *pszState) +{ + /* marker */ + if ( pszState[0] != 'P' + || pszState[1] != 'M' + || pszState[2] != ':') + return VERR_PARSE_ERROR; + pszState += 3; + + /* u32Ctx */ + char *pszNext = NULL; + uint32_t u32Ctx; + int rc = RTStrToUInt32Ex(pszState, &pszNext, 16, &u32Ctx); + if ( rc != VWRN_TRAILING_CHARS + || pszNext != pszState + 8 + || *pszNext != ',') + return VERR_PARSE_ERROR; + pszState += 8 + 1; + + /* u32Bits */ + uint32_t u32Bits; + rc = RTStrToUInt32Ex(pszState, &pszNext, 16, &u32Bits); + if ( rc != VWRN_TRAILING_CHARS + || pszNext != pszState + 8 + || *pszNext != ',') + return VERR_PARSE_ERROR; + pszState += 8 + 1; + + /* cBits */ + uint32_t cBits; + rc = RTStrToUInt32Ex(pszState, &pszNext, 16, &cBits); + if ( rc != VWRN_TRAILING_CHARS + || pszNext != pszState + 2 + || *pszNext != ';' + || pszNext[1] != '\0') + return VERR_PARSE_ERROR; + + /* commit */ + pThis->u.ParkMiller.u32Ctx = u32Ctx; + pThis->u.ParkMiller.u32Bits = u32Bits; + pThis->u.ParkMiller.cBits = cBits; + return VINF_SUCCESS; +} + + +RTDECL(int) RTRandAdvCreateParkMiller(PRTRAND phRand) RT_NO_THROW_DEF +{ + PRTRANDINT pThis = (PRTRANDINT)RTMemAlloc(sizeof(*pThis)); + if (!pThis) + return VERR_NO_MEMORY; + pThis->u32Magic = RTRANDINT_MAGIC; + pThis->pfnGetBytes= rtRandAdvSynthesizeBytesFromU32; + pThis->pfnGetU32 = rtRandParkMillerGetU32; + pThis->pfnGetU64 = rtRandAdvSynthesizeU64FromU32; + pThis->pfnSeed = rtRandParkMillerSeed; + pThis->pfnSaveState = rtRandParkMillerSaveState; + pThis->pfnRestoreState = rtRandParkMillerRestoreState; + pThis->pfnDestroy = rtRandAdvDefaultDestroy; + pThis->u.ParkMiller.u32Ctx = 0x20080806; + pThis->u.ParkMiller.u32Bits = 0; + pThis->u.ParkMiller.cBits = 0; + *phRand = pThis; + return VINF_SUCCESS; +} +RT_EXPORT_SYMBOL(RTRandAdvCreateParkMiller); + |