6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync/* $Id$ */
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync/** @file
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * IPRT - Random Numbers, Park-Miller Pseudo Random.
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync */
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync/*
c7814cf6e1240a519cbec0441e033d0e2470ed00vboxsync * Copyright (C) 2008-2012 Oracle Corporation
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync *
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * This file is part of VirtualBox Open Source Edition (OSE), as
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * available from http://www.virtualbox.org. This file is free software;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * you can redistribute it and/or modify it under the terms of the GNU
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * General Public License (GPL) as published by the Free Software
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * Foundation, in version 2 as it comes in the "COPYING" file of the
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync *
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * The contents of this file may alternatively be used under the terms
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * of the Common Development and Distribution License Version 1.0
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * VirtualBox OSE distribution, in which case the provisions of the
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * CDDL are applicable instead of those of the GPL.
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync *
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * You may elect to license modified versions of this file under the
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * terms and conditions of either the GPL or the CDDL or both.
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync */
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync/*******************************************************************************
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync* Header Files *
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync*******************************************************************************/
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync#include <iprt/rand.h>
aa4bcf0a4b2db3ac352b56a291d49cb8d4b66d32vboxsync#include "internal/iprt.h"
aa4bcf0a4b2db3ac352b56a291d49cb8d4b66d32vboxsync
2f0d866e126dd288169fed591c259c1c6b4016e5vboxsync#include <iprt/asm-math.h>
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync#include <iprt/mem.h>
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync#include <iprt/string.h>
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync#include <iprt/err.h>
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync#include "internal/rand.h"
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync#include "internal/magics.h"
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsyncDECLINLINE(uint32_t) rtRandParkMillerU31(uint32_t *pu32Ctx)
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync{
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync /*
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * Park-Miller random number generator:
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * X2 = X1 * g mod n.
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync *
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * We use the constants suggested by Park and Miller:
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * n = 2^31 - 1 = INT32_MAX
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * g = 7^5 = 16807
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync *
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * This will produce numbers in the range [0..INT32_MAX-1], which is
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * almost 31-bits. We'll ignore the missing number for now and settle
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * for just filling in the missing bit instead (the caller does this).
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync */
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync uint32_t x1 = *pu32Ctx;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync if (!x1)
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync x1 = 20080806;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync /*uint32_t x2 = ((uint64_t)x1 * 16807) % INT32_MAX;*/
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync uint32_t x2 = ASMModU64ByU32RetU32(ASMMult2xU32RetU64(x1, 16807), INT32_MAX);
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync return *pu32Ctx = x2;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync}
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync/** @copydoc RTRANDINT::pfnGetU32 */
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsyncstatic DECLCALLBACK(uint32_t) rtRandParkMillerGetU32(PRTRANDINT pThis, uint32_t u32First, uint32_t u32Last)
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync{
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync uint32_t off;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync uint32_t offLast = u32Last - u32First;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync if (offLast == UINT32_MAX)
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync {
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync /* 30 + 2 bit (make up for the missing INT32_MAX value) */
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync off = rtRandParkMillerU31(&pThis->u.ParkMiller.u32Ctx);
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync if (pThis->u.ParkMiller.cBits < 2)
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync {
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync pThis->u.ParkMiller.u32Bits = rtRandParkMillerU31(&pThis->u.ParkMiller.u32Ctx);
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync pThis->u.ParkMiller.cBits = 30;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync }
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync off >>= 1;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync off |= (pThis->u.ParkMiller.u32Bits & 3) << 30;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync pThis->u.ParkMiller.u32Bits >>= 2;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync pThis->u.ParkMiller.cBits -= 2;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync }
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync else if (offLast == (uint32_t)INT32_MAX - 1)
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync /* The exact range. */
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync off = rtRandParkMillerU31(&pThis->u.ParkMiller.u32Ctx);
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync else if (offLast < UINT32_C(0x07ffffff))
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync {
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync /* Requested 23 or fewer bits, just lose the lower bit. */
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync off = rtRandParkMillerU31(&pThis->u.ParkMiller.u32Ctx);
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync off >>= 1;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync off %= (offLast + 1);
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync }
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync else
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync {
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync /*
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync * 30 + 6 bits.
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync */
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync uint64_t off64 = rtRandParkMillerU31(&pThis->u.ParkMiller.u32Ctx);
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync if (pThis->u.ParkMiller.cBits < 6)
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync {
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync pThis->u.ParkMiller.u32Bits = rtRandParkMillerU31(&pThis->u.ParkMiller.u32Ctx);
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync pThis->u.ParkMiller.cBits = 30;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync }
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync off64 >>= 1;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync off64 |= (uint64_t)(pThis->u.ParkMiller.u32Bits & 0x3f) << 30;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync pThis->u.ParkMiller.u32Bits >>= 6;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync pThis->u.ParkMiller.cBits -= 6;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync off = ASMModU64ByU32RetU32(off64, offLast + 1);
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync }
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync return off + u32First;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync}
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync/** @copydoc RTRANDINT::pfnSeed */
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsyncstatic DECLCALLBACK(int) rtRandParkMillerSeed(PRTRANDINT pThis, uint64_t u64Seed)
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync{
d43ce0928d131e4008cb9a0e4b67e5967cf6c6afvboxsync pThis->u.ParkMiller.u32Ctx = (uint32_t)u64Seed;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync pThis->u.ParkMiller.u32Bits = 0;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync pThis->u.ParkMiller.cBits = 0;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync return VINF_SUCCESS;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync}
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync/** @copydoc RTRANDINT::pfnSaveState */
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsyncstatic DECLCALLBACK(int) rtRandParkMillerSaveState(PRTRANDINT pThis, char *pszState, size_t *pcbState)
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync{
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync#define RTRAND_PARKMILLER_STATE_SIZE (3+8+1+8+1+2+1+1)
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync if (*pcbState < RTRAND_PARKMILLER_STATE_SIZE)
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync {
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync *pcbState = RTRAND_PARKMILLER_STATE_SIZE;
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync return VERR_BUFFER_OVERFLOW;
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync }
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync RTStrPrintf(pszState, *pcbState, "PM:%08RX32,%08RX32,%02x;",
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync pThis->u.ParkMiller.u32Ctx,
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync pThis->u.ParkMiller.u32Bits,
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync pThis->u.ParkMiller.cBits);
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync return VINF_SUCCESS;
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync}
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync/** @copydoc RTRANDINT::pfnRestoreState */
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsyncstatic DECLCALLBACK(int) rtRandParkMillerRestoreState(PRTRANDINT pThis, char const *pszState)
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync{
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync /* marker */
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync if ( pszState[0] != 'P'
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync || pszState[1] != 'M'
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync || pszState[2] != ':')
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync return VERR_PARSE_ERROR;
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync pszState += 3;
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync /* u32Ctx */
210e87cc03f92d54681b81a81cc1fdbd48a9d2c8vboxsync char *pszNext = NULL;
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync uint32_t u32Ctx;
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync int rc = RTStrToUInt32Ex(pszState, &pszNext, 16, &u32Ctx);
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync if ( rc != VWRN_TRAILING_CHARS
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync || pszNext != pszState + 8
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync || *pszNext != ',')
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync return VERR_PARSE_ERROR;
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync pszState += 8 + 1;
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync /* u32Bits */
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync uint32_t u32Bits;
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync rc = RTStrToUInt32Ex(pszState, &pszNext, 16, &u32Bits);
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync if ( rc != VWRN_TRAILING_CHARS
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync || pszNext != pszState + 8
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync || *pszNext != ',')
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync return VERR_PARSE_ERROR;
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync pszState += 8 + 1;
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync /* cBits */
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync uint32_t cBits;
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync rc = RTStrToUInt32Ex(pszState, &pszNext, 16, &cBits);
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync if ( rc != VWRN_TRAILING_CHARS
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync || pszNext != pszState + 2
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync || *pszNext != ';'
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync || pszNext[1] != '\0')
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync return VERR_PARSE_ERROR;
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync /* commit */
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync pThis->u.ParkMiller.u32Ctx = u32Ctx;
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync pThis->u.ParkMiller.u32Bits = u32Bits;
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync pThis->u.ParkMiller.cBits = cBits;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync return VINF_SUCCESS;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync}
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsyncRTDECL(int) RTRandAdvCreateParkMiller(PRTRAND phRand) RT_NO_THROW
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync{
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync PRTRANDINT pThis = (PRTRANDINT)RTMemAlloc(sizeof(*pThis));
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync if (!pThis)
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync return VERR_NO_MEMORY;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync pThis->u32Magic = RTRANDINT_MAGIC;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync pThis->pfnGetBytes= rtRandAdvSynthesizeBytesFromU32;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync pThis->pfnGetU32 = rtRandParkMillerGetU32;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync pThis->pfnGetU64 = rtRandAdvSynthesizeU64FromU32;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync pThis->pfnSeed = rtRandParkMillerSeed;
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync pThis->pfnSaveState = rtRandParkMillerSaveState;
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync pThis->pfnRestoreState = rtRandParkMillerRestoreState;
062b8a43e237d9e2edde03b5837d44506e35eb47vboxsync pThis->pfnDestroy = rtRandAdvDefaultDestroy;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync pThis->u.ParkMiller.u32Ctx = 0x20080806;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync pThis->u.ParkMiller.u32Bits = 0;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync pThis->u.ParkMiller.cBits = 0;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync *phRand = pThis;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync return VINF_SUCCESS;
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync}
aa4bcf0a4b2db3ac352b56a291d49cb8d4b66d32vboxsyncRT_EXPORT_SYMBOL(RTRandAdvCreateParkMiller);
6fea4abcc6ee0f2797ac01ef79c374d506aedc02vboxsync